← Back to branch summary

~ubuntu-branches/ubuntu/quantal/llvm-3.1/quantal

« back to all changes in this revision

Viewing changes to lib/Analysis/ValueTracking.cpp

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2012-04-10 23:38:33 UTC
  • mfrom: (1.1.2)
  • Revision ID: package-import@ubuntu.com-20120410233833-5ibwguerdnr58six
Tags: 3.1~svn154439-1
* New snapshot release
* Change the soname to match what Debian is expecting
* Clean up the dh_shlibdeps call

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/Analysis/ValueTracking.cpp
44
44
}
45
45
 
46
46
static void ComputeMaskedBitsAddSub(bool Add, Value *Op0, Value *Op1, bool NSW,
47
 
                                    const APInt &Mask,
48
47
                                    APInt &KnownZero, APInt &KnownOne,
49
48
                                    APInt &KnownZero2, APInt &KnownOne2,
50
49
                                    const TargetData *TD, unsigned Depth) {
54
53
      // than C (i.e. no wrap-around can happen).  For example, 20-X is
55
54
      // positive if we can prove that X is >= 0 and < 16.
56
55
      if (!CLHS->getValue().isNegative()) {
57
 
        unsigned BitWidth = Mask.getBitWidth();
 
56
        unsigned BitWidth = KnownZero.getBitWidth();
58
57
        unsigned NLZ = (CLHS->getValue()+1).countLeadingZeros();
59
58
        // NLZ can't be BitWidth with no sign bit
60
59
        APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
61
 
        llvm::ComputeMaskedBits(Op1, MaskV, KnownZero2, KnownOne2, TD, Depth+1);
 
60
        llvm::ComputeMaskedBits(Op1, KnownZero2, KnownOne2, TD, Depth+1);
62
61
    
63
62
        // If all of the MaskV bits are known to be zero, then we know the
64
63
        // output top bits are zero, because we now know that the output is
66
65
        if ((KnownZero2 & MaskV) == MaskV) {
67
66
          unsigned NLZ2 = CLHS->getValue().countLeadingZeros();
68
67
          // Top bits known zero.
69
 
          KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2) & Mask;
 
68
          KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
70
69
        }
71
70
      }
72
71
    }
73
72
  }
74
73
 
75
 
  unsigned BitWidth = Mask.getBitWidth();
 
74
  unsigned BitWidth = KnownZero.getBitWidth();
76
75
 
77
76
  // If one of the operands has trailing zeros, then the bits that the
78
77
  // other operand has in those bit positions will be preserved in the
79
78
  // result. For an add, this works with either operand. For a subtract,
80
79
  // this only works if the known zeros are in the right operand.
81
80
  APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0);
82
 
  APInt Mask2 = APInt::getLowBitsSet(BitWidth,
83
 
                                     BitWidth - Mask.countLeadingZeros());
84
 
  llvm::ComputeMaskedBits(Op0, Mask2, LHSKnownZero, LHSKnownOne, TD, Depth+1);
 
81
  llvm::ComputeMaskedBits(Op0, LHSKnownZero, LHSKnownOne, TD, Depth+1);
85
82
  assert((LHSKnownZero & LHSKnownOne) == 0 &&
86
83
         "Bits known to be one AND zero?");
87
84
  unsigned LHSKnownZeroOut = LHSKnownZero.countTrailingOnes();
88
85
 
89
 
  llvm::ComputeMaskedBits(Op1, Mask2, KnownZero2, KnownOne2, TD, Depth+1);
 
86
  llvm::ComputeMaskedBits(Op1, KnownZero2, KnownOne2, TD, Depth+1);
90
87
  assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 
91
88
  unsigned RHSKnownZeroOut = KnownZero2.countTrailingOnes();
92
89
 
111
108
  }
112
109
 
113
110
  // Are we still trying to solve for the sign bit?
