[SCEV] Verify integrity of ValuesAtScopes and users (NFC)

Make sure that ValuesAtScopes and ValuesAtScopesUsers are
consistent during SCEV verification.

[SCEV] Track and invalidate ValuesAtScopes users

ValuesAtScopes maps a SCEV and a Loop to another SCEV. While we
invalidate entries if the left-hand SCEV is invalidated, we
currently don't do this f

[SCEV] Track and invalidate ValuesAtScopes users

ValuesAtScopes maps a SCEV and a Loop to another SCEV. While we
invalidate entries if the left-hand SCEV is invalidated, we
currently don't do this for the right-hand SCEV. Fix this by
tracking users in a reverse map and using it for invalidation.

This is conceptually the same change as D114738, but using the
reverse map to avoid performance issues.

Differential Revision: https://reviews.llvm.org/D114788

show more ...

[SCEV] Remove incorrect assert

Fix assertion failure reported on D113349 by removing the assert.
While the produced expression should be equivalent, it may not
be strictly the same, e.g. due to lazy

[SCEV] Remove incorrect assert

Fix assertion failure reported on D113349 by removing the assert.
While the produced expression should be equivalent, it may not
be strictly the same, e.g. due to lazy nowrap flag updates. Similar
to what the main createSCEV() code does, simply retain the old
value map entry if one already exists.

show more ...

[SCEV] Turn validity check in getExistingSCEV into assert (NFC).

Now that we track users of SCEV expressions, we should be able to always
invalidate containing expressions.

With that, I think the c

[SCEV] Turn validity check in getExistingSCEV into assert (NFC).

Now that we track users of SCEV expressions, we should be able to always
invalidate containing expressions.

With that, I think the case where a value gets removed but
SCEVs containing references to it should not be possible any longer.
Turn check into an assert.

This slightly reduces compile-time:

NewPM-O3: -0.27%
NewPM-ReleaseThinLTO: -0.21%
NewPM-ReleaseLTO-g: -0.26%

http://llvm-compile-time-tracker.com/compare.php?from=c3dc6b081da6ba503e67d260033f81f61eb38ea3&to=95a4a028b1f1dd0bc3d221435953b7d2c031b3d5&stat=instructions

Reviewed By: nikic

Differential Revision: https://reviews.llvm.org/D114633

show more ...

[SCEV] Simplify forgetSymbolicName() (NFCI)

With the recently introduced tracking as well as D113349, we can
greatly simplify forgetSymbolicName(). In fact, we can simply
replace it with forgetMemoi

[SCEV] Simplify forgetSymbolicName() (NFCI)

With the recently introduced tracking as well as D113349, we can
greatly simplify forgetSymbolicName(). In fact, we can simply
replace it with forgetMemoizedResults().

What forgetSymbolicName() used to do is to walk the IR use-def
chain to find all SCEVs that mention the SymbolicName. However,
thanks to use tracking, we can now determine the relevant SCEVs
in a more direct way. D113349 is needed to also clear out the
actual IR to SCEV mapping in ValueExprMap.

Differential Revision: https://reviews.llvm.org/D114263

show more ...

[SCEV] Simplify invalidation after BE count calculation (NFCI)

After backedge taken counts have been calculated, we want to
invalidate all addrecs and dependent expressions in the loop,
because we m

[SCEV] Simplify invalidation after BE count calculation (NFCI)

After backedge taken counts have been calculated, we want to
invalidate all addrecs and dependent expressions in the loop,
because we might compute better results with the newly available
backedge taken counts. Previously this was done with a forgetLoop()
style use-def walk. With recent improvements to SCEV invalidation,
we can instead directly invalidate any SCEVs using addrecs in this
loop. This requires a great deal less subtlety to avoid invalidating
more than necessary, and in particular gets rid of the hack from
D113349. The change is similar to D114263 in spirit.

show more ...

Reland [SCEV] Fix and validate ValueExprMap/ExprValueMap consistency

Relative to the previous landing attempt, this introduces an additional
flag on forgetMemoizedResults() to not remove SCEVUnknown

