[SCEVExpander] Make CanonicalMode handing in isSafeToExpand() more robust (PR50506)

isSafeToExpand() for addrecs depends on whether the SCEVExpander
will be used in CanonicalMode. At least one calle

[SCEVExpander] Make CanonicalMode handing in isSafeToExpand() more robust (PR50506)

isSafeToExpand() for addrecs depends on whether the SCEVExpander
will be used in CanonicalMode. At least one caller currently gets
this wrong, resulting in PR50506.

Fix this by a) making the CanonicalMode argument on the freestanding
functions required and b) adding member functions on SCEVExpander
that automatically take the SCEVExpander mode into account. We can
use the latter variant nearly everywhere, and thus make sure that
there is no chance of CanonicalMode mismatch.

Fixes https://github.com/llvm/llvm-project/issues/50506.

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

show more ...

[IndVars] Make sure header phi simplification preserves LCSSA form

When simplifying instructions, make sure that the replacement
preserves LCSSA form. This fixes the issue reported at:
https://revie

[IndVars] Make sure header phi simplification preserves LCSSA form

When simplifying instructions, make sure that the replacement
preserves LCSSA form. This fixes the issue reported at:
https://reviews.llvm.org/D129293#3650851

show more ...

[IndVars] Simplify instructions after replacing header phi with preheader value

After replacing a loop phi with the preheader value, it's usually
possible to simplify some of the using instructions,

[IndVars] Simplify instructions after replacing header phi with preheader value

After replacing a loop phi with the preheader value, it's usually
possible to simplify some of the using instructions, so do that as
part of replaceLoopPHINodesWithPreheaderValues().

Doing this as part of IndVars is valuable, because it may make GEPs
in the loop have constant offsets and allow the following SROA run
to succeed (as demonstrated in the PhaseOrdering test).

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

show more ...

[IndVars] Call replaceLoopPHINodesWithPreheaderValues() for already constant exits

Currently we only call replaceLoopPHINodesWithPreheaderValues() if
optimizeLoopExits() replaces the exit with an un

[IndVars] Call replaceLoopPHINodesWithPreheaderValues() for already constant exits

Currently we only call replaceLoopPHINodesWithPreheaderValues() if
optimizeLoopExits() replaces the exit with an unconditional exit.
However, it is very common that this already happens as part of
eliminateIVComparison(), in which case we're leaving behind the
dead header phi.

Tweak the early bailout for already-constant exits to also call
replaceLoopPHINodesWithPreheaderValues().

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

show more ...

[LSR] Fix bug for optimizing unused IVs to final values

This is a fix for a crash reported for https://reviews.llvm.org/D118808
The fix is to only consider PHINodes which are induction phis.
Fixes #

[LSR] Fix bug for optimizing unused IVs to final values

This is a fix for a crash reported for https://reviews.llvm.org/D118808
The fix is to only consider PHINodes which are induction phis.
Fixes #55529

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

show more ...

[NFC] Switch a few uses of undef to poison as placeholders for unreachble code

Cleanup includes: Transform/Scalar

Estimated impact on preprocessor output line:
before: 1062981579
after: 1062494547

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cl

Cleanup includes: Transform/Scalar

Estimated impact on preprocessor output line:
before: 1062981579
after: 1062494547

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D120817

show more ...

[IndVars] Use phis() (NFC)

[llvm] Remove unused forward declarations (NFC)

[IndVars] Support opaque pointers in LFTR

Remove the assertion about the pointer element type, only check
that the stride is one. Ultimately, the actual pointer type here
doesn't matter, because SCE

[IndVars] Support opaque pointers in LFTR

Remove the assertion about the pointer element type, only check
that the stride is one. Ultimately, the actual pointer type here
doesn't matter, because SCEVExpander would insert appropriate
casts if necessary.

show more ...

[indvars] Fix lftr crash when preheader is terminated by switch

This was found by oss-fuzz. The switch will get canonicalized to a branch, but if it hasn't been when we run LFTR, we crashed on an u

[indvars] Fix lftr crash when preheader is terminated by switch

This was found by oss-fuzz. The switch will get canonicalized to a branch, but if it hasn't been when we run LFTR, we crashed on an unneeded assert.

show more ...

