]>
git.proxmox.com Git - rustc.git/blob - src/llvm/lib/Transforms/Utils/IntegerDivision.cpp
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 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.
15 //===----------------------------------------------------------------------===//
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"
26 #define DEBUG_TYPE "integer-division"
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
34 static Value
*generateSignedRemainderCode(Value
*Dividend
, Value
*Divisor
,
35 IRBuilder
<> &Builder
) {
36 unsigned BitWidth
= Dividend
->getType()->getIntegerBitWidth();
40 Shift
= Builder
.getInt64(63);
42 assert(BitWidth
== 32 && "Unexpected bit width");
43 Shift
= Builder
.getInt32(31);
46 // Following instructions are generated for both i32 (shift 31) and
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
);
68 if (Instruction
*URemInst
= dyn_cast
<Instruction
>(URem
))
69 Builder
.SetInsertPoint(URemInst
);
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
80 static Value
*generatedUnsignedRemainderCode(Value
*Dividend
, Value
*Divisor
,
81 IRBuilder
<> &Builder
) {
82 // Remainder = Dividend - Quotient*Divisor
84 // Following instructions are generated for both i32 and i64
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
);
93 if (Instruction
*UDiv
= dyn_cast
<Instruction
>(Quotient
))
94 Builder
.SetInsertPoint(UDiv
);
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.
104 static Value
*generateSignedDivisionCode(Value
*Dividend
, Value
*Divisor
,
105 IRBuilder
<> &Builder
) {
106 // Implementation taken from compiler-rt's __divsi3 and __divdi3
108 unsigned BitWidth
= Dividend
->getType()->getIntegerBitWidth();
111 if (BitWidth
== 64) {
112 Shift
= Builder
.getInt64(63);
114 assert(BitWidth
== 32 && "Unexpected bit width");
115 Shift
= Builder
.getInt32(31);
118 // Following instructions are generated for both i32 (shift 31) and
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
);
142 if (Instruction
*UDiv
= dyn_cast
<Instruction
>(Q_Mag
))
143 Builder
.SetInsertPoint(UDiv
);
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.
151 static 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.
157 // Some helper values
158 IntegerType
*DivTy
= cast
<IntegerType
>(Dividend
->getType());
159 unsigned BitWidth
= DivTy
->getBitWidth();
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);
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);
179 ConstantInt
*True
= Builder
.getTrue();
181 BasicBlock
*IBB
= Builder
.GetInsertBlock();
182 Function
*F
= IBB
->getParent();
183 Function
*CTLZ
= Intrinsic::getDeclaration(F
->getParent(), Intrinsic::ctlz
,
186 // Our CFG is going to look like:
187 // +---------------------+
190 // +---------------------+
197 // | | +------------+
200 // | | +------------+
204 // | | +------------+ |
205 // | | | do-while | |
207 // | | +------------+ |
209 // | +-----------+ +---+
218 BasicBlock
*SpecialCases
= Builder
.GetInsertBlock();
219 SpecialCases
->setName(Twine(SpecialCases
->getName(), "_udiv-special-cases"));
220 BasicBlock
*End
= SpecialCases
->splitBasicBlock(Builder
.GetInsertPoint(),
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(),
231 // We'll be overwriting the terminator to insert our extra blocks
232 SpecialCases
->getTerminator()->eraseFromParent();
234 // Same instructions are generated for both i32 (msb 31) and i64 (msb 63).
236 // First off, check for special cases: dividend or divisor is zero, divisor
237 // is greater than dividend, and divisor is 1.
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
);
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
);
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
);
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
);
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
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
);
337 // ; end: ; preds = %loop-exit, %special-cases
338 // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
340 Builder
.SetInsertPoint(End
, End
->begin());
341 PHINode
*Q_5
= Builder
.CreatePHI(DivTy
, 2);
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
);
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
375 /// @brief Replace Rem with generated code.
376 bool 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");
381 IRBuilder
<> Builder(Rem
);
383 Type
*RemTy
= Rem
->getType();
384 if (RemTy
->isVectorTy())
385 llvm_unreachable("Div over vectors not supported");
387 unsigned RemTyBitWidth
= RemTy
->getIntegerBitWidth();
389 if (RemTyBitWidth
!= 32 && RemTyBitWidth
!= 64)
390 llvm_unreachable("Div of bitwidth other than 32 or 64 not supported");
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
);
397 Rem
->replaceAllUsesWith(Remainder
);
398 Rem
->dropAllReferences();
399 Rem
->eraseFromParent();
401 // If we didn't actually generate an urem instruction, we're done
402 // This happens for example if the input were constant. In this case the
403 // Builder insertion point was unchanged
404 if (Rem
== Builder
.GetInsertPoint())
407 BinaryOperator
*BO
= dyn_cast
<BinaryOperator
>(Builder
.GetInsertPoint());
411 Value
*Remainder
= generatedUnsignedRemainderCode(Rem
->getOperand(0),
415 Rem
->replaceAllUsesWith(Remainder
);
416 Rem
->dropAllReferences();
417 Rem
->eraseFromParent();
420 if (BinaryOperator
*UDiv
= dyn_cast
<BinaryOperator
>(Builder
.GetInsertPoint())) {
421 assert(UDiv
->getOpcode() == Instruction::UDiv
&& "Non-udiv in expansion?");
422 expandDivision(UDiv
);
429 /// Generate code to divide two integers, replacing Div with the generated
430 /// code. This currently generates code similarly to compiler-rt's
431 /// implementations, but future work includes generating more specialized code
432 /// when more information about the operands are known. Implements both
433 /// 32bit and 64bit scalar division.
435 /// @brief Replace Div with generated code.
436 bool llvm::expandDivision(BinaryOperator
*Div
) {
437 assert((Div
->getOpcode() == Instruction::SDiv
||
438 Div
->getOpcode() == Instruction::UDiv
) &&
439 "Trying to expand division from a non-division function");
441 IRBuilder
<> Builder(Div
);
443 Type
*DivTy
= Div
->getType();
444 if (DivTy
->isVectorTy())
445 llvm_unreachable("Div over vectors not supported");
447 unsigned DivTyBitWidth
= DivTy
->getIntegerBitWidth();
449 if (DivTyBitWidth
!= 32 && DivTyBitWidth
!= 64)
450 llvm_unreachable("Div of bitwidth other than 32 or 64 not supported");
452 // First prepare the sign if it's a signed division
453 if (Div
->getOpcode() == Instruction::SDiv
) {
454 // Lower the code to unsigned division, and reset Div to point to the udiv.
455 Value
*Quotient
= generateSignedDivisionCode(Div
->getOperand(0),
456 Div
->getOperand(1), Builder
);
457 Div
->replaceAllUsesWith(Quotient
);
458 Div
->dropAllReferences();
459 Div
->eraseFromParent();
461 // If we didn't actually generate an udiv instruction, we're done
462 // This happens for example if the input were constant. In this case the
463 // Builder insertion point was unchanged
464 if (Div
== Builder
.GetInsertPoint())
467 BinaryOperator
*BO
= dyn_cast
<BinaryOperator
>(Builder
.GetInsertPoint());
471 // Insert the unsigned division code
472 Value
*Quotient
= generateUnsignedDivisionCode(Div
->getOperand(0),
475 Div
->replaceAllUsesWith(Quotient
);
476 Div
->dropAllReferences();
477 Div
->eraseFromParent();
482 /// Generate code to compute the remainder of two integers of bitwidth up to
483 /// 32 bits. Uses the above routines and extends the inputs/truncates the
484 /// outputs to operate in 32 bits; that is, these routines are good for targets
485 /// that have no or very little suppport for smaller than 32 bit integer
488 /// @brief Replace Rem with emulation code.
489 bool llvm::expandRemainderUpTo32Bits(BinaryOperator
*Rem
) {
490 assert((Rem
->getOpcode() == Instruction::SRem
||
491 Rem
->getOpcode() == Instruction::URem
) &&
492 "Trying to expand remainder from a non-remainder function");
494 Type
*RemTy
= Rem
->getType();
495 if (RemTy
->isVectorTy())
496 llvm_unreachable("Div over vectors not supported");
498 unsigned RemTyBitWidth
= RemTy
->getIntegerBitWidth();
500 if (RemTyBitWidth
> 32)
501 llvm_unreachable("Div of bitwidth greater than 32 not supported");
503 if (RemTyBitWidth
== 32)
504 return expandRemainder(Rem
);
506 // If bitwidth smaller than 32 extend inputs, extend output and proceed
507 // with 32 bit division.
508 IRBuilder
<> Builder(Rem
);
514 Type
*Int32Ty
= Builder
.getInt32Ty();
516 if (Rem
->getOpcode() == Instruction::SRem
) {
517 ExtDividend
= Builder
.CreateSExt(Rem
->getOperand(0), Int32Ty
);
518 ExtDivisor
= Builder
.CreateSExt(Rem
->getOperand(1), Int32Ty
);
519 ExtRem
= Builder
.CreateSRem(ExtDividend
, ExtDivisor
);
521 ExtDividend
= Builder
.CreateZExt(Rem
->getOperand(0), Int32Ty
);
522 ExtDivisor
= Builder
.CreateZExt(Rem
->getOperand(1), Int32Ty
);
523 ExtRem
= Builder
.CreateURem(ExtDividend
, ExtDivisor
);
525 Trunc
= Builder
.CreateTrunc(ExtRem
, RemTy
);
527 Rem
->replaceAllUsesWith(Trunc
);
528 Rem
->dropAllReferences();
529 Rem
->eraseFromParent();
531 return expandRemainder(cast
<BinaryOperator
>(ExtRem
));
534 /// Generate code to compute the remainder of two integers of bitwidth up to
535 /// 64 bits. Uses the above routines and extends the inputs/truncates the
536 /// outputs to operate in 64 bits.
538 /// @brief Replace Rem with emulation code.
539 bool llvm::expandRemainderUpTo64Bits(BinaryOperator
*Rem
) {
540 assert((Rem
->getOpcode() == Instruction::SRem
||
541 Rem
->getOpcode() == Instruction::URem
) &&
542 "Trying to expand remainder from a non-remainder function");
544 Type
*RemTy
= Rem
->getType();
545 if (RemTy
->isVectorTy())
546 llvm_unreachable("Div over vectors not supported");
548 unsigned RemTyBitWidth
= RemTy
->getIntegerBitWidth();
550 if (RemTyBitWidth
> 64)
551 llvm_unreachable("Div of bitwidth greater than 64 not supported");
553 if (RemTyBitWidth
== 64)
554 return expandRemainder(Rem
);
556 // If bitwidth smaller than 64 extend inputs, extend output and proceed
557 // with 64 bit division.
558 IRBuilder
<> Builder(Rem
);
564 Type
*Int64Ty
= Builder
.getInt64Ty();
566 if (Rem
->getOpcode() == Instruction::SRem
) {
567 ExtDividend
= Builder
.CreateSExt(Rem
->getOperand(0), Int64Ty
);
568 ExtDivisor
= Builder
.CreateSExt(Rem
->getOperand(1), Int64Ty
);
569 ExtRem
= Builder
.CreateSRem(ExtDividend
, ExtDivisor
);
571 ExtDividend
= Builder
.CreateZExt(Rem
->getOperand(0), Int64Ty
);
572 ExtDivisor
= Builder
.CreateZExt(Rem
->getOperand(1), Int64Ty
);
573 ExtRem
= Builder
.CreateURem(ExtDividend
, ExtDivisor
);
575 Trunc
= Builder
.CreateTrunc(ExtRem
, RemTy
);
577 Rem
->replaceAllUsesWith(Trunc
);
578 Rem
->dropAllReferences();
579 Rem
->eraseFromParent();
581 return expandRemainder(cast
<BinaryOperator
>(ExtRem
));
584 /// Generate code to divide two integers of bitwidth up to 32 bits. Uses the
585 /// above routines and extends the inputs/truncates the outputs to operate
586 /// in 32 bits; that is, these routines are good for targets that have no
587 /// or very little support for smaller than 32 bit integer arithmetic.
589 /// @brief Replace Div with emulation code.
590 bool llvm::expandDivisionUpTo32Bits(BinaryOperator
*Div
) {
591 assert((Div
->getOpcode() == Instruction::SDiv
||
592 Div
->getOpcode() == Instruction::UDiv
) &&
593 "Trying to expand division from a non-division function");
595 Type
*DivTy
= Div
->getType();
596 if (DivTy
->isVectorTy())
597 llvm_unreachable("Div over vectors not supported");
599 unsigned DivTyBitWidth
= DivTy
->getIntegerBitWidth();
601 if (DivTyBitWidth
> 32)
602 llvm_unreachable("Div of bitwidth greater than 32 not supported");
604 if (DivTyBitWidth
== 32)
605 return expandDivision(Div
);
607 // If bitwidth smaller than 32 extend inputs, extend output and proceed
608 // with 32 bit division.
609 IRBuilder
<> Builder(Div
);
615 Type
*Int32Ty
= Builder
.getInt32Ty();
617 if (Div
->getOpcode() == Instruction::SDiv
) {
618 ExtDividend
= Builder
.CreateSExt(Div
->getOperand(0), Int32Ty
);
619 ExtDivisor
= Builder
.CreateSExt(Div
->getOperand(1), Int32Ty
);
620 ExtDiv
= Builder
.CreateSDiv(ExtDividend
, ExtDivisor
);
622 ExtDividend
= Builder
.CreateZExt(Div
->getOperand(0), Int32Ty
);
623 ExtDivisor
= Builder
.CreateZExt(Div
->getOperand(1), Int32Ty
);
624 ExtDiv
= Builder
.CreateUDiv(ExtDividend
, ExtDivisor
);
626 Trunc
= Builder
.CreateTrunc(ExtDiv
, DivTy
);
628 Div
->replaceAllUsesWith(Trunc
);
629 Div
->dropAllReferences();
630 Div
->eraseFromParent();
632 return expandDivision(cast
<BinaryOperator
>(ExtDiv
));
635 /// Generate code to divide two integers of bitwidth up to 64 bits. Uses the
636 /// above routines and extends the inputs/truncates the outputs to operate
639 /// @brief Replace Div with emulation code.
640 bool llvm::expandDivisionUpTo64Bits(BinaryOperator
*Div
) {
641 assert((Div
->getOpcode() == Instruction::SDiv
||
642 Div
->getOpcode() == Instruction::UDiv
) &&
643 "Trying to expand division from a non-division function");
645 Type
*DivTy
= Div
->getType();
646 if (DivTy
->isVectorTy())
647 llvm_unreachable("Div over vectors not supported");
649 unsigned DivTyBitWidth
= DivTy
->getIntegerBitWidth();
651 if (DivTyBitWidth
> 64)
652 llvm_unreachable("Div of bitwidth greater than 64 not supported");
654 if (DivTyBitWidth
== 64)
655 return expandDivision(Div
);
657 // If bitwidth smaller than 64 extend inputs, extend output and proceed
658 // with 64 bit division.
659 IRBuilder
<> Builder(Div
);
665 Type
*Int64Ty
= Builder
.getInt64Ty();
667 if (Div
->getOpcode() == Instruction::SDiv
) {
668 ExtDividend
= Builder
.CreateSExt(Div
->getOperand(0), Int64Ty
);
669 ExtDivisor
= Builder
.CreateSExt(Div
->getOperand(1), Int64Ty
);
670 ExtDiv
= Builder
.CreateSDiv(ExtDividend
, ExtDivisor
);
672 ExtDividend
= Builder
.CreateZExt(Div
->getOperand(0), Int64Ty
);
673 ExtDivisor
= Builder
.CreateZExt(Div
->getOperand(1), Int64Ty
);
674 ExtDiv
= Builder
.CreateUDiv(ExtDividend
, ExtDivisor
);
676 Trunc
= Builder
.CreateTrunc(ExtDiv
, DivTy
);
678 Div
->replaceAllUsesWith(Trunc
);
679 Div
->dropAllReferences();
680 Div
->eraseFromParent();
682 return expandDivision(cast
<BinaryOperator
>(ExtDiv
));