Reland [SCEV] Fix and validate ValueExprMap/ExprValueMap consistency

Relative to the previous landing attempt, this introduces an additional
flag on forgetMemoizedResults() to not remove SCEVUnknown phis from
the value map. The invalidation after BECount calculation wants to
leave these alone and skips them in its own use-def walk, but we can
still end up invalidating them via forgetMemoizedResults() if there
is another IR value with the same SCEV. This is intended as a temporary
workaround only, and the need for this should go away once the
getBackedgeTakenInfo() invalidation is refactored in the spirit of
D114263.

-----

This adds validation for consistency of ValueExprMap and
ExprValueMap, and fixes identified issues:

* Addrec construction directly wrote to ValueExprMap in a few places,
without updating ExprValueMap. Add a helper to ensures they stay
consistent. The adjustment in forgetSymbolicName() explicitly
drops the old value from the map, so that we don't rely on it
being overwritten.
* forgetMemoizedResultsImpl() was dropping the SCEV from
ExprValueMap, but not dropping the corresponding entries from
ValueExprMap.

Differential Revision: https://reviews.llvm.org/D113349

show more ...

Revert "[SCEV] Fix and validate ValueExprMap/ExprValueMap consistency"

This reverts commit bee8dcda1f01831808885ea23f9ac1467ce660f5.

Some sanitizer buildbots fail with:
> Attempt to use a SCEVCould

Revert "[SCEV] Fix and validate ValueExprMap/ExprValueMap consistency"

This reverts commit bee8dcda1f01831808885ea23f9ac1467ce660f5.

Some sanitizer buildbots fail with:
> Attempt to use a SCEVCouldNotCompute object!

For example:
https://lab.llvm.org/buildbot/#/builders/85/builds/7020/steps/9/logs/stdio

show more ...

[SCEV] Fix and validate ValueExprMap/ExprValueMap consistency

Relative to the previous landing attempt, this makes
insertValueToMap() resilient against the value already being
present in the map --

[SCEV] Fix and validate ValueExprMap/ExprValueMap consistency

Relative to the previous landing attempt, this makes
insertValueToMap() resilient against the value already being
present in the map -- previously I only checked this for the
createSimpleAffineAddRec() case, but the same issue can also
occur for the general createNodeForPHI(). In both cases, the
addrec may be constructed and added to the map in a recursive
query trying to create said addrec. In this case, this happens
due to the invalidation when the BE count is computed, which
ends up clearing out the symbolic name as well.

-----

This adds validation for consistency of ValueExprMap and
ExprValueMap, and fixes identified issues:

* Addrec construction directly wrote to ValueExprMap in a few places,
without updating ExprValueMap. Add a helper to ensures they stay
consistent. The adjustment in forgetSymbolicName() explicitly
drops the old value from the map, so that we don't rely on it
being overwritten.
* forgetMemoizedResultsImpl() was dropping the SCEV from
ExprValueMap, but not dropping the corresponding entries from
ValueExprMap.

Differential Revision: https://reviews.llvm.org/D113349

show more ...

[SCEV] Turn check in createSimpleAffineAddRec to assertion. (NFC)

Accum is guaranteed to be defined outside L (via Loop::isLoopInvariant
checks above). I think that should guarantee that the more po

[SCEV] Turn check in createSimpleAffineAddRec to assertion. (NFC)

Accum is guaranteed to be defined outside L (via Loop::isLoopInvariant
checks above). I think that should guarantee that the more powerful
ScalarEvolution::isLoopInvariant also determines that the value is loop
invariant.

Reviewed By: nikic

Differential Revision: https://reviews.llvm.org/D114634

show more ...

[LLVM][NFC]Inclusive language: remove occurances of sanity check/test from llvm

Part of work to use more inclusive language in clang/llvm. Rewording
some comments and change function and variable na

[LLVM][NFC]Inclusive language: remove occurances of sanity check/test from llvm

Part of work to use more inclusive language in clang/llvm. Rewording
some comments and change function and variable names.

show more ...

Revert "[SCEV] Fix and validate ValueExprMap/ExprValueMap consistency"

