1 //===-- IntegerDivision.cpp - Expand integer division ---------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file contains an implementation of 32bit and 64bit scalar integer
10 // division for targets that don't have native support. It's largely derived
11 // from compiler-rt's implementations of __udivsi3 and __udivmoddi4,
12 // but hand-tuned for targets that prefer less control flow.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/Transforms/Utils/IntegerDivision.h"
17 #include "llvm/IR/Function.h"
18 #include "llvm/IR/IRBuilder.h"
19 #include "llvm/IR/Instructions.h"
20 #include "llvm/IR/Intrinsics.h"
21 
22 using namespace llvm;
23 
24 #define DEBUG_TYPE "integer-division"
25 
26 /// Generate code to compute the remainder of two signed integers. Returns the
27 /// remainder, which will have the sign of the dividend. Builder's insert point
28 /// should be pointing where the caller wants code generated, e.g. at the srem
29 /// instruction. This will generate a urem in the process, and Builder's insert
30 /// point will be pointing at the uren (if present, i.e. not folded), ready to
31 /// be expanded if the user wishes
32 static Value *generateSignedRemainderCode(Value *Dividend, Value *Divisor,
33                                           IRBuilder<> &Builder) {
34   unsigned BitWidth = Dividend->getType()->getIntegerBitWidth();
35   ConstantInt *Shift;
36 
37   if (BitWidth == 64) {
38     Shift = Builder.getInt64(63);
39   } else {
40     assert(BitWidth == 32 && "Unexpected bit width");
41     Shift = Builder.getInt32(31);
42   }
43 
44   // Following instructions are generated for both i32 (shift 31) and
45   // i64 (shift 63).
46 
47   // ;   %dividend_sgn = ashr i32 %dividend, 31
48   // ;   %divisor_sgn  = ashr i32 %divisor, 31
49   // ;   %dvd_xor      = xor i32 %dividend, %dividend_sgn
50   // ;   %dvs_xor      = xor i32 %divisor, %divisor_sgn
51   // ;   %u_dividend   = sub i32 %dvd_xor, %dividend_sgn
52   // ;   %u_divisor    = sub i32 %dvs_xor, %divisor_sgn
53   // ;   %urem         = urem i32 %dividend, %divisor
54   // ;   %xored        = xor i32 %urem, %dividend_sgn
55   // ;   %srem         = sub i32 %xored, %dividend_sgn
56   Value *DividendSign = Builder.CreateAShr(Dividend, Shift);
57   Value *DivisorSign  = Builder.CreateAShr(Divisor, Shift);
58   Value *DvdXor       = Builder.CreateXor(Dividend, DividendSign);
59   Value *DvsXor       = Builder.CreateXor(Divisor, DivisorSign);
60   Value *UDividend    = Builder.CreateSub(DvdXor, DividendSign);
61   Value *UDivisor     = Builder.CreateSub(DvsXor, DivisorSign);
62   Value *URem         = Builder.CreateURem(UDividend, UDivisor);
63   Value *Xored        = Builder.CreateXor(URem, DividendSign);
64   Value *SRem         = Builder.CreateSub(Xored, DividendSign);
65 
66   if (Instruction *URemInst = dyn_cast<Instruction>(URem))
67     Builder.SetInsertPoint(URemInst);
68 
69   return SRem;
70 }
71 
72 
73 /// Generate code to compute the remainder of two unsigned integers. Returns the
74 /// remainder. Builder's insert point should be pointing where the caller wants
75 /// code generated, e.g. at the urem instruction. This will generate a udiv in
76 /// the process, and Builder's insert point will be pointing at the udiv (if
77 /// present, i.e. not folded), ready to be expanded if the user wishes
78 static Value *generatedUnsignedRemainderCode(Value *Dividend, Value *Divisor,
79                                              IRBuilder<> &Builder) {
80   // Remainder = Dividend - Quotient*Divisor
81 
82   // Following instructions are generated for both i32 and i64
83 
84   // ;   %quotient  = udiv i32 %dividend, %divisor
85   // ;   %product   = mul i32 %divisor, %quotient
86   // ;   %remainder = sub i32 %dividend, %product
87   Value *Quotient  = Builder.CreateUDiv(Dividend, Divisor);
88   Value *Product   = Builder.CreateMul(Divisor, Quotient);
89   Value *Remainder = Builder.CreateSub(Dividend, Product);
90 
91   if (Instruction *UDiv = dyn_cast<Instruction>(Quotient))
92     Builder.SetInsertPoint(UDiv);
93 
94   return Remainder;
95 }
96 
97 /// Generate code to divide two signed integers. Returns the quotient, rounded
98 /// towards 0. Builder's insert point should be pointing where the caller wants
99 /// code generated, e.g. at the sdiv instruction. This will generate a udiv in
100 /// the process, and Builder's insert point will be pointing at the udiv (if
101 /// present, i.e. not folded), ready to be expanded if the user wishes.
102 static Value *generateSignedDivisionCode(Value *Dividend, Value *Divisor,
103                                          IRBuilder<> &Builder) {
104   // Implementation taken from compiler-rt's __divsi3 and __divdi3
105 
106   unsigned BitWidth = Dividend->getType()->getIntegerBitWidth();
107   ConstantInt *Shift;
108 
109   if (BitWidth == 64) {
110     Shift = Builder.getInt64(63);
111   } else {
112     assert(BitWidth == 32 && "Unexpected bit width");
113     Shift = Builder.getInt32(31);
114   }
115 
116   // Following instructions are generated for both i32 (shift 31) and
117   // i64 (shift 63).
118 
119   // ;   %tmp    = ashr i32 %dividend, 31
120   // ;   %tmp1   = ashr i32 %divisor, 31
121   // ;   %tmp2   = xor i32 %tmp, %dividend
122   // ;   %u_dvnd = sub nsw i32 %tmp2, %tmp
123   // ;   %tmp3   = xor i32 %tmp1, %divisor
124   // ;   %u_dvsr = sub nsw i32 %tmp3, %tmp1
125   // ;   %q_sgn  = xor i32 %tmp1, %tmp
126   // ;   %q_mag  = udiv i32 %u_dvnd, %u_dvsr
127   // ;   %tmp4   = xor i32 %q_mag, %q_sgn
128   // ;   %q      = sub i32 %tmp4, %q_sgn
129   Value *Tmp    = Builder.CreateAShr(Dividend, Shift);
130   Value *Tmp1   = Builder.CreateAShr(Divisor, Shift);
131   Value *Tmp2   = Builder.CreateXor(Tmp, Dividend);
132   Value *U_Dvnd = Builder.CreateSub(Tmp2, Tmp);
133   Value *Tmp3   = Builder.CreateXor(Tmp1, Divisor);
134   Value *U_Dvsr = Builder.CreateSub(Tmp3, Tmp1);
135   Value *Q_Sgn  = Builder.CreateXor(Tmp1, Tmp);
136   Value *Q_Mag  = Builder.CreateUDiv(U_Dvnd, U_Dvsr);
137   Value *Tmp4   = Builder.CreateXor(Q_Mag, Q_Sgn);
138   Value *Q      = Builder.CreateSub(Tmp4, Q_Sgn);
139 
140   if (Instruction *UDiv = dyn_cast<Instruction>(Q_Mag))
141     Builder.SetInsertPoint(UDiv);
142 
143   return Q;
144 }
145 
146 /// Generates code to divide two unsigned scalar 32-bit or 64-bit integers.
147 /// Returns the quotient, rounded towards 0. Builder's insert point should
148 /// point where the caller wants code generated, e.g. at the udiv instruction.
149 static Value *generateUnsignedDivisionCode(Value *Dividend, Value *Divisor,
150                                            IRBuilder<> &Builder) {
151   // The basic algorithm can be found in the compiler-rt project's
152   // implementation of __udivsi3.c. Here, we do a lower-level IR based approach
153   // that's been hand-tuned to lessen the amount of control flow involved.
154 
155   // Some helper values
156   IntegerType *DivTy = cast<IntegerType>(Dividend->getType());
157   unsigned BitWidth = DivTy->getBitWidth();
158 
159   ConstantInt *Zero;
160   ConstantInt *One;
161   ConstantInt *NegOne;
162   ConstantInt *MSB;
163 
164   if (BitWidth == 64) {
165     Zero      = Builder.getInt64(0);
166     One       = Builder.getInt64(1);
167     NegOne    = ConstantInt::getSigned(DivTy, -1);
168     MSB       = Builder.getInt64(63);
169   } else {
170     assert(BitWidth == 32 && "Unexpected bit width");
171     Zero      = Builder.getInt32(0);
172     One       = Builder.getInt32(1);
173     NegOne    = ConstantInt::getSigned(DivTy, -1);
174     MSB       = Builder.getInt32(31);
175   }
176 
177   ConstantInt *True = Builder.getTrue();
178 
179   BasicBlock *IBB = Builder.GetInsertBlock();
180   Function *F = IBB->getParent();
181   Function *CTLZ = Intrinsic::getDeclaration(F->getParent(), Intrinsic::ctlz,
182                                              DivTy);
183 
184   // Our CFG is going to look like:
185   // +---------------------+
186   // | special-cases       |
187   // |   ...               |
188   // +---------------------+
189   //  |       |
190   //  |   +----------+
191   //  |   |  bb1     |
192   //  |   |  ...     |
193   //  |   +----------+
194   //  |    |      |
195   //  |    |  +------------+
196   //  |    |  |  preheader |
197   //  |    |  |  ...       |
198   //  |    |  +------------+
199   //  |    |      |
200   //  |    |      |      +---+
201   //  |    |      |      |   |
202   //  |    |  +------------+ |
203   //  |    |  |  do-while  | |
204   //  |    |  |  ...       | |
205   //  |    |  +------------+ |
206   //  |    |      |      |   |
207   //  |   +-----------+  +---+
208   //  |   | loop-exit |
209   //  |   |  ...      |
210   //  |   +-----------+
211   //  |     |
212   // +-------+
213   // | ...   |
214   // | end   |
215   // +-------+
216   BasicBlock *SpecialCases = Builder.GetInsertBlock();
217   SpecialCases->setName(Twine(SpecialCases->getName(), "_udiv-special-cases"));
218   BasicBlock *End = SpecialCases->splitBasicBlock(Builder.GetInsertPoint(),
219                                                   "udiv-end");
220   BasicBlock *LoopExit  = BasicBlock::Create(Builder.getContext(),
221                                              "udiv-loop-exit", F, End);
222   BasicBlock *DoWhile   = BasicBlock::Create(Builder.getContext(),
223                                              "udiv-do-while", F, End);
224   BasicBlock *Preheader = BasicBlock::Create(Builder.getContext(),
225                                              "udiv-preheader", F, End);
226   BasicBlock *BB1       = BasicBlock::Create(Builder.getContext(),
227                                              "udiv-bb1", F, End);
228 
229   // We'll be overwriting the terminator to insert our extra blocks
230   SpecialCases->getTerminator()->eraseFromParent();
231 
232   // Same instructions are generated for both i32 (msb 31) and i64 (msb 63).
233 
234   // First off, check for special cases: dividend or divisor is zero, divisor
235   // is greater than dividend, and divisor is 1.
236   // ; special-cases:
237   // ;   %ret0_1      = icmp eq i32 %divisor, 0
238   // ;   %ret0_2      = icmp eq i32 %dividend, 0
239   // ;   %ret0_3      = or i1 %ret0_1, %ret0_2
240   // ;   %tmp0        = tail call i32 @llvm.ctlz.i32(i32 %divisor, i1 true)
241   // ;   %tmp1        = tail call i32 @llvm.ctlz.i32(i32 %dividend, i1 true)
242   // ;   %sr          = sub nsw i32 %tmp0, %tmp1
243   // ;   %ret0_4      = icmp ugt i32 %sr, 31
244   // ;   %ret0        = or i1 %ret0_3, %ret0_4
245   // ;   %retDividend = icmp eq i32 %sr, 31
246   // ;   %retVal      = select i1 %ret0, i32 0, i32 %dividend
247   // ;   %earlyRet    = or i1 %ret0, %retDividend
248   // ;   br i1 %earlyRet, label %end, label %bb1
249   Builder.SetInsertPoint(SpecialCases);
250   Value *Ret0_1      = Builder.CreateICmpEQ(Divisor, Zero);
251   Value *Ret0_2      = Builder.CreateICmpEQ(Dividend, Zero);
252   Value *Ret0_3      = Builder.CreateOr(Ret0_1, Ret0_2);
253   Value *Tmp0 = Builder.CreateCall(CTLZ, {Divisor, True});
254   Value *Tmp1 = Builder.CreateCall(CTLZ, {Dividend, True});
255   Value *SR          = Builder.CreateSub(Tmp0, Tmp1);
256   Value *Ret0_4      = Builder.CreateICmpUGT(SR, MSB);
257   Value *Ret0        = Builder.CreateOr(Ret0_3, Ret0_4);
258   Value *RetDividend = Builder.CreateICmpEQ(SR, MSB);
259   Value *RetVal      = Builder.CreateSelect(Ret0, Zero, Dividend);
260   Value *EarlyRet    = Builder.CreateOr(Ret0, RetDividend);
261   Builder.CreateCondBr(EarlyRet, End, BB1);
262 
263   // ; bb1:                                             ; preds = %special-cases
264   // ;   %sr_1     = add i32 %sr, 1
265   // ;   %tmp2     = sub i32 31, %sr
266   // ;   %q        = shl i32 %dividend, %tmp2
267   // ;   %skipLoop = icmp eq i32 %sr_1, 0
268   // ;   br i1 %skipLoop, label %loop-exit, label %preheader
269   Builder.SetInsertPoint(BB1);
270   Value *SR_1     = Builder.CreateAdd(SR, One);
271   Value *Tmp2     = Builder.CreateSub(MSB, SR);
272   Value *Q        = Builder.CreateShl(Dividend, Tmp2);
273   Value *SkipLoop = Builder.CreateICmpEQ(SR_1, Zero);
274   Builder.CreateCondBr(SkipLoop, LoopExit, Preheader);
275 
276   // ; preheader:                                           ; preds = %bb1
277   // ;   %tmp3 = lshr i32 %dividend, %sr_1
278   // ;   %tmp4 = add i32 %divisor, -1
279   // ;   br label %do-while
280   Builder.SetInsertPoint(Preheader);
281   Value *Tmp3 = Builder.CreateLShr(Dividend, SR_1);
282   Value *Tmp4 = Builder.CreateAdd(Divisor, NegOne);
283   Builder.CreateBr(DoWhile);
284 
285   // ; do-while:                                 ; preds = %do-while, %preheader
286   // ;   %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]
287   // ;   %sr_3    = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
288   // ;   %r_1     = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
289   // ;   %q_2     = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
290   // ;   %tmp5  = shl i32 %r_1, 1
291   // ;   %tmp6  = lshr i32 %q_2, 31
292   // ;   %tmp7  = or i32 %tmp5, %tmp6
293   // ;   %tmp8  = shl i32 %q_2, 1
294   // ;   %q_1   = or i32 %carry_1, %tmp8
295   // ;   %tmp9  = sub i32 %tmp4, %tmp7
296   // ;   %tmp10 = ashr i32 %tmp9, 31
297   // ;   %carry = and i32 %tmp10, 1
298   // ;   %tmp11 = and i32 %tmp10, %divisor
299   // ;   %r     = sub i32 %tmp7, %tmp11
300   // ;   %sr_2  = add i32 %sr_3, -1
301   // ;   %tmp12 = icmp eq i32 %sr_2, 0
302   // ;   br i1 %tmp12, label %loop-exit, label %do-while
303   Builder.SetInsertPoint(DoWhile);
304   PHINode *Carry_1 = Builder.CreatePHI(DivTy, 2);
305   PHINode *SR_3    = Builder.CreatePHI(DivTy, 2);
306   PHINode *R_1     = Builder.CreatePHI(DivTy, 2);
307   PHINode *Q_2     = Builder.CreatePHI(DivTy, 2);
308   Value *Tmp5  = Builder.CreateShl(R_1, One);
309   Value *Tmp6  = Builder.CreateLShr(Q_2, MSB);
310   Value *Tmp7  = Builder.CreateOr(Tmp5, Tmp6);
311   Value *Tmp8  = Builder.CreateShl(Q_2, One);
312   Value *Q_1   = Builder.CreateOr(Carry_1, Tmp8);
313   Value *Tmp9  = Builder.CreateSub(Tmp4, Tmp7);
314   Value *Tmp10 = Builder.CreateAShr(Tmp9, MSB);
315   Value *Carry = Builder.CreateAnd(Tmp10, One);
316   Value *Tmp11 = Builder.CreateAnd(Tmp10, Divisor);
317   Value *R     = Builder.CreateSub(Tmp7, Tmp11);
318   Value *SR_2  = Builder.CreateAdd(SR_3, NegOne);
319   Value *Tmp12 = Builder.CreateICmpEQ(SR_2, Zero);
320   Builder.CreateCondBr(Tmp12, LoopExit, DoWhile);
321 
322   // ; loop-exit:                                      ; preds = %do-while, %bb1
323   // ;   %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
324   // ;   %q_3     = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
325   // ;   %tmp13 = shl i32 %q_3, 1
326   // ;   %q_4   = or i32 %carry_2, %tmp13
327   // ;   br label %end
328   Builder.SetInsertPoint(LoopExit);
329   PHINode *Carry_2 = Builder.CreatePHI(DivTy, 2);
330   PHINode *Q_3     = Builder.CreatePHI(DivTy, 2);
331   Value *Tmp13 = Builder.CreateShl(Q_3, One);
332   Value *Q_4   = Builder.CreateOr(Carry_2, Tmp13);
333   Builder.CreateBr(End);
334 
335   // ; end:                                 ; preds = %loop-exit, %special-cases
336   // ;   %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
337   // ;   ret i32 %q_5
338   Builder.SetInsertPoint(End, End->begin());
339   PHINode *Q_5 = Builder.CreatePHI(DivTy, 2);
340 
341   // Populate the Phis, since all values have now been created. Our Phis were:
342   // ;   %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]
343   Carry_1->addIncoming(Zero, Preheader);
344   Carry_1->addIncoming(Carry, DoWhile);
345   // ;   %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
346   SR_3->addIncoming(SR_1, Preheader);
347   SR_3->addIncoming(SR_2, DoWhile);
348   // ;   %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
349   R_1->addIncoming(Tmp3, Preheader);
350   R_1->addIncoming(R, DoWhile);
351   // ;   %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
352   Q_2->addIncoming(Q, Preheader);
353   Q_2->addIncoming(Q_1, DoWhile);
354   // ;   %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
355   Carry_2->addIncoming(Zero, BB1);
356   Carry_2->addIncoming(Carry, DoWhile);
357   // ;   %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
358   Q_3->addIncoming(Q, BB1);
359   Q_3->addIncoming(Q_1, DoWhile);
360   // ;   %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
361   Q_5->addIncoming(Q_4, LoopExit);
362   Q_5->addIncoming(RetVal, SpecialCases);
363 
364   return Q_5;
365 }
366 
367 /// Generate code to calculate the remainder of two integers, replacing Rem with
368 /// the generated code. This currently generates code using the udiv expansion,
369 /// but future work includes generating more specialized code, e.g. when more
370 /// information about the operands are known. Implements both 32bit and 64bit
371 /// scalar division.
372 ///
373 /// Replace Rem with generated code.
374 bool llvm::expandRemainder(BinaryOperator *Rem) {
375   assert((Rem->getOpcode() == Instruction::SRem ||
376           Rem->getOpcode() == Instruction::URem) &&
377          "Trying to expand remainder from a non-remainder function");
378 
379   IRBuilder<> Builder(Rem);
380 
381   assert(!Rem->getType()->isVectorTy() && "Div over vectors not supported");
382   assert((Rem->getType()->getIntegerBitWidth() == 32 ||
383           Rem->getType()->getIntegerBitWidth() == 64) &&
384          "Div of bitwidth other than 32 or 64 not supported");
385 
386   // First prepare the sign if it's a signed remainder
387   if (Rem->getOpcode() == Instruction::SRem) {
388     Value *Remainder = generateSignedRemainderCode(Rem->getOperand(0),
389                                                    Rem->getOperand(1), Builder);
390 
391     // Check whether this is the insert point while Rem is still valid.
392     bool IsInsertPoint = Rem->getIterator() == Builder.GetInsertPoint();
393     Rem->replaceAllUsesWith(Remainder);
394     Rem->dropAllReferences();
395     Rem->eraseFromParent();
396 
397     // If we didn't actually generate an urem instruction, we're done
398     // This happens for example if the input were constant. In this case the
399     // Builder insertion point was unchanged
400     if (IsInsertPoint)
401       return true;
402 
403     BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
404     Rem = BO;
405   }
406 
407   Value *Remainder = generatedUnsignedRemainderCode(Rem->getOperand(0),
408                                                     Rem->getOperand(1),
409                                                     Builder);
410 
411   Rem->replaceAllUsesWith(Remainder);
412   Rem->dropAllReferences();
413   Rem->eraseFromParent();
414 
415   // Expand the udiv
416   if (BinaryOperator *UDiv = dyn_cast<BinaryOperator>(Builder.GetInsertPoint())) {
417     assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?");
418     expandDivision(UDiv);
419   }
420 
421   return true;
422 }
423 
424 
425 /// Generate code to divide two integers, replacing Div with the generated
426 /// code. This currently generates code similarly to compiler-rt's
427 /// implementations, but future work includes generating more specialized code
428 /// when more information about the operands are known. Implements both
429 /// 32bit and 64bit scalar division.
430 ///
431 /// Replace Div with generated code.
432 bool llvm::expandDivision(BinaryOperator *Div) {
433   assert((Div->getOpcode() == Instruction::SDiv ||
434           Div->getOpcode() == Instruction::UDiv) &&
435          "Trying to expand division from a non-division function");
436 
437   IRBuilder<> Builder(Div);
438 
439   assert(!Div->getType()->isVectorTy() && "Div over vectors not supported");
440   assert((Div->getType()->getIntegerBitWidth() == 32 ||
441           Div->getType()->getIntegerBitWidth() == 64) &&
442          "Div of bitwidth other than 32 or 64 not supported");
443 
444   // First prepare the sign if it's a signed division
445   if (Div->getOpcode() == Instruction::SDiv) {
446     // Lower the code to unsigned division, and reset Div to point to the udiv.
447     Value *Quotient = generateSignedDivisionCode(Div->getOperand(0),
448                                                  Div->getOperand(1), Builder);
449 
450     // Check whether this is the insert point while Div is still valid.
451     bool IsInsertPoint = Div->getIterator() == Builder.GetInsertPoint();
452     Div->replaceAllUsesWith(Quotient);
453     Div->dropAllReferences();
454     Div->eraseFromParent();
455 
456     // If we didn't actually generate an udiv instruction, we're done
457     // This happens for example if the input were constant. In this case the
458     // Builder insertion point was unchanged
459     if (IsInsertPoint)
460       return true;
461 
462     BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
463     Div = BO;
464   }
465 
466   // Insert the unsigned division code
467   Value *Quotient = generateUnsignedDivisionCode(Div->getOperand(0),
468                                                  Div->getOperand(1),
469                                                  Builder);
470   Div->replaceAllUsesWith(Quotient);
471   Div->dropAllReferences();
472   Div->eraseFromParent();
473 
474   return true;
475 }
476 
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
481 /// arithmetic.
482 ///
483 /// 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");
488 
489   Type *RemTy = Rem->getType();
490   assert(!RemTy->isVectorTy() && "Div over vectors not supported");
491 
492   unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
493 
494   assert(RemTyBitWidth <= 32 &&
495          "Div of bitwidth greater than 32 not supported");
496 
497   if (RemTyBitWidth == 32)
498     return expandRemainder(Rem);
499 
500   // If bitwidth smaller than 32 extend inputs, extend output and proceed
501   // with 32 bit division.
502   IRBuilder<> Builder(Rem);
503 
504   Value *ExtDividend;
505   Value *ExtDivisor;
506   Value *ExtRem;
507   Value *Trunc;
508   Type *Int32Ty = Builder.getInt32Ty();
509 
510   if (Rem->getOpcode() == Instruction::SRem) {
511     ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int32Ty);
512     ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int32Ty);
513     ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);
514   } else {
515     ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int32Ty);
516     ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int32Ty);
517     ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
518   }
519   Trunc = Builder.CreateTrunc(ExtRem, RemTy);
520 
521   Rem->replaceAllUsesWith(Trunc);
522   Rem->dropAllReferences();
523   Rem->eraseFromParent();
524 
525   return expandRemainder(cast<BinaryOperator>(ExtRem));
526 }
527 
528 /// Generate code to compute the remainder of two integers of bitwidth up to
529 /// 64 bits. Uses the above routines and extends the inputs/truncates the
530 /// outputs to operate in 64 bits.
531 ///
532 /// Replace Rem with emulation code.
533 bool llvm::expandRemainderUpTo64Bits(BinaryOperator *Rem) {
534   assert((Rem->getOpcode() == Instruction::SRem ||
535           Rem->getOpcode() == Instruction::URem) &&
536           "Trying to expand remainder from a non-remainder function");
537 
538   Type *RemTy = Rem->getType();
539   assert(!RemTy->isVectorTy() && "Div over vectors not supported");
540 
541   unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
542 
543   assert(RemTyBitWidth <= 64 && "Div of bitwidth greater than 64 not supported");
544 
545   if (RemTyBitWidth == 64)
546     return expandRemainder(Rem);
547 
548   // If bitwidth smaller than 64 extend inputs, extend output and proceed
549   // with 64 bit division.
550   IRBuilder<> Builder(Rem);
551 
552   Value *ExtDividend;
553   Value *ExtDivisor;
554   Value *ExtRem;
555   Value *Trunc;
556   Type *Int64Ty = Builder.getInt64Ty();
557 
558   if (Rem->getOpcode() == Instruction::SRem) {
559     ExtDividend = Builder.CreateSExt(Rem->getOperand(0), Int64Ty);
560     ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int64Ty);
561     ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);
562   } else {
563     ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int64Ty);
564     ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int64Ty);
565     ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
566   }
567   Trunc = Builder.CreateTrunc(ExtRem, RemTy);
568 
569   Rem->replaceAllUsesWith(Trunc);
570   Rem->dropAllReferences();
571   Rem->eraseFromParent();
572 
573   return expandRemainder(cast<BinaryOperator>(ExtRem));
574 }
575 
576 /// Generate code to divide two integers of bitwidth up to 32 bits. Uses the
577 /// above routines and extends the inputs/truncates the outputs to operate
578 /// in 32 bits; that is, these routines are good for targets that have no
579 /// or very little support for smaller than 32 bit integer arithmetic.
580 ///
581 /// Replace Div with emulation code.
582 bool llvm::expandDivisionUpTo32Bits(BinaryOperator *Div) {
583   assert((Div->getOpcode() == Instruction::SDiv ||
584           Div->getOpcode() == Instruction::UDiv) &&
585           "Trying to expand division from a non-division function");
586 
587   Type *DivTy = Div->getType();
588   assert(!DivTy->isVectorTy() && "Div over vectors not supported");
589 
590   unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
591 
592   assert(DivTyBitWidth <= 32 && "Div of bitwidth greater than 32 not supported");
593 
594   if (DivTyBitWidth == 32)
595     return expandDivision(Div);
596 
597   // If bitwidth smaller than 32 extend inputs, extend output and proceed
598   // with 32 bit division.
599   IRBuilder<> Builder(Div);
600 
601   Value *ExtDividend;
602   Value *ExtDivisor;
603   Value *ExtDiv;
604   Value *Trunc;
605   Type *Int32Ty = Builder.getInt32Ty();
606 
607   if (Div->getOpcode() == Instruction::SDiv) {
608     ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int32Ty);
609     ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int32Ty);
610     ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);
611   } else {
612     ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int32Ty);
613     ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int32Ty);
614     ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);
615   }
616   Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
617 
618   Div->replaceAllUsesWith(Trunc);
619   Div->dropAllReferences();
620   Div->eraseFromParent();
621 
622   return expandDivision(cast<BinaryOperator>(ExtDiv));
623 }
624 
625 /// Generate code to divide two integers of bitwidth up to 64 bits. Uses the
626 /// above routines and extends the inputs/truncates the outputs to operate
627 /// in 64 bits.
628 ///
629 /// Replace Div with emulation code.
630 bool llvm::expandDivisionUpTo64Bits(BinaryOperator *Div) {
631   assert((Div->getOpcode() == Instruction::SDiv ||
632           Div->getOpcode() == Instruction::UDiv) &&
633           "Trying to expand division from a non-division function");
634 
635   Type *DivTy = Div->getType();
636   assert(!DivTy->isVectorTy() && "Div over vectors not supported");
637 
638   unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
639 
640   assert(DivTyBitWidth <= 64 &&
641          "Div of bitwidth greater than 64 not supported");
642 
643   if (DivTyBitWidth == 64)
644     return expandDivision(Div);
645 
646   // If bitwidth smaller than 64 extend inputs, extend output and proceed
647   // with 64 bit division.
648   IRBuilder<> Builder(Div);
649 
650   Value *ExtDividend;
651   Value *ExtDivisor;
652   Value *ExtDiv;
653   Value *Trunc;
654   Type *Int64Ty = Builder.getInt64Ty();
655 
656   if (Div->getOpcode() == Instruction::SDiv) {
657     ExtDividend = Builder.CreateSExt(Div->getOperand(0), Int64Ty);
658     ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int64Ty);
659     ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);
660   } else {
661     ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int64Ty);
662     ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int64Ty);
663     ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);
664   }
665   Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
666 
667   Div->replaceAllUsesWith(Trunc);
668   Div->dropAllReferences();
669   Div->eraseFromParent();
670 
671   return expandDivision(cast<BinaryOperator>(ExtDiv));
672 }
673