1 //===- LazyValueInfo.cpp - Value constraint analysis ----------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the interface for lazy computation of value constraint
13 //===----------------------------------------------------------------------===//
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/PointerIntPair.h"
26 #include "llvm/ADT/STLExtras.h"
29 char LazyValueInfo::ID = 0;
30 static RegisterPass<LazyValueInfo>
31 X("lazy-value-info", "Lazy Value Information Analysis", false, true);
34 FunctionPass *createLazyValueInfoPass() { return new LazyValueInfo(); }
38 //===----------------------------------------------------------------------===//
40 //===----------------------------------------------------------------------===//
42 /// LVILatticeVal - This is the information tracked by LazyValueInfo for each
45 /// FIXME: This is basically just for bringup, this can be made a lot more rich
51 /// undefined - This LLVM Value has no known value yet.
53 /// constant - This LLVM Value has a specific constant value.
56 /// notconstant - This LLVM value is known to not have the specified value.
59 /// overdefined - This instruction is not known to be constant, and we know
64 /// Val: This stores the current lattice value along with the Constant* for
65 /// the constant if this is a 'constant' or 'notconstant' value.
66 PointerIntPair<Constant *, 2, LatticeValueTy> Val;
69 LVILatticeVal() : Val(0, undefined) {}
71 static LVILatticeVal get(Constant *C) {
76 static LVILatticeVal getNot(Constant *C) {
78 Res.markNotConstant(C);
82 bool isUndefined() const { return Val.getInt() == undefined; }
83 bool isConstant() const { return Val.getInt() == constant; }
84 bool isNotConstant() const { return Val.getInt() == notconstant; }
85 bool isOverdefined() const { return Val.getInt() == overdefined; }
87 Constant *getConstant() const {
88 assert(isConstant() && "Cannot get the constant of a non-constant!");
89 return Val.getPointer();
92 Constant *getNotConstant() const {
93 assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
94 return Val.getPointer();
97 /// markOverdefined - Return true if this is a change in status.
98 bool markOverdefined() {
101 Val.setInt(overdefined);
105 /// markConstant - Return true if this is a change in status.
106 bool markConstant(Constant *V) {
108 assert(getConstant() == V && "Marking constant with different value");
112 assert(isUndefined());
113 Val.setInt(constant);
114 assert(V && "Marking constant with NULL");
119 /// markNotConstant - Return true if this is a change in status.
120 bool markNotConstant(Constant *V) {
121 if (isNotConstant()) {
122 assert(getNotConstant() == V && "Marking !constant with different value");
127 assert(getConstant() != V && "Marking not constant with different value");
129 assert(isUndefined());
131 Val.setInt(notconstant);
132 assert(V && "Marking constant with NULL");
137 /// mergeIn - Merge the specified lattice value into this one, updating this
138 /// one and returning true if anything changed.
139 bool mergeIn(const LVILatticeVal &RHS) {
140 if (RHS.isUndefined() || isOverdefined()) return false;
141 if (RHS.isOverdefined()) return markOverdefined();
143 if (RHS.isNotConstant()) {
144 if (isNotConstant()) {
145 if (getNotConstant() != RHS.getNotConstant() ||
146 isa<ConstantExpr>(getNotConstant()) ||
147 isa<ConstantExpr>(RHS.getNotConstant()))
148 return markOverdefined();
152 if (getConstant() == RHS.getNotConstant() ||
153 isa<ConstantExpr>(RHS.getNotConstant()) ||
154 isa<ConstantExpr>(getConstant()))
155 return markOverdefined();
156 return markNotConstant(RHS.getNotConstant());
159 assert(isUndefined() && "Unexpected lattice");
160 return markNotConstant(RHS.getNotConstant());
163 // RHS must be a constant, we must be undef, constant, or notconstant.
165 return markConstant(RHS.getConstant());
168 if (getConstant() != RHS.getConstant())
169 return markOverdefined();
173 // If we are known "!=4" and RHS is "==5", stay at "!=4".
174 if (getNotConstant() == RHS.getConstant() ||
175 isa<ConstantExpr>(getNotConstant()) ||
176 isa<ConstantExpr>(RHS.getConstant()))
177 return markOverdefined();
183 } // end anonymous namespace.
186 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) {
187 if (Val.isUndefined())
188 return OS << "undefined";
189 if (Val.isOverdefined())
190 return OS << "overdefined";
192 if (Val.isNotConstant())
193 return OS << "notconstant<" << *Val.getNotConstant() << '>';
194 return OS << "constant<" << *Val.getConstant() << '>';
198 //===----------------------------------------------------------------------===//
199 // LazyValueInfoCache Decl
200 //===----------------------------------------------------------------------===//
203 /// LazyValueInfoCache - This is the cache kept by LazyValueInfo which
204 /// maintains information about queries across the clients' queries.
205 class LazyValueInfoCache {
207 /// BlockCacheEntryTy - This is a computed lattice value at the end of the
208 /// specified basic block for a Value* that depends on context.
209 typedef std::pair<BasicBlock*, LVILatticeVal> BlockCacheEntryTy;
211 /// ValueCacheEntryTy - This is all of the cached block information for
212 /// exactly one Value*. The entries are sorted by the BasicBlock* of the
213 /// entries, allowing us to do a lookup with a binary search.
214 typedef std::vector<BlockCacheEntryTy> ValueCacheEntryTy;
217 /// ValueCache - This is all of the cached information for all values,
218 /// mapped from Value* to key information.
219 DenseMap<Value*, ValueCacheEntryTy> ValueCache;
222 /// getValueInBlock - This is the query interface to determine the lattice
223 /// value for the specified Value* at the end of the specified block.
224 LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB);
226 /// getValueOnEdge - This is the query interface to determine the lattice
227 /// value for the specified Value* that is true on the specified edge.
228 LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB);
230 } // end anonymous namespace
233 struct BlockCacheEntryComparator {
234 static int Compare(const void *LHSv, const void *RHSv) {
235 const LazyValueInfoCache::BlockCacheEntryTy *LHS =
236 static_cast<const LazyValueInfoCache::BlockCacheEntryTy *>(LHSv);
237 const LazyValueInfoCache::BlockCacheEntryTy *RHS =
238 static_cast<const LazyValueInfoCache::BlockCacheEntryTy *>(RHSv);
239 if (LHS->first < RHS->first)
241 if (LHS->first > RHS->first)
246 bool operator()(const LazyValueInfoCache::BlockCacheEntryTy &LHS,
247 const LazyValueInfoCache::BlockCacheEntryTy &RHS) const {
248 return LHS.first < RHS.first;
253 //===----------------------------------------------------------------------===//
255 //===----------------------------------------------------------------------===//
258 /// LVIQuery - This is a transient object that exists while a query is
261 /// TODO: Reuse LVIQuery instead of recreating it for every query, this avoids
262 /// reallocation of the densemap on every query.
264 typedef LazyValueInfoCache::BlockCacheEntryTy BlockCacheEntryTy;
265 typedef LazyValueInfoCache::ValueCacheEntryTy ValueCacheEntryTy;
267 /// This is the current value being queried for.
270 /// This is all of the cached information about this value.
271 ValueCacheEntryTy &Cache;
273 /// NewBlocks - This is a mapping of the new BasicBlocks which have been
274 /// added to cache but that are not in sorted order.
275 DenseMap<BasicBlock*, LVILatticeVal> NewBlockInfo;
278 LVIQuery(Value *V, ValueCacheEntryTy &VC) : Val(V), Cache(VC) {
282 // When the query is done, insert the newly discovered facts into the
283 // cache in sorted order.
284 if (NewBlockInfo.empty()) return;
286 // Grow the cache to exactly fit the new data.
287 Cache.reserve(Cache.size() + NewBlockInfo.size());
289 // If we only have one new entry, insert it instead of doing a full-on
291 if (NewBlockInfo.size() == 1) {
292 BlockCacheEntryTy Entry = *NewBlockInfo.begin();
293 ValueCacheEntryTy::iterator I =
294 std::lower_bound(Cache.begin(), Cache.end(), Entry,
295 BlockCacheEntryComparator());
296 assert((I == Cache.end() || I->first != Entry.first) &&
297 "Entry already in map!");
299 Cache.insert(I, Entry);
303 // TODO: If we only have two new elements, INSERT them both.
305 Cache.insert(Cache.end(), NewBlockInfo.begin(), NewBlockInfo.end());
306 array_pod_sort(Cache.begin(), Cache.end(),
307 BlockCacheEntryComparator::Compare);
311 LVILatticeVal getBlockValue(BasicBlock *BB);
312 LVILatticeVal getEdgeValue(BasicBlock *FromBB, BasicBlock *ToBB);
315 LVILatticeVal &getCachedEntryForBlock(BasicBlock *BB);
317 } // end anonymous namespace
319 /// getCachedEntryForBlock - See if we already have a value for this block. If
320 /// so, return it, otherwise create a new entry in the NewBlockInfo map to use.
321 LVILatticeVal &LVIQuery::getCachedEntryForBlock(BasicBlock *BB) {
323 // Do a binary search to see if we already have an entry for this block in
324 // the cache set. If so, find it.
325 if (!Cache.empty()) {
326 ValueCacheEntryTy::iterator Entry =
327 std::lower_bound(Cache.begin(), Cache.end(),
328 BlockCacheEntryTy(BB, LVILatticeVal()),
329 BlockCacheEntryComparator());
330 if (Entry != Cache.end() && Entry->first == BB)
331 return Entry->second;
334 // Otherwise, check to see if it's in NewBlockInfo or create a new entry if
336 return NewBlockInfo[BB];
339 LVILatticeVal LVIQuery::getBlockValue(BasicBlock *BB) {
340 // See if we already have a value for this block.
341 LVILatticeVal &BBLV = getCachedEntryForBlock(BB);
343 // If we've already computed this block's value, return it.
344 if (!BBLV.isUndefined()) {
345 DEBUG(dbgs() << " reuse BB '" << BB->getName() << "' val=" << BBLV <<'\n');
349 // Otherwise, this is the first time we're seeing this block. Reset the
350 // lattice value to overdefined, so that cycles will terminate and be
351 // conservatively correct.
352 BBLV.markOverdefined();
354 // If V is live into BB, see if our predecessors know anything about it.
355 Instruction *BBI = dyn_cast<Instruction>(Val);
356 if (BBI == 0 || BBI->getParent() != BB) {
357 LVILatticeVal Result; // Start Undefined.
358 unsigned NumPreds = 0;
360 // Loop over all of our predecessors, merging what we know from them into
362 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
363 Result.mergeIn(getEdgeValue(*PI, BB));
365 // If we hit overdefined, exit early. The BlockVals entry is already set
367 if (Result.isOverdefined()) {
368 DEBUG(dbgs() << " compute BB '" << BB->getName()
369 << "' - overdefined because of pred.\n");
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();
383 // Return the merged value, which is more precise than 'overdefined'.
384 assert(!Result.isOverdefined());
385 return getCachedEntryForBlock(BB) = Result;
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)) {
392 // TODO: PHI Translation in preds.
397 DEBUG(dbgs() << " compute BB '" << BB->getName()
398 << "' - overdefined because inst def found.\n");
400 LVILatticeVal Result;
401 Result.markOverdefined();
402 return getCachedEntryForBlock(BB) = Result;
406 /// getEdgeValue - This method attempts to infer more complex
407 LVILatticeVal LVIQuery::getEdgeValue(BasicBlock *BBFrom, BasicBlock *BBTo) {
408 // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
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");
419 // If V is the condition of the branch itself, then we know exactly what
421 if (BI->getCondition() == Val)
422 return LVILatticeVal::get(ConstantInt::get(
423 Type::getInt1Ty(Val->getContext()), isTrueDest));
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
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)));
439 // If the edge was formed by a switch on the value, then we may know exactly
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
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);
454 assert(EdgeVal && "Missing successor?");
456 return LVILatticeVal::get(EdgeVal);
460 // Otherwise see if the value is known in the block.
461 return getBlockValue(BBFrom);
465 //===----------------------------------------------------------------------===//
466 // LazyValueInfoCache Impl
467 //===----------------------------------------------------------------------===//
469 LVILatticeVal 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);
474 DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
475 << BB->getName() << "'\n");
477 LVILatticeVal Result = LVIQuery(V, ValueCache[V]).getBlockValue(BB);
479 DEBUG(dbgs() << " Result = " << Result << "\n");
483 LVILatticeVal LazyValueInfoCache::
484 getValueOnEdge(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);
489 DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
490 << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
491 LVILatticeVal Result =
492 LVIQuery(V, ValueCache[V]).getEdgeValue(FromBB, ToBB);
494 DEBUG(dbgs() << " Result = " << Result << "\n");
499 //===----------------------------------------------------------------------===//
500 // LazyValueInfo Impl
501 //===----------------------------------------------------------------------===//
503 bool LazyValueInfo::runOnFunction(Function &F) {
504 TD = getAnalysisIfAvailable<TargetData>();
509 /// getCache - This lazily constructs the LazyValueInfoCache.
510 static LazyValueInfoCache &getCache(void *&PImpl) {
512 PImpl = new LazyValueInfoCache();
513 return *static_cast<LazyValueInfoCache*>(PImpl);
516 void LazyValueInfo::releaseMemory() {
517 // If the cache was allocated, free it.
519 delete &getCache(PImpl);
524 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB) {
525 LVILatticeVal Result = getCache(PImpl).getValueInBlock(V, BB);
527 if (Result.isConstant())
528 return Result.getConstant();
532 /// getConstantOnEdge - Determine whether the specified value is known to be a
533 /// constant on the specified edge. Return null if not.
534 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
536 LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB);
538 if (Result.isConstant())
539 return Result.getConstant();
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.
546 LazyValueInfo::Tristate
547 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
548 BasicBlock *FromBB, BasicBlock *ToBB) {
549 LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB);
551 // If we know the value is a constant, evaluate the conditional.
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;
560 if (Result.isNotConstant()) {
561 // If this is an equality comparison, we can try to fold it knowing that
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())
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())