Index: include/llvm/Analysis/LazyValueInfo.h =================================================================== --- include/llvm/Analysis/LazyValueInfo.h +++ include/llvm/Analysis/LazyValueInfo.h @@ -18,16 +18,21 @@ #include "llvm/Pass.h" namespace llvm { + class AssumptionTracker; class Constant; class DataLayout; + class DominatorTree; + class Instruction; class TargetLibraryInfo; class Value; /// LazyValueInfo - This pass computes, caches, and vends lazy value constraint /// information. class LazyValueInfo : public FunctionPass { + AssumptionTracker *AT; const DataLayout *DL; class TargetLibraryInfo *TLI; + DominatorTree *DT; void *PImpl; LazyValueInfo(const LazyValueInfo&) LLVM_DELETED_FUNCTION; void operator=(const LazyValueInfo&) LLVM_DELETED_FUNCTION; @@ -50,16 +55,23 @@ /// with a constant is known to be true or false on the specified CFG edge. /// Pred is a CmpInst predicate. Tristate getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, - BasicBlock *FromBB, BasicBlock *ToBB); - + BasicBlock *FromBB, BasicBlock *ToBB, + Instruction *CxtI = nullptr); + /// getPredicateAt - Determine whether the specified value comparison + /// with a constant is known to be true or false at the specified instruction + /// (from an assume intrinsic). Pred is a CmpInst predicate. + Tristate getPredicateAt(unsigned Pred, Value *V, Constant *C, + Instruction *CxtI); + /// getConstant - Determine whether the specified value is known to be a /// constant at the end of the specified block. Return null if not. - Constant *getConstant(Value *V, BasicBlock *BB); + Constant *getConstant(Value *V, BasicBlock *BB, Instruction *CxtI = nullptr); /// getConstantOnEdge - Determine whether the specified value is known to be a /// constant on the specified edge. Return null if not. - Constant *getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB); + Constant *getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, + Instruction *CxtI = nullptr); /// threadEdge - Inform the analysis cache that we have threaded an edge from /// PredBB to OldSucc to be from PredBB to NewSucc instead. Index: lib/Analysis/LazyValueInfo.cpp =================================================================== --- lib/Analysis/LazyValueInfo.cpp +++ lib/Analysis/LazyValueInfo.cpp @@ -15,12 +15,14 @@ #include "llvm/Analysis/LazyValueInfo.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/Analysis/AssumptionTracker.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/CFG.h" #include "llvm/IR/ConstantRange.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" +#include "llvm/IR/Dominators.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/PatternMatch.h" @@ -38,6 +40,7 @@ char LazyValueInfo::ID = 0; INITIALIZE_PASS_BEGIN(LazyValueInfo, "lazy-value-info", "Lazy Value Information Analysis", false, true) +INITIALIZE_PASS_DEPENDENCY(AssumptionTracker) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) INITIALIZE_PASS_END(LazyValueInfo, "lazy-value-info", "Lazy Value Information Analysis", false, true) @@ -338,6 +341,13 @@ /// during a query. It basically emulates the callstack of the naive /// recursive value lookup process. std::stack > BlockValueStack; + + /// A pointer to the cache of @llvm.assume calls. + AssumptionTracker *AT; + /// An optional DL pointer. + const DataLayout *DL; + /// An optional DT pointer. + DominatorTree *DT; friend struct LVIValueHandle; @@ -364,7 +374,8 @@ LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB); bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T, - LVILatticeVal &Result); + LVILatticeVal &Result, + Instruction *CxtI = nullptr); bool hasBlockValue(Value *Val, BasicBlock *BB); // These methods process one work item and may add more. A false value @@ -377,6 +388,8 @@ PHINode *PN, BasicBlock *BB); bool solveBlockValueConstantRange(LVILatticeVal &BBLV, Instruction *BBI, BasicBlock *BB); + void mergeAssumeBlockValueConstantRange(Value *Val, LVILatticeVal &BBLV, + Instruction *BBI); void solve(); @@ -387,11 +400,18 @@ public: /// getValueInBlock - This is the query interface to determine the lattice /// value for the specified Value* at the end of the specified block. - LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB); + LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB, + Instruction *CxtI = nullptr); + + /// getValueAt - This is the query interface to determine the lattice + /// value for the specified Value* at the specified instruction (generally + /// from an assume intrinsic). + LVILatticeVal getValueAt(Value *V, Instruction *CxtI); /// getValueOnEdge - This is the query interface to determine the lattice /// value for the specified Value* that is true on the specified edge. - LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB); + LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB, + Instruction *CxtI = nullptr); /// threadEdge - This is the update interface to inform the cache that an /// edge from PredBB to OldSucc has been threaded to be from PredBB to @@ -408,6 +428,10 @@ ValueCache.clear(); OverDefinedCache.clear(); } + + LazyValueInfoCache(AssumptionTracker *AT, + const DataLayout *DL = nullptr, + DominatorTree *DT = nullptr) : AT(AT), DL(DL), DT(DT) {} }; } // end anonymous namespace @@ -669,7 +693,7 @@ BasicBlock *PhiBB = PN->getIncomingBlock(i); Value *PhiVal = PN->getIncomingValue(i); LVILatticeVal EdgeResult; - EdgesMissing |= !getEdgeValue(PhiVal, PhiBB, BB, EdgeResult); + EdgesMissing |= !getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN); if (EdgesMissing) continue; @@ -694,6 +718,36 @@ return true; } +static bool getValueFromFromCondition(Value *Val, ICmpInst *ICI, + LVILatticeVal &Result, + bool isTrueDest = true); + +// If we can determine a constant range for the value Val at 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, LVILatticeVal &BBLV, Instruction *BBI) { + BBI = BBI ? BBI : dyn_cast(Val); + if (!BBI) + return; + + for (auto &I : AT->assumptions(BBI->getParent()->getParent())) { + if (!isValidAssumeForContext(I, BBI, DL, DT)) + continue; + + Value *C = I->getArgOperand(0); + if (ICmpInst *ICI = dyn_cast(C)) { + LVILatticeVal Result; + if (getValueFromFromCondition(Val, ICI, Result)) { + if (BBLV.isOverdefined()) + BBLV = Result; + else + BBLV.mergeIn(Result); + } + } + } +} + bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV, Instruction *BBI, BasicBlock *BB) { @@ -704,6 +758,7 @@ } LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB); + mergeAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI); if (!LHSVal.isConstantRange()) { BBLV.markOverdefined(); return true; @@ -775,6 +830,47 @@ return true; } +bool getValueFromFromCondition(Value *Val, ICmpInst *ICI, + LVILatticeVal &Result, bool isTrueDest) { + if (ICI && isa(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. + if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ)) + Result = LVILatticeVal::get(cast(ICI->getOperand(1))); + else + Result = LVILatticeVal::getNot(cast(ICI->getOperand(1))); + return true; + } + + // Recognize the range checking idiom that InstCombine produces. + // (X-C1) u< C2 --> [C1, C1+C2) + ConstantInt *NegOffset = nullptr; + if (ICI->getPredicate() == ICmpInst::ICMP_ULT) + match(ICI->getOperand(0), m_Add(m_Specific(Val), + m_ConstantInt(NegOffset))); + + ConstantInt *CI = dyn_cast(ICI->getOperand(1)); + if (CI && (ICI->getOperand(0) == Val || NegOffset)) { + // Calculate the range of values that would satisfy the comparison. + ConstantRange CmpRange(CI->getValue()); + ConstantRange TrueValues = + ConstantRange::makeICmpRegion(ICI->getPredicate(), CmpRange); + + if (NegOffset) // Apply the offset from above. + TrueValues = TrueValues.subtract(NegOffset->getValue()); + + // If we're interested in the false dest, invert the condition. + if (!isTrueDest) TrueValues = TrueValues.inverse(); + + Result = LVILatticeVal::getRange(TrueValues); + return true; + } + } + + return false; +} + /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if /// Val is not constrained on the edge. static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, @@ -801,41 +897,8 @@ // If the condition of the branch is an equality comparison, we may be // able to infer the value. ICmpInst *ICI = dyn_cast(BI->getCondition()); - if (ICI && isa(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. - if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ)) - Result = LVILatticeVal::get(cast(ICI->getOperand(1))); - else - Result = LVILatticeVal::getNot(cast(ICI->getOperand(1))); - return true; - } - - // Recognize the range checking idiom that InstCombine produces. - // (X-C1) u< C2 --> [C1, C1+C2) - ConstantInt *NegOffset = nullptr; - if (ICI->getPredicate() == ICmpInst::ICMP_ULT) - match(ICI->getOperand(0), m_Add(m_Specific(Val), - m_ConstantInt(NegOffset))); - - ConstantInt *CI = dyn_cast(ICI->getOperand(1)); - if (CI && (ICI->getOperand(0) == Val || NegOffset)) { - // Calculate the range of values that would satisfy the comparison. - ConstantRange CmpRange(CI->getValue()); - ConstantRange TrueValues = - ConstantRange::makeICmpRegion(ICI->getPredicate(), CmpRange); - - if (NegOffset) // Apply the offset from above. - TrueValues = TrueValues.subtract(NegOffset->getValue()); - - // If we're interested in the false dest, invert the condition. - if (!isTrueDest) TrueValues = TrueValues.inverse(); - - Result = LVILatticeVal::getRange(TrueValues); - return true; - } - } + if (getValueFromFromCondition(Val, ICI, Result, isTrueDest)) + return true; } } @@ -869,7 +932,8 @@ /// \brief Compute the value of Val on the edge BBFrom -> BBTo, or the value at /// the basic block if the edge does not constraint Val. bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom, - BasicBlock *BBTo, LVILatticeVal &Result) { + BasicBlock *BBTo, LVILatticeVal &Result, + Instruction *CxtI) { // If already a constant, there is nothing to compute. if (Constant *VC = dyn_cast(Val)) { Result = LVILatticeVal::get(VC); @@ -891,6 +955,7 @@ // Try to intersect ranges of the BB and the constraint on the edge. LVILatticeVal InBlock = getBlockValue(Val, BBFrom); + mergeAssumeBlockValueConstantRange(Val, InBlock, CxtI); if (!InBlock.isConstantRange()) return true; @@ -907,30 +972,45 @@ // if we couldn't compute the value on the edge, use the value from the BB Result = getBlockValue(Val, BBFrom); + mergeAssumeBlockValueConstantRange(Val, Result, CxtI); return true; } -LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB) { +LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB, + Instruction *CxtI) { DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '" << BB->getName() << "'\n"); BlockValueStack.push(std::make_pair(BB, V)); solve(); LVILatticeVal Result = getBlockValue(V, BB); + mergeAssumeBlockValueConstantRange(V, Result, CxtI); + + DEBUG(dbgs() << " Result = " << Result << "\n"); + return Result; +} + +LVILatticeVal LazyValueInfoCache::getValueAt(Value *V, Instruction *CxtI) { + DEBUG(dbgs() << "LVI Getting value " << *V << " at '" + << CxtI->getName() << "'\n"); + + LVILatticeVal Result; + mergeAssumeBlockValueConstantRange(V, Result, CxtI); DEBUG(dbgs() << " Result = " << Result << "\n"); return Result; } LVILatticeVal LazyValueInfoCache:: -getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB) { +getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, + Instruction *CxtI) { DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '" << FromBB->getName() << "' to '" << ToBB->getName() << "'\n"); LVILatticeVal Result; - if (!getEdgeValue(V, FromBB, ToBB, Result)) { + if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) { solve(); - bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result); + bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI); (void)WasFastQuery; assert(WasFastQuery && "More work to do after problem solved?"); } @@ -1004,39 +1084,51 @@ //===----------------------------------------------------------------------===// /// getCache - This lazily constructs the LazyValueInfoCache. -static LazyValueInfoCache &getCache(void *&PImpl) { +static LazyValueInfoCache &getCache(void *&PImpl, + AssumptionTracker *AT, + const DataLayout *DL = nullptr, + DominatorTree *DT = nullptr) { if (!PImpl) - PImpl = new LazyValueInfoCache(); + PImpl = new LazyValueInfoCache(AT, DL, DT); return *static_cast(PImpl); } bool LazyValueInfo::runOnFunction(Function &F) { - if (PImpl) - getCache(PImpl).clear(); + AT = &getAnalysis(); + + DominatorTreeWrapperPass *DTWP = + getAnalysisIfAvailable(); + DT = DTWP ? &DTWP->getDomTree() : nullptr; DataLayoutPass *DLP = getAnalysisIfAvailable(); DL = DLP ? &DLP->getDataLayout() : nullptr; TLI = &getAnalysis(); + if (PImpl) + getCache(PImpl, AT, DL, DT).clear(); + // Fully lazy. return false; } void LazyValueInfo::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); + AU.addRequired(); AU.addRequired(); } void LazyValueInfo::releaseMemory() { // If the cache was allocated, free it. if (PImpl) { - delete &getCache(PImpl); + delete &getCache(PImpl, AT); PImpl = nullptr; } } -Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB) { - LVILatticeVal Result = getCache(PImpl).getValueInBlock(V, BB); +Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB, + Instruction *CxtI) { + LVILatticeVal Result = + getCache(PImpl, AT, DL, DT).getValueInBlock(V, BB, CxtI); if (Result.isConstant()) return Result.getConstant(); @@ -1051,8 +1143,10 @@ /// getConstantOnEdge - 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, - BasicBlock *ToBB) { - LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB); + BasicBlock *ToBB, + Instruction *CxtI) { + LVILatticeVal Result = + getCache(PImpl, AT, DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI); if (Result.isConstant()) return Result.getConstant(); @@ -1064,51 +1158,47 @@ return nullptr; } -/// getPredicateOnEdge - Determine whether the specified value comparison -/// with a constant is known to be true or false on the specified CFG edge. -/// Pred is a CmpInst predicate. -LazyValueInfo::Tristate -LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, - BasicBlock *FromBB, BasicBlock *ToBB) { - LVILatticeVal Result = getCache(PImpl).getValueOnEdge(V, FromBB, ToBB); - +static LazyValueInfo::Tristate +getPredicateResult(unsigned Pred, Constant *C, LVILatticeVal &Result, + const DataLayout *DL, TargetLibraryInfo *TLI) { + // If we know the value is a constant, evaluate the conditional. Constant *Res = nullptr; if (Result.isConstant()) { Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, DL, TLI); if (ConstantInt *ResCI = dyn_cast(Res)) - return ResCI->isZero() ? False : True; - return Unknown; + return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True; + return LazyValueInfo::Unknown; } if (Result.isConstantRange()) { ConstantInt *CI = dyn_cast(C); - if (!CI) return Unknown; + if (!CI) return LazyValueInfo::Unknown; ConstantRange CR = Result.getConstantRange(); if (Pred == ICmpInst::ICMP_EQ) { if (!CR.contains(CI->getValue())) - return False; + return LazyValueInfo::False; if (CR.isSingleElement() && CR.contains(CI->getValue())) - return True; + return LazyValueInfo::True; } else if (Pred == ICmpInst::ICMP_NE) { if (!CR.contains(CI->getValue())) - return True; + return LazyValueInfo::True; if (CR.isSingleElement() && CR.contains(CI->getValue())) - return False; + return LazyValueInfo::False; } // Handle more complex predicates. ConstantRange TrueValues = ICmpInst::makeConstantRange((ICmpInst::Predicate)Pred, CI->getValue()); if (TrueValues.contains(CR)) - return True; + return LazyValueInfo::True; if (TrueValues.inverse().contains(CR)) - return False; - return Unknown; + return LazyValueInfo::False; + return LazyValueInfo::Unknown; } if (Result.isNotConstant()) { @@ -1120,26 +1210,48 @@ Result.getNotConstant(), C, DL, TLI); if (Res->isNullValue()) - return False; + return LazyValueInfo::False; } else if (Pred == ICmpInst::ICMP_NE) { // !C1 != C -> true iff C1 == C. Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE, Result.getNotConstant(), C, DL, TLI); if (Res->isNullValue()) - return True; + return LazyValueInfo::True; } - return Unknown; + return LazyValueInfo::Unknown; } - return Unknown; + return LazyValueInfo::Unknown; +} + +/// getPredicateOnEdge - Determine whether the specified value comparison +/// with a constant is known to be true or false on the specified CFG edge. +/// Pred is a CmpInst predicate. +LazyValueInfo::Tristate +LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C, + BasicBlock *FromBB, BasicBlock *ToBB, + Instruction *CxtI) { + LVILatticeVal Result = + getCache(PImpl, AT, DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI); + + return getPredicateResult(Pred, C, Result, DL, TLI); +} + +LazyValueInfo::Tristate +LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C, + Instruction *CxtI) { + LVILatticeVal Result = + getCache(PImpl, AT, DL, DT).getValueAt(V, CxtI); + + return getPredicateResult(Pred, C, Result, DL, TLI); } void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc) { - if (PImpl) getCache(PImpl).threadEdge(PredBB, OldSucc, NewSucc); + if (PImpl) getCache(PImpl, AT, DL, DT).threadEdge(PredBB, OldSucc, NewSucc); } void LazyValueInfo::eraseBlock(BasicBlock *BB) { - if (PImpl) getCache(PImpl).eraseBlock(BB); + if (PImpl) getCache(PImpl, AT, DL, DT).eraseBlock(BB); } Index: lib/Transforms/Scalar/CorrelatedValuePropagation.cpp =================================================================== --- lib/Transforms/Scalar/CorrelatedValuePropagation.cpp +++ lib/Transforms/Scalar/CorrelatedValuePropagation.cpp @@ -73,7 +73,7 @@ if (S->getType()->isVectorTy()) return false; if (isa(S->getOperand(0))) return false; - Constant *C = LVI->getConstant(S->getOperand(0), S->getParent()); + Constant *C = LVI->getConstant(S->getOperand(0), S->getParent(), S); if (!C) return false; ConstantInt *CI = dyn_cast(C); @@ -100,7 +100,7 @@ Value *Incoming = P->getIncomingValue(i); if (isa(Incoming)) continue; - Value *V = LVI->getConstantOnEdge(Incoming, P->getIncomingBlock(i), BB); + Value *V = LVI->getConstantOnEdge(Incoming, P->getIncomingBlock(i), BB, P); // Look if the incoming value is a select with a constant but LVI tells us // that the incoming value can never be that constant. In that case replace @@ -114,7 +114,7 @@ if (!C) continue; if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C, - P->getIncomingBlock(i), BB) != + P->getIncomingBlock(i), BB, P) != LazyValueInfo::False) continue; @@ -148,7 +148,7 @@ if (isa(Pointer)) return false; - Constant *C = LVI->getConstant(Pointer, I->getParent()); + Constant *C = LVI->getConstant(Pointer, I->getParent(), I); if (!C) return false; ++NumMemAccess; @@ -174,13 +174,15 @@ if (PI == PE) return false; LazyValueInfo::Tristate Result = LVI->getPredicateOnEdge(C->getPredicate(), - C->getOperand(0), Op1, *PI, C->getParent()); + C->getOperand(0), Op1, *PI, + C->getParent(), C); if (Result == LazyValueInfo::Unknown) return false; ++PI; while (PI != PE) { LazyValueInfo::Tristate Res = LVI->getPredicateOnEdge(C->getPredicate(), - C->getOperand(0), Op1, *PI, C->getParent()); + C->getOperand(0), Op1, *PI, + C->getParent(), C); if (Res != Result) return false; ++PI; } @@ -230,7 +232,8 @@ for (pred_iterator PI = PB; PI != PE; ++PI) { // Is the switch condition equal to the case value? LazyValueInfo::Tristate Value = LVI->getPredicateOnEdge(CmpInst::ICMP_EQ, - Cond, Case, *PI, BB); + Cond, Case, *PI, + BB, SI); // Give up on this case if nothing is known. if (Value == LazyValueInfo::Unknown) { State = LazyValueInfo::Unknown; Index: lib/Transforms/Scalar/JumpThreading.cpp =================================================================== --- lib/Transforms/Scalar/JumpThreading.cpp +++ lib/Transforms/Scalar/JumpThreading.cpp @@ -124,9 +124,11 @@ bool ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result, - ConstantPreference Preference); + ConstantPreference Preference, + Instruction *CxtI = nullptr); bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB, - ConstantPreference Preference); + ConstantPreference Preference, + Instruction *CxtI = nullptr); bool ProcessBranchOnPHI(PHINode *PN); bool ProcessBranchOnXOR(BinaryOperator *BO); @@ -340,7 +342,8 @@ /// bool JumpThreading:: ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result, - ConstantPreference Preference) { + ConstantPreference Preference, + Instruction *CxtI) { // This method walks up use-def chains recursively. Because of this, we could // get into an infinite loop going around loops in the use-def chain. To // prevent this, keep track of what (value, block) pairs we've already visited @@ -382,7 +385,7 @@ BasicBlock *P = *PI; // If the value is known by LazyValueInfo to be a constant in a // predecessor, use that information to try to thread this block. - Constant *PredCst = LVI->getConstantOnEdge(V, P, BB); + Constant *PredCst = LVI->getConstantOnEdge(V, P, BB, CxtI); if (Constant *KC = getKnownConstant(PredCst, Preference)) Result.push_back(std::make_pair(KC, P)); } @@ -398,7 +401,8 @@ Result.push_back(std::make_pair(KC, PN->getIncomingBlock(i))); } else { Constant *CI = LVI->getConstantOnEdge(InVal, - PN->getIncomingBlock(i), BB); + PN->getIncomingBlock(i), + BB, CxtI); if (Constant *KC = getKnownConstant(CI, Preference)) Result.push_back(std::make_pair(KC, PN->getIncomingBlock(i))); } @@ -417,9 +421,9 @@ if (I->getOpcode() == Instruction::Or || I->getOpcode() == Instruction::And) { ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals, - WantInteger); + WantInteger, CxtI); ComputeValueKnownInPredecessors(I->getOperand(1), BB, RHSVals, - WantInteger); + WantInteger, CxtI); if (LHSVals.empty() && RHSVals.empty()) return false; @@ -460,7 +464,7 @@ isa(I->getOperand(1)) && cast(I->getOperand(1))->isOne()) { ComputeValueKnownInPredecessors(I->getOperand(0), BB, Result, - WantInteger); + WantInteger, CxtI); if (Result.empty()) return false; @@ -478,7 +482,7 @@ if (ConstantInt *CI = dyn_cast(BO->getOperand(1))) { PredValueInfoTy LHSVals; ComputeValueKnownInPredecessors(BO->getOperand(0), BB, LHSVals, - WantInteger); + WantInteger, CxtI); // Try to use constant folding to simplify the binary operator. for (unsigned i = 0, e = LHSVals.size(); i != e; ++i) { @@ -512,7 +516,8 @@ LazyValueInfo::Tristate ResT = LVI->getPredicateOnEdge(Cmp->getPredicate(), LHS, - cast(RHS), PredBB, BB); + cast(RHS), PredBB, BB, + CxtI ? CxtI : Cmp); if (ResT == LazyValueInfo::Unknown) continue; Res = ConstantInt::get(Type::getInt1Ty(LHS->getContext()), ResT); @@ -525,7 +530,6 @@ return !Result.empty(); } - // If comparing a live-in value against a constant, see if we know the // live-in value on any predecessors. if (isa(Cmp->getOperand(1)) && Cmp->getType()->isIntegerTy()) { @@ -539,7 +543,7 @@ // predecessor, use that information to try to thread this block. LazyValueInfo::Tristate Res = LVI->getPredicateOnEdge(Cmp->getPredicate(), Cmp->getOperand(0), - RHSCst, P, BB); + RHSCst, P, BB, CxtI ? CxtI : Cmp); if (Res == LazyValueInfo::Unknown) continue; @@ -555,7 +559,7 @@ if (Constant *CmpConst = dyn_cast(Cmp->getOperand(1))) { PredValueInfoTy LHSVals; ComputeValueKnownInPredecessors(I->getOperand(0), BB, LHSVals, - WantInteger); + WantInteger, CxtI); for (unsigned i = 0, e = LHSVals.size(); i != e; ++i) { Constant *V = LHSVals[i].first; @@ -578,7 +582,7 @@ PredValueInfoTy Conds; if ((TrueVal || FalseVal) && ComputeValueKnownInPredecessors(SI->getCondition(), BB, Conds, - WantInteger)) { + WantInteger, CxtI)) { for (unsigned i = 0, e = Conds.size(); i != e; ++i) { Constant *Cond = Conds[i].first; @@ -605,7 +609,7 @@ } // If all else fails, see if LVI can figure out a constant value for us. - Constant *CI = LVI->getConstant(V, BB); + Constant *CI = LVI->getConstant(V, BB, CxtI); if (Constant *KC = getKnownConstant(CI, Preference)) { for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) Result.push_back(std::make_pair(KC, *PI)); @@ -745,7 +749,7 @@ // All the rest of our checks depend on the condition being an instruction. if (!CondInst) { // FIXME: Unify this with code below. - if (ProcessThreadableEdges(Condition, BB, Preference)) + if (ProcessThreadableEdges(Condition, BB, Preference, Terminator)) return true; return false; } @@ -767,13 +771,14 @@ // FIXME: We could handle mixed true/false by duplicating code. LazyValueInfo::Tristate Baseline = LVI->getPredicateOnEdge(CondCmp->getPredicate(), CondCmp->getOperand(0), - CondConst, *PI, BB); + CondConst, *PI, BB, CondCmp); if (Baseline != LazyValueInfo::Unknown) { // Check that all remaining incoming values match the first one. while (++PI != PE) { LazyValueInfo::Tristate Ret = LVI->getPredicateOnEdge(CondCmp->getPredicate(), - CondCmp->getOperand(0), CondConst, *PI, BB); + CondCmp->getOperand(0), CondConst, *PI, BB, + CondCmp); if (Ret != Baseline) break; } @@ -788,6 +793,21 @@ } } + } else if (CondBr && CondConst && CondBr->isConditional()) { + // There might be an invairant in the same block with the conditional + // that can determine the predicate. + + LazyValueInfo::Tristate Ret = + LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0), + CondConst, CondCmp); + if (Ret != LazyValueInfo::Unknown) { + unsigned ToRemove = Ret == LazyValueInfo::True ? 1 : 0; + unsigned ToKeep = Ret == LazyValueInfo::True ? 0 : 1; + CondBr->getSuccessor(ToRemove)->removePredecessor(BB, true); + BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr); + CondBr->eraseFromParent(); + return true; + } } if (CondBr && CondConst && TryToUnfoldSelect(CondCmp, BB)) @@ -815,7 +835,7 @@ // a PHI node in the current block. If we can prove that any predecessors // compute a predictable value based on a PHI node, thread those predecessors. // - if (ProcessThreadableEdges(CondInst, BB, Preference)) + if (ProcessThreadableEdges(CondInst, BB, Preference, Terminator)) return true; // If this is an otherwise-unfoldable branch on a phi node in the current @@ -1083,14 +1103,15 @@ } bool JumpThreading::ProcessThreadableEdges(Value *Cond, BasicBlock *BB, - ConstantPreference Preference) { + ConstantPreference Preference, + Instruction *CxtI) { // If threading this would thread across a loop header, don't even try to // thread the edge. if (LoopHeaders.count(BB)) return false; PredValueInfoTy PredValues; - if (!ComputeValueKnownInPredecessors(Cond, BB, PredValues, Preference)) + if (!ComputeValueKnownInPredecessors(Cond, BB, PredValues, Preference, CxtI)) return false; assert(!PredValues.empty() && @@ -1255,10 +1276,10 @@ PredValueInfoTy XorOpValues; bool isLHS = true; if (!ComputeValueKnownInPredecessors(BO->getOperand(0), BB, XorOpValues, - WantInteger)) { + WantInteger, BO)) { assert(XorOpValues.empty()); if (!ComputeValueKnownInPredecessors(BO->getOperand(1), BB, XorOpValues, - WantInteger)) + WantInteger, BO)) return false; isLHS = false; } @@ -1674,10 +1695,10 @@ // cases will be threaded in any case. LazyValueInfo::Tristate LHSFolds = LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(1), - CondRHS, Pred, BB); + CondRHS, Pred, BB, CondCmp); LazyValueInfo::Tristate RHSFolds = LVI->getPredicateOnEdge(CondCmp->getPredicate(), SI->getOperand(2), - CondRHS, Pred, BB); + CondRHS, Pred, BB, CondCmp); if ((LHSFolds != LazyValueInfo::Unknown || RHSFolds != LazyValueInfo::Unknown) && LHSFolds != RHSFolds) { Index: test/Transforms/JumpThreading/assume.ll =================================================================== --- /dev/null +++ test/Transforms/JumpThreading/assume.ll @@ -0,0 +1,68 @@ +; RUN: opt -S -jump-threading -dce < %s | FileCheck %s +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +; Function Attrs: nounwind uwtable +define i32 @test1(i32 %a, i32 %b) #0 { +entry: + %cmp = icmp sgt i32 %a, 5 + tail call void @llvm.assume(i1 %cmp) + %cmp1 = icmp sgt i32 %b, 1234 + br i1 %cmp1, label %if.then, label %if.else + +; CHECK-LABEL: @test1 +; CHECK: icmp sgt i32 %a, 5 +; CHECK: call void @llvm.assume +; CHECK-NOT: icmp sgt i32 %a, 3 +; CHECK: ret i32 + +if.then: ; preds = %entry + %cmp2 = icmp sgt i32 %a, 3 + br i1 %cmp2, label %if.then3, label %return + +if.then3: ; preds = %if.then + tail call void (...)* @bar() #1 + br label %return + +if.else: ; preds = %entry + tail call void (...)* @car() #1 + br label %return + +return: ; preds = %if.else, %if.then, %if.then3 + %retval.0 = phi i32 [ 1, %if.then3 ], [ 0, %if.then ], [ 0, %if.else ] + ret i32 %retval.0 +} + +define i32 @test2(i32 %a) #0 { +entry: + %cmp = icmp sgt i32 %a, 5 + tail call void @llvm.assume(i1 %cmp) + %cmp1 = icmp sgt i32 %a, 3 + br i1 %cmp1, label %if.then, label %return + +; CHECK-LABEL: @test2 +; CHECK: icmp sgt i32 %a, 5 +; CHECK: tail call void @llvm.assume +; CHECK: tail call void (...)* @bar() +; CHECK: ret i32 1 + + +if.then: ; preds = %entry + tail call void (...)* @bar() #1 + br label %return + +return: ; preds = %entry, %if.then + %retval.0 = phi i32 [ 1, %if.then ], [ 0, %entry ] + ret i32 %retval.0 +} + +; Function Attrs: nounwind +declare void @llvm.assume(i1) #1 + +declare void @bar(...) + +declare void @car(...) + +attributes #0 = { nounwind uwtable } +attributes #1 = { nounwind } +