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