1 //===- LazyValueInfo.cpp - Value constraint analysis ------------*- C++ -*-===//
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 #include "llvm/Analysis/LazyValueInfo.h"
16 #include "llvm/ADT/DenseSet.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/Analysis/AssumptionCache.h"
19 #include "llvm/Analysis/ConstantFolding.h"
20 #include "llvm/Analysis/TargetLibraryInfo.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/IR/CFG.h"
23 #include "llvm/IR/ConstantRange.h"
24 #include "llvm/IR/Constants.h"
25 #include "llvm/IR/DataLayout.h"
26 #include "llvm/IR/Dominators.h"
27 #include "llvm/IR/Instructions.h"
28 #include "llvm/IR/IntrinsicInst.h"
29 #include "llvm/IR/LLVMContext.h"
30 #include "llvm/IR/PatternMatch.h"
31 #include "llvm/IR/ValueHandle.h"
32 #include "llvm/Support/Debug.h"
33 #include "llvm/Support/raw_ostream.h"
37 using namespace PatternMatch;
39 #define DEBUG_TYPE "lazy-value-info"
41 char LazyValueInfo::ID = 0;
42 INITIALIZE_PASS_BEGIN(LazyValueInfo, "lazy-value-info",
43 "Lazy Value Information Analysis", false, true)
44 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
45 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
46 INITIALIZE_PASS_END(LazyValueInfo, "lazy-value-info",
47 "Lazy Value Information Analysis", false, true)
50 FunctionPass *createLazyValueInfoPass() { return new LazyValueInfo(); }
54 //===----------------------------------------------------------------------===//
56 //===----------------------------------------------------------------------===//
58 /// This is the information tracked by LazyValueInfo for each value.
60 /// FIXME: This is basically just for bringup, this can be made a lot more rich
66 /// This Value has no known value yet.
69 /// This Value has a specific constant value.
72 /// This Value is known to not have the specified value.
75 /// The Value falls within this range.
78 /// This value is not known to be constant, and we know that it has a value.
82 /// Val: This stores the current lattice value along with the Constant* for
83 /// the constant if this is a 'constant' or 'notconstant' value.
89 LVILatticeVal() : Tag(undefined), Val(nullptr), Range(1, true) {}
91 static LVILatticeVal get(Constant *C) {
93 if (!isa<UndefValue>(C))
97 static LVILatticeVal getNot(Constant *C) {
99 if (!isa<UndefValue>(C))
100 Res.markNotConstant(C);
103 static LVILatticeVal getRange(ConstantRange CR) {
105 Res.markConstantRange(CR);
109 bool isUndefined() const { return Tag == undefined; }
110 bool isConstant() const { return Tag == constant; }
111 bool isNotConstant() const { return Tag == notconstant; }
112 bool isConstantRange() const { return Tag == constantrange; }
113 bool isOverdefined() const { return Tag == overdefined; }
115 Constant *getConstant() const {
116 assert(isConstant() && "Cannot get the constant of a non-constant!");
120 Constant *getNotConstant() const {
121 assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
125 ConstantRange getConstantRange() const {
126 assert(isConstantRange() &&
127 "Cannot get the constant-range of a non-constant-range!");
131 /// Return true if this is a change in status.
132 bool markOverdefined() {
139 /// Return true if this is a change in status.
140 bool markConstant(Constant *V) {
141 assert(V && "Marking constant with NULL");
142 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
143 return markConstantRange(ConstantRange(CI->getValue()));
144 if (isa<UndefValue>(V))
147 assert((!isConstant() || getConstant() == V) &&
148 "Marking constant with different value");
149 assert(isUndefined());
155 /// Return true if this is a change in status.
156 bool markNotConstant(Constant *V) {
157 assert(V && "Marking constant with NULL");
158 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
159 return markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue()));
160 if (isa<UndefValue>(V))
163 assert((!isConstant() || getConstant() != V) &&
164 "Marking constant !constant with same value");
165 assert((!isNotConstant() || getNotConstant() == V) &&
166 "Marking !constant with different value");
167 assert(isUndefined() || isConstant());
173 /// Return true if this is a change in status.
174 bool markConstantRange(const ConstantRange NewR) {
175 if (isConstantRange()) {
176 if (NewR.isEmptySet())
177 return markOverdefined();
179 bool changed = Range != NewR;
184 assert(isUndefined());
185 if (NewR.isEmptySet())
186 return markOverdefined();
193 /// Merge the specified lattice value into this one, updating this
194 /// one and returning true if anything changed.
195 bool mergeIn(const LVILatticeVal &RHS, const DataLayout &DL) {
196 if (RHS.isUndefined() || isOverdefined()) return false;
197 if (RHS.isOverdefined()) return markOverdefined();
207 if (RHS.isConstant()) {
210 return markOverdefined();
213 if (RHS.isNotConstant()) {
215 return markOverdefined();
217 // Unless we can prove that the two Constants are different, we must
218 // move to overdefined.
219 if (ConstantInt *Res =
220 dyn_cast<ConstantInt>(ConstantFoldCompareInstOperands(
221 CmpInst::ICMP_NE, getConstant(), RHS.getNotConstant(), DL)))
223 return markNotConstant(RHS.getNotConstant());
225 return markOverdefined();
228 // RHS is a ConstantRange, LHS is a non-integer Constant.
230 // FIXME: consider the case where RHS is a range [1, 0) and LHS is
231 // a function. The correct result is to pick up RHS.
233 return markOverdefined();
236 if (isNotConstant()) {
237 if (RHS.isConstant()) {
239 return markOverdefined();
241 // Unless we can prove that the two Constants are different, we must
242 // move to overdefined.
243 if (ConstantInt *Res =
244 dyn_cast<ConstantInt>(ConstantFoldCompareInstOperands(
245 CmpInst::ICMP_NE, getNotConstant(), RHS.getConstant(), DL)))
249 return markOverdefined();
252 if (RHS.isNotConstant()) {
255 return markOverdefined();
258 return markOverdefined();
261 assert(isConstantRange() && "New LVILattice type?");
262 if (!RHS.isConstantRange())
263 return markOverdefined();
265 ConstantRange NewR = Range.unionWith(RHS.getConstantRange());
266 if (NewR.isFullSet())
267 return markOverdefined();
268 return markConstantRange(NewR);
272 } // end anonymous namespace.
275 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val)
277 raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) {
278 if (Val.isUndefined())
279 return OS << "undefined";
280 if (Val.isOverdefined())
281 return OS << "overdefined";
283 if (Val.isNotConstant())
284 return OS << "notconstant<" << *Val.getNotConstant() << '>';
285 else if (Val.isConstantRange())
286 return OS << "constantrange<" << Val.getConstantRange().getLower() << ", "
287 << Val.getConstantRange().getUpper() << '>';
288 return OS << "constant<" << *Val.getConstant() << '>';
292 //===----------------------------------------------------------------------===//
293 // LazyValueInfoCache Decl
294 //===----------------------------------------------------------------------===//
297 /// A callback value handle updates the cache when values are erased.
298 class LazyValueInfoCache;
299 struct LVIValueHandle final : public CallbackVH {
300 LazyValueInfoCache *Parent;
302 LVIValueHandle(Value *V, LazyValueInfoCache *P)
303 : CallbackVH(V), Parent(P) { }
305 void deleted() override;
306 void allUsesReplacedWith(Value *V) override {
313 /// This is the cache kept by LazyValueInfo which
314 /// maintains information about queries across the clients' queries.
315 class LazyValueInfoCache {
316 /// This is all of the cached block information for exactly one Value*.
317 /// The entries are sorted by the BasicBlock* of the
318 /// entries, allowing us to do a lookup with a binary search.
319 typedef SmallDenseMap<AssertingVH<BasicBlock>, LVILatticeVal, 4>
322 /// This is all of the cached information for all values,
323 /// mapped from Value* to key information.
324 std::map<LVIValueHandle, ValueCacheEntryTy> ValueCache;
326 /// This tracks, on a per-block basis, the set of values that are
327 /// over-defined at the end of that block. This is required
328 /// for cache updating.
329 typedef DenseMap<AssertingVH<BasicBlock>, SmallPtrSet<Value *, 4>>
331 OverDefinedCacheTy OverDefinedCache;
333 /// Keep track of all blocks that we have ever seen, so we
334 /// don't spend time removing unused blocks from our caches.
335 DenseSet<AssertingVH<BasicBlock> > SeenBlocks;
337 /// This stack holds the state of the value solver during a query.
338 /// It basically emulates the callstack of the naive
339 /// recursive value lookup process.
340 std::stack<std::pair<BasicBlock*, Value*> > BlockValueStack;
342 /// Keeps track of which block-value pairs are in BlockValueStack.
343 DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
345 /// Push BV onto BlockValueStack unless it's already in there.
346 /// Returns true on success.
347 bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
348 if (!BlockValueSet.insert(BV).second)
349 return false; // It's already in the stack.
351 BlockValueStack.push(BV);
355 AssumptionCache *AC; ///< A pointer to the cache of @llvm.assume calls.
356 const DataLayout &DL; ///< A mandatory DataLayout
357 DominatorTree *DT; ///< An optional DT pointer.
359 friend struct LVIValueHandle;
361 void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) {
362 SeenBlocks.insert(BB);
363 lookup(Val)[BB] = Result;
364 if (Result.isOverdefined())
365 OverDefinedCache[BB].insert(Val);
368 LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
369 bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
370 LVILatticeVal &Result,
371 Instruction *CxtI = nullptr);
372 bool hasBlockValue(Value *Val, BasicBlock *BB);
374 // These methods process one work item and may add more. A false value
375 // returned means that the work item was not completely processed and must
376 // be revisited after going through the new items.
377 bool solveBlockValue(Value *Val, BasicBlock *BB);
378 bool solveBlockValueNonLocal(LVILatticeVal &BBLV,
379 Value *Val, BasicBlock *BB);
380 bool solveBlockValuePHINode(LVILatticeVal &BBLV,
381 PHINode *PN, BasicBlock *BB);
382 bool solveBlockValueConstantRange(LVILatticeVal &BBLV,
383 Instruction *BBI, BasicBlock *BB);
384 void mergeAssumeBlockValueConstantRange(Value *Val, LVILatticeVal &BBLV,
389 ValueCacheEntryTy &lookup(Value *V) {
390 return ValueCache[LVIValueHandle(V, this)];
394 /// This is the query interface to determine the lattice
395 /// value for the specified Value* at the end of the specified block.
396 LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB,
397 Instruction *CxtI = nullptr);
399 /// This is the query interface to determine the lattice
400 /// value for the specified Value* at the specified instruction (generally
401 /// from an assume intrinsic).
402 LVILatticeVal getValueAt(Value *V, Instruction *CxtI);
404 /// This is the query interface to determine the lattice
405 /// value for the specified Value* that is true on the specified edge.
406 LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB,
407 Instruction *CxtI = nullptr);
409 /// This is the update interface to inform the cache that an edge from
410 /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
411 void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
413 /// This is part of the update interface to inform the cache
414 /// that a block has been deleted.
415 void eraseBlock(BasicBlock *BB);
417 /// clear - Empty the cache.
421 OverDefinedCache.clear();
424 LazyValueInfoCache(AssumptionCache *AC, const DataLayout &DL,
425 DominatorTree *DT = nullptr)
426 : AC(AC), DL(DL), DT(DT) {}
428 } // end anonymous namespace
430 void LVIValueHandle::deleted() {
431 SmallVector<AssertingVH<BasicBlock>, 4> ToErase;
432 for (auto &I : Parent->OverDefinedCache) {
433 SmallPtrSetImpl<Value *> &ValueSet = I.second;
434 if (ValueSet.count(getValPtr()))
435 ValueSet.erase(getValPtr());
436 if (ValueSet.empty())
437 ToErase.push_back(I.first);
439 for (auto &BB : ToErase)
440 Parent->OverDefinedCache.erase(BB);
442 // This erasure deallocates *this, so it MUST happen after we're done
443 // using any and all members of *this.
444 Parent->ValueCache.erase(*this);
447 void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
448 // Shortcut if we have never seen this block.
449 DenseSet<AssertingVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
450 if (I == SeenBlocks.end())
454 auto ODI = OverDefinedCache.find(BB);
455 if (ODI != OverDefinedCache.end())
456 OverDefinedCache.erase(ODI);
458 for (auto I = ValueCache.begin(), E = ValueCache.end(); I != E; ++I)
462 void LazyValueInfoCache::solve() {
463 while (!BlockValueStack.empty()) {
464 std::pair<BasicBlock*, Value*> &e = BlockValueStack.top();
465 assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
467 if (solveBlockValue(e.second, e.first)) {
468 // The work item was completely processed.
469 assert(BlockValueStack.top() == e && "Nothing should have been pushed!");
470 assert(lookup(e.second).count(e.first) && "Result should be in cache!");
472 BlockValueStack.pop();
473 BlockValueSet.erase(e);
475 // More work needs to be done before revisiting.
476 assert(BlockValueStack.top() != e && "Stack should have been pushed!");
481 bool LazyValueInfoCache::hasBlockValue(Value *Val, BasicBlock *BB) {
482 // If already a constant, there is nothing to compute.
483 if (isa<Constant>(Val))
486 LVIValueHandle ValHandle(Val, this);
487 auto I = ValueCache.find(ValHandle);
488 if (I == ValueCache.end()) return false;
489 return I->second.count(BB);
492 LVILatticeVal LazyValueInfoCache::getBlockValue(Value *Val, BasicBlock *BB) {
493 // If already a constant, there is nothing to compute.
494 if (Constant *VC = dyn_cast<Constant>(Val))
495 return LVILatticeVal::get(VC);
497 SeenBlocks.insert(BB);
498 return lookup(Val)[BB];
501 static LVILatticeVal getFromRangeMetadata(Instruction *BBI) {
502 switch (BBI->getOpcode()) {
504 case Instruction::Load:
505 case Instruction::Call:
506 case Instruction::Invoke:
507 if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
508 if (isa<IntegerType>(BBI->getType())) {
509 ConstantRange Result = getConstantRangeFromMetadata(*Ranges);
510 return LVILatticeVal::getRange(Result);
514 // Nothing known - Note that we do not want overdefined here. We may know
515 // something else about the value and not having range metadata shouldn't
516 // cause us to throw away those facts.
517 return LVILatticeVal();
520 bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
521 if (isa<Constant>(Val))
524 if (lookup(Val).count(BB)) {
525 // If we have a cached value, use that.
526 DEBUG(dbgs() << " reuse BB '" << BB->getName()
527 << "' val=" << lookup(Val)[BB] << '\n');
529 // Since we're reusing a cached value, we don't need to update the
530 // OverDefinedCache. The cache will have been properly updated whenever the
531 // cached value was inserted.
535 // Hold off inserting this value into the Cache in case we have to return
536 // false and come back later.
539 Instruction *BBI = dyn_cast<Instruction>(Val);
540 if (!BBI || BBI->getParent() != BB) {
541 if (!solveBlockValueNonLocal(Res, Val, BB))
543 insertResult(Val, BB, Res);
547 if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
548 if (!solveBlockValuePHINode(Res, PN, BB))
550 insertResult(Val, BB, Res);
554 // If this value is a nonnull pointer, record it's range and bailout.
555 PointerType *PT = dyn_cast<PointerType>(BBI->getType());
556 if (PT && isKnownNonNull(BBI)) {
557 Res = LVILatticeVal::getNot(ConstantPointerNull::get(PT));
558 insertResult(Val, BB, Res);
562 // If this is an instruction which supports range metadata, return the
563 // implied range. TODO: This should be an intersection, not a union.
564 Res.mergeIn(getFromRangeMetadata(BBI), DL);
566 // We can only analyze the definitions of certain classes of instructions
567 // (integral binops and casts at the moment), so bail if this isn't one.
568 LVILatticeVal Result;
569 if ((!isa<BinaryOperator>(BBI) && !isa<CastInst>(BBI)) ||
570 !BBI->getType()->isIntegerTy()) {
571 DEBUG(dbgs() << " compute BB '" << BB->getName()
572 << "' - overdefined because inst def found.\n");
573 Res.markOverdefined();
574 insertResult(Val, BB, Res);
578 // FIXME: We're currently limited to binops with a constant RHS. This should
580 BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
581 if (BO && !isa<ConstantInt>(BO->getOperand(1))) {
582 DEBUG(dbgs() << " compute BB '" << BB->getName()
583 << "' - overdefined because inst def found.\n");
585 Res.markOverdefined();
586 insertResult(Val, BB, Res);
590 if (!solveBlockValueConstantRange(Res, BBI, BB))
592 insertResult(Val, BB, Res);
596 static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
597 if (LoadInst *L = dyn_cast<LoadInst>(I)) {
598 return L->getPointerAddressSpace() == 0 &&
599 GetUnderlyingObject(L->getPointerOperand(),
600 L->getModule()->getDataLayout()) == Ptr;
602 if (StoreInst *S = dyn_cast<StoreInst>(I)) {
603 return S->getPointerAddressSpace() == 0 &&
604 GetUnderlyingObject(S->getPointerOperand(),
605 S->getModule()->getDataLayout()) == Ptr;
607 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
608 if (MI->isVolatile()) return false;
610 // FIXME: check whether it has a valuerange that excludes zero?
611 ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
612 if (!Len || Len->isZero()) return false;
614 if (MI->getDestAddressSpace() == 0)
615 if (GetUnderlyingObject(MI->getRawDest(),
616 MI->getModule()->getDataLayout()) == Ptr)
618 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
619 if (MTI->getSourceAddressSpace() == 0)
620 if (GetUnderlyingObject(MTI->getRawSource(),
621 MTI->getModule()->getDataLayout()) == Ptr)
627 bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV,
628 Value *Val, BasicBlock *BB) {
629 LVILatticeVal Result; // Start Undefined.
631 // If this is a pointer, and there's a load from that pointer in this BB,
632 // then we know that the pointer can't be NULL.
633 bool NotNull = false;
634 if (Val->getType()->isPointerTy()) {
635 if (isKnownNonNull(Val)) {
638 const DataLayout &DL = BB->getModule()->getDataLayout();
639 Value *UnderlyingVal = GetUnderlyingObject(Val, DL);
640 // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge
641 // inside InstructionDereferencesPointer either.
642 if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1)) {
643 for (Instruction &I : *BB) {
644 if (InstructionDereferencesPointer(&I, UnderlyingVal)) {
653 // If this is the entry block, we must be asking about an argument. The
654 // value is overdefined.
655 if (BB == &BB->getParent()->getEntryBlock()) {
656 assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
658 PointerType *PTy = cast<PointerType>(Val->getType());
659 Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
661 Result.markOverdefined();
667 // Loop over all of our predecessors, merging what we know from them into
669 bool EdgesMissing = false;
670 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
671 LVILatticeVal EdgeResult;
672 EdgesMissing |= !getEdgeValue(Val, *PI, BB, EdgeResult);
676 Result.mergeIn(EdgeResult, DL);
678 // If we hit overdefined, exit early. The BlockVals entry is already set
680 if (Result.isOverdefined()) {
681 DEBUG(dbgs() << " compute BB '" << BB->getName()
682 << "' - overdefined because of pred.\n");
683 // If we previously determined that this is a pointer that can't be null
684 // then return that rather than giving up entirely.
686 PointerType *PTy = cast<PointerType>(Val->getType());
687 Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
697 // Return the merged value, which is more precise than 'overdefined'.
698 assert(!Result.isOverdefined());
703 bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV,
704 PHINode *PN, BasicBlock *BB) {
705 LVILatticeVal Result; // Start Undefined.
707 // Loop over all of our predecessors, merging what we know from them into
709 bool EdgesMissing = false;
710 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
711 BasicBlock *PhiBB = PN->getIncomingBlock(i);
712 Value *PhiVal = PN->getIncomingValue(i);
713 LVILatticeVal EdgeResult;
714 // Note that we can provide PN as the context value to getEdgeValue, even
715 // though the results will be cached, because PN is the value being used as
716 // the cache key in the caller.
717 EdgesMissing |= !getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN);
721 Result.mergeIn(EdgeResult, DL);
723 // If we hit overdefined, exit early. The BlockVals entry is already set
725 if (Result.isOverdefined()) {
726 DEBUG(dbgs() << " compute BB '" << BB->getName()
727 << "' - overdefined because of pred.\n");
736 // Return the merged value, which is more precise than 'overdefined'.
737 assert(!Result.isOverdefined() && "Possible PHI in entry block?");
742 static bool getValueFromFromCondition(Value *Val, ICmpInst *ICI,
743 LVILatticeVal &Result,
744 bool isTrueDest = true);
746 // If we can determine a constant range for the value Val in the context
747 // provided by the instruction BBI, then merge it into BBLV. If we did find a
748 // constant range, return true.
749 void LazyValueInfoCache::mergeAssumeBlockValueConstantRange(Value *Val,
752 BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
756 for (auto &AssumeVH : AC->assumptions()) {
759 auto *I = cast<CallInst>(AssumeVH);
760 if (!isValidAssumeForContext(I, BBI, DT))
763 Value *C = I->getArgOperand(0);
764 if (ICmpInst *ICI = dyn_cast<ICmpInst>(C)) {
765 LVILatticeVal Result;
766 if (getValueFromFromCondition(Val, ICI, Result)) {
767 if (BBLV.isOverdefined())
770 BBLV.mergeIn(Result, DL);
776 bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
779 // Figure out the range of the LHS. If that fails, bail.
780 if (!hasBlockValue(BBI->getOperand(0), BB)) {
781 if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0))))
783 BBLV.markOverdefined();
787 LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
788 mergeAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI);
789 if (!LHSVal.isConstantRange()) {
790 BBLV.markOverdefined();
794 ConstantRange LHSRange = LHSVal.getConstantRange();
795 ConstantRange RHSRange(1);
796 IntegerType *ResultTy = cast<IntegerType>(BBI->getType());
797 if (isa<BinaryOperator>(BBI)) {
798 if (ConstantInt *RHS = dyn_cast<ConstantInt>(BBI->getOperand(1))) {
799 RHSRange = ConstantRange(RHS->getValue());
801 BBLV.markOverdefined();
806 // NOTE: We're currently limited by the set of operations that ConstantRange
807 // can evaluate symbolically. Enhancing that set will allows us to analyze
809 LVILatticeVal Result;
810 switch (BBI->getOpcode()) {
811 case Instruction::Add:
812 Result.markConstantRange(LHSRange.add(RHSRange));
814 case Instruction::Sub:
815 Result.markConstantRange(LHSRange.sub(RHSRange));
817 case Instruction::Mul:
818 Result.markConstantRange(LHSRange.multiply(RHSRange));
820 case Instruction::UDiv:
821 Result.markConstantRange(LHSRange.udiv(RHSRange));
823 case Instruction::Shl:
824 Result.markConstantRange(LHSRange.shl(RHSRange));
826 case Instruction::LShr:
827 Result.markConstantRange(LHSRange.lshr(RHSRange));
829 case Instruction::Trunc:
830 Result.markConstantRange(LHSRange.truncate(ResultTy->getBitWidth()));
832 case Instruction::SExt:
833 Result.markConstantRange(LHSRange.signExtend(ResultTy->getBitWidth()));
835 case Instruction::ZExt:
836 Result.markConstantRange(LHSRange.zeroExtend(ResultTy->getBitWidth()));
838 case Instruction::BitCast:
839 Result.markConstantRange(LHSRange);
841 case Instruction::And:
842 Result.markConstantRange(LHSRange.binaryAnd(RHSRange));
844 case Instruction::Or:
845 Result.markConstantRange(LHSRange.binaryOr(RHSRange));
848 // Unhandled instructions are overdefined.
850 DEBUG(dbgs() << " compute BB '" << BB->getName()
851 << "' - overdefined because inst def found.\n");
852 Result.markOverdefined();
860 bool getValueFromFromCondition(Value *Val, ICmpInst *ICI,
861 LVILatticeVal &Result, bool isTrueDest) {
862 if (ICI && isa<Constant>(ICI->getOperand(1))) {
863 if (ICI->isEquality() && ICI->getOperand(0) == Val) {
864 // We know that V has the RHS constant if this is a true SETEQ or
866 if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
867 Result = LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
869 Result = LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1)));
873 // Recognize the range checking idiom that InstCombine produces.
874 // (X-C1) u< C2 --> [C1, C1+C2)
875 ConstantInt *NegOffset = nullptr;
876 if (ICI->getPredicate() == ICmpInst::ICMP_ULT)
877 match(ICI->getOperand(0), m_Add(m_Specific(Val),
878 m_ConstantInt(NegOffset)));
880 ConstantInt *CI = dyn_cast<ConstantInt>(ICI->getOperand(1));
881 if (CI && (ICI->getOperand(0) == Val || NegOffset)) {
882 // Calculate the range of values that are allowed by the comparison
883 ConstantRange CmpRange(CI->getValue());
884 ConstantRange TrueValues =
885 ConstantRange::makeAllowedICmpRegion(ICI->getPredicate(), CmpRange);
887 if (NegOffset) // Apply the offset from above.
888 TrueValues = TrueValues.subtract(NegOffset->getValue());
890 // If we're interested in the false dest, invert the condition.
891 if (!isTrueDest) TrueValues = TrueValues.inverse();
893 Result = LVILatticeVal::getRange(TrueValues);
901 /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
902 /// Val is not constrained on the edge.
903 static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
904 BasicBlock *BBTo, LVILatticeVal &Result) {
905 // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
907 if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
908 // If this is a conditional branch and only one successor goes to BBTo, then
909 // we may be able to infer something from the condition.
910 if (BI->isConditional() &&
911 BI->getSuccessor(0) != BI->getSuccessor(1)) {
912 bool isTrueDest = BI->getSuccessor(0) == BBTo;
913 assert(BI->getSuccessor(!isTrueDest) == BBTo &&
914 "BBTo isn't a successor of BBFrom");
916 // If V is the condition of the branch itself, then we know exactly what
918 if (BI->getCondition() == Val) {
919 Result = LVILatticeVal::get(ConstantInt::get(
920 Type::getInt1Ty(Val->getContext()), isTrueDest));
924 // If the condition of the branch is an equality comparison, we may be
925 // able to infer the value.
926 if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition()))
927 if (getValueFromFromCondition(Val, ICI, Result, isTrueDest))
932 // If the edge was formed by a switch on the value, then we may know exactly
934 if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
935 if (SI->getCondition() != Val)
938 bool DefaultCase = SI->getDefaultDest() == BBTo;
939 unsigned BitWidth = Val->getType()->getIntegerBitWidth();
940 ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
942 for (SwitchInst::CaseIt i : SI->cases()) {
943 ConstantRange EdgeVal(i.getCaseValue()->getValue());
945 // It is possible that the default destination is the destination of
946 // some cases. There is no need to perform difference for those cases.
947 if (i.getCaseSuccessor() != BBTo)
948 EdgesVals = EdgesVals.difference(EdgeVal);
949 } else if (i.getCaseSuccessor() == BBTo)
950 EdgesVals = EdgesVals.unionWith(EdgeVal);
952 Result = LVILatticeVal::getRange(EdgesVals);
958 /// \brief Compute the value of Val on the edge BBFrom -> BBTo or the value at
959 /// the basic block if the edge does not constrain Val.
960 bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
961 BasicBlock *BBTo, LVILatticeVal &Result,
963 // If already a constant, there is nothing to compute.
964 if (Constant *VC = dyn_cast<Constant>(Val)) {
965 Result = LVILatticeVal::get(VC);
969 if (getEdgeValueLocal(Val, BBFrom, BBTo, Result)) {
970 if (!Result.isConstantRange() ||
971 Result.getConstantRange().getSingleElement())
974 // FIXME: this check should be moved to the beginning of the function when
975 // LVI better supports recursive values. Even for the single value case, we
976 // can intersect to detect dead code (an empty range).
977 if (!hasBlockValue(Val, BBFrom)) {
978 if (pushBlockValue(std::make_pair(BBFrom, Val)))
980 Result.markOverdefined();
984 // Try to intersect ranges of the BB and the constraint on the edge.
985 LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
986 mergeAssumeBlockValueConstantRange(Val, InBlock, BBFrom->getTerminator());
987 // See note on the use of the CxtI with mergeAssumeBlockValueConstantRange,
988 // and caching, below.
989 mergeAssumeBlockValueConstantRange(Val, InBlock, CxtI);
990 if (!InBlock.isConstantRange())
993 ConstantRange Range =
994 Result.getConstantRange().intersectWith(InBlock.getConstantRange());
995 Result = LVILatticeVal::getRange(Range);
999 if (!hasBlockValue(Val, BBFrom)) {
1000 if (pushBlockValue(std::make_pair(BBFrom, Val)))
1002 Result.markOverdefined();
1006 // If we couldn't compute the value on the edge, use the value from the BB.
1007 Result = getBlockValue(Val, BBFrom);
1008 mergeAssumeBlockValueConstantRange(Val, Result, BBFrom->getTerminator());
1009 // We can use the context instruction (generically the ultimate instruction
1010 // the calling pass is trying to simplify) here, even though the result of
1011 // this function is generally cached when called from the solve* functions
1012 // (and that cached result might be used with queries using a different
1013 // context instruction), because when this function is called from the solve*
1014 // functions, the context instruction is not provided. When called from
1015 // LazyValueInfoCache::getValueOnEdge, the context instruction is provided,
1016 // but then the result is not cached.
1017 mergeAssumeBlockValueConstantRange(Val, Result, CxtI);
1021 LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB,
1022 Instruction *CxtI) {
1023 DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
1024 << BB->getName() << "'\n");
1026 assert(BlockValueStack.empty() && BlockValueSet.empty());
1027 pushBlockValue(std::make_pair(BB, V));
1030 LVILatticeVal Result = getBlockValue(V, BB);
1031 mergeAssumeBlockValueConstantRange(V, Result, CxtI);
1033 DEBUG(dbgs() << " Result = " << Result << "\n");
1037 LVILatticeVal LazyValueInfoCache::getValueAt(Value *V, Instruction *CxtI) {
1038 DEBUG(dbgs() << "LVI Getting value " << *V << " at '"
1039 << CxtI->getName() << "'\n");
1041 LVILatticeVal Result;
1042 if (auto *I = dyn_cast<Instruction>(V))
1043 Result = getFromRangeMetadata(I);
1044 mergeAssumeBlockValueConstantRange(V, Result, CxtI);
1046 DEBUG(dbgs() << " Result = " << Result << "\n");
1050 LVILatticeVal LazyValueInfoCache::
1051 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
1052 Instruction *CxtI) {
1053 DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
1054 << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
1056 LVILatticeVal Result;
1057 if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) {
1059 bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI);
1061 assert(WasFastQuery && "More work to do after problem solved?");
1064 DEBUG(dbgs() << " Result = " << Result << "\n");
1068 void LazyValueInfoCache::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1069 BasicBlock *NewSucc) {
1070 // When an edge in the graph has been threaded, values that we could not
1071 // determine a value for before (i.e. were marked overdefined) may be
1072 // possible to solve now. We do NOT try to proactively update these values.
1073 // Instead, we clear their entries from the cache, and allow lazy updating to
1074 // recompute them when needed.
1076 // The updating process is fairly simple: we need to drop cached info
1077 // for all values that were marked overdefined in OldSucc, and for those same
1078 // values in any successor of OldSucc (except NewSucc) in which they were
1079 // also marked overdefined.
1080 std::vector<BasicBlock*> worklist;
1081 worklist.push_back(OldSucc);
1083 auto I = OverDefinedCache.find(OldSucc);
1084 if (I == OverDefinedCache.end())
1085 return; // Nothing to process here.
1086 SmallVector<Value *, 4> ValsToClear(I->second.begin(), I->second.end());
1088 // Use a worklist to perform a depth-first search of OldSucc's successors.
1089 // NOTE: We do not need a visited list since any blocks we have already
1090 // visited will have had their overdefined markers cleared already, and we
1091 // thus won't loop to their successors.
1092 while (!worklist.empty()) {
1093 BasicBlock *ToUpdate = worklist.back();
1094 worklist.pop_back();
1096 // Skip blocks only accessible through NewSucc.
1097 if (ToUpdate == NewSucc) continue;
1099 bool changed = false;
1100 for (Value *V : ValsToClear) {
1101 // If a value was marked overdefined in OldSucc, and is here too...
1102 auto OI = OverDefinedCache.find(ToUpdate);
1103 if (OI == OverDefinedCache.end())
1105 SmallPtrSetImpl<Value *> &ValueSet = OI->second;
1106 if (!ValueSet.count(V))
1109 // Remove it from the caches.
1110 ValueCacheEntryTy &Entry = ValueCache[LVIValueHandle(V, this)];
1111 ValueCacheEntryTy::iterator CI = Entry.find(ToUpdate);
1113 assert(CI != Entry.end() && "Couldn't find entry to update?");
1116 if (ValueSet.empty())
1117 OverDefinedCache.erase(OI);
1119 // If we removed anything, then we potentially need to update
1120 // blocks successors too.
1124 if (!changed) continue;
1126 worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
1130 //===----------------------------------------------------------------------===//
1131 // LazyValueInfo Impl
1132 //===----------------------------------------------------------------------===//
1134 /// This lazily constructs the LazyValueInfoCache.
1135 static LazyValueInfoCache &getCache(void *&PImpl, AssumptionCache *AC,
1136 const DataLayout *DL,
1137 DominatorTree *DT = nullptr) {
1139 assert(DL && "getCache() called with a null DataLayout");
1140 PImpl = new LazyValueInfoCache(AC, *DL, DT);
1142 return *static_cast<LazyValueInfoCache*>(PImpl);
1145 bool LazyValueInfo::runOnFunction(Function &F) {
1146 AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1147 const DataLayout &DL = F.getParent()->getDataLayout();
1149 DominatorTreeWrapperPass *DTWP =
1150 getAnalysisIfAvailable<DominatorTreeWrapperPass>();
1151 DT = DTWP ? &DTWP->getDomTree() : nullptr;
1153 TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1156 getCache(PImpl, AC, &DL, DT).clear();
1162 void LazyValueInfo::getAnalysisUsage(AnalysisUsage &AU) const {
1163 AU.setPreservesAll();
1164 AU.addRequired<AssumptionCacheTracker>();
1165 AU.addRequired<TargetLibraryInfoWrapperPass>();
1168 void LazyValueInfo::releaseMemory() {
1169 // If the cache was allocated, free it.
1171 delete &getCache(PImpl, AC, nullptr);
1176 Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB,
1177 Instruction *CxtI) {
1178 const DataLayout &DL = BB->getModule()->getDataLayout();
1179 LVILatticeVal Result =
1180 getCache(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1182 if (Result.isConstant())
1183 return Result.getConstant();
1184 if (Result.isConstantRange()) {
1185 ConstantRange CR = Result.getConstantRange();
1186 if (const APInt *SingleVal = CR.getSingleElement())
1187 return ConstantInt::get(V->getContext(), *SingleVal);
1192 /// Determine whether the specified value is known to be a
1193 /// constant on the specified edge. Return null if not.
1194 Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
1196 Instruction *CxtI) {
1197 const DataLayout &DL = FromBB->getModule()->getDataLayout();
1198 LVILatticeVal Result =
1199 getCache(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1201 if (Result.isConstant())
1202 return Result.getConstant();
1203 if (Result.isConstantRange()) {
1204 ConstantRange CR = Result.getConstantRange();
1205 if (const APInt *SingleVal = CR.getSingleElement())
1206 return ConstantInt::get(V->getContext(), *SingleVal);
1211 static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C,
1212 LVILatticeVal &Result,
1213 const DataLayout &DL,
1214 TargetLibraryInfo *TLI) {
1216 // If we know the value is a constant, evaluate the conditional.
1217 Constant *Res = nullptr;
1218 if (Result.isConstant()) {
1219 Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, DL,
1221 if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
1222 return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
1223 return LazyValueInfo::Unknown;
1226 if (Result.isConstantRange()) {
1227 ConstantInt *CI = dyn_cast<ConstantInt>(C);
1228 if (!CI) return LazyValueInfo::Unknown;
1230 ConstantRange CR = Result.getConstantRange();
1231 if (Pred == ICmpInst::ICMP_EQ) {
1232 if (!CR.contains(CI->getValue()))
1233 return LazyValueInfo::False;
1235 if (CR.isSingleElement() && CR.contains(CI->getValue()))
1236 return LazyValueInfo::True;
1237 } else if (Pred == ICmpInst::ICMP_NE) {
1238 if (!CR.contains(CI->getValue()))
1239 return LazyValueInfo::True;
1241 if (CR.isSingleElement() && CR.contains(CI->getValue()))
1242 return LazyValueInfo::False;
1245 // Handle more complex predicates.
1246 ConstantRange TrueValues =
1247 ICmpInst::makeConstantRange((ICmpInst::Predicate)Pred, CI->getValue());
1248 if (TrueValues.contains(CR))
1249 return LazyValueInfo::True;
1250 if (TrueValues.inverse().contains(CR))
1251 return LazyValueInfo::False;
1252 return LazyValueInfo::Unknown;
1255 if (Result.isNotConstant()) {
1256 // If this is an equality comparison, we can try to fold it knowing that
1258 if (Pred == ICmpInst::ICMP_EQ) {
1259 // !C1 == C -> false iff C1 == C.
1260 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1261 Result.getNotConstant(), C, DL,
1263 if (Res->isNullValue())
1264 return LazyValueInfo::False;
1265 } else if (Pred == ICmpInst::ICMP_NE) {
1266 // !C1 != C -> true iff C1 == C.
1267 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
1268 Result.getNotConstant(), C, DL,
1270 if (Res->isNullValue())
1271 return LazyValueInfo::True;
1273 return LazyValueInfo::Unknown;
1276 return LazyValueInfo::Unknown;
1279 /// Determine whether the specified value comparison with a constant is known to
1280 /// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
1281 LazyValueInfo::Tristate
1282 LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
1283 BasicBlock *FromBB, BasicBlock *ToBB,
1284 Instruction *CxtI) {
1285 const DataLayout &DL = FromBB->getModule()->getDataLayout();
1286 LVILatticeVal Result =
1287 getCache(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
1289 return getPredicateResult(Pred, C, Result, DL, TLI);
1292 LazyValueInfo::Tristate
1293 LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
1294 Instruction *CxtI) {
1295 const DataLayout &DL = CxtI->getModule()->getDataLayout();
1296 LVILatticeVal Result = getCache(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
1297 Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
1301 // Note: The following bit of code is somewhat distinct from the rest of LVI;
1302 // LVI as a whole tries to compute a lattice value which is conservatively
1303 // correct at a given location. In this case, we have a predicate which we
1304 // weren't able to prove about the merged result, and we're pushing that
1305 // predicate back along each incoming edge to see if we can prove it
1306 // separately for each input. As a motivating example, consider:
1308 // %v1 = ... ; constantrange<1, 5>
1311 // %v2 = ... ; constantrange<10, 20>
1314 // %phi = phi [%v1, %v2] ; constantrange<1,20>
1315 // %pred = icmp eq i32 %phi, 8
1316 // We can't tell from the lattice value for '%phi' that '%pred' is false
1317 // along each path, but by checking the predicate over each input separately,
1319 // We limit the search to one step backwards from the current BB and value.
1320 // We could consider extending this to search further backwards through the
1321 // CFG and/or value graph, but there are non-obvious compile time vs quality
1324 BasicBlock *BB = CxtI->getParent();
1326 // Function entry or an unreachable block. Bail to avoid confusing
1328 pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1332 // If V is a PHI node in the same block as the context, we need to ask
1333 // questions about the predicate as applied to the incoming value along
1334 // each edge. This is useful for eliminating cases where the predicate is
1335 // known along all incoming edges.
1336 if (auto *PHI = dyn_cast<PHINode>(V))
1337 if (PHI->getParent() == BB) {
1338 Tristate Baseline = Unknown;
1339 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
1340 Value *Incoming = PHI->getIncomingValue(i);
1341 BasicBlock *PredBB = PHI->getIncomingBlock(i);
1342 // Note that PredBB may be BB itself.
1343 Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB,
1346 // Keep going as long as we've seen a consistent known result for
1348 Baseline = (i == 0) ? Result /* First iteration */
1349 : (Baseline == Result ? Baseline : Unknown); /* All others */
1350 if (Baseline == Unknown)
1353 if (Baseline != Unknown)
1357 // For a comparison where the V is outside this block, it's possible
1358 // that we've branched on it before. Look to see if the value is known
1359 // on all incoming edges.
1360 if (!isa<Instruction>(V) ||
1361 cast<Instruction>(V)->getParent() != BB) {
1362 // For predecessor edge, determine if the comparison is true or false
1363 // on that edge. If they're all true or all false, we can conclude
1364 // the value of the comparison in this block.
1365 Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1366 if (Baseline != Unknown) {
1367 // Check that all remaining incoming values match the first one.
1368 while (++PI != PE) {
1369 Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1370 if (Ret != Baseline) break;
1372 // If we terminated early, then one of the values didn't match.
1382 void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1383 BasicBlock *NewSucc) {
1385 const DataLayout &DL = PredBB->getModule()->getDataLayout();
1386 getCache(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc);
1390 void LazyValueInfo::eraseBlock(BasicBlock *BB) {
1392 const DataLayout &DL = BB->getModule()->getDataLayout();
1393 getCache(PImpl, AC, &DL, DT).eraseBlock(BB);