[LoopDeletion] Convert tests to opaque pointers (NFC)

[NFC] Port all LoopDeletion tests to `-passes=` syntax

[LoopDeletion] Use max trip count to break backedge in addition to exact one

We'd added support a while back from breaking the backedge if SCEV can prove the trip count is zero. However, we used the

[LoopDeletion] Use max trip count to break backedge in addition to exact one

We'd added support a while back from breaking the backedge if SCEV can prove the trip count is zero. However, we used the exact trip count which requires *all* exits be analyzeable. I noticed while writing test cases for another patch that this disallows cases where one exit is provably taken paired with another which is unknown. This patch adds the upper bound case.

We could use a symbolic max trip count here instead, but we use an isKnownNonZero filter (presumably for compile time?) for the first-iteration reasoning. I decided this was a more obvious incremental step, and we could go back and untangle the schemes separately.

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

show more ...

Special case common branch patterns in breakLoopBackedge (try 2)

Changes since aec08e:
* Adjust placement of a closing brace so that the general case actually runs. Turns out we had *no* coverage o

Special case common branch patterns in breakLoopBackedge (try 2)

Changes since aec08e:
* Adjust placement of a closing brace so that the general case actually runs. Turns out we had *no* coverage of the switch case. I added one in eae90fd.
* Drop .llvm.loop.* metadata from the new branch as there is no longer a loop to annotate.

Original commit message:

This special cases an unconditional latch and a conditional branch latch exit to improve codegen and test readability. I am hoping to reuse this function in the runtime unroll code, but without this change, the test diffs are far too complex to assess.

show more ...

Revert "Special case common branch patterns in breakLoopBackedge"

This reverts commit aec08e86004bb3b8a7c5a86992945c936593db59.

Several problems have been reported with malformed loopinfo after thi

Revert "Special case common branch patterns in breakLoopBackedge"

This reverts commit aec08e86004bb3b8a7c5a86992945c936593db59.

Several problems have been reported with malformed loopinfo after this change, see discussion on https://reviews.llvm.org/rGaec08e86004b.

show more ...

Special case common branch patterns in breakLoopBackedge

This special cases an unconditional latch and a conditional branch latch exit to improve codegen and test readability. I am hoping to reuse

Special case common branch patterns in breakLoopBackedge

This special cases an unconditional latch and a conditional branch latch exit to improve codegen and test readability. I am hoping to reuse this function in the runtime unroll code, but without this change, the test diffs are far too complex to assess.

show more ...

[LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3)

This patch handles one particular case of one-iteration loops for which SCEV
cannot straightforwardly p

[LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3)

This patch handles one particular case of one-iteration loops for which SCEV
cannot straightforwardly prove BECount = 1. The idea of the optimization is to
symbolically execute conditional branches on the 1st iteration, moving in topoligical
order, and only visiting blocks that may be reached on the first iteration. If we find out
that we never reach header via the latch, then the backedge can be broken.

This implementation uses InstSimplify. SCEV version was rejected due to high
compile time impact.

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

show more ...

Revert "Return "[LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration" (try 2)"

This reverts commit be1a23203b1de655b8c7dac7549818d975a0cbbf.

Return "[LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration" (try 2)

The patch was reverted due to compile time impact of contextual SCEV
queries. It also appeared

Return "[LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration" (try 2)

The patch was reverted due to compile time impact of contextual SCEV
queries. It also appeared that it introduced a miscompile on irreducible CFG.

Changes made:
1. isKnownPredicateAt is replaced with more lightweight isKnownPredicate;
2. Irreducible CFG in live code is now detected and excluded from processing.

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

show more ...

Revert "Return "[LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration""

This reverts commit 43d2e51c2e86788b9e2a582fdd3d8ffa7829328a.

Commited wrong version.

Return "[LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration"

The patch was reverted due to compile time impact of contextual SCEV
queries. It also appeared that it

Return "[LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration"

The patch was reverted due to compile time impact of contextual SCEV
queries. It also appeared that it introduced a miscompile on irreducible CFG.

Changes made:
1. isKnownPredicateAt is replaced with more lightweight isKnownPredicate;
2. Irreducible CFG in live code is now detected and excluded from processing.

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

show more ...

Revert "[LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration"

This reverts commit 2531fd70d19aa5d61feb533bbdeee7717a4129eb due to
performance regression on the PPC

Revert "[LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration"

This reverts commit 2531fd70d19aa5d61feb533bbdeee7717a4129eb due to
performance regression on the PPC buildbot.

show more ...

[LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration

This patch handles one particular case of one-iteration loops for which SCEV
cannot straightforwardly prove BEC

[LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration

This patch handles one particular case of one-iteration loops for which SCEV
cannot straightforwardly prove BECount = 1. The idea of the optimization is to
symbolically execute conditional branches on the 1st iteration, moving in topoligical
order, and only visiting blocks that may be reached on the first iteration. If we find out
that we never reach header via the latch, then the backedge can be broken.

Differential Revision: https://reviews.llvm.org/D102615
Reviewed By: reames

show more ...

[LoopDeletion] Handle inner loops w/untaken backedges

This builds on the restricted after initial revert form of D93906, and adds back support for breaking backedges of inner loops. It turns out the

[LoopDeletion] Handle inner loops w/untaken backedges

This builds on the restricted after initial revert form of D93906, and adds back support for breaking backedges of inner loops. It turns out the original invalidation logic wasn't quite right, specifically around the handling of LCSSA.

When breaking the backedge of an inner loop, we can cause blocks which were in the outer loop only because they were also included in a sub-loop to be removed from both loops. This results in the exit block set for our original parent loop changing, and thus a need for new LCSSA phi nodes.

This case happens when the inner loop has an exit block which is also an exit block of the parent, and there's a block in the child which reaches an exit to said block without also reaching an exit to the parent loop.

(I'm describing this in terms of the immediate parent, but the problem is general for any transitive parent in the nest.)

The approach implemented here involves a potentially expensive LCSSA rebuild. Perf testing during review didn't show anything concerning, but we may end up needing to revert this if anyone encounters a practical compile time issue.

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

show more ...

[LoopDeletion] Break backedge of outermost loops when known not taken

This is a resubmit of dd6bb367 (which was reverted due to stage2 build failures in 7c63aac), with the additional restriction add

[LoopDeletion] Break backedge of outermost loops when known not taken

This is a resubmit of dd6bb367 (which was reverted due to stage2 build failures in 7c63aac), with the additional restriction added to the transform to only consider outer most loops.

As shown in the added test case, ensuring LCSSA is up to date when deleting an inner loop is tricky as we may actually need to remove blocks from any outer loops, thus changing the exit block set. For the moment, just avoid transforming this case. I plan to return to this case in a follow up patch and see if we can do better.

Original commit message follows...

The basic idea is that if SCEV can prove the backedge isn't taken, we can go ahead and get rid of the backedge (and thus the loop) while leaving the rest of the control in place. This nicely handles cases with dispatch between multiple exits and internal side effects.

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

show more ...

[Tests] Precommit tests from to simplify rebase

[LoopDeletion] Break backedge of loops when known not taken

The basic idea is that if SCEV can prove the backedge isn't taken, we can go ahead and get rid of the backedge (and thus the loop) while l

[LoopDeletion] Break backedge of loops when known not taken

The basic idea is that if SCEV can prove the backedge isn't taken, we can go ahead and get rid of the backedge (and thus the loop) while leaving the rest of the control in place. This nicely handles cases with dispatch between multiple exits and internal side effects.

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

show more ...