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 INITIALIZE_PASS(LazyValueInfo, "lazy-value-info",
31 "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;
221 /// OverDefinedCache - This tracks, on a per-block basis, the set of
222 /// values that are over-defined at the end of that block. This is required
223 /// for cache updating.
224 DenseMap<BasicBlock*, std::set<Value*> > OverDefinedCache;
227 /// getValueInBlock - This is the query interface to determine the lattice
228 /// value for the specified Value* at the end of the specified block.
229 LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB);
231 /// getValueOnEdge - This is the query interface to determine the lattice
232 /// value for the specified Value* that is true on the specified edge.
233 LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB);
235 /// threadEdge - This is the update interface to inform the cache that an
236 /// edge from PredBB to OldSucc has been threaded to be from PredBB to
238 void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
240 } // end anonymous namespace
243 struct BlockCacheEntryComparator {
244 static int Compare(const void *LHSv, const void *RHSv) {
245 const LazyValueInfoCache::BlockCacheEntryTy *LHS =
246 static_cast<const LazyValueInfoCache::BlockCacheEntryTy *>(LHSv);
247 const LazyValueInfoCache::BlockCacheEntryTy *RHS =
248 static_cast<const LazyValueInfoCache::BlockCacheEntryTy *>(RHSv);
249 if (LHS->first < RHS->first)
251 if (LHS->first > RHS->first)
256 bool operator()(const LazyValueInfoCache::BlockCacheEntryTy &LHS,
257 const LazyValueInfoCache::BlockCacheEntryTy &RHS) const {
258 return LHS.first < RHS.first;
263 //===----------------------------------------------------------------------===//
265 //===----------------------------------------------------------------------===//
268 /// LVIQuery - This is a transient object that exists while a query is
271 /// TODO: Reuse LVIQuery instead of recreating it for every query, this avoids
272 /// reallocation of the densemap on every query.
274 typedef LazyValueInfoCache::BlockCacheEntryTy BlockCacheEntryTy;
275 typedef LazyValueInfoCache::ValueCacheEntryTy ValueCacheEntryTy;
277 /// This is the current value being queried for.
280 /// This is all of the cached information about this value.
281 ValueCacheEntryTy &Cache;
283 /// This tracks, for each block, what values are overdefined.
284 DenseMap<BasicBlock*, std::set<Value*> > &OverDefinedCache;
286 /// NewBlocks - This is a mapping of the new BasicBlocks which have been
287 /// added to cache but that are not in sorted order.
288 DenseMap<BasicBlock*, LVILatticeVal> NewBlockInfo;
291 LVIQuery(Value *V, ValueCacheEntryTy &VC,
292 DenseMap<BasicBlock*, std::set<Value*> > &ODC)
293 : Val(V), Cache(VC), OverDefinedCache(ODC) {
297 // When the query is done, insert the newly discovered facts into the
298 // cache in sorted order.
299 if (NewBlockInfo.empty()) return;
301 // Grow the cache to exactly fit the new data.
302 Cache.reserve(Cache.size() + NewBlockInfo.size());
304 // If we only have one new entry, insert it instead of doing a full-on
306 if (NewBlockInfo.size() == 1) {
307 BlockCacheEntryTy Entry = *NewBlockInfo.begin();
308 ValueCacheEntryTy::iterator I =
309 std::lower_bound(Cache.begin(), Cache.end(), Entry,
310 BlockCacheEntryComparator());
311 assert((I == Cache.end() || I->first != Entry.first) &&
312 "Entry already in map!");
314 Cache.insert(I, Entry);
318 // TODO: If we only have two new elements, INSERT them both.
320 Cache.insert(Cache.end(), NewBlockInfo.begin(), NewBlockInfo.end());
321 array_pod_sort(Cache.begin(), Cache.end(),
322 BlockCacheEntryComparator::Compare);
324 for (DenseMap<BasicBlock*, LVILatticeVal>::iterator
325 I = NewBlockInfo.begin(), E = NewBlockInfo.end(); I != E; ++I) {
326 if (I->second.isOverdefined())
327 OverDefinedCache[I->first].insert(Val);
331 LVILatticeVal getBlockValue(BasicBlock *BB);
332 LVILatticeVal getEdgeValue(BasicBlock *FromBB, BasicBlock *ToBB);
335 LVILatticeVal &getCachedEntryForBlock(BasicBlock *BB);
337 } // end anonymous namespace
339 /// getCachedEntryForBlock - See if we already have a value for this block. If
340 /// so, return it, otherwise create a new entry in the NewBlockInfo map to use.
341 LVILatticeVal &LVIQuery::getCachedEntryForBlock(BasicBlock *BB) {
343 // Do a binary search to see if we already have an entry for this block in
344 // the cache set. If so, find it.
345 if (!Cache.empty()) {
346 ValueCacheEntryTy::iterator Entry =
347 std::lower_bound(Cache.begin(), Cache.end(),
348 BlockCacheEntryTy(BB, LVILatticeVal()),
349 BlockCacheEntryComparator());
350 if (Entry != Cache.end() && Entry->first == BB)
351 return Entry->second;
354 // Otherwise, check to see if it's in NewBlockInfo or create a new entry if
356 return NewBlockInfo[BB];
359 LVILatticeVal LVIQuery::getBlockValue(BasicBlock *BB) {
360 // See if we already have a value for this block.
361 LVILatticeVal &BBLV = getCachedEntryForBlock(BB);
363 // If we've already computed this block's value, return it.
364 if (!BBLV.isUndefined()) {
365 DEBUG(dbgs() << " reuse BB '" << BB->getName() << "' val=" << BBLV <<'\n');
369 // Otherwise, this is the first time we're seeing this block. Reset the
370 // lattice value to overdefined, so that cycles will terminate and be
371 // conservatively correct.
372 BBLV.markOverdefined();
374 // If V is live into BB, see if our predecessors know anything about it.
375 Instruction *BBI = dyn_cast<Instruction>(Val);
376 if (BBI == 0 || BBI->getParent() != BB) {
377 LVILatticeVal Result; // Start Undefined.
378 unsigned NumPreds = 0;
380 // Loop over all of our predecessors, merging what we know from them into
382 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
383 Result.mergeIn(getEdgeValue(*PI, BB));
385 // If we hit overdefined, exit early. The BlockVals entry is already set
387 if (Result.isOverdefined()) {
388 DEBUG(dbgs() << " compute BB '" << BB->getName()
389 << "' - overdefined because of pred.\n");
395 // If this is the entry block, we must be asking about an argument. The
396 // value is overdefined.
397 if (NumPreds == 0 && BB == &BB->getParent()->front()) {
398 assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
399 Result.markOverdefined();
403 // Return the merged value, which is more precise than 'overdefined'.
404 assert(!Result.isOverdefined());
405 return getCachedEntryForBlock(BB) = Result;
408 // If this value is defined by an instruction in this block, we have to
409 // process it here somehow or return overdefined.
410 if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
412 // TODO: PHI Translation in preds.
417 DEBUG(dbgs() << " compute BB '" << BB->getName()
418 << "' - overdefined because inst def found.\n");
420 LVILatticeVal Result;
421 Result.markOverdefined();
422 return getCachedEntryForBlock(BB) = Result;
426 /// getEdgeValue - This method attempts to infer more complex
427 LVILatticeVal LVIQuery::getEdgeValue(BasicBlock *BBFrom, BasicBlock *BBTo) {
428 // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
430 if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
431 // If this is a conditional branch and only one successor goes to BBTo, then
432 // we maybe able to infer something from the condition.
433 if (BI->isConditional() &&
434 BI->getSuccessor(0) != BI->getSuccessor(1)) {
435 bool isTrueDest = BI->getSuccessor(0) == BBTo;
436 assert(BI->getSuccessor(!isTrueDest) == BBTo &&
437 "BBTo isn't a successor of BBFrom");
439 // If V is the condition of the branch itself, then we know exactly what
441 if (BI->getCondition() == Val)
442 return LVILatticeVal::get(ConstantInt::get(
443 Type::getInt1Ty(Val->getContext()), isTrueDest));
445 // If the condition of the branch is an equality comparison, we may be
446 // able to infer the value.
447 if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition()))
448 if (ICI->isEquality() && ICI->getOperand(0) == Val &&
449 isa<Constant>(ICI->getOperand(1))) {
450 // We know that V has the RHS constant if this is a true SETEQ or
452 if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
453 return LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
454 return LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1)));
459 // If the edge was formed by a switch on the value, then we may know exactly
461 if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
462 // If BBTo is the default destination of the switch, we don't know anything.
463 // Given a more powerful range analysis we could know stuff.
464 if (SI->getCondition() == Val && SI->getDefaultDest() != BBTo) {
465 // We only know something if there is exactly one value that goes from
467 unsigned NumEdges = 0;
468 ConstantInt *EdgeVal = 0;
469 for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) {
470 if (SI->getSuccessor(i) != BBTo) continue;
471 if (NumEdges++) break;
472 EdgeVal = SI->getCaseValue(i);
474 assert(EdgeVal && "Missing successor?");
476 return LVILatticeVal::get(EdgeVal);
480 // Otherwise see if the value is known in the block.
481 return getBlockValue(BBFrom);
485 //===----------------------------------------------------------------------===//
486 // LazyValueInfoCache Impl
487 //===----------------------------------------------------------------------===//
489 LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB) {
490 // If already a constant, there is nothing to compute.
491 if (Constant *VC = dyn_cast<Constant>(V))
492 return LVILatticeVal::get(VC);
494 DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
495 << BB->getName() << "'\n");
497 LVILatticeVal Result = LVIQuery(V, ValueCache[V],
498 OverDefinedCache).getBlockValue(BB);
500 DEBUG(dbgs() << " Result = " << Result << "\n");
504 LVILatticeVal LazyValueInfoCache::
505 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB) {
506 // If already a constant, there is nothing to compute.
507 if (Constant *VC = dyn_cast<Constant>(V))
508 return LVILatticeVal::get(VC);
510 DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
511 << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
513 LVILatticeVal Result =
514 LVIQuery(V, ValueCache[V],
515 OverDefinedCache).getEdgeValue(FromBB, ToBB);
517 DEBUG(dbgs() << " Result = " << Result << "\n");
522 void LazyValueInfoCache::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
523 BasicBlock *NewSucc) {
524 // When an edge in the graph has been threaded, values that we could not
525 // determine a value for before (i.e. were marked overdefined) may be possible
526 // to solve now. We do NOT try to proactively update these values. Instead,
527 // we clear their entries from the cache, and allow lazy updating to recompute
530 // The updating process is fairly simple: we need to dropped cached info
531 // for all values that were marked overdefined in OldSucc, and for those same
532 // values in any successor of OldSucc (except NewSucc) in which they were
533 // also marked overdefined.
534 std::vector<BasicBlock*> worklist;
535 worklist.push_back(OldSucc);
537 std::set<Value*> ClearSet = OverDefinedCache[OldSucc];
538 LVILatticeVal OverDef;
539 OverDef.markOverdefined();
541 // Use a worklist to perform a depth-first search of OldSucc's successors.
542 // NOTE: We do not need a visited list since any blocks we have already
543 // visited will have had their overdefined markers cleared already, and we
544 // thus won't loop to their successors.
545 while (!worklist.empty()) {
546 BasicBlock *ToUpdate = worklist.back();
549 // Skip blocks only accessible through NewSucc.
550 if (ToUpdate == NewSucc) continue;
552 bool changed = false;
553 std::set<Value*> &CurrentSet = OverDefinedCache[ToUpdate];
554 for (std::set<Value*>::iterator I = ClearSet.begin(),E = ClearSet.end();
556 // If a value was marked overdefined in OldSucc, and is here too...
557 if (CurrentSet.count(*I)) {
558 // Remove it from the caches.
559 ValueCacheEntryTy &Entry = ValueCache[*I];
560 ValueCacheEntryTy::iterator CI =
561 std::lower_bound(Entry.begin(), Entry.end(),
562 std::make_pair(ToUpdate, OverDef),
563 BlockCacheEntryComparator());
564 assert(CI != Entry.end() && "Couldn't find entry to update?");
567 CurrentSet.erase(*I);
569 // If we removed anything, then we potentially need to update
570 // blocks successors too.
575 if (!changed) continue;
577 worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
581 //===----------------------------------------------------------------------===//
582 // LazyValueInfo Impl
583 //===----------------------------------------------------------------------===//
585 bool LazyValueInfo::runOnFunction(Function &F) {
586 TD = getAnalysisIfAvailable<TargetData>();
591 /// getCache - This lazily constructs the LazyValueInfoCache.
592 static LazyValueInfoCache &getCache(void *&PImpl) {
594 PImpl = new LazyValueInfoCache();
595 return *static_cast<LazyValueInfoCache*>(PImpl);
598 void LazyValueInfo::releaseMemory() {
599 // If the cache was allocated, free it.
601 delete &getCache(PImpl);
606 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB) {
607 LVILatticeVal Result = getCache(PImpl).getValueInBlock(V, BB);
609 if (Result.isConstant())
610 return Result.getConstant();
614 /// getConstantOnEdge - Determine whether the specified value is known to be a
615 /// constant on the specified edge. Return null if not.
616 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
618 LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB);
620 if (Result.isConstant())
621 return Result.getConstant();
625 /// getPredicateOnEdge - Determine whether the specified value comparison
626 /// with a constant is known to be true or false on the specified CFG edge.
627 /// Pred is a CmpInst predicate.
628 LazyValueInfo::Tristate
629 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
630 BasicBlock *FromBB, BasicBlock *ToBB) {
631 LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB);
633 // If we know the value is a constant, evaluate the conditional.
635 if (Result.isConstant()) {
636 Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, TD);
637 if (ConstantInt *ResCI = dyn_cast_or_null<ConstantInt>(Res))
638 return ResCI->isZero() ? False : True;
642 if (Result.isNotConstant()) {
643 // If this is an equality comparison, we can try to fold it knowing that
645 if (Pred == ICmpInst::ICMP_EQ) {
646 // !C1 == C -> false iff C1 == C.
647 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
648 Result.getNotConstant(), C, TD);
649 if (Res->isNullValue())
651 } else if (Pred == ICmpInst::ICMP_NE) {
652 // !C1 != C -> true iff C1 == C.
653 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
654 Result.getNotConstant(), C, TD);
655 if (Res->isNullValue())
664 void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
665 BasicBlock* NewSucc) {
666 getCache(PImpl).threadEdge(PredBB, OldSucc, NewSucc);