IntegerDivision.cpp Source File (original) (raw)

22using namespace llvm;

24#define DEBUG_TYPE "integer-division"

49 Dividend = Builder.CreateFreeze(Dividend);

50 Divisor = Builder.CreateFreeze(Divisor);

51 Value *DividendSign = Builder.CreateAShr(Dividend, Shift);

52 Value *DivisorSign = Builder.CreateAShr(Divisor, Shift);

53 Value *DvdXor = Builder.CreateXor(Dividend, DividendSign);

54 Value *DvsXor = Builder.CreateXor(Divisor, DivisorSign);

55 Value *UDividend = Builder.CreateSub(DvdXor, DividendSign);

56 Value *UDivisor = Builder.CreateSub(DvsXor, DivisorSign);

57 Value *URem = Builder.CreateURem(UDividend, UDivisor);

58 Value *Xored = Builder.CreateXor(URem, DividendSign);

59 Value *SRem = Builder.CreateSub(Xored, DividendSign);

62 Builder.SetInsertPoint(URemInst);

64 return SRem;

65}

82 Dividend = Builder.CreateFreeze(Dividend);

83 Divisor = Builder.CreateFreeze(Divisor);

84 Value *Quotient = Builder.CreateUDiv(Dividend, Divisor);

85 Value *Product = Builder.CreateMul(Divisor, Quotient);

86 Value *Remainder = Builder.CreateSub(Dividend, Product);

89 Builder.SetInsertPoint(UDiv);

91 return Remainder;

92}

101

102

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119 Dividend = Builder.CreateFreeze(Dividend);

120 Divisor = Builder.CreateFreeze(Divisor);

121 Value *Tmp = Builder.CreateAShr(Dividend, Shift);

122 Value *Tmp1 = Builder.CreateAShr(Divisor, Shift);

123 Value *Tmp2 = Builder.CreateXor(Tmp, Dividend);

124 Value *U_Dvnd = Builder.CreateSub(Tmp2, Tmp);

125 Value *Tmp3 = Builder.CreateXor(Tmp1, Divisor);

126 Value *U_Dvsr = Builder.CreateSub(Tmp3, Tmp1);

127 Value *Q_Sgn = Builder.CreateXor(Tmp1, Tmp);

128 Value *Q_Mag = Builder.CreateUDiv(U_Dvnd, U_Dvsr);

129 Value *Tmp4 = Builder.CreateXor(Q_Mag, Q_Sgn);

130 Value *Q = Builder.CreateSub(Tmp4, Q_Sgn);

131

133 Builder.SetInsertPoint(UDiv);

134

135 return Q;

136}

137

138

139

140

143

144

145

146

147

150

151 ConstantInt *Zero = ConstantInt::get(DivTy, 0);

152 ConstantInt *One = ConstantInt::get(DivTy, 1);

155

157

158 BasicBlock *IBB = Builder.GetInsertBlock();

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195 BasicBlock *SpecialCases = Builder.GetInsertBlock();

196 SpecialCases->setName(Twine(SpecialCases->getName(), "_udiv-special-cases"));

198 "udiv-end");

200 "udiv-loop-exit", F, End);

202 "udiv-do-while", F, End);

204 "udiv-preheader", F, End);

206 "udiv-bb1", F, End);

207

208

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228 Builder.SetInsertPoint(SpecialCases);

229 Divisor = Builder.CreateFreeze(Divisor);

230 Dividend = Builder.CreateFreeze(Dividend);

231 Value *Ret0_1 = Builder.CreateICmpEQ(Divisor, Zero);

232 Value *Ret0_2 = Builder.CreateICmpEQ(Dividend, Zero);

233 Value *Ret0_3 = Builder.CreateOr(Ret0_1, Ret0_2);

234 Value *Tmp0 = Builder.CreateCall(CTLZ, {Divisor, True});

235 Value *Tmp1 = Builder.CreateCall(CTLZ, {Dividend, True});

236 Value *SR = Builder.CreateSub(Tmp0, Tmp1);

237 Value *Ret0_4 = Builder.CreateICmpUGT(SR, MSB);

238 Value *Ret0 = Builder.CreateLogicalOr(Ret0_3, Ret0_4);

239 Value *RetDividend = Builder.CreateICmpEQ(SR, MSB);

240 Value *RetVal = Builder.CreateSelect(Ret0, Zero, Dividend);

241 Value *EarlyRet = Builder.CreateLogicalOr(Ret0, RetDividend);

242 Builder.CreateCondBr(EarlyRet, End, BB1);

243

244

245

246

247

248

249

250 Builder.SetInsertPoint(BB1);

251 Value *SR_1 = Builder.CreateAdd(SR, One);

252 Value *Tmp2 = Builder.CreateSub(MSB, SR);

253 Value *Q = Builder.CreateShl(Dividend, Tmp2);

254 Value *SkipLoop = Builder.CreateICmpEQ(SR_1, Zero);

255 Builder.CreateCondBr(SkipLoop, LoopExit, Preheader);

