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 #define DEBUG_TYPE "integer-division"
18 #include "llvm/Transforms/Utils/IntegerDivision.h"
19 #include "llvm/IR/Function.h"
20 #include "llvm/IR/IRBuilder.h"
21 #include "llvm/IR/Instructions.h"
22 #include "llvm/IR/Intrinsics.h"
27 /// Generate code to compute the remainder of two signed integers. Returns the
28 /// remainder, which will have the sign of the dividend. Builder's insert point
29 /// should be pointing where the caller wants code generated, e.g. at the srem
30 /// instruction. This will generate a urem in the process, and Builder's insert
31 /// point will be pointing at the uren (if present, i.e. not folded), ready to
32 /// be expanded if the user wishes
33 static Value *generateSignedRemainderCode(Value *Dividend, Value *Divisor,
34 IRBuilder<> &Builder) {
35 unsigned BitWidth = Dividend->getType()->getIntegerBitWidth();
39 Shift = Builder.getInt64(63);
41 assert(BitWidth == 32 && "Unexpected bit width");
42 Shift = Builder.getInt32(31);
45 // Following instructions are generated for both i32 (shift 31) and
48 // ; %dividend_sgn = ashr i32 %dividend, 31
49 // ; %divisor_sgn = ashr i32 %divisor, 31
50 // ; %dvd_xor = xor i32 %dividend, %dividend_sgn
51 // ; %dvs_xor = xor i32 %divisor, %divisor_sgn
52 // ; %u_dividend = sub i32 %dvd_xor, %dividend_sgn
53 // ; %u_divisor = sub i32 %dvs_xor, %divisor_sgn
54 // ; %urem = urem i32 %dividend, %divisor
55 // ; %xored = xor i32 %urem, %dividend_sgn
56 // ; %srem = sub i32 %xored, %dividend_sgn
57 Value *DividendSign = Builder.CreateAShr(Dividend, Shift);
58 Value *DivisorSign = Builder.CreateAShr(Divisor, Shift);
59 Value *DvdXor = Builder.CreateXor(Dividend, DividendSign);
60 Value *DvsXor = Builder.CreateXor(Divisor, DivisorSign);
61 Value *UDividend = Builder.CreateSub(DvdXor, DividendSign);
62 Value *UDivisor = Builder.CreateSub(DvsXor, DivisorSign);
63 Value *URem = Builder.CreateURem(UDividend, UDivisor);
64 Value *Xored = Builder.CreateXor(URem, DividendSign);
65 Value *SRem = Builder.CreateSub(Xored, DividendSign);
67 if (Instruction *URemInst = dyn_cast<Instruction>(URem))
68 Builder.SetInsertPoint(URemInst);
74 /// Generate code to compute the remainder of two unsigned integers. Returns the
75 /// remainder. Builder's insert point should be pointing where the caller wants
76 /// code generated, e.g. at the urem instruction. This will generate a udiv in
77 /// the process, and Builder's insert point will be pointing at the udiv (if
78 /// present, i.e. not folded), ready to be expanded if the user wishes
79 static Value *generatedUnsignedRemainderCode(Value *Dividend, Value *Divisor,
80 IRBuilder<> &Builder) {
81 // Remainder = Dividend - Quotient*Divisor
83 // Following instructions are generated for both i32 and i64
85 // ; %quotient = udiv i32 %dividend, %divisor
86 // ; %product = mul i32 %divisor, %quotient
87 // ; %remainder = sub i32 %dividend, %product
88 Value *Quotient = Builder.CreateUDiv(Dividend, Divisor);
89 Value *Product = Builder.CreateMul(Divisor, Quotient);
90 Value *Remainder = Builder.CreateSub(Dividend, Product);
92 if (Instruction *UDiv = dyn_cast<Instruction>(Quotient))
93 Builder.SetInsertPoint(UDiv);
98 /// Generate code to divide two signed integers. Returns the quotient, rounded
99 /// towards 0. Builder's insert point should be pointing where the caller wants
100 /// code generated, e.g. at the sdiv instruction. This will generate a udiv in
101 /// the process, and Builder's insert point will be pointing at the udiv (if
102 /// present, i.e. not folded), ready to be expanded if the user wishes.
103 static Value *generateSignedDivisionCode(Value *Dividend, Value *Divisor,
104 IRBuilder<> &Builder) {
105 // Implementation taken from compiler-rt's __divsi3 and __divdi3
107 unsigned BitWidth = Dividend->getType()->getIntegerBitWidth();
110 if (BitWidth == 64) {
111 Shift = Builder.getInt64(63);
113 assert(BitWidth == 32 && "Unexpected bit width");
114 Shift = Builder.getInt32(31);
117 // Following instructions are generated for both i32 (shift 31) and
120 // ; %tmp = ashr i32 %dividend, 31
121 // ; %tmp1 = ashr i32 %divisor, 31
122 // ; %tmp2 = xor i32 %tmp, %dividend
123 // ; %u_dvnd = sub nsw i32 %tmp2, %tmp
124 // ; %tmp3 = xor i32 %tmp1, %divisor
125 // ; %u_dvsr = sub nsw i32 %tmp3, %tmp1
126 // ; %q_sgn = xor i32 %tmp1, %tmp
127 // ; %q_mag = udiv i32 %u_dvnd, %u_dvsr
128 // ; %tmp4 = xor i32 %q_mag, %q_sgn
129 // ; %q = sub i32 %tmp4, %q_sgn
130 Value *Tmp = Builder.CreateAShr(Dividend, Shift);
131 Value *Tmp1 = Builder.CreateAShr(Divisor, Shift);
132 Value *Tmp2 = Builder.CreateXor(Tmp, Dividend);
133 Value *U_Dvnd = Builder.CreateSub(Tmp2, Tmp);
134 Value *Tmp3 = Builder.CreateXor(Tmp1, Divisor);
135 Value *U_Dvsr = Builder.CreateSub(Tmp3, Tmp1);
136 Value *Q_Sgn = Builder.CreateXor(Tmp1, Tmp);
137 Value *Q_Mag = Builder.CreateUDiv(U_Dvnd, U_Dvsr);
138 Value *Tmp4 = Builder.CreateXor(Q_Mag, Q_Sgn);
139 Value *Q = Builder.CreateSub(Tmp4, Q_Sgn);
141 if (Instruction *UDiv = dyn_cast<Instruction>(Q_Mag))
142 Builder.SetInsertPoint(UDiv);
147 /// Generates code to divide two unsigned scalar 32-bit or 64-bit integers.
148 /// Returns the quotient, rounded towards 0. Builder's insert point should
149 /// point where the caller wants code generated, e.g. at the udiv instruction.
150 static Value *generateUnsignedDivisionCode(Value *Dividend, Value *Divisor,
151 IRBuilder<> &Builder) {
152 // The basic algorithm can be found in the compiler-rt project's
153 // implementation of __udivsi3.c. Here, we do a lower-level IR based approach
154 // that's been hand-tuned to lessen the amount of control flow involved.
156 // Some helper values
157 IntegerType *DivTy = cast<IntegerType>(Dividend->getType());
158 unsigned BitWidth = DivTy->getBitWidth();
165 if (BitWidth == 64) {
166 Zero = Builder.getInt64(0);
167 One = Builder.getInt64(1);
168 NegOne = ConstantInt::getSigned(DivTy, -1);
169 MSB = Builder.getInt64(63);
171 assert(BitWidth == 32 && "Unexpected bit width");
172 Zero = Builder.getInt32(0);
173 One = Builder.getInt32(1);
174 NegOne = ConstantInt::getSigned(DivTy, -1);
175 MSB = Builder.getInt32(31);
178 ConstantInt *True = Builder.getTrue();
180 BasicBlock *IBB = Builder.GetInsertBlock();
181 Function *F = IBB->getParent();
182 Function *CTLZ = Intrinsic::getDeclaration(F->getParent(), Intrinsic::ctlz,
185 // Our CFG is going to look like:
186 // +---------------------+
189 // +---------------------+
196 // | | +------------+
199 // | | +------------+
203 // | | +------------+ |
204 // | | | do-while | |
206 // | | +------------+ |
208 // | +-----------+ +---+
217 BasicBlock *SpecialCases = Builder.GetInsertBlock();
218 SpecialCases->setName(Twine(SpecialCases->getName(), "_udiv-special-cases"));
219 BasicBlock *End = SpecialCases->splitBasicBlock(Builder.GetInsertPoint(),
221 BasicBlock *LoopExit = BasicBlock::Create(Builder.getContext(),
222 "udiv-loop-exit", F, End);
223 BasicBlock *DoWhile = BasicBlock::Create(Builder.getContext(),
224 "udiv-do-while", F, End);
225 BasicBlock *Preheader = BasicBlock::Create(Builder.getContext(),
226 "udiv-preheader", F, End);
227 BasicBlock *BB1 = BasicBlock::Create(Builder.getContext(),
230 // We'll be overwriting the terminator to insert our extra blocks
231 SpecialCases->getTerminator()->eraseFromParent();
233 // Same instructions are generated for both i32 (msb 31) and i64 (msb 63).
235 // First off, check for special cases: dividend or divisor is zero, divisor
236 // is greater than dividend, and divisor is 1.
238 // ; %ret0_1 = icmp eq i32 %divisor, 0
239 // ; %ret0_2 = icmp eq i32 %dividend, 0
240 // ; %ret0_3 = or i1 %ret0_1, %ret0_2
241 // ; %tmp0 = tail call i32 @llvm.ctlz.i32(i32 %divisor, i1 true)
242 // ; %tmp1 = tail call i32 @llvm.ctlz.i32(i32 %dividend, i1 true)
243 // ; %sr = sub nsw i32 %tmp0, %tmp1
244 // ; %ret0_4 = icmp ugt i32 %sr, 31
245 // ; %ret0 = or i1 %ret0_3, %ret0_4
246 // ; %retDividend = icmp eq i32 %sr, 31
247 // ; %retVal = select i1 %ret0, i32 0, i32 %dividend
248 // ; %earlyRet = or i1 %ret0, %retDividend
249 // ; br i1 %earlyRet, label %end, label %bb1
250 Builder.SetInsertPoint(SpecialCases);
251 Value *Ret0_1 = Builder.CreateICmpEQ(Divisor, Zero);
252 Value *Ret0_2 = Builder.CreateICmpEQ(Dividend, Zero);
253 Value *Ret0_3 = Builder.CreateOr(Ret0_1, Ret0_2);
254 Value *Tmp0 = Builder.CreateCall2(CTLZ, Divisor, True);
255 Value *Tmp1 = Builder.CreateCall2(CTLZ, Dividend, True);
256 Value *SR = Builder.CreateSub(Tmp0, Tmp1);
257 Value *Ret0_4 = Builder.CreateICmpUGT(SR, MSB);
258 Value *Ret0 = Builder.CreateOr(Ret0_3, Ret0_4);
259 Value *RetDividend = Builder.CreateICmpEQ(SR, MSB);
260 Value *RetVal = Builder.CreateSelect(Ret0, Zero, Dividend);
261 Value *EarlyRet = Builder.CreateOr(Ret0, RetDividend);
262 Builder.CreateCondBr(EarlyRet, End, BB1);
264 // ; bb1: ; preds = %special-cases
265 // ; %sr_1 = add i32 %sr, 1
266 // ; %tmp2 = sub i32 31, %sr
267 // ; %q = shl i32 %dividend, %tmp2
268 // ; %skipLoop = icmp eq i32 %sr_1, 0
269 // ; br i1 %skipLoop, label %loop-exit, label %preheader
270 Builder.SetInsertPoint(BB1);
271 Value *SR_1 = Builder.CreateAdd(SR, One);
272 Value *Tmp2 = Builder.CreateSub(MSB, SR);
273 Value *Q = Builder.CreateShl(Dividend, Tmp2);
274 Value *SkipLoop = Builder.CreateICmpEQ(SR_1, Zero);
275 Builder.CreateCondBr(SkipLoop, LoopExit, Preheader);
277 // ; preheader: ; preds = %bb1
278 // ; %tmp3 = lshr i32 %dividend, %sr_1
279 // ; %tmp4 = add i32 %divisor, -1
280 // ; br label %do-while
281 Builder.SetInsertPoint(Preheader);
282 Value *Tmp3 = Builder.CreateLShr(Dividend, SR_1);
283 Value *Tmp4 = Builder.CreateAdd(Divisor, NegOne);
284 Builder.CreateBr(DoWhile);
286 // ; do-while: ; preds = %do-while, %preheader
287 // ; %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]
288 // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
289 // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
290 // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
291 // ; %tmp5 = shl i32 %r_1, 1
292 // ; %tmp6 = lshr i32 %q_2, 31
293 // ; %tmp7 = or i32 %tmp5, %tmp6
294 // ; %tmp8 = shl i32 %q_2, 1
295 // ; %q_1 = or i32 %carry_1, %tmp8
296 // ; %tmp9 = sub i32 %tmp4, %tmp7
297 // ; %tmp10 = ashr i32 %tmp9, 31
298 // ; %carry = and i32 %tmp10, 1
299 // ; %tmp11 = and i32 %tmp10, %divisor
300 // ; %r = sub i32 %tmp7, %tmp11
301 // ; %sr_2 = add i32 %sr_3, -1
302 // ; %tmp12 = icmp eq i32 %sr_2, 0
303 // ; br i1 %tmp12, label %loop-exit, label %do-while
304 Builder.SetInsertPoint(DoWhile);
305 PHINode *Carry_1 = Builder.CreatePHI(DivTy, 2);
306 PHINode *SR_3 = Builder.CreatePHI(DivTy, 2);
307 PHINode *R_1 = Builder.CreatePHI(DivTy, 2);
308 PHINode *Q_2 = Builder.CreatePHI(DivTy, 2);
309 Value *Tmp5 = Builder.CreateShl(R_1, One);
310 Value *Tmp6 = Builder.CreateLShr(Q_2, MSB);
311 Value *Tmp7 = Builder.CreateOr(Tmp5, Tmp6);
312 Value *Tmp8 = Builder.CreateShl(Q_2, One);
313 Value *Q_1 = Builder.CreateOr(Carry_1, Tmp8);
314 Value *Tmp9 = Builder.CreateSub(Tmp4, Tmp7);
315 Value *Tmp10 = Builder.CreateAShr(Tmp9, MSB);
316 Value *Carry = Builder.CreateAnd(Tmp10, One);
317 Value *Tmp11 = Builder.CreateAnd(Tmp10, Divisor);
318 Value *R = Builder.CreateSub(Tmp7, Tmp11);
319 Value *SR_2 = Builder.CreateAdd(SR_3, NegOne);
320 Value *Tmp12 = Builder.CreateICmpEQ(SR_2, Zero);
321 Builder.CreateCondBr(Tmp12, LoopExit, DoWhile);
323 // ; loop-exit: ; preds = %do-while, %bb1
324 // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
325 // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
326 // ; %tmp13 = shl i32 %q_3, 1
327 // ; %q_4 = or i32 %carry_2, %tmp13
329 Builder.SetInsertPoint(LoopExit);
330 PHINode *Carry_2 = Builder.CreatePHI(DivTy, 2);
331 PHINode *Q_3 = Builder.CreatePHI(DivTy, 2);
332 Value *Tmp13 = Builder.CreateShl(Q_3, One);
333 Value *Q_4 = Builder.CreateOr(Carry_2, Tmp13);
334 Builder.CreateBr(End);
336 // ; end: ; preds = %loop-exit, %special-cases
337 // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
339 Builder.SetInsertPoint(End, End->begin());
340 PHINode *Q_5 = Builder.CreatePHI(DivTy, 2);
342 // Populate the Phis, since all values have now been created. Our Phis were:
343 // ; %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]
344 Carry_1->addIncoming(Zero, Preheader);
345 Carry_1->addIncoming(Carry, DoWhile);
346 // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
347 SR_3->addIncoming(SR_1, Preheader);
348 SR_3->addIncoming(SR_2, DoWhile);
349 // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
350 R_1->addIncoming(Tmp3, Preheader);
351 R_1->addIncoming(R, DoWhile);
352 // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
353 Q_2->addIncoming(Q, Preheader);
354 Q_2->addIncoming(Q_1, DoWhile);
355 // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
356 Carry_2->addIncoming(Zero, BB1);
357 Carry_2->addIncoming(Carry, DoWhile);
358 // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
359 Q_3->addIncoming(Q, BB1);
360 Q_3->addIncoming(Q_1, DoWhile);
361 // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
362 Q_5->addIncoming(Q_4, LoopExit);
363 Q_5->addIncoming(RetVal, SpecialCases);
368 /// Generate code to calculate the remainder of two integers, replacing Rem with
369 /// the generated code. This currently generates code using the udiv expansion,
370 /// but future work includes generating more specialized code, e.g. when more
371 /// information about the operands are known. Implements both 32bit and 64bit
374 /// @brief Replace Rem with generated code.
375 bool llvm::expandRemainder(BinaryOperator *Rem) {
376 assert((Rem->getOpcode() == Instruction::SRem ||
377 Rem->getOpcode() == Instruction::URem) &&
378 "Trying to expand remainder from a non-remainder function");
380 IRBuilder<> Builder(Rem);
382 Type *RemTy = Rem->getType();
383 if (RemTy->isVectorTy())
384 llvm_unreachable("Div over vectors not supported");
386 unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
388 if (RemTyBitWidth != 32 && RemTyBitWidth != 64)
389 llvm_unreachable("Div of bitwidth other than 32 or 64 not supported");
391 // First prepare the sign if it's a signed remainder
392 if (Rem->getOpcode() == Instruction::SRem) {
393 Value *Remainder = generateSignedRemainderCode(Rem->getOperand(0),
394 Rem->getOperand(1), Builder);
396 Rem->replaceAllUsesWith(Remainder);
397 Rem->dropAllReferences();
398 Rem->eraseFromParent();
400 // If we didn't actually generate a udiv instruction, we're done
401 BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
402 if (!BO || BO->getOpcode() != Instruction::URem)
408 Value *Remainder = generatedUnsignedRemainderCode(Rem->getOperand(0),
412 Rem->replaceAllUsesWith(Remainder);
413 Rem->dropAllReferences();
414 Rem->eraseFromParent();
417 if (BinaryOperator *UDiv = dyn_cast<BinaryOperator>(Builder.GetInsertPoint())) {
418 assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?");
419 expandDivision(UDiv);
426 /// Generate code to divide two integers, replacing Div with the generated
427 /// code. This currently generates code similarly to compiler-rt's
428 /// implementations, but future work includes generating more specialized code
429 /// when more information about the operands are known. Implements both
430 /// 32bit and 64bit scalar division.
432 /// @brief Replace Div with generated code.
433 bool llvm::expandDivision(BinaryOperator *Div) {
434 assert((Div->getOpcode() == Instruction::SDiv ||
435 Div->getOpcode() == Instruction::UDiv) &&
436 "Trying to expand division from a non-division function");
438 IRBuilder<> Builder(Div);
440 Type *DivTy = Div->getType();
441 if (DivTy->isVectorTy())
442 llvm_unreachable("Div over vectors not supported");
444 unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
446 if (DivTyBitWidth != 32 && DivTyBitWidth != 64)
447 llvm_unreachable("Div of bitwidth other than 32 or 64 not supported");
449 // First prepare the sign if it's a signed division
450 if (Div->getOpcode() == Instruction::SDiv) {
451 // Lower the code to unsigned division, and reset Div to point to the udiv.
452 Value *Quotient = generateSignedDivisionCode(Div->getOperand(0),
453 Div->getOperand(1), Builder);
454 Div->replaceAllUsesWith(Quotient);
455 Div->dropAllReferences();
456 Div->eraseFromParent();
458 // If we didn't actually generate a udiv instruction, we're done
459 BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
460 if (!BO || BO->getOpcode() != Instruction::UDiv)
466 // Insert the unsigned division code
467 Value *Quotient = generateUnsignedDivisionCode(Div->getOperand(0),
470 Div->replaceAllUsesWith(Quotient);
471 Div->dropAllReferences();
472 Div->eraseFromParent();
477 /// Generate code to compute the remainder of two integers of bitwidth up to
478 /// 32 bits. Uses the above routines and extends the inputs/truncates the
479 /// outputs to operate in 32 bits; that is, these routines are good for targets
480 /// that have no or very little suppport for smaller than 32 bit integer
483 /// @brief Replace Rem with emulation code.
484 bool llvm::expandRemainderUpTo32Bits(BinaryOperator *Rem) {
485 assert((Rem->getOpcode() == Instruction::SRem ||
486 Rem->getOpcode() == Instruction::URem) &&
487 "Trying to expand remainder from a non-remainder function");
489 Type *RemTy = Rem->getType();
490 if (RemTy->isVectorTy())
491 llvm_unreachable("Div over vectors not supported");
493 unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
495 if (RemTyBitWidth > 32)
496 llvm_unreachable("Div of bitwidth greater than 32 not supported");
498 if (RemTyBitWidth == 32)
499 return expandRemainder(Rem);
501 // If bitwidth smaller than 32 extend inputs, extend output and proceed
502 // with 32 bit division.
503 IRBuilder<> Builder(Rem);
509 Type *Int32Ty = Builder.getInt32Ty();
511 if (Rem->getOpcode() == Instruction::SRem) {
512 ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int32Ty);
513 ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int32Ty);
514 ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);
516 ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int32Ty);
517 ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int32Ty);
518 ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
520 Trunc = Builder.CreateTrunc(ExtRem, RemTy);
522 Rem->replaceAllUsesWith(Trunc);
523 Rem->dropAllReferences();
524 Rem->eraseFromParent();
526 return expandRemainder(cast<BinaryOperator>(ExtRem));
529 /// Generate code to compute the remainder of two integers of bitwidth up to
530 /// 64 bits. Uses the above routines and extends the inputs/truncates the
531 /// outputs to operate in 64 bits.
533 /// @brief Replace Rem with emulation code.
534 bool llvm::expandRemainderUpTo64Bits(BinaryOperator *Rem) {
535 assert((Rem->getOpcode() == Instruction::SRem ||
536 Rem->getOpcode() == Instruction::URem) &&
537 "Trying to expand remainder from a non-remainder function");
539 Type *RemTy = Rem->getType();
540 if (RemTy->isVectorTy())
541 llvm_unreachable("Div over vectors not supported");
543 unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
545 if (RemTyBitWidth > 64)
546 llvm_unreachable("Div of bitwidth greater than 64 not supported");
548 if (RemTyBitWidth == 64)
549 return expandRemainder(Rem);
551 // If bitwidth smaller than 64 extend inputs, extend output and proceed
552 // with 64 bit division.
553 IRBuilder<> Builder(Rem);
559 Type *Int64Ty = Builder.getInt64Ty();
561 if (Rem->getOpcode() == Instruction::SRem) {
562 ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int64Ty);
563 ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int64Ty);
564 ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);
566 ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int64Ty);
567 ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int64Ty);
568 ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
570 Trunc = Builder.CreateTrunc(ExtRem, RemTy);
572 Rem->replaceAllUsesWith(Trunc);
573 Rem->dropAllReferences();
574 Rem->eraseFromParent();
576 return expandRemainder(cast<BinaryOperator>(ExtRem));
579 /// Generate code to divide two integers of bitwidth up to 32 bits. Uses the
580 /// above routines and extends the inputs/truncates the outputs to operate
581 /// in 32 bits; that is, these routines are good for targets that have no
582 /// or very little support for smaller than 32 bit integer arithmetic.
584 /// @brief Replace Div with emulation code.
585 bool llvm::expandDivisionUpTo32Bits(BinaryOperator *Div) {
586 assert((Div->getOpcode() == Instruction::SDiv ||
587 Div->getOpcode() == Instruction::UDiv) &&
588 "Trying to expand division from a non-division function");
590 Type *DivTy = Div->getType();
591 if (DivTy->isVectorTy())
592 llvm_unreachable("Div over vectors not supported");
594 unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
596 if (DivTyBitWidth > 32)
597 llvm_unreachable("Div of bitwidth greater than 32 not supported");
599 if (DivTyBitWidth == 32)
600 return expandDivision(Div);
602 // If bitwidth smaller than 32 extend inputs, extend output and proceed
603 // with 32 bit division.
604 IRBuilder<> Builder(Div);
610 Type *Int32Ty = Builder.getInt32Ty();
612 if (Div->getOpcode() == Instruction::SDiv) {
613 ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int32Ty);
614 ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int32Ty);
615 ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);
617 ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int32Ty);
618 ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int32Ty);
619 ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);
621 Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
623 Div->replaceAllUsesWith(Trunc);
624 Div->dropAllReferences();
625 Div->eraseFromParent();
627 return expandDivision(cast<BinaryOperator>(ExtDiv));
630 /// Generate code to divide two integers of bitwidth up to 64 bits. Uses the
631 /// above routines and extends the inputs/truncates the outputs to operate
634 /// @brief Replace Div with emulation code.
635 bool llvm::expandDivisionUpTo64Bits(BinaryOperator *Div) {
636 assert((Div->getOpcode() == Instruction::SDiv ||
637 Div->getOpcode() == Instruction::UDiv) &&
638 "Trying to expand division from a non-division function");
640 Type *DivTy = Div->getType();
641 if (DivTy->isVectorTy())
642 llvm_unreachable("Div over vectors not supported");
644 unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
646 if (DivTyBitWidth > 64)
647 llvm_unreachable("Div of bitwidth greater than 64 not supported");
649 if (DivTyBitWidth == 64)
650 return expandDivision(Div);
652 // If bitwidth smaller than 64 extend inputs, extend output and proceed
653 // with 64 bit division.
654 IRBuilder<> Builder(Div);
660 Type *Int64Ty = Builder.getInt64Ty();
662 if (Div->getOpcode() == Instruction::SDiv) {
663 ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int64Ty);
664 ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int64Ty);
665 ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);
667 ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int64Ty);
668 ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int64Ty);
669 ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);
671 Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
673 Div->replaceAllUsesWith(Trunc);
674 Div->dropAllReferences();
675 Div->eraseFromParent();
677 return expandDivision(cast<BinaryOperator>(ExtDiv));