1 //===-- IntegerDivision.cpp - Expand integer division ---------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
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.
14 //
15 //===----------------------------------------------------------------------===//
16 
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"
22 #include <utility>
23 
24 using namespace llvm;
25 
26 #define DEBUG_TYPE "integer-division"
27 
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
generateSignedRemainderCode(Value * Dividend,Value * Divisor,IRBuilder<> & Builder)34 static Value *generateSignedRemainderCode(Value *Dividend, Value *Divisor,
35                                           IRBuilder<> &Builder) {
36   unsigned BitWidth = Dividend->getType()->getIntegerBitWidth();
37   ConstantInt *Shift;
38 
39   if (BitWidth == 64) {
40     Shift = Builder.getInt64(63);
41   } else {
42     assert(BitWidth == 32 && "Unexpected bit width");
43     Shift = Builder.getInt32(31);
44   }
45 
46   // Following instructions are generated for both i32 (shift 31) and
47   // i64 (shift 63).
48 
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);
67 
68   if (Instruction *URemInst = dyn_cast<Instruction>(URem))
69     Builder.SetInsertPoint(URemInst);
70 
71   return SRem;
72 }
73 
74 
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
generatedUnsignedRemainderCode(Value * Dividend,Value * Divisor,IRBuilder<> & Builder)80 static Value *generatedUnsignedRemainderCode(Value *Dividend, Value *Divisor,
81                                              IRBuilder<> &Builder) {
82   // Remainder = Dividend - Quotient*Divisor
83 
84   // Following instructions are generated for both i32 and i64
85 
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);
92 
93   if (Instruction *UDiv = dyn_cast<Instruction>(Quotient))
94     Builder.SetInsertPoint(UDiv);
95 
96   return Remainder;
97 }
98 
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.
generateSignedDivisionCode(Value * Dividend,Value * Divisor,IRBuilder<> & Builder)104 static Value *generateSignedDivisionCode(Value *Dividend, Value *Divisor,
105                                          IRBuilder<> &Builder) {
106   // Implementation taken from compiler-rt's __divsi3 and __divdi3
107 
108   unsigned BitWidth = Dividend->getType()->getIntegerBitWidth();
109   ConstantInt *Shift;
110 
111   if (BitWidth == 64) {
112     Shift = Builder.getInt64(63);
113   } else {
114     assert(BitWidth == 32 && "Unexpected bit width");
115     Shift = Builder.getInt32(31);
116   }
117 
118   // Following instructions are generated for both i32 (shift 31) and
119   // i64 (shift 63).
120 
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);
141 
142   if (Instruction *UDiv = dyn_cast<Instruction>(Q_Mag))
143     Builder.SetInsertPoint(UDiv);
144 
145   return Q;
146 }
147 
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.
generateUnsignedDivisionCode(Value * Dividend,Value * Divisor,IRBuilder<> & Builder)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.
156 
157   // Some helper values
158   IntegerType *DivTy = cast<IntegerType>(Dividend->getType());
159   unsigned BitWidth = DivTy->getBitWidth();
160 
161   ConstantInt *Zero;
162   ConstantInt *One;
163   ConstantInt *NegOne;
164   ConstantInt *MSB;
165 
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);
171   } else {
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);
177   }
178 
179   ConstantInt *True = Builder.getTrue();
180 
181   BasicBlock *IBB = Builder.GetInsertBlock();
182   Function *F = IBB->getParent();
183   Function *CTLZ = Intrinsic::getDeclaration(F->getParent(), Intrinsic::ctlz,
184                                              DivTy);
185 
186   // Our CFG is going to look like:
187   // +---------------------+
188   // | special-cases       |
189   // |   ...               |
190   // +---------------------+
191   //  |       |
192   //  |   +----------+
193   //  |   |  bb1     |
194   //  |   |  ...     |
195   //  |   +----------+
196   //  |    |      |
197   //  |    |  +------------+
198   //  |    |  |  preheader |
199   //  |    |  |  ...       |
200   //  |    |  +------------+
201   //  |    |      |
202   //  |    |      |      +---+
203   //  |    |      |      |   |
204   //  |    |  +------------+ |
205   //  |    |  |  do-while  | |
206   //  |    |  |  ...       | |
207   //  |    |  +------------+ |
208   //  |    |      |      |   |
209   //  |   +-----------+  +---+
210   //  |   | loop-exit |
211   //  |   |  ...      |
212   //  |   +-----------+
213   //  |     |
214   // +-------+
215   // | ...   |
216   // | end   |
217   // +-------+
218   BasicBlock *SpecialCases = Builder.GetInsertBlock();
219   SpecialCases->setName(Twine(SpecialCases->getName(), "_udiv-special-cases"));
220   BasicBlock *End = SpecialCases->splitBasicBlock(Builder.GetInsertPoint(),
221                                                   "udiv-end");
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(),
229                                              "udiv-bb1", F, End);
230 
231   // We'll be overwriting the terminator to insert our extra blocks
232   SpecialCases->getTerminator()->eraseFromParent();
233 
234   // Same instructions are generated for both i32 (msb 31) and i64 (msb 63).
235 
236   // First off, check for special cases: dividend or divisor is zero, divisor
237   // is greater than dividend, and divisor is 1.
238   // ; special-cases:
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);
264 
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);
277 
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);
286 
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);
323 
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
329   // ;   br label %end
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);
336 
337   // ; end:                                 ; preds = %loop-exit, %special-cases
338   // ;   %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
339   // ;   ret i32 %q_5
340   Builder.SetInsertPoint(End, End->begin());
341   PHINode *Q_5 = Builder.CreatePHI(DivTy, 2);
342 
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);
365 
366   return Q_5;
367 }
368 
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
373 /// scalar division.
374 ///
375 /// @brief Replace Rem with generated code.
expandRemainder(BinaryOperator * Rem)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");
380 
381   IRBuilder<> Builder(Rem);
382 
383   Type *RemTy = Rem->getType();
384   if (RemTy->isVectorTy())
385     llvm_unreachable("Div over vectors not supported");
386 
387   unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
388 
389   if (RemTyBitWidth != 32 && RemTyBitWidth != 64)
390     llvm_unreachable("Div of bitwidth other than 32 or 64 not supported");
391 
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);
396 
397     Rem->replaceAllUsesWith(Remainder);
398     Rem->dropAllReferences();
399     Rem->eraseFromParent();
400 
401     // If we didn't actually generate an urem instruction, we're done
402     // This happens for example if the input were constant. In this case the
403     // Builder insertion point was unchanged
404     if (Rem == Builder.GetInsertPoint())
405       return true;
406 
407     BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
408     Rem = BO;
409   }
410 
411   Value *Remainder = generatedUnsignedRemainderCode(Rem->getOperand(0),
412                                                     Rem->getOperand(1),
413                                                     Builder);
414 
415   Rem->replaceAllUsesWith(Remainder);
416   Rem->dropAllReferences();
417   Rem->eraseFromParent();
418 
419   // Expand the udiv
420   if (BinaryOperator *UDiv = dyn_cast<BinaryOperator>(Builder.GetInsertPoint())) {
421     assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?");
422     expandDivision(UDiv);
423   }
424 
425   return true;
426 }
427 
428 
429 /// Generate code to divide two integers, replacing Div with the generated
430 /// code. This currently generates code similarly to compiler-rt's
431 /// implementations, but future work includes generating more specialized code
432 /// when more information about the operands are known. Implements both
433 /// 32bit and 64bit scalar division.
434 ///
435 /// @brief Replace Div with generated code.
expandDivision(BinaryOperator * Div)436 bool llvm::expandDivision(BinaryOperator *Div) {
437   assert((Div->getOpcode() == Instruction::SDiv ||
438           Div->getOpcode() == Instruction::UDiv) &&
439          "Trying to expand division from a non-division function");
440 
441   IRBuilder<> Builder(Div);
442 
443   Type *DivTy = Div->getType();
444   if (DivTy->isVectorTy())
445     llvm_unreachable("Div over vectors not supported");
446 
447   unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
448 
449   if (DivTyBitWidth != 32 && DivTyBitWidth != 64)
450     llvm_unreachable("Div of bitwidth other than 32 or 64 not supported");
451 
452   // First prepare the sign if it's a signed division
453   if (Div->getOpcode() == Instruction::SDiv) {
454     // Lower the code to unsigned division, and reset Div to point to the udiv.
455     Value *Quotient = generateSignedDivisionCode(Div->getOperand(0),
456                                                  Div->getOperand(1), Builder);
457     Div->replaceAllUsesWith(Quotient);
458     Div->dropAllReferences();
459     Div->eraseFromParent();
460 
461     // If we didn't actually generate an udiv instruction, we're done
462     // This happens for example if the input were constant. In this case the
463     // Builder insertion point was unchanged
464     if (Div == Builder.GetInsertPoint())
465       return true;
466 
467     BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
468     Div = BO;
469   }
470 
471   // Insert the unsigned division code
472   Value *Quotient = generateUnsignedDivisionCode(Div->getOperand(0),
473                                                  Div->getOperand(1),
474                                                  Builder);
475   Div->replaceAllUsesWith(Quotient);
476   Div->dropAllReferences();
477   Div->eraseFromParent();
478 
479   return true;
480 }
481 
482 /// Generate code to compute the remainder of two integers of bitwidth up to
483 /// 32 bits. Uses the above routines and extends the inputs/truncates the
484 /// outputs to operate in 32 bits; that is, these routines are good for targets
485 /// that have no or very little suppport for smaller than 32 bit integer
486 /// arithmetic.
487 ///
488 /// @brief Replace Rem with emulation code.
expandRemainderUpTo32Bits(BinaryOperator * Rem)489 bool llvm::expandRemainderUpTo32Bits(BinaryOperator *Rem) {
490   assert((Rem->getOpcode() == Instruction::SRem ||
491           Rem->getOpcode() == Instruction::URem) &&
492           "Trying to expand remainder from a non-remainder function");
493 
494   Type *RemTy = Rem->getType();
495   if (RemTy->isVectorTy())
496     llvm_unreachable("Div over vectors not supported");
497 
498   unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
499 
500   if (RemTyBitWidth > 32)
501     llvm_unreachable("Div of bitwidth greater than 32 not supported");
502 
503   if (RemTyBitWidth == 32)
504     return expandRemainder(Rem);
505 
506   // If bitwidth smaller than 32 extend inputs, extend output and proceed
507   // with 32 bit division.
508   IRBuilder<> Builder(Rem);
509 
510   Value *ExtDividend;
511   Value *ExtDivisor;
512   Value *ExtRem;
513   Value *Trunc;
514   Type *Int32Ty = Builder.getInt32Ty();
515 
516   if (Rem->getOpcode() == Instruction::SRem) {
517     ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int32Ty);
518     ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int32Ty);
519     ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);
520   } else {
521     ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int32Ty);
522     ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int32Ty);
523     ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
524   }
525   Trunc = Builder.CreateTrunc(ExtRem, RemTy);
526 
527   Rem->replaceAllUsesWith(Trunc);
528   Rem->dropAllReferences();
529   Rem->eraseFromParent();
530 
531   return expandRemainder(cast<BinaryOperator>(ExtRem));
532 }
533 
534 /// Generate code to compute the remainder of two integers of bitwidth up to
535 /// 64 bits. Uses the above routines and extends the inputs/truncates the
536 /// outputs to operate in 64 bits.
537 ///
538 /// @brief Replace Rem with emulation code.
expandRemainderUpTo64Bits(BinaryOperator * Rem)539 bool llvm::expandRemainderUpTo64Bits(BinaryOperator *Rem) {
540   assert((Rem->getOpcode() == Instruction::SRem ||
541           Rem->getOpcode() == Instruction::URem) &&
542           "Trying to expand remainder from a non-remainder function");
543 
544   Type *RemTy = Rem->getType();
545   if (RemTy->isVectorTy())
546     llvm_unreachable("Div over vectors not supported");
547 
548   unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
549 
550   if (RemTyBitWidth > 64)
551     llvm_unreachable("Div of bitwidth greater than 64 not supported");
552 
553   if (RemTyBitWidth == 64)
554     return expandRemainder(Rem);
555 
556   // If bitwidth smaller than 64 extend inputs, extend output and proceed
557   // with 64 bit division.
558   IRBuilder<> Builder(Rem);
559 
560   Value *ExtDividend;
561   Value *ExtDivisor;
562   Value *ExtRem;
563   Value *Trunc;
564   Type *Int64Ty = Builder.getInt64Ty();
565 
566   if (Rem->getOpcode() == Instruction::SRem) {
567     ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int64Ty);
568     ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int64Ty);
569     ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);
570   } else {
571     ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int64Ty);
572     ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int64Ty);
573     ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
574   }
575   Trunc = Builder.CreateTrunc(ExtRem, RemTy);
576 
577   Rem->replaceAllUsesWith(Trunc);
578   Rem->dropAllReferences();
579   Rem->eraseFromParent();
580 
581   return expandRemainder(cast<BinaryOperator>(ExtRem));
582 }
583 
584 /// Generate code to divide two integers of bitwidth up to 32 bits. Uses the
585 /// above routines and extends the inputs/truncates the outputs to operate
586 /// in 32 bits; that is, these routines are good for targets that have no
587 /// or very little support for smaller than 32 bit integer arithmetic.
588 ///
589 /// @brief Replace Div with emulation code.
expandDivisionUpTo32Bits(BinaryOperator * Div)590 bool llvm::expandDivisionUpTo32Bits(BinaryOperator *Div) {
591   assert((Div->getOpcode() == Instruction::SDiv ||
592           Div->getOpcode() == Instruction::UDiv) &&
593           "Trying to expand division from a non-division function");
594 
595   Type *DivTy = Div->getType();
596   if (DivTy->isVectorTy())
597     llvm_unreachable("Div over vectors not supported");
598 
599   unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
600 
601   if (DivTyBitWidth > 32)
602     llvm_unreachable("Div of bitwidth greater than 32 not supported");
603 
604   if (DivTyBitWidth == 32)
605     return expandDivision(Div);
606 
607   // If bitwidth smaller than 32 extend inputs, extend output and proceed
608   // with 32 bit division.
609   IRBuilder<> Builder(Div);
610 
611   Value *ExtDividend;
612   Value *ExtDivisor;
613   Value *ExtDiv;
614   Value *Trunc;
615   Type *Int32Ty = Builder.getInt32Ty();
616 
617   if (Div->getOpcode() == Instruction::SDiv) {
618     ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int32Ty);
619     ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int32Ty);
620     ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);
621   } else {
622     ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int32Ty);
623     ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int32Ty);
624     ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);
625   }
626   Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
627 
628   Div->replaceAllUsesWith(Trunc);
629   Div->dropAllReferences();
630   Div->eraseFromParent();
631 
632   return expandDivision(cast<BinaryOperator>(ExtDiv));
633 }
634 
635 /// Generate code to divide two integers of bitwidth up to 64 bits. Uses the
636 /// above routines and extends the inputs/truncates the outputs to operate
637 /// in 64 bits.
638 ///
639 /// @brief Replace Div with emulation code.
expandDivisionUpTo64Bits(BinaryOperator * Div)640 bool llvm::expandDivisionUpTo64Bits(BinaryOperator *Div) {
641   assert((Div->getOpcode() == Instruction::SDiv ||
642           Div->getOpcode() == Instruction::UDiv) &&
643           "Trying to expand division from a non-division function");
644 
645   Type *DivTy = Div->getType();
646   if (DivTy->isVectorTy())
647     llvm_unreachable("Div over vectors not supported");
648 
649   unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
650 
651   if (DivTyBitWidth > 64)
652     llvm_unreachable("Div of bitwidth greater than 64 not supported");
653 
654   if (DivTyBitWidth == 64)
655     return expandDivision(Div);
656 
657   // If bitwidth smaller than 64 extend inputs, extend output and proceed
658   // with 64 bit division.
659   IRBuilder<> Builder(Div);
660 
661   Value *ExtDividend;
662   Value *ExtDivisor;
663   Value *ExtDiv;
664   Value *Trunc;
665   Type *Int64Ty = Builder.getInt64Ty();
666 
667   if (Div->getOpcode() == Instruction::SDiv) {
668     ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int64Ty);
669     ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int64Ty);
670     ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);
671   } else {
672     ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int64Ty);
673     ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int64Ty);
674     ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);
675   }
676   Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
677 
678   Div->replaceAllUsesWith(Trunc);
679   Div->dropAllReferences();
680   Div->eraseFromParent();
681 
682   return expandDivision(cast<BinaryOperator>(ExtDiv));
683 }
684