summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/include/llvm/Analysis/LazyValueInfo.h20
-rw-r--r--llvm/lib/Analysis/LazyValueInfo.cpp266
-rw-r--r--llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp17
-rw-r--r--llvm/lib/Transforms/Scalar/JumpThreading.cpp71
-rw-r--r--llvm/test/Transforms/JumpThreading/assume.ll68
5 files changed, 329 insertions, 113 deletions
diff --git a/llvm/include/llvm/Analysis/LazyValueInfo.h b/llvm/include/llvm/Analysis/LazyValueInfo.h
index 2fe7386e730..52cc0d1e07a 100644
--- a/llvm/include/llvm/Analysis/LazyValueInfo.h
+++ b/llvm/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 @@ public:
/// 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.
diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp
index 281ff89bfe4..3062cfa1949 100644
--- a/llvm/lib/Analysis/LazyValueInfo.cpp
+++ b/llvm/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 @@ using namespace PatternMatch;
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 @@ namespace {
/// during a query. It basically emulates the callstack of the naive
/// recursive value lookup process.
std::stack<std::pair<BasicBlock*, Value*> > 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 @@ namespace {
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 @@ namespace {
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 @@ namespace {
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 @@ namespace {
ValueCache.clear();
OverDefinedCache.clear();
}
+
+ LazyValueInfoCache(AssumptionTracker *AT,
+ const DataLayout *DL = nullptr,
+ DominatorTree *DT = nullptr) : AT(AT), DL(DL), DT(DT) {}
};
} // end anonymous namespace
@@ -684,7 +708,7 @@ bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV,
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;
@@ -709,6 +733,36 @@ bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV,
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<Instruction>(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<ICmpInst>(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) {
@@ -719,6 +773,7 @@ bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
}
LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
+ mergeAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI);
if (!LHSVal.isConstantRange()) {
BBLV.markOverdefined();
return true;
@@ -790,6 +845,47 @@ bool LazyValueInfoCache::solveBlockValueConstantRange(LVILatticeVal &BBLV,
return true;
}
+bool getValueFromFromCondition(Value *Val, ICmpInst *ICI,
+ LVILatticeVal &Result, bool isTrueDest) {
+ if (ICI && 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.
+ if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
+ Result = LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
+ else
+ Result = LVILatticeVal::getNot(cast<Constant>(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<ConstantInt>(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,
@@ -816,41 +912,8 @@ static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
// If the condition of the branch is an equality comparison, we may be
// able to infer the value.
ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition());
- if (ICI && 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.
- if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
- Result = LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
- else
- Result = LVILatticeVal::getNot(cast<Constant>(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<ConstantInt>(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;
}
}
@@ -884,7 +947,8 @@ static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
/// \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<Constant>(Val)) {
Result = LVILatticeVal::get(VC);
@@ -906,6 +970,7 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
// 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;
@@ -922,30 +987,45 @@ bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
// 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?");
}
@@ -1019,39 +1099,51 @@ void LazyValueInfoCache::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
//===----------------------------------------------------------------------===//
/// 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<LazyValueInfoCache*>(PImpl);
}
bool LazyValueInfo::runOnFunction(Function &F) {
- if (PImpl)
- getCache(PImpl).clear();
+ AT = &getAnalysis<AssumptionTracker>();
+
+ DominatorTreeWrapperPass *DTWP =
+ getAnalysisIfAvailable<DominatorTreeWrapperPass>();
+ DT = DTWP ? &DTWP->getDomTree() : nullptr;
DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
DL = DLP ? &DLP->getDataLayout() : nullptr;
TLI = &getAnalysis<TargetLibraryInfo>();
+ if (PImpl)
+ getCache(PImpl, AT, DL, DT).clear();
+
// Fully lazy.
return false;
}
void LazyValueInfo::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
+ AU.addRequired<AssumptionTracker>();
AU.addRequired<TargetLibraryInfo>();
}
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();
@@ -1066,8 +1158,10 @@ Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB) {
/// 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();
@@ -1079,51 +1173,47 @@ Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
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<ConstantInt>(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<ConstantInt>(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()) {
@@ -1135,26 +1225,48 @@ LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
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);
}
diff --git a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
index 075c0351534..5a3b5cf34cc 100644
--- a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
+++ b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
@@ -73,7 +73,7 @@ bool CorrelatedValuePropagation::processSelect(SelectInst *S) {
if (S->getType()->isVectorTy()) return false;
if (isa<Constant>(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<ConstantInt>(C);
@@ -100,7 +100,7 @@ bool CorrelatedValuePropagation::processPHI(PHINode *P) {
Value *Incoming = P->getIncomingValue(i);
if (isa<Constant>(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 @@ bool CorrelatedValuePropagation::processPHI(PHINode *P) {
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 @@ bool CorrelatedValuePropagation::processMemAccess(Instruction *I) {
if (isa<Constant>(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 @@ bool CorrelatedValuePropagation::processCmp(CmpInst *C) {
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 @@ bool CorrelatedValuePropagation::processSwitch(SwitchInst *SI) {
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;
diff --git a/llvm/lib/Transforms/Scalar/JumpThreading.cpp b/llvm/lib/Transforms/Scalar/JumpThreading.cpp
index 2b4e3ff00dd..bd8c0e8e699 100644
--- a/llvm/lib/Transforms/Scalar/JumpThreading.cpp
+++ b/llvm/lib/Transforms/Scalar/JumpThreading.cpp
@@ -124,9 +124,11 @@ namespace {
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 @@ static Constant *getKnownConstant(Value *Val, ConstantPreference Preference) {
///
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 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result,
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 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result,
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 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result,
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 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result,
isa<ConstantInt>(I->getOperand(1)) &&
cast<ConstantInt>(I->getOperand(1))->isOne()) {
ComputeValueKnownInPredecessors(I->getOperand(0), BB, Result,
- WantInteger);
+ WantInteger, CxtI);
if (Result.empty())
return false;
@@ -478,7 +482,7 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result,
if (ConstantInt *CI = dyn_cast<ConstantInt>(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 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result,
LazyValueInfo::Tristate
ResT = LVI->getPredicateOnEdge(Cmp->getPredicate(), LHS,
- cast<Constant>(RHS), PredBB, BB);
+ cast<Constant>(RHS), PredBB, BB,
+ CxtI ? CxtI : Cmp);
if (ResT == LazyValueInfo::Unknown)
continue;
Res = ConstantInt::get(Type::getInt1Ty(LHS->getContext()), ResT);
@@ -525,7 +530,6 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result,
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<Constant>(Cmp->getOperand(1)) && Cmp->getType()->isIntegerTy()) {
@@ -539,7 +543,7 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result,
// 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 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result,
if (Constant *CmpConst = dyn_cast<Constant>(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 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result,
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 @@ ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result,
}
// 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 @@ bool JumpThreading::ProcessBlock(BasicBlock *BB) {
// 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 @@ bool JumpThreading::ProcessBlock(BasicBlock *BB) {
// 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 @@ bool JumpThreading::ProcessBlock(BasicBlock *BB) {
}
}
+ } 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 @@ bool JumpThreading::ProcessBlock(BasicBlock *BB) {
// 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 @@ FindMostPopularDest(BasicBlock *BB,
}
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 @@ bool JumpThreading::ProcessBranchOnXOR(BinaryOperator *BO) {
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 @@ bool JumpThreading::TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB) {
// 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) {
diff --git a/llvm/test/Transforms/JumpThreading/assume.ll b/llvm/test/Transforms/JumpThreading/assume.ll
new file mode 100644
index 00000000000..89dd0a954c0
--- /dev/null
+++ b/llvm/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 }
+
OpenPOWER on IntegriCloud