114
 
  if (Mask.isNegative() && !KnownZero.isNegative() && !KnownOne.isNegative()) {
 
111
  if (!KnownZero.isNegative() && !KnownOne.isNegative()) {
115
112
    if (NSW) {
116
113
      if (Add) {
117
114
        // Adding two positive numbers can't wrap into negative
133
130
}
134
131
 
135
132
static void ComputeMaskedBitsMul(Value *Op0, Value *Op1, bool NSW,
136
 
                                 const APInt &Mask,
137
133
                                 APInt &KnownZero, APInt &KnownOne,
138
134
                                 APInt &KnownZero2, APInt &KnownOne2,
139
135
                                 const TargetData *TD, unsigned Depth) {
140
 
  unsigned BitWidth = Mask.getBitWidth();
141
 
  APInt Mask2 = APInt::getAllOnesValue(BitWidth);
142
 
  ComputeMaskedBits(Op1, Mask2, KnownZero, KnownOne, TD, Depth+1);
143
 
  ComputeMaskedBits(Op0, Mask2, KnownZero2, KnownOne2, TD, Depth+1);
 
136
  unsigned BitWidth = KnownZero.getBitWidth();
 
137
  ComputeMaskedBits(Op1, KnownZero, KnownOne, TD, Depth+1);
 
138
  ComputeMaskedBits(Op0, KnownZero2, KnownOne2, TD, Depth+1);
144
139
  assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
145
140
  assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
146
141
 
147
142
  bool isKnownNegative = false;
148
143
  bool isKnownNonNegative = false;
149
144
  // If the multiplication is known not to overflow, compute the sign bit.
150
 
  if (Mask.isNegative() && NSW) {
 
145
  if (NSW) {
151
146
    if (Op0 == Op1) {
152
147
      // The product of a number with itself is non-negative.
153
148
      isKnownNonNegative = true;
184
179
  LeadZ = std::min(LeadZ, BitWidth);
185
180
  KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
186
181
              APInt::getHighBitsSet(BitWidth, LeadZ);
187
 
  KnownZero &= Mask;
188
182
 
189
183
  // Only make use of no-wrap flags if we failed to compute the sign bit
190
184
  // directly.  This matters if the multiplication always overflows, in
197
191
    KnownOne.setBit(BitWidth - 1);
198
192
}
199
193
 
200
 
void llvm::computeMaskedBitsLoad(const MDNode &Ranges, const APInt &Mask,
201
 
                                 APInt &KnownZero) {
202
 
  unsigned BitWidth = Mask.getBitWidth();
 
194
void llvm::computeMaskedBitsLoad(const MDNode &Ranges, APInt &KnownZero) {
 
195
  unsigned BitWidth = KnownZero.getBitWidth();
203
196
  unsigned NumRanges = Ranges.getNumOperands() / 2;
204
197
  assert(NumRanges >= 1);
205
198
 
215
208
    MinLeadingZeros = std::min(LeadingZeros, MinLeadingZeros);
216
209
  }
217
210
 
218
 
  KnownZero = Mask & APInt::getHighBitsSet(BitWidth, MinLeadingZeros);
 
211
  KnownZero = APInt::getHighBitsSet(BitWidth, MinLeadingZeros);
219
212
}
220
 
/// ComputeMaskedBits - Determine which of the bits specified in Mask are
221
 
/// known to be either zero or one and return them in the KnownZero/KnownOne
222
 
/// bit sets.  This code only analyzes bits in Mask, in order to short-circuit
223
 
/// processing.
 
213
/// ComputeMaskedBits - Determine which of the bits are known to be either zero
 
214
/// or one and return them in the KnownZero/KnownOne bit sets.
 
215
///
224
216
/// NOTE: we cannot consider 'undef' to be "IsZero" here.  The problem is that
225
217
/// we cannot optimize based on the assumption that it is zero without changing
226
218
/// it to be an explicit zero.  If we don't change it to zero, other code could
230
222
///
231
223
/// This function is defined on values with integer type, values with pointer
232
224
/// type (but only if TD is non-null), and vectors of integers.  In the case
233
 
/// where V is a vector, the mask, known zero, and known one values are the
 
225
/// where V is a vector, known zero, and known one values are the
234
226
/// same width as the vector element, and the bit is set only if it is true
235
227
/// for all of the elements in the vector.
236
 
void llvm::ComputeMaskedBits(Value *V, const APInt &Mask,
237
 
                             APInt &KnownZero, APInt &KnownOne,
 
228
void llvm::ComputeMaskedBits(Value *V, APInt &KnownZero, APInt &KnownOne,
238
229
                             const TargetData *TD, unsigned Depth) {
239
230
  assert(V && "No Value?");
240
231
  assert(Depth <= MaxDepth && "Limit Search Depth");
241
 
  unsigned BitWidth = Mask.getBitWidth();
 
232
  unsigned BitWidth = KnownZero.getBitWidth();
 
233
 
242
234
  assert((V->getType()->isIntOrIntVectorTy() ||
243
235
          V->getType()->getScalarType()->isPointerTy()) &&
244
236
         "Not integer or pointer type!");
252
244
 
253
245
  if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
254
246
    // We know all of the bits for a constant!
255
 
    KnownOne = CI->getValue() & Mask;
256
 
    KnownZero = ~KnownOne & Mask;
 
247
    KnownOne = CI->getValue();
 
248
    KnownZero = ~KnownOne;
257
249
    return;
258
250
  }
259
251
  // Null and aggregate-zero are all-zeros.
260
252
  if (isa<ConstantPointerNull>(V) ||
261
253
      isa<ConstantAggregateZero>(V)) {
262
254
    KnownOne.clearAllBits();
263
 
    KnownZero = Mask;
 
255
    KnownZero = APInt::getAllOnesValue(BitWidth);
264
256
    return;
265
257
  }
266
258
  // Handle a constant vector by taking the intersection of the known bits of
297
289
      }
298
290
    }
299
291
    if (Align > 0)
300
 
      KnownZero = Mask & APInt::getLowBitsSet(BitWidth,
301
 
                                              CountTrailingZeros_32(Align));
 
292
      KnownZero = APInt::getLowBitsSet(BitWidth,
 
293
                                       CountTrailingZeros_32(Align));
302
294
    else
303
295
      KnownZero.clearAllBits();
304
296
    KnownOne.clearAllBits();
310
302
    if (GA->mayBeOverridden()) {
311
303
      KnownZero.clearAllBits(); KnownOne.clearAllBits();
312
304
    } else {
313
 
      ComputeMaskedBits(GA->getAliasee(), Mask, KnownZero, KnownOne,
314
 
                        TD, Depth+1);
 
305
      ComputeMaskedBits(GA->getAliasee(), KnownZero, KnownOne, TD, Depth+1);
315
306
    }
316
307
    return;
317
308
  }
320
311
    // Get alignment information off byval arguments if specified in the IR.
321
312
    if (A->hasByValAttr())
322
313
      if (unsigned Align = A->getParamAlignment())
323
 
        KnownZero = Mask & APInt::getLowBitsSet(BitWidth,
324
 
                                                CountTrailingZeros_32(Align));
 
314
        KnownZero = APInt::getLowBitsSet(BitWidth,
 
315
                                         CountTrailingZeros_32(Align));
325
316
    return;
326
317
  }
327
318
 
328
319
  // Start out not knowing anything.
329
320
  KnownZero.clearAllBits(); KnownOne.clearAllBits();
330
321
 
331
 
  if (Depth == MaxDepth || Mask == 0)
 
322
  if (Depth == MaxDepth)
332
323
    return;  // Limit search depth.
333
324
 
334
325
  Operator *I = dyn_cast<Operator>(V);
339
330
  default: break;
340
331
  case Instruction::Load:
341
332
    if (MDNode *MD = cast<LoadInst>(I)->getMetadata(LLVMContext::MD_range))
342
 
      computeMaskedBitsLoad(*MD, Mask, KnownZero);
 
333
      computeMaskedBitsLoad(*MD, KnownZero);
343
334
    return;
344
335
  case Instruction::And: {
345
336
    // If either the LHS or the RHS are Zero, the result is zero.
346
 
    ComputeMaskedBits(I->getOperand(1), Mask, KnownZero, KnownOne, TD, Depth+1);
347
 
    APInt Mask2(Mask & ~KnownZero);
348
 
    ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD,
349
 
                      Depth+1);
 
337
    ComputeMaskedBits(I->getOperand(1), KnownZero, KnownOne, TD, Depth+1);
 
338
    ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1);
350
339
    assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
351
340
    assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 
352
341
    
357
346
    return;
358
347
  }
359
348
  case Instruction::Or: {
360
 
    ComputeMaskedBits(I->getOperand(1), Mask, KnownZero, KnownOne, TD, Depth+1);
361
 
    APInt Mask2(Mask & ~KnownOne);
362
 
    ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD,
363
 
                      Depth+1);
 
349
    ComputeMaskedBits(I->getOperand(1), KnownZero, KnownOne, TD, Depth+1);
 
350
    ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1);
