lib/Analysis/LazyValueInfo.cpp

   1 //===- LazyValueInfo.cpp - Value constraint analysis ----------------------===//
   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 defines the interface for lazy computation of value constraint
  11 // information.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "lazy-value-info"
  16 #include "llvm/Analysis/LazyValueInfo.h"
  17 #include "llvm/Analysis/ValueTracking.h"
  18 #include "llvm/Constants.h"
  19 #include "llvm/Instructions.h"
  20 #include "llvm/IntrinsicInst.h"
  21 #include "llvm/Analysis/ConstantFolding.h"
  22 #include "llvm/Target/TargetData.h"
  23 #include "llvm/Target/TargetLibraryInfo.h"
  24 #include "llvm/Support/CFG.h"
  25 #include "llvm/Support/ConstantRange.h"
  26 #include "llvm/Support/Debug.h"
  27 #include "llvm/Support/raw_ostream.h"
  28 #include "llvm/Support/ValueHandle.h"
  29 #include "llvm/ADT/DenseSet.h"
  30 #include "llvm/ADT/STLExtras.h"
  31 #include <map>
  32 #include <stack>
  33 using namespace llvm;
  34
  35 char LazyValueInfo::ID = 0;
  36 INITIALIZE_PASS_BEGIN(LazyValueInfo, "lazy-value-info",
  37                 "Lazy Value Information Analysis", false, true)
  38 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
  39 INITIALIZE_PASS_END(LazyValueInfo, "lazy-value-info",
  40                 "Lazy Value Information Analysis", false, true)
  41
  42 namespace llvm {
  43   FunctionPass *createLazyValueInfoPass() { return new LazyValueInfo(); }
  44 }
  45
  46
  47 //===----------------------------------------------------------------------===//
  48 //                               LVILatticeVal
  49 //===----------------------------------------------------------------------===//
  50
  51 /// LVILatticeVal - This is the information tracked by LazyValueInfo for each
  52 /// value.
  53 ///
  54 /// FIXME: This is basically just for bringup, this can be made a lot more rich
  55 /// in the future.
  56 ///
  57 namespace {
  58 class LVILatticeVal {
  59   enum LatticeValueTy {
  60     /// undefined - This Value has no known value yet.
  61     undefined,
  62
  63     /// constant - This Value has a specific constant value.
  64     constant,
  65     /// notconstant - This Value is known to not have the specified value.
  66     notconstant,
  67
  68     /// constantrange - The Value falls within this range.
  69     constantrange,
  70
  71     /// overdefined - This value is not known to be constant, and we know that
  72     /// it has a value.
  73     overdefined
  74   };
  75
  76   /// Val: This stores the current lattice value along with the Constant* for
  77   /// the constant if this is a 'constant' or 'notconstant' value.
  78   LatticeValueTy Tag;
  79   Constant *Val;
  80   ConstantRange Range;
  81
  82 public:
  83   LVILatticeVal() : Tag(undefined), Val(0), Range(1, true) {}
  84
  85   static LVILatticeVal get(Constant *C) {
  86     LVILatticeVal Res;
  87     if (!isa<UndefValue>(C))
  88       Res.markConstant(C);
  89     return Res;
  90   }
  91   static LVILatticeVal getNot(Constant *C) {
  92     LVILatticeVal Res;
  93     if (!isa<UndefValue>(C))
  94       Res.markNotConstant(C);
  95     return Res;
  96   }
  97   static LVILatticeVal getRange(ConstantRange CR) {
  98     LVILatticeVal Res;
  99     Res.markConstantRange(CR);
 100     return Res;
 101   }
 102
 103   bool isUndefined() const     { return Tag == undefined; }
 104   bool isConstant() const      { return Tag == constant; }
 105   bool isNotConstant() const   { return Tag == notconstant; }
 106   bool isConstantRange() const { return Tag == constantrange; }
 107   bool isOverdefined() const   { return Tag == overdefined; }
 108
 109   Constant *getConstant() const {
 110     assert(isConstant() && "Cannot get the constant of a non-constant!");
 111     return Val;
 112   }
 113
 114   Constant *getNotConstant() const {
 115     assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
 116     return Val;
 117   }
 118
 119   ConstantRange getConstantRange() const {
 120     assert(isConstantRange() &&
 121            "Cannot get the constant-range of a non-constant-range!");
 122     return Range;
 123   }
 124
 125   /// markOverdefined - Return true if this is a change in status.
 126   bool markOverdefined() {
 127     if (isOverdefined())
 128       return false;
 129     Tag = overdefined;
 130     return true;
 131   }
 132
 133   /// markConstant - Return true if this is a change in status.
 134   bool markConstant(Constant *V) {
 135     assert(V && "Marking constant with NULL");
 136     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
 137       return markConstantRange(ConstantRange(CI->getValue()));
 138     if (isa<UndefValue>(V))
 139       return false;
 140
 141     assert((!isConstant() || getConstant() == V) &&
 142            "Marking constant with different value");
 143     assert(isUndefined());
 144     Tag = constant;
 145     Val = V;
 146     return true;
 147   }
 148
 149   /// markNotConstant - Return true if this is a change in status.
 150   bool markNotConstant(Constant *V) {
 151     assert(V && "Marking constant with NULL");
 152     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
 153       return markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue()));
 154     if (isa<UndefValue>(V))
 155       return false;
 156
 157     assert((!isConstant() || getConstant() != V) &&
 158            "Marking constant !constant with same value");
 159     assert((!isNotConstant() || getNotConstant() == V) &&
 160            "Marking !constant with different value");
 161     assert(isUndefined() || isConstant());
 162     Tag = notconstant;
 163     Val = V;
 164     return true;
 165   }
 166
 167   /// markConstantRange - Return true if this is a change in status.
 168   bool markConstantRange(const ConstantRange NewR) {
 169     if (isConstantRange()) {
 170       if (NewR.isEmptySet())
 171         return markOverdefined();
 172
 173       bool changed = Range == NewR;
 174       Range = NewR;
 175       return changed;
 176     }
 177
 178     assert(isUndefined());
 179     if (NewR.isEmptySet())
 180       return markOverdefined();
 181
 182     Tag = constantrange;
 183     Range = NewR;
 184     return true;
 185   }
 186
 187   /// mergeIn - Merge the specified lattice value into this one, updating this
 188   /// one and returning true if anything changed.
 189   bool mergeIn(const LVILatticeVal &RHS) {
 190     if (RHS.isUndefined() || isOverdefined()) return false;
 191     if (RHS.isOverdefined()) return markOverdefined();
 192
 193     if (isUndefined()) {
 194       Tag = RHS.Tag;
 195       Val = RHS.Val;
 196       Range = RHS.Range;
 197       return true;
 198     }
 199
 200     if (isConstant()) {
 201       if (RHS.isConstant()) {
 202         if (Val == RHS.Val)
 203           return false;
 204         return markOverdefined();
 205       }
 206
 207       if (RHS.isNotConstant()) {
 208         if (Val == RHS.Val)
 209           return markOverdefined();
 210
 211         // Unless we can prove that the two Constants are different, we must
 212         // move to overdefined.
 213         // FIXME: use TargetData/TargetLibraryInfo for smarter constant folding.
 214         if (ConstantInt *Res = dyn_cast<ConstantInt>(
 215                 ConstantFoldCompareInstOperands(CmpInst::ICMP_NE,
 216                                                 getConstant(),
 217                                                 RHS.getNotConstant())))
 218           if (Res->isOne())
 219             return markNotConstant(RHS.getNotConstant());
 220
 221         return markOverdefined();
 222       }
 223
 224       // RHS is a ConstantRange, LHS is a non-integer Constant.
 225
 226       // FIXME: consider the case where RHS is a range [1, 0) and LHS is
 227       // a function. The correct result is to pick up RHS.
 228
 229       return markOverdefined();
 230     }
 231
 232     if (isNotConstant()) {
 233       if (RHS.isConstant()) {
 234         if (Val == RHS.Val)
 235           return markOverdefined();
 236
 237         // Unless we can prove that the two Constants are different, we must
 238         // move to overdefined.
 239         // FIXME: use TargetData/TargetLibraryInfo for smarter constant folding.
 240         if (ConstantInt *Res = dyn_cast<ConstantInt>(
 241                 ConstantFoldCompareInstOperands(CmpInst::ICMP_NE,
 242                                                 getNotConstant(),
 243                                                 RHS.getConstant())))
 244           if (Res->isOne())
 245             return false;
 246
 247         return markOverdefined();
 248       }
 249
 250       if (RHS.isNotConstant()) {
 251         if (Val == RHS.Val)
 252           return false;
 253         return markOverdefined();
 254       }
 255
 256       return markOverdefined();
 257     }
 258
 259     assert(isConstantRange() && "New LVILattice type?");
 260     if (!RHS.isConstantRange())
 261       return markOverdefined();
 262
 263     ConstantRange NewR = Range.unionWith(RHS.getConstantRange());
 264     if (NewR.isFullSet())
 265       return markOverdefined();
 266     return markConstantRange(NewR);
 267   }
 268 };
 269
 270 } // end anonymous namespace.
 271
 272 namespace llvm {
 273 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val)
 274     LLVM_ATTRIBUTE_USED;
 275 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) {
 276   if (Val.isUndefined())
 277     return OS << "undefined";
 278   if (Val.isOverdefined())
 279     return OS << "overdefined";
 280
 281   if (Val.isNotConstant())
 282     return OS << "notconstant<" << *Val.getNotConstant() << '>';
 283   else if (Val.isConstantRange())
 284     return OS << "constantrange<" << Val.getConstantRange().getLower() << ", "
 285               << Val.getConstantRange().getUpper() << '>';
 286   return OS << "constant<" << *Val.getConstant() << '>';
 287 }
 288 }
 289
 290 //===----------------------------------------------------------------------===//
 291 //                          LazyValueInfoCache Decl
 292 //===----------------------------------------------------------------------===//
 293
 294 namespace {
 295   /// LVIValueHandle - A callback value handle update the cache when
 296   /// values are erased.
 297   class LazyValueInfoCache;
 298   struct LVIValueHandle : public CallbackVH {
 299     LazyValueInfoCache *Parent;
 300
 301     LVIValueHandle(Value *V, LazyValueInfoCache *P)
 302       : CallbackVH(V), Parent(P) { }
 303
 304     void deleted();
 305     void allUsesReplacedWith(Value *V) {
 306       deleted();
 307     }
 308   };
 309 }
 310
 311 namespace {
 312   /// LazyValueInfoCache - This is the cache kept by LazyValueInfo which
 313   /// maintains information about queries across the clients' queries.
 314   class LazyValueInfoCache {
 315     /// ValueCacheEntryTy - This is all of the cached block information for
 316     /// exactly one Value*.  The entries are sorted by the BasicBlock* of the
 317     /// entries, allowing us to do a lookup with a binary search.
 318     typedef std::map<AssertingVH<BasicBlock>, LVILatticeVal> ValueCacheEntryTy;
 319
 320     /// ValueCache - This is all of the cached information for all values,
 321     /// mapped from Value* to key information.
 322     std::map<LVIValueHandle, ValueCacheEntryTy> ValueCache;
 323
 324     /// OverDefinedCache - This tracks, on a per-block basis, the set of
 325     /// values that are over-defined at the end of that block.  This is required
 326     /// for cache updating.
 327     typedef std::pair<AssertingVH<BasicBlock>, Value*> OverDefinedPairTy;
 328     DenseSet<OverDefinedPairTy> OverDefinedCache;
 329
 330     /// SeenBlocks - Keep track of all blocks that we have ever seen, so we
 331     /// don't spend time removing unused blocks from our caches.
 332     DenseSet<AssertingVH<BasicBlock> > SeenBlocks;
 333
 334     /// BlockValueStack - This stack holds the state of the value solver
 335     /// during a query.  It basically emulates the callstack of the naive
 336     /// recursive value lookup process.
 337     std::stack<std::pair<BasicBlock*, Value*> > BlockValueStack;
 338
 339     friend struct LVIValueHandle;
 340
 341     /// OverDefinedCacheUpdater - A helper object that ensures that the
 342     /// OverDefinedCache is updated whenever solveBlockValue returns.
 343     struct OverDefinedCacheUpdater {
 344       LazyValueInfoCache *Parent;
 345       Value *Val;
 346       BasicBlock *BB;
 347       LVILatticeVal &BBLV;
 348
 349       OverDefinedCacheUpdater(Value *V, BasicBlock *B, LVILatticeVal &LV,
 350                        LazyValueInfoCache *P)
 351         : Parent(P), Val(V), BB(B), BBLV(LV) { }
 352
 353       bool markResult(bool changed) {
 354         if (changed && BBLV.isOverdefined())
 355           Parent->OverDefinedCache.insert(std::make_pair(BB, Val));
 356         return changed;
 357       }
 358     };
 359
 360
 361
 362     LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
 363     bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
 364                       LVILatticeVal &Result);
 365     bool hasBlockValue(Value *Val, BasicBlock *BB);
 366
 367     // These methods process one work item and may add more. A false value
 368     // returned means that the work item was not completely processed and must
 369     // be revisited after going through the new items.
 370     bool solveBlockValue(Value *Val, BasicBlock *BB);
 371     bool solveBlockValueNonLocal(LVILatticeVal &BBLV,
 372                                  Value *Val, BasicBlock *BB);
 373     bool solveBlockValuePHINode(LVILatticeVal &BBLV,
 374                                 PHINode *PN, BasicBlock *BB);
 375     bool solveBlockValueConstantRange(LVILatticeVal &BBLV,
 376                                       Instruction *BBI, BasicBlock *BB);
 377
 378     void solve();
 379
 380     ValueCacheEntryTy &lookup(Value *V) {
 381       return ValueCache[LVIValueHandle(V, this)];
 382     }
 383
 384   public:
 385     /// getValueInBlock - This is the query interface to determine the lattice
 386     /// value for the specified Value* at the end of the specified block.
 387     LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB);
 388
 389     /// getValueOnEdge - This is the query interface to determine the lattice
 390     /// value for the specified Value* that is true on the specified edge.
 391     LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB);
 392
 393     /// threadEdge - This is the update interface to inform the cache that an
 394     /// edge from PredBB to OldSucc has been threaded to be from PredBB to
 395     /// NewSucc.
 396     void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
 397
 398     /// eraseBlock - This is part of the update interface to inform the cache
 399     /// that a block has been deleted.
 400     void eraseBlock(BasicBlock *BB);
 401
 402     /// clear - Empty the cache.
 403     void clear() {
 404       SeenBlocks.clear();
 405       ValueCache.clear();
 406       OverDefinedCache.clear();
 407     }
 408   };
 409 } // end anonymous namespace
 410
 411 void LVIValueHandle::deleted() {
 412   typedef std::pair<AssertingVH<BasicBlock>, Value*> OverDefinedPairTy;
 413
 414   SmallVector<OverDefinedPairTy, 4> ToErase;
 415   for (DenseSet<OverDefinedPairTy>::iterator
 416        I = Parent->OverDefinedCache.begin(),
 417        E = Parent->OverDefinedCache.end();
 418        I != E; ++I) {
 419     if (I->second == getValPtr())
 420       ToErase.push_back(*I);
 421   }
 422
 423   for (SmallVector<OverDefinedPairTy, 4>::iterator I = ToErase.begin(),
 424        E = ToErase.end(); I != E; ++I)
 425     Parent->OverDefinedCache.erase(*I);
 426
 427   // This erasure deallocates *this, so it MUST happen after we're done
 428   // using any and all members of *this.
 429   Parent->ValueCache.erase(*this);
 430 }
 431
 432 void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
 433   // Shortcut if we have never seen this block.
 434   DenseSet<AssertingVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
 435   if (I == SeenBlocks.end())
 436     return;
 437   SeenBlocks.erase(I);
 438
 439   SmallVector<OverDefinedPairTy, 4> ToErase;
 440   for (DenseSet<OverDefinedPairTy>::iterator  I = OverDefinedCache.begin(),
 441        E = OverDefinedCache.end(); I != E; ++I) {
 442     if (I->first == BB)
 443       ToErase.push_back(*I);
 444   }
 445
 446   for (SmallVector<OverDefinedPairTy, 4>::iterator I = ToErase.begin(),
 447        E = ToErase.end(); I != E; ++I)
 448     OverDefinedCache.erase(*I);
 449
 450   for (std::map<LVIValueHandle, ValueCacheEntryTy>::iterator
 451        I = ValueCache.begin(), E = ValueCache.end(); I != E; ++I)
 452     I->second.erase(BB);
 453 }
 454
 455 void LazyValueInfoCache::solve() {
 456   while (!BlockValueStack.empty()) {
 457     std::pair<BasicBlock*, Value*> &e = BlockValueStack.top();
 458     if (solveBlockValue(e.second, e.first))
 459       BlockValueStack.pop();
 460   }
 461 }
 462
 463 bool LazyValueInfoCache::hasBlockValue(Value *Val, BasicBlock *BB) {
 464   // If already a constant, there is nothing to compute.
 465   if (isa<Constant>(Val))
 466     return true;
 467
 468   LVIValueHandle ValHandle(Val, this);
 469   if (!ValueCache.count(ValHandle)) return false;
 470   return ValueCache[ValHandle].count(BB);
 471 }
 472
 473 LVILatticeVal LazyValueInfoCache::getBlockValue(Value *Val, BasicBlock *BB) {
 474   // If already a constant, there is nothing to compute.
 475   if (Constant *VC = dyn_cast<Constant>(Val))
 476     return LVILatticeVal::get(VC);
 477
 478   SeenBlocks.insert(BB);
 479   return lookup(Val)[BB];
 480 }
 481
 482 bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
 483   if (isa<Constant>(Val))
 484     return true;
 485
 486   ValueCacheEntryTy &Cache = lookup(Val);
 487   SeenBlocks.insert(BB);
 488   LVILatticeVal &BBLV = Cache[BB];
 489
 490   // OverDefinedCacheUpdater is a helper object that will update
 491   // the OverDefinedCache for us when this method exits.  Make sure to
 492   // call markResult on it as we exist, passing a bool to indicate if the
 493   // cache needs updating, i.e. if we have solve a new value or not.
 494   OverDefinedCacheUpdater ODCacheUpdater(Val, BB, BBLV, this);
 495
 496   // If we've already computed this block's value, return it.
 497   if (!BBLV.isUndefined()) {
 498     DEBUG(dbgs() << "  reuse BB '" << BB->getName() << "' val=" << BBLV <<'\n');
 499
 500     // Since we're reusing a cached value here, we don't need to update the
 501     // OverDefinedCahce.  The cache will have been properly updated
 502     // whenever the cached value was inserted.
 503     ODCacheUpdater.markResult(false);
 504     return true;
 505   }
 506
 507   // Otherwise, this is the first time we're seeing this block.  Reset the
 508   // lattice value to overdefined, so that cycles will terminate and be
 509   // conservatively correct.
 510   BBLV.markOverdefined();
 511
 512   Instruction *BBI = dyn_cast<Instruction>(Val);
 513   if (BBI == 0 || BBI->getParent() != BB) {
 514     return ODCacheUpdater.markResult(solveBlockValueNonLocal(BBLV, Val, BB));
 515   }
 516
 517   if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
 518     return ODCacheUpdater.markResult(solveBlockValuePHINode(BBLV, PN, BB));
 519   }
 520
 521   if (AllocaInst *AI = dyn_cast<AllocaInst>(BBI)) {
 522     BBLV = LVILatticeVal::getNot(ConstantPointerNull::get(AI->getType()));
 523     return ODCacheUpdater.markResult(true);
 524   }
 525
 526   // We can only analyze the definitions of certain classes of instructions
 527   // (integral binops and casts at the moment), so bail if this isn't one.
 528   LVILatticeVal Result;
 529   if ((!isa<BinaryOperator>(BBI) && !isa<CastInst>(BBI)) ||
 530      !BBI->getType()->isIntegerTy()) {
 531     DEBUG(dbgs() << " compute BB '" << BB->getName()
 532                  << "' - overdefined because inst def found.\n");
 533     BBLV.markOverdefined();
 534     return ODCacheUpdater.markResult(true);
 535   }
 536
 537   // FIXME: We're currently limited to binops with a constant RHS.  This should
 538   // be improved.
 539   BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
 540   if (BO && !isa<ConstantInt>(BO->getOperand(1))) {
 541     DEBUG(dbgs() << " compute BB '" << BB->getName()
 542                  << "' - overdefined because inst def found.\n");
 543
 544     BBLV.markOverdefined();
 545     return ODCacheUpdater.markResult(true);
 546   }
 547
 548   return ODCacheUpdater.markResult(solveBlockValueConstantRange(BBLV, BBI, BB));
 549 }
 550
 551 static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
 552   if (LoadInst *L = dyn_cast<LoadInst>(I)) {
 553     return L->getPointerAddressSpace() == 0 &&
 554         GetUnderlyingObject(L->getPointerOperand()) ==
 555         GetUnderlyingObject(Ptr);
 556   }
 557   if (StoreInst *S = dyn_cast<StoreInst>(I)) {
 558     return S->getPointerAddressSpace() == 0 &&
 559         GetUnderlyingObject(S->getPointerOperand()) ==
 560         GetUnderlyingObject(Ptr);
 561   }
 562   if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
 563     if (MI->isVolatile()) return false;
 564
 565     // FIXME: check whether it has a valuerange that excludes zero?
 566     ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
 567     if (!Len || Len->isZero()) return false;
 568
 569     if (MI->getDestAddressSpace() == 0)
 570       if (MI->getRawDest() == Ptr || MI->getDest() == Ptr)
 571         return true;
 572     if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
 573       if (MTI->getSourceAddressSpace() == 0)
 574         if (MTI->getRawSource() == Ptr || MTI->getSource() == Ptr)
 575           return true;
 576   }
 577   return false;
 578 }
 579
 580 bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV,
 581                                                  Value *Val, BasicBlock *BB) {
 582   LVILatticeVal Result;  // Start Undefined.
 583
 584   // If this is a pointer, and there's a load from that pointer in this BB,
 585   // then we know that the pointer can't be NULL.
 586   bool NotNull = false;
 587   if (Val->getType()->isPointerTy()) {
 588     if (isa<AllocaInst>(Val)) {
 589       NotNull = true;
 590     } else {
 591       for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();BI != BE;++BI){
 592         if (InstructionDereferencesPointer(BI, Val)) {
 593           NotNull = true;
 594           break;
 595         }
 596       }
 597     }
 598   }
 599
 600   // If this is the entry block, we must be asking about an argument.  The
 601   // value is overdefined.
 602   if (BB == &BB->getParent()->getEntryBlock()) {
 603     assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
 604     if (NotNull) {
 605       PointerType *PTy = cast<PointerType>(Val->getType());
 606       Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
 607     } else {
 608       Result.markOverdefined();
 609     }
 610     BBLV = Result;
 611     return true;
 612   }
 613
 614   // Loop over all of our predecessors, merging what we know from them into
 615   // result.
 616   bool EdgesMissing = false;
 617   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
 618     LVILatticeVal EdgeResult;
 619     EdgesMissing |= !getEdgeValue(Val, *PI, BB, EdgeResult);
 620     if (EdgesMissing)
 621       continue;
 622
 623     Result.mergeIn(EdgeResult);
 624
 625     // If we hit overdefined, exit early.  The BlockVals entry is already set
 626     // to overdefined.
 627     if (Result.isOverdefined()) {
 628       DEBUG(dbgs() << " compute BB '" << BB->getName()
 629             << "' - overdefined because of pred.\n");
 630       // If we previously determined that this is a pointer that can't be null
 631       // then return that rather than giving up entirely.
 632       if (NotNull) {
 633         PointerType *PTy = cast<PointerType>(Val->getType());
 634         Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
 635       }
 636
 637       BBLV = Result;
 638       return true;
 639     }
 640   }
 641   if (EdgesMissing)
 642     return false;
 643
 644   // Return the merged value, which is more precise than 'overdefined'.
 645   assert(!Result.isOverdefined());
 646   BBLV = Result;
 647   return true;
 648 }
 649
 650 bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV,
 651                                                 PHINode *PN, BasicBlock *BB) {
 652   LVILatticeVal Result;  // Start Undefined.
 653
 654   // Loop over all of our predecessors, merging what we know from them into
 655   // result.
 656   bool EdgesMissing = false;
 657   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 658     BasicBlock *PhiBB = PN->getIncomingBlock(i);
 659     Value *PhiVal = PN->getIncomingValue(i);
 660     LVILatticeVal EdgeResult;
 661     EdgesMissing |= !getEdgeValue(PhiVal, PhiBB, BB, EdgeResult);
 662     if (EdgesMissing)
 663       continue;
 664
 665     Result.mergeIn(EdgeResult);
 666
 667     // If we hit overdefined, exit early.  The BlockVals entry is already set
 668     // to overdefined.
 669     if (Result.isOverdefined()) {
 670       DEBUG(dbgs() << " compute BB '" << BB->getName()
 671             << "' - overdefined because of pred.\n");
 672
 673       BBLV = Result;
 674       return true;
 675     }
 676   }
 677   if (EdgesMissing)
 678     return false;
 679
 680   // Return the merged value, which is more precise than 'overdefined'.
 681   assert(!Result.isOverdefined() && "Possible PHI in entry block?");
 682   BBLV = Result;
 683   return true;
 684 }
 685
 686 bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
 687                                                       Instruction *BBI,
 688                                                       BasicBlock *BB) {
 689   // Figure out the range of the LHS.  If that fails, bail.
 690   if (!hasBlockValue(BBI->getOperand(0), BB)) {
 691     BlockValueStack.push(std::make_pair(BB, BBI->getOperand(0)));
 692     return false;
 693   }
 694
 695   LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
 696   if (!LHSVal.isConstantRange()) {
 697     BBLV.markOverdefined();
 698     return true;
 699   }
 700
 701   ConstantRange LHSRange = LHSVal.getConstantRange();
 702   ConstantRange RHSRange(1);
 703   IntegerType *ResultTy = cast<IntegerType>(BBI->getType());
 704   if (isa<BinaryOperator>(BBI)) {
 705     if (ConstantInt *RHS = dyn_cast<ConstantInt>(BBI->getOperand(1))) {
 706       RHSRange = ConstantRange(RHS->getValue());
 707     } else {
 708       BBLV.markOverdefined();
 709       return true;
 710     }
 711   }
 712
 713   // NOTE: We're currently limited by the set of operations that ConstantRange
 714   // can evaluate symbolically.  Enhancing that set will allows us to analyze
 715   // more definitions.
 716   LVILatticeVal Result;
 717   switch (BBI->getOpcode()) {
 718   case Instruction::Add:
 719     Result.markConstantRange(LHSRange.add(RHSRange));
 720     break;
 721   case Instruction::Sub:
 722     Result.markConstantRange(LHSRange.sub(RHSRange));
 723     break;
 724   case Instruction::Mul:
 725     Result.markConstantRange(LHSRange.multiply(RHSRange));
 726     break;
 727   case Instruction::UDiv:
 728     Result.markConstantRange(LHSRange.udiv(RHSRange));
 729     break;
 730   case Instruction::Shl:
 731     Result.markConstantRange(LHSRange.shl(RHSRange));
 732     break;
 733   case Instruction::LShr:
 734     Result.markConstantRange(LHSRange.lshr(RHSRange));
 735     break;
 736   case Instruction::Trunc:
 737     Result.markConstantRange(LHSRange.truncate(ResultTy->getBitWidth()));
 738     break;
 739   case Instruction::SExt:
 740     Result.markConstantRange(LHSRange.signExtend(ResultTy->getBitWidth()));
 741     break;
 742   case Instruction::ZExt:
 743     Result.markConstantRange(LHSRange.zeroExtend(ResultTy->getBitWidth()));
 744     break;
 745   case Instruction::BitCast:
 746     Result.markConstantRange(LHSRange);
 747     break;
 748   case Instruction::And:
 749     Result.markConstantRange(LHSRange.binaryAnd(RHSRange));
 750     break;
 751   case Instruction::Or:
 752     Result.markConstantRange(LHSRange.binaryOr(RHSRange));
 753     break;
 754
 755   // Unhandled instructions are overdefined.
 756   default:
 757     DEBUG(dbgs() << " compute BB '" << BB->getName()
 758                  << "' - overdefined because inst def found.\n");
 759     Result.markOverdefined();
 760     break;
 761   }
 762
 763   BBLV = Result;
 764   return true;
 765 }
 766
 767 /// getEdgeValue - This method attempts to infer more complex
 768 bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
 769                                       BasicBlock *BBTo, LVILatticeVal &Result) {
 770   // If already a constant, there is nothing to compute.
 771   if (Constant *VC = dyn_cast<Constant>(Val)) {
 772     Result = LVILatticeVal::get(VC);
 773     return true;
 774   }
 775
 776   // TODO: Handle more complex conditionals.  If (v == 0 || v2 < 1) is false, we
 777   // know that v != 0.
 778   if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
 779     // If this is a conditional branch and only one successor goes to BBTo, then
 780     // we maybe able to infer something from the condition.
 781     if (BI->isConditional() &&
 782         BI->getSuccessor(0) != BI->getSuccessor(1)) {
 783       bool isTrueDest = BI->getSuccessor(0) == BBTo;
 784       assert(BI->getSuccessor(!isTrueDest) == BBTo &&
 785              "BBTo isn't a successor of BBFrom");
 786
 787       // If V is the condition of the branch itself, then we know exactly what
 788       // it is.
 789       if (BI->getCondition() == Val) {
 790         Result = LVILatticeVal::get(ConstantInt::get(
 791                               Type::getInt1Ty(Val->getContext()), isTrueDest));
 792         return true;
 793       }
 794
 795       // If the condition of the branch is an equality comparison, we may be
 796       // able to infer the value.
 797       ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition());
 798       if (ICI && ICI->getOperand(0) == Val &&
 799           isa<Constant>(ICI->getOperand(1))) {
 800         if (ICI->isEquality()) {
 801           // We know that V has the RHS constant if this is a true SETEQ or
 802           // false SETNE.
 803           if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
 804             Result = LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
 805           else
 806             Result = LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1)));
 807           return true;
 808         }
 809
 810         if (ConstantInt *CI = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
 811           // Calculate the range of values that would satisfy the comparison.
 812           ConstantRange CmpRange(CI->getValue(), CI->getValue()+1);
 813           ConstantRange TrueValues =
 814             ConstantRange::makeICmpRegion(ICI->getPredicate(), CmpRange);
 815
 816           // If we're interested in the false dest, invert the condition.
 817           if (!isTrueDest) TrueValues = TrueValues.inverse();
 818
 819           // Figure out the possible values of the query BEFORE this branch.
 820           if (!hasBlockValue(Val, BBFrom)) {
 821             BlockValueStack.push(std::make_pair(BBFrom, Val));
 822             return false;
 823           }
 824
 825           LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
 826           if (!InBlock.isConstantRange()) {
 827             Result = LVILatticeVal::getRange(TrueValues);
 828             return true;
 829           }
 830
 831           // Find all potential values that satisfy both the input and output
 832           // conditions.
 833           ConstantRange PossibleValues =
 834             TrueValues.intersectWith(InBlock.getConstantRange());
 835
 836           Result = LVILatticeVal::getRange(PossibleValues);
 837           return true;
 838         }
 839       }
 840     }
 841   }
 842
 843   // If the edge was formed by a switch on the value, then we may know exactly
 844   // what it is.
 845   if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
 846     if (SI->getCondition() == Val) {
 847       // We don't know anything in the default case.
 848       if (SI->getDefaultDest() == BBTo) {
 849         Result.markOverdefined();
 850         return true;
 851       }
 852
 853       // We only know something if there is exactly one value that goes from
 854       // BBFrom to BBTo.
 855       unsigned NumEdges = 0;
 856       ConstantInt *EdgeVal = 0;
 857       for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) {
 858         if (SI->getSuccessor(i) != BBTo) continue;
 859         if (NumEdges++) break;
 860         EdgeVal = SI->getCaseValue(i);
 861       }
 862       assert(EdgeVal && "Missing successor?");
 863       if (NumEdges == 1) {
 864         Result = LVILatticeVal::get(EdgeVal);
 865         return true;
 866       }
 867     }
 868   }
 869
 870   // Otherwise see if the value is known in the block.
 871   if (hasBlockValue(Val, BBFrom)) {
 872     Result = getBlockValue(Val, BBFrom);
 873     return true;
 874   }
 875   BlockValueStack.push(std::make_pair(BBFrom, Val));
 876   return false;
 877 }
 878
 879 LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB) {
 880   DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
 881         << BB->getName() << "'\n");
 882
 883   BlockValueStack.push(std::make_pair(BB, V));
 884   solve();
 885   LVILatticeVal Result = getBlockValue(V, BB);
 886
 887   DEBUG(dbgs() << "  Result = " << Result << "\n");
 888   return Result;
 889 }
 890
 891 LVILatticeVal LazyValueInfoCache::
 892 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB) {
 893   DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
 894         << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
 895
 896   LVILatticeVal Result;
 897   if (!getEdgeValue(V, FromBB, ToBB, Result)) {
 898     solve();
 899     bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result);
 900     (void)WasFastQuery;
 901     assert(WasFastQuery && "More work to do after problem solved?");
 902   }
 903
 904   DEBUG(dbgs() << "  Result = " << Result << "\n");
 905   return Result;
 906 }
 907
 908 void LazyValueInfoCache::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
 909                                     BasicBlock *NewSucc) {
 910   // When an edge in the graph has been threaded, values that we could not
 911   // determine a value for before (i.e. were marked overdefined) may be possible
 912   // to solve now.  We do NOT try to proactively update these values.  Instead,
 913   // we clear their entries from the cache, and allow lazy updating to recompute
 914   // them when needed.
 915
 916   // The updating process is fairly simple: we need to dropped cached info
 917   // for all values that were marked overdefined in OldSucc, and for those same
 918   // values in any successor of OldSucc (except NewSucc) in which they were
 919   // also marked overdefined.
 920   std::vector<BasicBlock*> worklist;
 921   worklist.push_back(OldSucc);
 922
 923   DenseSet<Value*> ClearSet;
 924   for (DenseSet<OverDefinedPairTy>::iterator I = OverDefinedCache.begin(),
 925        E = OverDefinedCache.end(); I != E; ++I) {
 926     if (I->first == OldSucc)
 927       ClearSet.insert(I->second);
 928   }
 929
 930   // Use a worklist to perform a depth-first search of OldSucc's successors.
 931   // NOTE: We do not need a visited list since any blocks we have already
 932   // visited will have had their overdefined markers cleared already, and we
 933   // thus won't loop to their successors.
 934   while (!worklist.empty()) {
 935     BasicBlock *ToUpdate = worklist.back();
 936     worklist.pop_back();
 937
 938     // Skip blocks only accessible through NewSucc.
 939     if (ToUpdate == NewSucc) continue;
 940
 941     bool changed = false;
 942     for (DenseSet<Value*>::iterator I = ClearSet.begin(), E = ClearSet.end();
 943          I != E; ++I) {
 944       // If a value was marked overdefined in OldSucc, and is here too...
 945       DenseSet<OverDefinedPairTy>::iterator OI =
 946         OverDefinedCache.find(std::make_pair(ToUpdate, *I));
 947       if (OI == OverDefinedCache.end()) continue;
 948
 949       // Remove it from the caches.
 950       ValueCacheEntryTy &Entry = ValueCache[LVIValueHandle(*I, this)];
 951       ValueCacheEntryTy::iterator CI = Entry.find(ToUpdate);
 952
 953       assert(CI != Entry.end() && "Couldn't find entry to update?");
 954       Entry.erase(CI);
 955       OverDefinedCache.erase(OI);
 956
 957       // If we removed anything, then we potentially need to update
 958       // blocks successors too.
 959       changed = true;
 960     }
 961
 962     if (!changed) continue;
 963
 964     worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
 965   }
 966 }
 967
 968 //===----------------------------------------------------------------------===//
 969 //                            LazyValueInfo Impl
 970 //===----------------------------------------------------------------------===//
 971
 972 /// getCache - This lazily constructs the LazyValueInfoCache.
 973 static LazyValueInfoCache &getCache(void *&PImpl) {
 974   if (!PImpl)
 975     PImpl = new LazyValueInfoCache();
 976   return *static_cast<LazyValueInfoCache*>(PImpl);
 977 }
 978
 979 bool LazyValueInfo::runOnFunction(Function &F) {
 980   if (PImpl)
 981     getCache(PImpl).clear();
 982
 983   TD = getAnalysisIfAvailable<TargetData>();
 984   TLI = &getAnalysis<TargetLibraryInfo>();
 985
 986   // Fully lazy.
 987   return false;
 988 }
 989
 990 void LazyValueInfo::getAnalysisUsage(AnalysisUsage &AU) const {
 991   AU.setPreservesAll();
 992   AU.addRequired<TargetLibraryInfo>();
 993 }
 994
 995 void LazyValueInfo::releaseMemory() {
 996   // If the cache was allocated, free it.
 997   if (PImpl) {
 998     delete &getCache(PImpl);
 999     PImpl = 0;
1000   }
1001 }
1002
1003 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB) {
1004   LVILatticeVal Result = getCache(PImpl).getValueInBlock(V, BB);
1005
1006   if (Result.isConstant())
1007     return Result.getConstant();
1008   if (Result.isConstantRange()) {
1009     ConstantRange CR = Result.getConstantRange();
1010     if (const APInt *SingleVal = CR.getSingleElement())
1011       return ConstantInt::get(V->getContext(), *SingleVal);
1012   }
1013   return 0;
1014 }
1015
1016 /// getConstantOnEdge - Determine whether the specified value is known to be a
1017 /// constant on the specified edge.  Return null if not.
1018 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
1019                                            BasicBlock *ToBB) {
1020   LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB);
1021
1022   if (Result.isConstant())
1023     return Result.getConstant();
1024   if (Result.isConstantRange()) {
1025     ConstantRange CR = Result.getConstantRange();
1026     if (const APInt *SingleVal = CR.getSingleElement())
1027       return ConstantInt::get(V->getContext(), *SingleVal);
1028   }
1029   return 0;
1030 }
1031
1032 /// getPredicateOnEdge - Determine whether the specified value comparison
1033 /// with a constant is known to be true or false on the specified CFG edge.
1034 /// Pred is a CmpInst predicate.
1035 LazyValueInfo::Tristate
1036 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
1037                                   BasicBlock *FromBB, BasicBlock *ToBB) {
1038   LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB);
1039
1040   // If we know the value is a constant, evaluate the conditional.
1041   Constant *Res = 0;
1042   if (Result.isConstant()) {
1043     Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, TD,
1044                                           TLI);
1045     if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
1046       return ResCI->isZero() ? False : True;
1047     return Unknown;
1048   }
1049
1050   if (Result.isConstantRange()) {
1051     ConstantInt *CI = dyn_cast<ConstantInt>(C);
1052     if (!CI) return Unknown;
1053
1054     ConstantRange CR = Result.getConstantRange();
1055     if (Pred == ICmpInst::ICMP_EQ) {
1056       if (!CR.contains(CI->getValue()))
1057         return False;
1058
1059       if (CR.isSingleElement() && CR.contains(CI->getValue()))
1060         return True;
1061     } else if (Pred == ICmpInst::ICMP_NE) {
1062       if (!CR.contains(CI->getValue()))
1063         return True;
1064
1065       if (CR.isSingleElement() && CR.contains(CI->getValue()))
1066         return False;
1067     }
1068
1069     // Handle more complex predicates.
1070     ConstantRange TrueValues =
1071         ICmpInst::makeConstantRange((ICmpInst::Predicate)Pred, CI->getValue());
1072     if (TrueValues.contains(CR))
1073       return True;
1074     if (TrueValues.inverse().contains(CR))
1075       return False;
1076     return Unknown;
1077   }
1078
1079   if (Result.isNotConstant()) {
1080     // If this is an equality comparison, we can try to fold it knowing that
1081     // "V != C1".
1082     if (Pred == ICmpInst::ICMP_EQ) {
1083       // !C1 == C -> false iff C1 == C.
1084       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1085                                             Result.getNotConstant(), C, TD,
1086                                             TLI);
1087       if (Res->isNullValue())
1088         return False;
1089     } else if (Pred == ICmpInst::ICMP_NE) {
1090       // !C1 != C -> true iff C1 == C.
1091       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1092                                             Result.getNotConstant(), C, TD,
1093                                             TLI);
1094       if (Res->isNullValue())
1095         return True;
1096     }
1097     return Unknown;
1098   }
1099
1100   return Unknown;
1101 }
1102
1103 void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1104                                BasicBlock *NewSucc) {
1105   if (PImpl) getCache(PImpl).threadEdge(PredBB, OldSucc, NewSucc);
1106 }
1107
1108 void LazyValueInfo::eraseBlock(BasicBlock *BB) {
1109   if (PImpl) getCache(PImpl).eraseBlock(BB);
1110 }