← Back to branch summary

~pali/+junk/llvm-toolchain-3.7

« back to all changes in this revision

Viewing changes to lib/Transforms/Utils/IntegerDivision.cpp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2015-07-15 17:51:08 UTC
  • Revision ID: package-import@ubuntu.com-20150715175108-l8mynwovkx4zx697
Tags: upstream-3.7~+rc2
Import upstream version 3.7~+rc2

Show diffs side-by-side

added added

removed removed

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