364
351
    assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
365
352
    assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 
366
353
    
371
358
    return;
372
359
  }
373
360
  case Instruction::Xor: {
374
 
    ComputeMaskedBits(I->getOperand(1), Mask, KnownZero, KnownOne, TD, Depth+1);
375
 
    ComputeMaskedBits(I->getOperand(0), Mask, KnownZero2, KnownOne2, TD,
376
 
                      Depth+1);
 
361
    ComputeMaskedBits(I->getOperand(1), KnownZero, KnownOne, TD, Depth+1);
 
362
    ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1);
377
363
    assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
378
364
    assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 
379
365
    
387
373
  case Instruction::Mul: {
388
374
    bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap();
389
375
    ComputeMaskedBitsMul(I->getOperand(0), I->getOperand(1), NSW,
390
 
                         Mask, KnownZero, KnownOne, KnownZero2, KnownOne2,
391
 
                         TD, Depth);
 
376
                         KnownZero, KnownOne, KnownZero2, KnownOne2, TD, Depth);
392
377
    break;
393
378
  }
394
379
  case Instruction::UDiv: {
395
380
    // For the purposes of computing leading zeros we can conservatively
396
381
    // treat a udiv as a logical right shift by the power of 2 known to
397
382
    // be less than the denominator.
398
 
    APInt AllOnes = APInt::getAllOnesValue(BitWidth);
399
 
    ComputeMaskedBits(I->getOperand(0),
400
 
                      AllOnes, KnownZero2, KnownOne2, TD, Depth+1);
 
383
    ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1);
