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