[IndVarSimplify] Reduce nondeterministic behaviour in visitIVCast.

rGf39978b84f1d3a1da6c32db48f64c8daae64b3ad led to and/or exposed
an issue with IndVarSimplification for a loop where a i32 phi node

[IndVarSimplify] Reduce nondeterministic behaviour in visitIVCast.

rGf39978b84f1d3a1da6c32db48f64c8daae64b3ad led to and/or exposed
an issue with IndVarSimplification for a loop where a i32 phi node is
no longer replaced by a widened (i64) phi node, because the SCEVs of a
sign-extend no longer folded the same way. I'm unsure how to properly
explain this because it's all rather complicated, but in short: SCEVs
don't fold as nicely as they used to and this caused a difference.

While investigating this, I found that IndVarSimplify can actually
optimise the case in the way we want to if it chooses the widened IV to
be 'signed' (the i32 IV is both sign and zero-extended). Oddly enough,
there is some level of indeterminism in the way the algorithm works,
it just picks the sign of the 'first' zext/sext user, where the order of
the users-iterator is not guaranteed to be the same on each invocation
of the pass (e.g. shown by first running loop-rotate, which puts the
users in a different order).

While I think the fix is valid in the sense that consistently picking
_any_ order is better than having an nondeterministic order, I can
use a bit of advice from people more familiar in this area of the
code-base.

For example, I'm not sure if this fix is hiding another issue where the
IndVarSimplify pass could actually draw the same conclusions (i.e. that
it only needs an i64 phi node) if it does a bit more work, regardless
of whether it chooses the induction variable to be signed or unsigned.

I'm also not sure if choosing signed is better than unsigned, or whether
that just happens to be beneficial only in this individual case.

Any feedback would be much appreciated!

Reviewed By: reames

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

show more ...

Reapply 5ec2386 "Reapply db28934 "[IndVars] Pass TTI to replaceCongruentIVs""

This reverts commit 7cd273c339cfe8427404f881ae280bd9fae6ff78.

Several patches with tests fixes have been applied:
0cada

Reapply 5ec2386 "Reapply db28934 "[IndVars] Pass TTI to replaceCongruentIVs""

This reverts commit 7cd273c339cfe8427404f881ae280bd9fae6ff78.

Several patches with tests fixes have been applied:
0cada82f0a30e5ae22dce66b58604ab9b47a3897 "[Test] Remove incorrect test in GVN"
97cb13615d6d9df254e3c0f3deef9eaedfe189b6 "[Test] Separate IndVars test into AArch64 and X86 parts"
985cc490f17d28b20392ee214895d947b85120ef "[Test] Remove separated test in IndVars",
and test failures caused by 5ec2386 should be resolved now.

show more ...

Revert "Reapply db28934 "[IndVars] Pass TTI to replaceCongruentIVs""

This reverts commit 5ec23863320ca12bfabb6dcff1d0425cb614b7a5.

This change is causing test failures on the PS4 linux build bot: h

Revert "Reapply db28934 "[IndVars] Pass TTI to replaceCongruentIVs""

This reverts commit 5ec23863320ca12bfabb6dcff1d0425cb614b7a5.

This change is causing test failures on the PS4 linux build bot: https://lab.llvm.org/buildbot/#/builders/139/builds/12871

show more ...

Reapply db28934 "[IndVars] Pass TTI to replaceCongruentIVs"

This reapplies patch db289340c841990055a164e8eb2a3b5ff25677bf.

The test failures on build with expensive checks caused by the patch happe

Reapply db28934 "[IndVars] Pass TTI to replaceCongruentIVs"

This reapplies patch db289340c841990055a164e8eb2a3b5ff25677bf.

The test failures on build with expensive checks caused by the patch happened due
to the fact that we sorted loop Phis in replaceCongruentIVs using llvm::sort,
which shuffles the given container if the expensive checks are enabled,
so equivalent Phis in the sorted vector had different mutual order from run
to run. replaceCongruentIVs tries to replace narrow Phis with truncations
of wide ones. In some test cases there were several Phis with the same
width, so if their order differs from run to run, the narrow Phis would
be replaced with a different Phi, depending on the shuffling result.

