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   private:
 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     /// ValueCache - This is all of the cached information for all values,
 218     /// mapped from Value* to key information.
 219     DenseMap<Value*, ValueCacheEntryTy> ValueCache;
 220
 221     /// OverDefinedCache - This tracks, on a per-block basis, the set of
 222     /// values that are over-defined at the end of that block.  This is required
 223     /// for cache updating.
 224     DenseSet<std::pair<BasicBlock*, Value*> > OverDefinedCache;
 225
 226     LVILatticeVal getBlockValue(ValueCacheEntryTy &Cache, BasicBlock *BB);
 227     LVILatticeVal getEdgeValue(ValueCacheEntryTy &Cache,
 228                                BasicBlock *Pred, BasicBlock *Succ);
 229     LVILatticeVal &getCachedEntryForBlock(ValueCacheEntryTy &Cache,
 230                                           BasicBlock *BB);
 231
 232     /************* Begin Per-Query State *************/
 233     /// This is the current value being queried for.
 234     Value *Val;
 235
 236     /// This is all of the cached information about this value.
 237     //ValueCacheEntryTy *Cache;
 238
 239     ///  NewBlocks - This is a mapping of the new BasicBlocks which have been
 240     /// added to cache but that are not in sorted order.
 241     DenseSet<BasicBlock*> NewBlockInfo;
 242
 243     /// QuerySetup - An RAII helper to construct and tear-down per-query
 244     /// temporary state.
 245     struct QuerySetup {
 246       LazyValueInfoCache &Owner;
 247       QuerySetup(LazyValueInfoCache &O, Value* Val) : Owner(O) {
 248         assert(!Owner.Val && "Per-query info not cleared?");
 249         Owner.Val = Val;
 250         assert(Owner.NewBlockInfo.empty() && "Leaked block info!");
 251       }
 252
 253       ~QuerySetup() {
 254         // When the query is done, insert the newly discovered facts into the
 255         // cache in sorted order.
 256         LazyValueInfoCache::ValueCacheEntryTy Cache =
 257           Owner.ValueCache[Owner.Val];
 258         for (DenseSet<BasicBlock*>::iterator I = Owner.NewBlockInfo.begin(),
 259              E = Owner.NewBlockInfo.end(); I != E; ++I) {
 260           if (Cache[*I].isOverdefined())
 261             Owner.OverDefinedCache.insert(std::make_pair(*I, Owner.Val));
 262         }
 263
 264         // Reset Per-Query State
 265         Owner.Val = 0;
 266         Owner.NewBlockInfo.clear();
 267       }
 268     };
 269     /************* End Per-Query State *************/
 270
 271   public:
 272     LazyValueInfoCache() : Val(0) { }
 273
 274     /// getValueInBlock - This is the query interface to determine the lattice
 275     /// value for the specified Value* at the end of the specified block.
 276     LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB);
 277
 278     /// getValueOnEdge - This is the query interface to determine the lattice
 279     /// value for the specified Value* that is true on the specified edge.
 280     LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB);
 281
 282     /// threadEdge - This is the update interface to inform the cache that an
 283     /// edge from PredBB to OldSucc has been threaded to be from PredBB to
 284     /// NewSucc.
 285     void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
 286   };
 287 } // end anonymous namespace
 288
 289
 290 /// getCachedEntryForBlock - See if we already have a value for this block.  If
 291 /// so, return it, otherwise create a new entry in the Cache map to use.
 292 LVILatticeVal&
 293 LazyValueInfoCache::getCachedEntryForBlock(ValueCacheEntryTy &Cache,
 294                                            BasicBlock *BB) {
 295   NewBlockInfo.insert(BB);
 296   return Cache[BB];
 297 }
 298
 299 LVILatticeVal
 300 LazyValueInfoCache::getBlockValue(ValueCacheEntryTy &Cache, BasicBlock *BB) {
 301   // See if we already have a value for this block.
 302   LVILatticeVal &BBLV = getCachedEntryForBlock(Cache, BB);
 303
 304   // If we've already computed this block's value, return it.
 305   if (!BBLV.isUndefined()) {
 306     DEBUG(dbgs() << "  reuse BB '" << BB->getName() << "' val=" << BBLV <<'\n');
 307     return BBLV;
 308   }
 309
 310   // Otherwise, this is the first time we're seeing this block.  Reset the
 311   // lattice value to overdefined, so that cycles will terminate and be
 312   // conservatively correct.
 313   BBLV.markOverdefined();
 314
 315   // If V is live into BB, see if our predecessors know anything about it.
 316   Instruction *BBI = dyn_cast<Instruction>(Val);
 317   if (BBI == 0 || BBI->getParent() != BB) {
 318     LVILatticeVal Result;  // Start Undefined.
 319     unsigned NumPreds = 0;
 320
 321     // Loop over all of our predecessors, merging what we know from them into
 322     // result.
 323     for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
 324       Result.mergeIn(getEdgeValue(Cache, *PI, BB));
 325
 326       // If we hit overdefined, exit early.  The BlockVals entry is already set
 327       // to overdefined.
 328       if (Result.isOverdefined()) {
 329         DEBUG(dbgs() << " compute BB '" << BB->getName()
 330                      << "' - overdefined because of pred.\n");
 331         return Result;
 332       }
 333       ++NumPreds;
 334     }
 335
 336     // If this is the entry block, we must be asking about an argument.  The
 337     // value is overdefined.
 338     if (NumPreds == 0 && BB == &BB->getParent()->front()) {
 339       assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
 340       Result.markOverdefined();
 341       return Result;
 342     }
 343
 344     // Return the merged value, which is more precise than 'overdefined'.
 345     assert(!Result.isOverdefined());
 346     return getCachedEntryForBlock(Cache, BB) = Result;
 347   }
 348
 349   // If this value is defined by an instruction in this block, we have to
 350   // process it here somehow or return overdefined.
 351   if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
 352     (void)PN;
 353     // TODO: PHI Translation in preds.
 354   } else {
 355
 356   }
 357
 358   DEBUG(dbgs() << " compute BB '" << BB->getName()
 359                << "' - overdefined because inst def found.\n");
 360
 361   LVILatticeVal Result;
 362   Result.markOverdefined();
 363   return getCachedEntryForBlock(Cache, BB) = Result;
 364 }
 365
 366
 367 /// getEdgeValue - This method attempts to infer more complex
 368 LVILatticeVal LazyValueInfoCache::getEdgeValue(ValueCacheEntryTy &Cache,
 369                                          BasicBlock *BBFrom, BasicBlock *BBTo) {
 370   // TODO: Handle more complex conditionals.  If (v == 0 || v2 < 1) is false, we
 371   // know that v != 0.
 372   if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
 373     // If this is a conditional branch and only one successor goes to BBTo, then
 374     // we maybe able to infer something from the condition.
 375     if (BI->isConditional() &&
 376         BI->getSuccessor(0) != BI->getSuccessor(1)) {
 377       bool isTrueDest = BI->getSuccessor(0) == BBTo;
 378       assert(BI->getSuccessor(!isTrueDest) == BBTo &&
 379              "BBTo isn't a successor of BBFrom");
 380
 381       // If V is the condition of the branch itself, then we know exactly what
 382       // it is.
 383       if (BI->getCondition() == Val)
 384         return LVILatticeVal::get(ConstantInt::get(
 385                                Type::getInt1Ty(Val->getContext()), isTrueDest));
 386
 387       // If the condition of the branch is an equality comparison, we may be
 388       // able to infer the value.
 389       if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition()))
 390         if (ICI->isEquality() && ICI->getOperand(0) == Val &&
 391             isa<Constant>(ICI->getOperand(1))) {
 392           // We know that V has the RHS constant if this is a true SETEQ or
 393           // false SETNE.
 394           if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
 395             return LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
 396           return LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1)));
 397         }
 398     }
 399   }
 400
 401   // If the edge was formed by a switch on the value, then we may know exactly
 402   // what it is.
 403   if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
 404     // If BBTo is the default destination of the switch, we don't know anything.
 405     // Given a more powerful range analysis we could know stuff.
 406     if (SI->getCondition() == Val && SI->getDefaultDest() != BBTo) {
 407       // We only know something if there is exactly one value that goes from
 408       // BBFrom to BBTo.
 409       unsigned NumEdges = 0;
 410       ConstantInt *EdgeVal = 0;
 411       for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) {
 412         if (SI->getSuccessor(i) != BBTo) continue;
 413         if (NumEdges++) break;
 414         EdgeVal = SI->getCaseValue(i);
 415       }
 416       assert(EdgeVal && "Missing successor?");
 417       if (NumEdges == 1)
 418         return LVILatticeVal::get(EdgeVal);
 419     }
 420   }
 421
 422   // Otherwise see if the value is known in the block.
 423   return getBlockValue(Cache, BBFrom);
 424 }
 425
 426 LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB) {
 427   // If already a constant, there is nothing to compute.
 428   if (Constant *VC = dyn_cast<Constant>(V))
 429     return LVILatticeVal::get(VC);
 430
 431   DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
 432         << BB->getName() << "'\n");
 433
 434   QuerySetup QS(*this, V);
 435   ValueCacheEntryTy &Cache = ValueCache[V];
 436   LVILatticeVal Result = getBlockValue(Cache, BB);
 437
 438   DEBUG(dbgs() << "  Result = " << Result << "\n");
 439   return Result;
 440 }
 441
 442 LVILatticeVal LazyValueInfoCache::
 443 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB) {
 444   // If already a constant, there is nothing to compute.
 445   if (Constant *VC = dyn_cast<Constant>(V))
 446     return LVILatticeVal::get(VC);
 447
 448   DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
 449         << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
 450
 451   QuerySetup QS(*this, V);
 452   ValueCacheEntryTy &Cache = ValueCache[V];
 453   LVILatticeVal Result = getEdgeValue(Cache, FromBB, ToBB);
 454
 455   DEBUG(dbgs() << "  Result = " << Result << "\n");
 456
 457   return Result;
 458 }
 459
 460 void LazyValueInfoCache::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
 461                                     BasicBlock *NewSucc) {
 462   // When an edge in the graph has been threaded, values that we could not
 463   // determine a value for before (i.e. were marked overdefined) may be possible
 464   // to solve now.  We do NOT try to proactively update these values.  Instead,
 465   // we clear their entries from the cache, and allow lazy updating to recompute
 466   // them when needed.
 467
 468   // The updating process is fairly simple: we need to dropped cached info
 469   // for all values that were marked overdefined in OldSucc, and for those same
 470   // values in any successor of OldSucc (except NewSucc) in which they were
 471   // also marked overdefined.
 472   std::vector<BasicBlock*> worklist;
 473   worklist.push_back(OldSucc);
 474
 475   DenseSet<Value*> ClearSet;
 476   for (DenseSet<std::pair<BasicBlock*, Value*> >::iterator
 477        I = OverDefinedCache.begin(), E = OverDefinedCache.end(); I != E; ++I) {
 478     if (I->first == OldSucc)
 479       ClearSet.insert(I->second);
 480   }
 481
 482   // Use a worklist to perform a depth-first search of OldSucc's successors.
 483   // NOTE: We do not need a visited list since any blocks we have already
 484   // visited will have had their overdefined markers cleared already, and we
 485   // thus won't loop to their successors.
 486   while (!worklist.empty()) {
 487     BasicBlock *ToUpdate = worklist.back();
 488     worklist.pop_back();
 489
 490     // Skip blocks only accessible through NewSucc.
 491     if (ToUpdate == NewSucc) continue;
 492
 493     bool changed = false;
 494     for (DenseSet<Value*>::iterator I = ClearSet.begin(),E = ClearSet.end();
 495          I != E; ++I) {
 496       // If a value was marked overdefined in OldSucc, and is here too...
 497       DenseSet<std::pair<BasicBlock*, Value*> >::iterator OI =
 498         OverDefinedCache.find(std::make_pair(ToUpdate, *I));
 499       if (OI == OverDefinedCache.end()) continue;
 500
 501       // Remove it from the caches.
 502       ValueCacheEntryTy &Entry = ValueCache[*I];
 503       ValueCacheEntryTy::iterator CI = Entry.find(ToUpdate);
 504
 505       assert(CI != Entry.end() && "Couldn't find entry to update?");
 506       Entry.erase(CI);
 507       OverDefinedCache.erase(OI);
 508
 509       // If we removed anything, then we potentially need to update
 510       // blocks successors too.
 511       changed = true;
 512     }
 513
 514     if (!changed) continue;
 515
 516     worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
 517   }
 518 }
 519
 520 //===----------------------------------------------------------------------===//
 521 //                            LazyValueInfo Impl
 522 //===----------------------------------------------------------------------===//
 523
 524 bool LazyValueInfo::runOnFunction(Function &F) {
 525   TD = getAnalysisIfAvailable<TargetData>();
 526   // Fully lazy.
 527   return false;
 528 }
 529
 530 /// getCache - This lazily constructs the LazyValueInfoCache.
 531 static LazyValueInfoCache &getCache(void *&PImpl) {
 532   if (!PImpl)
 533     PImpl = new LazyValueInfoCache();
 534   return *static_cast<LazyValueInfoCache*>(PImpl);
 535 }
 536
 537 void LazyValueInfo::releaseMemory() {
 538   // If the cache was allocated, free it.
 539   if (PImpl) {
 540     delete &getCache(PImpl);
 541     PImpl = 0;
 542   }
 543 }
 544
 545 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB) {
 546   LVILatticeVal Result = getCache(PImpl).getValueInBlock(V, BB);
 547
 548   if (Result.isConstant())
 549     return Result.getConstant();
 550   return 0;
 551 }
 552
 553 /// getConstantOnEdge - Determine whether the specified value is known to be a
 554 /// constant on the specified edge.  Return null if not.
 555 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
 556                                            BasicBlock *ToBB) {
 557   LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB);
 558
 559   if (Result.isConstant())
 560     return Result.getConstant();
 561   return 0;
 562 }
 563
 564 /// getPredicateOnEdge - Determine whether the specified value comparison
 565 /// with a constant is known to be true or false on the specified CFG edge.
 566 /// Pred is a CmpInst predicate.
 567 LazyValueInfo::Tristate
 568 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
 569                                   BasicBlock *FromBB, BasicBlock *ToBB) {
 570   LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB);
 571
 572   // If we know the value is a constant, evaluate the conditional.
 573   Constant *Res = 0;
 574   if (Result.isConstant()) {
 575     Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, TD);
 576     if (ConstantInt *ResCI = dyn_cast_or_null<ConstantInt>(Res))
 577       return ResCI->isZero() ? False : True;
 578     return Unknown;
 579   }
 580
 581   if (Result.isNotConstant()) {
 582     // If this is an equality comparison, we can try to fold it knowing that
 583     // "V != C1".
 584     if (Pred == ICmpInst::ICMP_EQ) {
 585       // !C1 == C -> false iff C1 == C.
 586       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
 587                                             Result.getNotConstant(), C, TD);
 588       if (Res->isNullValue())
 589         return False;
 590     } else if (Pred == ICmpInst::ICMP_NE) {
 591       // !C1 != C -> true iff C1 == C.
 592       Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
 593                                             Result.getNotConstant(), C, TD);
 594       if (Res->isNullValue())
 595         return True;
 596     }
 597     return Unknown;
 598   }
 599
 600   return Unknown;
 601 }
 602
 603 void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
 604                                BasicBlock* NewSucc) {
 605   getCache(PImpl).threadEdge(PredBB, OldSucc, NewSucc);
 606 }