401
384
    unsigned LeadZ = KnownZero2.countLeadingOnes();
402
385
 
403
386
    KnownOne2.clearAllBits();
404
387
    KnownZero2.clearAllBits();
405
 
    ComputeMaskedBits(I->getOperand(1),
406
 
                      AllOnes, KnownZero2, KnownOne2, TD, Depth+1);
 
388
    ComputeMaskedBits(I->getOperand(1), KnownZero2, KnownOne2, TD, Depth+1);
407
389
    unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
408
390
    if (RHSUnknownLeadingOnes != BitWidth)
409
391
      LeadZ = std::min(BitWidth,
410
392
                       LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
411
393
 
412
 
    KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ) & Mask;
 
394
    KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
413
395
    return;
414
396
  }
415
397
  case Instruction::Select:
416
 
    ComputeMaskedBits(I->getOperand(2), Mask, KnownZero, KnownOne, TD, Depth+1);
417
 
    ComputeMaskedBits(I->getOperand(1), Mask, KnownZero2, KnownOne2, TD,
 
398
    ComputeMaskedBits(I->getOperand(2), KnownZero, KnownOne, TD, Depth+1);
 
399
    ComputeMaskedBits(I->getOperand(1), KnownZero2, KnownOne2, TD,
418
400
                      Depth+1);
419
401
    assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
420
402
    assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 
447
429
    else
448
430
      SrcBitWidth = SrcTy->getScalarSizeInBits();
449
431
    
450
 
    APInt MaskIn = Mask.zextOrTrunc(SrcBitWidth);
451
432
    KnownZero = KnownZero.zextOrTrunc(SrcBitWidth);
452
433
    KnownOne = KnownOne.zextOrTrunc(SrcBitWidth);
453
 
    ComputeMaskedBits(I->getOperand(0), MaskIn, KnownZero, KnownOne, TD,
454
 
                      Depth+1);
 
434
    ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1);
455
435
    KnownZero = KnownZero.zextOrTrunc(BitWidth);
456
436
    KnownOne = KnownOne.zextOrTrunc(BitWidth);
457
437
    // Any top bits are known to be zero.
465
445
        // TODO: For now, not handling conversions like:
466
446
        // (bitcast i64 %x to <2 x i32>)
467
447
        !I->getType()->isVectorTy()) {
468
 
      ComputeMaskedBits(I->getOperand(0), Mask, KnownZero, KnownOne, TD,
469
 
                        Depth+1);
 
448
      ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1);
470
449
      return;
471
450
    }
472
451
    break;
475
454
    // Compute the bits in the result that are not present in the input.
476
455
    unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits();
477
456
      
478
 
    APInt MaskIn = Mask.trunc(SrcBitWidth);
479
457
    KnownZero = KnownZero.trunc(SrcBitWidth);
480
458
    KnownOne = KnownOne.trunc(SrcBitWidth);
481
 
    ComputeMaskedBits(I->getOperand(0), MaskIn, KnownZero, KnownOne, TD,
482
 
                      Depth+1);
 
459
    ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1);
483
460
    assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
484
461
    KnownZero = KnownZero.zext(BitWidth);
485
462
    KnownOne = KnownOne.zext(BitWidth);
496
473
    // (shl X, C1) & C2 == 0   iff   (X & C2 >>u C1) == 0
497
474
    if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
498
475
      uint64_t ShiftAmt = SA->getLimitedValue(BitWidth);
499
 
      APInt Mask2(Mask.lshr(ShiftAmt));
500
 
      ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero, KnownOne, TD,
501
 
                        Depth+1);
 
476
      ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1);
502
477
      assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
503
478
      KnownZero <<= ShiftAmt;
504
479
      KnownOne  <<= ShiftAmt;
513
488
      uint64_t ShiftAmt = SA->getLimitedValue(BitWidth);
514
489
      
515
490
      // Unsigned shift right.
516
 
      APInt Mask2(Mask.shl(ShiftAmt));
517
 
      ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero,KnownOne, TD,
518
 
                        Depth+1);
 
491
      ComputeMaskedBits(I->getOperand(0), KnownZero,KnownOne, TD, Depth+1);
519
492
      assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
520
493
      KnownZero = APIntOps::lshr(KnownZero, ShiftAmt);
521
494
      KnownOne  = APIntOps::lshr(KnownOne, ShiftAmt);
531
504
      uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1);
