diff options
Diffstat (limited to 'contrib/llvm/lib/Analysis/LazyValueInfo.cpp')
| -rw-r--r-- | contrib/llvm/lib/Analysis/LazyValueInfo.cpp | 707 |
1 files changed, 499 insertions, 208 deletions
diff --git a/contrib/llvm/lib/Analysis/LazyValueInfo.cpp b/contrib/llvm/lib/Analysis/LazyValueInfo.cpp index 961c010..3ce667f 100644 --- a/contrib/llvm/lib/Analysis/LazyValueInfo.cpp +++ b/contrib/llvm/lib/Analysis/LazyValueInfo.cpp @@ -38,18 +38,19 @@ using namespace PatternMatch; #define DEBUG_TYPE "lazy-value-info" -char LazyValueInfo::ID = 0; -INITIALIZE_PASS_BEGIN(LazyValueInfo, "lazy-value-info", +char LazyValueInfoWrapperPass::ID = 0; +INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info", "Lazy Value Information Analysis", false, true) INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) -INITIALIZE_PASS_END(LazyValueInfo, "lazy-value-info", +INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info", "Lazy Value Information Analysis", false, true) namespace llvm { - FunctionPass *createLazyValueInfoPass() { return new LazyValueInfo(); } + FunctionPass *createLazyValueInfoPass() { return new LazyValueInfoWrapperPass(); } } +char LazyValueAnalysis::PassID; //===----------------------------------------------------------------------===// // LVILatticeVal @@ -63,19 +64,24 @@ namespace llvm { namespace { class LVILatticeVal { enum LatticeValueTy { - /// This Value has no known value yet. + /// This Value has no known value yet. As a result, this implies the + /// producing instruction is dead. Caution: We use this as the starting + /// state in our local meet rules. In this usage, it's taken to mean + /// "nothing known yet". undefined, - /// This Value has a specific constant value. + /// This Value has a specific constant value. (For integers, constantrange + /// is used instead.) constant, - /// This Value is known to not have the specified value. + /// This Value is known to not have the specified value. (For integers, + /// constantrange is used instead.) notconstant, - /// The Value falls within this range. + /// The Value falls within this range. (Used only for integer typed values.) constantrange, - /// This value is not known to be constant, and we know that it has a value. + /// We can not precisely model the dynamic values this value might take. overdefined }; @@ -102,7 +108,7 @@ public: } static LVILatticeVal getRange(ConstantRange CR) { LVILatticeVal Res; - Res.markConstantRange(CR); + Res.markConstantRange(std::move(CR)); return Res; } static LVILatticeVal getOverdefined() { @@ -110,7 +116,7 @@ public: Res.markOverdefined(); return Res; } - + bool isUndefined() const { return Tag == undefined; } bool isConstant() const { return Tag == constant; } bool isNotConstant() const { return Tag == notconstant; } @@ -176,13 +182,13 @@ public: } /// Return true if this is a change in status. - bool markConstantRange(const ConstantRange NewR) { + bool markConstantRange(ConstantRange NewR) { if (isConstantRange()) { if (NewR.isEmptySet()) return markOverdefined(); bool changed = Range != NewR; - Range = NewR; + Range = std::move(NewR); return changed; } @@ -191,7 +197,7 @@ public: return markOverdefined(); Tag = constantrange; - Range = NewR; + Range = std::move(NewR); return true; } @@ -230,11 +236,6 @@ public: return markOverdefined(); } - // RHS is a ConstantRange, LHS is a non-integer Constant. - - // FIXME: consider the case where RHS is a range [1, 0) and LHS is - // a function. The correct result is to pick up RHS. - return markOverdefined(); } @@ -287,13 +288,76 @@ raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) { if (Val.isNotConstant()) return OS << "notconstant<" << *Val.getNotConstant() << '>'; - else if (Val.isConstantRange()) + if (Val.isConstantRange()) return OS << "constantrange<" << Val.getConstantRange().getLower() << ", " << Val.getConstantRange().getUpper() << '>'; return OS << "constant<" << *Val.getConstant() << '>'; } } +/// Returns true if this lattice value represents at most one possible value. +/// This is as precise as any lattice value can get while still representing +/// reachable code. +static bool hasSingleValue(const LVILatticeVal &Val) { + if (Val.isConstantRange() && + Val.getConstantRange().isSingleElement()) + // Integer constants are single element ranges + return true; + if (Val.isConstant()) + // Non integer constants + return true; + return false; +} + +/// Combine two sets of facts about the same value into a single set of +/// facts. Note that this method is not suitable for merging facts along +/// different paths in a CFG; that's what the mergeIn function is for. This +/// is for merging facts gathered about the same value at the same location +/// through two independent means. +/// Notes: +/// * This method does not promise to return the most precise possible lattice +/// value implied by A and B. It is allowed to return any lattice element +/// which is at least as strong as *either* A or B (unless our facts +/// conflict, see below). +/// * Due to unreachable code, the intersection of two lattice values could be +/// contradictory. If this happens, we return some valid lattice value so as +/// not confuse the rest of LVI. Ideally, we'd always return Undefined, but +/// we do not make this guarantee. TODO: This would be a useful enhancement. +static LVILatticeVal intersect(LVILatticeVal A, LVILatticeVal B) { + // Undefined is the strongest state. It means the value is known to be along + // an unreachable path. + if (A.isUndefined()) + return A; + if (B.isUndefined()) + return B; + + // If we gave up for one, but got a useable fact from the other, use it. + if (A.isOverdefined()) + return B; + if (B.isOverdefined()) + return A; + + // Can't get any more precise than constants. + if (hasSingleValue(A)) + return A; + if (hasSingleValue(B)) + return B; + + // Could be either constant range or not constant here. + if (!A.isConstantRange() || !B.isConstantRange()) { + // TODO: Arbitrary choice, could be improved + return A; + } + + // Intersect two constant ranges + ConstantRange Range = + A.getConstantRange().intersectWith(B.getConstantRange()); + // Note: An empty range is implicitly converted to overdefined internally. + // TODO: We could instead use Undefined here since we've proven a conflict + // and thus know this path must be unreachable. + return LVILatticeVal::getRange(std::move(Range)); +} + //===----------------------------------------------------------------------===// // LazyValueInfoCache Decl //===----------------------------------------------------------------------===// @@ -354,6 +418,8 @@ namespace { if (!BlockValueSet.insert(BV).second) return false; // It's already in the stack. + DEBUG(dbgs() << "PUSH: " << *BV.second << " in " << BV.first->getName() + << "\n"); BlockValueStack.push(BV); return true; } @@ -375,30 +441,31 @@ namespace { lookup(Val)[BB] = Result; } - LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB); - bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T, - LVILatticeVal &Result, - Instruction *CxtI = nullptr); - bool hasBlockValue(Value *Val, BasicBlock *BB); - - // These methods process one work item and may add more. A false value - // returned means that the work item was not completely processed and must - // be revisited after going through the new items. - bool solveBlockValue(Value *Val, BasicBlock *BB); - bool solveBlockValueNonLocal(LVILatticeVal &BBLV, - Value *Val, BasicBlock *BB); - bool solveBlockValuePHINode(LVILatticeVal &BBLV, - PHINode *PN, BasicBlock *BB); - bool solveBlockValueConstantRange(LVILatticeVal &BBLV, - Instruction *BBI, BasicBlock *BB); - void mergeAssumeBlockValueConstantRange(Value *Val, LVILatticeVal &BBLV, - Instruction *BBI); - - void solve(); - - ValueCacheEntryTy &lookup(Value *V) { - return ValueCache[LVIValueHandle(V, this)]; - } + LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB); + bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T, + LVILatticeVal &Result, Instruction *CxtI = nullptr); + bool hasBlockValue(Value *Val, BasicBlock *BB); + + // These methods process one work item and may add more. A false value + // returned means that the work item was not completely processed and must + // be revisited after going through the new items. + bool solveBlockValue(Value *Val, BasicBlock *BB); + bool solveBlockValueNonLocal(LVILatticeVal &BBLV, Value *Val, BasicBlock *BB); + bool solveBlockValuePHINode(LVILatticeVal &BBLV, PHINode *PN, BasicBlock *BB); + bool solveBlockValueSelect(LVILatticeVal &BBLV, SelectInst *S, + BasicBlock *BB); + bool solveBlockValueBinaryOp(LVILatticeVal &BBLV, Instruction *BBI, + BasicBlock *BB); + bool solveBlockValueCast(LVILatticeVal &BBLV, Instruction *BBI, + BasicBlock *BB); + void intersectAssumeBlockValueConstantRange(Value *Val, LVILatticeVal &BBLV, + Instruction *BBI); + + void solve(); + + ValueCacheEntryTy &lookup(Value *V) { + return ValueCache[LVIValueHandle(V, this)]; + } bool isOverdefined(Value *V, BasicBlock *BB) const { auto ODI = OverDefinedCache.find(BB); @@ -427,7 +494,7 @@ namespace { return lookup(V)[BB]; } - + public: /// This is the query interface to determine the lattice /// value for the specified Value* at the end of the specified block. @@ -493,8 +560,8 @@ void LazyValueInfoCache::eraseBlock(BasicBlock *BB) { if (ODI != OverDefinedCache.end()) OverDefinedCache.erase(ODI); - for (auto I = ValueCache.begin(), E = ValueCache.end(); I != E; ++I) - I->second.erase(BB); + for (auto &I : ValueCache) + I.second.erase(BB); } void LazyValueInfoCache::solve() { @@ -508,6 +575,9 @@ void LazyValueInfoCache::solve() { assert(hasCachedValueInfo(e.second, e.first) && "Result should be in cache!"); + DEBUG(dbgs() << "POP " << *e.second << " in " << e.first->getName() + << " = " << getCachedValueInfo(e.second, e.first) << "\n"); + BlockValueStack.pop(); BlockValueSet.erase(e); } else { @@ -542,15 +612,12 @@ static LVILatticeVal getFromRangeMetadata(Instruction *BBI) { case Instruction::Invoke: if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range)) if (isa<IntegerType>(BBI->getType())) { - ConstantRange Result = getConstantRangeFromMetadata(*Ranges); - return LVILatticeVal::getRange(Result); + return LVILatticeVal::getRange(getConstantRangeFromMetadata(*Ranges)); } break; }; - // Nothing known - Note that we do not want overdefined here. We may know - // something else about the value and not having range metadata shouldn't - // cause us to throw away those facts. - return LVILatticeVal(); + // Nothing known - will be intersected with other facts + return LVILatticeVal::getOverdefined(); } bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) { @@ -587,44 +654,47 @@ bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) { return true; } - // If this value is a nonnull pointer, record it's range and bailout. - PointerType *PT = dyn_cast<PointerType>(BBI->getType()); - if (PT && isKnownNonNull(BBI)) { - Res = LVILatticeVal::getNot(ConstantPointerNull::get(PT)); + if (auto *SI = dyn_cast<SelectInst>(BBI)) { + if (!solveBlockValueSelect(Res, SI, BB)) + return false; insertResult(Val, BB, Res); return true; } - // If this is an instruction which supports range metadata, return the - // implied range. TODO: This should be an intersection, not a union. - Res.mergeIn(getFromRangeMetadata(BBI), DL); - - // We can only analyze the definitions of certain classes of instructions - // (integral binops and casts at the moment), so bail if this isn't one. - LVILatticeVal Result; - if ((!isa<BinaryOperator>(BBI) && !isa<CastInst>(BBI)) || - !BBI->getType()->isIntegerTy()) { - DEBUG(dbgs() << " compute BB '" << BB->getName() - << "' - overdefined because inst def found.\n"); - Res.markOverdefined(); + // If this value is a nonnull pointer, record it's range and bailout. Note + // that for all other pointer typed values, we terminate the search at the + // definition. We could easily extend this to look through geps, bitcasts, + // and the like to prove non-nullness, but it's not clear that's worth it + // compile time wise. The context-insensative value walk done inside + // isKnownNonNull gets most of the profitable cases at much less expense. + // This does mean that we have a sensativity to where the defining + // instruction is placed, even if it could legally be hoisted much higher. + // That is unfortunate. + PointerType *PT = dyn_cast<PointerType>(BBI->getType()); + if (PT && isKnownNonNull(BBI)) { + Res = LVILatticeVal::getNot(ConstantPointerNull::get(PT)); insertResult(Val, BB, Res); return true; } - - // FIXME: We're currently limited to binops with a constant RHS. This should - // be improved. - BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI); - if (BO && !isa<ConstantInt>(BO->getOperand(1))) { - DEBUG(dbgs() << " compute BB '" << BB->getName() - << "' - overdefined because inst def found.\n"); - - Res.markOverdefined(); - insertResult(Val, BB, Res); - return true; + if (BBI->getType()->isIntegerTy()) { + if (isa<CastInst>(BBI)) { + if (!solveBlockValueCast(Res, BBI, BB)) + return false; + insertResult(Val, BB, Res); + return true; + } + BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI); + if (BO && isa<ConstantInt>(BO->getOperand(1))) { + if (!solveBlockValueBinaryOp(Res, BBI, BB)) + return false; + insertResult(Val, BB, Res); + return true; + } } - if (!solveBlockValueConstantRange(Res, BBI, BB)) - return false; + DEBUG(dbgs() << " compute BB '" << BB->getName() + << "' - unknown inst def found.\n"); + Res = getFromRangeMetadata(BBI); insertResult(Val, BB, Res); return true; } @@ -660,37 +730,36 @@ static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) { return false; } +/// Return true if the allocation associated with Val is ever dereferenced +/// within the given basic block. This establishes the fact Val is not null, +/// but does not imply that the memory at Val is dereferenceable. (Val may +/// point off the end of the dereferenceable part of the object.) +static bool isObjectDereferencedInBlock(Value *Val, BasicBlock *BB) { + assert(Val->getType()->isPointerTy()); + + const DataLayout &DL = BB->getModule()->getDataLayout(); + Value *UnderlyingVal = GetUnderlyingObject(Val, DL); + // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge + // inside InstructionDereferencesPointer either. + if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1)) + for (Instruction &I : *BB) + if (InstructionDereferencesPointer(&I, UnderlyingVal)) + return true; + return false; +} + bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV, Value *Val, BasicBlock *BB) { LVILatticeVal Result; // Start Undefined. - // If this is a pointer, and there's a load from that pointer in this BB, - // then we know that the pointer can't be NULL. - bool NotNull = false; - if (Val->getType()->isPointerTy()) { - if (isKnownNonNull(Val)) { - NotNull = true; - } else { - const DataLayout &DL = BB->getModule()->getDataLayout(); - Value *UnderlyingVal = GetUnderlyingObject(Val, DL); - // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge - // inside InstructionDereferencesPointer either. - if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1)) { - for (Instruction &I : *BB) { - if (InstructionDereferencesPointer(&I, UnderlyingVal)) { - NotNull = true; - break; - } - } - } - } - } - // If this is the entry block, we must be asking about an argument. The // value is overdefined. if (BB == &BB->getParent()->getEntryBlock()) { assert(isa<Argument>(Val) && "Unknown live-in to the entry block"); - if (NotNull) { + // Bofore giving up, see if we can prove the pointer non-null local to + // this particular block. + if (Val->getType()->isPointerTy() && + (isKnownNonNull(Val) || isObjectDereferencedInBlock(Val, BB))) { PointerType *PTy = cast<PointerType>(Val->getType()); Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy)); } else { @@ -715,10 +784,11 @@ bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV, // to overdefined. if (Result.isOverdefined()) { DEBUG(dbgs() << " compute BB '" << BB->getName() - << "' - overdefined because of pred.\n"); - // If we previously determined that this is a pointer that can't be null - // then return that rather than giving up entirely. - if (NotNull) { + << "' - overdefined because of pred (non local).\n"); + // Bofore giving up, see if we can prove the pointer non-null local to + // this particular block. + if (Val->getType()->isPointerTy() && + isObjectDereferencedInBlock(Val, BB)) { PointerType *PTy = cast<PointerType>(Val->getType()); Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy)); } @@ -760,7 +830,7 @@ bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV, // to overdefined. if (Result.isOverdefined()) { DEBUG(dbgs() << " compute BB '" << BB->getName() - << "' - overdefined because of pred.\n"); + << "' - overdefined because of pred (local).\n"); BBLV = Result; return true; @@ -779,10 +849,9 @@ static bool getValueFromFromCondition(Value *Val, ICmpInst *ICI, LVILatticeVal &Result, bool isTrueDest = true); -// If we can determine a constant range for the value Val in the context -// provided by the instruction BBI, then merge it into BBLV. If we did find a -// constant range, return true. -void LazyValueInfoCache::mergeAssumeBlockValueConstantRange(Value *Val, +// If we can determine a constraint on the value given conditions assumed by +// the program, intersect those constraints with BBLV +void LazyValueInfoCache::intersectAssumeBlockValueConstantRange(Value *Val, LVILatticeVal &BBLV, Instruction *BBI) { BBI = BBI ? BBI : dyn_cast<Instruction>(Val); @@ -799,46 +868,264 @@ void LazyValueInfoCache::mergeAssumeBlockValueConstantRange(Value *Val, Value *C = I->getArgOperand(0); if (ICmpInst *ICI = dyn_cast<ICmpInst>(C)) { LVILatticeVal Result; - if (getValueFromFromCondition(Val, ICI, Result)) { - if (BBLV.isOverdefined()) - BBLV = Result; - else - BBLV.mergeIn(Result, DL); - } + if (getValueFromFromCondition(Val, ICI, Result)) + BBLV = intersect(BBLV, Result); } } } -bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV, - Instruction *BBI, - BasicBlock *BB) { - // Figure out the range of the LHS. If that fails, bail. - if (!hasBlockValue(BBI->getOperand(0), BB)) { - if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0)))) +bool LazyValueInfoCache::solveBlockValueSelect(LVILatticeVal &BBLV, + SelectInst *SI, BasicBlock *BB) { + + // Recurse on our inputs if needed + if (!hasBlockValue(SI->getTrueValue(), BB)) { + if (pushBlockValue(std::make_pair(BB, SI->getTrueValue()))) return false; BBLV.markOverdefined(); return true; } + LVILatticeVal TrueVal = getBlockValue(SI->getTrueValue(), BB); + // If we hit overdefined, don't ask more queries. We want to avoid poisoning + // extra slots in the table if we can. + if (TrueVal.isOverdefined()) { + BBLV.markOverdefined(); + return true; + } - LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB); - mergeAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI); - if (!LHSVal.isConstantRange()) { + if (!hasBlockValue(SI->getFalseValue(), BB)) { + if (pushBlockValue(std::make_pair(BB, SI->getFalseValue()))) + return false; + BBLV.markOverdefined(); + return true; + } + LVILatticeVal FalseVal = getBlockValue(SI->getFalseValue(), BB); + // If we hit overdefined, don't ask more queries. We want to avoid poisoning + // extra slots in the table if we can. + if (FalseVal.isOverdefined()) { BBLV.markOverdefined(); return true; } - ConstantRange LHSRange = LHSVal.getConstantRange(); - ConstantRange RHSRange(1); - IntegerType *ResultTy = cast<IntegerType>(BBI->getType()); - if (isa<BinaryOperator>(BBI)) { - if (ConstantInt *RHS = dyn_cast<ConstantInt>(BBI->getOperand(1))) { - RHSRange = ConstantRange(RHS->getValue()); - } else { - BBLV.markOverdefined(); - return true; + if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) { + ConstantRange TrueCR = TrueVal.getConstantRange(); + ConstantRange FalseCR = FalseVal.getConstantRange(); + Value *LHS = nullptr; + Value *RHS = nullptr; + SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS); + // Is this a min specifically of our two inputs? (Avoid the risk of + // ValueTracking getting smarter looking back past our immediate inputs.) + if (SelectPatternResult::isMinOrMax(SPR.Flavor) && + LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) { + switch (SPR.Flavor) { + default: + llvm_unreachable("unexpected minmax type!"); + case SPF_SMIN: /// Signed minimum + BBLV.markConstantRange(TrueCR.smin(FalseCR)); + return true; + case SPF_UMIN: /// Unsigned minimum + BBLV.markConstantRange(TrueCR.umin(FalseCR)); + return true; + case SPF_SMAX: /// Signed maximum + BBLV.markConstantRange(TrueCR.smax(FalseCR)); + return true; + case SPF_UMAX: /// Unsigned maximum + BBLV.markConstantRange(TrueCR.umax(FalseCR)); + return true; + }; + } + + // TODO: ABS, NABS from the SelectPatternResult + } + + // Can we constrain the facts about the true and false values by using the + // condition itself? This shows up with idioms like e.g. select(a > 5, a, 5). + // TODO: We could potentially refine an overdefined true value above. + if (auto *ICI = dyn_cast<ICmpInst>(SI->getCondition())) { + LVILatticeVal TrueValTaken, FalseValTaken; + if (!getValueFromFromCondition(SI->getTrueValue(), ICI, + TrueValTaken, true)) + TrueValTaken.markOverdefined(); + if (!getValueFromFromCondition(SI->getFalseValue(), ICI, + FalseValTaken, false)) + FalseValTaken.markOverdefined(); + + TrueVal = intersect(TrueVal, TrueValTaken); + FalseVal = intersect(FalseVal, FalseValTaken); + + + // Handle clamp idioms such as: + // %24 = constantrange<0, 17> + // %39 = icmp eq i32 %24, 0 + // %40 = add i32 %24, -1 + // %siv.next = select i1 %39, i32 16, i32 %40 + // %siv.next = constantrange<0, 17> not <-1, 17> + // In general, this can handle any clamp idiom which tests the edge + // condition via an equality or inequality. + ICmpInst::Predicate Pred = ICI->getPredicate(); + Value *A = ICI->getOperand(0); + if (ConstantInt *CIBase = dyn_cast<ConstantInt>(ICI->getOperand(1))) { + auto addConstants = [](ConstantInt *A, ConstantInt *B) { + assert(A->getType() == B->getType()); + return ConstantInt::get(A->getType(), A->getValue() + B->getValue()); + }; + // See if either input is A + C2, subject to the constraint from the + // condition that A != C when that input is used. We can assume that + // that input doesn't include C + C2. + ConstantInt *CIAdded; + switch (Pred) { + default: break; + case ICmpInst::ICMP_EQ: + if (match(SI->getFalseValue(), m_Add(m_Specific(A), + m_ConstantInt(CIAdded)))) { + auto ResNot = addConstants(CIBase, CIAdded); + FalseVal = intersect(FalseVal, + LVILatticeVal::getNot(ResNot)); + } + break; + case ICmpInst::ICMP_NE: + if (match(SI->getTrueValue(), m_Add(m_Specific(A), + m_ConstantInt(CIAdded)))) { + auto ResNot = addConstants(CIBase, CIAdded); + TrueVal = intersect(TrueVal, + LVILatticeVal::getNot(ResNot)); + } + break; + }; } } + LVILatticeVal Result; // Start Undefined. + Result.mergeIn(TrueVal, DL); + Result.mergeIn(FalseVal, DL); + BBLV = Result; + return true; +} + +bool LazyValueInfoCache::solveBlockValueCast(LVILatticeVal &BBLV, + Instruction *BBI, + BasicBlock *BB) { + if (!BBI->getOperand(0)->getType()->isSized()) { + // Without knowing how wide the input is, we can't analyze it in any useful + // way. + BBLV.markOverdefined(); + return true; + } + + // Filter out casts we don't know how to reason about before attempting to + // recurse on our operand. This can cut a long search short if we know we're + // not going to be able to get any useful information anways. + switch (BBI->getOpcode()) { + case Instruction::Trunc: + case Instruction::SExt: + case Instruction::ZExt: + case Instruction::BitCast: + break; + default: + // Unhandled instructions are overdefined. + DEBUG(dbgs() << " compute BB '" << BB->getName() + << "' - overdefined (unknown cast).\n"); + BBLV.markOverdefined(); + return true; + } + + // Figure out the range of the LHS. If that fails, we still apply the + // transfer rule on the full set since we may be able to locally infer + // interesting facts. + if (!hasBlockValue(BBI->getOperand(0), BB)) + if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0)))) + // More work to do before applying this transfer rule. + return false; + + const unsigned OperandBitWidth = + DL.getTypeSizeInBits(BBI->getOperand(0)->getType()); + ConstantRange LHSRange = ConstantRange(OperandBitWidth); + if (hasBlockValue(BBI->getOperand(0), BB)) { + LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB); + intersectAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI); + if (LHSVal.isConstantRange()) + LHSRange = LHSVal.getConstantRange(); + } + + const unsigned ResultBitWidth = + cast<IntegerType>(BBI->getType())->getBitWidth(); + + // NOTE: We're currently limited by the set of operations that ConstantRange + // can evaluate symbolically. Enhancing that set will allows us to analyze + // more definitions. + LVILatticeVal Result; + switch (BBI->getOpcode()) { + case Instruction::Trunc: + Result.markConstantRange(LHSRange.truncate(ResultBitWidth)); + break; + case Instruction::SExt: + Result.markConstantRange(LHSRange.signExtend(ResultBitWidth)); + break; + case Instruction::ZExt: + Result.markConstantRange(LHSRange.zeroExtend(ResultBitWidth)); + break; + case Instruction::BitCast: + Result.markConstantRange(LHSRange); + break; + default: + // Should be dead if the code above is correct + llvm_unreachable("inconsistent with above"); + break; + } + + BBLV = Result; + return true; +} + +bool LazyValueInfoCache::solveBlockValueBinaryOp(LVILatticeVal &BBLV, + Instruction *BBI, + BasicBlock *BB) { + + assert(BBI->getOperand(0)->getType()->isSized() && + "all operands to binary operators are sized"); + + // Filter out operators we don't know how to reason about before attempting to + // recurse on our operand(s). This can cut a long search short if we know + // we're not going to be able to get any useful information anways. + switch (BBI->getOpcode()) { + case Instruction::Add: + case Instruction::Sub: + case Instruction::Mul: + case Instruction::UDiv: + case Instruction::Shl: + case Instruction::LShr: + case Instruction::And: + case Instruction::Or: + // continue into the code below + break; + default: + // Unhandled instructions are overdefined. + DEBUG(dbgs() << " compute BB '" << BB->getName() + << "' - overdefined (unknown binary operator).\n"); + BBLV.markOverdefined(); + return true; + }; + + // Figure out the range of the LHS. If that fails, use a conservative range, + // but apply the transfer rule anyways. This lets us pick up facts from + // expressions like "and i32 (call i32 @foo()), 32" + if (!hasBlockValue(BBI->getOperand(0), BB)) + if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0)))) + // More work to do before applying this transfer rule. + return false; + + const unsigned OperandBitWidth = + DL.getTypeSizeInBits(BBI->getOperand(0)->getType()); + ConstantRange LHSRange = ConstantRange(OperandBitWidth); + if (hasBlockValue(BBI->getOperand(0), BB)) { + LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB); + intersectAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI); + if (LHSVal.isConstantRange()) + LHSRange = LHSVal.getConstantRange(); + } + + ConstantInt *RHS = cast<ConstantInt>(BBI->getOperand(1)); + ConstantRange RHSRange = ConstantRange(RHS->getValue()); + // NOTE: We're currently limited by the set of operations that ConstantRange // can evaluate symbolically. Enhancing that set will allows us to analyze // more definitions. @@ -862,30 +1149,15 @@ bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV, case Instruction::LShr: Result.markConstantRange(LHSRange.lshr(RHSRange)); break; - case Instruction::Trunc: - Result.markConstantRange(LHSRange.truncate(ResultTy->getBitWidth())); - break; - case Instruction::SExt: - Result.markConstantRange(LHSRange.signExtend(ResultTy->getBitWidth())); - break; - case Instruction::ZExt: - Result.markConstantRange(LHSRange.zeroExtend(ResultTy->getBitWidth())); - break; - case Instruction::BitCast: - Result.markConstantRange(LHSRange); - break; case Instruction::And: Result.markConstantRange(LHSRange.binaryAnd(RHSRange)); break; case Instruction::Or: Result.markConstantRange(LHSRange.binaryOr(RHSRange)); break; - - // Unhandled instructions are overdefined. default: - DEBUG(dbgs() << " compute BB '" << BB->getName() - << "' - overdefined because inst def found.\n"); - Result.markOverdefined(); + // Should be dead if the code above is correct + llvm_unreachable("inconsistent with above"); break; } @@ -895,10 +1167,11 @@ bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV, bool getValueFromFromCondition(Value *Val, ICmpInst *ICI, LVILatticeVal &Result, bool isTrueDest) { - if (ICI && isa<Constant>(ICI->getOperand(1))) { + assert(ICI && "precondition"); + if (isa<Constant>(ICI->getOperand(1))) { if (ICI->isEquality() && ICI->getOperand(0) == Val) { // We know that V has the RHS constant if this is a true SETEQ or - // false SETNE. + // false SETNE. if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ)) Result = LVILatticeVal::get(cast<Constant>(ICI->getOperand(1))); else @@ -926,7 +1199,7 @@ bool getValueFromFromCondition(Value *Val, ICmpInst *ICI, // If we're interested in the false dest, invert the condition. if (!isTrueDest) TrueValues = TrueValues.inverse(); - Result = LVILatticeVal::getRange(TrueValues); + Result = LVILatticeVal::getRange(std::move(TrueValues)); return true; } } @@ -935,7 +1208,8 @@ bool getValueFromFromCondition(Value *Val, ICmpInst *ICI, } /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if -/// Val is not constrained on the edge. +/// Val is not constrained on the edge. Result is unspecified if return value +/// is false. static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, BasicBlock *BBTo, LVILatticeVal &Result) { // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we @@ -985,7 +1259,7 @@ static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, } else if (i.getCaseSuccessor() == BBTo) EdgesVals = EdgesVals.unionWith(EdgeVal); } - Result = LVILatticeVal::getRange(EdgesVals); + Result = LVILatticeVal::getRange(std::move(EdgesVals)); return true; } return false; @@ -1002,46 +1276,29 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom, return true; } - if (getEdgeValueLocal(Val, BBFrom, BBTo, Result)) { - if (!Result.isConstantRange() || - Result.getConstantRange().getSingleElement()) - return true; - - // FIXME: this check should be moved to the beginning of the function when - // LVI better supports recursive values. Even for the single value case, we - // can intersect to detect dead code (an empty range). - if (!hasBlockValue(Val, BBFrom)) { - if (pushBlockValue(std::make_pair(BBFrom, Val))) - return false; - Result.markOverdefined(); - return true; - } - - // Try to intersect ranges of the BB and the constraint on the edge. - LVILatticeVal InBlock = getBlockValue(Val, BBFrom); - mergeAssumeBlockValueConstantRange(Val, InBlock, BBFrom->getTerminator()); - // See note on the use of the CxtI with mergeAssumeBlockValueConstantRange, - // and caching, below. - mergeAssumeBlockValueConstantRange(Val, InBlock, CxtI); - if (!InBlock.isConstantRange()) - return true; + LVILatticeVal LocalResult; + if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult)) + // If we couldn't constrain the value on the edge, LocalResult doesn't + // provide any information. + LocalResult.markOverdefined(); - ConstantRange Range = - Result.getConstantRange().intersectWith(InBlock.getConstantRange()); - Result = LVILatticeVal::getRange(Range); + if (hasSingleValue(LocalResult)) { + // Can't get any more precise here + Result = LocalResult; return true; } if (!hasBlockValue(Val, BBFrom)) { if (pushBlockValue(std::make_pair(BBFrom, Val))) return false; - Result.markOverdefined(); + // No new information. + Result = LocalResult; return true; } - // If we couldn't compute the value on the edge, use the value from the BB. - Result = getBlockValue(Val, BBFrom); - mergeAssumeBlockValueConstantRange(Val, Result, BBFrom->getTerminator()); + // Try to intersect ranges of the BB and the constraint on the edge. + LVILatticeVal InBlock = getBlockValue(Val, BBFrom); + intersectAssumeBlockValueConstantRange(Val, InBlock, BBFrom->getTerminator()); // We can use the context instruction (generically the ultimate instruction // the calling pass is trying to simplify) here, even though the result of // this function is generally cached when called from the solve* functions @@ -1050,7 +1307,9 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom, // functions, the context instruction is not provided. When called from // LazyValueInfoCache::getValueOnEdge, the context instruction is provided, // but then the result is not cached. - mergeAssumeBlockValueConstantRange(Val, Result, CxtI); + intersectAssumeBlockValueConstantRange(Val, InBlock, CxtI); + + Result = intersect(LocalResult, InBlock); return true; } @@ -1060,11 +1319,12 @@ LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB, << BB->getName() << "'\n"); assert(BlockValueStack.empty() && BlockValueSet.empty()); - pushBlockValue(std::make_pair(BB, V)); - - solve(); + if (!hasBlockValue(V, BB)) { + pushBlockValue(std::make_pair(BB, V)); + solve(); + } LVILatticeVal Result = getBlockValue(V, BB); - mergeAssumeBlockValueConstantRange(V, Result, CxtI); + intersectAssumeBlockValueConstantRange(V, Result, CxtI); DEBUG(dbgs() << " Result = " << Result << "\n"); return Result; @@ -1074,10 +1334,13 @@ LVILatticeVal LazyValueInfoCache::getValueAt(Value *V, Instruction *CxtI) { DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName() << "'\n"); - LVILatticeVal Result; + if (auto *C = dyn_cast<Constant>(V)) + return LVILatticeVal::get(C); + + LVILatticeVal Result = LVILatticeVal::getOverdefined(); if (auto *I = dyn_cast<Instruction>(V)) Result = getFromRangeMetadata(I); - mergeAssumeBlockValueConstantRange(V, Result, CxtI); + intersectAssumeBlockValueConstantRange(V, Result, CxtI); DEBUG(dbgs() << " Result = " << Result << "\n"); return Result; @@ -1172,29 +1435,32 @@ static LazyValueInfoCache &getCache(void *&PImpl, AssumptionCache *AC, return *static_cast<LazyValueInfoCache*>(PImpl); } -bool LazyValueInfo::runOnFunction(Function &F) { - AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); +bool LazyValueInfoWrapperPass::runOnFunction(Function &F) { + Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); const DataLayout &DL = F.getParent()->getDataLayout(); DominatorTreeWrapperPass *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); - DT = DTWP ? &DTWP->getDomTree() : nullptr; - - TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); + Info.DT = DTWP ? &DTWP->getDomTree() : nullptr; + Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); - if (PImpl) - getCache(PImpl, AC, &DL, DT).clear(); + if (Info.PImpl) + getCache(Info.PImpl, Info.AC, &DL, Info.DT).clear(); // Fully lazy. return false; } -void LazyValueInfo::getAnalysisUsage(AnalysisUsage &AU) const { +void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequired<AssumptionCacheTracker>(); AU.addRequired<TargetLibraryInfoWrapperPass>(); } +LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; } + +LazyValueInfo::~LazyValueInfo() { releaseMemory(); } + void LazyValueInfo::releaseMemory() { // If the cache was allocated, free it. if (PImpl) { @@ -1203,6 +1469,16 @@ void LazyValueInfo::releaseMemory() { } } +void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); } + +LazyValueInfo LazyValueAnalysis::run(Function &F, FunctionAnalysisManager &FAM) { + auto &AC = FAM.getResult<AssumptionAnalysis>(F); + auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F); + auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F); + + return LazyValueInfo(&AC, &TLI, DT); +} + /// Returns true if we can statically tell that this value will never be a /// "useful" constant. In practice, this means we've got something like an @@ -1238,6 +1514,21 @@ Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB, return nullptr; } +ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB, + Instruction *CxtI) { + assert(V->getType()->isIntegerTy()); + unsigned Width = V->getType()->getIntegerBitWidth(); + const DataLayout &DL = BB->getModule()->getDataLayout(); + LVILatticeVal Result = + getCache(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI); + assert(!Result.isConstant()); + if (Result.isUndefined()) + return ConstantRange(Width, /*isFullSet=*/false); + if (Result.isConstantRange()) + return Result.getConstantRange(); + return ConstantRange(Width, /*isFullSet=*/true); +} + /// Determine whether the specified value is known to be a /// constant on the specified edge. Return null if not. Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB, @@ -1379,7 +1670,7 @@ LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C, // We limit the search to one step backwards from the current BB and value. // We could consider extending this to search further backwards through the // CFG and/or value graph, but there are non-obvious compile time vs quality - // tradeoffs. + // tradeoffs. if (CxtI) { BasicBlock *BB = CxtI->getParent(); @@ -1399,10 +1690,10 @@ LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C, for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) { Value *Incoming = PHI->getIncomingValue(i); BasicBlock *PredBB = PHI->getIncomingBlock(i); - // Note that PredBB may be BB itself. + // Note that PredBB may be BB itself. Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB, CxtI); - + // Keep going as long as we've seen a consistent known result for // all inputs. Baseline = (i == 0) ? Result /* First iteration */ |