256

257

258

259

260

261 Builder.SetInsertPoint(Preheader);

262 Value *Tmp3 = Builder.CreateLShr(Dividend, SR_1);

263 Value *Tmp4 = Builder.CreateAdd(Divisor, NegOne);

264 Builder.CreateBr(DoWhile);

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284 Builder.SetInsertPoint(DoWhile);

285 PHINode *Carry_1 = Builder.CreatePHI(DivTy, 2);

286 PHINode *SR_3 = Builder.CreatePHI(DivTy, 2);

287 PHINode *R_1 = Builder.CreatePHI(DivTy, 2);

288 PHINode *Q_2 = Builder.CreatePHI(DivTy, 2);

289 Value *Tmp5 = Builder.CreateShl(R_1, One);

290 Value *Tmp6 = Builder.CreateLShr(Q_2, MSB);

291 Value *Tmp7 = Builder.CreateOr(Tmp5, Tmp6);

292 Value *Tmp8 = Builder.CreateShl(Q_2, One);

293 Value *Q_1 = Builder.CreateOr(Carry_1, Tmp8);

294 Value *Tmp9 = Builder.CreateSub(Tmp4, Tmp7);

295 Value *Tmp10 = Builder.CreateAShr(Tmp9, MSB);

296 Value *Carry = Builder.CreateAnd(Tmp10, One);

297 Value *Tmp11 = Builder.CreateAnd(Tmp10, Divisor);

298 Value *R = Builder.CreateSub(Tmp7, Tmp11);

299 Value *SR_2 = Builder.CreateAdd(SR_3, NegOne);

300 Value *Tmp12 = Builder.CreateICmpEQ(SR_2, Zero);

301 Builder.CreateCondBr(Tmp12, LoopExit, DoWhile);

302

303

304

305

306

307

308

309 Builder.SetInsertPoint(LoopExit);

310 PHINode *Carry_2 = Builder.CreatePHI(DivTy, 2);

311 PHINode *Q_3 = Builder.CreatePHI(DivTy, 2);

312 Value *Tmp13 = Builder.CreateShl(Q_3, One);

313 Value *Q_4 = Builder.CreateOr(Carry_2, Tmp13);

314 Builder.CreateBr(End);

315

316

317

318

319 Builder.SetInsertPoint(End, End->begin());

320 PHINode *Q_5 = Builder.CreatePHI(DivTy, 2);

321

322

323

326

329

332

335

338

341

344

345 return Q_5;

346}

347

348

349

350

351

352

353

356 Rem->getOpcode() == Instruction::URem) &&

357 "Trying to expand remainder from a non-remainder function");

358

360

362

363

364 if (Rem->getOpcode() == Instruction::SRem) {

367

368

369 bool IsInsertPoint = Rem->getIterator() == Builder.GetInsertPoint();

373

374

375

376

377 if (IsInsertPoint)

378 return true;

379

381 Rem = BO;

382 }

383

386

390

391

393 assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?");

395 }

396

397 return true;

398}

399

400

401

402

403

404

405

408 Div->getOpcode() == Instruction::UDiv) &&

409 "Trying to expand division from a non-division function");

410

412

414

415

416 if (Div->getOpcode() == Instruction::SDiv) {

417

420

421

422 bool IsInsertPoint = Div->getIterator() == Builder.GetInsertPoint();

426

427

428

429

430 if (IsInsertPoint)

431 return true;

432

434 Div = BO;

435 }

436

437

440 Builder);

444

445 return true;

446}

447

448

449

450

451

452

453

454

457 Rem->getOpcode() == Instruction::URem) &&

458 "Trying to expand remainder from a non-remainder function");

459

461 assert(!RemTy->isVectorTy() && "Div over vectors not supported");

462

464

465 assert(RemTyBitWidth <= 32 &&

466 "Div of bitwidth greater than 32 not supported");

467

468 if (RemTyBitWidth == 32)

470

471

472

474

475 Value *ExtDividend;

476 Value *ExtDivisor;

480

481 if (Rem->getOpcode() == Instruction::SRem) {

484 ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);

485 } else {

488 ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);

489 }

490 Trunc = Builder.CreateTrunc(ExtRem, RemTy);

491

495

497}

498

499

500

501

502

503

506 Rem->getOpcode() == Instruction::URem) &&

507 "Trying to expand remainder from a non-remainder function");

508

510 assert(!RemTy->isVectorTy() && "Div over vectors not supported");

511

513

514 if (RemTyBitWidth >= 64)

516

517

518

520

521 Value *ExtDividend;

522 Value *ExtDivisor;

526

527 if (Rem->getOpcode() == Instruction::SRem) {

528 ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int64Ty);

529 ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int64Ty);

530 ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);

531 } else {

532 ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int64Ty);

533 ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int64Ty);

534 ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);

535 }

536 Trunc = Builder.CreateTrunc(ExtRem, RemTy);

537

541

543}

544

545

546

547

548

549

550

