[SCEV] Rename max backedge-taken count -> constant max backedge taken-count in printout

This is a preparatory step for introducing symbolic max backedge-taken count.

[SCEV][NFC] Rename MaxNotTaken -> ConstantMaxNotTaken

We are going to introduce SymbolicMaxNotTaken, avoid mixing
things up.

Differential Revision: https://reviews.llvm.org/D138568
Reviewed By: leb

[SCEV][NFC] Rename MaxNotTaken -> ConstantMaxNotTaken

We are going to introduce SymbolicMaxNotTaken, avoid mixing
things up.

Differential Revision: https://reviews.llvm.org/D138568
Reviewed By: lebedev.ri

show more ...

[SCEV][NFC] Fix typo in comment

[SCEV][NFC] Introduce API for getting basic block's symbolic max exit count

Currently, it just returns exact exit count. This is a refectoring step
before it is actually implemented.

[SCEV][NFC] Call getExitCount with SymbolicMaximum when computing loop symbolic max

Currently this is NFC, because SymbolicMaximum for BB is not implemented and just
reuses exact result. However, fr

[SCEV][NFC] Call getExitCount with SymbolicMaximum when computing loop symbolic max

Currently this is NFC, because SymbolicMaximum for BB is not implemented and just
reuses exact result. However, from code purity perspective, it's a necessary step
to do. Plans to implement symbolic max for blocks are underway.

show more ...

[SCEV] Iteratively compute ranges for deeply nested expressions.

At the moment, getRangeRef may overflow the stack for very deeply nested
expressions.

This patch introduces a new getRangeRefIter fu

[SCEV] Iteratively compute ranges for deeply nested expressions.

At the moment, getRangeRef may overflow the stack for very deeply nested
expressions.

This patch introduces a new getRangeRefIter function, which first builds
a worklist of N-ary expressions and phi nodes, followed by their
operands iteratively.

getRangeRef has been extended to also take a Depth argument and it
switches to use getRangeRefIter once the depth reaches a certain
threshold.

This ensures compile-time is not impacted in general. Note that
the iterative algorithm may lead to a slightly different evaluation
order, which could result in slightly worse ranges for cyclic phis.

https://llvm-compile-time-tracker.com/compare.php?from=23c3eb7cdf3478c9db86f6cb5115821a8f0f5f40&to=e0e09fa338e77e53242bfc846e1484350ad79773&stat=instructions

Fixes #49579.

Reviewed By: mkazantsev

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

show more ...

[SCEV] Replace assert with returning CouldNotComp in computeMaxBECountForLT.

This patch removes the bail out for signed predicates and non-positive
strides in howManyLessThans and updates computeMax

[SCEV] Replace assert with returning CouldNotComp in computeMaxBECountForLT.

This patch removes the bail out for signed predicates and non-positive
strides in howManyLessThans and updates computeMaxBECountForLT to return
SCEVCouldNotCompute for signed predicates with negative strides.

AFAICT bail-out was only added because computeMaxBECountForLT may not
handle negative signed strides correctly. Instead of not calling
computeMaxBECountForLT at all because we bail out earlier, we can
instead return SCEVCouldNotCompute in computeMaxBECountForLT.

The max backedge taken count will be computed as the max value of the
symbolic backedge taken count.

This improves precision in cases where we can compute symbolic backedge
taken counts and also fixes a crash.

Fixes #57818.

Reviewed By: nikic

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

show more ...

[IndVarSimplify] Clear block and loop dispositions after moving instr.

Moving an instruction can invalidate the cached block dispositions of
the corresponding SCEV. Invalidate the cached disposition

[IndVarSimplify] Clear block and loop dispositions after moving instr.

Moving an instruction can invalidate the cached block dispositions of
the corresponding SCEV. Invalidate the cached dispositions.

Also fixes a copy-paste error in forgetBlockAndLoopDispositions where
the start expression S was removed from BlockDispositions in the loop
but not the current values. This was also exposed by the new test case.

Fixes #58439.

show more ...

[SCEV] Verify block disposition cache.