This reverts commit d633db8f9dd4a361e60a9030c82adc490d5797e3.

Causes bootstrap assertion failures:
https://lab.llvm.org/buildb

Revert "[SCEV] Fix and validate ValueExprMap/ExprValueMap consistency"

This reverts commit d633db8f9dd4a361e60a9030c82adc490d5797e3.

Causes bootstrap assertion failures:
https://lab.llvm.org/buildbot/#/builders/168/builds/3459/steps/9/logs/stdio

show more ...

[SCEV] Fix and validate ValueExprMap/ExprValueMap consistency

This adds validation for consistency of ValueExprMap and
ExprValueMap, and fixes identified issues:

* Addrec construction directly wrot

[SCEV] Fix and validate ValueExprMap/ExprValueMap consistency

This adds validation for consistency of ValueExprMap and
ExprValueMap, and fixes identified issues:

* Addrec construction directly wrote to ValueExprMap in a few places,
without updating ExprValueMap. Add a helper to ensures they stay
consistent. The adjustment in forgetSymbolicName() explicitly
drops the old value from the map, so that we don't rely on it
being overwritten.
* forgetMemoizedResultsImpl() was dropping the SCEV from
ExprValueMap, but not dropping the corresponding entries from
ValueExprMap.

Differential Revision: https://reviews.llvm.org/D113349

show more ...

[llvm] Use range-based for loops (NFC)

[SCEV] Revert two speculative compile time optimizations which made no difference

Revert "[SCEV] Defer all work from ea12c2cb as late as possible"
Revert "[SCEV] Defer loop property checks from ea12

[SCEV] Revert two speculative compile time optimizations which made no difference

Revert "[SCEV] Defer all work from ea12c2cb as late as possible"
Revert "[SCEV] Defer loop property checks from ea12c2cb as late as possible"

This reverts commit 734abbad79dbcbd0e880510fbab1ef0e701cfc7b and 1a5666acb281c7510504e726ba481d09ab5f5b95.

Both of these changes were speculative attempts to address a compile time regression. Neither worked, and both complicated the code in undesirable ways.

show more ...

[SCEV] Defer all work from ea12c2cb as late as possible

This is a second speculative compile time optimization to address a reported regression. My actual suspicion is that availability of no-self-

[SCEV] Defer all work from ea12c2cb as late as possible

This is a second speculative compile time optimization to address a reported regression. My actual suspicion is that availability of no-self-wrap is making some *other* bit of code trigger, but let's rule this out.

show more ...

[SCEV] Defer loop property checks from ea12c2cb as late as possible

This is a speculative compile time optimization to address a reported regression. It's the only thing which vaguely makes sense.

[SCEV] Move mustprogress based no-self-wrap logic so it applies to all exit conditions

This change moves logic which we'd added specifically for less than tests so that it applies to equalities and

[SCEV] Move mustprogress based no-self-wrap logic so it applies to all exit conditions

This change moves logic which we'd added specifically for less than tests so that it applies to equalities and greater than tests as well. The basic idea is that if we can show an IV cycles infinitely through the same series on self-wrap, and that the exit condition must be taken to prevent UB, we can conclude that it must be taken before self-wrap and thus infer said flag.

The motivation here is simple loops with unsigned induction variables w/non-one steps and inequality tests. A toy example would be:
for (unsigned i = 0; i != N; i += 2) { body; }

If body contains no side effects, and this is a mustprogress function, we can assume that this must be a finite loop and thus that the exit count is N/2.

Differential Revision: https://reviews.llvm.org/D103991

show more ...

[SCEV] Reorder operands checks in collectConditions.

The initial two cases require a SCEVConstant as RHS. Pull up the condition
to check and swap SCEVConstants from below. Also remove a redundant
ch

[SCEV] Reorder operands checks in collectConditions.

The initial two cases require a SCEVConstant as RHS. Pull up the condition
to check and swap SCEVConstants from below. Also remove a redundant
check & swap if RHS is SCEVUnknown.

show more ...

[SCEVAA] Avoid forming malformed pointer diff expressions

