LLVM  16.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"
19 #include "llvm/IR/Instructions.h"
20 #include "llvm/IR/Intrinsics.h"
21 
22 using 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
32 static Value *generateSignedRemainderCode(Value *Dividend, Value *Divisor,
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
73 static Value *generatedUnsignedRemainderCode(Value *Dividend, Value *Divisor,
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.
99 static 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.
141 static 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);
205  BasicBlock *BB1 = BasicBlock::Create(Builder.getContext(),
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 
384  Value *Remainder = generatedUnsignedRemainderCode(Rem->getOperand(0),
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
439  Value *Quotient = generateUnsignedDivisionCode(Div->getOperand(0),
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 }
llvm::expandDivisionUpTo32Bits
bool expandDivisionUpTo32Bits(BinaryOperator *Div)
Generate code to divide two integers, replacing Div with the generated code.
Definition: IntegerDivision.cpp:552
Int32Ty
IntegerType * Int32Ty
Definition: NVVMIntrRange.cpp:67
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
llvm::Function
Definition: Function.h:60
llvm::User::dropAllReferences
void dropAllReferences()
Drop all references to operands.
Definition: User.h:299
llvm::IRBuilder<>
Shift
bool Shift
Definition: README.txt:468
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::BasicBlock::splitBasicBlock
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:402
generateSignedDivisionCode
static Value * generateSignedDivisionCode(Value *Dividend, Value *Divisor, IRBuilder<> &Builder)
Generate code to divide two signed integers.
Definition: IntegerDivision.cpp:99
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::ISD::CTLZ
@ CTLZ
Definition: ISDOpcodes.h:702
Intrinsics.h
llvm::expandDivision
bool expandDivision(BinaryOperator *Div)
Generate code to divide two integers, replacing Div with the generated code.
Definition: IntegerDivision.cpp:407
llvm::Type::isVectorTy
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:246
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::BinaryOperator::getOpcode
BinaryOps getOpcode() const
Definition: InstrTypes.h:392
llvm::Instruction
Definition: Instruction.h:42
llvm::Value::setName
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:375
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:879
llvm::Type::getIntegerBitWidth
unsigned getIntegerBitWidth() const
Definition: DerivedTypes.h:97
generateSignedRemainderCode
static Value * generateSignedRemainderCode(Value *Dividend, Value *Divisor, IRBuilder<> &Builder)
Generate code to compute the remainder of two signed integers.
Definition: IntegerDivision.cpp:32
generateUnsignedDivisionCode
static Value * generateUnsignedDivisionCode(Value *Dividend, Value *Divisor, IRBuilder<> &Builder)
Generates code to divide two unsigned scalar 32-bit or 64-bit integers.
Definition: IntegerDivision.cpp:141
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:81
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2847
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::expandRemainderUpTo32Bits
bool expandRemainderUpTo32Bits(BinaryOperator *Rem)
Generate code to calculate the remainder of two integers, replacing Rem with the generated code.
Definition: IntegerDivision.cpp:456
llvm::expandRemainder
bool expandRemainder(BinaryOperator *Rem)
Generate code to calculate the remainder of two integers, replacing Rem with the generated code.
Definition: IntegerDivision.cpp:354
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::BinaryOperator
Definition: InstrTypes.h:188
llvm::expandDivisionUpTo64Bits
bool expandDivisionUpTo64Bits(BinaryOperator *Div)
Generate code to divide two integers, replacing Div with the generated code.
Definition: IntegerDivision.cpp:600
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:532
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:97
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
generatedUnsignedRemainderCode
static Value * generatedUnsignedRemainderCode(Value *Dividend, Value *Divisor, IRBuilder<> &Builder)
Generate code to compute the remainder of two unsigned integers.
Definition: IntegerDivision.cpp:73
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::Intrinsic::getDeclaration
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:1481
llvm::expandRemainderUpTo64Bits
bool expandRemainderUpTo64Bits(BinaryOperator *Rem)
Generate code to calculate the remainder of two integers, replacing Rem with the generated code.
Definition: IntegerDivision.cpp:505
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
llvm::ConstantInt::getSigned
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
Definition: Constants.cpp:893
Function.h
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
IntegerDivision.h
Instructions.h
llvm::IntegerType::getBitWidth
unsigned getBitWidth() const
Get the number of bits in this IntegerType.
Definition: DerivedTypes.h:72
llvm::PHINode
Definition: Instructions.h:2697
llvm::BasicBlock::getTerminator
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:119
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::Value
LLVM Value Representation.
Definition: Value.h:74