553 Div->getOpcode() == Instruction::UDiv) &&

554 "Trying to expand division from a non-division function");

555

557 assert(!DivTy->isVectorTy() && "Div over vectors not supported");

558

560

561 assert(DivTyBitWidth <= 32 && "Div of bitwidth greater than 32 not supported");

562

563 if (DivTyBitWidth == 32)

565

566

567

569

570 Value *ExtDividend;

571 Value *ExtDivisor;

575

576 if (Div->getOpcode() == Instruction::SDiv) {

579 ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);

580 } else {

583 ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);

584 }

585 Trunc = Builder.CreateTrunc(ExtDiv, DivTy);

586

590

592}

593

594

595

596

597

598

601 Div->getOpcode() == Instruction::UDiv) &&

602 "Trying to expand division from a non-division function");

603

605 assert(!DivTy->isVectorTy() && "Div over vectors not supported");

606

608

609 if (DivTyBitWidth >= 64)

611

612

613

615

616 Value *ExtDividend;

617 Value *ExtDivisor;

621

622 if (Div->getOpcode() == Instruction::SDiv) {

623 ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int64Ty);

624 ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int64Ty);

625 ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);

626 } else {

627 ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int64Ty);

628 ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int64Ty);

629 ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);

630 }

631 Trunc = Builder.CreateTrunc(ExtDiv, DivTy);

632

636

638}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

static Value * generateSignedDivisionCode(Value *Dividend, Value *Divisor, IRBuilder<> &Builder)

Generate code to divide two signed integers.

Definition IntegerDivision.cpp:99

static Value * generateUnsignedRemainderCode(Value *Dividend, Value *Divisor, IRBuilder<> &Builder)

Generate code to compute the remainder of two unsigned integers.

Definition IntegerDivision.cpp:73

static Value * generateSignedRemainderCode(Value *Dividend, Value *Divisor, IRBuilder<> &Builder)

Generate code to compute the remainder of two signed integers.

Definition IntegerDivision.cpp:32

static Value * generateUnsignedDivisionCode(Value *Dividend, Value *Divisor, IRBuilder<> &Builder)

Generates code to divide two unsigned scalar 32-bit or 64-bit integers.

Definition IntegerDivision.cpp:141

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

const Function * getParent() const

Return the enclosing method, or null if none.

static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)

Creates a new BasicBlock.

LLVM_ABI BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)

Split the basic block into two basic blocks at the specified instruction.

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

BinaryOps getOpcode() const

This is the shared class of boolean and integer constants.

static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)

static ConstantInt * getSigned(IntegerType *Ty, int64_t V)

Return a ConstantInt with the specified value for the specified type.

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

LLVM_ABI InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

Class to represent integer types.

unsigned getBitWidth() const

Get the number of bits in this IntegerType.

void addIncoming(Value *V, BasicBlock *BB)

Add an incoming value to the end of the PHI list.

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

The instances of the Type class are immutable: once they are created, they are never changed.

static LLVM_ABI IntegerType * getInt64Ty(LLVMContext &C)

LLVM_ABI unsigned getIntegerBitWidth() const

bool isVectorTy() const

True if this is an instance of VectorType.

void dropAllReferences()

Drop all references to operands.

Value * getOperand(unsigned i) const

LLVM Value Representation.

Type * getType() const

All values are typed, get the type of this value.

LLVM_ABI void setName(const Twine &Name)

Change the name of the value.

LLVM_ABI void replaceAllUsesWith(Value *V)

Change all uses of this to point to a new Value.

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

self_iterator getIterator()

LLVM_ABI Function * getOrInsertDeclaration(Module *M, ID id, ArrayRef< Type * > Tys={})

Look up the Function declaration of the intrinsic id in the Module M.

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI bool expandDivision(BinaryOperator *Div)

Generate code to divide two integers, replacing Div with the generated code.

Definition IntegerDivision.cpp:406

LLVM_ABI bool expandRemainderUpTo32Bits(BinaryOperator *Rem)

Generate code to calculate the remainder of two integers, replacing Rem with the generated code.

Definition IntegerDivision.cpp:455

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

FunctionAddr VTableAddr uintptr_t uintptr_t Int32Ty

LLVM_ABI bool expandRemainderUpTo64Bits(BinaryOperator *Rem)

Generate code to calculate the remainder of two integers, replacing Rem with the generated code.

Definition IntegerDivision.cpp:504

LLVM_ABI bool expandDivisionUpTo64Bits(BinaryOperator *Div)

Generate code to divide two integers, replacing Div with the generated code.

Definition IntegerDivision.cpp:599

LLVM_ABI bool expandDivisionUpTo32Bits(BinaryOperator *Div)

Generate code to divide two integers, replacing Div with the generated code.

Definition IntegerDivision.cpp:551

constexpr unsigned BitWidth

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

LLVM_ABI bool expandRemainder(BinaryOperator *Rem)

Generate code to calculate the remainder of two integers, replacing Rem with the generated code.

Definition IntegerDivision.cpp:354