The patch ae14fae0ff4304022beda5ab484f84ac0fdda807 fixed this issue by
replacing llvm::sort with llvm::stable_sort.

show more ...

Revert "[IndVars] Pass TTI to replaceCongruentIVs"

This reverts commit db289340c841990055a164e8eb2a3b5ff25677bf.

The patch caused 2 crashes with expensive checks enabled.

[IndVars] Pass TTI to replaceCongruentIVs

In IndVarSimplify after simplifying and extending loop IVs we call 'replaceCongruentIVs'.
This function optionally takes a TTI argument to be able to replac

[IndVars] Pass TTI to replaceCongruentIVs

In IndVarSimplify after simplifying and extending loop IVs we call 'replaceCongruentIVs'.
This function optionally takes a TTI argument to be able to replace narrow IVs uses
with truncates of the widest one.
For some reason the TTI wasn't passed to the function, so it couldn't perform such
transform.
This patch fixes it.

Reviewed By: mkazantsev

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

show more ...

[indvars] Use loop guards when canonicalizing exit conditions

This extends the logic in canonicalizeExitConditions to use loop guards to specialize the SCEV of the loop invariant term before quering

[indvars] Use loop guards when canonicalizing exit conditions

This extends the logic in canonicalizeExitConditions to use loop guards to specialize the SCEV of the loop invariant term before quering it's range.

show more ...

[indvars] Allow rotation (narrowing) of exit test when discovering trip count

This relaxes the one-use requirement on the rotation transform specifically for the case where we know we're zexting an

[indvars] Allow rotation (narrowing) of exit test when discovering trip count

This relaxes the one-use requirement on the rotation transform specifically for the case where we know we're zexting an IV of the loop. This allows us to discover trip count information in SCEV, which seems worth a single extra loop invariant truncate. Honestly, I'd prefer if SCEV could just compute the trip count directly (e.g. D109457), but this unblocks practical benefit.

show more ...

[indvars] Extend canonicalizeExitConditions to inverted operands

As discussed in the original reviews, but done in a follow on.

Backout must-exit based parts of 3fc9882e, and 412eb0

Not sure these are correct. I think I missed a case when porting this from the original SCEV change to the IndVar changes. I may end up reappl

Backout must-exit based parts of 3fc9882e, and 412eb0

Not sure these are correct. I think I missed a case when porting this from the original SCEV change to the IndVar changes. I may end up reapplying this later with a comment about how this is correct, but in case the current bad feeling turns out to be true, I'm removing from tree while investigating further.

show more ...

Revert "[indvars] Move a check slightlly earlier [NFC]"

This reverts commit 7ff943a9ed878e3b8ffe162b2af41a81da1a11a2.

This wasn't NFC. isSigned != !isUnsigned as there are also relational operator

Revert "[indvars] Move a check slightlly earlier [NFC]"

This reverts commit 7ff943a9ed878e3b8ffe162b2af41a81da1a11a2.

This wasn't NFC. isSigned != !isUnsigned as there are also relational operators.

show more ...

[indvars] Move a check slightlly earlier [NFC]

[indvars] Rotate zext though icmp to reduce loop varying computation

This change looks for cases where we can prove that an exit test of a loop can be performed in a narrower bitwidth, and that by d

[indvars] Rotate zext though icmp to reduce loop varying computation

This change looks for cases where we can prove that an exit test of a loop can be performed in a narrower bitwidth, and that by doing so we can replace a loop-varying extend with a loop-invariant truncate.

The motivation here is that doing this unblocks the trip count analysis for narrow IVs involved in extended compare exit tests. It also has the nice side effect of simply making the code faster, even if we gain no other benefit from the improved analysis ability.

I've noted a few places this could be extended, but I think this stands reasonable on it's own as well.

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

show more ...

[indvars] Fix pr52276 (missing one use check)

The recently added logic to canonicalize exit conditions to unsigned relies on facts which hold about the use (i.e. exit test). Applying this blindly t

[indvars] Fix pr52276 (missing one use check)

The recently added logic to canonicalize exit conditions to unsigned relies on facts which hold about the use (i.e. exit test). Applying this blindly to the icmp is not legal, as there may be another use which never reaches the exit. Restrict ourselves to case where we have a single use.

show more ...