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 scalar integer division for
11 // targets that don't have native support. It's largely derived from
12 // compiler-rt's implementation of __udivsi3, but hand-tuned to reduce the
13 // amount of control flow
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #define DEBUG_TYPE "integer-division"
18 #include "llvm/Function.h"
19 #include "llvm/Instructions.h"
20 #include "llvm/Intrinsics.h"
21 #include "llvm/IRBuilder.h"
22 #include "llvm/Transforms/Utils/IntegerDivision.h"
23 
24 using namespace llvm;
25 
26 /// Generate code to divide two signed integers. Returns the quotient, rounded
27 /// towards 0. Builder's insert point should be pointing at the sdiv
28 /// instruction. This will generate a udiv in the process, and Builder's insert
29 /// point will be pointing at the udiv (if present, i.e. not folded), ready to
30 /// be expanded if the user wishes.
31 static Value *generateSignedDivisionCode(Value *Dividend, Value *Divisor,
32                                          IRBuilder<> &Builder) {
33   // Implementation taken from compiler-rt's __divsi3
34 
35   ConstantInt *ThirtyOne = Builder.getInt32(31);
36 
37   // ;   %tmp    = ashr i32 %dividend, 31
38   // ;   %tmp1   = ashr i32 %divisor, 31
39   // ;   %tmp2   = xor i32 %tmp, %dividend
40   // ;   %u_dvnd = sub nsw i32 %tmp2, %tmp
41   // ;   %tmp3   = xor i32 %tmp1, %divisor
42   // ;   %u_dvsr = sub nsw i32 %tmp3, %tmp1
43   // ;   %q_sgn  = xor i32 %tmp1, %tmp
44   // ;   %q_mag  = udiv i32 %u_dvnd, %u_dvsr
45   // ;   %tmp4   = xor i32 %q_mag, %q_sgn
46   // ;   %q      = sub i32 %tmp4, %q_sgn
47   Value *Tmp    = Builder.CreateAShr(Dividend, ThirtyOne);
48   Value *Tmp1   = Builder.CreateAShr(Divisor, ThirtyOne);
49   Value *Tmp2   = Builder.CreateXor(Tmp, Dividend);
50   Value *U_Dvnd = Builder.CreateSub(Tmp2, Tmp);
51   Value *Tmp3   = Builder.CreateXor(Tmp1, Divisor);
52   Value *U_Dvsr = Builder.CreateSub(Tmp3, Tmp1);
53   Value *Q_Sgn  = Builder.CreateXor(Tmp1, Tmp);
54   Value *Q_Mag  = Builder.CreateUDiv(U_Dvnd, U_Dvsr);
55   Value *Tmp4   = Builder.CreateXor(Q_Mag, Q_Sgn);
56   Value *Q      = Builder.CreateSub(Tmp4, Q_Sgn);
57 
58   if (Instruction *UDiv = dyn_cast<Instruction>(Q_Mag))
59     Builder.SetInsertPoint(UDiv);
60 
61   return Q;
62 }
63 
64 /// Generates code to divide two unsigned scalar 32-bit integers. Returns the
65 /// quotient, rounded towards 0. Builder's insert point should be pointing at
66 /// the udiv instruction.
67 static Value *generateUnsignedDivisionCode(Value *Dividend, Value *Divisor,
68                                            IRBuilder<> &Builder) {
69   // The basic algorithm can be found in the compiler-rt project's
70   // implementation of __udivsi3.c. Here, we do a lower-level IR based approach
71   // that's been hand-tuned to lessen the amount of control flow involved.
72 
73   // Some helper values
74   IntegerType *I32Ty = Builder.getInt32Ty();
75 
76   ConstantInt *Zero      = Builder.getInt32(0);
77   ConstantInt *One       = Builder.getInt32(1);
78   ConstantInt *ThirtyOne = Builder.getInt32(31);
79   ConstantInt *NegOne    = ConstantInt::getSigned(I32Ty, -1);
80   ConstantInt *True      = Builder.getTrue();
81 
82   BasicBlock *IBB = Builder.GetInsertBlock();
83   Function *F = IBB->getParent();
84   Function *CTLZi32 = Intrinsic::getDeclaration(F->getParent(), Intrinsic::ctlz,
85                                                 I32Ty);
86 
87   // Our CFG is going to look like:
88   // +---------------------+
89   // | special-cases       |
90   // |   ...               |
91   // +---------------------+
92   //  |       |
93   //  |   +----------+
94   //  |   |  bb1     |
95   //  |   |  ...     |
96   //  |   +----------+
97   //  |    |      |
98   //  |    |  +------------+
99   //  |    |  |  preheader |
100   //  |    |  |  ...       |
101   //  |    |  +------------+
102   //  |    |      |
103   //  |    |      |      +---+
104   //  |    |      |      |   |
105   //  |    |  +------------+ |
106   //  |    |  |  do-while  | |
107   //  |    |  |  ...       | |
108   //  |    |  +------------+ |
109   //  |    |      |      |   |
110   //  |   +-----------+  +---+
111   //  |   | loop-exit |
112   //  |   |  ...      |
113   //  |   +-----------+
114   //  |     |
115   // +-------+
116   // | ...   |
117   // | end   |
118   // +-------+
119   BasicBlock *SpecialCases = Builder.GetInsertBlock();
120   SpecialCases->setName(Twine(SpecialCases->getName(), "_udiv-special-cases"));
121   BasicBlock *End = SpecialCases->splitBasicBlock(Builder.GetInsertPoint(),
122                                                   "udiv-end");
123   BasicBlock *LoopExit  = BasicBlock::Create(Builder.getContext(),
124                                              "udiv-loop-exit", F, End);
125   BasicBlock *DoWhile   = BasicBlock::Create(Builder.getContext(),
126                                              "udiv-do-while", F, End);
127   BasicBlock *Preheader = BasicBlock::Create(Builder.getContext(),
128                                              "udiv-preheader", F, End);
129   BasicBlock *BB1       = BasicBlock::Create(Builder.getContext(),
130                                              "udiv-bb1", F, End);
131 
132   // We'll be overwriting the terminator to insert our extra blocks
133   SpecialCases->getTerminator()->eraseFromParent();
134 
135   // First off, check for special cases: dividend or divisor is zero, divisor
136   // is greater than dividend, and divisor is 1.
137   // ; special-cases:
138   // ;   %ret0_1      = icmp eq i32 %divisor, 0
139   // ;   %ret0_2      = icmp eq i32 %dividend, 0
140   // ;   %ret0_3      = or i1 %ret0_1, %ret0_2
141   // ;   %tmp0        = tail call i32 @llvm.ctlz.i32(i32 %divisor, i1 true)
142   // ;   %tmp1        = tail call i32 @llvm.ctlz.i32(i32 %dividend, i1 true)
143   // ;   %sr          = sub nsw i32 %tmp0, %tmp1
144   // ;   %ret0_4      = icmp ugt i32 %sr, 31
145   // ;   %ret0        = or i1 %ret0_3, %ret0_4
146   // ;   %retDividend = icmp eq i32 %sr, 31
147   // ;   %retVal      = select i1 %ret0, i32 0, i32 %dividend
148   // ;   %earlyRet    = or i1 %ret0, %retDividend
149   // ;   br i1 %earlyRet, label %end, label %bb1
150   Builder.SetInsertPoint(SpecialCases);
151   Value *Ret0_1      = Builder.CreateICmpEQ(Divisor, Zero);
152   Value *Ret0_2      = Builder.CreateICmpEQ(Dividend, Zero);
153   Value *Ret0_3      = Builder.CreateOr(Ret0_1, Ret0_2);
154   Value *Tmp0        = Builder.CreateCall2(CTLZi32, Divisor, True);
155   Value *Tmp1        = Builder.CreateCall2(CTLZi32, Dividend, True);
156   Value *SR          = Builder.CreateSub(Tmp0, Tmp1);
157   Value *Ret0_4      = Builder.CreateICmpUGT(SR, ThirtyOne);
158   Value *Ret0        = Builder.CreateOr(Ret0_3, Ret0_4);
159   Value *RetDividend = Builder.CreateICmpEQ(SR, ThirtyOne);
160   Value *RetVal      = Builder.CreateSelect(Ret0, Zero, Dividend);
161   Value *EarlyRet    = Builder.CreateOr(Ret0, RetDividend);
162   Builder.CreateCondBr(EarlyRet, End, BB1);
163 
164   // ; bb1:                                             ; preds = %special-cases
165   // ;   %sr_1     = add i32 %sr, 1
166   // ;   %tmp2     = sub i32 31, %sr
167   // ;   %q        = shl i32 %dividend, %tmp2
168   // ;   %skipLoop = icmp eq i32 %sr_1, 0
169   // ;   br i1 %skipLoop, label %loop-exit, label %preheader
170   Builder.SetInsertPoint(BB1);
171   Value *SR_1     = Builder.CreateAdd(SR, One);
172   Value *Tmp2     = Builder.CreateSub(ThirtyOne, SR);
173   Value *Q        = Builder.CreateShl(Dividend, Tmp2);
174   Value *SkipLoop = Builder.CreateICmpEQ(SR_1, Zero);
175   Builder.CreateCondBr(SkipLoop, LoopExit, Preheader);
176 
177   // ; preheader:                                           ; preds = %bb1
178   // ;   %tmp3 = lshr i32 %dividend, %sr_1
179   // ;   %tmp4 = add i32 %divisor, -1
180   // ;   br label %do-while
181   Builder.SetInsertPoint(Preheader);
182   Value *Tmp3 = Builder.CreateLShr(Dividend, SR_1);
183   Value *Tmp4 = Builder.CreateAdd(Divisor, NegOne);
184   Builder.CreateBr(DoWhile);
185 
186   // ; do-while:                                 ; preds = %do-while, %preheader
187   // ;   %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]
188   // ;   %sr_3    = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
189   // ;   %r_1     = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
190   // ;   %q_2     = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
191   // ;   %tmp5  = shl i32 %r_1, 1
192   // ;   %tmp6  = lshr i32 %q_2, 31
193   // ;   %tmp7  = or i32 %tmp5, %tmp6
194   // ;   %tmp8  = shl i32 %q_2, 1
195   // ;   %q_1   = or i32 %carry_1, %tmp8
196   // ;   %tmp9  = sub i32 %tmp4, %tmp7
197   // ;   %tmp10 = ashr i32 %tmp9, 31
198   // ;   %carry = and i32 %tmp10, 1
199   // ;   %tmp11 = and i32 %tmp10, %divisor
200   // ;   %r     = sub i32 %tmp7, %tmp11
201   // ;   %sr_2  = add i32 %sr_3, -1
202   // ;   %tmp12 = icmp eq i32 %sr_2, 0
203   // ;   br i1 %tmp12, label %loop-exit, label %do-while
204   Builder.SetInsertPoint(DoWhile);
205   PHINode *Carry_1 = Builder.CreatePHI(I32Ty, 2);
206   PHINode *SR_3    = Builder.CreatePHI(I32Ty, 2);
207   PHINode *R_1     = Builder.CreatePHI(I32Ty, 2);
208   PHINode *Q_2     = Builder.CreatePHI(I32Ty, 2);
209   Value *Tmp5  = Builder.CreateShl(R_1, One);
210   Value *Tmp6  = Builder.CreateLShr(Q_2, ThirtyOne);
211   Value *Tmp7  = Builder.CreateOr(Tmp5, Tmp6);
212   Value *Tmp8  = Builder.CreateShl(Q_2, One);
213   Value *Q_1   = Builder.CreateOr(Carry_1, Tmp8);
214   Value *Tmp9  = Builder.CreateSub(Tmp4, Tmp7);
215   Value *Tmp10 = Builder.CreateAShr(Tmp9, 31);
216   Value *Carry = Builder.CreateAnd(Tmp10, One);
217   Value *Tmp11 = Builder.CreateAnd(Tmp10, Divisor);
218   Value *R     = Builder.CreateSub(Tmp7, Tmp11);
219   Value *SR_2  = Builder.CreateAdd(SR_3, NegOne);
220   Value *Tmp12 = Builder.CreateICmpEQ(SR_2, Zero);
221   Builder.CreateCondBr(Tmp12, LoopExit, DoWhile);
222 
223   // ; loop-exit:                                      ; preds = %do-while, %bb1
224   // ;   %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
225   // ;   %q_3     = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
226   // ;   %tmp13 = shl i32 %q_3, 1
227   // ;   %q_4   = or i32 %carry_2, %tmp13
228   // ;   br label %end
229   Builder.SetInsertPoint(LoopExit);
230   PHINode *Carry_2 = Builder.CreatePHI(I32Ty, 2);
231   PHINode *Q_3     = Builder.CreatePHI(I32Ty, 2);
232   Value *Tmp13 = Builder.CreateShl(Q_3, One);
233   Value *Q_4   = Builder.CreateOr(Carry_2, Tmp13);
234   Builder.CreateBr(End);
235 
236   // ; end:                                 ; preds = %loop-exit, %special-cases
237   // ;   %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
238   // ;   ret i32 %q_5
239   Builder.SetInsertPoint(End, End->begin());
240   PHINode *Q_5 = Builder.CreatePHI(I32Ty, 2);
241 
242   // Populate the Phis, since all values have now been created. Our Phis were:
243   // ;   %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]
244   Carry_1->addIncoming(Zero, Preheader);
245   Carry_1->addIncoming(Carry, DoWhile);
246   // ;   %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
247   SR_3->addIncoming(SR_1, Preheader);
248   SR_3->addIncoming(SR_2, DoWhile);
249   // ;   %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
250   R_1->addIncoming(Tmp3, Preheader);
251   R_1->addIncoming(R, DoWhile);
252   // ;   %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
253   Q_2->addIncoming(Q, Preheader);
254   Q_2->addIncoming(Q_1, DoWhile);
255   // ;   %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
256   Carry_2->addIncoming(Zero, BB1);
257   Carry_2->addIncoming(Carry, DoWhile);
258   // ;   %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
259   Q_3->addIncoming(Q, BB1);
260   Q_3->addIncoming(Q_1, DoWhile);
261   // ;   %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
262   Q_5->addIncoming(Q_4, LoopExit);
263   Q_5->addIncoming(RetVal, SpecialCases);
264 
265   return Q_5;
266 }
267 
268 /// Generate code to divide two integers, replacing Div with the generated
269 /// code. This currently generates code similarly to compiler-rt's
270 /// implementations, but future work includes generating more specialized code
271 /// when more information about the operands are known. Currently only
272 /// implements 32bit scalar division, but future work is removing this
273 /// limitation.
274 ///
275 /// @brief Replace Div with generated code.
276 bool llvm::expandDivision(BinaryOperator *Div) {
277   assert((Div->getOpcode() == Instruction::SDiv ||
278           Div->getOpcode() == Instruction::UDiv) &&
279          "Trying to expand division from a non-division function");
280 
281   IRBuilder<> Builder(Div);
282 
283   if (Div->getType()->isVectorTy())
284     llvm_unreachable("Div over vectors not supported");
285 
286   // First prepare the sign if it's a signed division
287   if (Div->getOpcode() == Instruction::SDiv) {
288     // Lower the code to unsigned division, and reset Div to point to the udiv.
289     Value *Quotient = generateSignedDivisionCode(Div->getOperand(0),
290                                                 Div->getOperand(1), Builder);
291     Div->replaceAllUsesWith(Quotient);
292     Div->dropAllReferences();
293     Div->eraseFromParent();
294 
295     // If we didn't actually generate a udiv instruction, we're done
296     BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
297     if (!BO || BO->getOpcode() != Instruction::UDiv)
298       return true;
299 
300     Div = BO;
301   }
302 
303   // Insert the unsigned division code
304   Value *Quotient = generateUnsignedDivisionCode(Div->getOperand(0),
305                                                  Div->getOperand(1),
306                                                  Builder);
307   Div->replaceAllUsesWith(Quotient);
308   Div->dropAllReferences();
309   Div->eraseFromParent();
310 
311   return true;
312 }
313