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