LLVM 19.0.0git
IntegerDivision.cpp
Go to the documentation of this file.
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
17#include "llvm/IR/Function.h"
18#include "llvm/IR/IRBuilder.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(BitWidth, 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(Dividend);
50 Divisor = Builder.CreateFreeze(Divisor);
51 Value *DividendSign = Builder.CreateAShr(Dividend, Shift);
52 Value *DivisorSign = Builder.CreateAShr(Divisor, Shift);
53 Value *DvdXor = Builder.CreateXor(Dividend, DividendSign);
54 Value *DvsXor = Builder.CreateXor(Divisor, DivisorSign);
55 Value *UDividend = Builder.CreateSub(DvdXor, DividendSign);
56 Value *UDivisor = Builder.CreateSub(DvsXor, DivisorSign);
57 Value *URem = Builder.CreateURem(UDividend, UDivisor);
58 Value *Xored = Builder.CreateXor(URem, DividendSign);
59 Value *SRem = Builder.CreateSub(Xored, DividendSign);
60
61 if (Instruction *URemInst = dyn_cast<Instruction>(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(Dividend);
83 Divisor = Builder.CreateFreeze(Divisor);
84 Value *Quotient = Builder.CreateUDiv(Dividend, Divisor);
85 Value *Product = Builder.CreateMul(Divisor, Quotient);
86 Value *Remainder = Builder.CreateSub(Dividend, Product);
87
88 if (Instruction *UDiv = dyn_cast<Instruction>(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(BitWidth, 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(Dividend);
120 Divisor = Builder.CreateFreeze(Divisor);
121 Value *Tmp = Builder.CreateAShr(Dividend, Shift);
122 Value *Tmp1 = Builder.CreateAShr(Divisor, Shift);
123 Value *Tmp2 = Builder.CreateXor(Tmp, Dividend);
124 Value *U_Dvnd = Builder.CreateSub(Tmp2, Tmp);
125 Value *Tmp3 = Builder.CreateXor(Tmp1, Divisor);
126 Value *U_Dvsr = Builder.CreateSub(Tmp3, Tmp1);
127 Value *Q_Sgn = Builder.CreateXor(Tmp1, Tmp);
128 Value *Q_Mag = Builder.CreateUDiv(U_Dvnd, U_Dvsr);
129 Value *Tmp4 = Builder.CreateXor(Q_Mag, Q_Sgn);
130 Value *Q = Builder.CreateSub(Tmp4, Q_Sgn);
131
132 if (Instruction *UDiv = dyn_cast<Instruction>(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>(Dividend->getType());
149 unsigned BitWidth = DivTy->getBitWidth();
150
151 ConstantInt *Zero = ConstantInt::get(DivTy, 0);
152 ConstantInt *One = ConstantInt::get(DivTy, 1);
153 ConstantInt *NegOne = ConstantInt::getSigned(DivTy, -1);
154 ConstantInt *MSB = ConstantInt::get(DivTy, BitWidth - 1);
155
156 ConstantInt *True = Builder.getTrue();
157
158 BasicBlock *IBB = Builder.GetInsertBlock();
159 Function *F = IBB->getParent();
160 Function *CTLZ = Intrinsic::getDeclaration(F->getParent(), Intrinsic::ctlz,
161 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(Builder.GetInsertPoint(),
198 "udiv-end");
199 BasicBlock *LoopExit = BasicBlock::Create(Builder.getContext(),
200 "udiv-loop-exit", F, End);
201 BasicBlock *DoWhile = BasicBlock::Create(Builder.getContext(),
202 "udiv-do-while", F, End);
203 BasicBlock *Preheader = BasicBlock::Create(Builder.getContext(),
204 "udiv-preheader", F, End);
206 "udiv-bb1", F, 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(Divisor);
230 Dividend = Builder.CreateFreeze(Dividend);
231 Value *Ret0_1 = Builder.CreateICmpEQ(Divisor, Zero);
232 Value *Ret0_2 = Builder.CreateICmpEQ(Dividend, Zero);
233 Value *Ret0_3 = Builder.CreateOr(Ret0_1, Ret0_2);
234 Value *Tmp0 = Builder.CreateCall(CTLZ, {Divisor, True});
235 Value *Tmp1 = Builder.CreateCall(CTLZ, {Dividend, True});
236 Value *SR = Builder.CreateSub(Tmp0, Tmp1);
237 Value *Ret0_4 = Builder.CreateICmpUGT(SR, MSB);
238 Value *Ret0 = Builder.CreateLogicalOr(Ret0_3, Ret0_4);
239 Value *RetDividend = Builder.CreateICmpEQ(SR, MSB);
240 Value *RetVal = Builder.CreateSelect(Ret0, Zero, Dividend);
241 Value *EarlyRet = Builder.CreateLogicalOr(Ret0, RetDividend);
242 Builder.CreateCondBr(EarlyRet, End, 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(SR, One);
252 Value *Tmp2 = Builder.CreateSub(MSB, SR);
253 Value *Q = Builder.CreateShl(Dividend, Tmp2);
254 Value *SkipLoop = Builder.CreateICmpEQ(SR_1, Zero);
255 Builder.CreateCondBr(SkipLoop, LoopExit, 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(Dividend, SR_1);
263 Value *Tmp4 = Builder.CreateAdd(Divisor, NegOne);
264 Builder.CreateBr(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(DivTy, 2);
286 PHINode *SR_3 = Builder.CreatePHI(DivTy, 2);
287 PHINode *R_1 = Builder.CreatePHI(DivTy, 2);
288 PHINode *Q_2 = Builder.CreatePHI(DivTy, 2);
289 Value *Tmp5 = Builder.CreateShl(R_1, One);
290 Value *Tmp6 = Builder.CreateLShr(Q_2, MSB);
291 Value *Tmp7 = Builder.CreateOr(Tmp5, Tmp6);
292 Value *Tmp8 = Builder.CreateShl(Q_2, One);
293 Value *Q_1 = Builder.CreateOr(Carry_1, Tmp8);
294 Value *Tmp9 = Builder.CreateSub(Tmp4, Tmp7);
295 Value *Tmp10 = Builder.CreateAShr(Tmp9, MSB);
296 Value *Carry = Builder.CreateAnd(Tmp10, One);
297 Value *Tmp11 = Builder.CreateAnd(Tmp10, Divisor);
298 Value *R = Builder.CreateSub(Tmp7, Tmp11);
299 Value *SR_2 = Builder.CreateAdd(SR_3, NegOne);
300 Value *Tmp12 = Builder.CreateICmpEQ(SR_2, Zero);
301 Builder.CreateCondBr(Tmp12, LoopExit, 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(DivTy, 2);
311 PHINode *Q_3 = Builder.CreatePHI(DivTy, 2);
312 Value *Tmp13 = Builder.CreateShl(Q_3, One);
313 Value *Q_4 = Builder.CreateOr(Carry_2, Tmp13);
314 Builder.CreateBr(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(End, End->begin());
320 PHINode *Q_5 = Builder.CreatePHI(DivTy, 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(Zero, Preheader);
325 Carry_1->addIncoming(Carry, DoWhile);
326 // ; %sr_3 = phi i32 [ %sr_1, %preheader ], [ %sr_2, %do-while ]
327 SR_3->addIncoming(SR_1, Preheader);
328 SR_3->addIncoming(SR_2, DoWhile);
329 // ; %r_1 = phi i32 [ %tmp3, %preheader ], [ %r, %do-while ]
330 R_1->addIncoming(Tmp3, Preheader);
331 R_1->addIncoming(R, DoWhile);
332 // ; %q_2 = phi i32 [ %q, %preheader ], [ %q_1, %do-while ]
333 Q_2->addIncoming(Q, Preheader);
334 Q_2->addIncoming(Q_1, DoWhile);
335 // ; %carry_2 = phi i32 [ 0, %bb1 ], [ %carry, %do-while ]
336 Carry_2->addIncoming(Zero, BB1);
337 Carry_2->addIncoming(Carry, DoWhile);
338 // ; %q_3 = phi i32 [ %q, %bb1 ], [ %q_1, %do-while ]
339 Q_3->addIncoming(Q, BB1);
340 Q_3->addIncoming(Q_1, DoWhile);
341 // ; %q_5 = phi i32 [ %q_4, %loop-exit ], [ %retVal, %special-cases ]
342 Q_5->addIncoming(Q_4, LoopExit);
343 Q_5->addIncoming(RetVal, 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.
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(Rem->getOperand(0),
366 Rem->getOperand(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(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>(Builder.GetInsertPoint());
381 Rem = BO;
382 }
383
385 Rem->getOperand(1),
386 Builder);
387
388 Rem->replaceAllUsesWith(Remainder);
389 Rem->dropAllReferences();
390 Rem->eraseFromParent();
391
392 // Expand the udiv
393 if (BinaryOperator *UDiv = dyn_cast<BinaryOperator>(Builder.GetInsertPoint())) {
394 assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?");
395 expandDivision(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.
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(Div->getOperand(0),
420 Div->getOperand(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(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>(Builder.GetInsertPoint());
435 Div = BO;
436 }
437
438 // Insert the unsigned division code
440 Div->getOperand(1),
441 Builder);
442 Div->replaceAllUsesWith(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.
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(Rem->getOperand(0), Int32Ty);
484 ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int32Ty);
485 ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);
486 } else {
487 ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int32Ty);
488 ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int32Ty);
489 ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
490 }
491 Trunc = Builder.CreateTrunc(ExtRem, RemTy);
492
493 Rem->replaceAllUsesWith(Trunc);
494 Rem->dropAllReferences();
495 Rem->eraseFromParent();
496
497 return expandRemainder(cast<BinaryOperator>(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.
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(Rem->getOperand(0), Int64Ty);
530 ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int64Ty);
531 ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);
532 } else {
533 ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int64Ty);
534 ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int64Ty);
535 ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
536 }
537 Trunc = Builder.CreateTrunc(ExtRem, RemTy);
538
539 Rem->replaceAllUsesWith(Trunc);
540 Rem->dropAllReferences();
541 Rem->eraseFromParent();
542
543 return expandRemainder(cast<BinaryOperator>(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.
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(Div->getOperand(0), Int32Ty);
579 ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int32Ty);
580 ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);
581 } else {
582 ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int32Ty);
583 ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int32Ty);
584 ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);
585 }
586 Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
587
588 Div->replaceAllUsesWith(Trunc);
589 Div->dropAllReferences();
590 Div->eraseFromParent();
591
592 return expandDivision(cast<BinaryOperator>(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.
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(Div->getOperand(0), Int64Ty);
625 ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int64Ty);
626 ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);
627 } else {
628 ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int64Ty);
629 ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int64Ty);
630 ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);
631 }
632 Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
633
634 Div->replaceAllUsesWith(Trunc);
635 Div->dropAllReferences();
636 Div->eraseFromParent();
637
638 return expandDivision(cast<BinaryOperator>(ExtDiv));
639}
bool End
Definition: ELF_riscv.cpp:480
static Value * generateSignedDivisionCode(Value *Dividend, Value *Divisor, IRBuilder<> &Builder)
Generate code to divide two signed integers.
static Value * generateSignedRemainderCode(Value *Dividend, Value *Divisor, IRBuilder<> &Builder)
Generate code to compute the remainder of two signed integers.
static Value * generateUnsignedDivisionCode(Value *Dividend, Value *Divisor, IRBuilder<> &Builder)
Generates code to divide two unsigned scalar 32-bit or 64-bit integers.
static Value * generatedUnsignedRemainderCode(Value *Dividend, Value *Divisor, IRBuilder<> &Builder)
Generate code to compute the remainder of two unsigned integers.
#define F(x, y, z)
Definition: MD5.cpp:55
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:201
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:571
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:208
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:223
BinaryOps getOpcode() const
Definition: InstrTypes.h:442
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
Definition: Constants.h:124
Value * CreateSRem(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1408
ConstantInt * getTrue()
Get the constant value for i1 true.
Definition: IRBuilder.h:464
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.cpp:1090
BasicBlock::iterator GetInsertPoint() const
Definition: IRBuilder.h:173
Value * CreateSExt(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2031
Value * CreateFreeze(Value *V, const Twine &Name="")
Definition: IRBuilder.h:2533
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1435
IntegerType * getInt32Ty()
Fetch the type representing a 32-bit integer.
Definition: IRBuilder.h:524
BasicBlock * GetInsertBlock() const
Definition: IRBuilder.h:172
IntegerType * getInt64Ty()
Fetch the type representing a 64-bit integer.
Definition: IRBuilder.h:529
Value * CreateUDiv(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1376
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
Definition: IRBuilder.h:2395
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2239
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1342
ConstantInt * getIntN(unsigned N, uint64_t C)
Get a constant N-bit value, zero extended or truncated from a 64-bit value.
Definition: IRBuilder.h:495
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
Definition: IRBuilder.h:1118
Value * CreateICmpUGT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2247
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1414
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Definition: IRBuilder.h:2019
LLVMContext & getContext() const
Definition: IRBuilder.h:174
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1473
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1325
Value * CreateSDiv(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1389
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Definition: IRBuilder.h:2005
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1495
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Definition: IRBuilder.h:1112
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:178
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value * > Args=std::nullopt, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2410
Value * CreateAShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1454
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1517
Value * CreateLogicalOr(Value *Cond1, Value *Cond2, const Twine &Name="")
Definition: IRBuilder.h:1680
Value * CreateURem(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1402
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1359
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2664
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:87
Class to represent integer types.
Definition: DerivedTypes.h:40
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Definition: DerivedTypes.h:72
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
unsigned getIntegerBitWidth() const
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:265
void dropAllReferences()
Drop all references to operands.
Definition: User.h:299
Value * getOperand(unsigned i) const
Definition: User.h:169
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:377
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
self_iterator getIterator()
Definition: ilist_node.h:132
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1474
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool expandDivision(BinaryOperator *Div)
Generate code to divide two integers, replacing Div with the generated code.
bool expandRemainderUpTo32Bits(BinaryOperator *Rem)
Generate code to calculate the remainder of two integers, replacing Rem with the generated code.
bool expandRemainderUpTo64Bits(BinaryOperator *Rem)
Generate code to calculate the remainder of two integers, replacing Rem with the generated code.
bool expandDivisionUpTo64Bits(BinaryOperator *Div)
Generate code to divide two integers, replacing Div with the generated code.
bool expandDivisionUpTo32Bits(BinaryOperator *Div)
Generate code to divide two integers, replacing Div with the generated code.
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:191
bool expandRemainder(BinaryOperator *Rem)
Generate code to calculate the remainder of two integers, replacing Rem with the generated code.