1 //===-- IntegerDivision.cpp - Expand integer division ---------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains an implementation of 32bit and 64bit scalar integer
11 // division for targets that don't have native support. It's largely derived
12 // from compiler-rt's implementations of __udivsi3 and __udivmoddi4,
13 // but hand-tuned for targets that prefer less control flow.
15 //===----------------------------------------------------------------------===//
17 #include "llvm/Transforms/Utils/IntegerDivision.h"
18 #include "llvm/IR/Function.h"
19 #include "llvm/IR/IRBuilder.h"
20 #include "llvm/IR/Instructions.h"
21 #include "llvm/IR/Intrinsics.h"
26 #define DEBUG_TYPE "integer-division"
28 /// Generate code to compute the remainder of two signed integers. Returns the
29 /// remainder, which will have the sign of the dividend. Builder's insert point
30 /// should be pointing where the caller wants code generated, e.g. at the srem
31 /// instruction. This will generate a urem in the process, and Builder's insert
32 /// point will be pointing at the uren (if present, i.e. not folded), ready to
33 /// be expanded if the user wishes
34 static Value *generateSignedRemainderCode(Value *Dividend, Value *Divisor,
35 IRBuilder<> &Builder) {
36 unsigned BitWidth = Dividend->getType()->getIntegerBitWidth();
40 Shift = Builder.getInt64(63);
42 assert(BitWidth == 32 && "Unexpected bit width");
43 Shift = Builder.getInt32(31);
46 // Following instructions are generated for both i32 (shift 31) and
49 // ; %dividend_sgn = ashr i32 %dividend, 31
50 // ; %divisor_sgn = ashr i32 %divisor, 31
51 // ; %dvd_xor = xor i32 %dividend, %dividend_sgn
52 // ; %dvs_xor = xor i32 %divisor, %divisor_sgn
53 // ; %u_dividend = sub i32 %dvd_xor, %dividend_sgn
54 // ; %u_divisor = sub i32 %dvs_xor, %divisor_sgn
55 // ; %urem = urem i32 %dividend, %divisor
56 // ; %xored = xor i32 %urem, %dividend_sgn
57 // ; %srem = sub i32 %xored, %dividend_sgn
58 Value *DividendSign = Builder.CreateAShr(Dividend, Shift);
59 Value *DivisorSign = Builder.CreateAShr(Divisor, Shift);
60 Value *DvdXor = Builder.CreateXor(Dividend, DividendSign);
61 Value *DvsXor = Builder.CreateXor(Divisor, DivisorSign);
62 Value *UDividend = Builder.CreateSub(DvdXor, DividendSign);
63 Value *UDivisor = Builder.CreateSub(DvsXor, DivisorSign);
64 Value *URem = Builder.CreateURem(UDividend, UDivisor);
65 Value *Xored = Builder.CreateXor(URem, DividendSign);
66 Value *SRem = Builder.CreateSub(Xored, DividendSign);
68 if (Instruction *URemInst = dyn_cast<Instruction>(URem))
69 Builder.SetInsertPoint(URemInst);
75 /// Generate code to compute the remainder of two unsigned integers. Returns the
76 /// remainder. Builder's insert point should be pointing where the caller wants
77 /// code generated, e.g. at the urem instruction. This will generate a udiv in
78 /// the process, and Builder's insert point will be pointing at the udiv (if
79 /// present, i.e. not folded), ready to be expanded if the user wishes
80 static Value *generatedUnsignedRemainderCode(Value *Dividend, Value *Divisor,
81 IRBuilder<> &Builder) {
82 // Remainder = Dividend - Quotient*Divisor
84 // Following instructions are generated for both i32 and i64
86 // ; %quotient = udiv i32 %dividend, %divisor
87 // ; %product = mul i32 %divisor, %quotient
88 // ; %remainder = sub i32 %dividend, %product
89 Value *Quotient = Builder.CreateUDiv(Dividend, Divisor);
90 Value *Product = Builder.CreateMul(Divisor, Quotient);
91 Value *Remainder = Builder.CreateSub(Dividend, Product);
93 if (Instruction *UDiv = dyn_cast<Instruction>(Quotient))
94 Builder.SetInsertPoint(UDiv);
99 /// Generate code to divide two signed integers. Returns the quotient, rounded
100 /// towards 0. Builder's insert point should be pointing where the caller wants
101 /// code generated, e.g. at the sdiv instruction. This will generate a udiv in
102 /// the process, and Builder's insert point will be pointing at the udiv (if
103 /// present, i.e. not folded), ready to be expanded if the user wishes.
104 static Value *generateSignedDivisionCode(Value *Dividend, Value *Divisor,
105 IRBuilder<> &Builder) {
106 // Implementation taken from compiler-rt's __divsi3 and __divdi3
108 unsigned BitWidth = Dividend->getType()->getIntegerBitWidth();
111 if (BitWidth == 64) {
112 Shift = Builder.getInt64(63);
114 assert(BitWidth == 32 && "Unexpected bit width");
115 Shift = Builder.getInt32(31);
118 // Following instructions are generated for both i32 (shift 31) and
121 // ; %tmp = ashr i32 %dividend, 31
122 // ; %tmp1 = ashr i32 %divisor, 31
123 // ; %tmp2 = xor i32 %tmp, %dividend
124 // ; %u_dvnd = sub nsw i32 %tmp2, %tmp
125 // ; %tmp3 = xor i32 %tmp1, %divisor
126 // ; %u_dvsr = sub nsw i32 %tmp3, %tmp1
127 // ; %q_sgn = xor i32 %tmp1, %tmp
128 // ; %q_mag = udiv i32 %u_dvnd, %u_dvsr
129 // ; %tmp4 = xor i32 %q_mag, %q_sgn
130 // ; %q = sub i32 %tmp4, %q_sgn
131 Value *Tmp = Builder.CreateAShr(Dividend, Shift);
132 Value *Tmp1 = Builder.CreateAShr(Divisor, Shift);
133 Value *Tmp2 = Builder.CreateXor(Tmp, Dividend);
134 Value *U_Dvnd = Builder.CreateSub(Tmp2, Tmp);
135 Value *Tmp3 = Builder.CreateXor(Tmp1, Divisor);
136 Value *U_Dvsr = Builder.CreateSub(Tmp3, Tmp1);
137 Value *Q_Sgn = Builder.CreateXor(Tmp1, Tmp);
138 Value *Q_Mag = Builder.CreateUDiv(U_Dvnd, U_Dvsr);
139 Value *Tmp4 = Builder.CreateXor(Q_Mag, Q_Sgn);
140 Value *Q = Builder.CreateSub(Tmp4, Q_Sgn);
142 if (Instruction *UDiv = dyn_cast<Instruction>(Q_Mag))
143 Builder.SetInsertPoint(UDiv);
148 /// Generates code to divide two unsigned scalar 32-bit or 64-bit integers.
149 /// Returns the quotient, rounded towards 0. Builder's insert point should
150 /// point where the caller wants code generated, e.g. at the udiv instruction.
151 static Value *generateUnsignedDivisionCode(Value *Dividend, Value *Divisor,
152 IRBuilder<> &Builder) {
153 // The basic algorithm can be found in the compiler-rt project's
154 // implementation of __udivsi3.c. Here, we do a lower-level IR based approach
155 // that's been hand-tuned to lessen the amount of control flow involved.
157 // Some helper values
158 IntegerType *DivTy = cast<IntegerType>(Dividend->getType());
159 unsigned BitWidth = DivTy->getBitWidth();
166 if (BitWidth == 64) {
167 Zero = Builder.getInt64(0);
168 One = Builder.getInt64(1);
169 NegOne = ConstantInt::getSigned(DivTy, -1);
170 MSB = Builder.getInt64(63);
172 assert(BitWidth == 32 && "Unexpected bit width");
173 Zero = Builder.getInt32(0);
174 One = Builder.getInt32(1);
175 NegOne = ConstantInt::getSigned(DivTy, -1);
176 MSB = Builder.getInt32(31);
179 ConstantInt *True = Builder.getTrue();
181 BasicBlock *IBB = Builder.GetInsertBlock();
182 Function *F = IBB->getParent();
183 Function *CTLZ = Intrinsic::getDeclaration(F->getParent(), Intrinsic::ctlz,
186 // Our CFG is going to look like:
187 // +---------------------+
190 // +---------------------+
197 // | | +------------+
200 // | | +------------+
204 // | | +------------+ |
205 // | | | do-while | |
207 // | | +------------+ |
209 // | +-----------+ +---+
218 BasicBlock *SpecialCases = Builder.GetInsertBlock();
219 SpecialCases->setName(Twine(SpecialCases->getName(), "_udiv-special-cases"));
220 BasicBlock *End = SpecialCases->splitBasicBlock(Builder.GetInsertPoint(),
222 BasicBlock *LoopExit = BasicBlock::Create(Builder.getContext(),
223 "udiv-loop-exit", F, End);
224 BasicBlock *DoWhile = BasicBlock::Create(Builder.getContext(),
225 "udiv-do-while", F, End);
226 BasicBlock *Preheader = BasicBlock::Create(Builder.getContext(),
227 "udiv-preheader", F, End);
228 BasicBlock *BB1 = BasicBlock::Create(Builder.getContext(),
231 // We'll be overwriting the terminator to insert our extra blocks
232 SpecialCases->getTerminator()->eraseFromParent();
234 // Same instructions are generated for both i32 (msb 31) and i64 (msb 63).
236 // First off, check for special cases: dividend or divisor is zero, divisor
237 // is greater than dividend, and divisor is 1.
239 // ; %ret0_1 = icmp eq i32 %divisor, 0
240 // ; %ret0_2 = icmp eq i32 %dividend, 0
241 // ; %ret0_3 = or i1 %ret0_1, %ret0_2
242 // ; %tmp0 = tail call i32 @llvm.ctlz.i32(i32 %divisor, i1 true)
243 // ; %tmp1 = tail call i32 @llvm.ctlz.i32(i32 %dividend, i1 true)
244 // ; %sr = sub nsw i32 %tmp0, %tmp1
245 // ; %ret0_4 = icmp ugt i32 %sr, 31
246 // ; %ret0 = or i1 %ret0_3, %ret0_4
247 // ; %retDividend = icmp eq i32 %sr, 31
248 // ; %retVal = select i1 %ret0, i32 0, i32 %dividend
249 // ; %earlyRet = or i1 %ret0, %retDividend
250 // ; br i1 %earlyRet, label %end, label %bb1
251 Builder.SetInsertPoint(SpecialCases);
252 Value *Ret0_1 = Builder.CreateICmpEQ(Divisor, Zero);
253 Value *Ret0_2 = Builder.CreateICmpEQ(Dividend, Zero);
254 Value *Ret0_3 = Builder.CreateOr(Ret0_1, Ret0_2);
255 Value *Tmp0 = Builder.CreateCall2(CTLZ, Divisor, True);
256 Value *Tmp1 = Builder.CreateCall2(CTLZ, Dividend, True);
257 Value *SR = Builder.CreateSub(Tmp0, Tmp1);
258 Value *Ret0_4 = Builder.CreateICmpUGT(SR, MSB);
259 Value *Ret0 = Builder.CreateOr(Ret0_3, Ret0_4);
260 Value *RetDividend = Builder.CreateICmpEQ(SR, MSB);
261 Value *RetVal = Builder.CreateSelect(Ret0, Zero, Dividend);
262 Value *EarlyRet = Builder.CreateOr(Ret0, RetDividend);
263 Builder.CreateCondBr(EarlyRet, End, BB1);
265 // ; bb1: ; preds = %special-cases
266 // ; %sr_1 = add i32 %sr, 1
267 // ; %tmp2 = sub i32 31, %sr
268 // ; %q = shl i32 %dividend, %tmp2
269 // ; %skipLoop = icmp eq i32 %sr_1, 0
270 // ; br i1 %skipLoop, label %loop-exit, label %preheader
271 Builder.SetInsertPoint(BB1);
272 Value *SR_1 = Builder.CreateAdd(SR, One);
273 Value *Tmp2 = Builder.CreateSub(MSB, SR);
274 Value *Q = Builder.CreateShl(Dividend, Tmp2);
275 Value *SkipLoop = Builder.CreateICmpEQ(SR_1, Zero);
276 Builder.CreateCondBr(SkipLoop, LoopExit, Preheader);
278 // ; preheader: ; preds = %bb1
279 // ; %tmp3 = lshr i32 %dividend, %sr_1
280 // ; %tmp4 = add i32 %divisor, -1
281 // ; br label %do-while
282 Builder.SetInsertPoint(Preheader);
283 Value *Tmp3 = Builder.CreateLShr(Dividend, SR_1);
284 Value *Tmp4 = Builder.CreateAdd(Divisor, NegOne);
285 Builder.CreateBr(DoWhile);
287 // ; do-while: ; preds = %do-while, %preheader
288 // ; %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]
289 // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
290 // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
291 // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
292 // ; %tmp5 = shl i32 %r_1, 1
293 // ; %tmp6 = lshr i32 %q_2, 31
294 // ; %tmp7 = or i32 %tmp5, %tmp6
295 // ; %tmp8 = shl i32 %q_2, 1
296 // ; %q_1 = or i32 %carry_1, %tmp8
297 // ; %tmp9 = sub i32 %tmp4, %tmp7
298 // ; %tmp10 = ashr i32 %tmp9, 31
299 // ; %carry = and i32 %tmp10, 1
300 // ; %tmp11 = and i32 %tmp10, %divisor
301 // ; %r = sub i32 %tmp7, %tmp11
302 // ; %sr_2 = add i32 %sr_3, -1
303 // ; %tmp12 = icmp eq i32 %sr_2, 0
304 // ; br i1 %tmp12, label %loop-exit, label %do-while
305 Builder.SetInsertPoint(DoWhile);
306 PHINode *Carry_1 = Builder.CreatePHI(DivTy, 2);
307 PHINode *SR_3 = Builder.CreatePHI(DivTy, 2);
308 PHINode *R_1 = Builder.CreatePHI(DivTy, 2);
309 PHINode *Q_2 = Builder.CreatePHI(DivTy, 2);
310 Value *Tmp5 = Builder.CreateShl(R_1, One);
311 Value *Tmp6 = Builder.CreateLShr(Q_2, MSB);
312 Value *Tmp7 = Builder.CreateOr(Tmp5, Tmp6);
313 Value *Tmp8 = Builder.CreateShl(Q_2, One);
314 Value *Q_1 = Builder.CreateOr(Carry_1, Tmp8);
315 Value *Tmp9 = Builder.CreateSub(Tmp4, Tmp7);
316 Value *Tmp10 = Builder.CreateAShr(Tmp9, MSB);
317 Value *Carry = Builder.CreateAnd(Tmp10, One);
318 Value *Tmp11 = Builder.CreateAnd(Tmp10, Divisor);
319 Value *R = Builder.CreateSub(Tmp7, Tmp11);
320 Value *SR_2 = Builder.CreateAdd(SR_3, NegOne);
321 Value *Tmp12 = Builder.CreateICmpEQ(SR_2, Zero);
322 Builder.CreateCondBr(Tmp12, LoopExit, DoWhile);
324 // ; loop-exit: ; preds = %do-while, %bb1
325 // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
326 // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
327 // ; %tmp13 = shl i32 %q_3, 1
328 // ; %q_4 = or i32 %carry_2, %tmp13
330 Builder.SetInsertPoint(LoopExit);
331 PHINode *Carry_2 = Builder.CreatePHI(DivTy, 2);
332 PHINode *Q_3 = Builder.CreatePHI(DivTy, 2);
333 Value *Tmp13 = Builder.CreateShl(Q_3, One);
334 Value *Q_4 = Builder.CreateOr(Carry_2, Tmp13);
335 Builder.CreateBr(End);
337 // ; end: ; preds = %loop-exit, %special-cases
338 // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
340 Builder.SetInsertPoint(End, End->begin());
341 PHINode *Q_5 = Builder.CreatePHI(DivTy, 2);
343 // Populate the Phis, since all values have now been created. Our Phis were:
344 // ; %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]
345 Carry_1->addIncoming(Zero, Preheader);
346 Carry_1->addIncoming(Carry, DoWhile);
347 // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
348 SR_3->addIncoming(SR_1, Preheader);
349 SR_3->addIncoming(SR_2, DoWhile);
350 // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
351 R_1->addIncoming(Tmp3, Preheader);
352 R_1->addIncoming(R, DoWhile);
353 // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
354 Q_2->addIncoming(Q, Preheader);
355 Q_2->addIncoming(Q_1, DoWhile);
356 // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
357 Carry_2->addIncoming(Zero, BB1);
358 Carry_2->addIncoming(Carry, DoWhile);
359 // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
360 Q_3->addIncoming(Q, BB1);
361 Q_3->addIncoming(Q_1, DoWhile);
362 // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
363 Q_5->addIncoming(Q_4, LoopExit);
364 Q_5->addIncoming(RetVal, SpecialCases);
369 /// Generate code to calculate the remainder of two integers, replacing Rem with
370 /// the generated code. This currently generates code using the udiv expansion,
371 /// but future work includes generating more specialized code, e.g. when more
372 /// information about the operands are known. Implements both 32bit and 64bit
375 /// @brief Replace Rem with generated code.
376 bool llvm::expandRemainder(BinaryOperator *Rem) {
377 assert((Rem->getOpcode() == Instruction::SRem ||
378 Rem->getOpcode() == Instruction::URem) &&
379 "Trying to expand remainder from a non-remainder function");
381 IRBuilder<> Builder(Rem);
383 Type *RemTy = Rem->getType();
384 if (RemTy->isVectorTy())
385 llvm_unreachable("Div over vectors not supported");
387 unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
389 if (RemTyBitWidth != 32 && RemTyBitWidth != 64)
390 llvm_unreachable("Div of bitwidth other than 32 or 64 not supported");
392 // First prepare the sign if it's a signed remainder
393 if (Rem->getOpcode() == Instruction::SRem) {
394 Value *Remainder = generateSignedRemainderCode(Rem->getOperand(0),
395 Rem->getOperand(1), Builder);
397 Rem->replaceAllUsesWith(Remainder);
398 Rem->dropAllReferences();
399 Rem->eraseFromParent();
401 // If we didn't actually generate a udiv instruction, we're done
402 BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
403 if (!BO || BO->getOpcode() != Instruction::URem)
409 Value *Remainder = generatedUnsignedRemainderCode(Rem->getOperand(0),
413 Rem->replaceAllUsesWith(Remainder);
414 Rem->dropAllReferences();
415 Rem->eraseFromParent();
418 if (BinaryOperator *UDiv = dyn_cast<BinaryOperator>(Builder.GetInsertPoint())) {
419 assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?");
420 expandDivision(UDiv);
427 /// Generate code to divide two integers, replacing Div with the generated
428 /// code. This currently generates code similarly to compiler-rt's
429 /// implementations, but future work includes generating more specialized code
430 /// when more information about the operands are known. Implements both
431 /// 32bit and 64bit scalar division.
433 /// @brief Replace Div with generated code.
434 bool llvm::expandDivision(BinaryOperator *Div) {
435 assert((Div->getOpcode() == Instruction::SDiv ||
436 Div->getOpcode() == Instruction::UDiv) &&
437 "Trying to expand division from a non-division function");
439 IRBuilder<> Builder(Div);
441 Type *DivTy = Div->getType();
442 if (DivTy->isVectorTy())
443 llvm_unreachable("Div over vectors not supported");
445 unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
447 if (DivTyBitWidth != 32 && DivTyBitWidth != 64)
448 llvm_unreachable("Div of bitwidth other than 32 or 64 not supported");
450 // First prepare the sign if it's a signed division
451 if (Div->getOpcode() == Instruction::SDiv) {
452 // Lower the code to unsigned division, and reset Div to point to the udiv.
453 Value *Quotient = generateSignedDivisionCode(Div->getOperand(0),
454 Div->getOperand(1), Builder);
455 Div->replaceAllUsesWith(Quotient);
456 Div->dropAllReferences();
457 Div->eraseFromParent();
459 // If we didn't actually generate a udiv instruction, we're done
460 BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
461 if (!BO || BO->getOpcode() != Instruction::UDiv)
467 // Insert the unsigned division code
468 Value *Quotient = generateUnsignedDivisionCode(Div->getOperand(0),
471 Div->replaceAllUsesWith(Quotient);
472 Div->dropAllReferences();
473 Div->eraseFromParent();
478 /// Generate code to compute the remainder of two integers of bitwidth up to
479 /// 32 bits. Uses the above routines and extends the inputs/truncates the
480 /// outputs to operate in 32 bits; that is, these routines are good for targets
481 /// that have no or very little suppport for smaller than 32 bit integer
484 /// @brief Replace Rem with emulation code.
485 bool llvm::expandRemainderUpTo32Bits(BinaryOperator *Rem) {
486 assert((Rem->getOpcode() == Instruction::SRem ||
487 Rem->getOpcode() == Instruction::URem) &&
488 "Trying to expand remainder from a non-remainder function");
490 Type *RemTy = Rem->getType();
491 if (RemTy->isVectorTy())
492 llvm_unreachable("Div over vectors not supported");
494 unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
496 if (RemTyBitWidth > 32)
497 llvm_unreachable("Div of bitwidth greater than 32 not supported");
499 if (RemTyBitWidth == 32)
500 return expandRemainder(Rem);
502 // If bitwidth smaller than 32 extend inputs, extend output and proceed
503 // with 32 bit division.
504 IRBuilder<> Builder(Rem);
510 Type *Int32Ty = Builder.getInt32Ty();
512 if (Rem->getOpcode() == Instruction::SRem) {
513 ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int32Ty);
514 ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int32Ty);
515 ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);
517 ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int32Ty);
518 ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int32Ty);
519 ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
521 Trunc = Builder.CreateTrunc(ExtRem, RemTy);
523 Rem->replaceAllUsesWith(Trunc);
524 Rem->dropAllReferences();
525 Rem->eraseFromParent();
527 return expandRemainder(cast<BinaryOperator>(ExtRem));
530 /// Generate code to compute the remainder of two integers of bitwidth up to
531 /// 64 bits. Uses the above routines and extends the inputs/truncates the
532 /// outputs to operate in 64 bits.
534 /// @brief Replace Rem with emulation code.
535 bool llvm::expandRemainderUpTo64Bits(BinaryOperator *Rem) {
536 assert((Rem->getOpcode() == Instruction::SRem ||
537 Rem->getOpcode() == Instruction::URem) &&
538 "Trying to expand remainder from a non-remainder function");
540 Type *RemTy = Rem->getType();
541 if (RemTy->isVectorTy())
542 llvm_unreachable("Div over vectors not supported");
544 unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
546 if (RemTyBitWidth > 64)
547 llvm_unreachable("Div of bitwidth greater than 64 not supported");
549 if (RemTyBitWidth == 64)
550 return expandRemainder(Rem);
552 // If bitwidth smaller than 64 extend inputs, extend output and proceed
553 // with 64 bit division.
554 IRBuilder<> Builder(Rem);
560 Type *Int64Ty = Builder.getInt64Ty();
562 if (Rem->getOpcode() == Instruction::SRem) {
563 ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int64Ty);
564 ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int64Ty);
565 ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);
567 ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int64Ty);
568 ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int64Ty);
569 ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
571 Trunc = Builder.CreateTrunc(ExtRem, RemTy);
573 Rem->replaceAllUsesWith(Trunc);
574 Rem->dropAllReferences();
575 Rem->eraseFromParent();
577 return expandRemainder(cast<BinaryOperator>(ExtRem));
580 /// Generate code to divide two integers of bitwidth up to 32 bits. Uses the
581 /// above routines and extends the inputs/truncates the outputs to operate
582 /// in 32 bits; that is, these routines are good for targets that have no
583 /// or very little support for smaller than 32 bit integer arithmetic.
585 /// @brief Replace Div with emulation code.
586 bool llvm::expandDivisionUpTo32Bits(BinaryOperator *Div) {
587 assert((Div->getOpcode() == Instruction::SDiv ||
588 Div->getOpcode() == Instruction::UDiv) &&
589 "Trying to expand division from a non-division function");
591 Type *DivTy = Div->getType();
592 if (DivTy->isVectorTy())
593 llvm_unreachable("Div over vectors not supported");
595 unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
597 if (DivTyBitWidth > 32)
598 llvm_unreachable("Div of bitwidth greater than 32 not supported");
600 if (DivTyBitWidth == 32)
601 return expandDivision(Div);
603 // If bitwidth smaller than 32 extend inputs, extend output and proceed
604 // with 32 bit division.
605 IRBuilder<> Builder(Div);
611 Type *Int32Ty = Builder.getInt32Ty();
613 if (Div->getOpcode() == Instruction::SDiv) {
614 ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int32Ty);
615 ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int32Ty);
616 ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);
618 ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int32Ty);
619 ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int32Ty);
620 ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);
622 Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
624 Div->replaceAllUsesWith(Trunc);
625 Div->dropAllReferences();
626 Div->eraseFromParent();
628 return expandDivision(cast<BinaryOperator>(ExtDiv));
631 /// Generate code to divide two integers of bitwidth up to 64 bits. Uses the
632 /// above routines and extends the inputs/truncates the outputs to operate
635 /// @brief Replace Div with emulation code.
636 bool llvm::expandDivisionUpTo64Bits(BinaryOperator *Div) {
637 assert((Div->getOpcode() == Instruction::SDiv ||
638 Div->getOpcode() == Instruction::UDiv) &&
639 "Trying to expand division from a non-division function");
641 Type *DivTy = Div->getType();
642 if (DivTy->isVectorTy())
643 llvm_unreachable("Div over vectors not supported");
645 unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
647 if (DivTyBitWidth > 64)
648 llvm_unreachable("Div of bitwidth greater than 64 not supported");
650 if (DivTyBitWidth == 64)
651 return expandDivision(Div);
653 // If bitwidth smaller than 64 extend inputs, extend output and proceed
654 // with 64 bit division.
655 IRBuilder<> Builder(Div);
661 Type *Int64Ty = Builder.getInt64Ty();
663 if (Div->getOpcode() == Instruction::SDiv) {
664 ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int64Ty);
665 ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int64Ty);
666 ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);
668 ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int64Ty);
669 ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int64Ty);
670 ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);
672 Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
674 Div->replaceAllUsesWith(Trunc);
675 Div->dropAllReferences();
676 Div->eraseFromParent();
678 return expandDivision(cast<BinaryOperator>(ExtDiv));