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/Instruction.h"
20#include "llvm/IR/Instructions.h"
21#include "llvm/IR/Intrinsics.h"
22#include "llvm/IR/LLVMContext.h"
23#include "llvm/IR/MDBuilder.h"
24#include "llvm/IR/ProfDataUtils.h"
25#include "llvm/IR/Value.h"
26#include "llvm/Support/Casting.h"
27
28using namespace llvm;
29
30#define DEBUG_TYPE "integer-division"
31
32/// Generate code to compute the remainder of two signed integers. Returns the
33/// remainder, which will have the sign of the dividend. Builder's insert point
34/// should be pointing where the caller wants code generated, e.g. at the srem
35/// instruction. This will generate a urem in the process, and Builder's insert
36/// point will be pointing at the uren (if present, i.e. not folded), ready to
37/// be expanded if the user wishes
38static Value *generateSignedRemainderCode(Value *Dividend, Value *Divisor,
39 IRBuilder<> &Builder) {
40 unsigned BitWidth = Dividend->getType()->getIntegerBitWidth();
41 ConstantInt *Shift = Builder.getIntN(N: BitWidth, C: BitWidth - 1);
42
43 // Following instructions are generated for both i32 (shift 31) and
44 // i64 (shift 63).
45
46 // ; %dividend_sgn = ashr i32 %dividend, 31
47 // ; %divisor_sgn = ashr i32 %divisor, 31
48 // ; %dvd_xor = xor i32 %dividend, %dividend_sgn
49 // ; %dvs_xor = xor i32 %divisor, %divisor_sgn
50 // ; %u_dividend = sub i32 %dvd_xor, %dividend_sgn
51 // ; %u_divisor = sub i32 %dvs_xor, %divisor_sgn
52 // ; %urem = urem i32 %dividend, %divisor
53 // ; %xored = xor i32 %urem, %dividend_sgn
54 // ; %srem = sub i32 %xored, %dividend_sgn
55 Dividend = Builder.CreateFreeze(V: Dividend);
56 Divisor = Builder.CreateFreeze(V: Divisor);
57 Value *DividendSign = Builder.CreateAShr(LHS: Dividend, RHS: Shift);
58 Value *DivisorSign = Builder.CreateAShr(LHS: Divisor, RHS: Shift);
59 Value *DvdXor = Builder.CreateXor(LHS: Dividend, RHS: DividendSign);
60 Value *DvsXor = Builder.CreateXor(LHS: Divisor, RHS: DivisorSign);
61 Value *UDividend = Builder.CreateSub(LHS: DvdXor, RHS: DividendSign);
62 Value *UDivisor = Builder.CreateSub(LHS: DvsXor, RHS: DivisorSign);
63 Value *URem = Builder.CreateURem(LHS: UDividend, RHS: UDivisor);
64 Value *Xored = Builder.CreateXor(LHS: URem, RHS: DividendSign);
65 Value *SRem = Builder.CreateSub(LHS: Xored, RHS: DividendSign);
66
67 if (Instruction *URemInst = dyn_cast<Instruction>(Val: URem))
68 Builder.SetInsertPoint(URemInst);
69
70 return SRem;
71}
72
73
74/// Generate code to compute the remainder of two unsigned integers. Returns the
75/// remainder. Builder's insert point should be pointing where the caller wants
76/// code generated, e.g. at the urem instruction. This will generate a udiv in
77/// the process, and Builder's insert point will be pointing at the udiv (if
78/// present, i.e. not folded), ready to be expanded if the user wishes
79static Value *generateUnsignedRemainderCode(Value *Dividend, Value *Divisor,
80 IRBuilder<> &Builder) {
81 // Remainder = Dividend - Quotient*Divisor
82
83 // Following instructions are generated for both i32 and i64
84
85 // ; %quotient = udiv i32 %dividend, %divisor
86 // ; %product = mul i32 %divisor, %quotient
87 // ; %remainder = sub i32 %dividend, %product
88 Dividend = Builder.CreateFreeze(V: Dividend);
89 Divisor = Builder.CreateFreeze(V: Divisor);
90 Value *Quotient = Builder.CreateUDiv(LHS: Dividend, RHS: Divisor);
91 Value *Product = Builder.CreateMul(LHS: Divisor, RHS: Quotient);
92 Value *Remainder = Builder.CreateSub(LHS: Dividend, RHS: Product);
93
94 if (Instruction *UDiv = dyn_cast<Instruction>(Val: Quotient))
95 Builder.SetInsertPoint(UDiv);
96
97 return Remainder;
98}
99
100/// Generate code to divide two signed integers. Returns the quotient, rounded
101/// towards 0. Builder's insert point should be pointing where the caller wants
102/// code generated, e.g. at the sdiv instruction. This will generate a udiv in
103/// the process, and Builder's insert point will be pointing at the udiv (if
104/// present, i.e. not folded), ready to be expanded if the user wishes.
105static Value *generateSignedDivisionCode(Value *Dividend, Value *Divisor,
106 IRBuilder<> &Builder) {
107 // Implementation taken from compiler-rt's __divsi3 and __divdi3
108
109 unsigned BitWidth = Dividend->getType()->getIntegerBitWidth();
110 ConstantInt *Shift = Builder.getIntN(N: BitWidth, C: BitWidth - 1);
111
112 // Following instructions are generated for both i32 (shift 31) and
113 // i64 (shift 63).
114
115 // ; %tmp = ashr i32 %dividend, 31
116 // ; %tmp1 = ashr i32 %divisor, 31
117 // ; %tmp2 = xor i32 %tmp, %dividend
118 // ; %u_dvnd = sub nsw i32 %tmp2, %tmp
119 // ; %tmp3 = xor i32 %tmp1, %divisor
120 // ; %u_dvsr = sub nsw i32 %tmp3, %tmp1
121 // ; %q_sgn = xor i32 %tmp1, %tmp
122 // ; %q_mag = udiv i32 %u_dvnd, %u_dvsr
123 // ; %tmp4 = xor i32 %q_mag, %q_sgn
124 // ; %q = sub i32 %tmp4, %q_sgn
125 Dividend = Builder.CreateFreeze(V: Dividend);
126 Divisor = Builder.CreateFreeze(V: Divisor);
127 Value *Tmp = Builder.CreateAShr(LHS: Dividend, RHS: Shift);
128 Value *Tmp1 = Builder.CreateAShr(LHS: Divisor, RHS: Shift);
129 Value *Tmp2 = Builder.CreateXor(LHS: Tmp, RHS: Dividend);
130 Value *U_Dvnd = Builder.CreateSub(LHS: Tmp2, RHS: Tmp);
131 Value *Tmp3 = Builder.CreateXor(LHS: Tmp1, RHS: Divisor);
132 Value *U_Dvsr = Builder.CreateSub(LHS: Tmp3, RHS: Tmp1);
133 Value *Q_Sgn = Builder.CreateXor(LHS: Tmp1, RHS: Tmp);
134 Value *Q_Mag = Builder.CreateUDiv(LHS: U_Dvnd, RHS: U_Dvsr);
135 Value *Tmp4 = Builder.CreateXor(LHS: Q_Mag, RHS: Q_Sgn);
136 Value *Q = Builder.CreateSub(LHS: Tmp4, RHS: Q_Sgn);
137
138 if (Instruction *UDiv = dyn_cast<Instruction>(Val: Q_Mag))
139 Builder.SetInsertPoint(UDiv);
140
141 return Q;
142}
143
144/// Generates code to divide two unsigned scalar 32-bit or 64-bit integers.
145/// Returns the quotient, rounded towards 0. Builder's insert point should
146/// point where the caller wants code generated, e.g. at the udiv instruction.
147static Value *generateUnsignedDivisionCode(Value *Dividend, Value *Divisor,
148 IRBuilder<> &Builder) {
149 // The basic algorithm can be found in the compiler-rt project's
150 // implementation of __udivsi3.c. Here, we do a lower-level IR based approach
151 // that's been hand-tuned to lessen the amount of control flow involved.
152
153 // Some helper values
154 IntegerType *DivTy = cast<IntegerType>(Val: Dividend->getType());
155 unsigned BitWidth = DivTy->getBitWidth();
156
157 ConstantInt *Zero = ConstantInt::get(Ty: DivTy, V: 0);
158 ConstantInt *One = ConstantInt::get(Ty: DivTy, V: 1);
159 ConstantInt *NegOne = ConstantInt::getSigned(Ty: DivTy, V: -1);
160 ConstantInt *MSB = ConstantInt::get(Ty: DivTy, V: BitWidth - 1);
161
162 ConstantInt *True = Builder.getTrue();
163
164 BasicBlock *IBB = Builder.GetInsertBlock();
165 Function *F = IBB->getParent();
166 Function *CTLZ =
167 Intrinsic::getOrInsertDeclaration(M: F->getParent(), id: Intrinsic::ctlz, OverloadTys: DivTy);
168
169 // Our CFG is going to look like:
170 // +---------------------+
171 // | special-cases |
172 // | ... |
173 // +---------------------+
174 // | |
175 // | +----------+
176 // | | bb1 |
177 // | | ... |
178 // | +----------+
179 // | | |
180 // | | +------------+
181 // | | | preheader |
182 // | | | ... |
183 // | | +------------+
184 // | | |
185 // | | | +---+
186 // | | | | |
187 // | | +------------+ |
188 // | | | do-while | |
189 // | | | ... | |
190 // | | +------------+ |
191 // | | | | |
192 // | +-----------+ +---+
193 // | | loop-exit |
194 // | | ... |
195 // | +-----------+
196 // | |
197 // +-------+
198 // | ... |
199 // | end |
200 // +-------+
201 BasicBlock *SpecialCases = Builder.GetInsertBlock();
202 SpecialCases->setName(Twine(SpecialCases->getName(), "_udiv-special-cases"));
203 BasicBlock *End = SpecialCases->splitBasicBlock(I: Builder.GetInsertPoint(),
204 BBName: "udiv-end");
205 BasicBlock *LoopExit = BasicBlock::Create(Context&: Builder.getContext(),
206 Name: "udiv-loop-exit", Parent: F, InsertBefore: End);
207 BasicBlock *DoWhile = BasicBlock::Create(Context&: Builder.getContext(),
208 Name: "udiv-do-while", Parent: F, InsertBefore: End);
209 BasicBlock *Preheader = BasicBlock::Create(Context&: Builder.getContext(),
210 Name: "udiv-preheader", Parent: F, InsertBefore: End);
211 BasicBlock *BB1 = BasicBlock::Create(Context&: Builder.getContext(),
212 Name: "udiv-bb1", Parent: F, InsertBefore: End);
213
214 // We'll be overwriting the terminator to insert our extra blocks
215 SpecialCases->getTerminator()->eraseFromParent();
216
217 // Same instructions are generated for both i32 (msb 31) and i64 (msb 63).
218
219 // First off, check for special cases: dividend or divisor is zero, divisor
220 // is greater than dividend, and divisor is 1.
221 // ; special-cases:
222 // ; %ret0_1 = icmp eq i32 %divisor, 0
223 // ; %ret0_2 = icmp eq i32 %dividend, 0
224 // ; %ret0_3 = or i1 %ret0_1, %ret0_2
225 // ; %tmp0 = tail call i32 @llvm.ctlz.i32(i32 %divisor, i1 true)
226 // ; %tmp1 = tail call i32 @llvm.ctlz.i32(i32 %dividend, i1 true)
227 // ; %sr = sub nsw i32 %tmp0, %tmp1
228 // ; %ret0_4 = icmp ugt i32 %sr, 31
229 // ; %ret0 = select i1 %ret0_3, i1 true, i1 %ret0_4
230 // ; %retDividend = icmp eq i32 %sr, 31
231 // ; %retVal = select i1 %ret0, i32 0, i32 %dividend
232 // ; %earlyRet = select i1 %ret0, i1 true, %retDividend
233 // ; br i1 %earlyRet, label %end, label %bb1
234 Builder.SetInsertPoint(SpecialCases);
235 Divisor = Builder.CreateFreeze(V: Divisor);
236 Dividend = Builder.CreateFreeze(V: Dividend);
237 Value *Ret0_1 = Builder.CreateICmpEQ(LHS: Divisor, RHS: Zero);
238 Value *Ret0_2 = Builder.CreateICmpEQ(LHS: Dividend, RHS: Zero);
239 Value *Ret0_3 = Builder.CreateOr(LHS: Ret0_1, RHS: Ret0_2);
240 Value *Tmp0 = Builder.CreateCall(Callee: CTLZ, Args: {Divisor, True});
241 Value *Tmp1 = Builder.CreateCall(Callee: CTLZ, Args: {Dividend, True});
242 Value *SR = Builder.CreateSub(LHS: Tmp0, RHS: Tmp1);
243 Value *Ret0_4 = Builder.CreateICmpUGT(LHS: SR, RHS: MSB);
244
245 // Add 'unlikely' branch weights. We mark the case where either the divisor
246 // or the dividend is equal to zero as unlikely.
247 Value *Ret0 = Builder.CreateLogicalOr(Cond1: Ret0_3, Cond2: Ret0_4);
248 if (auto *Inst = dyn_cast<Instruction>(Val: Ret0))
249 Inst->setMetadata(
250 KindID: LLVMContext::MD_prof,
251 Node: MDBuilder(Inst->getContext()).createUnlikelyBranchWeights());
252 Value *RetDividend = Builder.CreateICmpEQ(LHS: SR, RHS: MSB);
253
254 // Conservatively, we treat the case |divisor| > |dividend| as unknown
255 Value *RetVal = Builder.CreateSelect(C: Ret0, True: Zero, False: Dividend);
256 if (auto *Inst = dyn_cast<Instruction>(Val: RetVal))
257 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *Inst, DEBUG_TYPE, F);
258 Value *EarlyRet = Builder.CreateLogicalOr(Cond1: Ret0, Cond2: RetDividend);
259 if (auto *Inst = dyn_cast<Instruction>(Val: EarlyRet))
260 setExplicitlyUnknownBranchWeightsIfProfiled(I&: *Inst, DEBUG_TYPE, F);
261
262 // The condition of this branch is based on `EarlyRet`. `EarlyRet` is true
263 // only for special cases like dividend or divisor being zero, or the divisor
264 // being greater than the dividend. Thus, the branch to `End` is unlikely,
265 // and we expect to more frequently enter `BB1`.
266 Value *ConBrSpecialCases = Builder.CreateCondBr(Cond: EarlyRet, True: End, False: BB1);
267 if (auto *Inst = dyn_cast<Instruction>(Val: ConBrSpecialCases))
268 Inst->setMetadata(
269 KindID: LLVMContext::MD_prof,
270 Node: MDBuilder(Inst->getContext()).createUnlikelyBranchWeights());
271
272 // ; bb1: ; preds = %special-cases
273 // ; %sr_1 = add i32 %sr, 1
274 // ; %tmp2 = sub i32 31, %sr
275 // ; %q = shl i32 %dividend, %tmp2
276 // ; %skipLoop = icmp eq i32 %sr_1, 0
277 // ; br i1 %skipLoop, label %loop-exit, label %preheader
278 Builder.SetInsertPoint(BB1);
279 Value *SR_1 = Builder.CreateAdd(LHS: SR, RHS: One);
280 Value *Tmp2 = Builder.CreateSub(LHS: MSB, RHS: SR);
281 Value *Q = Builder.CreateShl(LHS: Dividend, RHS: Tmp2);
282 // We assume that in the common case, the dividend's magnitude is larger than
283 // the divisor's magnitude such that the loop counter (SR) is non-zero.
284 // Specifically, if |dividend| >= 2 * |divisor|, then SR >= 1, ensuring SR_1
285 // >= 2. The case where SR_1 == 0 is thus considered unlikely.
286 Value *SkipLoop = Builder.CreateICmpEQ(LHS: SR_1, RHS: Zero);
287 Value *ConBrBB1 = Builder.CreateCondBr(Cond: SkipLoop, True: LoopExit, False: Preheader);
288 if (auto *Inst = dyn_cast<Instruction>(Val: ConBrBB1))
289 Inst->setMetadata(
290 KindID: LLVMContext::MD_prof,
291 Node: MDBuilder(Inst->getContext()).createUnlikelyBranchWeights());
292
293 // ; preheader: ; preds = %bb1
294 // ; %tmp3 = lshr i32 %dividend, %sr_1
295 // ; %tmp4 = add i32 %divisor, -1
296 // ; br label %do-while
297 Builder.SetInsertPoint(Preheader);
298 Value *Tmp3 = Builder.CreateLShr(LHS: Dividend, RHS: SR_1);
299 Value *Tmp4 = Builder.CreateAdd(LHS: Divisor, RHS: NegOne);
300 Builder.CreateBr(Dest: DoWhile);
301
302 // ; do-while: ; preds = %do-while, %preheader
303 // ; %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]
304 // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
305 // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
306 // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
307 // ; %tmp5 = shl i32 %r_1, 1
308 // ; %tmp6 = lshr i32 %q_2, 31
309 // ; %tmp7 = or i32 %tmp5, %tmp6
310 // ; %tmp8 = shl i32 %q_2, 1
311 // ; %q_1 = or i32 %carry_1, %tmp8
312 // ; %tmp9 = sub i32 %tmp4, %tmp7
313 // ; %tmp10 = ashr i32 %tmp9, 31
314 // ; %carry = and i32 %tmp10, 1
315 // ; %tmp11 = and i32 %tmp10, %divisor
316 // ; %r = sub i32 %tmp7, %tmp11
317 // ; %sr_2 = add i32 %sr_3, -1
318 // ; %tmp12 = icmp eq i32 %sr_2, 0
319 // ; br i1 %tmp12, label %loop-exit, label %do-while
320 Builder.SetInsertPoint(DoWhile);
321 PHINode *Carry_1 = Builder.CreatePHI(Ty: DivTy, NumReservedValues: 2);
322 PHINode *SR_3 = Builder.CreatePHI(Ty: DivTy, NumReservedValues: 2);
323 PHINode *R_1 = Builder.CreatePHI(Ty: DivTy, NumReservedValues: 2);
324 PHINode *Q_2 = Builder.CreatePHI(Ty: DivTy, NumReservedValues: 2);
325 Value *Tmp5 = Builder.CreateShl(LHS: R_1, RHS: One);
326 Value *Tmp6 = Builder.CreateLShr(LHS: Q_2, RHS: MSB);
327 Value *Tmp7 = Builder.CreateOr(LHS: Tmp5, RHS: Tmp6);
328 Value *Tmp8 = Builder.CreateShl(LHS: Q_2, RHS: One);
329 Value *Q_1 = Builder.CreateOr(LHS: Carry_1, RHS: Tmp8);
330 Value *Tmp9 = Builder.CreateSub(LHS: Tmp4, RHS: Tmp7);
331 Value *Tmp10 = Builder.CreateAShr(LHS: Tmp9, RHS: MSB);
332 Value *Carry = Builder.CreateAnd(LHS: Tmp10, RHS: One);
333 Value *Tmp11 = Builder.CreateAnd(LHS: Tmp10, RHS: Divisor);
334 Value *R = Builder.CreateSub(LHS: Tmp7, RHS: Tmp11);
335 Value *SR_2 = Builder.CreateAdd(LHS: SR_3, RHS: NegOne);
336 Value *Tmp12 = Builder.CreateICmpEQ(LHS: SR_2, RHS: Zero);
337 // The loop implements the core bit-by-bit binary long division algorithm.
338 // The branch is unlikely to exit the loop early until it has processed all
339 // significant bits.
340 Value *ConBrDoWhile = Builder.CreateCondBr(Cond: Tmp12, True: LoopExit, False: DoWhile);
341 if (auto *Inst = dyn_cast<Instruction>(Val: ConBrDoWhile))
342 Inst->setMetadata(
343 KindID: LLVMContext::MD_prof,
344 Node: MDBuilder(Inst->getContext()).createUnlikelyBranchWeights());
345
346 // ; loop-exit: ; preds = %do-while, %bb1
347 // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
348 // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
349 // ; %tmp13 = shl i32 %q_3, 1
350 // ; %q_4 = or i32 %carry_2, %tmp13
351 // ; br label %end
352 Builder.SetInsertPoint(LoopExit);
353 PHINode *Carry_2 = Builder.CreatePHI(Ty: DivTy, NumReservedValues: 2);
354 PHINode *Q_3 = Builder.CreatePHI(Ty: DivTy, NumReservedValues: 2);
355 Value *Tmp13 = Builder.CreateShl(LHS: Q_3, RHS: One);
356 Value *Q_4 = Builder.CreateOr(LHS: Carry_2, RHS: Tmp13);
357 Builder.CreateBr(Dest: End);
358
359 // ; end: ; preds = %loop-exit, %special-cases
360 // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
361 // ; ret i32 %q_5
362 Builder.SetInsertPoint(TheBB: End, IP: End->begin());
363 PHINode *Q_5 = Builder.CreatePHI(Ty: DivTy, NumReservedValues: 2);
364
365 // Populate the Phis, since all values have now been created. Our Phis were:
366 // ; %carry_1 = phi i32 [ 0, %preheader ], [ %carry, %do-while ]
367 Carry_1->addIncoming(V: Zero, BB: Preheader);
368 Carry_1->addIncoming(V: Carry, BB: DoWhile);
369 // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
370 SR_3->addIncoming(V: SR_1, BB: Preheader);
371 SR_3->addIncoming(V: SR_2, BB: DoWhile);
372 // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
373 R_1->addIncoming(V: Tmp3, BB: Preheader);
374 R_1->addIncoming(V: R, BB: DoWhile);
375 // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
376 Q_2->addIncoming(V: Q, BB: Preheader);
377 Q_2->addIncoming(V: Q_1, BB: DoWhile);
378 // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
379 Carry_2->addIncoming(V: Zero, BB: BB1);
380 Carry_2->addIncoming(V: Carry, BB: DoWhile);
381 // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
382 Q_3->addIncoming(V: Q, BB: BB1);
383 Q_3->addIncoming(V: Q_1, BB: DoWhile);
384 // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
385 Q_5->addIncoming(V: Q_4, BB: LoopExit);
386 Q_5->addIncoming(V: RetVal, BB: SpecialCases);
387
388 return Q_5;
389}
390
391/// Generate code to calculate the remainder of two integers, replacing Rem with
392/// the generated code. This currently generates code using the udiv expansion,
393/// but future work includes generating more specialized code, e.g. when more
394/// information about the operands are known.
395///
396/// Replace Rem with generated code.
397bool llvm::expandRemainder(BinaryOperator *Rem) {
398 assert((Rem->getOpcode() == Instruction::SRem ||
399 Rem->getOpcode() == Instruction::URem) &&
400 "Trying to expand remainder from a non-remainder function");
401
402 IRBuilder<> Builder(Rem);
403
404 assert(!Rem->getType()->isVectorTy() && "Div over vectors not supported");
405
406 // First prepare the sign if it's a signed remainder
407 if (Rem->getOpcode() == Instruction::SRem) {
408 Value *Remainder = generateSignedRemainderCode(Dividend: Rem->getOperand(i_nocapture: 0),
409 Divisor: Rem->getOperand(i_nocapture: 1), Builder);
410
411 // Check whether this is the insert point while Rem is still valid.
412 bool IsInsertPoint = Rem->getIterator() == Builder.GetInsertPoint();
413 Rem->replaceAllUsesWith(V: Remainder);
414 Rem->dropAllReferences();
415 Rem->eraseFromParent();
416
417 // If we didn't actually generate an urem instruction, we're done
418 // This happens for example if the input were constant. In this case the
419 // Builder insertion point was unchanged
420 if (IsInsertPoint)
421 return true;
422
423 BinaryOperator *BO = dyn_cast<BinaryOperator>(Val: Builder.GetInsertPoint());
424 Rem = BO;
425 }
426
427 Value *Remainder = generateUnsignedRemainderCode(Dividend: Rem->getOperand(i_nocapture: 0),
428 Divisor: Rem->getOperand(i_nocapture: 1), Builder);
429
430 Rem->replaceAllUsesWith(V: Remainder);
431 Rem->dropAllReferences();
432 Rem->eraseFromParent();
433
434 // Expand the udiv
435 if (BinaryOperator *UDiv = dyn_cast<BinaryOperator>(Val: Builder.GetInsertPoint())) {
436 assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?");
437 expandDivision(Div: UDiv);
438 }
439
440 return true;
441}
442
443/// Generate code to divide two integers, replacing Div with the generated
444/// code. This currently generates code similarly to compiler-rt's
445/// implementations, but future work includes generating more specialized code
446/// when more information about the operands are known.
447///
448/// Replace Div with generated code.
449bool llvm::expandDivision(BinaryOperator *Div) {
450 assert((Div->getOpcode() == Instruction::SDiv ||
451 Div->getOpcode() == Instruction::UDiv) &&
452 "Trying to expand division from a non-division function");
453
454 IRBuilder<> Builder(Div);
455
456 assert(!Div->getType()->isVectorTy() && "Div over vectors not supported");
457
458 // First prepare the sign if it's a signed division
459 if (Div->getOpcode() == Instruction::SDiv) {
460 // Lower the code to unsigned division, and reset Div to point to the udiv.
461 Value *Quotient = generateSignedDivisionCode(Dividend: Div->getOperand(i_nocapture: 0),
462 Divisor: Div->getOperand(i_nocapture: 1), Builder);
463
464 // Check whether this is the insert point while Div is still valid.
465 bool IsInsertPoint = Div->getIterator() == Builder.GetInsertPoint();
466 Div->replaceAllUsesWith(V: Quotient);
467 Div->dropAllReferences();
468 Div->eraseFromParent();
469
470 // If we didn't actually generate an udiv instruction, we're done
471 // This happens for example if the input were constant. In this case the
472 // Builder insertion point was unchanged
473 if (IsInsertPoint)
474 return true;
475
476 BinaryOperator *BO = dyn_cast<BinaryOperator>(Val: Builder.GetInsertPoint());
477 Div = BO;
478 }
479
480 // Insert the unsigned division code
481 Value *Quotient = generateUnsignedDivisionCode(Dividend: Div->getOperand(i_nocapture: 0),
482 Divisor: Div->getOperand(i_nocapture: 1),
483 Builder);
484 Div->replaceAllUsesWith(V: Quotient);
485 Div->dropAllReferences();
486 Div->eraseFromParent();
487
488 return true;
489}
490
491/// Generate code to compute the remainder of two integers of bitwidth up to
492/// 32 bits. Uses the above routines and extends the inputs/truncates the
493/// outputs to operate in 32 bits; that is, these routines are good for targets
494/// that have no or very little suppport for smaller than 32 bit integer
495/// arithmetic.
496///
497/// Replace Rem with emulation code.
498bool llvm::expandRemainderUpTo32Bits(BinaryOperator *Rem) {
499 assert((Rem->getOpcode() == Instruction::SRem ||
500 Rem->getOpcode() == Instruction::URem) &&
501 "Trying to expand remainder from a non-remainder function");
502
503 Type *RemTy = Rem->getType();
504 assert(!RemTy->isVectorTy() && "Div over vectors not supported");
505
506 unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
507
508 assert(RemTyBitWidth <= 32 &&
509 "Div of bitwidth greater than 32 not supported");
510
511 if (RemTyBitWidth == 32)
512 return expandRemainder(Rem);
513
514 // If bitwidth smaller than 32 extend inputs, extend output and proceed
515 // with 32 bit division.
516 IRBuilder<> Builder(Rem);
517
518 Value *ExtDividend;
519 Value *ExtDivisor;
520 Value *ExtRem;
521 Value *Trunc;
522 Type *Int32Ty = Builder.getInt32Ty();
523
524 if (Rem->getOpcode() == Instruction::SRem) {
525 ExtDividend = Builder.CreateSExt(V: Rem->getOperand(i_nocapture: 0), DestTy: Int32Ty);
526 ExtDivisor = Builder.CreateSExt(V: Rem->getOperand(i_nocapture: 1), DestTy: Int32Ty);
527 ExtRem = Builder.CreateSRem(LHS: ExtDividend, RHS: ExtDivisor);
528 } else {
529 ExtDividend = Builder.CreateZExt(V: Rem->getOperand(i_nocapture: 0), DestTy: Int32Ty);
530 ExtDivisor = Builder.CreateZExt(V: Rem->getOperand(i_nocapture: 1), DestTy: Int32Ty);
531 ExtRem = Builder.CreateURem(LHS: ExtDividend, RHS: ExtDivisor);
532 }
533 Trunc = Builder.CreateTrunc(V: ExtRem, DestTy: RemTy);
534
535 Rem->replaceAllUsesWith(V: Trunc);
536 Rem->dropAllReferences();
537 Rem->eraseFromParent();
538
539 return expandRemainder(Rem: cast<BinaryOperator>(Val: ExtRem));
540}
541
542/// Generate code to compute the remainder of two integers of bitwidth up to
543/// 64 bits. Uses the above routines and extends the inputs/truncates the
544/// outputs to operate in 64 bits.
545///
546/// Replace Rem with emulation code.
547bool llvm::expandRemainderUpTo64Bits(BinaryOperator *Rem) {
548 assert((Rem->getOpcode() == Instruction::SRem ||
549 Rem->getOpcode() == Instruction::URem) &&
550 "Trying to expand remainder from a non-remainder function");
551
552 Type *RemTy = Rem->getType();
553 assert(!RemTy->isVectorTy() && "Div over vectors not supported");
554
555 unsigned RemTyBitWidth = RemTy->getIntegerBitWidth();
556
557 if (RemTyBitWidth >= 64)
558 return expandRemainder(Rem);
559
560 // If bitwidth smaller than 64 extend inputs, extend output and proceed
561 // with 64 bit division.
562 IRBuilder<> Builder(Rem);
563
564 Value *ExtDividend;
565 Value *ExtDivisor;
566 Value *ExtRem;
567 Value *Trunc;
568 Type *Int64Ty = Builder.getInt64Ty();
569
570 if (Rem->getOpcode() == Instruction::SRem) {
571 ExtDividend = Builder.CreateSExt(V: Rem->getOperand(i_nocapture: 0), DestTy: Int64Ty);
572 ExtDivisor = Builder.CreateSExt(V: Rem->getOperand(i_nocapture: 1), DestTy: Int64Ty);
573 ExtRem = Builder.CreateSRem(LHS: ExtDividend, RHS: ExtDivisor);
574 } else {
575 ExtDividend = Builder.CreateZExt(V: Rem->getOperand(i_nocapture: 0), DestTy: Int64Ty);
576 ExtDivisor = Builder.CreateZExt(V: Rem->getOperand(i_nocapture: 1), DestTy: Int64Ty);
577 ExtRem = Builder.CreateURem(LHS: ExtDividend, RHS: ExtDivisor);
578 }
579 Trunc = Builder.CreateTrunc(V: ExtRem, DestTy: RemTy);
580
581 Rem->replaceAllUsesWith(V: Trunc);
582 Rem->dropAllReferences();
583 Rem->eraseFromParent();
584
585 return expandRemainder(Rem: cast<BinaryOperator>(Val: ExtRem));
586}
587
588/// Generate code to divide two integers of bitwidth up to 32 bits. Uses the
589/// above routines and extends the inputs/truncates the outputs to operate
590/// in 32 bits; that is, these routines are good for targets that have no
591/// or very little support for smaller than 32 bit integer arithmetic.
592///
593/// Replace Div with emulation code.
594bool llvm::expandDivisionUpTo32Bits(BinaryOperator *Div) {
595 assert((Div->getOpcode() == Instruction::SDiv ||
596 Div->getOpcode() == Instruction::UDiv) &&
597 "Trying to expand division from a non-division function");
598
599 Type *DivTy = Div->getType();
600 assert(!DivTy->isVectorTy() && "Div over vectors not supported");
601
602 unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
603
604 assert(DivTyBitWidth <= 32 && "Div of bitwidth greater than 32 not supported");
605
606 if (DivTyBitWidth == 32)
607 return expandDivision(Div);
608
609 // If bitwidth smaller than 32 extend inputs, extend output and proceed
610 // with 32 bit division.
611 IRBuilder<> Builder(Div);
612
613 Value *ExtDividend;
614 Value *ExtDivisor;
615 Value *ExtDiv;
616 Value *Trunc;
617 Type *Int32Ty = Builder.getInt32Ty();
618
619 if (Div->getOpcode() == Instruction::SDiv) {
620 ExtDividend = Builder.CreateSExt(V: Div->getOperand(i_nocapture: 0), DestTy: Int32Ty);
621 ExtDivisor = Builder.CreateSExt(V: Div->getOperand(i_nocapture: 1), DestTy: Int32Ty);
622 ExtDiv = Builder.CreateSDiv(LHS: ExtDividend, RHS: ExtDivisor);
623 } else {
624 ExtDividend = Builder.CreateZExt(V: Div->getOperand(i_nocapture: 0), DestTy: Int32Ty);
625 ExtDivisor = Builder.CreateZExt(V: Div->getOperand(i_nocapture: 1), DestTy: Int32Ty);
626 ExtDiv = Builder.CreateUDiv(LHS: ExtDividend, RHS: ExtDivisor);
627 }
628 Trunc = Builder.CreateTrunc(V: ExtDiv, DestTy: DivTy);
629
630 Div->replaceAllUsesWith(V: Trunc);
631 Div->dropAllReferences();
632 Div->eraseFromParent();
633
634 return expandDivision(Div: cast<BinaryOperator>(Val: ExtDiv));
635}
636
637/// Generate code to divide two integers of bitwidth up to 64 bits. Uses the
638/// above routines and extends the inputs/truncates the outputs to operate
639/// in 64 bits.
640///
641/// Replace Div with emulation code.
642bool llvm::expandDivisionUpTo64Bits(BinaryOperator *Div) {
643 assert((Div->getOpcode() == Instruction::SDiv ||
644 Div->getOpcode() == Instruction::UDiv) &&
645 "Trying to expand division from a non-division function");
646
647 Type *DivTy = Div->getType();
648 assert(!DivTy->isVectorTy() && "Div over vectors not supported");
649
650 unsigned DivTyBitWidth = DivTy->getIntegerBitWidth();
651
652 if (DivTyBitWidth >= 64)
653 return expandDivision(Div);
654
655 // If bitwidth smaller than 64 extend inputs, extend output and proceed
656 // with 64 bit division.
657 IRBuilder<> Builder(Div);
658
659 Value *ExtDividend;
660 Value *ExtDivisor;
661 Value *ExtDiv;
662 Value *Trunc;
663 Type *Int64Ty = Builder.getInt64Ty();
664
665 if (Div->getOpcode() == Instruction::SDiv) {
666 ExtDividend = Builder.CreateSExt(V: Div->getOperand(i_nocapture: 0), DestTy: Int64Ty);
667 ExtDivisor = Builder.CreateSExt(V: Div->getOperand(i_nocapture: 1), DestTy: Int64Ty);
668 ExtDiv = Builder.CreateSDiv(LHS: ExtDividend, RHS: ExtDivisor);
669 } else {
670 ExtDividend = Builder.CreateZExt(V: Div->getOperand(i_nocapture: 0), DestTy: Int64Ty);
671 ExtDivisor = Builder.CreateZExt(V: Div->getOperand(i_nocapture: 1), DestTy: Int64Ty);
672 ExtDiv = Builder.CreateUDiv(LHS: ExtDividend, RHS: ExtDivisor);
673 }
674 Trunc = Builder.CreateTrunc(V: ExtDiv, DestTy: DivTy);
675
676 Div->replaceAllUsesWith(V: Trunc);
677 Div->dropAllReferences();
678 Div->eraseFromParent();
679
680 return expandDivision(Div: cast<BinaryOperator>(Val: ExtDiv));
681}
682