1199481Srdivacky//===- LazyValueInfo.cpp - Value constraint analysis ----------------------===// 2199481Srdivacky// 3199481Srdivacky// The LLVM Compiler Infrastructure 4199481Srdivacky// 5199481Srdivacky// This file is distributed under the University of Illinois Open Source 6199481Srdivacky// License. See LICENSE.TXT for details. 7199481Srdivacky// 8199481Srdivacky//===----------------------------------------------------------------------===// 9199481Srdivacky// 10199481Srdivacky// This file defines the interface for lazy computation of value constraint 11199481Srdivacky// information. 12199481Srdivacky// 13199481Srdivacky//===----------------------------------------------------------------------===// 14199481Srdivacky 15199481Srdivacky#define DEBUG_TYPE "lazy-value-info" 16199481Srdivacky#include "llvm/Analysis/LazyValueInfo.h" 17252723Sdim#include "llvm/ADT/DenseSet.h" 18252723Sdim#include "llvm/ADT/STLExtras.h" 19252723Sdim#include "llvm/Analysis/ConstantFolding.h" 20218893Sdim#include "llvm/Analysis/ValueTracking.h" 21252723Sdim#include "llvm/IR/Constants.h" 22252723Sdim#include "llvm/IR/DataLayout.h" 23252723Sdim#include "llvm/IR/Instructions.h" 24252723Sdim#include "llvm/IR/IntrinsicInst.h" 25199481Srdivacky#include "llvm/Support/CFG.h" 26212904Sdim#include "llvm/Support/ConstantRange.h" 27199481Srdivacky#include "llvm/Support/Debug.h" 28235633Sdim#include "llvm/Support/PatternMatch.h" 29252723Sdim#include "llvm/Support/ValueHandle.h" 30199481Srdivacky#include "llvm/Support/raw_ostream.h" 31252723Sdim#include "llvm/Target/TargetLibraryInfo.h" 32218893Sdim#include <map> 33218893Sdim#include <stack> 34199481Srdivackyusing namespace llvm; 35235633Sdimusing namespace PatternMatch; 36199481Srdivacky 37199481Srdivackychar LazyValueInfo::ID = 0; 38235633SdimINITIALIZE_PASS_BEGIN(LazyValueInfo, "lazy-value-info", 39218893Sdim "Lazy Value Information Analysis", false, true) 40235633SdimINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 41235633SdimINITIALIZE_PASS_END(LazyValueInfo, "lazy-value-info", 42235633Sdim "Lazy Value Information Analysis", false, true) 43199481Srdivacky 44199481Srdivackynamespace llvm { 45199481Srdivacky FunctionPass *createLazyValueInfoPass() { return new LazyValueInfo(); } 46199481Srdivacky} 47199481Srdivacky 48199481Srdivacky 49199481Srdivacky//===----------------------------------------------------------------------===// 50199481Srdivacky// LVILatticeVal 51199481Srdivacky//===----------------------------------------------------------------------===// 52199481Srdivacky 53199481Srdivacky/// LVILatticeVal - This is the information tracked by LazyValueInfo for each 54199481Srdivacky/// value. 55199481Srdivacky/// 56199481Srdivacky/// FIXME: This is basically just for bringup, this can be made a lot more rich 57199481Srdivacky/// in the future. 58199481Srdivacky/// 59199481Srdivackynamespace { 60199481Srdivackyclass LVILatticeVal { 61199481Srdivacky enum LatticeValueTy { 62218893Sdim /// undefined - This Value has no known value yet. 63199481Srdivacky undefined, 64212904Sdim 65218893Sdim /// constant - This Value has a specific constant value. 66199481Srdivacky constant, 67218893Sdim /// notconstant - This Value is known to not have the specified value. 68199481Srdivacky notconstant, 69235633Sdim 70218893Sdim /// constantrange - The Value falls within this range. 71212904Sdim constantrange, 72235633Sdim 73218893Sdim /// overdefined - This value is not known to be constant, and we know that 74199481Srdivacky /// it has a value. 75199481Srdivacky overdefined 76199481Srdivacky }; 77199481Srdivacky 78199481Srdivacky /// Val: This stores the current lattice value along with the Constant* for 79199481Srdivacky /// the constant if this is a 'constant' or 'notconstant' value. 80212904Sdim LatticeValueTy Tag; 81212904Sdim Constant *Val; 82212904Sdim ConstantRange Range; 83199481Srdivacky 84199481Srdivackypublic: 85212904Sdim LVILatticeVal() : Tag(undefined), Val(0), Range(1, true) {} 86199481Srdivacky 87199481Srdivacky static LVILatticeVal get(Constant *C) { 88199481Srdivacky LVILatticeVal Res; 89218893Sdim if (!isa<UndefValue>(C)) 90212904Sdim Res.markConstant(C); 91199481Srdivacky return Res; 92199481Srdivacky } 93199481Srdivacky static LVILatticeVal getNot(Constant *C) { 94199481Srdivacky LVILatticeVal Res; 95218893Sdim if (!isa<UndefValue>(C)) 96212904Sdim Res.markNotConstant(C); 97199481Srdivacky return Res; 98199481Srdivacky } 99212904Sdim static LVILatticeVal getRange(ConstantRange CR) { 100212904Sdim LVILatticeVal Res; 101212904Sdim Res.markConstantRange(CR); 102212904Sdim return Res; 103212904Sdim } 104199481Srdivacky 105212904Sdim bool isUndefined() const { return Tag == undefined; } 106212904Sdim bool isConstant() const { return Tag == constant; } 107212904Sdim bool isNotConstant() const { return Tag == notconstant; } 108212904Sdim bool isConstantRange() const { return Tag == constantrange; } 109212904Sdim bool isOverdefined() const { return Tag == overdefined; } 110199481Srdivacky 111199481Srdivacky Constant *getConstant() const { 112199481Srdivacky assert(isConstant() && "Cannot get the constant of a non-constant!"); 113212904Sdim return Val; 114199481Srdivacky } 115199481Srdivacky 116199481Srdivacky Constant *getNotConstant() const { 117199481Srdivacky assert(isNotConstant() && "Cannot get the constant of a non-notconstant!"); 118212904Sdim return Val; 119199481Srdivacky } 120199481Srdivacky 121212904Sdim ConstantRange getConstantRange() const { 122212904Sdim assert(isConstantRange() && 123212904Sdim "Cannot get the constant-range of a non-constant-range!"); 124212904Sdim return Range; 125212904Sdim } 126212904Sdim 127199481Srdivacky /// markOverdefined - Return true if this is a change in status. 128199481Srdivacky bool markOverdefined() { 129199481Srdivacky if (isOverdefined()) 130199481Srdivacky return false; 131212904Sdim Tag = overdefined; 132199481Srdivacky return true; 133199481Srdivacky } 134199481Srdivacky 135199481Srdivacky /// markConstant - Return true if this is a change in status. 136199481Srdivacky bool markConstant(Constant *V) { 137218893Sdim assert(V && "Marking constant with NULL"); 138218893Sdim if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 139218893Sdim return markConstantRange(ConstantRange(CI->getValue())); 140218893Sdim if (isa<UndefValue>(V)) 141199481Srdivacky return false; 142218893Sdim 143218893Sdim assert((!isConstant() || getConstant() == V) && 144218893Sdim "Marking constant with different value"); 145199481Srdivacky assert(isUndefined()); 146212904Sdim Tag = constant; 147212904Sdim Val = V; 148199481Srdivacky return true; 149199481Srdivacky } 150199481Srdivacky 151199481Srdivacky /// markNotConstant - Return true if this is a change in status. 152199481Srdivacky bool markNotConstant(Constant *V) { 153218893Sdim assert(V && "Marking constant with NULL"); 154218893Sdim if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 155218893Sdim return markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue())); 156218893Sdim if (isa<UndefValue>(V)) 157199481Srdivacky return false; 158199481Srdivacky 159218893Sdim assert((!isConstant() || getConstant() != V) && 160218893Sdim "Marking constant !constant with same value"); 161218893Sdim assert((!isNotConstant() || getNotConstant() == V) && 162218893Sdim "Marking !constant with different value"); 163218893Sdim assert(isUndefined() || isConstant()); 164212904Sdim Tag = notconstant; 165212904Sdim Val = V; 166199481Srdivacky return true; 167199481Srdivacky } 168199481Srdivacky 169212904Sdim /// markConstantRange - Return true if this is a change in status. 170212904Sdim bool markConstantRange(const ConstantRange NewR) { 171212904Sdim if (isConstantRange()) { 172212904Sdim if (NewR.isEmptySet()) 173212904Sdim return markOverdefined(); 174212904Sdim 175245431Sdim bool changed = Range != NewR; 176212904Sdim Range = NewR; 177212904Sdim return changed; 178212904Sdim } 179212904Sdim 180212904Sdim assert(isUndefined()); 181212904Sdim if (NewR.isEmptySet()) 182212904Sdim return markOverdefined(); 183212904Sdim 184212904Sdim Tag = constantrange; 185212904Sdim Range = NewR; 186212904Sdim return true; 187212904Sdim } 188212904Sdim 189199481Srdivacky /// mergeIn - Merge the specified lattice value into this one, updating this 190199481Srdivacky /// one and returning true if anything changed. 191199481Srdivacky bool mergeIn(const LVILatticeVal &RHS) { 192199481Srdivacky if (RHS.isUndefined() || isOverdefined()) return false; 193199481Srdivacky if (RHS.isOverdefined()) return markOverdefined(); 194199481Srdivacky 195218893Sdim if (isUndefined()) { 196218893Sdim Tag = RHS.Tag; 197218893Sdim Val = RHS.Val; 198218893Sdim Range = RHS.Range; 199218893Sdim return true; 200218893Sdim } 201218893Sdim 202218893Sdim if (isConstant()) { 203218893Sdim if (RHS.isConstant()) { 204218893Sdim if (Val == RHS.Val) 205218893Sdim return false; 206218893Sdim return markOverdefined(); 207218893Sdim } 208218893Sdim 209218893Sdim if (RHS.isNotConstant()) { 210218893Sdim if (Val == RHS.Val) 211199481Srdivacky return markOverdefined(); 212218893Sdim 213218893Sdim // Unless we can prove that the two Constants are different, we must 214218893Sdim // move to overdefined. 215245431Sdim // FIXME: use DataLayout/TargetLibraryInfo for smarter constant folding. 216218893Sdim if (ConstantInt *Res = dyn_cast<ConstantInt>( 217218893Sdim ConstantFoldCompareInstOperands(CmpInst::ICMP_NE, 218218893Sdim getConstant(), 219218893Sdim RHS.getNotConstant()))) 220218893Sdim if (Res->isOne()) 221218893Sdim return markNotConstant(RHS.getNotConstant()); 222218893Sdim 223212904Sdim return markOverdefined(); 224199481Srdivacky } 225218893Sdim 226218893Sdim // RHS is a ConstantRange, LHS is a non-integer Constant. 227218893Sdim 228218893Sdim // FIXME: consider the case where RHS is a range [1, 0) and LHS is 229218893Sdim // a function. The correct result is to pick up RHS. 230218893Sdim 231218893Sdim return markOverdefined(); 232199481Srdivacky } 233218893Sdim 234218893Sdim if (isNotConstant()) { 235218893Sdim if (RHS.isConstant()) { 236218893Sdim if (Val == RHS.Val) 237212904Sdim return markOverdefined(); 238218893Sdim 239218893Sdim // Unless we can prove that the two Constants are different, we must 240218893Sdim // move to overdefined. 241245431Sdim // FIXME: use DataLayout/TargetLibraryInfo for smarter constant folding. 242218893Sdim if (ConstantInt *Res = dyn_cast<ConstantInt>( 243218893Sdim ConstantFoldCompareInstOperands(CmpInst::ICMP_NE, 244218893Sdim getNotConstant(), 245218893Sdim RHS.getConstant()))) 246218893Sdim if (Res->isOne()) 247218893Sdim return false; 248218893Sdim 249212904Sdim return markOverdefined(); 250212904Sdim } 251218893Sdim 252218893Sdim if (RHS.isNotConstant()) { 253218893Sdim if (Val == RHS.Val) 254218893Sdim return false; 255199481Srdivacky return markOverdefined(); 256218893Sdim } 257218893Sdim 258218893Sdim return markOverdefined(); 259199481Srdivacky } 260199481Srdivacky 261218893Sdim assert(isConstantRange() && "New LVILattice type?"); 262218893Sdim if (!RHS.isConstantRange()) 263199481Srdivacky return markOverdefined(); 264218893Sdim 265218893Sdim ConstantRange NewR = Range.unionWith(RHS.getConstantRange()); 266218893Sdim if (NewR.isFullSet()) 267218893Sdim return markOverdefined(); 268218893Sdim return markConstantRange(NewR); 269199481Srdivacky } 270199481Srdivacky}; 271199481Srdivacky 272199481Srdivacky} // end anonymous namespace. 273199481Srdivacky 274199481Srdivackynamespace llvm { 275221345Sdimraw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) 276221345Sdim LLVM_ATTRIBUTE_USED; 277199481Srdivackyraw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) { 278199481Srdivacky if (Val.isUndefined()) 279199481Srdivacky return OS << "undefined"; 280199481Srdivacky if (Val.isOverdefined()) 281199481Srdivacky return OS << "overdefined"; 282199481Srdivacky 283199481Srdivacky if (Val.isNotConstant()) 284199481Srdivacky return OS << "notconstant<" << *Val.getNotConstant() << '>'; 285212904Sdim else if (Val.isConstantRange()) 286212904Sdim return OS << "constantrange<" << Val.getConstantRange().getLower() << ", " 287212904Sdim << Val.getConstantRange().getUpper() << '>'; 288199481Srdivacky return OS << "constant<" << *Val.getConstant() << '>'; 289199481Srdivacky} 290199481Srdivacky} 291199481Srdivacky 292199481Srdivacky//===----------------------------------------------------------------------===// 293199481Srdivacky// LazyValueInfoCache Decl 294199481Srdivacky//===----------------------------------------------------------------------===// 295199481Srdivacky 296199481Srdivackynamespace { 297245431Sdim /// LVIValueHandle - A callback value handle updates the cache when 298218893Sdim /// values are erased. 299218893Sdim class LazyValueInfoCache; 300218893Sdim struct LVIValueHandle : public CallbackVH { 301218893Sdim LazyValueInfoCache *Parent; 302218893Sdim 303218893Sdim LVIValueHandle(Value *V, LazyValueInfoCache *P) 304218893Sdim : CallbackVH(V), Parent(P) { } 305218893Sdim 306218893Sdim void deleted(); 307218893Sdim void allUsesReplacedWith(Value *V) { 308218893Sdim deleted(); 309218893Sdim } 310218893Sdim }; 311218893Sdim} 312218893Sdim 313218893Sdimnamespace { 314199481Srdivacky /// LazyValueInfoCache - This is the cache kept by LazyValueInfo which 315199481Srdivacky /// maintains information about queries across the clients' queries. 316199481Srdivacky class LazyValueInfoCache { 317199481Srdivacky /// ValueCacheEntryTy - This is all of the cached block information for 318199481Srdivacky /// exactly one Value*. The entries are sorted by the BasicBlock* of the 319199481Srdivacky /// entries, allowing us to do a lookup with a binary search. 320212904Sdim typedef std::map<AssertingVH<BasicBlock>, LVILatticeVal> ValueCacheEntryTy; 321199481Srdivacky 322218893Sdim /// ValueCache - This is all of the cached information for all values, 323218893Sdim /// mapped from Value* to key information. 324235633Sdim std::map<LVIValueHandle, ValueCacheEntryTy> ValueCache; 325218893Sdim 326218893Sdim /// OverDefinedCache - This tracks, on a per-block basis, the set of 327218893Sdim /// values that are over-defined at the end of that block. This is required 328218893Sdim /// for cache updating. 329218893Sdim typedef std::pair<AssertingVH<BasicBlock>, Value*> OverDefinedPairTy; 330218893Sdim DenseSet<OverDefinedPairTy> OverDefinedCache; 331235633Sdim 332235633Sdim /// SeenBlocks - Keep track of all blocks that we have ever seen, so we 333235633Sdim /// don't spend time removing unused blocks from our caches. 334235633Sdim DenseSet<AssertingVH<BasicBlock> > SeenBlocks; 335235633Sdim 336218893Sdim /// BlockValueStack - This stack holds the state of the value solver 337218893Sdim /// during a query. It basically emulates the callstack of the naive 338218893Sdim /// recursive value lookup process. 339218893Sdim std::stack<std::pair<BasicBlock*, Value*> > BlockValueStack; 340218893Sdim 341218893Sdim friend struct LVIValueHandle; 342218893Sdim 343218893Sdim /// OverDefinedCacheUpdater - A helper object that ensures that the 344218893Sdim /// OverDefinedCache is updated whenever solveBlockValue returns. 345218893Sdim struct OverDefinedCacheUpdater { 346212904Sdim LazyValueInfoCache *Parent; 347218893Sdim Value *Val; 348218893Sdim BasicBlock *BB; 349218893Sdim LVILatticeVal &BBLV; 350212904Sdim 351218893Sdim OverDefinedCacheUpdater(Value *V, BasicBlock *B, LVILatticeVal &LV, 352218893Sdim LazyValueInfoCache *P) 353218893Sdim : Parent(P), Val(V), BB(B), BBLV(LV) { } 354212904Sdim 355218893Sdim bool markResult(bool changed) { 356218893Sdim if (changed && BBLV.isOverdefined()) 357218893Sdim Parent->OverDefinedCache.insert(std::make_pair(BB, Val)); 358218893Sdim return changed; 359212904Sdim } 360212904Sdim }; 361218893Sdim 362212904Sdim 363218893Sdim 364218893Sdim LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB); 365218893Sdim bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T, 366218893Sdim LVILatticeVal &Result); 367218893Sdim bool hasBlockValue(Value *Val, BasicBlock *BB); 368218893Sdim 369218893Sdim // These methods process one work item and may add more. A false value 370218893Sdim // returned means that the work item was not completely processed and must 371218893Sdim // be revisited after going through the new items. 372218893Sdim bool solveBlockValue(Value *Val, BasicBlock *BB); 373218893Sdim bool solveBlockValueNonLocal(LVILatticeVal &BBLV, 374218893Sdim Value *Val, BasicBlock *BB); 375218893Sdim bool solveBlockValuePHINode(LVILatticeVal &BBLV, 376218893Sdim PHINode *PN, BasicBlock *BB); 377218893Sdim bool solveBlockValueConstantRange(LVILatticeVal &BBLV, 378218893Sdim Instruction *BBI, BasicBlock *BB); 379218893Sdim 380218893Sdim void solve(); 381212904Sdim 382218893Sdim ValueCacheEntryTy &lookup(Value *V) { 383218893Sdim return ValueCache[LVIValueHandle(V, this)]; 384218893Sdim } 385212904Sdim 386199481Srdivacky public: 387199481Srdivacky /// getValueInBlock - This is the query interface to determine the lattice 388199481Srdivacky /// value for the specified Value* at the end of the specified block. 389199481Srdivacky LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB); 390199481Srdivacky 391199481Srdivacky /// getValueOnEdge - This is the query interface to determine the lattice 392199481Srdivacky /// value for the specified Value* that is true on the specified edge. 393199481Srdivacky LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB); 394199481Srdivacky 395212904Sdim /// threadEdge - This is the update interface to inform the cache that an 396212904Sdim /// edge from PredBB to OldSucc has been threaded to be from PredBB to 397212904Sdim /// NewSucc. 398212904Sdim void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc); 399212904Sdim 400212904Sdim /// eraseBlock - This is part of the update interface to inform the cache 401212904Sdim /// that a block has been deleted. 402212904Sdim void eraseBlock(BasicBlock *BB); 403212904Sdim 404212904Sdim /// clear - Empty the cache. 405212904Sdim void clear() { 406235633Sdim SeenBlocks.clear(); 407212904Sdim ValueCache.clear(); 408212904Sdim OverDefinedCache.clear(); 409199481Srdivacky } 410199481Srdivacky }; 411212904Sdim} // end anonymous namespace 412199481Srdivacky 413218893Sdimvoid LVIValueHandle::deleted() { 414218893Sdim typedef std::pair<AssertingVH<BasicBlock>, Value*> OverDefinedPairTy; 415218893Sdim 416218893Sdim SmallVector<OverDefinedPairTy, 4> ToErase; 417218893Sdim for (DenseSet<OverDefinedPairTy>::iterator 418212904Sdim I = Parent->OverDefinedCache.begin(), 419212904Sdim E = Parent->OverDefinedCache.end(); 420218893Sdim I != E; ++I) { 421218893Sdim if (I->second == getValPtr()) 422218893Sdim ToErase.push_back(*I); 423199481Srdivacky } 424263509Sdim 425263509Sdim for (SmallVectorImpl<OverDefinedPairTy>::iterator I = ToErase.begin(), 426218893Sdim E = ToErase.end(); I != E; ++I) 427218893Sdim Parent->OverDefinedCache.erase(*I); 428218893Sdim 429212904Sdim // This erasure deallocates *this, so it MUST happen after we're done 430212904Sdim // using any and all members of *this. 431212904Sdim Parent->ValueCache.erase(*this); 432199481Srdivacky} 433199481Srdivacky 434212904Sdimvoid LazyValueInfoCache::eraseBlock(BasicBlock *BB) { 435235633Sdim // Shortcut if we have never seen this block. 436235633Sdim DenseSet<AssertingVH<BasicBlock> >::iterator I = SeenBlocks.find(BB); 437235633Sdim if (I == SeenBlocks.end()) 438235633Sdim return; 439235633Sdim SeenBlocks.erase(I); 440235633Sdim 441218893Sdim SmallVector<OverDefinedPairTy, 4> ToErase; 442218893Sdim for (DenseSet<OverDefinedPairTy>::iterator I = OverDefinedCache.begin(), 443218893Sdim E = OverDefinedCache.end(); I != E; ++I) { 444218893Sdim if (I->first == BB) 445218893Sdim ToErase.push_back(*I); 446212904Sdim } 447263509Sdim 448263509Sdim for (SmallVectorImpl<OverDefinedPairTy>::iterator I = ToErase.begin(), 449218893Sdim E = ToErase.end(); I != E; ++I) 450218893Sdim OverDefinedCache.erase(*I); 451212904Sdim 452235633Sdim for (std::map<LVIValueHandle, ValueCacheEntryTy>::iterator 453212904Sdim I = ValueCache.begin(), E = ValueCache.end(); I != E; ++I) 454212904Sdim I->second.erase(BB); 455212904Sdim} 456212904Sdim 457218893Sdimvoid LazyValueInfoCache::solve() { 458218893Sdim while (!BlockValueStack.empty()) { 459218893Sdim std::pair<BasicBlock*, Value*> &e = BlockValueStack.top(); 460245431Sdim if (solveBlockValue(e.second, e.first)) { 461245431Sdim assert(BlockValueStack.top() == e); 462218893Sdim BlockValueStack.pop(); 463245431Sdim } 464218893Sdim } 465212904Sdim} 466212904Sdim 467218893Sdimbool LazyValueInfoCache::hasBlockValue(Value *Val, BasicBlock *BB) { 468218893Sdim // If already a constant, there is nothing to compute. 469218893Sdim if (isa<Constant>(Val)) 470218893Sdim return true; 471218893Sdim 472218893Sdim LVIValueHandle ValHandle(Val, this); 473245431Sdim std::map<LVIValueHandle, ValueCacheEntryTy>::iterator I = 474245431Sdim ValueCache.find(ValHandle); 475245431Sdim if (I == ValueCache.end()) return false; 476245431Sdim return I->second.count(BB); 477218893Sdim} 478218893Sdim 479218893SdimLVILatticeVal LazyValueInfoCache::getBlockValue(Value *Val, BasicBlock *BB) { 480218893Sdim // If already a constant, there is nothing to compute. 481218893Sdim if (Constant *VC = dyn_cast<Constant>(Val)) 482218893Sdim return LVILatticeVal::get(VC); 483218893Sdim 484235633Sdim SeenBlocks.insert(BB); 485218893Sdim return lookup(Val)[BB]; 486218893Sdim} 487218893Sdim 488218893Sdimbool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) { 489218893Sdim if (isa<Constant>(Val)) 490218893Sdim return true; 491218893Sdim 492218893Sdim ValueCacheEntryTy &Cache = lookup(Val); 493235633Sdim SeenBlocks.insert(BB); 494218893Sdim LVILatticeVal &BBLV = Cache[BB]; 495199481Srdivacky 496218893Sdim // OverDefinedCacheUpdater is a helper object that will update 497218893Sdim // the OverDefinedCache for us when this method exits. Make sure to 498218893Sdim // call markResult on it as we exist, passing a bool to indicate if the 499218893Sdim // cache needs updating, i.e. if we have solve a new value or not. 500218893Sdim OverDefinedCacheUpdater ODCacheUpdater(Val, BB, BBLV, this); 501218893Sdim 502199481Srdivacky // If we've already computed this block's value, return it. 503199481Srdivacky if (!BBLV.isUndefined()) { 504201360Srdivacky DEBUG(dbgs() << " reuse BB '" << BB->getName() << "' val=" << BBLV <<'\n'); 505218893Sdim 506218893Sdim // Since we're reusing a cached value here, we don't need to update the 507218893Sdim // OverDefinedCahce. The cache will have been properly updated 508218893Sdim // whenever the cached value was inserted. 509218893Sdim ODCacheUpdater.markResult(false); 510218893Sdim return true; 511199481Srdivacky } 512199481Srdivacky 513199481Srdivacky // Otherwise, this is the first time we're seeing this block. Reset the 514199481Srdivacky // lattice value to overdefined, so that cycles will terminate and be 515199481Srdivacky // conservatively correct. 516199481Srdivacky BBLV.markOverdefined(); 517199481Srdivacky 518199481Srdivacky Instruction *BBI = dyn_cast<Instruction>(Val); 519199481Srdivacky if (BBI == 0 || BBI->getParent() != BB) { 520218893Sdim return ODCacheUpdater.markResult(solveBlockValueNonLocal(BBLV, Val, BB)); 521199481Srdivacky } 522218893Sdim 523199481Srdivacky if (PHINode *PN = dyn_cast<PHINode>(BBI)) { 524218893Sdim return ODCacheUpdater.markResult(solveBlockValuePHINode(BBLV, PN, BB)); 525199481Srdivacky } 526199481Srdivacky 527218893Sdim if (AllocaInst *AI = dyn_cast<AllocaInst>(BBI)) { 528218893Sdim BBLV = LVILatticeVal::getNot(ConstantPointerNull::get(AI->getType())); 529218893Sdim return ODCacheUpdater.markResult(true); 530218893Sdim } 531212904Sdim 532212904Sdim // We can only analyze the definitions of certain classes of instructions 533212904Sdim // (integral binops and casts at the moment), so bail if this isn't one. 534199481Srdivacky LVILatticeVal Result; 535212904Sdim if ((!isa<BinaryOperator>(BBI) && !isa<CastInst>(BBI)) || 536212904Sdim !BBI->getType()->isIntegerTy()) { 537212904Sdim DEBUG(dbgs() << " compute BB '" << BB->getName() 538212904Sdim << "' - overdefined because inst def found.\n"); 539218893Sdim BBLV.markOverdefined(); 540218893Sdim return ODCacheUpdater.markResult(true); 541212904Sdim } 542218893Sdim 543212904Sdim // FIXME: We're currently limited to binops with a constant RHS. This should 544212904Sdim // be improved. 545212904Sdim BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI); 546212904Sdim if (BO && !isa<ConstantInt>(BO->getOperand(1))) { 547212904Sdim DEBUG(dbgs() << " compute BB '" << BB->getName() 548212904Sdim << "' - overdefined because inst def found.\n"); 549212904Sdim 550218893Sdim BBLV.markOverdefined(); 551218893Sdim return ODCacheUpdater.markResult(true); 552218893Sdim } 553212904Sdim 554218893Sdim return ODCacheUpdater.markResult(solveBlockValueConstantRange(BBLV, BBI, BB)); 555218893Sdim} 556218893Sdim 557218893Sdimstatic bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) { 558218893Sdim if (LoadInst *L = dyn_cast<LoadInst>(I)) { 559218893Sdim return L->getPointerAddressSpace() == 0 && 560245431Sdim GetUnderlyingObject(L->getPointerOperand()) == Ptr; 561218893Sdim } 562218893Sdim if (StoreInst *S = dyn_cast<StoreInst>(I)) { 563218893Sdim return S->getPointerAddressSpace() == 0 && 564245431Sdim GetUnderlyingObject(S->getPointerOperand()) == Ptr; 565218893Sdim } 566218893Sdim if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) { 567218893Sdim if (MI->isVolatile()) return false; 568218893Sdim 569218893Sdim // FIXME: check whether it has a valuerange that excludes zero? 570218893Sdim ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength()); 571218893Sdim if (!Len || Len->isZero()) return false; 572218893Sdim 573223017Sdim if (MI->getDestAddressSpace() == 0) 574245431Sdim if (GetUnderlyingObject(MI->getRawDest()) == Ptr) 575223017Sdim return true; 576218893Sdim if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) 577223017Sdim if (MTI->getSourceAddressSpace() == 0) 578245431Sdim if (GetUnderlyingObject(MTI->getRawSource()) == Ptr) 579223017Sdim return true; 580218893Sdim } 581218893Sdim return false; 582218893Sdim} 583218893Sdim 584218893Sdimbool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV, 585218893Sdim Value *Val, BasicBlock *BB) { 586218893Sdim LVILatticeVal Result; // Start Undefined. 587218893Sdim 588218893Sdim // If this is a pointer, and there's a load from that pointer in this BB, 589218893Sdim // then we know that the pointer can't be NULL. 590218893Sdim bool NotNull = false; 591218893Sdim if (Val->getType()->isPointerTy()) { 592245431Sdim if (isKnownNonNull(Val)) { 593218893Sdim NotNull = true; 594218893Sdim } else { 595245431Sdim Value *UnderlyingVal = GetUnderlyingObject(Val); 596245431Sdim // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge 597245431Sdim // inside InstructionDereferencesPointer either. 598245431Sdim if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, NULL, 1)) { 599245431Sdim for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); 600245431Sdim BI != BE; ++BI) { 601245431Sdim if (InstructionDereferencesPointer(BI, UnderlyingVal)) { 602245431Sdim NotNull = true; 603245431Sdim break; 604245431Sdim } 605218893Sdim } 606218893Sdim } 607218893Sdim } 608218893Sdim } 609218893Sdim 610218893Sdim // If this is the entry block, we must be asking about an argument. The 611218893Sdim // value is overdefined. 612218893Sdim if (BB == &BB->getParent()->getEntryBlock()) { 613218893Sdim assert(isa<Argument>(Val) && "Unknown live-in to the entry block"); 614218893Sdim if (NotNull) { 615226890Sdim PointerType *PTy = cast<PointerType>(Val->getType()); 616218893Sdim Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy)); 617218893Sdim } else { 618218893Sdim Result.markOverdefined(); 619218893Sdim } 620218893Sdim BBLV = Result; 621218893Sdim return true; 622218893Sdim } 623218893Sdim 624218893Sdim // Loop over all of our predecessors, merging what we know from them into 625218893Sdim // result. 626218893Sdim bool EdgesMissing = false; 627218893Sdim for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 628218893Sdim LVILatticeVal EdgeResult; 629218893Sdim EdgesMissing |= !getEdgeValue(Val, *PI, BB, EdgeResult); 630218893Sdim if (EdgesMissing) 631218893Sdim continue; 632218893Sdim 633218893Sdim Result.mergeIn(EdgeResult); 634218893Sdim 635218893Sdim // If we hit overdefined, exit early. The BlockVals entry is already set 636218893Sdim // to overdefined. 637218893Sdim if (Result.isOverdefined()) { 638218893Sdim DEBUG(dbgs() << " compute BB '" << BB->getName() 639218893Sdim << "' - overdefined because of pred.\n"); 640218893Sdim // If we previously determined that this is a pointer that can't be null 641218893Sdim // then return that rather than giving up entirely. 642218893Sdim if (NotNull) { 643226890Sdim PointerType *PTy = cast<PointerType>(Val->getType()); 644218893Sdim Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy)); 645218893Sdim } 646218893Sdim 647218893Sdim BBLV = Result; 648218893Sdim return true; 649218893Sdim } 650218893Sdim } 651218893Sdim if (EdgesMissing) 652218893Sdim return false; 653218893Sdim 654218893Sdim // Return the merged value, which is more precise than 'overdefined'. 655218893Sdim assert(!Result.isOverdefined()); 656218893Sdim BBLV = Result; 657218893Sdim return true; 658218893Sdim} 659218893Sdim 660218893Sdimbool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV, 661218893Sdim PHINode *PN, BasicBlock *BB) { 662218893Sdim LVILatticeVal Result; // Start Undefined. 663218893Sdim 664218893Sdim // Loop over all of our predecessors, merging what we know from them into 665218893Sdim // result. 666218893Sdim bool EdgesMissing = false; 667218893Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 668218893Sdim BasicBlock *PhiBB = PN->getIncomingBlock(i); 669218893Sdim Value *PhiVal = PN->getIncomingValue(i); 670218893Sdim LVILatticeVal EdgeResult; 671218893Sdim EdgesMissing |= !getEdgeValue(PhiVal, PhiBB, BB, EdgeResult); 672218893Sdim if (EdgesMissing) 673218893Sdim continue; 674218893Sdim 675218893Sdim Result.mergeIn(EdgeResult); 676218893Sdim 677218893Sdim // If we hit overdefined, exit early. The BlockVals entry is already set 678218893Sdim // to overdefined. 679218893Sdim if (Result.isOverdefined()) { 680218893Sdim DEBUG(dbgs() << " compute BB '" << BB->getName() 681218893Sdim << "' - overdefined because of pred.\n"); 682218893Sdim 683218893Sdim BBLV = Result; 684218893Sdim return true; 685218893Sdim } 686218893Sdim } 687218893Sdim if (EdgesMissing) 688218893Sdim return false; 689218893Sdim 690218893Sdim // Return the merged value, which is more precise than 'overdefined'. 691218893Sdim assert(!Result.isOverdefined() && "Possible PHI in entry block?"); 692218893Sdim BBLV = Result; 693218893Sdim return true; 694218893Sdim} 695218893Sdim 696218893Sdimbool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV, 697218893Sdim Instruction *BBI, 698218893Sdim BasicBlock *BB) { 699212904Sdim // Figure out the range of the LHS. If that fails, bail. 700218893Sdim if (!hasBlockValue(BBI->getOperand(0), BB)) { 701218893Sdim BlockValueStack.push(std::make_pair(BB, BBI->getOperand(0))); 702218893Sdim return false; 703218893Sdim } 704218893Sdim 705218893Sdim LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB); 706212904Sdim if (!LHSVal.isConstantRange()) { 707218893Sdim BBLV.markOverdefined(); 708218893Sdim return true; 709212904Sdim } 710212904Sdim 711212904Sdim ConstantRange LHSRange = LHSVal.getConstantRange(); 712212904Sdim ConstantRange RHSRange(1); 713226890Sdim IntegerType *ResultTy = cast<IntegerType>(BBI->getType()); 714212904Sdim if (isa<BinaryOperator>(BBI)) { 715218893Sdim if (ConstantInt *RHS = dyn_cast<ConstantInt>(BBI->getOperand(1))) { 716218893Sdim RHSRange = ConstantRange(RHS->getValue()); 717218893Sdim } else { 718218893Sdim BBLV.markOverdefined(); 719218893Sdim return true; 720212904Sdim } 721212904Sdim } 722218893Sdim 723212904Sdim // NOTE: We're currently limited by the set of operations that ConstantRange 724212904Sdim // can evaluate symbolically. Enhancing that set will allows us to analyze 725212904Sdim // more definitions. 726218893Sdim LVILatticeVal Result; 727212904Sdim switch (BBI->getOpcode()) { 728212904Sdim case Instruction::Add: 729212904Sdim Result.markConstantRange(LHSRange.add(RHSRange)); 730212904Sdim break; 731212904Sdim case Instruction::Sub: 732212904Sdim Result.markConstantRange(LHSRange.sub(RHSRange)); 733212904Sdim break; 734212904Sdim case Instruction::Mul: 735212904Sdim Result.markConstantRange(LHSRange.multiply(RHSRange)); 736212904Sdim break; 737212904Sdim case Instruction::UDiv: 738212904Sdim Result.markConstantRange(LHSRange.udiv(RHSRange)); 739212904Sdim break; 740212904Sdim case Instruction::Shl: 741212904Sdim Result.markConstantRange(LHSRange.shl(RHSRange)); 742212904Sdim break; 743212904Sdim case Instruction::LShr: 744212904Sdim Result.markConstantRange(LHSRange.lshr(RHSRange)); 745212904Sdim break; 746212904Sdim case Instruction::Trunc: 747212904Sdim Result.markConstantRange(LHSRange.truncate(ResultTy->getBitWidth())); 748212904Sdim break; 749212904Sdim case Instruction::SExt: 750212904Sdim Result.markConstantRange(LHSRange.signExtend(ResultTy->getBitWidth())); 751212904Sdim break; 752212904Sdim case Instruction::ZExt: 753212904Sdim Result.markConstantRange(LHSRange.zeroExtend(ResultTy->getBitWidth())); 754212904Sdim break; 755212904Sdim case Instruction::BitCast: 756212904Sdim Result.markConstantRange(LHSRange); 757212904Sdim break; 758218893Sdim case Instruction::And: 759218893Sdim Result.markConstantRange(LHSRange.binaryAnd(RHSRange)); 760218893Sdim break; 761218893Sdim case Instruction::Or: 762218893Sdim Result.markConstantRange(LHSRange.binaryOr(RHSRange)); 763218893Sdim break; 764212904Sdim 765212904Sdim // Unhandled instructions are overdefined. 766212904Sdim default: 767212904Sdim DEBUG(dbgs() << " compute BB '" << BB->getName() 768212904Sdim << "' - overdefined because inst def found.\n"); 769212904Sdim Result.markOverdefined(); 770212904Sdim break; 771212904Sdim } 772212904Sdim 773218893Sdim BBLV = Result; 774218893Sdim return true; 775199481Srdivacky} 776199481Srdivacky 777245431Sdim/// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if 778245431Sdim/// Val is not constrained on the edge. 779245431Sdimstatic bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, 780245431Sdim BasicBlock *BBTo, LVILatticeVal &Result) { 781199481Srdivacky // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we 782199481Srdivacky // know that v != 0. 783199481Srdivacky if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) { 784199481Srdivacky // If this is a conditional branch and only one successor goes to BBTo, then 785199481Srdivacky // we maybe able to infer something from the condition. 786199481Srdivacky if (BI->isConditional() && 787199481Srdivacky BI->getSuccessor(0) != BI->getSuccessor(1)) { 788199481Srdivacky bool isTrueDest = BI->getSuccessor(0) == BBTo; 789199481Srdivacky assert(BI->getSuccessor(!isTrueDest) == BBTo && 790199481Srdivacky "BBTo isn't a successor of BBFrom"); 791199481Srdivacky 792199481Srdivacky // If V is the condition of the branch itself, then we know exactly what 793199481Srdivacky // it is. 794218893Sdim if (BI->getCondition() == Val) { 795218893Sdim Result = LVILatticeVal::get(ConstantInt::get( 796212904Sdim Type::getInt1Ty(Val->getContext()), isTrueDest)); 797218893Sdim return true; 798218893Sdim } 799199481Srdivacky 800199481Srdivacky // If the condition of the branch is an equality comparison, we may be 801199481Srdivacky // able to infer the value. 802212904Sdim ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition()); 803235633Sdim if (ICI && isa<Constant>(ICI->getOperand(1))) { 804235633Sdim if (ICI->isEquality() && ICI->getOperand(0) == Val) { 805199481Srdivacky // We know that V has the RHS constant if this is a true SETEQ or 806199481Srdivacky // false SETNE. 807199481Srdivacky if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ)) 808218893Sdim Result = LVILatticeVal::get(cast<Constant>(ICI->getOperand(1))); 809218893Sdim else 810218893Sdim Result = LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1))); 811218893Sdim return true; 812199481Srdivacky } 813218893Sdim 814235633Sdim // Recognize the range checking idiom that InstCombine produces. 815235633Sdim // (X-C1) u< C2 --> [C1, C1+C2) 816235633Sdim ConstantInt *NegOffset = 0; 817235633Sdim if (ICI->getPredicate() == ICmpInst::ICMP_ULT) 818235633Sdim match(ICI->getOperand(0), m_Add(m_Specific(Val), 819235633Sdim m_ConstantInt(NegOffset))); 820235633Sdim 821235633Sdim ConstantInt *CI = dyn_cast<ConstantInt>(ICI->getOperand(1)); 822235633Sdim if (CI && (ICI->getOperand(0) == Val || NegOffset)) { 823212904Sdim // Calculate the range of values that would satisfy the comparison. 824245431Sdim ConstantRange CmpRange(CI->getValue()); 825212904Sdim ConstantRange TrueValues = 826212904Sdim ConstantRange::makeICmpRegion(ICI->getPredicate(), CmpRange); 827218893Sdim 828235633Sdim if (NegOffset) // Apply the offset from above. 829235633Sdim TrueValues = TrueValues.subtract(NegOffset->getValue()); 830235633Sdim 831212904Sdim // If we're interested in the false dest, invert the condition. 832212904Sdim if (!isTrueDest) TrueValues = TrueValues.inverse(); 833218893Sdim 834245431Sdim Result = LVILatticeVal::getRange(TrueValues); 835218893Sdim return true; 836212904Sdim } 837212904Sdim } 838199481Srdivacky } 839199481Srdivacky } 840199481Srdivacky 841199481Srdivacky // If the edge was formed by a switch on the value, then we may know exactly 842199481Srdivacky // what it is. 843199481Srdivacky if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) { 844245431Sdim if (SI->getCondition() != Val) 845245431Sdim return false; 846245431Sdim 847245431Sdim bool DefaultCase = SI->getDefaultDest() == BBTo; 848245431Sdim unsigned BitWidth = Val->getType()->getIntegerBitWidth(); 849245431Sdim ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/); 850245431Sdim 851245431Sdim for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); 852245431Sdim i != e; ++i) { 853245431Sdim ConstantRange EdgeVal(i.getCaseValue()->getValue()); 854245431Sdim if (DefaultCase) { 855245431Sdim // It is possible that the default destination is the destination of 856245431Sdim // some cases. There is no need to perform difference for those cases. 857245431Sdim if (i.getCaseSuccessor() != BBTo) 858245431Sdim EdgesVals = EdgesVals.difference(EdgeVal); 859245431Sdim } else if (i.getCaseSuccessor() == BBTo) 860245431Sdim EdgesVals = EdgesVals.unionWith(EdgeVal); 861199481Srdivacky } 862245431Sdim Result = LVILatticeVal::getRange(EdgesVals); 863218893Sdim return true; 864218893Sdim } 865218893Sdim return false; 866199481Srdivacky} 867199481Srdivacky 868245431Sdim/// \brief Compute the value of Val on the edge BBFrom -> BBTo, or the value at 869245431Sdim/// the basic block if the edge does not constraint Val. 870245431Sdimbool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom, 871245431Sdim BasicBlock *BBTo, LVILatticeVal &Result) { 872245431Sdim // If already a constant, there is nothing to compute. 873245431Sdim if (Constant *VC = dyn_cast<Constant>(Val)) { 874245431Sdim Result = LVILatticeVal::get(VC); 875245431Sdim return true; 876245431Sdim } 877245431Sdim 878245431Sdim if (getEdgeValueLocal(Val, BBFrom, BBTo, Result)) { 879245431Sdim if (!Result.isConstantRange() || 880245431Sdim Result.getConstantRange().getSingleElement()) 881245431Sdim return true; 882245431Sdim 883245431Sdim // FIXME: this check should be moved to the beginning of the function when 884245431Sdim // LVI better supports recursive values. Even for the single value case, we 885245431Sdim // can intersect to detect dead code (an empty range). 886245431Sdim if (!hasBlockValue(Val, BBFrom)) { 887245431Sdim BlockValueStack.push(std::make_pair(BBFrom, Val)); 888245431Sdim return false; 889245431Sdim } 890245431Sdim 891245431Sdim // Try to intersect ranges of the BB and the constraint on the edge. 892245431Sdim LVILatticeVal InBlock = getBlockValue(Val, BBFrom); 893245431Sdim if (!InBlock.isConstantRange()) 894245431Sdim return true; 895245431Sdim 896245431Sdim ConstantRange Range = 897245431Sdim Result.getConstantRange().intersectWith(InBlock.getConstantRange()); 898245431Sdim Result = LVILatticeVal::getRange(Range); 899245431Sdim return true; 900245431Sdim } 901245431Sdim 902245431Sdim if (!hasBlockValue(Val, BBFrom)) { 903245431Sdim BlockValueStack.push(std::make_pair(BBFrom, Val)); 904245431Sdim return false; 905245431Sdim } 906245431Sdim 907245431Sdim // if we couldn't compute the value on the edge, use the value from the BB 908245431Sdim Result = getBlockValue(Val, BBFrom); 909245431Sdim return true; 910245431Sdim} 911245431Sdim 912199481SrdivackyLVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB) { 913201360Srdivacky DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '" 914199481Srdivacky << BB->getName() << "'\n"); 915199481Srdivacky 916218893Sdim BlockValueStack.push(std::make_pair(BB, V)); 917218893Sdim solve(); 918218893Sdim LVILatticeVal Result = getBlockValue(V, BB); 919218893Sdim 920201360Srdivacky DEBUG(dbgs() << " Result = " << Result << "\n"); 921199481Srdivacky return Result; 922199481Srdivacky} 923199481Srdivacky 924199481SrdivackyLVILatticeVal LazyValueInfoCache:: 925199481SrdivackygetValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB) { 926201360Srdivacky DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '" 927199481Srdivacky << FromBB->getName() << "' to '" << ToBB->getName() << "'\n"); 928212904Sdim 929218893Sdim LVILatticeVal Result; 930218893Sdim if (!getEdgeValue(V, FromBB, ToBB, Result)) { 931218893Sdim solve(); 932218893Sdim bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result); 933218893Sdim (void)WasFastQuery; 934218893Sdim assert(WasFastQuery && "More work to do after problem solved?"); 935218893Sdim } 936218893Sdim 937201360Srdivacky DEBUG(dbgs() << " Result = " << Result << "\n"); 938199481Srdivacky return Result; 939199481Srdivacky} 940199481Srdivacky 941212904Sdimvoid LazyValueInfoCache::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, 942212904Sdim BasicBlock *NewSucc) { 943212904Sdim // When an edge in the graph has been threaded, values that we could not 944212904Sdim // determine a value for before (i.e. were marked overdefined) may be possible 945212904Sdim // to solve now. We do NOT try to proactively update these values. Instead, 946212904Sdim // we clear their entries from the cache, and allow lazy updating to recompute 947212904Sdim // them when needed. 948212904Sdim 949212904Sdim // The updating process is fairly simple: we need to dropped cached info 950212904Sdim // for all values that were marked overdefined in OldSucc, and for those same 951212904Sdim // values in any successor of OldSucc (except NewSucc) in which they were 952212904Sdim // also marked overdefined. 953212904Sdim std::vector<BasicBlock*> worklist; 954212904Sdim worklist.push_back(OldSucc); 955212904Sdim 956212904Sdim DenseSet<Value*> ClearSet; 957218893Sdim for (DenseSet<OverDefinedPairTy>::iterator I = OverDefinedCache.begin(), 958218893Sdim E = OverDefinedCache.end(); I != E; ++I) { 959212904Sdim if (I->first == OldSucc) 960212904Sdim ClearSet.insert(I->second); 961212904Sdim } 962212904Sdim 963212904Sdim // Use a worklist to perform a depth-first search of OldSucc's successors. 964212904Sdim // NOTE: We do not need a visited list since any blocks we have already 965212904Sdim // visited will have had their overdefined markers cleared already, and we 966212904Sdim // thus won't loop to their successors. 967212904Sdim while (!worklist.empty()) { 968212904Sdim BasicBlock *ToUpdate = worklist.back(); 969212904Sdim worklist.pop_back(); 970212904Sdim 971212904Sdim // Skip blocks only accessible through NewSucc. 972212904Sdim if (ToUpdate == NewSucc) continue; 973212904Sdim 974212904Sdim bool changed = false; 975218893Sdim for (DenseSet<Value*>::iterator I = ClearSet.begin(), E = ClearSet.end(); 976212904Sdim I != E; ++I) { 977212904Sdim // If a value was marked overdefined in OldSucc, and is here too... 978218893Sdim DenseSet<OverDefinedPairTy>::iterator OI = 979212904Sdim OverDefinedCache.find(std::make_pair(ToUpdate, *I)); 980212904Sdim if (OI == OverDefinedCache.end()) continue; 981212904Sdim 982212904Sdim // Remove it from the caches. 983212904Sdim ValueCacheEntryTy &Entry = ValueCache[LVIValueHandle(*I, this)]; 984212904Sdim ValueCacheEntryTy::iterator CI = Entry.find(ToUpdate); 985218893Sdim 986212904Sdim assert(CI != Entry.end() && "Couldn't find entry to update?"); 987212904Sdim Entry.erase(CI); 988212904Sdim OverDefinedCache.erase(OI); 989212904Sdim 990212904Sdim // If we removed anything, then we potentially need to update 991212904Sdim // blocks successors too. 992212904Sdim changed = true; 993212904Sdim } 994218893Sdim 995212904Sdim if (!changed) continue; 996212904Sdim 997212904Sdim worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate)); 998212904Sdim } 999212904Sdim} 1000212904Sdim 1001199481Srdivacky//===----------------------------------------------------------------------===// 1002199481Srdivacky// LazyValueInfo Impl 1003199481Srdivacky//===----------------------------------------------------------------------===// 1004199481Srdivacky 1005199481Srdivacky/// getCache - This lazily constructs the LazyValueInfoCache. 1006199481Srdivackystatic LazyValueInfoCache &getCache(void *&PImpl) { 1007199481Srdivacky if (!PImpl) 1008199481Srdivacky PImpl = new LazyValueInfoCache(); 1009199481Srdivacky return *static_cast<LazyValueInfoCache*>(PImpl); 1010199481Srdivacky} 1011199481Srdivacky 1012212904Sdimbool LazyValueInfo::runOnFunction(Function &F) { 1013212904Sdim if (PImpl) 1014212904Sdim getCache(PImpl).clear(); 1015235633Sdim 1016245431Sdim TD = getAnalysisIfAvailable<DataLayout>(); 1017235633Sdim TLI = &getAnalysis<TargetLibraryInfo>(); 1018235633Sdim 1019212904Sdim // Fully lazy. 1020212904Sdim return false; 1021212904Sdim} 1022212904Sdim 1023235633Sdimvoid LazyValueInfo::getAnalysisUsage(AnalysisUsage &AU) const { 1024235633Sdim AU.setPreservesAll(); 1025235633Sdim AU.addRequired<TargetLibraryInfo>(); 1026235633Sdim} 1027235633Sdim 1028199481Srdivackyvoid LazyValueInfo::releaseMemory() { 1029199481Srdivacky // If the cache was allocated, free it. 1030199481Srdivacky if (PImpl) { 1031199481Srdivacky delete &getCache(PImpl); 1032199481Srdivacky PImpl = 0; 1033199481Srdivacky } 1034199481Srdivacky} 1035199481Srdivacky 1036199481SrdivackyConstant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB) { 1037199481Srdivacky LVILatticeVal Result = getCache(PImpl).getValueInBlock(V, BB); 1038199481Srdivacky 1039199481Srdivacky if (Result.isConstant()) 1040199481Srdivacky return Result.getConstant(); 1041218893Sdim if (Result.isConstantRange()) { 1042212904Sdim ConstantRange CR = Result.getConstantRange(); 1043212904Sdim if (const APInt *SingleVal = CR.getSingleElement()) 1044212904Sdim return ConstantInt::get(V->getContext(), *SingleVal); 1045212904Sdim } 1046199481Srdivacky return 0; 1047199481Srdivacky} 1048199481Srdivacky 1049199481Srdivacky/// getConstantOnEdge - Determine whether the specified value is known to be a 1050199481Srdivacky/// constant on the specified edge. Return null if not. 1051199481SrdivackyConstant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB, 1052199481Srdivacky BasicBlock *ToBB) { 1053199481Srdivacky LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB); 1054199481Srdivacky 1055199481Srdivacky if (Result.isConstant()) 1056199481Srdivacky return Result.getConstant(); 1057218893Sdim if (Result.isConstantRange()) { 1058212904Sdim ConstantRange CR = Result.getConstantRange(); 1059212904Sdim if (const APInt *SingleVal = CR.getSingleElement()) 1060212904Sdim return ConstantInt::get(V->getContext(), *SingleVal); 1061212904Sdim } 1062199481Srdivacky return 0; 1063199481Srdivacky} 1064199481Srdivacky 1065199481Srdivacky/// getPredicateOnEdge - Determine whether the specified value comparison 1066199481Srdivacky/// with a constant is known to be true or false on the specified CFG edge. 1067199481Srdivacky/// Pred is a CmpInst predicate. 1068199481SrdivackyLazyValueInfo::Tristate 1069199481SrdivackyLazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, 1070199481Srdivacky BasicBlock *FromBB, BasicBlock *ToBB) { 1071199481Srdivacky LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB); 1072199481Srdivacky 1073199481Srdivacky // If we know the value is a constant, evaluate the conditional. 1074199481Srdivacky Constant *Res = 0; 1075199481Srdivacky if (Result.isConstant()) { 1076235633Sdim Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, TD, 1077235633Sdim TLI); 1078218893Sdim if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res)) 1079199481Srdivacky return ResCI->isZero() ? False : True; 1080199481Srdivacky return Unknown; 1081199481Srdivacky } 1082199481Srdivacky 1083212904Sdim if (Result.isConstantRange()) { 1084212904Sdim ConstantInt *CI = dyn_cast<ConstantInt>(C); 1085212904Sdim if (!CI) return Unknown; 1086212904Sdim 1087212904Sdim ConstantRange CR = Result.getConstantRange(); 1088212904Sdim if (Pred == ICmpInst::ICMP_EQ) { 1089212904Sdim if (!CR.contains(CI->getValue())) 1090212904Sdim return False; 1091212904Sdim 1092212904Sdim if (CR.isSingleElement() && CR.contains(CI->getValue())) 1093212904Sdim return True; 1094212904Sdim } else if (Pred == ICmpInst::ICMP_NE) { 1095212904Sdim if (!CR.contains(CI->getValue())) 1096212904Sdim return True; 1097212904Sdim 1098212904Sdim if (CR.isSingleElement() && CR.contains(CI->getValue())) 1099212904Sdim return False; 1100212904Sdim } 1101212904Sdim 1102212904Sdim // Handle more complex predicates. 1103218893Sdim ConstantRange TrueValues = 1104218893Sdim ICmpInst::makeConstantRange((ICmpInst::Predicate)Pred, CI->getValue()); 1105218893Sdim if (TrueValues.contains(CR)) 1106218893Sdim return True; 1107218893Sdim if (TrueValues.inverse().contains(CR)) 1108212904Sdim return False; 1109212904Sdim return Unknown; 1110212904Sdim } 1111212904Sdim 1112199481Srdivacky if (Result.isNotConstant()) { 1113199481Srdivacky // If this is an equality comparison, we can try to fold it knowing that 1114199481Srdivacky // "V != C1". 1115199481Srdivacky if (Pred == ICmpInst::ICMP_EQ) { 1116199481Srdivacky // !C1 == C -> false iff C1 == C. 1117199481Srdivacky Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE, 1118235633Sdim Result.getNotConstant(), C, TD, 1119235633Sdim TLI); 1120199481Srdivacky if (Res->isNullValue()) 1121199481Srdivacky return False; 1122199481Srdivacky } else if (Pred == ICmpInst::ICMP_NE) { 1123199481Srdivacky // !C1 != C -> true iff C1 == C. 1124199481Srdivacky Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE, 1125235633Sdim Result.getNotConstant(), C, TD, 1126235633Sdim TLI); 1127199481Srdivacky if (Res->isNullValue()) 1128199481Srdivacky return True; 1129199481Srdivacky } 1130199481Srdivacky return Unknown; 1131199481Srdivacky } 1132199481Srdivacky 1133199481Srdivacky return Unknown; 1134199481Srdivacky} 1135199481Srdivacky 1136212904Sdimvoid LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, 1137218893Sdim BasicBlock *NewSucc) { 1138212904Sdim if (PImpl) getCache(PImpl).threadEdge(PredBB, OldSucc, NewSucc); 1139212904Sdim} 1140199481Srdivacky 1141212904Sdimvoid LazyValueInfo::eraseBlock(BasicBlock *BB) { 1142212904Sdim if (PImpl) getCache(PImpl).eraseBlock(BB); 1143212904Sdim} 1144