532
505
      
533
506
      // Signed shift right.
534
 
      APInt Mask2(Mask.shl(ShiftAmt));
535
 
      ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero, KnownOne, TD,
536
 
                        Depth+1);
 
507
      ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1);
537
508
      assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
538
509
      KnownZero = APIntOps::lshr(KnownZero, ShiftAmt);
539
510
      KnownOne  = APIntOps::lshr(KnownOne, ShiftAmt);
549
520
  case Instruction::Sub: {
550
521
    bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap();
551
522
    ComputeMaskedBitsAddSub(false, I->getOperand(0), I->getOperand(1), NSW,
552
 
                            Mask, KnownZero, KnownOne, KnownZero2, KnownOne2,
553
 
                            TD, Depth);
 
523
                            KnownZero, KnownOne, KnownZero2, KnownOne2, TD,
 
524
                            Depth);
554
525
    break;
555
526
  }
556
527
  case Instruction::Add: {
557
528
    bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap();
558
529
    ComputeMaskedBitsAddSub(true, I->getOperand(0), I->getOperand(1), NSW,
559
 
                            Mask, KnownZero, KnownOne, KnownZero2, KnownOne2,
560
 
                            TD, Depth);
 
530
                            KnownZero, KnownOne, KnownZero2, KnownOne2, TD,
 
531
                            Depth);
561
532
    break;
562
533
  }
563
534
  case Instruction::SRem:
565
536
      APInt RA = Rem->getValue().abs();
566
537
      if (RA.isPowerOf2()) {
567
538
        APInt LowBits = RA - 1;
568
 
        APInt Mask2 = LowBits | APInt::getSignBit(BitWidth);
569
 
        ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero2, KnownOne2, TD, 
570
 
                          Depth+1);
 
539
        ComputeMaskedBits(I->getOperand(0), KnownZero2, KnownOne2, TD, Depth+1);
571
540
 
572
541
        // The low bits of the first operand are unchanged by the srem.
573
542
        KnownZero = KnownZero2 & LowBits;
583
552
        if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
584
553
          KnownOne |= ~LowBits;
585
554
 
586
 
        KnownZero &= Mask;
587
 
        KnownOne &= Mask;
588
 
 
589
555
        assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
590
556
      }
591
557
    }
592
558
 
593
559
    // The sign bit is the LHS's sign bit, except when the result of the
594
560
    // remainder is zero.
595
 
    if (Mask.isNegative() && KnownZero.isNonNegative()) {
596
 
      APInt Mask2 = APInt::getSignBit(BitWidth);
 
561
    if (KnownZero.isNonNegative()) {
597
562
      APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0);
598
 
      ComputeMaskedBits(I->getOperand(0), Mask2, LHSKnownZero, LHSKnownOne, TD,
 
563
      ComputeMaskedBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, TD,
599
564
                        Depth+1);
600
565
      // If it's known zero, our sign bit is also zero.
601
566
      if (LHSKnownZero.isNegative())
608
573
      APInt RA = Rem->getValue();
609
574
      if (RA.isPowerOf2()) {
610
575
        APInt LowBits = (RA - 1);
611
 
        APInt Mask2 = LowBits & Mask;
612
 
        KnownZero |= ~LowBits & Mask;
613
 
        ComputeMaskedBits(I->getOperand(0), Mask2, KnownZero, KnownOne, TD,
 
576
        ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD,
614
577
                          Depth+1);
615
578
        assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 
579
        KnownZero |= ~LowBits;
 
580
        KnownOne &= LowBits;
616
581
        break;
617
582
      }
618
583
    }
619
584
 
620
585
    // Since the result is less than or equal to either operand, any leading
621
586
    // zero bits in either operand must also exist in the result.
622
 
    APInt AllOnes = APInt::getAllOnesValue(BitWidth);
623
 
    ComputeMaskedBits(I->getOperand(0), AllOnes, KnownZero, KnownOne,
624
 
                      TD, Depth+1);
625
 
    ComputeMaskedBits(I->getOperand(1), AllOnes, KnownZero2, KnownOne2,
626
 
                      TD, Depth+1);
 
587
    ComputeMaskedBits(I->getOperand(0), KnownZero, KnownOne, TD, Depth+1);
 
588
    ComputeMaskedBits(I->getOperand(1), KnownZero2, KnownOne2, TD, Depth+1);
627
589
 
628
590
    unsigned Leaders = std::max(KnownZero.countLeadingOnes(),
629
591
                                KnownZero2.countLeadingOnes());
630
592
    KnownOne.clearAllBits();
631
 
    KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & Mask;
 
593
    KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
632
594
    break;
633
595
  }
634
596
 
639
601
      Align = TD->getABITypeAlignment(AI->getType()->getElementType());
