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
24using 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
34static 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
80static 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.
104static 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.
151static 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.
376bool 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 a udiv instruction, we're done
402    BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
403    if (!BO || BO->getOpcode() != Instruction::URem)
404      return true;
405
406    Rem = BO;
407  }
408
409  Value *Remainder = generatedUnsignedRemainderCode(Rem->getOperand(0),
410                                                    Rem->getOperand(1),
411                                                    Builder);
412
413  Rem->replaceAllUsesWith(Remainder);
414  Rem->dropAllReferences();
415  Rem->eraseFromParent();
416
417  // Expand the udiv
418  if (BinaryOperator *UDiv = dyn_cast<BinaryOperator>(Builder.GetInsertPoint())) {
419    assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?");
420    expandDivision(UDiv);
421  }
422
423  return true;
424}
425
426
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.
432///
433/// @brief Replace Div with generated code.
434bool 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");
438
439  IRBuilder<> Builder(Div);
440
441  Type *DivTy = Div->getType();
442  if (DivTy->isVectorTy())
443    llvm_unreachable("Div over vectors not supported");
444
445  unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
446
447  if (DivTyBitWidth != 32 && DivTyBitWidth != 64)
448    llvm_unreachable("Div of bitwidth other than 32 or 64 not supported");
449
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();
458
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)
462      return true;
463
464    Div = BO;
465  }
466
467  // Insert the unsigned division code
468  Value *Quotient = generateUnsignedDivisionCode(Div->getOperand(0),
469                                                 Div->getOperand(1),
470                                                 Builder);
471  Div->replaceAllUsesWith(Quotient);
472  Div->dropAllReferences();
473  Div->eraseFromParent();
474
475  return true;
476}
477
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
482/// arithmetic.
483///
484/// @brief Replace Rem with emulation code.
485bool 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");
489
490  Type *RemTy = Rem->getType();
491  if (RemTy->isVectorTy())
492    llvm_unreachable("Div over vectors not supported");
493
494  unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
495
496  if (RemTyBitWidth > 32)
497    llvm_unreachable("Div of bitwidth greater than 32 not supported");
498
499  if (RemTyBitWidth == 32)
500    return expandRemainder(Rem);
501
502  // If bitwidth smaller than 32 extend inputs, extend output and proceed
503  // with 32 bit division.
504  IRBuilder<> Builder(Rem);
505
506  Value *ExtDividend;
507  Value *ExtDivisor;
508  Value *ExtRem;
509  Value *Trunc;
510  Type *Int32Ty = Builder.getInt32Ty();
511
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);
516  } else {
517    ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int32Ty);
518    ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int32Ty);
519    ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
520  }
521  Trunc = Builder.CreateTrunc(ExtRem, RemTy);
522
523  Rem->replaceAllUsesWith(Trunc);
524  Rem->dropAllReferences();
525  Rem->eraseFromParent();
526
527  return expandRemainder(cast<BinaryOperator>(ExtRem));
528}
529
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.
533///
534/// @brief Replace Rem with emulation code.
535bool 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");
539
540  Type *RemTy = Rem->getType();
541  if (RemTy->isVectorTy())
542    llvm_unreachable("Div over vectors not supported");
543
544  unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
545
546  if (RemTyBitWidth > 64)
547    llvm_unreachable("Div of bitwidth greater than 64 not supported");
548
549  if (RemTyBitWidth == 64)
550    return expandRemainder(Rem);
551
552  // If bitwidth smaller than 64 extend inputs, extend output and proceed
553  // with 64 bit division.
554  IRBuilder<> Builder(Rem);
555
556  Value *ExtDividend;
557  Value *ExtDivisor;
558  Value *ExtRem;
559  Value *Trunc;
560  Type *Int64Ty = Builder.getInt64Ty();
561
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);
566  } else {
567    ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int64Ty);
568    ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int64Ty);
569    ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
570  }
571  Trunc = Builder.CreateTrunc(ExtRem, RemTy);
572
573  Rem->replaceAllUsesWith(Trunc);
574  Rem->dropAllReferences();
575  Rem->eraseFromParent();
576
577  return expandRemainder(cast<BinaryOperator>(ExtRem));
578}
579
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.
584///
585/// @brief Replace Div with emulation code.
586bool 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");
590
591  Type *DivTy = Div->getType();
592  if (DivTy->isVectorTy())
593    llvm_unreachable("Div over vectors not supported");
594
595  unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
596
597  if (DivTyBitWidth > 32)
598    llvm_unreachable("Div of bitwidth greater than 32 not supported");
599
600  if (DivTyBitWidth == 32)
601    return expandDivision(Div);
602
603  // If bitwidth smaller than 32 extend inputs, extend output and proceed
604  // with 32 bit division.
605  IRBuilder<> Builder(Div);
606
607  Value *ExtDividend;
608  Value *ExtDivisor;
609  Value *ExtDiv;
610  Value *Trunc;
611  Type *Int32Ty = Builder.getInt32Ty();
612
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);
617  } else {
618    ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int32Ty);
619    ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int32Ty);
620    ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);
621  }
622  Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
623
624  Div->replaceAllUsesWith(Trunc);
625  Div->dropAllReferences();
626  Div->eraseFromParent();
627
628  return expandDivision(cast<BinaryOperator>(ExtDiv));
629}
630
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
633/// in 64 bits.
634///
635/// @brief Replace Div with emulation code.
636bool 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");
640
641  Type *DivTy = Div->getType();
642  if (DivTy->isVectorTy())
643    llvm_unreachable("Div over vectors not supported");
644
645  unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
646
647  if (DivTyBitWidth > 64)
648    llvm_unreachable("Div of bitwidth greater than 64 not supported");
649
650  if (DivTyBitWidth == 64)
651    return expandDivision(Div);
652
653  // If bitwidth smaller than 64 extend inputs, extend output and proceed
654  // with 64 bit division.
655  IRBuilder<> Builder(Div);
656
657  Value *ExtDividend;
658  Value *ExtDivisor;
659  Value *ExtDiv;
660  Value *Trunc;
661  Type *Int64Ty = Builder.getInt64Ty();
662
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);
667  } else {
668    ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int64Ty);
669    ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int64Ty);
670    ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);
671  }
672  Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
673
674  Div->replaceAllUsesWith(Trunc);
675  Div->dropAllReferences();
676  Div->eraseFromParent();
677
678  return expandDivision(cast<BinaryOperator>(ExtDiv));
679}
680