aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Analysis/ScalarEvolution.cpp')
-rw-r--r--llvm/lib/Analysis/ScalarEvolution.cpp363
1 files changed, 201 insertions, 162 deletions
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index f7c22cfb0310..7dc7f9904c70 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -2915,8 +2915,8 @@ ScalarEvolution::getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops,
const Loop *L, SCEV::NoWrapFlags Flags) {
FoldingSetNodeID ID;
ID.AddInteger(scAddRecExpr);
- for (unsigned i = 0, e = Ops.size(); i != e; ++i)
- ID.AddPointer(Ops[i]);
+ for (const SCEV *Op : Ops)
+ ID.AddPointer(Op);
ID.AddPointer(L);
void *IP = nullptr;
SCEVAddRecExpr *S =
@@ -2939,8 +2939,8 @@ ScalarEvolution::getOrCreateMulExpr(ArrayRef<const SCEV *> Ops,
SCEV::NoWrapFlags Flags) {
FoldingSetNodeID ID;
ID.AddInteger(scMulExpr);
- for (unsigned i = 0, e = Ops.size(); i != e; ++i)
- ID.AddPointer(Ops[i]);
+ for (const SCEV *Op : Ops)
+ ID.AddPointer(Op);
void *IP = nullptr;
SCEVMulExpr *S =
static_cast<SCEVMulExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
@@ -3708,8 +3708,8 @@ SCEV *ScalarEvolution::findExistingSCEVInCache(SCEVTypes SCEVType,
ArrayRef<const SCEV *> Ops) {
FoldingSetNodeID ID;
ID.AddInteger(SCEVType);
- for (unsigned i = 0, e = Ops.size(); i != e; ++i)
- ID.AddPointer(Ops[i]);
+ for (const SCEV *Op : Ops)
+ ID.AddPointer(Op);
void *IP = nullptr;
return UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
}
@@ -4094,6 +4094,17 @@ void ScalarEvolution::eraseValueFromMap(Value *V) {
}
}
+void ScalarEvolution::insertValueToMap(Value *V, const SCEV *S) {
+ // A recursive query may have already computed the SCEV. It should be
+ // equivalent, but may not necessarily be exactly the same, e.g. due to lazily
+ // inferred nowrap flags.
+ auto It = ValueExprMap.find_as(V);
+ if (It == ValueExprMap.end()) {
+ ValueExprMap.insert({SCEVCallbackVH(V, this), S});
+ ExprValueMap[S].insert({V, nullptr});
+ }
+}
+
/// Return an existing SCEV if it exists, otherwise analyze the expression and
/// create a new one.
const SCEV *ScalarEvolution::getSCEV(Value *V) {
@@ -4134,10 +4145,9 @@ const SCEV *ScalarEvolution::getExistingSCEV(Value *V) {
ValueExprMapType::iterator I = ValueExprMap.find_as(V);
if (I != ValueExprMap.end()) {
const SCEV *S = I->second;
- if (checkValidity(S))
- return S;
- eraseValueFromMap(V);
- forgetMemoizedResults(S);
+ assert(checkValidity(S) &&
+ "existing SCEV has not been properly invalidated");
+ return S;
}
return nullptr;
}
@@ -4430,44 +4440,6 @@ static void PushDefUseChildren(Instruction *I,
}
}
-void ScalarEvolution::forgetSymbolicName(Instruction *PN, const SCEV *SymName) {
- SmallVector<Instruction *, 16> Worklist;
- SmallPtrSet<Instruction *, 8> Visited;
- SmallVector<const SCEV *, 8> ToForget;
- Visited.insert(PN);
- Worklist.push_back(PN);
- while (!Worklist.empty()) {
- Instruction *I = Worklist.pop_back_val();
-
- auto It = ValueExprMap.find_as(static_cast<Value *>(I));
- if (It != ValueExprMap.end()) {
- const SCEV *Old = It->second;
-
- // Short-circuit the def-use traversal if the symbolic name
- // ceases to appear in expressions.
- if (Old != SymName && !hasOperand(Old, SymName))
- continue;
-
- // SCEVUnknown for a PHI either means that it has an unrecognized
- // structure, it's a PHI that's in the progress of being computed
- // by createNodeForPHI, or it's a single-value PHI. In the first case,
- // additional loop trip count information isn't going to change anything.
- // In the second case, createNodeForPHI will perform the necessary
- // updates on its own when it gets to that point. In the third, we do
- // want to forget the SCEVUnknown.
- if (!isa<PHINode>(I) ||
- !isa<SCEVUnknown>(Old) ||
- (I != PN && Old == SymName)) {
- eraseValueFromMap(It->first);
- ToForget.push_back(Old);
- }
- }
-
- PushDefUseChildren(I, Worklist, Visited);
- }
- forgetMemoizedResults(ToForget);
-}
-
namespace {
/// Takes SCEV S and Loop L. For each AddRec sub-expression, use its start
@@ -5335,15 +5307,17 @@ const SCEV *ScalarEvolution::createSimpleAffineAddRec(PHINode *PN,
const SCEV *StartVal = getSCEV(StartValueV);
const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags);
-
- ValueExprMap[SCEVCallbackVH(PN, this)] = PHISCEV;
+ insertValueToMap(PN, PHISCEV);
// We can add Flags to the post-inc expression only if we
// know that it is *undefined behavior* for BEValueV to
// overflow.
- if (auto *BEInst = dyn_cast<Instruction>(BEValueV))
- if (isLoopInvariant(Accum, L) && isAddRecNeverPoison(BEInst, L))
+ if (auto *BEInst = dyn_cast<Instruction>(BEValueV)) {
+ assert(isLoopInvariant(Accum, L) &&
+ "Accum is defined outside L, but is not invariant?");
+ if (isAddRecNeverPoison(BEInst, L))
(void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, Flags);
+ }
return PHISCEV;
}
@@ -5386,7 +5360,7 @@ const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) {
// Handle PHI node value symbolically.
const SCEV *SymbolicName = getUnknown(PN);
- ValueExprMap.insert({SCEVCallbackVH(PN, this), SymbolicName});
+ insertValueToMap(PN, SymbolicName);
// Using this symbolic name for the PHI, analyze the value coming around
// the back-edge.
@@ -5457,8 +5431,8 @@ const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) {
// Okay, for the entire analysis of this edge we assumed the PHI
// to be symbolic. We now need to go back and purge all of the
// entries for the scalars that use the symbolic expression.
- forgetSymbolicName(PN, SymbolicName);
- ValueExprMap[SCEVCallbackVH(PN, this)] = PHISCEV;
+ forgetMemoizedResults(SymbolicName);
+ insertValueToMap(PN, PHISCEV);
// We can add Flags to the post-inc expression only if we
// know that it is *undefined behavior* for BEValueV to
@@ -5489,8 +5463,8 @@ const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) {
// Okay, for the entire analysis of this edge we assumed the PHI
// to be symbolic. We now need to go back and purge all of the
// entries for the scalars that use the symbolic expression.
- forgetSymbolicName(PN, SymbolicName);
- ValueExprMap[SCEVCallbackVH(PN, this)] = Shifted;
+ forgetMemoizedResults(SymbolicName);
+ insertValueToMap(PN, Shifted);
return Shifted;
}
}
@@ -7598,62 +7572,19 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) {
// Now that we know more about the trip count for this loop, forget any
// existing SCEV values for PHI nodes in this loop since they are only
// conservative estimates made without the benefit of trip count
- // information. This is similar to the code in forgetLoop, except that
- // it handles SCEVUnknown PHI nodes specially.
+ // information. This invalidation is not necessary for correctness, and is
+ // only done to produce more precise results.
if (Result.hasAnyInfo()) {
- SmallVector<Instruction *, 16> Worklist;
- SmallPtrSet<Instruction *, 8> Discovered;
+ // Invalidate any expression using an addrec in this loop.
SmallVector<const SCEV *, 8> ToForget;
- PushLoopPHIs(L, Worklist, Discovered);
- while (!Worklist.empty()) {
- Instruction *I = Worklist.pop_back_val();
-
- ValueExprMapType::iterator It =
- ValueExprMap.find_as(static_cast<Value *>(I));
- if (It != ValueExprMap.end()) {
- const SCEV *Old = It->second;
-
- // SCEVUnknown for a PHI either means that it has an unrecognized
- // structure, or it's a PHI that's in the progress of being computed
- // by createNodeForPHI. In the former case, additional loop trip
- // count information isn't going to change anything. In the later
- // case, createNodeForPHI will perform the necessary updates on its
- // own when it gets to that point.
- if (!isa<PHINode>(I) || !isa<SCEVUnknown>(Old)) {
- eraseValueFromMap(It->first);
- ToForget.push_back(Old);
- }
- if (PHINode *PN = dyn_cast<PHINode>(I))
- ConstantEvolutionLoopExitValue.erase(PN);
- }
-
- // Since we don't need to invalidate anything for correctness and we're
- // only invalidating to make SCEV's results more precise, we get to stop
- // early to avoid invalidating too much. This is especially important in
- // cases like:
- //
- // %v = f(pn0, pn1) // pn0 and pn1 used through some other phi node
- // loop0:
- // %pn0 = phi
- // ...
- // loop1:
- // %pn1 = phi
- // ...
- //
- // where both loop0 and loop1's backedge taken count uses the SCEV
- // expression for %v. If we don't have the early stop below then in cases
- // like the above, getBackedgeTakenInfo(loop1) will clear out the trip
- // count for loop0 and getBackedgeTakenInfo(loop0) will clear out the trip
- // count for loop1, effectively nullifying SCEV's trip count cache.
- for (auto *U : I->users())
- if (auto *I = dyn_cast<Instruction>(U)) {
- auto *LoopForUser = LI.getLoopFor(I->getParent());
- if (LoopForUser && L->contains(LoopForUser) &&
- Discovered.insert(I).second)
- Worklist.push_back(I);
- }
- }
+ auto LoopUsersIt = LoopUsers.find(L);
+ if (LoopUsersIt != LoopUsers.end())
+ append_range(ToForget, LoopUsersIt->second);
forgetMemoizedResults(ToForget);
+
+ // Invalidate constant-evolved loop header phis.
+ for (PHINode &PN : L->getHeader()->phis())
+ ConstantEvolutionLoopExitValue.erase(&PN);
}
// Re-lookup the insert position, since the call to
@@ -7672,10 +7603,12 @@ void ScalarEvolution::forgetAllLoops() {
// result.
BackedgeTakenCounts.clear();
PredicatedBackedgeTakenCounts.clear();
+ BECountUsers.clear();
LoopPropertiesCache.clear();
ConstantEvolutionLoopExitValue.clear();
ValueExprMap.clear();
ValuesAtScopes.clear();
+ ValuesAtScopesUsers.clear();
LoopDispositions.clear();
BlockDispositions.clear();
UnsignedRanges.clear();
@@ -7697,8 +7630,8 @@ void ScalarEvolution::forgetLoop(const Loop *L) {
auto *CurrL = LoopWorklist.pop_back_val();
// Drop any stored trip count value.
- BackedgeTakenCounts.erase(CurrL);
- PredicatedBackedgeTakenCounts.erase(CurrL);
+ forgetBackedgeTakenCounts(CurrL, /* Predicated */ false);
+ forgetBackedgeTakenCounts(CurrL, /* Predicated */ true);
// Drop information about predicated SCEV rewrites for this loop.
for (auto I = PredicatedSCEVRewrites.begin();
@@ -7872,10 +7805,6 @@ bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
return MaxOrZero && !any_of(ExitNotTaken, PredicateNotAlwaysTrue);
}
-bool ScalarEvolution::BackedgeTakenInfo::hasOperand(const SCEV *S) const {
- return Operands.contains(S);
-}
-
ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E)
: ExitLimit(E, E, false, None) {
}
@@ -7916,19 +7845,6 @@ ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E, const SCEV *M,
: ExitLimit(E, M, MaxOrZero, None) {
}
-class SCEVRecordOperands {
- SmallPtrSetImpl<const SCEV *> &Operands;
-
-public:
- SCEVRecordOperands(SmallPtrSetImpl<const SCEV *> &Operands)
- : Operands(Operands) {}
- bool follow(const SCEV *S) {
- Operands.insert(S);
- return true;
- }
- bool isDone() { return false; }
-};
-
/// Allocate memory for BackedgeTakenInfo and copy the not-taken count of each
/// computable exit into a persistent ExitNotTakenInfo array.
ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
@@ -7957,14 +7873,6 @@ ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
assert((isa<SCEVCouldNotCompute>(ConstantMax) ||
isa<SCEVConstant>(ConstantMax)) &&
"No point in having a non-constant max backedge taken count!");
-
- SCEVRecordOperands RecordOperands(Operands);
- SCEVTraversal<SCEVRecordOperands> ST(RecordOperands);
- if (!isa<SCEVCouldNotCompute>(ConstantMax))
- ST.visitAll(ConstantMax);
- for (auto &ENT : ExitNotTaken)
- if (!isa<SCEVCouldNotCompute>(ENT.ExactNotTaken))
- ST.visitAll(ENT.ExactNotTaken);
}
/// Compute the number of times the backedge of the specified loop will execute.
@@ -8046,6 +7954,13 @@ ScalarEvolution::computeBackedgeTakenCount(const Loop *L,
// The loop backedge will be taken the maximum or zero times if there's
// a single exit that must be taken the maximum or zero times.
bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
+
+ // Remember which SCEVs are used in exit limits for invalidation purposes.
+ // We only care about non-constant SCEVs here, so we can ignore EL.MaxNotTaken
+ // and MaxBECount, which must be SCEVConstant.
+ for (const auto &Pair : ExitCounts)
+ if (!isa<SCEVConstant>(Pair.second.ExactNotTaken))
+ BECountUsers[Pair.second.ExactNotTaken].insert({L, AllowPredicates});
return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
MaxBECount, MaxOrZero);
}
@@ -8916,6 +8831,9 @@ const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) {
LS.second = C;
break;
}
+
+ if (!isa<SCEVConstant>(C))
+ ValuesAtScopesUsers[C].push_back({L, V});
return C;
}
@@ -12387,7 +12305,7 @@ const SCEV *SCEVAddRecExpr::getNumIterationsInRange(const ConstantRange &Range,
if (Range.contains(Val->getValue()))
return SE.getCouldNotCompute(); // Something strange happened
- // Ensure that the previous value is in the range. This is a sanity check.
+ // Ensure that the previous value is in the range.
assert(Range.contains(
EvaluateConstantChrecAtConstant(this,
ConstantInt::get(SE.getContext(), ExitVal - 1), SE)->getValue()) &&
@@ -12531,9 +12449,11 @@ ScalarEvolution::ScalarEvolution(ScalarEvolution &&Arg)
BackedgeTakenCounts(std::move(Arg.BackedgeTakenCounts)),
PredicatedBackedgeTakenCounts(
std::move(Arg.PredicatedBackedgeTakenCounts)),
+ BECountUsers(std::move(Arg.BECountUsers)),
ConstantEvolutionLoopExitValue(
std::move(Arg.ConstantEvolutionLoopExitValue)),
ValuesAtScopes(std::move(Arg.ValuesAtScopes)),
+ ValuesAtScopesUsers(std::move(Arg.ValuesAtScopesUsers)),
LoopDispositions(std::move(Arg.LoopDispositions)),
LoopPropertiesCache(std::move(Arg.LoopPropertiesCache)),
BlockDispositions(std::move(Arg.BlockDispositions)),
@@ -12946,6 +12866,23 @@ bool ScalarEvolution::hasOperand(const SCEV *S, const SCEV *Op) const {
return SCEVExprContains(S, [&](const SCEV *Expr) { return Expr == Op; });
}
+void ScalarEvolution::forgetBackedgeTakenCounts(const Loop *L,
+ bool Predicated) {
+ auto &BECounts =
+ Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
+ auto It = BECounts.find(L);
+ if (It != BECounts.end()) {
+ for (const ExitNotTakenInfo &ENT : It->second.ExitNotTaken) {
+ if (!isa<SCEVConstant>(ENT.ExactNotTaken)) {
+ auto UserIt = BECountUsers.find(ENT.ExactNotTaken);
+ assert(UserIt != BECountUsers.end());
+ UserIt->second.erase({L, Predicated});
+ }
+ }
+ BECounts.erase(It);
+ }
+}
+
void ScalarEvolution::forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs) {
SmallPtrSet<const SCEV *, 8> ToForget(SCEVs.begin(), SCEVs.end());
SmallVector<const SCEV *, 8> Worklist(ToForget.begin(), ToForget.end());
@@ -12970,32 +12907,52 @@ void ScalarEvolution::forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs) {
else
++I;
}
-
- auto RemoveSCEVFromBackedgeMap = [&ToForget](
- DenseMap<const Loop *, BackedgeTakenInfo> &Map) {
- for (auto I = Map.begin(), E = Map.end(); I != E;) {
- BackedgeTakenInfo &BEInfo = I->second;
- if (any_of(ToForget,
- [&BEInfo](const SCEV *S) { return BEInfo.hasOperand(S); }))
- Map.erase(I++);
- else
- ++I;
- }
- };
-
- RemoveSCEVFromBackedgeMap(BackedgeTakenCounts);
- RemoveSCEVFromBackedgeMap(PredicatedBackedgeTakenCounts);
}
void ScalarEvolution::forgetMemoizedResultsImpl(const SCEV *S) {
- ValuesAtScopes.erase(S);
LoopDispositions.erase(S);
BlockDispositions.erase(S);
UnsignedRanges.erase(S);
SignedRanges.erase(S);
- ExprValueMap.erase(S);
HasRecMap.erase(S);
MinTrailingZerosCache.erase(S);
+
+ auto ExprIt = ExprValueMap.find(S);
+ if (ExprIt != ExprValueMap.end()) {
+ for (auto &ValueAndOffset : ExprIt->second) {
+ if (ValueAndOffset.second == nullptr) {
+ auto ValueIt = ValueExprMap.find_as(ValueAndOffset.first);
+ if (ValueIt != ValueExprMap.end())
+ ValueExprMap.erase(ValueIt);
+ }
+ }
+ ExprValueMap.erase(ExprIt);
+ }
+
+ auto ScopeIt = ValuesAtScopes.find(S);
+ if (ScopeIt != ValuesAtScopes.end()) {
+ for (const auto &Pair : ScopeIt->second)
+ if (!isa_and_nonnull<SCEVConstant>(Pair.second))
+ erase_value(ValuesAtScopesUsers[Pair.second],
+ std::make_pair(Pair.first, S));
+ ValuesAtScopes.erase(ScopeIt);
+ }
+
+ auto ScopeUserIt = ValuesAtScopesUsers.find(S);
+ if (ScopeUserIt != ValuesAtScopesUsers.end()) {
+ for (const auto &Pair : ScopeUserIt->second)
+ erase_value(ValuesAtScopes[Pair.second], std::make_pair(Pair.first, S));
+ ValuesAtScopesUsers.erase(ScopeUserIt);
+ }
+
+ auto BEUsersIt = BECountUsers.find(S);
+ if (BEUsersIt != BECountUsers.end()) {
+ // Work on a copy, as forgetBackedgeTakenCounts() will modify the original.
+ auto Copy = BEUsersIt->second;
+ for (const auto &Pair : Copy)
+ forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
+ BECountUsers.erase(BEUsersIt);
+ }
}
void
@@ -13100,16 +13057,43 @@ void ScalarEvolution::verify() const {
ValidLoops.insert(L);
Worklist.append(L->begin(), L->end());
}
- // Check for SCEV expressions referencing invalid/deleted loops.
for (auto &KV : ValueExprMap) {
- auto *AR = dyn_cast<SCEVAddRecExpr>(KV.second);
- if (!AR)
- continue;
- assert(ValidLoops.contains(AR->getLoop()) &&
- "AddRec references invalid loop");
+ // Check for SCEV expressions referencing invalid/deleted loops.
+ if (auto *AR = dyn_cast<SCEVAddRecExpr>(KV.second)) {
+ assert(ValidLoops.contains(AR->getLoop()) &&
+ "AddRec references invalid loop");
+ }
+
+ // Check that the value is also part of the reverse map.
+ auto It = ExprValueMap.find(KV.second);
+ if (It == ExprValueMap.end() || !It->second.contains({KV.first, nullptr})) {
+ dbgs() << "Value " << *KV.first
+ << " is in ValueExprMap but not in ExprValueMap\n";
+ std::abort();
+ }
+ }
+
+ for (const auto &KV : ExprValueMap) {
+ for (const auto &ValueAndOffset : KV.second) {
+ if (ValueAndOffset.second != nullptr)
+ continue;
+
+ auto It = ValueExprMap.find_as(ValueAndOffset.first);
+ if (It == ValueExprMap.end()) {
+ dbgs() << "Value " << *ValueAndOffset.first
+ << " is in ExprValueMap but not in ValueExprMap\n";
+ std::abort();
+ }
+ if (It->second != KV.first) {
+ dbgs() << "Value " << *ValueAndOffset.first
+ << " mapped to " << *It->second
+ << " rather than " << *KV.first << "\n";
+ std::abort();
+ }
+ }
}
- // Verify intergity of SCEV users.
+ // Verify integrity of SCEV users.
for (const auto &S : UniqueSCEVs) {
SmallVector<const SCEV *, 4> Ops;
collectUniqueOps(&S, Ops);
@@ -13125,6 +13109,61 @@ void ScalarEvolution::verify() const {
std::abort();
}
}
+
+ // Verify integrity of ValuesAtScopes users.
+ for (const auto &ValueAndVec : ValuesAtScopes) {
+ const SCEV *Value = ValueAndVec.first;
+ for (const auto &LoopAndValueAtScope : ValueAndVec.second) {
+ const Loop *L = LoopAndValueAtScope.first;
+ const SCEV *ValueAtScope = LoopAndValueAtScope.second;
+ if (!isa<SCEVConstant>(ValueAtScope)) {
+ auto It = ValuesAtScopesUsers.find(ValueAtScope);
+ if (It != ValuesAtScopesUsers.end() &&
+ is_contained(It->second, std::make_pair(L, Value)))
+ continue;
+ dbgs() << "Value: " << *Value << ", Loop: " << *L << ", ValueAtScope: "
+ << ValueAtScope << " missing in ValuesAtScopesUsers\n";
+ std::abort();
+ }
+ }
+ }
+
+ for (const auto &ValueAtScopeAndVec : ValuesAtScopesUsers) {
+ const SCEV *ValueAtScope = ValueAtScopeAndVec.first;
+ for (const auto &LoopAndValue : ValueAtScopeAndVec.second) {
+ const Loop *L = LoopAndValue.first;
+ const SCEV *Value = LoopAndValue.second;
+ assert(!isa<SCEVConstant>(Value));
+ auto It = ValuesAtScopes.find(Value);
+ if (It != ValuesAtScopes.end() &&
+ is_contained(It->second, std::make_pair(L, ValueAtScope)))
+ continue;
+ dbgs() << "Value: " << *Value << ", Loop: " << *L << ", ValueAtScope: "
+ << ValueAtScope << " missing in ValuesAtScopes\n";
+ std::abort();
+ }
+ }
+
+ // Verify integrity of BECountUsers.
+ auto VerifyBECountUsers = [&](bool Predicated) {
+ auto &BECounts =
+ Predicated ? PredicatedBackedgeTakenCounts : BackedgeTakenCounts;
+ for (const auto &LoopAndBEInfo : BECounts) {
+ for (const ExitNotTakenInfo &ENT : LoopAndBEInfo.second.ExitNotTaken) {
+ if (!isa<SCEVConstant>(ENT.ExactNotTaken)) {
+ auto UserIt = BECountUsers.find(ENT.ExactNotTaken);
+ if (UserIt != BECountUsers.end() &&
+ UserIt->second.contains({ LoopAndBEInfo.first, Predicated }))
+ continue;
+ dbgs() << "Value " << *ENT.ExactNotTaken << " for loop "
+ << *LoopAndBEInfo.first << " missing from BECountUsers\n";
+ std::abort();
+ }
+ }
+ }
+ };
+ VerifyBECountUsers(/* Predicated */ false);
+ VerifyBECountUsers(/* Predicated */ true);
}
bool ScalarEvolution::invalidate(
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-11 09:32:48 +0000