LLVM 20.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 *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(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 =
161 Intrinsic::getOrInsertDeclaration(F->getParent(), Intrinsic::ctlz, 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), Builder);
386
387 Rem->replaceAllUsesWith(Remainder);
388 Rem->dropAllReferences();
389 Rem->eraseFromParent();
390
391 // Expand the udiv
392 if (BinaryOperator *UDiv = dyn_cast<BinaryOperator>(Builder.GetInsertPoint())) {
393 assert(UDiv->getOpcode() == Instruction::UDiv && "Non-udiv in expansion?");
394 expandDivision(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.
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(Div->getOperand(0),
419 Div->getOperand(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(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>(Builder.GetInsertPoint());
434 Div = BO;
435 }
436
437 // Insert the unsigned division code
439 Div->getOperand(1),
440 Builder);
441 Div->replaceAllUsesWith(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.
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(Rem->getOperand(0), Int32Ty);
483 ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int32Ty);
484 ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);
485 } else {
486 ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int32Ty);
487 ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int32Ty);
488 ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
489 }
490 Trunc = Builder.CreateTrunc(ExtRem, RemTy);
491
492 Rem->replaceAllUsesWith(Trunc);
493 Rem->dropAllReferences();
494 Rem->eraseFromParent();
495
496 return expandRemainder(cast<BinaryOperator>(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.
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(Rem->getOperand(0), Int64Ty);
529 ExtDivisor = Builder.CreateSExt(Rem->getOperand(1), Int64Ty);
530 ExtRem = Builder.CreateSRem(ExtDividend, ExtDivisor);
531 } else {
532 ExtDividend = Builder.CreateZExt(Rem->getOperand(0), Int64Ty);
533 ExtDivisor = Builder.CreateZExt(Rem->getOperand(1), Int64Ty);
534 ExtRem = Builder.CreateURem(ExtDividend, ExtDivisor);
535 }
536 Trunc = Builder.CreateTrunc(ExtRem, RemTy);
537
538 Rem->replaceAllUsesWith(Trunc);
539 Rem->dropAllReferences();
540 Rem->eraseFromParent();
541
542 return expandRemainder(cast<BinaryOperator>(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.
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(Div->getOperand(0), Int32Ty);
578 ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int32Ty);
579 ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);
580 } else {
581 ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int32Ty);
582 ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int32Ty);
583 ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);
584 }
585 Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
586
587 Div->replaceAllUsesWith(Trunc);
588 Div->dropAllReferences();
589 Div->eraseFromParent();
590
591 return expandDivision(cast<BinaryOperator>(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.
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(Div->getOperand(0), Int64Ty);
624 ExtDivisor = Builder.CreateSExt(Div->getOperand(1), Int64Ty);
625 ExtDiv = Builder.CreateSDiv(ExtDividend, ExtDivisor);
626 } else {
627 ExtDividend = Builder.CreateZExt(Div->getOperand(0), Int64Ty);
628 ExtDivisor = Builder.CreateZExt(Div->getOperand(1), Int64Ty);
629 ExtDiv = Builder.CreateUDiv(ExtDividend, ExtDivisor);
630 }
631 Trunc = Builder.CreateTrunc(ExtDiv, DivTy);
632
633 Div->replaceAllUsesWith(Trunc);
634 Div->dropAllReferences();
635 Div->eraseFromParent();
636
637 return expandDivision(cast<BinaryOperator>(ExtDiv));
638}
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 * generateUnsignedRemainderCode(Value *Dividend, Value *Divisor, IRBuilder<> &Builder)
Generate code to compute the remainder of two unsigned 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.
#define F(x, y, z)
Definition: MD5.cpp:55
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:212
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:577
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:219
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:239
BinaryOps getOpcode() const
Definition: InstrTypes.h:370
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
Definition: Constants.h:126
Value * CreateSRem(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1433
ConstantInt * getTrue()
Get the constant value for i1 true.
Definition: IRBuilder.h:463
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Definition: IRBuilder.cpp:1048
BasicBlock::iterator GetInsertPoint() const
Definition: IRBuilder.h:172
Value * CreateSExt(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:2060
Value * CreateFreeze(Value *V, const Twine &Name="")
Definition: IRBuilder.h:2566
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1460
IntegerType * getInt32Ty()
Fetch the type representing a 32-bit integer.
Definition: IRBuilder.h:523
BasicBlock * GetInsertBlock() const
Definition: IRBuilder.h:171
IntegerType * getInt64Ty()
Fetch the type representing a 64-bit integer.
Definition: IRBuilder.h:528
Value * CreateUDiv(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1401
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
Definition: IRBuilder.h:2429
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2273
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1367
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:494
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:1144
Value * CreateICmpUGT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2281
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1439
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Definition: IRBuilder.h:2048
LLVMContext & getContext() const
Definition: IRBuilder.h:173
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1498
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1350
Value * CreateSDiv(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1414
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value * > Args={}, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:2444
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Definition: IRBuilder.h:2034
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1520
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Definition: IRBuilder.h:1138
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:177
Value * CreateAShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1479
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1542
Value * CreateLogicalOr(Value *Cond1, Value *Cond2, const Twine &Name="")
Definition: IRBuilder.h:1705
Value * CreateURem(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1427
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1384
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2697
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:92
Class to represent integer types.
Definition: DerivedTypes.h:42
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Definition: DerivedTypes.h:74
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:270
void dropAllReferences()
Drop all references to operands.
Definition: User.h:345
Value * getOperand(unsigned i) const
Definition: User.h:228
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 * getOrInsertDeclaration(Module *M, ID id, ArrayRef< Type * > Tys={})
Look up the Function declaration of the intrinsic id in the Module M.
Definition: Intrinsics.cpp:731
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:217
bool expandRemainder(BinaryOperator *Rem)
Generate code to calculate the remainder of two integers, replacing Rem with the generated code.