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 *generateUnsignedRemainderCode(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 =
161 Intrinsic::getOrInsertDeclaration(M: F->getParent(), id: Intrinsic::ctlz, 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 = generateUnsignedRemainderCode(Dividend: Rem->getOperand(i_nocapture: 0),
385 Divisor: Rem->getOperand(i_nocapture: 1), Builder);
386
387 Rem->replaceAllUsesWith(V: Remainder);
388 Rem->dropAllReferences();
389 Rem->eraseFromParent();
390
391 // Expand the udiv
392 if (BinaryOperator *UDiv = dyn_cast<BinaryOperator>(Val: Builder.GetInsertPoint())) {
393 assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?");
394 expandDivision(Div: UDiv);
395 }
396
397 return true;
398}
399
400/// Generate code to divide two integers, replacing Div with the generated
401/// code. This currently generates code similarly to compiler-rt's
402/// implementations, but future work includes generating more specialized code
403/// when more information about the operands are known.
404///
405/// Replace Div with generated code.
406bool llvm::expandDivision(BinaryOperator *Div) {
407 assert((Div->getOpcode() == Instruction::SDiv ||
408 Div->getOpcode() == Instruction::UDiv) &&
409 "Trying to expand division from a non-division function");
410
411 IRBuilder<> Builder(Div);
412
413 assert(!Div->getType()->isVectorTy() && "Div over vectors not supported");
414
415 // First prepare the sign if it's a signed division
416 if (Div->getOpcode() == Instruction::SDiv) {
417 // Lower the code to unsigned division, and reset Div to point to the udiv.
418 Value *Quotient = generateSignedDivisionCode(Dividend: Div->getOperand(i_nocapture: 0),
419 Divisor: Div->getOperand(i_nocapture: 1), Builder);
420
421 // Check whether this is the insert point while Div is still valid.
422 bool IsInsertPoint = Div->getIterator() == Builder.GetInsertPoint();
423 Div->replaceAllUsesWith(V: Quotient);
424 Div->dropAllReferences();
425 Div->eraseFromParent();
426
427 // If we didn't actually generate an udiv instruction, we're done
428 // This happens for example if the input were constant. In this case the
429 // Builder insertion point was unchanged
430 if (IsInsertPoint)
431 return true;
432
433 BinaryOperator *BO = dyn_cast<BinaryOperator>(Val: Builder.GetInsertPoint());
434 Div = BO;
435 }
436
437 // Insert the unsigned division code
438 Value *Quotient = generateUnsignedDivisionCode(Dividend: Div->getOperand(i_nocapture: 0),
439 Divisor: Div->getOperand(i_nocapture: 1),
440 Builder);
441 Div->replaceAllUsesWith(V: Quotient);
442 Div->dropAllReferences();
443 Div->eraseFromParent();
444
445 return true;
446}
447
448/// Generate code to compute the remainder of two integers of bitwidth up to
449/// 32 bits. Uses the above routines and extends the inputs/truncates the
450/// outputs to operate in 32 bits; that is, these routines are good for targets
451/// that have no or very little suppport for smaller than 32 bit integer
452/// arithmetic.
453///
454/// Replace Rem with emulation code.
455bool llvm::expandRemainderUpTo32Bits(BinaryOperator *Rem) {
456 assert((Rem->getOpcode() == Instruction::SRem ||
457 Rem->getOpcode() == Instruction::URem) &&
458 "Trying to expand remainder from a non-remainder function");
459
460 Type *RemTy = Rem->getType();
461 assert(!RemTy->isVectorTy() && "Div over vectors not supported");
462
463 unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
464
465 assert(RemTyBitWidth <= 32 &&
466 "Div of bitwidth greater than 32 not supported");
467
468 if (RemTyBitWidth == 32)
469 return expandRemainder(Rem);
470
471 // If bitwidth smaller than 32 extend inputs, extend output and proceed
472 // with 32 bit division.
473 IRBuilder<> Builder(Rem);
474
475 Value *ExtDividend;
476 Value *ExtDivisor;
477 Value *ExtRem;
478 Value *Trunc;
479 Type *Int32Ty = Builder.getInt32Ty();
480
481 if (Rem->getOpcode() == Instruction::SRem) {
482 ExtDividend = Builder.CreateSExt(V: Rem->getOperand(i_nocapture: 0), DestTy: Int32Ty);
483 ExtDivisor = Builder.CreateSExt(V: Rem->getOperand(i_nocapture: 1), DestTy: Int32Ty);
484 ExtRem = Builder.CreateSRem(LHS: ExtDividend, RHS: ExtDivisor);
485 } else {
486 ExtDividend = Builder.CreateZExt(V: Rem->getOperand(i_nocapture: 0), DestTy: Int32Ty);
487 ExtDivisor = Builder.CreateZExt(V: Rem->getOperand(i_nocapture: 1), DestTy: Int32Ty);
488 ExtRem = Builder.CreateURem(LHS: ExtDividend, RHS: ExtDivisor);
489 }
490 Trunc = Builder.CreateTrunc(V: ExtRem, DestTy: RemTy);
491
492 Rem->replaceAllUsesWith(V: Trunc);
493 Rem->dropAllReferences();
494 Rem->eraseFromParent();
495
496 return expandRemainder(Rem: cast<BinaryOperator>(Val: ExtRem));
497}
498
499/// Generate code to compute the remainder of two integers of bitwidth up to
500/// 64 bits. Uses the above routines and extends the inputs/truncates the
501/// outputs to operate in 64 bits.
502///
503/// Replace Rem with emulation code.
504bool llvm::expandRemainderUpTo64Bits(BinaryOperator *Rem) {
505 assert((Rem->getOpcode() == Instruction::SRem ||
506 Rem->getOpcode() == Instruction::URem) &&
507 "Trying to expand remainder from a non-remainder function");
508
509 Type *RemTy = Rem->getType();
510 assert(!RemTy->isVectorTy() && "Div over vectors not supported");
511
512 unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
513
514 if (RemTyBitWidth >= 64)
515 return expandRemainder(Rem);
516
517 // If bitwidth smaller than 64 extend inputs, extend output and proceed
518 // with 64 bit division.
519 IRBuilder<> Builder(Rem);
520
521 Value *ExtDividend;
522 Value *ExtDivisor;
523 Value *ExtRem;
524 Value *Trunc;
525 Type *Int64Ty = Builder.getInt64Ty();
526
527 if (Rem->getOpcode() == Instruction::SRem) {
528 ExtDividend = Builder.CreateSExt(V: Rem->getOperand(i_nocapture: 0), DestTy: Int64Ty);
529 ExtDivisor = Builder.CreateSExt(V: Rem->getOperand(i_nocapture: 1), DestTy: Int64Ty);
530 ExtRem = Builder.CreateSRem(LHS: ExtDividend, RHS: ExtDivisor);
531 } else {
532 ExtDividend = Builder.CreateZExt(V: Rem->getOperand(i_nocapture: 0), DestTy: Int64Ty);
533 ExtDivisor = Builder.CreateZExt(V: Rem->getOperand(i_nocapture: 1), DestTy: Int64Ty);
534 ExtRem = Builder.CreateURem(LHS: ExtDividend, RHS: ExtDivisor);
535 }
536 Trunc = Builder.CreateTrunc(V: ExtRem, DestTy: RemTy);
537
538 Rem->replaceAllUsesWith(V: Trunc);
539 Rem->dropAllReferences();
540 Rem->eraseFromParent();
541
542 return expandRemainder(Rem: cast<BinaryOperator>(Val: ExtRem));
543}
544
545/// Generate code to divide two integers of bitwidth up to 32 bits. Uses the
546/// above routines and extends the inputs/truncates the outputs to operate
547/// in 32 bits; that is, these routines are good for targets that have no
548/// or very little support for smaller than 32 bit integer arithmetic.
549///
550/// Replace Div with emulation code.
551bool llvm::expandDivisionUpTo32Bits(BinaryOperator *Div) {
552 assert((Div->getOpcode() == Instruction::SDiv ||
553 Div->getOpcode() == Instruction::UDiv) &&
554 "Trying to expand division from a non-division function");
555
556 Type *DivTy = Div->getType();
557 assert(!DivTy->isVectorTy() && "Div over vectors not supported");
558
559 unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
560
561 assert(DivTyBitWidth <= 32 && "Div of bitwidth greater than 32 not supported");
562
563 if (DivTyBitWidth == 32)
564 return expandDivision(Div);
565
566 // If bitwidth smaller than 32 extend inputs, extend output and proceed
567 // with 32 bit division.
568 IRBuilder<> Builder(Div);
569
570 Value *ExtDividend;
571 Value *ExtDivisor;
572 Value *ExtDiv;
573 Value *Trunc;
574 Type *Int32Ty = Builder.getInt32Ty();
575
576 if (Div->getOpcode() == Instruction::SDiv) {
577 ExtDividend = Builder.CreateSExt(V: Div->getOperand(i_nocapture: 0), DestTy: Int32Ty);
578 ExtDivisor = Builder.CreateSExt(V: Div->getOperand(i_nocapture: 1), DestTy: Int32Ty);
579 ExtDiv = Builder.CreateSDiv(LHS: ExtDividend, RHS: ExtDivisor);
580 } else {
581 ExtDividend = Builder.CreateZExt(V: Div->getOperand(i_nocapture: 0), DestTy: Int32Ty);
582 ExtDivisor = Builder.CreateZExt(V: Div->getOperand(i_nocapture: 1), DestTy: Int32Ty);
583 ExtDiv = Builder.CreateUDiv(LHS: ExtDividend, RHS: ExtDivisor);
584 }
585 Trunc = Builder.CreateTrunc(V: ExtDiv, DestTy: DivTy);
586
587 Div->replaceAllUsesWith(V: Trunc);
588 Div->dropAllReferences();
589 Div->eraseFromParent();
590
591 return expandDivision(Div: cast<BinaryOperator>(Val: ExtDiv));
592}
593
594/// Generate code to divide two integers of bitwidth up to 64 bits. Uses the
595/// above routines and extends the inputs/truncates the outputs to operate
596/// in 64 bits.
597///
598/// Replace Div with emulation code.
599bool llvm::expandDivisionUpTo64Bits(BinaryOperator *Div) {
600 assert((Div->getOpcode() == Instruction::SDiv ||
601 Div->getOpcode() == Instruction::UDiv) &&
602 "Trying to expand division from a non-division function");
603
604 Type *DivTy = Div->getType();
605 assert(!DivTy->isVectorTy() && "Div over vectors not supported");
606
607 unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
608
609 if (DivTyBitWidth >= 64)
610 return expandDivision(Div);
611
612 // If bitwidth smaller than 64 extend inputs, extend output and proceed
613 // with 64 bit division.
614 IRBuilder<> Builder(Div);
615
616 Value *ExtDividend;
617 Value *ExtDivisor;
618 Value *ExtDiv;
619 Value *Trunc;
620 Type *Int64Ty = Builder.getInt64Ty();
621
622 if (Div->getOpcode() == Instruction::SDiv) {
623 ExtDividend = Builder.CreateSExt(V: Div->getOperand(i_nocapture: 0), DestTy: Int64Ty);
624 ExtDivisor = Builder.CreateSExt(V: Div->getOperand(i_nocapture: 1), DestTy: Int64Ty);
625 ExtDiv = Builder.CreateSDiv(LHS: ExtDividend, RHS: ExtDivisor);
626 } else {
627 ExtDividend = Builder.CreateZExt(V: Div->getOperand(i_nocapture: 0), DestTy: Int64Ty);
628 ExtDivisor = Builder.CreateZExt(V: Div->getOperand(i_nocapture: 1), DestTy: Int64Ty);
629 ExtDiv = Builder.CreateUDiv(LHS: ExtDividend, RHS: ExtDivisor);
630 }
631 Trunc = Builder.CreateTrunc(V: ExtDiv, DestTy: DivTy);
632
633 Div->replaceAllUsesWith(V: Trunc);
634 Div->dropAllReferences();
635 Div->eraseFromParent();
636
637 return expandDivision(Div: cast<BinaryOperator>(Val: ExtDiv));
638}
639