This extends the existing SCEV verification to catch cache invalidation
issues as in #57837.

The validation logic is similar to the recently added loop dispos

[SCEV] Verify block disposition cache.

This extends the existing SCEV verification to catch cache invalidation
issues as in #57837.

The validation logic is similar to the recently added loop disposition
cache validation in bb68b2402daa9.

Reviewed By: nikic

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

show more ...

Recommit "[SCEV] Support clearing Block/LoopDispositions for a single value."

This reverts commit 92f698f01fa0bb8967233a6391ada2d51849fa68.

The updated version of the patch includes handling for no

Recommit "[SCEV] Support clearing Block/LoopDispositions for a single value."

This reverts commit 92f698f01fa0bb8967233a6391ada2d51849fa68.

The updated version of the patch includes handling for non-SCEVable
types. A test case has been added in ec86e9a99bca802.

show more ...

Revert "[SCEV] Support clearing Block/LoopDispositions for a single value."

This reverts commit 9e931439ddb9b6b8f655940b9d8ed6db50c2a7e2.

This commit causes a crash when TSan, e.g. with
https://lab

Revert "[SCEV] Support clearing Block/LoopDispositions for a single value."

This reverts commit 9e931439ddb9b6b8f655940b9d8ed6db50c2a7e2.

This commit causes a crash when TSan, e.g. with
https://lab.llvm.org/buildbot/#/builders/70/builds/28309/steps/10/logs/stdio

Reverting while I extract a reproducer and submit a fix.

show more ...

[SCEV] Support clearing Block/LoopDispositions for a single value.

Extend forgetBlockAndLoopDisposition to allow clearing information for a
single value. This can be useful when only a single value

[SCEV] Support clearing Block/LoopDispositions for a single value.

Extend forgetBlockAndLoopDisposition to allow clearing information for a
single value. This can be useful when only a single value is changed,
e.g. because the instruction is moved.

We also need to clear the cached values for all SCEV users, because they
may depend on the starting value's disposition.

Reviewed By: nikic

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

show more ...

[LoopDeletion] Clear block & loop dispo cache after breaking backedge.

breakLoopBackedge may remove blocks and loops. Also clear block &
loop disposition to avoid the cache containing invalid blocks

[LoopDeletion] Clear block & loop dispo cache after breaking backedge.

breakLoopBackedge may remove blocks and loops. Also clear block &
loop disposition to avoid the cache containing invalid blocks and loops.

The coverage for the change is provided when using an ASAN build of opt
to run the LoopDeletion unit tests; without the fix, pointers to invalid
objects would be used.

Reviewed By: nikic

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

show more ...

[LoopUnroll] Forget block and loop dispositions during unrolling.

After unrolling a loop, the block and loop dispositions need to be
cleared. As we don't know which SCEVs in the loop/blocks may be
i

[LoopUnroll] Forget block and loop dispositions during unrolling.

After unrolling a loop, the block and loop dispositions need to be
cleared. As we don't know which SCEVs in the loop/blocks may be
impacted, completely clear the cache. This should also fix some cases
where deleted loops remained in the LoopDispositions cache.

This fixes a verification failure surfaced by D134531.

I am planning on reviewing/updating the existing uses of
forgetLoopDispositions to check if they should be replaced by
forgetBlockAndLoopDispositions.

Reviewed By: nikic

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

show more ...

[SCEV] Don't verify dispositions of invalid loops

This should fix the expensive checks build. Ideally we would not
have invalid loops in LoopDispositions.

[SCEV] Verify contents of loop disposition cache

It seems that it is sometimes broken. Initial motivation for this was
investigation of https://github.com/llvm/llvm-project/issues/56260, but
it also

[SCEV] Verify contents of loop disposition cache

It seems that it is sometimes broken. Initial motivation for this was
investigation of https://github.com/llvm/llvm-project/issues/56260, but
it also seems that we have found an unrelated bug in LoopFusion that leaves
broken caches.

Differential Revision: https://reviews.llvm.org/D134158
Reviewed By: nikic

show more ...