This solves the same crash as in D104503, but with a different approach.

The test case test_non_dom demonstrates a case where scev-aa crash

[SCEVAA] Avoid forming malformed pointer diff expressions

This solves the same crash as in D104503, but with a different approach.

The test case test_non_dom demonstrates a case where scev-aa crashes today. (If exercised either by -eval-aa or -licm.) The basic problem is that SCEV-AA expects to be able to compute a pointer difference between two SCEVs for any two pair of pointers we do an alias query on. For (valid, but out of scope) reasons, we can end up asking whether expressions in different sub-loops can alias each other. This results in a subtraction expression being formed where neither operand dominates the other.

The approach this patch takes is to leverage the "defining scope" notion we introduced for flag semantics to detect and disallow the formation of the problematic SCEV. This ends up being relatively straight forward on that new infrastructure. This change does hint that we should probably be verifying a similar property for all SCEVs somewhere, but I'll leave that to a follow on change.

Differential Revision: D114112

show more ...

[SCEV] Apply loop guards when computing max BTC for arbitrary steps.

Similar other cases in the current function (e.g. when the step is 1 or
-1), applying loop guards can lead to tighter upper bound

[SCEV] Apply loop guards when computing max BTC for arbitrary steps.

Similar other cases in the current function (e.g. when the step is 1 or
-1), applying loop guards can lead to tighter upper bounds for the
backedge-taken counts.

Fixes PR52464.

Reviewed By: reames, nikic

Differential Revision: https://reviews.llvm.org/D113578

show more ...

[SCEV] Canonicalize X - urem X, Y patterns

There are multiple possible ways to represent the X - urem X, Y pattern. SCEV was not canonicalizing, and thus, depending on which you analyzed, you could

[SCEV] Canonicalize X - urem X, Y patterns

There are multiple possible ways to represent the X - urem X, Y pattern. SCEV was not canonicalizing, and thus, depending on which you analyzed, you could get different results. The sub representation appears to produce strictly inferior results in practice, so I decided to canonicalize to the Y * X/Y version.

The motivation here is that runtime unroll produces the sub X - (and X, Y-1) pattern when Y is a power of two. SCEV is thus unable to recognize that an unrolled loop exits because we don't figure out that the new unrolled step evenly divides the trip count of the unrolled loop. After instcombine runs, we convert the the andn form which SCEV recognizes, so essentially, this is just fixing a nasty pass ordering dependency.

The ARM loop hardware interaction in the test diff is opague to me, but the comments in the review from others knowledge of the infrastructure appear to indicate these are improvements in loop recognition, not regressions.

Differential Revision: https://reviews.llvm.org/D114018

show more ...

[SCEV] Support rewriting ZExt expressions with loop guard info.

So far, applying loop guard information has been restricted to
SCEVUnknown. In a few cases, like PR40961 and PR52464, this leads to
SC

[SCEV] Support rewriting ZExt expressions with loop guard info.

So far, applying loop guard information has been restricted to
SCEVUnknown. In a few cases, like PR40961 and PR52464, this leads to
SCEV failing to determine tight upper bounds for the backedge taken
count.

This patch adjusts SCEVLoopGuardRewriter and applyLoopGuards to support
re-writing ZExt expressions.

This is a first step towards fixing PR40961 and PR52464.

Reviewed By: reames

Differential Revision: https://reviews.llvm.org/D113577

show more ...

[SCEV] Update SCEVLoopGuardRewriter to hold reference to map. (NFC)

SCEVLoopGuardRewriter doesn't need to copy the rewrite map. It can just
hold a const reference instead, to avoid an unnecessary co

[SCEV] Update SCEVLoopGuardRewriter to hold reference to map. (NFC)

SCEVLoopGuardRewriter doesn't need to copy the rewrite map. It can just
hold a const reference instead, to avoid an unnecessary copy.

show more ...

[SCEV] Update SCEVLoopGuardRewriter to take SCEV -> SCEV map (NFC).

Split off refactoring from D113577 to reduce the diff. NFC as the new
interface will only be used in D113577.