640
602
    
641
603
    if (Align > 0)
642
 
      KnownZero = Mask & APInt::getLowBitsSet(BitWidth,
643
 
                                              CountTrailingZeros_32(Align));
 
604
      KnownZero = APInt::getLowBitsSet(BitWidth, CountTrailingZeros_32(Align));
644
605
    break;
645
606
  }
646
607
  case Instruction::GetElementPtr: {
647
608
    // Analyze all of the subscripts of this getelementptr instruction
648
609
    // to determine if we can prove known low zero bits.
649
 
    APInt LocalMask = APInt::getAllOnesValue(BitWidth);
650
610
    APInt LocalKnownZero(BitWidth, 0), LocalKnownOne(BitWidth, 0);
651
 
    ComputeMaskedBits(I->getOperand(0), LocalMask,
652
 
                      LocalKnownZero, LocalKnownOne, TD, Depth+1);
 
611
    ComputeMaskedBits(I->getOperand(0), LocalKnownZero, LocalKnownOne, TD,
 
612
                      Depth+1);
653
613
    unsigned TrailZ = LocalKnownZero.countTrailingOnes();
654
614
 
655
615
    gep_type_iterator GTI = gep_type_begin(I);
669
629
        if (!IndexedTy->isSized()) return;
670
630
        unsigned GEPOpiBits = Index->getType()->getScalarSizeInBits();
671
631
        uint64_t TypeSize = TD ? TD->getTypeAllocSize(IndexedTy) : 1;
672
 
        LocalMask = APInt::getAllOnesValue(GEPOpiBits);
673
632
        LocalKnownZero = LocalKnownOne = APInt(GEPOpiBits, 0);
674
 
        ComputeMaskedBits(Index, LocalMask,
675
 
                          LocalKnownZero, LocalKnownOne, TD, Depth+1);
 
633
        ComputeMaskedBits(Index, LocalKnownZero, LocalKnownOne, TD, Depth+1);
676
634
        TrailZ = std::min(TrailZ,
677
635
                          unsigned(CountTrailingZeros_64(TypeSize) +
678
636
                                   LocalKnownZero.countTrailingOnes()));
679
637
      }
680
638
    }
681
639
    
682
 
    KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) & Mask;
 
640
    KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ);
683
641
    break;
684
642
  }
685
643
  case Instruction::PHI: {
714
672
            break;
715
673
          // Ok, we have a PHI of the form L op= R. Check for low
716
674
          // zero bits.
717
 
          APInt Mask2 = APInt::getAllOnesValue(BitWidth);
718
 
          ComputeMaskedBits(R, Mask2, KnownZero2, KnownOne2, TD, Depth+1);
719
 
          Mask2 = APInt::getLowBitsSet(BitWidth,
720
 
                                       KnownZero2.countTrailingOnes());
 
675
          ComputeMaskedBits(R, KnownZero2, KnownOne2, TD, Depth+1);
721
676
 
722
677
          // We need to take the minimum number of known bits
723
678
          APInt KnownZero3(KnownZero), KnownOne3(KnownOne);
724
 
          ComputeMaskedBits(L, Mask2, KnownZero3, KnownOne3, TD, Depth+1);
 
679
          ComputeMaskedBits(L, KnownZero3, KnownOne3, TD, Depth+1);
725
680
 
726
 
          KnownZero = Mask &
727
 
                      APInt::getLowBitsSet(BitWidth,
 
681
          KnownZero = APInt::getLowBitsSet(BitWidth,
728
682
                                           std::min(KnownZero2.countTrailingOnes(),
729
683
                                                    KnownZero3.countTrailingOnes()));
730
684
          break;
743
697
      if (P->hasConstantValue() == P)
744
698
        break;
745
699
 
746
 
      KnownZero = Mask;
747
 
      KnownOne = Mask;
 
700
      KnownZero = APInt::getAllOnesValue(BitWidth);
 
701
      KnownOne = APInt::getAllOnesValue(BitWidth);
748
702
      for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) {
749
703
        // Skip direct self references.
750
704
        if (P->getIncomingValue(i) == P) continue;
753
707
        KnownOne2 = APInt(BitWidth, 0);
754
708
        // Recurse, but cap the recursion to one level, because we don't
755
709
        // want to waste time spinning around in loops.
756
 
        ComputeMaskedBits(P->getIncomingValue(i), KnownZero | KnownOne,
757
 
                          KnownZero2, KnownOne2, TD, MaxDepth-1);
 
710
        ComputeMaskedBits(P->getIncomingValue(i), KnownZero2, KnownOne2, TD,
 
711
                          MaxDepth-1);
758
712
        KnownZero &= KnownZero2;
759
713
        KnownOne &= KnownOne2;
760
714
        // If all bits have been ruled out, there's no need to check
775
729
        // If this call is undefined for 0, the result will be less than 2^n.
776
730
        if (II->getArgOperand(1) == ConstantInt::getTrue(II->getContext()))
777
731
          LowBits -= 1;
778
 
        KnownZero = Mask & APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
 
732
        KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
779
733
        break;
780
734
      }
781
735
      case Intrinsic::ctpop: {
782
736
        unsigned LowBits = Log2_32(BitWidth)+1;
783
 
        KnownZero = Mask & APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
 
737
        KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
784
738
        break;
785
739
      }
786
740
      case Intrinsic::x86_sse42_crc32_64_8:
787
741
      case Intrinsic::x86_sse42_crc32_64_64:
788
 
        KnownZero = Mask & APInt::getHighBitsSet(64, 32);
 
742
        KnownZero = APInt::getHighBitsSet(64, 32);
789
743
        break;
790
744
      }
