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 mpping 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(errs() << " 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(errs() << " 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(errs() << " 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
407 LVILatticeVal LVIQuery::getEdgeValue(BasicBlock *BBFrom, BasicBlock *BBTo) {
408 if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
409 // If this is a conditional branch and only one successor goes to BBTo, then
410 // we maybe able to infer something from the condition.
411 if (BI->isConditional() &&
412 BI->getSuccessor(0) != BI->getSuccessor(1)) {
413 bool isTrueDest = BI->getSuccessor(0) == BBTo;
414 assert(BI->getSuccessor(!isTrueDest) == BBTo &&
415 "BBTo isn't a successor of BBFrom");
417 // If V is the condition of the branch itself, then we know exactly what
419 if (BI->getCondition() == Val)
420 return LVILatticeVal::get(ConstantInt::get(
421 Type::getInt1Ty(Val->getContext()), isTrueDest));
423 // If the condition of the branch is an equality comparison, we may be
424 // able to infer the value.
425 if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition()))
426 if (ICI->isEquality() && ICI->getOperand(0) == Val &&
427 isa<Constant>(ICI->getOperand(1))) {
428 // We know that V has the RHS constant if this is a true SETEQ or
430 if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
431 return LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
432 return LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1)));
437 // TODO: Info from switch.
439 // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
442 // Otherwise see if the value is known in the block.
443 return getBlockValue(BBFrom);
447 //===----------------------------------------------------------------------===//
448 // LazyValueInfoCache Impl
449 //===----------------------------------------------------------------------===//
451 LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB) {
452 // If already a constant, there is nothing to compute.
453 if (Constant *VC = dyn_cast<Constant>(V))
454 return LVILatticeVal::get(VC);
456 DEBUG(errs() << "LVI Getting block end value " << *V << " at '"
457 << BB->getName() << "'\n");
459 LVILatticeVal Result = LVIQuery(V, ValueCache[V]).getBlockValue(BB);
461 DEBUG(errs() << " Result = " << Result << "\n");
465 LVILatticeVal LazyValueInfoCache::
466 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB) {
467 // If already a constant, there is nothing to compute.
468 if (Constant *VC = dyn_cast<Constant>(V))
469 return LVILatticeVal::get(VC);
471 DEBUG(errs() << "LVI Getting edge value " << *V << " from '"
472 << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
473 LVILatticeVal Result =
474 LVIQuery(V, ValueCache[V]).getEdgeValue(FromBB, ToBB);
476 DEBUG(errs() << " Result = " << Result << "\n");
481 //===----------------------------------------------------------------------===//
482 // LazyValueInfo Impl
483 //===----------------------------------------------------------------------===//
485 bool LazyValueInfo::runOnFunction(Function &F) {
486 TD = getAnalysisIfAvailable<TargetData>();
491 /// getCache - This lazily constructs the LazyValueInfoCache.
492 static LazyValueInfoCache &getCache(void *&PImpl) {
494 PImpl = new LazyValueInfoCache();
495 return *static_cast<LazyValueInfoCache*>(PImpl);
498 void LazyValueInfo::releaseMemory() {
499 // If the cache was allocated, free it.
501 delete &getCache(PImpl);
506 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB) {
507 LVILatticeVal Result = getCache(PImpl).getValueInBlock(V, BB);
509 if (Result.isConstant())
510 return Result.getConstant();
514 /// getConstantOnEdge - Determine whether the specified value is known to be a
515 /// constant on the specified edge. Return null if not.
516 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
518 LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB);
520 if (Result.isConstant())
521 return Result.getConstant();
525 /// getPredicateOnEdge - Determine whether the specified value comparison
526 /// with a constant is known to be true or false on the specified CFG edge.
527 /// Pred is a CmpInst predicate.
528 LazyValueInfo::Tristate
529 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
530 BasicBlock *FromBB, BasicBlock *ToBB) {
531 LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB);
533 // If we know the value is a constant, evaluate the conditional.
535 if (Result.isConstant()) {
536 Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, TD);
537 if (ConstantInt *ResCI = dyn_cast_or_null<ConstantInt>(Res))
538 return ResCI->isZero() ? False : True;
542 if (Result.isNotConstant()) {
543 // If this is an equality comparison, we can try to fold it knowing that
545 if (Pred == ICmpInst::ICMP_EQ) {
546 // !C1 == C -> false iff C1 == C.
547 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
548 Result.getNotConstant(), C, TD);
549 if (Res->isNullValue())
551 } else if (Pred == ICmpInst::ICMP_NE) {
552 // !C1 != C -> true iff C1 == C.
553 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_EQ,
554 Result.getNotConstant(), C, TD);
555 if (Res->isNullValue())