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/Constants.h"
  18 #include "llvm/Instructions.h"
  19 #include "llvm/Analysis/ConstantFolding.h"
  20 #include "llvm/Target/TargetData.h"
  21 #include "llvm/Support/CFG.h"
  22 #include "llvm/Support/Debug.h"
  23 #include "llvm/Support/raw_ostream.h"
  24 #include "llvm/ADT/DenseMap.h"
  25 #include "llvm/ADT/DenseSet.h"
  26 #include "llvm/ADT/PointerIntPair.h"
  27 #include "llvm/ADT/STLExtras.h"
  28 using namespace llvm;
  29
  30 char LazyValueInfo::ID = 0;
  31 INITIALIZE_PASS(LazyValueInfo, "lazy-value-info",
  32                 "Lazy Value Information Analysis", false, true);
  33
  34 namespace llvm {
  35   FunctionPass *createLazyValueInfoPass() { return new LazyValueInfo(); }
  36 }
  37
  38
  39 //===----------------------------------------------------------------------===//
  40 //                               LVILatticeVal
  41 //===----------------------------------------------------------------------===//
  42
  43 /// LVILatticeVal - This is the information tracked by LazyValueInfo for each
  44 /// value.
  45 ///
  46 /// FIXME: This is basically just for bringup, this can be made a lot more rich
  47 /// in the future.
  48 ///
  49 namespace {
  50 class LVILatticeVal {
  51   enum LatticeValueTy {
  52     /// undefined - This LLVM Value has no known value yet.
  53     undefined,
  54     /// constant - This LLVM Value has a specific constant value.
  55     constant,
  56
  57     /// notconstant - This LLVM value is known to not have the specified value.
  58     notconstant,
  59
  60     /// overdefined - This instruction is not known to be constant, and we know
  61     /// it has a value.
  62     overdefined
  63   };
  64
  65   /// Val: This stores the current lattice value along with the Constant* for
  66   /// the constant if this is a 'constant' or 'notconstant' value.
  67   PointerIntPair<Constant *, 2, LatticeValueTy> Val;
  68
  69 public:
  70   LVILatticeVal() : Val(0, undefined) {}
  71
  72   static LVILatticeVal get(Constant *C) {
  73     LVILatticeVal Res;
  74     Res.markConstant(C);
  75     return Res;
  76   }
  77   static LVILatticeVal getNot(Constant *C) {
  78     LVILatticeVal Res;
  79     Res.markNotConstant(C);
  80     return Res;
  81   }
  82
  83   bool isUndefined() const   { return Val.getInt() == undefined; }
  84   bool isConstant() const    { return Val.getInt() == constant; }
  85   bool isNotConstant() const { return Val.getInt() == notconstant; }
  86   bool isOverdefined() const { return Val.getInt() == overdefined; }
  87
  88   Constant *getConstant() const {
  89     assert(isConstant() && "Cannot get the constant of a non-constant!");
  90     return Val.getPointer();
  91   }
  92
  93   Constant *getNotConstant() const {
  94     assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
  95     return Val.getPointer();
  96   }
  97
  98   /// markOverdefined - Return true if this is a change in status.
  99   bool markOverdefined() {
 100     if (isOverdefined())
 101       return false;
 102     Val.setInt(overdefined);
 103     return true;
 104   }
 105
 106   /// markConstant - Return true if this is a change in status.
 107   bool markConstant(Constant *V) {
 108     if (isConstant()) {
 109       assert(getConstant() == V && "Marking constant with different value");
 110       return false;
 111     }
 112
 113     assert(isUndefined());
 114     Val.setInt(constant);
 115     assert(V && "Marking constant with NULL");
 116     Val.setPointer(V);
 117     return true;
 118   }
 119
 120   /// markNotConstant - Return true if this is a change in status.
 121   bool markNotConstant(Constant *V) {
 122     if (isNotConstant()) {
 123       assert(getNotConstant() == V && "Marking !constant with different value");
 124       return false;
 125     }
 126
 127     if (isConstant())
 128       assert(getConstant() != V && "Marking not constant with different value");
 129     else
 130       assert(isUndefined());
 131
 132     Val.setInt(notconstant);
 133     assert(V && "Marking constant with NULL");
 134     Val.setPointer(V);
 135     return true;
 136   }
 137
 138   /// mergeIn - Merge the specified lattice value into this one, updating this
 139   /// one and returning true if anything changed.
 140   bool mergeIn(const LVILatticeVal &RHS) {
 141     if (RHS.isUndefined() || isOverdefined()) return false;
 142     if (RHS.isOverdefined()) return markOverdefined();
 143
 144     if (RHS.isNotConstant()) {
 145       if (isNotConstant()) {
 146         if (getNotConstant() != RHS.getNotConstant() ||
 147             isa<ConstantExpr>(getNotConstant()) ||
 148             isa<ConstantExpr>(RHS.getNotConstant()))
 149           return markOverdefined();
 150         return false;
 151       }
 152       if (isConstant()) {
 153         if (getConstant() == RHS.getNotConstant() ||
 154             isa<ConstantExpr>(RHS.getNotConstant()) ||
 155             isa<ConstantExpr>(getConstant()))
 156           return markOverdefined();
 157         return markNotConstant(RHS.getNotConstant());
 158       }
 159
 160       assert(isUndefined() && "Unexpected lattice");
 161       return markNotConstant(RHS.getNotConstant());
 162     }
 163
 164     // RHS must be a constant, we must be undef, constant, or notconstant.
 165     if (isUndefined())
 166       return markConstant(RHS.getConstant());
 167
 168     if (isConstant()) {
 169       if (getConstant() != RHS.getConstant())
 170         return markOverdefined();
 171       return false;
 172     }
 173
 174     // If we are known "!=4" and RHS is "==5", stay at "!=4".
 175     if (getNotConstant() == RHS.getConstant() ||
 176         isa<ConstantExpr>(getNotConstant()) ||
 177         isa<ConstantExpr>(RHS.getConstant()))
 178       return markOverdefined();
 179     return false;
 180   }
 181
 182 };
 183
 184 } // end anonymous namespace.
 185
 186 namespace llvm {
 187 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) {
 188   if (Val.isUndefined())
 189     return OS << "undefined";
 190   if (Val.isOverdefined())
 191     return OS << "overdefined";
 192
 193   if (Val.isNotConstant())
 194     return OS << "notconstant<" << *Val.getNotConstant() << '>';
 195   return OS << "constant<" << *Val.getConstant() << '>';
 196 }
 197 }
 198
 199 //===----------------------------------------------------------------------===//
 200 //                          LazyValueInfoCache Decl
 201 //===----------------------------------------------------------------------===//
 202
 203 namespace {
 204   /// LazyValueInfoCache - This is the cache kept by LazyValueInfo which
 205   /// maintains information about queries across the clients' queries.
 206   class LazyValueInfoCache {
 207   public:
 208     /// BlockCacheEntryTy - This is a computed lattice value at the end of the
 209     /// specified basic block for a Value* that depends on context.
 210     typedef std::pair<BasicBlock*, LVILatticeVal> BlockCacheEntryTy;
 211
 212     /// ValueCacheEntryTy - This is all of the cached block information for
 213     /// exactly one Value*.  The entries are sorted by the BasicBlock* of the
 214     /// entries, allowing us to do a lookup with a binary search.
 215     typedef DenseMap<BasicBlock*, LVILatticeVal> ValueCacheEntryTy;
 216
 217   private:
 218     /// ValueCache - This is all of the cached information for all values,
 219     /// mapped from Value* to key information.
 220     DenseMap<Value*, ValueCacheEntryTy> ValueCache;
 221
 222     /// OverDefinedCache - This tracks, on a per-block basis, the set of
 223     /// values that are over-defined at the end of that block.  This is required
 224     /// for cache updating.
 225     DenseSet<std::pair<BasicBlock*, Value*> > OverDefinedCache;
 226   public:
 227
 228     /// getValueInBlock - This is the query interface to determine the lattice
 229     /// value for the specified Value* at the end of the specified block.
 230     LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB);
 231
 232     /// getValueOnEdge - This is the query interface to determine the lattice
 233     /// value for the specified Value* that is true on the specified edge.
 234     LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB);
 235
 236     /// threadEdge - This is the update interface to inform the cache that an
 237     /// edge from PredBB to OldSucc has been threaded to be from PredBB to
 238     /// NewSucc.
 239     void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
 240   };
 241 } // end anonymous namespace
 242
 243 namespace {
 244   struct BlockCacheEntryComparator {
 245     static int Compare(const void *LHSv, const void *RHSv) {
 246       const LazyValueInfoCache::BlockCacheEntryTy *LHS =
 247         static_cast<const LazyValueInfoCache::BlockCacheEntryTy *>(LHSv);
 248       const LazyValueInfoCache::BlockCacheEntryTy *RHS =
 249         static_cast<const LazyValueInfoCache::BlockCacheEntryTy *>(RHSv);
 250       if (LHS->first < RHS->first)
 251         return -1;
 252       if (LHS->first > RHS->first)
 253         return 1;
 254       return 0;
 255     }
 256
 257     bool operator()(const LazyValueInfoCache::BlockCacheEntryTy &LHS,
 258                     const LazyValueInfoCache::BlockCacheEntryTy &RHS) const {
 259       return LHS.first < RHS.first;
 260     }
 261   };
 262 }
 263
 264 //===----------------------------------------------------------------------===//
 265 //                              LVIQuery Impl
 266 //===----------------------------------------------------------------------===//
 267
 268 namespace {
 269   /// LVIQuery - This is a transient object that exists while a query is
 270   /// being performed.
 271   ///
 272   /// TODO: Reuse LVIQuery instead of recreating it for every query, this avoids
 273   /// reallocation of the densemap on every query.
 274   class LVIQuery {
 275     typedef LazyValueInfoCache::BlockCacheEntryTy BlockCacheEntryTy;
 276     typedef LazyValueInfoCache::ValueCacheEntryTy ValueCacheEntryTy;
 277
 278     /// This is the current value being queried for.
 279     Value *Val;
 280
 281     /// This is all of the cached information about this value.
 282     ValueCacheEntryTy &Cache;
 283
 284     /// This tracks, for each block, what values are overdefined.
 285     DenseSet<std::pair<BasicBlock*, Value*> > &OverDefinedCache;
 286
 287     ///  NewBlocks - This is a mapping of the new BasicBlocks which have been
 288     /// added to cache but that are not in sorted order.
 289     DenseSet<BasicBlock*> NewBlockInfo;
 290   public:
 291
 292     LVIQuery(Value *V, ValueCacheEntryTy &VC,
 293              DenseSet<std::pair<BasicBlock*, Value*> > &ODC)
 294       : Val(V), Cache(VC), OverDefinedCache(ODC) {
 295     }
 296
 297     ~LVIQuery() {
 298       // When the query is done, insert the newly discovered facts into the
 299       // cache in sorted order.
 300       if (NewBlockInfo.empty()) return;
 301
 302       for (DenseSet<BasicBlock*>::iterator I = NewBlockInfo.begin(),
 303            E = NewBlockInfo.end(); I != E; ++I) {
 304         if (Cache[*I].isOverdefined())
 305           OverDefinedCache.insert(std::make_pair(*I, Val));
 306       }
 307     }
 308
 309     LVILatticeVal getBlockValue(BasicBlock *BB);
 310     LVILatticeVal getEdgeValue(BasicBlock *FromBB, BasicBlock *ToBB);
 311
 312   private:
 313     LVILatticeVal &getCachedEntryForBlock(BasicBlock *BB);
 314   };
 315 } // end anonymous namespace
 316
 317 /// getCachedEntryForBlock - See if we already have a value for this block.  If
 318 /// so, return it, otherwise create a new entry in the Cache map to use.
 319 LVILatticeVal &LVIQuery::getCachedEntryForBlock(BasicBlock *BB) {
 320   NewBlockInfo.insert(BB);
 321   return Cache[BB];
 322 }
 323
 324 LVILatticeVal LVIQuery::getBlockValue(BasicBlock *BB) {
 325   // See if we already have a value for this block.
 326   LVILatticeVal &BBLV = getCachedEntryForBlock(BB);
 327
 328   // If we've already computed this block's value, return it.
 329   if (!BBLV.isUndefined()) {
 330     DEBUG(dbgs() << "  reuse BB '" << BB->getName() << "' val=" << BBLV <<'\n');
 331     return BBLV;
 332   }
 333
 334   // Otherwise, this is the first time we're seeing this block.  Reset the
 335   // lattice value to overdefined, so that cycles will terminate and be
 336   // conservatively correct.
 337   BBLV.markOverdefined();
 338
 339   // If V is live into BB, see if our predecessors know anything about it.
 340   Instruction *BBI = dyn_cast<Instruction>(Val);
 341   if (BBI == 0 || BBI->getParent() != BB) {
 342     LVILatticeVal Result;  // Start Undefined.
 343     unsigned NumPreds = 0;
 344
 345     // Loop over all of our predecessors, merging what we know from them into
 346     // result.
 347     for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
 348       Result.mergeIn(getEdgeValue(*PI, BB));
 349
 350       // If we hit overdefined, exit early.  The BlockVals entry is already set
 351       // to overdefined.
 352       if (Result.isOverdefined()) {
 353         DEBUG(dbgs() << " compute BB '" << BB->getName()
 354                      << "' - overdefined because of pred.\n");
 355         return Result;
 356       }
 357       ++NumPreds;
 358     }
 359
 360     // If this is the entry block, we must be asking about an argument.  The
 361     // value is overdefined.
 362     if (NumPreds == 0 && BB == &BB->getParent()->front()) {
 363       assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
 364       Result.markOverdefined();
 365       return Result;
 366     }
 367
 368     // Return the merged value, which is more precise than 'overdefined'.
 369     assert(!Result.isOverdefined());
 370     return getCachedEntryForBlock(BB) = Result;
 371   }
 372
 373   // If this value is defined by an instruction in this block, we have to
 374   // process it here somehow or return overdefined.
 375   if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
 376     (void)PN;
 377     // TODO: PHI Translation in preds.
 378   } else {
 379
 380   }
 381
 382   DEBUG(dbgs() << " compute BB '" << BB->getName()
 383                << "' - overdefined because inst def found.\n");
 384
 385   LVILatticeVal Result;
 386   Result.markOverdefined();
 387   return getCachedEntryForBlock(BB) = Result;
 388 }
 389
 390
 391 /// getEdgeValue - This method attempts to infer more complex
 392 LVILatticeVal LVIQuery::getEdgeValue(BasicBlock *BBFrom, BasicBlock *BBTo) {
 393   // TODO: Handle more complex conditionals.  If (v == 0 || v2 < 1) is false, we
 394   // know that v != 0.
 395   if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
 396     // If this is a conditional branch and only one successor goes to BBTo, then
 397     // we maybe able to infer something from the condition.
 398     if (BI->isConditional() &&
 399         BI->getSuccessor(0) != BI->getSuccessor(1)) {
 400       bool isTrueDest = BI->getSuccessor(0) == BBTo;
 401       assert(BI->getSuccessor(!isTrueDest) == BBTo &&
 402              "BBTo isn't a successor of BBFrom");
 403
 404       // If V is the condition of the branch itself, then we know exactly what
 405       // it is.
 406       if (BI->getCondition() == Val)
 407         return LVILatticeVal::get(ConstantInt::get(
 408                                Type::getInt1Ty(Val->getContext()), isTrueDest));
 409
 410       // If the condition of the branch is an equality comparison, we may be
 411       // able to infer the value.
 412       if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition()))
 413         if (ICI->isEquality() && ICI->getOperand(0) == Val &&
 414             isa<Constant>(ICI->getOperand(1))) {
 415           // We know that V has the RHS constant if this is a true SETEQ or
 416           // false SETNE.
 417           if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
 418             return LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
 419           return LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1)));
 420         }
 421     }
 422   }
 423
 424   // If the edge was formed by a switch on the value, then we may know exactly
 425   // what it is.
 426   if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
 427     // If BBTo is the default destination of the switch, we don't know anything.
 428     // Given a more powerful range analysis we could know stuff.
 429     if (SI->getCondition() == Val && SI->getDefaultDest() != BBTo) {
 430       // We only know something if there is exactly one value that goes from
 431       // BBFrom to BBTo.
 432       unsigned NumEdges = 0;
 433       ConstantInt *EdgeVal = 0;
 434       for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) {
 435         if (SI->getSuccessor(i) != BBTo) continue;
 436         if (NumEdges++) break;
 437         EdgeVal = SI->getCaseValue(i);
 438       }
 439       assert(EdgeVal && "Missing successor?");
 440       if (NumEdges == 1)
 441         return LVILatticeVal::get(EdgeVal);
 442     }
 443   }
 444
 445   // Otherwise see if the value is known in the block.
 446   return getBlockValue(BBFrom);
 447 }
 448
 449
 450 //===----------------------------------------------------------------------===//
 451 //                         LazyValueInfoCache Impl
 452 //===----------------------------------------------------------------------===//
 453
 454 LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB) {
 455   // If already a constant, there is nothing to compute.
 456   if (Constant *VC = dyn_cast<Constant>(V))
 457     return LVILatticeVal::get(VC);
 458
 459   DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
 460         << BB->getName() << "'\n");
 461
 462   LVILatticeVal Result = LVIQuery(V, ValueCache[V],
 463                                   OverDefinedCache).getBlockValue(BB);
 464
 465   DEBUG(dbgs() << "  Result = " << Result << "\n");
 466   return Result;
 467 }
 468
 469 LVILatticeVal LazyValueInfoCache::
 470 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB) {
 471   // If already a constant, there is nothing to compute.
 472   if (Constant *VC = dyn_cast<Constant>(V))
 473     return LVILatticeVal::get(VC);
 474
 475   DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
 476         << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
 477
 478   LVILatticeVal Result =
 479     LVIQuery(V, ValueCache[V],
 480              OverDefinedCache).getEdgeValue(FromBB, ToBB);
 481
 482   DEBUG(dbgs() << "  Result = " << Result << "\n");
 483
 484   return Result;
 485 }
 486
 487 void LazyValueInfoCache::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
 488                                     BasicBlock *NewSucc) {
 489   // When an edge in the graph has been threaded, values that we could not
 490   // determine a value for before (i.e. were marked overdefined) may be possible
 491   // to solve now.  We do NOT try to proactively update these values.  Instead,
 492   // we clear their entries from the cache, and allow lazy updating to recompute
 493   // them when needed.
 494
 495   // The updating process is fairly simple: we need to dropped cached info
 496   // for all values that were marked overdefined in OldSucc, and for those same
 497   // values in any successor of OldSucc (except NewSucc) in which they were
 498   // also marked overdefined.
 499   std::vector<BasicBlock*> worklist;
 500   worklist.push_back(OldSucc);
 501
 502   DenseSet<Value*> ClearSet;
 503   for (DenseSet<std::pair<BasicBlock*, Value*> >::iterator
 504        I = OverDefinedCache.begin(), E = OverDefinedCache.end(); I != E; ++I) {
 505     if (I->first == OldSucc)
 506       ClearSet.insert(I->second);
 507   }
 508
 509   // Use a worklist to perform a depth-first search of OldSucc's successors.
 510   // NOTE: We do not need a visited list since any blocks we have already
 511   // visited will have had their overdefined markers cleared already, and we
 512   // thus won't loop to their successors.
 513   while (!worklist.empty()) {
 514     BasicBlock *ToUpdate = worklist.back();
 515     worklist.pop_back();
 516
 517     // Skip blocks only accessible through NewSucc.
 518     if (ToUpdate == NewSucc) continue;
 519
 520     bool changed = false;
 521     for (DenseSet<Value*>::iterator I = ClearSet.begin(),E = ClearSet.end();
 522          I != E; ++I) {
 523       // If a value was marked overdefined in OldSucc, and is here too...
 524       DenseSet<std::pair<BasicBlock*, Value*> >::iterator OI =
 525         OverDefinedCache.find(std::make_pair(ToUpdate, *I));
 526       if (OI == OverDefinedCache.end()) continue;
 527
 528       // Remove it from the caches.
 529       ValueCacheEntryTy &Entry = ValueCache[*I];
 530       ValueCacheEntryTy::iterator CI = Entry.find(ToUpdate);
 531
 532       assert(CI != Entry.end() && "Couldn't find entry to update?");
 533       Entry.erase(CI);
 534       OverDefinedCache.erase(OI);
 535
 536       // If we removed anything, then we potentially need to update
 537       // blocks successors too.
 538       changed = true;
 539     }
 540
 541     if (!changed) continue;
 542
 543     worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
 544   }
 545 }
 546
 547 //===----------------------------------------------------------------------===//
 548 //                            LazyValueInfo Impl
 549 //===----------------------------------------------------------------------===//
 550
 551 bool LazyValueInfo::runOnFunction(Function &F) {
 552   TD = getAnalysisIfAvailable<TargetData>();
 553   // Fully lazy.
 554   return false;
 555 }
 556
 557 /// getCache - This lazily constructs the LazyValueInfoCache.
 558 static LazyValueInfoCache &getCache(void *&PImpl) {
 559   if (!PImpl)
 560     PImpl = new LazyValueInfoCache();
 561   return *static_cast<LazyValueInfoCache*>(PImpl);
 562 }
 563
 564 void LazyValueInfo::releaseMemory() {
 565   // If the cache was allocated, free it.
 566   if (PImpl) {
 567     delete &getCache(PImpl);
 568     PImpl = 0;
 569   }
 570 }
 571
 572 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB) {
 573   LVILatticeVal Result = getCache(PImpl).getValueInBlock(V, BB);
 574
 575   if (Result.isConstant())
 576     return Result.getConstant();
 577   return 0;
 578 }
 579
 580 /// getConstantOnEdge - Determine whether the specified value is known to be a
 581 /// constant on the specified edge.  Return null if not.
 582 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
 583                                            BasicBlock *ToBB) {
 584   LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB);
 585
 586   if (Result.isConstant())
 587     return Result.getConstant();
 588   return 0;
 589 }
 590
 591 /// getPredicateOnEdge - Determine whether the specified value comparison
 592 /// with a constant is known to be true or false on the specified CFG edge.
 593 /// Pred is a CmpInst predicate.
 594 LazyValueInfo::Tristate
 595 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
 596                                   BasicBlock *FromBB, BasicBlock *ToBB) {
 597   LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB);
 598
 599   // If we know the value is a constant, evaluate the conditional.
 600   Constant *Res = 0;
 601   if (Result.isConstant()) {
 602     Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, TD);
 603     if (ConstantInt *ResCI = dyn_cast_or_null<ConstantInt>(Res))
 604       return ResCI->isZero() ? False : True;
 605     return Unknown;
 606   }
 607
 608   if (Result.isNotConstant()) {
 609     // If this is an equality comparison, we can try to fold it knowing that
 610     // "V != C1".
 611     if (Pred == ICmpInst::ICMP_EQ) {
 612       // !C1 == C -> false iff C1 == C.
 613       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
 614                                             Result.getNotConstant(), C, TD);
 615       if (Res->isNullValue())
 616         return False;
 617     } else if (Pred == ICmpInst::ICMP_NE) {
 618       // !C1 != C -> true iff C1 == C.
 619       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
 620                                             Result.getNotConstant(), C, TD);
 621       if (Res->isNullValue())
 622         return True;
 623     }
 624     return Unknown;
 625   }
 626
 627   return Unknown;
 628 }
 629
 630 void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
 631                                BasicBlock* NewSucc) {
 632   getCache(PImpl).threadEdge(PredBB, OldSucc, NewSucc);
 633 }