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