791
745
    }
800
754
        case Intrinsic::uadd_with_overflow:
801
755
        case Intrinsic::sadd_with_overflow:
802
756
          ComputeMaskedBitsAddSub(true, II->getArgOperand(0),
803
 
                                  II->getArgOperand(1), false, Mask,
804
 
                                  KnownZero, KnownOne, KnownZero2, KnownOne2,
805
 
                                  TD, Depth);
 
757
                                  II->getArgOperand(1), false, KnownZero,
 
758
                                  KnownOne, KnownZero2, KnownOne2, TD, Depth);
806
759
          break;
807
760
        case Intrinsic::usub_with_overflow:
808
761
        case Intrinsic::ssub_with_overflow:
809
762
          ComputeMaskedBitsAddSub(false, II->getArgOperand(0),
810
 
                                  II->getArgOperand(1), false, Mask,
811
 
                                  KnownZero, KnownOne, KnownZero2, KnownOne2,
812
 
                                  TD, Depth);
 
763
                                  II->getArgOperand(1), false, KnownZero,
 
764
                                  KnownOne, KnownZero2, KnownOne2, TD, Depth);
813
765
          break;
814
766
        case Intrinsic::umul_with_overflow:
815
767
        case Intrinsic::smul_with_overflow:
816
768
          ComputeMaskedBitsMul(II->getArgOperand(0), II->getArgOperand(1),
817
 
                               false, Mask, KnownZero, KnownOne,
 
769
                               false, KnownZero, KnownOne,
818
770
                               KnownZero2, KnownOne2, TD, Depth);
819
771
          break;
820
772
        }
835
787
  }
836
788
  APInt ZeroBits(BitWidth, 0);
837
789
  APInt OneBits(BitWidth, 0);
838
 
  ComputeMaskedBits(V, APInt::getSignBit(BitWidth), ZeroBits, OneBits, TD,
839
 
                    Depth);
 
790
  ComputeMaskedBits(V, ZeroBits, OneBits, TD, Depth);
840
791
  KnownOne = OneBits[BitWidth - 1];
841
792
  KnownZero = ZeroBits[BitWidth - 1];
842
793
}
944
895
 
945
896
    APInt KnownZero(BitWidth, 0);
946
897
    APInt KnownOne(BitWidth, 0);
947
 
    ComputeMaskedBits(X, APInt(BitWidth, 1), KnownZero, KnownOne, TD, Depth);
 
898
    ComputeMaskedBits(X, KnownZero, KnownOne, TD, Depth);
948
899
    if (KnownOne[0])
949
900
      return true;
950
901
  }
986
937
      APInt Mask = APInt::getSignedMaxValue(BitWidth);
987
938
      // The sign bit of X is set.  If some other bit is set then X is not equal
988
939
      // to INT_MIN.
989
 
      ComputeMaskedBits(X, Mask, KnownZero, KnownOne, TD, Depth);
 
940
      ComputeMaskedBits(X, KnownZero, KnownOne, TD, Depth);
990
941
      if ((KnownOne & Mask) != 0)
991
942
        return true;
992
943
      // The sign bit of Y is set.  If some other bit is set then Y is not equal
993
944
      // to INT_MIN.
994
 
      ComputeMaskedBits(Y, Mask, KnownZero, KnownOne, TD, Depth);
 
945
      ComputeMaskedBits(Y, KnownZero, KnownOne, TD, Depth);
995
946
      if ((KnownOne & Mask) != 0)
996
947
        return true;
997
948
    }
1021
972
  if (!BitWidth) return false;
1022
973
  APInt KnownZero(BitWidth, 0);
1023
974
  APInt KnownOne(BitWidth, 0);
1024
 
  ComputeMaskedBits(V, APInt::getAllOnesValue(BitWidth), KnownZero, KnownOne,
1025
 
                    TD, Depth);
 