[SCEV][NFC] Remove unused parameter from forgetLoopDispositions

Let's be honest about it, we don't drop loop dispositions for
particular loops. Remove the parameter that misleadingly makes
it appare

[SCEV][NFC] Remove unused parameter from forgetLoopDispositions

Let's be honest about it, we don't drop loop dispositions for
particular loops. Remove the parameter that misleadingly makes
it apparent that we do.

show more ...

[llvm] Don't including SetVector.h (NFC)

llvm/lib/ProfileData/RawMemProfReader.cpp uses SetVector without
including SetVector.h, so this patch adds an appropriate #include
there.

Use std::gcd (NFC)

This patch replaces calls to GreatestCommonDivisor64 with std::gcd
where both arguments are known to be of unsigned types no larger than
64 bits in size.

[SCEV] Prove condition invariance via context, try 2

Initial implementation had too weak requirements to positive/negative
range crossings. Not crossing zero with nuw is not enough for two reasons:

[SCEV] Prove condition invariance via context, try 2

Initial implementation had too weak requirements to positive/negative
range crossings. Not crossing zero with nuw is not enough for two reasons:

- If ArLHS has negative step, it may turn from positive to negative
without crossing 0 boundary from left to right (and crossing right to
left doesn't count for unsigned);
- If ArLHS crosses SINT_MAX boundary, it still turns from positive to
negative;

In fact we require that ArLHS always stays non-negative or negative,
which an be enforced by the following set of preconditions:

- both nuw and nsw;
- positive step (looks liftable);

Because of positive step, boundary crossing is only possible from left
part to the right part. And because of no-wrap flags, it is guaranteed
to never happen.

show more ...

Remove redundant initialization of Optional (NFC)

Revert "[SCEV] Prove condition invariance via context"

This reverts commit a3d1fb3b59b473e4f262a05f187de6474b7721e7.

Reverting until investigation of https://github.com/llvm/llvm-project/issues/572

Revert "[SCEV] Prove condition invariance via context"

This reverts commit a3d1fb3b59b473e4f262a05f187de6474b7721e7.

Reverting until investigation of https://github.com/llvm/llvm-project/issues/57247
has concluded.

show more ...

Return "[SCEV] Use context to strengthen flags of BinOps"

This reverts commit 354fa0b48008eca701a110badd6974bf449df257.

Returning as is. The patch was reverted due to a miscompile, but
this patch i

Return "[SCEV] Use context to strengthen flags of BinOps"

This reverts commit 354fa0b48008eca701a110badd6974bf449df257.

Returning as is. The patch was reverted due to a miscompile, but
this patch is not causing it. This patch made it possible to infer
some nuw flags in code guarded by `false` condition, and then someone
else to managed to propagate the flag from dead code outside.

Returning the patch to be able to reproduce the issue.

show more ...

Revert "[SCEV] Use context to strengthen flags of BinOps"

This reverts commit 34ae308c73e4d76dbdab25a6206d3fbc5ebafdf5.

Our internal testing found a miscompile. Not sure if it's caused by
this patc

Revert "[SCEV] Use context to strengthen flags of BinOps"

This reverts commit 34ae308c73e4d76dbdab25a6206d3fbc5ebafdf5.

Our internal testing found a miscompile. Not sure if it's caused by
this patch or it revealed something else. Reverting while investigating.

show more ...

[SCEV] Prove condition invariance via context

Contextual knowledge may be used to prove invariance of some conditions.
For example, in this case:
```
; %len >= 0
guard(%iv = {start,+,1}<nuw> <s

[SCEV] Prove condition invariance via context

Contextual knowledge may be used to prove invariance of some conditions.
For example, in this case:
```
; %len >= 0
guard(%iv = {start,+,1}<nuw> <s %len)
guard(%iv = {start,+,1}<nuw> <u %len)
```
the 2nd check always fails if `start` is negative and always passes otherwise.

It looks like there are more opportunities of this kind that are still to be
implemented in the future.

Differential Revision: https://reviews.llvm.org/D129753
Reviewed By: apilipenko

show more ...