1 //===-- IntegerDivision.cpp - Expand integer division ---------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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
15 //===----------------------------------------------------------------------===//
17 #define DEBUG_TYPE "integer-division"
18 #include "llvm/Transforms/Utils/IntegerDivision.h"
19 #include "llvm/IR/Function.h"
20 #include "llvm/IR/IRBuilder.h"
21 #include "llvm/IR/Instructions.h"
22 #include "llvm/IR/Intrinsics.h"
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 ConstantInt *ThirtyOne = Builder.getInt32(31);
36 // ; %dividend_sgn = ashr i32 %dividend, 31
37 // ; %divisor_sgn = ashr i32 %divisor, 31
38 // ; %dvd_xor = xor i32 %dividend, %dividend_sgn
39 // ; %dvs_xor = xor i32 %divisor, %divisor_sgn
40 // ; %u_dividend = sub i32 %dvd_xor, %dividend_sgn
41 // ; %u_divisor = sub i32 %dvs_xor, %divisor_sgn
42 // ; %urem = urem i32 %dividend, %divisor
43 // ; %xored = xor i32 %urem, %dividend_sgn
44 // ; %srem = sub i32 %xored, %dividend_sgn
45 Value *DividendSign = Builder.CreateAShr(Dividend, ThirtyOne);
46 Value *DivisorSign = Builder.CreateAShr(Divisor, ThirtyOne);
47 Value *DvdXor = Builder.CreateXor(Dividend, DividendSign);
48 Value *DvsXor = Builder.CreateXor(Divisor, DivisorSign);
49 Value *UDividend = Builder.CreateSub(DvdXor, DividendSign);
50 Value *UDivisor = Builder.CreateSub(DvsXor, DivisorSign);
51 Value *URem = Builder.CreateURem(UDividend, UDivisor);
52 Value *Xored = Builder.CreateXor(URem, DividendSign);
53 Value *SRem = Builder.CreateSub(Xored, DividendSign);
55 if (Instruction *URemInst = dyn_cast<Instruction>(URem))
56 Builder.SetInsertPoint(URemInst);
62 /// Generate code to compute the remainder of two unsigned integers. Returns the
63 /// remainder. Builder's insert point should be pointing where the caller wants
64 /// code generated, e.g. at the urem instruction. This will generate a udiv in
65 /// the process, and Builder's insert point will be pointing at the udiv (if
66 /// present, i.e. not folded), ready to be expanded if the user wishes
67 static Value *generatedUnsignedRemainderCode(Value *Dividend, Value *Divisor,
68 IRBuilder<> &Builder) {
69 // Remainder = Dividend - Quotient*Divisor
71 // ; %quotient = udiv i32 %dividend, %divisor
72 // ; %product = mul i32 %divisor, %quotient
73 // ; %remainder = sub i32 %dividend, %product
74 Value *Quotient = Builder.CreateUDiv(Dividend, Divisor);
75 Value *Product = Builder.CreateMul(Divisor, Quotient);
76 Value *Remainder = Builder.CreateSub(Dividend, Product);
78 if (Instruction *UDiv = dyn_cast<Instruction>(Quotient))
79 Builder.SetInsertPoint(UDiv);
84 /// Generate code to divide two signed integers. Returns the quotient, rounded
85 /// towards 0. Builder's insert point should be pointing where the caller wants
86 /// code generated, e.g. at the sdiv instruction. This will generate a udiv in
87 /// the process, and Builder's insert point will be pointing at the udiv (if
88 /// present, i.e. not folded), ready to be expanded if the user wishes.
89 static Value *generateSignedDivisionCode(Value *Dividend, Value *Divisor,
90 IRBuilder<> &Builder) {
91 // Implementation taken from compiler-rt's __divsi3
93 ConstantInt *ThirtyOne = Builder.getInt32(31);
95 // ; %tmp = ashr i32 %dividend, 31
96 // ; %tmp1 = ashr i32 %divisor, 31
97 // ; %tmp2 = xor i32 %tmp, %dividend
98 // ; %u_dvnd = sub nsw i32 %tmp2, %tmp
99 // ; %tmp3 = xor i32 %tmp1, %divisor
100 // ; %u_dvsr = sub nsw i32 %tmp3, %tmp1
101 // ; %q_sgn = xor i32 %tmp1, %tmp
102 // ; %q_mag = udiv i32 %u_dvnd, %u_dvsr
103 // ; %tmp4 = xor i32 %q_mag, %q_sgn
104 // ; %q = sub i32 %tmp4, %q_sgn
105 Value *Tmp = Builder.CreateAShr(Dividend, ThirtyOne);
106 Value *Tmp1 = Builder.CreateAShr(Divisor, ThirtyOne);
107 Value *Tmp2 = Builder.CreateXor(Tmp, Dividend);
108 Value *U_Dvnd = Builder.CreateSub(Tmp2, Tmp);
109 Value *Tmp3 = Builder.CreateXor(Tmp1, Divisor);
110 Value *U_Dvsr = Builder.CreateSub(Tmp3, Tmp1);
111 Value *Q_Sgn = Builder.CreateXor(Tmp1, Tmp);
112 Value *Q_Mag = Builder.CreateUDiv(U_Dvnd, U_Dvsr);
113 Value *Tmp4 = Builder.CreateXor(Q_Mag, Q_Sgn);
114 Value *Q = Builder.CreateSub(Tmp4, Q_Sgn);
116 if (Instruction *UDiv = dyn_cast<Instruction>(Q_Mag))
117 Builder.SetInsertPoint(UDiv);
122 /// Generates code to divide two unsigned scalar 32-bit integers. Returns the
123 /// quotient, rounded towards 0. Builder's insert point should be pointing where
124 /// the caller wants code generated, e.g. at the udiv instruction.
125 static Value *generateUnsignedDivisionCode(Value *Dividend, Value *Divisor,
126 IRBuilder<> &Builder) {
127 // The basic algorithm can be found in the compiler-rt project's
128 // implementation of __udivsi3.c. Here, we do a lower-level IR based approach
129 // that's been hand-tuned to lessen the amount of control flow involved.
131 // Some helper values
132 IntegerType *I32Ty = Builder.getInt32Ty();
134 ConstantInt *Zero = Builder.getInt32(0);
135 ConstantInt *One = Builder.getInt32(1);
136 ConstantInt *ThirtyOne = Builder.getInt32(31);
137 ConstantInt *NegOne = ConstantInt::getSigned(I32Ty, -1);
138 ConstantInt *True = Builder.getTrue();
140 BasicBlock *IBB = Builder.GetInsertBlock();
141 Function *F = IBB->getParent();
142 Function *CTLZi32 = Intrinsic::getDeclaration(F->getParent(), Intrinsic::ctlz,
145 // Our CFG is going to look like:
146 // +---------------------+
149 // +---------------------+
156 // | | +------------+
159 // | | +------------+
163 // | | +------------+ |
164 // | | | do-while | |
166 // | | +------------+ |
168 // | +-----------+ +---+
177 BasicBlock *SpecialCases = Builder.GetInsertBlock();
178 SpecialCases->setName(Twine(SpecialCases->getName(), "_udiv-special-cases"));
179 BasicBlock *End = SpecialCases->splitBasicBlock(Builder.GetInsertPoint(),
181 BasicBlock *LoopExit = BasicBlock::Create(Builder.getContext(),
182 "udiv-loop-exit", F, End);
183 BasicBlock *DoWhile = BasicBlock::Create(Builder.getContext(),
184 "udiv-do-while", F, End);
185 BasicBlock *Preheader = BasicBlock::Create(Builder.getContext(),
186 "udiv-preheader", F, End);
187 BasicBlock *BB1 = BasicBlock::Create(Builder.getContext(),
190 // We'll be overwriting the terminator to insert our extra blocks
191 SpecialCases->getTerminator()->eraseFromParent();
193 // First off, check for special cases: dividend or divisor is zero, divisor
194 // is greater than dividend, and divisor is 1.
196 // ; %ret0_1 = icmp eq i32 %divisor, 0
197 // ; %ret0_2 = icmp eq i32 %dividend, 0
198 // ; %ret0_3 = or i1 %ret0_1, %ret0_2
199 // ; %tmp0 = tail call i32 @llvm.ctlz.i32(i32 %divisor, i1 true)
200 // ; %tmp1 = tail call i32 @llvm.ctlz.i32(i32 %dividend, i1 true)
201 // ; %sr = sub nsw i32 %tmp0, %tmp1
202 // ; %ret0_4 = icmp ugt i32 %sr, 31
203 // ; %ret0 = or i1 %ret0_3, %ret0_4
204 // ; %retDividend = icmp eq i32 %sr, 31
205 // ; %retVal = select i1 %ret0, i32 0, i32 %dividend
206 // ; %earlyRet = or i1 %ret0, %retDividend
207 // ; br i1 %earlyRet, label %end, label %bb1
208 Builder.SetInsertPoint(SpecialCases);
209 Value *Ret0_1 = Builder.CreateICmpEQ(Divisor, Zero);
210 Value *Ret0_2 = Builder.CreateICmpEQ(Dividend, Zero);
211 Value *Ret0_3 = Builder.CreateOr(Ret0_1, Ret0_2);
212 Value *Tmp0 = Builder.CreateCall2(CTLZi32, Divisor, True);
213 Value *Tmp1 = Builder.CreateCall2(CTLZi32, Dividend, True);
214 Value *SR = Builder.CreateSub(Tmp0, Tmp1);
215 Value *Ret0_4 = Builder.CreateICmpUGT(SR, ThirtyOne);
216 Value *Ret0 = Builder.CreateOr(Ret0_3, Ret0_4);
217 Value *RetDividend = Builder.CreateICmpEQ(SR, ThirtyOne);
218 Value *RetVal = Builder.CreateSelect(Ret0, Zero, Dividend);
219 Value *EarlyRet = Builder.CreateOr(Ret0, RetDividend);
220 Builder.CreateCondBr(EarlyRet, End, BB1);
222 // ; bb1: ; preds = %special-cases
223 // ; %sr_1 = add i32 %sr, 1
224 // ; %tmp2 = sub i32 31, %sr
225 // ; %q = shl i32 %dividend, %tmp2
226 // ; %skipLoop = icmp eq i32 %sr_1, 0
227 // ; br i1 %skipLoop, label %loop-exit, label %preheader
228 Builder.SetInsertPoint(BB1);
229 Value *SR_1 = Builder.CreateAdd(SR, One);
230 Value *Tmp2 = Builder.CreateSub(ThirtyOne, SR);
231 Value *Q = Builder.CreateShl(Dividend, Tmp2);
232 Value *SkipLoop = Builder.CreateICmpEQ(SR_1, Zero);
233 Builder.CreateCondBr(SkipLoop, LoopExit, Preheader);
235 // ; preheader: ; preds = %bb1
236 // ; %tmp3 = lshr i32 %dividend, %sr_1
237 // ; %tmp4 = add i32 %divisor, -1
238 // ; br label %do-while
239 Builder.SetInsertPoint(Preheader);
240 Value *Tmp3 = Builder.CreateLShr(Dividend, SR_1);
241 Value *Tmp4 = Builder.CreateAdd(Divisor, NegOne);
242 Builder.CreateBr(DoWhile);
244 // ; do-while: ; preds = %do-while, %preheader
245 // ; %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]
246 // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
247 // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
248 // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
249 // ; %tmp5 = shl i32 %r_1, 1
250 // ; %tmp6 = lshr i32 %q_2, 31
251 // ; %tmp7 = or i32 %tmp5, %tmp6
252 // ; %tmp8 = shl i32 %q_2, 1
253 // ; %q_1 = or i32 %carry_1, %tmp8
254 // ; %tmp9 = sub i32 %tmp4, %tmp7
255 // ; %tmp10 = ashr i32 %tmp9, 31
256 // ; %carry = and i32 %tmp10, 1
257 // ; %tmp11 = and i32 %tmp10, %divisor
258 // ; %r = sub i32 %tmp7, %tmp11
259 // ; %sr_2 = add i32 %sr_3, -1
260 // ; %tmp12 = icmp eq i32 %sr_2, 0
261 // ; br i1 %tmp12, label %loop-exit, label %do-while
262 Builder.SetInsertPoint(DoWhile);
263 PHINode *Carry_1 = Builder.CreatePHI(I32Ty, 2);
264 PHINode *SR_3 = Builder.CreatePHI(I32Ty, 2);
265 PHINode *R_1 = Builder.CreatePHI(I32Ty, 2);
266 PHINode *Q_2 = Builder.CreatePHI(I32Ty, 2);
267 Value *Tmp5 = Builder.CreateShl(R_1, One);
268 Value *Tmp6 = Builder.CreateLShr(Q_2, ThirtyOne);
269 Value *Tmp7 = Builder.CreateOr(Tmp5, Tmp6);
270 Value *Tmp8 = Builder.CreateShl(Q_2, One);
271 Value *Q_1 = Builder.CreateOr(Carry_1, Tmp8);
272 Value *Tmp9 = Builder.CreateSub(Tmp4, Tmp7);
273 Value *Tmp10 = Builder.CreateAShr(Tmp9, 31);
274 Value *Carry = Builder.CreateAnd(Tmp10, One);
275 Value *Tmp11 = Builder.CreateAnd(Tmp10, Divisor);
276 Value *R = Builder.CreateSub(Tmp7, Tmp11);
277 Value *SR_2 = Builder.CreateAdd(SR_3, NegOne);
278 Value *Tmp12 = Builder.CreateICmpEQ(SR_2, Zero);
279 Builder.CreateCondBr(Tmp12, LoopExit, DoWhile);
281 // ; loop-exit: ; preds = %do-while, %bb1
282 // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
283 // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
284 // ; %tmp13 = shl i32 %q_3, 1
285 // ; %q_4 = or i32 %carry_2, %tmp13
287 Builder.SetInsertPoint(LoopExit);
288 PHINode *Carry_2 = Builder.CreatePHI(I32Ty, 2);
289 PHINode *Q_3 = Builder.CreatePHI(I32Ty, 2);
290 Value *Tmp13 = Builder.CreateShl(Q_3, One);
291 Value *Q_4 = Builder.CreateOr(Carry_2, Tmp13);
292 Builder.CreateBr(End);
294 // ; end: ; preds = %loop-exit, %special-cases
295 // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
297 Builder.SetInsertPoint(End, End->begin());
298 PHINode *Q_5 = Builder.CreatePHI(I32Ty, 2);
300 // Populate the Phis, since all values have now been created. Our Phis were:
301 // ; %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]
302 Carry_1->addIncoming(Zero, Preheader);
303 Carry_1->addIncoming(Carry, DoWhile);
304 // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
305 SR_3->addIncoming(SR_1, Preheader);
306 SR_3->addIncoming(SR_2, DoWhile);
307 // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
308 R_1->addIncoming(Tmp3, Preheader);
309 R_1->addIncoming(R, DoWhile);
310 // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
311 Q_2->addIncoming(Q, Preheader);
312 Q_2->addIncoming(Q_1, DoWhile);
313 // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
314 Carry_2->addIncoming(Zero, BB1);
315 Carry_2->addIncoming(Carry, DoWhile);
316 // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
317 Q_3->addIncoming(Q, BB1);
318 Q_3->addIncoming(Q_1, DoWhile);
319 // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
320 Q_5->addIncoming(Q_4, LoopExit);
321 Q_5->addIncoming(RetVal, SpecialCases);
326 /// Generate code to calculate the remainder of two integers, replacing Rem with
327 /// the generated code. This currently generates code using the udiv expansion,
328 /// but future work includes generating more specialized code, e.g. when more
329 /// information about the operands are known. Currently only implements 32bit
330 /// scalar division (due to udiv's limitation), but future work is removing this
333 /// @brief Replace Rem with generated code.
334 bool llvm::expandRemainder(BinaryOperator *Rem) {
335 assert((Rem->getOpcode() == Instruction::SRem ||
336 Rem->getOpcode() == Instruction::URem) &&
337 "Trying to expand remainder from a non-remainder function");
339 IRBuilder<> Builder(Rem);
341 // First prepare the sign if it's a signed remainder
342 if (Rem->getOpcode() == Instruction::SRem) {
343 Value *Remainder = generateSignedRemainderCode(Rem->getOperand(0),
344 Rem->getOperand(1), Builder);
346 Rem->replaceAllUsesWith(Remainder);
347 Rem->dropAllReferences();
348 Rem->eraseFromParent();
350 // If we didn't actually generate a udiv instruction, we're done
351 BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
352 if (!BO || BO->getOpcode() != Instruction::URem)
358 Value *Remainder = generatedUnsignedRemainderCode(Rem->getOperand(0),
362 Rem->replaceAllUsesWith(Remainder);
363 Rem->dropAllReferences();
364 Rem->eraseFromParent();
367 if (BinaryOperator *UDiv = dyn_cast<BinaryOperator>(Builder.GetInsertPoint())) {
368 assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?");
369 expandDivision(UDiv);
376 /// Generate code to divide two integers, replacing Div with the generated
377 /// code. This currently generates code similarly to compiler-rt's
378 /// implementations, but future work includes generating more specialized code
379 /// when more information about the operands are known. Currently only
380 /// implements 32bit scalar division, but future work is removing this
383 /// @brief Replace Div with generated code.
384 bool llvm::expandDivision(BinaryOperator *Div) {
385 assert((Div->getOpcode() == Instruction::SDiv ||
386 Div->getOpcode() == Instruction::UDiv) &&
387 "Trying to expand division from a non-division function");
389 IRBuilder<> Builder(Div);
391 if (Div->getType()->isVectorTy())
392 llvm_unreachable("Div over vectors not supported");
394 // First prepare the sign if it's a signed division
395 if (Div->getOpcode() == Instruction::SDiv) {
396 // Lower the code to unsigned division, and reset Div to point to the udiv.
397 Value *Quotient = generateSignedDivisionCode(Div->getOperand(0),
398 Div->getOperand(1), Builder);
399 Div->replaceAllUsesWith(Quotient);
400 Div->dropAllReferences();
401 Div->eraseFromParent();
403 // If we didn't actually generate a udiv instruction, we're done
404 BinaryOperator *BO = dyn_cast<BinaryOperator>(Builder.GetInsertPoint());
405 if (!BO || BO->getOpcode() != Instruction::UDiv)
411 // Insert the unsigned division code
412 Value *Quotient = generateUnsignedDivisionCode(Div->getOperand(0),
415 Div->replaceAllUsesWith(Quotient);
416 Div->dropAllReferences();
417 Div->eraseFromParent();