975
  ComputeMaskedBits(V, KnownZero, KnownOne, TD, Depth);
1026
976
  return KnownOne != 0;
1027
977
}
1028
978
 
1038
988
bool llvm::MaskedValueIsZero(Value *V, const APInt &Mask,
1039
989
                             const TargetData *TD, unsigned Depth) {
1040
990
  APInt KnownZero(Mask.getBitWidth(), 0), KnownOne(Mask.getBitWidth(), 0);
1041
 
  ComputeMaskedBits(V, Mask, KnownZero, KnownOne, TD, Depth);
 
991
  ComputeMaskedBits(V, KnownZero, KnownOne, TD, Depth);
1042
992
  assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 
1043
993
  return (KnownZero & Mask) == Mask;
1044
994
}
1129
1079
    if (ConstantInt *CRHS = dyn_cast<ConstantInt>(U->getOperand(1)))
1130
1080
      if (CRHS->isAllOnesValue()) {
1131
1081
        APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0);
1132
 
        APInt Mask = APInt::getAllOnesValue(TyBits);
1133
 
        ComputeMaskedBits(U->getOperand(0), Mask, KnownZero, KnownOne, TD,
1134
 
                          Depth+1);
 
1082
        ComputeMaskedBits(U->getOperand(0), KnownZero, KnownOne, TD, Depth+1);
1135
1083
        
1136
1084
        // If the input is known to be 0 or 1, the output is 0/-1, which is all
1137
1085
        // sign bits set.
1138
 
        if ((KnownZero | APInt(TyBits, 1)) == Mask)
 
1086
        if ((KnownZero | APInt(TyBits, 1)).isAllOnesValue())
1139
1087
          return TyBits;
1140
1088
        
1141
1089
        // If we are subtracting one from a positive number, there is no carry
1156
1104
    if (ConstantInt *CLHS = dyn_cast<ConstantInt>(U->getOperand(0)))
1157
1105
      if (CLHS->isNullValue()) {
1158
1106
        APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0);
1159
 
        APInt Mask = APInt::getAllOnesValue(TyBits);
1160
 
        ComputeMaskedBits(U->getOperand(1), Mask, KnownZero, KnownOne, 
1161
 
                          TD, Depth+1);
 
1107
        ComputeMaskedBits(U->getOperand(1), KnownZero, KnownOne, TD, Depth+1);
1162
1108
        // If the input is known to be 0 or 1, the output is 0/-1, which is all
1163
1109
        // sign bits set.
1164
 
        if ((KnownZero | APInt(TyBits, 1)) == Mask)
 
1110
        if ((KnownZero | APInt(TyBits, 1)).isAllOnesValue())
1165
1111
          return TyBits;
1166
1112
        
1167
1113
        // If the input is known to be positive (the sign bit is known clear),
1203
1149
  // Finally, if we can prove that the top bits of the result are 0's or 1's,
1204
1150
  // use this information.
1205
1151
  APInt KnownZero(TyBits, 0), KnownOne(TyBits, 0);
1206
 
  APInt Mask = APInt::getAllOnesValue(TyBits);
1207
 
  ComputeMaskedBits(V, Mask, KnownZero, KnownOne, TD, Depth);
 
1152
  APInt Mask;
 
1153
  ComputeMaskedBits(V, KnownZero, KnownOne, TD, Depth);
1208
1154
  
1209
1155
  if (KnownZero.isNegative()) {        // sign bit is 0
1210
1156
    Mask = KnownZero;
1896
1842
      return false;
1897
1843
    APInt KnownZero(BitWidth, 0);
1898
1844
    APInt KnownOne(BitWidth, 0);
1899
 
    ComputeMaskedBits(Op, APInt::getAllOnesValue(BitWidth),
1900
 
                      KnownZero, KnownOne, TD);
 
1845
    ComputeMaskedBits(Op, KnownZero, KnownOne, TD);
1901
1846
    return !!KnownZero;
1902
1847
  }
1903
1848
  case Instruction::Load: {
1909
1854
  case Instruction::Call: {
1910
1855
   if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
1911
1856
     switch (II->getIntrinsicID()) {
 
1857
       // These synthetic intrinsics have no side-effects, and just mark
 
1858
       // information about their operands.
 
1859
       // FIXME: There are other no-op synthetic instructions that potentially
 
1860
       // should be considered at least *safe* to speculate...
 
1861
       case Intrinsic::dbg_declare:
 
1862
       case Intrinsic::dbg_value:
 
1863
         return true;
 
1864
 
1912
1865
       case Intrinsic::bswap:
1913
1866
       case Intrinsic::ctlz:
1914
1867
       case Intrinsic::ctpop: