summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/include/llvm/Analysis/AssumptionCache.h41
-rw-r--r--llvm/lib/Analysis/AssumptionCache.cpp109
-rw-r--r--llvm/lib/Analysis/LazyValueInfo.cpp2
-rw-r--r--llvm/lib/Analysis/ValueTracking.cpp5
-rw-r--r--llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp3
5 files changed, 158 insertions, 2 deletions
diff --git a/llvm/include/llvm/Analysis/AssumptionCache.h b/llvm/include/llvm/Analysis/AssumptionCache.h
index 406a1fe9f56..b50545a0484 100644
--- a/llvm/include/llvm/Analysis/AssumptionCache.h
+++ b/llvm/include/llvm/Analysis/AssumptionCache.h
@@ -46,6 +46,30 @@ class AssumptionCache {
/// intrinsic.
SmallVector<WeakVH, 4> AssumeHandles;
+ class AffectedValueCallbackVH final : public CallbackVH {
+ AssumptionCache *AC;
+ void deleted() override;
+ void allUsesReplacedWith(Value *) override;
+
+ public:
+ using DMI = DenseMapInfo<Value *>;
+
+ AffectedValueCallbackVH(Value *V, AssumptionCache *AC = nullptr)
+ : CallbackVH(V), AC(AC) {}
+ };
+
+ friend AffectedValueCallbackVH;
+
+ /// \brief A map of values about which an assumption might be providing
+ /// information to the relevant set of assumptions.
+ using AffectedValuesMap =
+ DenseMap<AffectedValueCallbackVH, SmallVector<WeakVH, 1>,
+ AffectedValueCallbackVH::DMI>;
+ AffectedValuesMap AffectedValues;
+
+ /// Get the vector of assumptions which affect a value from the cache.
+ SmallVector<WeakVH, 1> &getAffectedValues(Value *V);
+
/// \brief Flag tracking whether we have scanned the function yet.
///
/// We want to be as lazy about this as possible, and so we scan the function
@@ -66,11 +90,16 @@ public:
/// not already be in the cache.
void registerAssumption(CallInst *CI);
+ /// \brief Update the cache of values being affected by this assumption (i.e.
+ /// the values about which this assumption provides information).
+ void updateAffectedValues(CallInst *CI);
+
/// \brief Clear the cache of @llvm.assume intrinsics for a function.
///
/// It will be re-scanned the next time it is requested.
void clear() {
AssumeHandles.clear();
+ AffectedValues.clear();
Scanned = false;
}
@@ -87,6 +116,18 @@ public:
scanFunction();
return AssumeHandles;
}
+
+ /// \brief Access the list of assumptions which affect this value.
+ MutableArrayRef<WeakVH> assumptionsFor(const Value *V) {
+ if (!Scanned)
+ scanFunction();
+
+ auto AVI = AffectedValues.find_as(const_cast<Value *>(V));
+ if (AVI == AffectedValues.end())
+ return MutableArrayRef<WeakVH>();
+
+ return AVI->second;
+ }
};
/// \brief A function analysis which provides an \c AssumptionCache.
diff --git a/llvm/lib/Analysis/AssumptionCache.cpp b/llvm/lib/Analysis/AssumptionCache.cpp
index 3c518034ba6..aa55d79b761 100644
--- a/llvm/lib/Analysis/AssumptionCache.cpp
+++ b/llvm/lib/Analysis/AssumptionCache.cpp
@@ -24,6 +24,109 @@
using namespace llvm;
using namespace llvm::PatternMatch;
+SmallVector<WeakVH, 1> &AssumptionCache::getAffectedValues(Value *V) {
+ // Try using find_as first to avoid creating extra value handles just for the
+ // purpose of doing the lookup.
+ auto AVI = AffectedValues.find_as(V);
+ if (AVI != AffectedValues.end())
+ return AVI->second;
+
+ auto AVIP = AffectedValues.insert({
+ AffectedValueCallbackVH(V, this), SmallVector<WeakVH, 1>()});
+ return AVIP.first->second;
+}
+
+void AssumptionCache::updateAffectedValues(CallInst *CI) {
+ // Note: This code must be kept in-sync with the code in
+ // computeKnownBitsFromAssume in ValueTracking.
+
+ SmallVector<Value *, 16> Affected;
+ auto AddAffected = [&Affected](Value *V) {
+ if (isa<Argument>(V)) {
+ Affected.push_back(V);
+ } else if (auto *I = dyn_cast<Instruction>(V)) {
+ Affected.push_back(I);
+
+ if (I->getOpcode() == Instruction::BitCast ||
+ I->getOpcode() == Instruction::PtrToInt) {
+ auto *Op = I->getOperand(0);
+ if (isa<Instruction>(Op) || isa<Argument>(Op))
+ Affected.push_back(Op);
+ }
+ }
+ };
+
+ Value *Cond = CI->getArgOperand(0), *A, *B;
+ AddAffected(Cond);
+
+ CmpInst::Predicate Pred;
+ if (match(Cond, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
+ AddAffected(A);
+ AddAffected(B);
+
+ if (Pred == ICmpInst::ICMP_EQ) {
+ // For equality comparisons, we handle the case of bit inversion.
+ auto AddAffectedFromEq = [&AddAffected](Value *V) {
+ Value *A;
+ if (match(V, m_Not(m_Value(A)))) {
+ AddAffected(A);
+ V = A;
+ }
+
+ Value *B;
+ ConstantInt *C;
+ // (A & B) or (A | B) or (A ^ B).
+ if (match(V,
+ m_CombineOr(m_And(m_Value(A), m_Value(B)),
+ m_CombineOr(m_Or(m_Value(A), m_Value(B)),
+ m_Xor(m_Value(A), m_Value(B)))))) {
+ AddAffected(A);
+ AddAffected(B);
+ // (A << C) or (A >>_s C) or (A >>_u C) where C is some constant.
+ } else if (match(V,
+ m_CombineOr(m_Shl(m_Value(A), m_ConstantInt(C)),
+ m_CombineOr(m_LShr(m_Value(A), m_ConstantInt(C)),
+ m_AShr(m_Value(A),
+ m_ConstantInt(C)))))) {
+ AddAffected(A);
+ }
+ };
+
+ AddAffectedFromEq(A);
+ AddAffectedFromEq(B);
+ }
+ }
+
+ for (auto &AV : Affected) {
+ auto &AVV = getAffectedValues(AV);
+ if (std::find(AVV.begin(), AVV.end(), CI) == AVV.end())
+ AVV.push_back(CI);
+ }
+}
+
+void AssumptionCache::AffectedValueCallbackVH::deleted() {
+ auto AVI = AC->AffectedValues.find(getValPtr());
+ if (AVI != AC->AffectedValues.end())
+ AC->AffectedValues.erase(AVI);
+ // 'this' now dangles!
+}
+
+void AssumptionCache::AffectedValueCallbackVH::allUsesReplacedWith(Value *NV) {
+ if (!isa<Instruction>(NV) && !isa<Argument>(NV))
+ return;
+
+ // Any assumptions that affected this value now affect the new value.
+
+ auto &NAVV = AC->getAffectedValues(NV);
+ auto AVI = AC->AffectedValues.find(getValPtr());
+ if (AVI == AC->AffectedValues.end())
+ return;
+
+ for (auto &A : AVI->second)
+ if (std::find(NAVV.begin(), NAVV.end(), A) == NAVV.end())
+ NAVV.push_back(A);
+}
+
void AssumptionCache::scanFunction() {
assert(!Scanned && "Tried to scan the function twice!");
assert(AssumeHandles.empty() && "Already have assumes when scanning!");
@@ -37,6 +140,10 @@ void AssumptionCache::scanFunction() {
// Mark the scan as complete.
Scanned = true;
+
+ // Update affected values.
+ for (auto &A : AssumeHandles)
+ updateAffectedValues(cast<CallInst>(A));
}
void AssumptionCache::registerAssumption(CallInst *CI) {
@@ -72,6 +179,8 @@ void AssumptionCache::registerAssumption(CallInst *CI) {
"Cache contains multiple copies of a call!");
}
#endif
+
+ updateAffectedValues(CI);
}
AnalysisKey AssumptionAnalysis::Key;
diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp
index 4f635523687..d442310476c 100644
--- a/llvm/lib/Analysis/LazyValueInfo.cpp
+++ b/llvm/lib/Analysis/LazyValueInfo.cpp
@@ -925,7 +925,7 @@ void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
if (!BBI)
return;
- for (auto &AssumeVH : AC->assumptions()) {
+ for (auto &AssumeVH : AC->assumptionsFor(Val)) {
if (!AssumeVH)
continue;
auto *I = cast<CallInst>(AssumeVH);
diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
index b98c9629960..b79370baad1 100644
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -526,7 +526,10 @@ static void computeKnownBitsFromAssume(const Value *V, APInt &KnownZero,
unsigned BitWidth = KnownZero.getBitWidth();
- for (auto &AssumeVH : Q.AC->assumptions()) {
+ // Note that the patterns below need to be kept in sync with the code
+ // in AssumptionCache::updateAffectedValues.
+
+ for (auto &AssumeVH : Q.AC->assumptionsFor(V)) {
if (!AssumeVH)
continue;
CallInst *I = cast<CallInst>(AssumeVH);
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
index d51d3687ea3..2ef82ba3ed8 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
@@ -2756,6 +2756,9 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) {
if (KnownOne.isAllOnesValue())
return eraseInstFromFunction(*II);
+ // Update the cache of affected values for this assumption (we might be
+ // here because we just simplified the condition).
+ AC.updateAffectedValues(II);
break;
}
case Intrinsic::experimental_gc_relocate: {
OpenPOWER on IntegriCloud