[LSR] Fold terminating condition to other IV when possible

[eopXD]

Summary

When the IV is only used by the terminating condition (say IV-A) and the loop
has a predictable back-edge count and we have another IV (say IV-B) that is an
affine add recursion, we will be able to calculate the terminating value of
IV-B in the loop pre-header. This patch adds attempts to replace IV-B as the
new terminating condition and remove IV-A. It is safe to do so since IV-A is
only used as the terminating condition.

This transformation is suitable to be appended after LSR as it may optimize the
loop into the situation mentioned above. The transformation can reduce number of
IV-s in the loop by one.

A cli option lsr-term-fold is added and default disabled.

[craig.topper]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6697

Combine this with the previous if

[eopXD]

Address comments from @craig.topper.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

189

Replaced all use of "terminal condition" to "terminating condition".

191–193

Thank you for the simplification. Was trying to explain in detail but this is much better.

6579

Thank you for the tip, done.

6611

Done.

6667

This simplifies the code very much. Thank you for the tip.

6697

Done. Thank you.

6785

Yes, thank you.

6786

The problem is elegantly solved by using PHINode:: getIncomingValueForBlock you've mentioned.

[craig.topper]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

189

The option name still says Terminal

Review needs to re-titled and the description needs to be updated

[craig.topper]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6604

neq -> ne

[craig.topper]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6634

Is PN.getNumIncomingValues() == 2 implied by LoopSimplifyForm?

6661

Is PN.getNumIncomingValues() == 2 implied by LoopSimplifyForm?

6668

Are the LoopPreheader and LoopLatch being predecessors of the phi implied by LoopSimplify form?

[eopXD]

Address review comments.

[eopXD]

By definition of LoopSimplifyForm (contains exactly 1 preheader, exactly 1 latch, and has dedicated exit), the code can be simplified.
Thank you @craig.topper for the review.

[eopXD]

Rebased upon change in D132443.

[eopXD]

Rename testcase.

[fhahn]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6609

Looks like a negative test with different branch conditions is missing.

6670

it looks like there's a negative test missing with types that aren't scev-able (e.g. vector types I think).

6675

It looks like there's a test case missing where one of the phis isn't an AddRec/non-affine AddRec.

[nikic]

Could you please update the patch description to describe in more detailed what this patch does?

[eopXD]

Added missing negative testcases.

[eopXD]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6670

Done, thank you for the reminder.

6675

Done, thank you for the reminder.

[eopXD]

Fix type-o.

[eopXD]

Some statistics to help push the patch, here are the number of loops affected when compiling spec2k6 with downstream compiler and this patch applied:

400.perlbench 56
401.bzip2 6
403.gcc 155
429.mcf 1
445.gobmk 45
456.hmmer 44
458.sjeng 9
462.libquantum 4
464.h264ref 125
471.omnetpp 7
473.astar 14
483.xalancbmk 81

[eopXD]

Add counter to record number of folding done.

[eopXD]

Gentle ping, thank you. @fhahn @craig.topper

Is the description acceptable now? @nikic

[eopXD]

ping, thank you.

[craig.topper]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6579

Looking at this again. Could this be an Optional<std::pair<PHINode *, PHINode *>> Then you could return None for CantFold.

[craig.topper]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6840

What are the other users of OldTermCond and why is it ok to replace them with poison?

6845

Is there a DCE after this? Earlier optimizations in this function used DeleteDeadPHIs to recursively clean up.

[eopXD]

Address comment.

[eopXD]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6579

Modified, thank you for the tip.

[eopXD]

Address comment.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6840

Nice catch. Added check and negative test for it.

6845

Yes. Removing the terminal condition and leveraging DeleteDeadPHIs is a much better approach. Thank you.

[craig.topper]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6840

What if OldTermCond isn't the direct user of the ToFold phi? Do we clean everything?

[eopXD]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

6840

Yes, DeleteDeadPHIs is able to delete the chain of uses of the ToFold phi.

[eopXD]

Fix testcase.

[craig.topper]

LGTM

[eopXD]

Rebase to latest main.

[eopXD]

Rebase to latest main.

[reames]

I recently stumbled into a test case which would benefit from this, and as a result, took a close look at the code in tree.

I posted one generalization https://reviews.llvm.org/D142240 so that this covers my case of interest.

However, I also think we've got a couple of correctness issues here which need addressed.

First, I don't see anything in the code which checks that the alternate IV is at least as wide as the starting IV. As a result, we can try to rewrite a loop with a BE count of say 1024 to use an IV which is an i8. This can change the BE count of the loop.

Second, we're adding a use to an existing IV. When doing that, we need to worry about about poison correctness. The case to consider is the alternate IV overflowing on the last iteration, and that poison value previously being unused (since we don't take backedge), and now used in the latch test (resulting in UB).

[reames]

(More observations)

For example of code which gets both of the above issues correct, look at the LFTR and rewriteLoopExitValues transformations.

Third, we need some form of cost model. The simplest would be to add a isHighCostExpansion check on the new bound. SCEV expressions can (in edge cases) be quite involved, and we probably don't want to do this rewrite universally.