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
22using 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
32static Value *generateSignedRemainderCode(Value *Dividend, Value *Divisor,
33 IRBuilder<> &Builder) {
34 unsigned BitWidth = Dividend->getType()->getIntegerBitWidth();
35 ConstantInt *Shift = Builder.getIntN(N: BitWidth, C: 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(V: Dividend);
50 Divisor = Builder.CreateFreeze(V: Divisor);
51 Value *DividendSign = Builder.CreateAShr(LHS: Dividend, RHS: Shift);
52 Value *DivisorSign = Builder.CreateAShr(LHS: Divisor, RHS: Shift);
53 Value *DvdXor = Builder.CreateXor(LHS: Dividend, RHS: DividendSign);
54 Value *DvsXor = Builder.CreateXor(LHS: Divisor, RHS: DivisorSign);
55 Value *UDividend = Builder.CreateSub(LHS: DvdXor, RHS: DividendSign);
56 Value *UDivisor = Builder.CreateSub(LHS: DvsXor, RHS: DivisorSign);
57 Value *URem = Builder.CreateURem(LHS: UDividend, RHS: UDivisor);
58 Value *Xored = Builder.CreateXor(LHS: URem, RHS: DividendSign);
59 Value *SRem = Builder.CreateSub(LHS: Xored, RHS: DividendSign);
60
61 if (Instruction *URemInst = dyn_cast<Instruction>(Val: 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
73static 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(V: Dividend);
83 Divisor = Builder.CreateFreeze(V: Divisor);
84 Value *Quotient = Builder.CreateUDiv(LHS: Dividend, RHS: Divisor);
85 Value *Product = Builder.CreateMul(LHS: Divisor, RHS: Quotient);
86 Value *Remainder = Builder.CreateSub(LHS: Dividend, RHS: Product);
87
88 if (Instruction *UDiv = dyn_cast<Instruction>(Val: 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.
99static 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(N: BitWidth, C: 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(V: Dividend);
120 Divisor = Builder.CreateFreeze(V: Divisor);
121 Value *Tmp = Builder.CreateAShr(LHS: Dividend, RHS: Shift);
122 Value *Tmp1 = Builder.CreateAShr(LHS: Divisor, RHS: Shift);
123 Value *Tmp2 = Builder.CreateXor(LHS: Tmp, RHS: Dividend);
124 Value *U_Dvnd = Builder.CreateSub(LHS: Tmp2, RHS: Tmp);
125 Value *Tmp3 = Builder.CreateXor(LHS: Tmp1, RHS: Divisor);
126 Value *U_Dvsr = Builder.CreateSub(LHS: Tmp3, RHS: Tmp1);
127 Value *Q_Sgn = Builder.CreateXor(LHS: Tmp1, RHS: Tmp);
128 Value *Q_Mag = Builder.CreateUDiv(LHS: U_Dvnd, RHS: U_Dvsr);
129 Value *Tmp4 = Builder.CreateXor(LHS: Q_Mag, RHS: Q_Sgn);
130 Value *Q = Builder.CreateSub(LHS: Tmp4, RHS: Q_Sgn);
131
132 if (Instruction *UDiv = dyn_cast<Instruction>(Val: 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.
141static 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>(Val: Dividend->getType());
149 unsigned BitWidth = DivTy->getBitWidth();
150
151 ConstantInt *Zero = ConstantInt::get(Ty: DivTy, V: 0);
152 ConstantInt *One = ConstantInt::get(Ty: DivTy, V: 1);
153 ConstantInt *NegOne = ConstantInt::getSigned(Ty: DivTy, V: -1);
154 ConstantInt *MSB = ConstantInt::get(Ty: DivTy, V: BitWidth - 1);
155
156 ConstantInt *True = Builder.getTrue();
157
158 BasicBlock *IBB = Builder.GetInsertBlock();
159 Function *F = IBB->getParent();
160 Function *CTLZ = Intrinsic::getDeclaration(M: F->getParent(), id: Intrinsic::ctlz,
161 Tys: 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(I: Builder.GetInsertPoint(),
198 BBName: "udiv-end");
199 BasicBlock *LoopExit = BasicBlock::Create(Context&: Builder.getContext(),
200 Name: "udiv-loop-exit", Parent: F, InsertBefore: End);
201 BasicBlock *DoWhile = BasicBlock::Create(Context&: Builder.getContext(),
202 Name: "udiv-do-while", Parent: F, InsertBefore: End);
203 BasicBlock *Preheader = BasicBlock::Create(Context&: Builder.getContext(),
204 Name: "udiv-preheader", Parent: F, InsertBefore: End);
205 BasicBlock *BB1 = BasicBlock::Create(Context&: Builder.getContext(),
206 Name: "udiv-bb1", Parent: F, InsertBefore: 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(V: Divisor);
230 Dividend = Builder.CreateFreeze(V: Dividend);
231 Value *Ret0_1 = Builder.CreateICmpEQ(LHS: Divisor, RHS: Zero);
232 Value *Ret0_2 = Builder.CreateICmpEQ(LHS: Dividend, RHS: Zero);
233 Value *Ret0_3 = Builder.CreateOr(LHS: Ret0_1, RHS: Ret0_2);
234 Value *Tmp0 = Builder.CreateCall(Callee: CTLZ, Args: {Divisor, True});
235 Value *Tmp1 = Builder.CreateCall(Callee: CTLZ, Args: {Dividend, True});
236 Value *SR = Builder.CreateSub(LHS: Tmp0, RHS: Tmp1);
237 Value *Ret0_4 = Builder.CreateICmpUGT(LHS: SR, RHS: MSB);
238 Value *Ret0 = Builder.CreateLogicalOr(Cond1: Ret0_3, Cond2: Ret0_4);
239 Value *RetDividend = Builder.CreateICmpEQ(LHS: SR, RHS: MSB);
240 Value *RetVal = Builder.CreateSelect(C: Ret0, True: Zero, False: Dividend);
241 Value *EarlyRet = Builder.CreateLogicalOr(Cond1: Ret0, Cond2: RetDividend);
242 Builder.CreateCondBr(Cond: EarlyRet, True: End, False: 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(LHS: SR, RHS: One);
252 Value *Tmp2 = Builder.CreateSub(LHS: MSB, RHS: SR);
253 Value *Q = Builder.CreateShl(LHS: Dividend, RHS: Tmp2);
254 Value *SkipLoop = Builder.CreateICmpEQ(LHS: SR_1, RHS: Zero);
255 Builder.CreateCondBr(Cond: SkipLoop, True: LoopExit, False: 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(LHS: Dividend, RHS: SR_1);
263 Value *Tmp4 = Builder.CreateAdd(LHS: Divisor, RHS: NegOne);
264 Builder.CreateBr(Dest: 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(Ty: DivTy, NumReservedValues: 2);
286 PHINode *SR_3 = Builder.CreatePHI(Ty: DivTy, NumReservedValues: 2);
287 PHINode *R_1 = Builder.CreatePHI(Ty: DivTy, NumReservedValues: 2);
288 PHINode *Q_2 = Builder.CreatePHI(Ty: DivTy, NumReservedValues: 2);
289 Value *Tmp5 = Builder.CreateShl(LHS: R_1, RHS: One);
290 Value *Tmp6 = Builder.CreateLShr(LHS: Q_2, RHS: MSB);
291 Value *Tmp7 = Builder.CreateOr(LHS: Tmp5, RHS: Tmp6);
292 Value *Tmp8 = Builder.CreateShl(LHS: Q_2, RHS: One);
293 Value *Q_1 = Builder.CreateOr(LHS: Carry_1, RHS: Tmp8);
294 Value *Tmp9 = Builder.CreateSub(LHS: Tmp4, RHS: Tmp7);
295 Value *Tmp10 = Builder.CreateAShr(LHS: Tmp9, RHS: MSB);
296 Value *Carry = Builder.CreateAnd(LHS: Tmp10, RHS: One);
297 Value *Tmp11 = Builder.CreateAnd(LHS: Tmp10, RHS: Divisor);
298 Value *R = Builder.CreateSub(LHS: Tmp7, RHS: Tmp11);
299 Value *SR_2 = Builder.CreateAdd(LHS: SR_3, RHS: NegOne);
300 Value *Tmp12 = Builder.CreateICmpEQ(LHS: SR_2, RHS: Zero);
301 Builder.CreateCondBr(Cond: Tmp12, True: LoopExit, False: 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(Ty: DivTy, NumReservedValues: 2);
311 PHINode *Q_3 = Builder.CreatePHI(Ty: DivTy, NumReservedValues: 2);
312 Value *Tmp13 = Builder.CreateShl(LHS: Q_3, RHS: One);
313 Value *Q_4 = Builder.CreateOr(LHS: Carry_2, RHS: Tmp13);
314 Builder.CreateBr(Dest: 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(TheBB: End, IP: End->begin());
320 PHINode *Q_5 = Builder.CreatePHI(Ty: DivTy, NumReservedValues: 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(V: Zero, BB: Preheader);
325 Carry_1->addIncoming(V: Carry, BB: DoWhile);
326 // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
327 SR_3->addIncoming(V: SR_1, BB: Preheader);
328 SR_3->addIncoming(V: SR_2, BB: DoWhile);
329 // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
330 R_1->addIncoming(V: Tmp3, BB: Preheader);
331 R_1->addIncoming(V: R, BB: DoWhile);
332 // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
333 Q_2->addIncoming(V: Q, BB: Preheader);
334 Q_2->addIncoming(V: Q_1, BB: DoWhile);
335 // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
336 Carry_2->addIncoming(V: Zero, BB: BB1);
337 Carry_2->addIncoming(V: Carry, BB: DoWhile);
338 // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
339 Q_3->addIncoming(V: Q, BB: BB1);
340 Q_3->addIncoming(V: Q_1, BB: DoWhile);
341 // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
342 Q_5->addIncoming(V: Q_4, BB: LoopExit);
343 Q_5->addIncoming(V: RetVal, BB: 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.
354bool 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(Dividend: Rem->getOperand(i_nocapture: 0),
366 Divisor: Rem->getOperand(i_nocapture: 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(V: 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>(Val: Builder.GetInsertPoint());
381 Rem = BO;
382 }
383
384 Value *Remainder = generatedUnsignedRemainderCode(Dividend: Rem->getOperand(i_nocapture: 0),
385 Divisor: Rem->getOperand(i_nocapture: 1),
386 Builder);
387
388 Rem->replaceAllUsesWith(V: Remainder);
389 Rem->dropAllReferences();
390 Rem->eraseFromParent();
391
392 // Expand the udiv
393 if (BinaryOperator *UDiv = dyn_cast<BinaryOperator>(Val: Builder.GetInsertPoint())) {
394 assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?");
395 expandDivision(Div: 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.
407bool 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(Dividend: Div->getOperand(i_nocapture: 0),
420 Divisor: Div->getOperand(i_nocapture: 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(V: 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>(Val: Builder.GetInsertPoint());
435 Div = BO;
436 }
437
438 // Insert the unsigned division code
439 Value *Quotient = generateUnsignedDivisionCode(Dividend: Div->getOperand(i_nocapture: 0),
440 Divisor: Div->getOperand(i_nocapture: 1),
441 Builder);
442 Div->replaceAllUsesWith(V: 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.
456bool 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(V: Rem->getOperand(i_nocapture: 0), DestTy: Int32Ty);
484 ExtDivisor = Builder.CreateSExt(V: Rem->getOperand(i_nocapture: 1), DestTy: Int32Ty);
485 ExtRem = Builder.CreateSRem(LHS: ExtDividend, RHS: ExtDivisor);
486 } else {
487 ExtDividend = Builder.CreateZExt(V: Rem->getOperand(i_nocapture: 0), DestTy: Int32Ty);
488 ExtDivisor = Builder.CreateZExt(V: Rem->getOperand(i_nocapture: 1), DestTy: Int32Ty);
489 ExtRem = Builder.CreateURem(LHS: ExtDividend, RHS: ExtDivisor);
490 }
491 Trunc = Builder.CreateTrunc(V: ExtRem, DestTy: RemTy);
492
493 Rem->replaceAllUsesWith(V: Trunc);
494 Rem->dropAllReferences();
495 Rem->eraseFromParent();
496
497 return expandRemainder(Rem: cast<BinaryOperator>(Val: 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.
505bool 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(V: Rem->getOperand(i_nocapture: 0), DestTy: Int64Ty);
530 ExtDivisor = Builder.CreateSExt(V: Rem->getOperand(i_nocapture: 1), DestTy: Int64Ty);
531 ExtRem = Builder.CreateSRem(LHS: ExtDividend, RHS: ExtDivisor);
532 } else {
533 ExtDividend = Builder.CreateZExt(V: Rem->getOperand(i_nocapture: 0), DestTy: Int64Ty);
534 ExtDivisor = Builder.CreateZExt(V: Rem->getOperand(i_nocapture: 1), DestTy: Int64Ty);
535 ExtRem = Builder.CreateURem(LHS: ExtDividend, RHS: ExtDivisor);
536 }
537 Trunc = Builder.CreateTrunc(V: ExtRem, DestTy: RemTy);
538
539 Rem->replaceAllUsesWith(V: Trunc);
540 Rem->dropAllReferences();
541 Rem->eraseFromParent();
542
543 return expandRemainder(Rem: cast<BinaryOperator>(Val: 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.
552bool 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(V: Div->getOperand(i_nocapture: 0), DestTy: Int32Ty);
579 ExtDivisor = Builder.CreateSExt(V: Div->getOperand(i_nocapture: 1), DestTy: Int32Ty);
580 ExtDiv = Builder.CreateSDiv(LHS: ExtDividend, RHS: ExtDivisor);
581 } else {
582 ExtDividend = Builder.CreateZExt(V: Div->getOperand(i_nocapture: 0), DestTy: Int32Ty);
583 ExtDivisor = Builder.CreateZExt(V: Div->getOperand(i_nocapture: 1), DestTy: Int32Ty);
584 ExtDiv = Builder.CreateUDiv(LHS: ExtDividend, RHS: ExtDivisor);
585 }
586 Trunc = Builder.CreateTrunc(V: ExtDiv, DestTy: DivTy);
587
588 Div->replaceAllUsesWith(V: Trunc);
589 Div->dropAllReferences();
590 Div->eraseFromParent();
591
592 return expandDivision(Div: cast<BinaryOperator>(Val: 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.
600bool 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(V: Div->getOperand(i_nocapture: 0), DestTy: Int64Ty);
625 ExtDivisor = Builder.CreateSExt(V: Div->getOperand(i_nocapture: 1), DestTy: Int64Ty);
626 ExtDiv = Builder.CreateSDiv(LHS: ExtDividend, RHS: ExtDivisor);
627 } else {
628 ExtDividend = Builder.CreateZExt(V: Div->getOperand(i_nocapture: 0), DestTy: Int64Ty);
629 ExtDivisor = Builder.CreateZExt(V: Div->getOperand(i_nocapture: 1), DestTy: Int64Ty);
630 ExtDiv = Builder.CreateUDiv(LHS: ExtDividend, RHS: ExtDivisor);
631 }
632 Trunc = Builder.CreateTrunc(V: ExtDiv, DestTy: DivTy);
633
634 Div->replaceAllUsesWith(V: Trunc);
635 Div->dropAllReferences();
636 Div->eraseFromParent();
637
638 return expandDivision(Div: cast<BinaryOperator>(Val: ExtDiv));
639}
640