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 ...

[indvars] Use fact loop must exit to canonicalize to unsigned conditions

The logic in this patch is that if we find a comparison which would be unsigned except for when the loop is infinite, and we

[indvars] Use fact loop must exit to canonicalize to unsigned conditions

The logic in this patch is that if we find a comparison which would be unsigned except for when the loop is infinite, and we can prove that an infinite loop must be ill defined, we can still make the predicate unsigned.

The eventual goal (combined with a follow on patch) is to use the fact the loop exits to remove the zext (see tests) entirely.

A couple of points worth noting:
* We loose the ability to prove the loop unreachable by committing to the must exit interpretation. If instead, we later proved that rhs was definitely outside the range required for finiteness, we could have killed the loop entirely. (We don't currently implement this transform, but could in theory, do so.)
* simplifyAndExtend has a very limited list of users it walks. In particular, in the examples is stops at the zext and never visits the icmp. (Because we can't fold the zext to an addrec yet in SCEV.) Being willing to visit when we haven't simplified regresses multiple tests (seemingly because of less optimal results when computing trip counts). D112170 explores fixing that, but - at least so far - appears to be too expensive compile time wise.

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

show more ...

Extend transform introduced in D111896 to multiple exits

This is trivial. It was left out of the original review only because we had multiple copies of the same code in review at the same time, and

Extend transform introduced in D111896 to multiple exits

This is trivial. It was left out of the original review only because we had multiple copies of the same code in review at the same time, and keeping them in sync was easiest if the structure was kept in sync.

show more ...

[indvars] Canonicalize exit conditions to unsigned using range info

This patch duplicates a bit of logic we apply to comparisons encountered during the IV users walk to conditions which feed exit co

[indvars] Canonicalize exit conditions to unsigned using range info

This patch duplicates a bit of logic we apply to comparisons encountered during the IV users walk to conditions which feed exit conditions. Why? simplifyAndExtend has a very limited list of users it walks. In particular, in the examples is stops at the zext and never visits the icmp. (Because we can't fold the zext to an addrec yet in SCEV.) Being willing to visit when we haven't simplified regresses multiple tests (seemingly because of less optimal results when computing trip counts).

Note that this can be trivially extended to multiple exiting blocks. I'm leaving that to a future patch (solely to cut down on the number of versions of the same code in review at once.)

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

show more ...

[CSSPGO] Unblock optimizations with pseudo probe instrumentation part 3.

This patch continues unblocking optimizations that are blocked by pseudo probe instrumentation.

Not exactly like DbgIntrinsi

[CSSPGO] Unblock optimizations with pseudo probe instrumentation part 3.

This patch continues unblocking optimizations that are blocked by pseudo probe instrumentation.

Not exactly like DbgIntrinsics, PseudoProbe intrinsic has other attributes (such as mayread, maywrite, mayhaveSideEffect) that can block optimizations. The issues fixed are:
- Flipped default param of getFirstNonPHIOrDbg API to skip pseudo probes
- Unblocked CSE by avoiding pseudo probe from clobbering memory SSA
- Unblocked induction variable simpliciation
- Allow empty loop deletion by treating probe intrinsic isDroppable
- Some refactoring.

Reviewed By: wenlei

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

show more ...

[IndVarSimplify] Forget phi value after changing incoming value.

This fixes an issue exposed by D71539, where IndVarSimplify tries
to access an invalid cached SCEV expression after making changes to

[IndVarSimplify] Forget phi value after changing incoming value.

This fixes an issue exposed by D71539, where IndVarSimplify tries
to access an invalid cached SCEV expression after making changes to the
underlying PHI instruction earlier.

When changing the incoming value of a PHI, forget the cached SCEV for
the PHI.

show more ...

[NFC] Add assert and test showing that revert of D109596 wasn't justified

All transforms of IndVars have prerequisite requirement of LCSSA and LoopSimplify
form and rely on it. Added test that shows

[NFC] Add assert and test showing that revert of D109596 wasn't justified

All transforms of IndVars have prerequisite requirement of LCSSA and LoopSimplify
form and rely on it. Added test that shows that this actually stands.

show more ...