LazyValueInfo.cpp revision 199481
175115Sfenner//===- LazyValueInfo.cpp - Value constraint analysis ----------------------===// 275115Sfenner// 375115Sfenner// The LLVM Compiler Infrastructure 475115Sfenner// 575115Sfenner// This file is distributed under the University of Illinois Open Source 675115Sfenner// License. See LICENSE.TXT for details. 775115Sfenner// 875115Sfenner//===----------------------------------------------------------------------===// 975115Sfenner// 1075115Sfenner// This file defines the interface for lazy computation of value constraint 1175115Sfenner// information. 1275115Sfenner// 1375115Sfenner//===----------------------------------------------------------------------===// 1475115Sfenner 1575115Sfenner#define DEBUG_TYPE "lazy-value-info" 1675115Sfenner#include "llvm/Analysis/LazyValueInfo.h" 1775115Sfenner#include "llvm/Constants.h" 1875115Sfenner#include "llvm/Instructions.h" 1975115Sfenner#include "llvm/Analysis/ConstantFolding.h" 2075115Sfenner#include "llvm/Target/TargetData.h" 2175115Sfenner#include "llvm/Support/CFG.h" 2275115Sfenner#include "llvm/Support/Debug.h" 2375115Sfenner#include "llvm/Support/raw_ostream.h" 2475115Sfenner#include "llvm/ADT/DenseMap.h" 2575115Sfenner#include "llvm/ADT/PointerIntPair.h" 2675115Sfenner#include "llvm/ADT/STLExtras.h" 2775115Sfennerusing namespace llvm; 28127668Sbms 29190207Srpaulochar LazyValueInfo::ID = 0; 3075115Sfennerstatic RegisterPass<LazyValueInfo> 3175115SfennerX("lazy-value-info", "Lazy Value Information Analysis", false, true); 3275115Sfenner 3375115Sfennernamespace llvm { 3475115Sfenner FunctionPass *createLazyValueInfoPass() { return new LazyValueInfo(); } 3575115Sfenner} 36127668Sbms 3775115Sfenner 3875115Sfenner//===----------------------------------------------------------------------===// 3975115Sfenner// LVILatticeVal 4075115Sfenner//===----------------------------------------------------------------------===// 4175115Sfenner 4275115Sfenner/// LVILatticeVal - This is the information tracked by LazyValueInfo for each 4375115Sfenner/// value. 44146773Ssam/// 4575115Sfenner/// FIXME: This is basically just for bringup, this can be made a lot more rich 46127668Sbms/// in the future. 47127668Sbms/// 48127668Sbmsnamespace { 49127668Sbmsclass LVILatticeVal { 50127668Sbms enum LatticeValueTy { 51127668Sbms /// undefined - This LLVM Value has no known value yet. 52127668Sbms undefined, 53127668Sbms /// constant - This LLVM Value has a specific constant value. 54127668Sbms constant, 55127668Sbms 56127668Sbms /// notconstant - This LLVM value is known to not have the specified value. 57127668Sbms notconstant, 58127668Sbms 59127668Sbms /// overdefined - This instruction is not known to be constant, and we know 60127668Sbms /// it has a value. 61127668Sbms overdefined 62127668Sbms }; 63127668Sbms 64127668Sbms /// Val: This stores the current lattice value along with the Constant* for 65127668Sbms /// the constant if this is a 'constant' or 'notconstant' value. 66127668Sbms PointerIntPair<Constant *, 2, LatticeValueTy> Val; 67127668Sbms 68127668Sbmspublic: 69127668Sbms LVILatticeVal() : Val(0, undefined) {} 70127668Sbms 71127668Sbms static LVILatticeVal get(Constant *C) { 72127668Sbms LVILatticeVal Res; 73127668Sbms Res.markConstant(C); 74127668Sbms return Res; 75127668Sbms } 76127668Sbms static LVILatticeVal getNot(Constant *C) { 77127668Sbms LVILatticeVal Res; 78127668Sbms Res.markNotConstant(C); 79127668Sbms return Res; 80127668Sbms } 81127668Sbms 82127668Sbms bool isUndefined() const { return Val.getInt() == undefined; } 83127668Sbms bool isConstant() const { return Val.getInt() == constant; } 8498524Sfenner bool isNotConstant() const { return Val.getInt() == notconstant; } 8598524Sfenner bool isOverdefined() const { return Val.getInt() == overdefined; } 86127668Sbms 8775115Sfenner Constant *getConstant() const { 8875115Sfenner assert(isConstant() && "Cannot get the constant of a non-constant!"); 89127668Sbms return Val.getPointer(); 9075115Sfenner } 91127668Sbms 92127668Sbms Constant *getNotConstant() const { 9375115Sfenner assert(isNotConstant() && "Cannot get the constant of a non-notconstant!"); 94127668Sbms return Val.getPointer(); 9575115Sfenner } 9675115Sfenner 9775115Sfenner /// markOverdefined - Return true if this is a change in status. 9875115Sfenner bool markOverdefined() { 99127668Sbms if (isOverdefined()) 10075115Sfenner return false; 101127668Sbms Val.setInt(overdefined); 102127668Sbms return true; 103127668Sbms } 104127668Sbms 105127668Sbms /// markConstant - Return true if this is a change in status. 106127668Sbms bool markConstant(Constant *V) { 10775115Sfenner if (isConstant()) { 108127668Sbms assert(getConstant() == V && "Marking constant with different value"); 10975115Sfenner return false; 110127668Sbms } 111127668Sbms 112127668Sbms assert(isUndefined()); 113127668Sbms Val.setInt(constant); 114127668Sbms assert(V && "Marking constant with NULL"); 115127668Sbms Val.setPointer(V); 11675115Sfenner return true; 117127668Sbms } 11898524Sfenner 11975115Sfenner /// markNotConstant - Return true if this is a change in status. 120127668Sbms bool markNotConstant(Constant *V) { 121127668Sbms if (isNotConstant()) { 122127668Sbms assert(getNotConstant() == V && "Marking !constant with different value"); 123127668Sbms return false; 124127668Sbms } 125127668Sbms 126127668Sbms if (isConstant()) 127127668Sbms assert(getConstant() != V && "Marking not constant with different value"); 128127668Sbms else 129127668Sbms assert(isUndefined()); 130127668Sbms 131127668Sbms Val.setInt(notconstant); 132127668Sbms assert(V && "Marking constant with NULL"); 133127668Sbms Val.setPointer(V); 134127668Sbms return true; 135127668Sbms } 13698524Sfenner 137127668Sbms /// mergeIn - Merge the specified lattice value into this one, updating this 138127668Sbms /// one and returning true if anything changed. 139127668Sbms bool mergeIn(const LVILatticeVal &RHS) { 14098524Sfenner if (RHS.isUndefined() || isOverdefined()) return false; 141127668Sbms if (RHS.isOverdefined()) return markOverdefined(); 142127668Sbms 14398524Sfenner if (RHS.isNotConstant()) { 144127668Sbms if (isNotConstant()) { 145127668Sbms if (getNotConstant() != RHS.getNotConstant() || 146127668Sbms isa<ConstantExpr>(getNotConstant()) || 147127668Sbms isa<ConstantExpr>(RHS.getNotConstant())) 14898524Sfenner return markOverdefined(); 149127668Sbms return false; 150127668Sbms } 151127668Sbms if (isConstant()) { 152127668Sbms if (getConstant() == RHS.getNotConstant() || 153127668Sbms isa<ConstantExpr>(RHS.getNotConstant()) || 154127668Sbms isa<ConstantExpr>(getConstant())) 155127668Sbms return markOverdefined(); 156127668Sbms return markNotConstant(RHS.getNotConstant()); 15798524Sfenner } 158127668Sbms 159127668Sbms assert(isUndefined() && "Unexpected lattice"); 16098524Sfenner return markNotConstant(RHS.getNotConstant()); 161127668Sbms } 162127668Sbms 163127668Sbms // RHS must be a constant, we must be undef, constant, or notconstant. 16498524Sfenner if (isUndefined()) 165127668Sbms return markConstant(RHS.getConstant()); 16698524Sfenner 167127668Sbms if (isConstant()) { 168127668Sbms if (getConstant() != RHS.getConstant()) 16998524Sfenner return markOverdefined(); 170127668Sbms return false; 171127668Sbms } 17298524Sfenner 173127668Sbms // If we are known "!=4" and RHS is "==5", stay at "!=4". 174127668Sbms if (getNotConstant() == RHS.getConstant() || 17598524Sfenner isa<ConstantExpr>(getNotConstant()) || 176127668Sbms isa<ConstantExpr>(RHS.getConstant())) 177127668Sbms return markOverdefined(); 178127668Sbms return false; 179127668Sbms } 180127668Sbms 181127668Sbms}; 182127668Sbms 18398524Sfenner} // end anonymous namespace. 184127668Sbms 185127668Sbmsnamespace llvm { 186127668Sbmsraw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) { 187127668Sbms if (Val.isUndefined()) 188127668Sbms return OS << "undefined"; 189127668Sbms if (Val.isOverdefined()) 190127668Sbms return OS << "overdefined"; 191127668Sbms 192127668Sbms if (Val.isNotConstant()) 193127668Sbms return OS << "notconstant<" << *Val.getNotConstant() << '>'; 194127668Sbms return OS << "constant<" << *Val.getConstant() << '>'; 195127668Sbms} 196127668Sbms} 197127668Sbms 198127668Sbms//===----------------------------------------------------------------------===// 199127668Sbms// LazyValueInfoCache Decl 200127668Sbms//===----------------------------------------------------------------------===// 201127668Sbms 202127668Sbmsnamespace { 203127668Sbms /// LazyValueInfoCache - This is the cache kept by LazyValueInfo which 204127668Sbms /// maintains information about queries across the clients' queries. 205127668Sbms class LazyValueInfoCache { 206127668Sbms public: 207127668Sbms /// BlockCacheEntryTy - This is a computed lattice value at the end of the 208127668Sbms /// specified basic block for a Value* that depends on context. 209127668Sbms typedef std::pair<BasicBlock*, LVILatticeVal> BlockCacheEntryTy; 210127668Sbms 211127668Sbms /// ValueCacheEntryTy - This is all of the cached block information for 21298524Sfenner /// exactly one Value*. The entries are sorted by the BasicBlock* of the 21398524Sfenner /// entries, allowing us to do a lookup with a binary search. 21498524Sfenner typedef std::vector<BlockCacheEntryTy> ValueCacheEntryTy; 215127668Sbms 21675115Sfenner private: 217127668Sbms /// ValueCache - This is all of the cached information for all values, 218127668Sbms /// mapped from Value* to key information. 21998524Sfenner DenseMap<Value*, ValueCacheEntryTy> ValueCache; 22098524Sfenner public: 22198524Sfenner 22298524Sfenner /// getValueInBlock - This is the query interface to determine the lattice 22375115Sfenner /// value for the specified Value* at the end of the specified block. 22475115Sfenner LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB); 22598524Sfenner 22698524Sfenner /// getValueOnEdge - This is the query interface to determine the lattice 22798524Sfenner /// value for the specified Value* that is true on the specified edge. 22898524Sfenner LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB); 22998524Sfenner }; 23098524Sfenner} // end anonymous namespace 23198524Sfenner 23298524Sfennernamespace { 23398524Sfenner struct BlockCacheEntryComparator { 23498524Sfenner static int Compare(const void *LHSv, const void *RHSv) { 23598524Sfenner const LazyValueInfoCache::BlockCacheEntryTy *LHS = 23698524Sfenner static_cast<const LazyValueInfoCache::BlockCacheEntryTy *>(LHSv); 23798524Sfenner const LazyValueInfoCache::BlockCacheEntryTy *RHS = 23875115Sfenner static_cast<const LazyValueInfoCache::BlockCacheEntryTy *>(RHSv); 23998524Sfenner if (LHS->first < RHS->first) 24098524Sfenner return -1; 24198524Sfenner if (LHS->first > RHS->first) 24298524Sfenner return 1; 24398524Sfenner return 0; 24498524Sfenner } 24598524Sfenner 24675115Sfenner bool operator()(const LazyValueInfoCache::BlockCacheEntryTy &LHS, 247127668Sbms const LazyValueInfoCache::BlockCacheEntryTy &RHS) const { 24898524Sfenner return LHS.first < RHS.first; 24998524Sfenner } 25075115Sfenner }; 25198524Sfenner} 252127668Sbms 25398524Sfenner//===----------------------------------------------------------------------===// 25498524Sfenner// LVIQuery Impl 25598524Sfenner//===----------------------------------------------------------------------===// 25698524Sfenner 25798524Sfennernamespace { 25875115Sfenner /// LVIQuery - This is a transient object that exists while a query is 259127668Sbms /// being performed. 26098524Sfenner /// 26198524Sfenner /// TODO: Reuse LVIQuery instead of recreating it for every query, this avoids 26298524Sfenner /// reallocation of the densemap on every query. 26375115Sfenner class LVIQuery { 264146773Ssam typedef LazyValueInfoCache::BlockCacheEntryTy BlockCacheEntryTy; 26598524Sfenner typedef LazyValueInfoCache::ValueCacheEntryTy ValueCacheEntryTy; 26698524Sfenner 26798524Sfenner /// This is the current value being queried for. 26898524Sfenner Value *Val; 26998524Sfenner 27098524Sfenner /// This is all of the cached information about this value. 27198524Sfenner ValueCacheEntryTy &Cache; 272127668Sbms 27398524Sfenner /// NewBlocks - This is a mapping of the new BasicBlocks which have been 27498524Sfenner /// added to cache but that are not in sorted order. 275127668Sbms DenseMap<BasicBlock*, LVILatticeVal> NewBlockInfo; 276127668Sbms public: 277127668Sbms 27898524Sfenner LVIQuery(Value *V, ValueCacheEntryTy &VC) : Val(V), Cache(VC) { 27975115Sfenner } 28098524Sfenner 28198524Sfenner ~LVIQuery() { 28298524Sfenner // When the query is done, insert the newly discovered facts into the 28398524Sfenner // cache in sorted order. 28498524Sfenner if (NewBlockInfo.empty()) return; 28598524Sfenner 28698524Sfenner // Grow the cache to exactly fit the new data. 28798524Sfenner Cache.reserve(Cache.size() + NewBlockInfo.size()); 28898524Sfenner 289127668Sbms // If we only have one new entry, insert it instead of doing a full-on 290127668Sbms // sort. 29198524Sfenner if (NewBlockInfo.size() == 1) { 29298524Sfenner BlockCacheEntryTy Entry = *NewBlockInfo.begin(); 29398524Sfenner ValueCacheEntryTy::iterator I = 294127668Sbms std::lower_bound(Cache.begin(), Cache.end(), Entry, 295127668Sbms BlockCacheEntryComparator()); 296127668Sbms assert((I == Cache.end() || I->first != Entry.first) && 29798524Sfenner "Entry already in map!"); 29898524Sfenner 29998524Sfenner Cache.insert(I, Entry); 30098524Sfenner return; 30198524Sfenner } 30298524Sfenner 30398524Sfenner // TODO: If we only have two new elements, INSERT them both. 304127668Sbms 30598524Sfenner Cache.insert(Cache.end(), NewBlockInfo.begin(), NewBlockInfo.end()); 30698524Sfenner array_pod_sort(Cache.begin(), Cache.end(), 30798524Sfenner BlockCacheEntryComparator::Compare); 30898524Sfenner 30998524Sfenner } 310127668Sbms 31198524Sfenner LVILatticeVal getBlockValue(BasicBlock *BB); 31298524Sfenner LVILatticeVal getEdgeValue(BasicBlock *FromBB, BasicBlock *ToBB); 31398524Sfenner 31498524Sfenner private: 31598524Sfenner LVILatticeVal &getCachedEntryForBlock(BasicBlock *BB); 316127668Sbms }; 31798524Sfenner} // end anonymous namespace 31898524Sfenner 31998524Sfenner/// getCachedEntryForBlock - See if we already have a value for this block. If 32098524Sfenner/// so, return it, otherwise create a new entry in the NewBlockInfo map to use. 32198524SfennerLVILatticeVal &LVIQuery::getCachedEntryForBlock(BasicBlock *BB) { 32275115Sfenner 32398524Sfenner // Do a binary search to see if we already have an entry for this block in 32498524Sfenner // the cache set. If so, find it. 32575115Sfenner if (!Cache.empty()) { 32698524Sfenner ValueCacheEntryTy::iterator Entry = 32798524Sfenner std::lower_bound(Cache.begin(), Cache.end(), 32898524Sfenner BlockCacheEntryTy(BB, LVILatticeVal()), 32998524Sfenner BlockCacheEntryComparator()); 33098524Sfenner if (Entry != Cache.end() && Entry->first == BB) 33175115Sfenner return Entry->second; 33275115Sfenner } 33375115Sfenner 33498524Sfenner // Otherwise, check to see if it's in NewBlockInfo or create a new entry if 33598524Sfenner // not. 33675115Sfenner return NewBlockInfo[BB]; 33798524Sfenner} 33898524Sfenner 33975115SfennerLVILatticeVal LVIQuery::getBlockValue(BasicBlock *BB) { 34098524Sfenner // See if we already have a value for this block. 34198524Sfenner LVILatticeVal &BBLV = getCachedEntryForBlock(BB); 34298524Sfenner 34398524Sfenner // If we've already computed this block's value, return it. 34498524Sfenner if (!BBLV.isUndefined()) { 34598524Sfenner DEBUG(errs() << " reuse BB '" << BB->getName() << "' val=" << BBLV <<'\n'); 34698524Sfenner return BBLV; 34798524Sfenner } 34898524Sfenner 34998524Sfenner // Otherwise, this is the first time we're seeing this block. Reset the 35098524Sfenner // lattice value to overdefined, so that cycles will terminate and be 35198524Sfenner // conservatively correct. 35275115Sfenner BBLV.markOverdefined(); 353127668Sbms 354127668Sbms // If V is live into BB, see if our predecessors know anything about it. 355127668Sbms Instruction *BBI = dyn_cast<Instruction>(Val); 356127668Sbms if (BBI == 0 || BBI->getParent() != BB) { 357127668Sbms LVILatticeVal Result; // Start Undefined. 358127668Sbms unsigned NumPreds = 0; 359127668Sbms 360127668Sbms // Loop over all of our predecessors, merging what we know from them into 361127668Sbms // result. 362127668Sbms for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 363127668Sbms Result.mergeIn(getEdgeValue(*PI, BB)); 364127668Sbms 365127668Sbms // If we hit overdefined, exit early. The BlockVals entry is already set 366127668Sbms // to overdefined. 367 if (Result.isOverdefined()) { 368 DEBUG(errs() << " compute BB '" << BB->getName() 369 << "' - overdefined because of pred.\n"); 370 return Result; 371 } 372 ++NumPreds; 373 } 374 375 // If this is the entry block, we must be asking about an argument. The 376 // value is overdefined. 377 if (NumPreds == 0 && BB == &BB->getParent()->front()) { 378 assert(isa<Argument>(Val) && "Unknown live-in to the entry block"); 379 Result.markOverdefined(); 380 return Result; 381 } 382 383 // Return the merged value, which is more precise than 'overdefined'. 384 assert(!Result.isOverdefined()); 385 return getCachedEntryForBlock(BB) = Result; 386 } 387 388 // If this value is defined by an instruction in this block, we have to 389 // process it here somehow or return overdefined. 390 if (PHINode *PN = dyn_cast<PHINode>(BBI)) { 391 (void)PN; 392 // TODO: PHI Translation in preds. 393 } else { 394 395 } 396 397 DEBUG(errs() << " compute BB '" << BB->getName() 398 << "' - overdefined because inst def found.\n"); 399 400 LVILatticeVal Result; 401 Result.markOverdefined(); 402 return getCachedEntryForBlock(BB) = Result; 403} 404 405 406/// getEdgeValue - This method attempts to infer more complex 407LVILatticeVal LVIQuery::getEdgeValue(BasicBlock *BBFrom, BasicBlock *BBTo) { 408 // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we 409 // know that v != 0. 410 if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) { 411 // If this is a conditional branch and only one successor goes to BBTo, then 412 // we maybe able to infer something from the condition. 413 if (BI->isConditional() && 414 BI->getSuccessor(0) != BI->getSuccessor(1)) { 415 bool isTrueDest = BI->getSuccessor(0) == BBTo; 416 assert(BI->getSuccessor(!isTrueDest) == BBTo && 417 "BBTo isn't a successor of BBFrom"); 418 419 // If V is the condition of the branch itself, then we know exactly what 420 // it is. 421 if (BI->getCondition() == Val) 422 return LVILatticeVal::get(ConstantInt::get( 423 Type::getInt1Ty(Val->getContext()), isTrueDest)); 424 425 // If the condition of the branch is an equality comparison, we may be 426 // able to infer the value. 427 if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) 428 if (ICI->isEquality() && ICI->getOperand(0) == Val && 429 isa<Constant>(ICI->getOperand(1))) { 430 // We know that V has the RHS constant if this is a true SETEQ or 431 // false SETNE. 432 if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ)) 433 return LVILatticeVal::get(cast<Constant>(ICI->getOperand(1))); 434 return LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1))); 435 } 436 } 437 } 438 439 // If the edge was formed by a switch on the value, then we may know exactly 440 // what it is. 441 if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) { 442 // If BBTo is the default destination of the switch, we don't know anything. 443 // Given a more powerful range analysis we could know stuff. 444 if (SI->getCondition() == Val && SI->getDefaultDest() != BBTo) { 445 // We only know something if there is exactly one value that goes from 446 // BBFrom to BBTo. 447 unsigned NumEdges = 0; 448 ConstantInt *EdgeVal = 0; 449 for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) { 450 if (SI->getSuccessor(i) != BBTo) continue; 451 if (NumEdges++) break; 452 EdgeVal = SI->getCaseValue(i); 453 } 454 assert(EdgeVal && "Missing successor?"); 455 if (NumEdges == 1) 456 return LVILatticeVal::get(EdgeVal); 457 } 458 } 459 460 // Otherwise see if the value is known in the block. 461 return getBlockValue(BBFrom); 462} 463 464 465//===----------------------------------------------------------------------===// 466// LazyValueInfoCache Impl 467//===----------------------------------------------------------------------===// 468 469LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB) { 470 // If already a constant, there is nothing to compute. 471 if (Constant *VC = dyn_cast<Constant>(V)) 472 return LVILatticeVal::get(VC); 473 474 DEBUG(errs() << "LVI Getting block end value " << *V << " at '" 475 << BB->getName() << "'\n"); 476 477 LVILatticeVal Result = LVIQuery(V, ValueCache[V]).getBlockValue(BB); 478 479 DEBUG(errs() << " Result = " << Result << "\n"); 480 return Result; 481} 482 483LVILatticeVal LazyValueInfoCache:: 484getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB) { 485 // If already a constant, there is nothing to compute. 486 if (Constant *VC = dyn_cast<Constant>(V)) 487 return LVILatticeVal::get(VC); 488 489 DEBUG(errs() << "LVI Getting edge value " << *V << " from '" 490 << FromBB->getName() << "' to '" << ToBB->getName() << "'\n"); 491 LVILatticeVal Result = 492 LVIQuery(V, ValueCache[V]).getEdgeValue(FromBB, ToBB); 493 494 DEBUG(errs() << " Result = " << Result << "\n"); 495 496 return Result; 497} 498 499//===----------------------------------------------------------------------===// 500// LazyValueInfo Impl 501//===----------------------------------------------------------------------===// 502 503bool LazyValueInfo::runOnFunction(Function &F) { 504 TD = getAnalysisIfAvailable<TargetData>(); 505 // Fully lazy. 506 return false; 507} 508 509/// getCache - This lazily constructs the LazyValueInfoCache. 510static LazyValueInfoCache &getCache(void *&PImpl) { 511 if (!PImpl) 512 PImpl = new LazyValueInfoCache(); 513 return *static_cast<LazyValueInfoCache*>(PImpl); 514} 515 516void LazyValueInfo::releaseMemory() { 517 // If the cache was allocated, free it. 518 if (PImpl) { 519 delete &getCache(PImpl); 520 PImpl = 0; 521 } 522} 523 524Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB) { 525 LVILatticeVal Result = getCache(PImpl).getValueInBlock(V, BB); 526 527 if (Result.isConstant()) 528 return Result.getConstant(); 529 return 0; 530} 531 532/// getConstantOnEdge - Determine whether the specified value is known to be a 533/// constant on the specified edge. Return null if not. 534Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB, 535 BasicBlock *ToBB) { 536 LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB); 537 538 if (Result.isConstant()) 539 return Result.getConstant(); 540 return 0; 541} 542 543/// getPredicateOnEdge - Determine whether the specified value comparison 544/// with a constant is known to be true or false on the specified CFG edge. 545/// Pred is a CmpInst predicate. 546LazyValueInfo::Tristate 547LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, 548 BasicBlock *FromBB, BasicBlock *ToBB) { 549 LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB); 550 551 // If we know the value is a constant, evaluate the conditional. 552 Constant *Res = 0; 553 if (Result.isConstant()) { 554 Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, TD); 555 if (ConstantInt *ResCI = dyn_cast_or_null<ConstantInt>(Res)) 556 return ResCI->isZero() ? False : True; 557 return Unknown; 558 } 559 560 if (Result.isNotConstant()) { 561 // If this is an equality comparison, we can try to fold it knowing that 562 // "V != C1". 563 if (Pred == ICmpInst::ICMP_EQ) { 564 // !C1 == C -> false iff C1 == C. 565 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE, 566 Result.getNotConstant(), C, TD); 567 if (Res->isNullValue()) 568 return False; 569 } else if (Pred == ICmpInst::ICMP_NE) { 570 // !C1 != C -> true iff C1 == C. 571 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE, 572 Result.getNotConstant(), C, TD); 573 if (Res->isNullValue()) 574 return True; 575 } 576 return Unknown; 577 } 578 579 return Unknown; 580} 581 582 583