This is an archive of the discontinued LLVM Phabricator instance.

[IndVars] Eliminate loop exits with equivalent exit counts
ClosedPublic

Authored by reames on Oct 15 2019, 2:56 PM.

Details

Summary

We can end up with two loop exits whose exit counts are equivalent, but whose textual representation is different and non-obvious. For the sub-case where we have a series of exits which dominate one another (common), eliminate any exits which would iterate *after* a previous exit on the exiting iteration.

As noted in the TODO being removed, I'd always thought this was a good idea, but I've now seen this in a real workload as well. This needs to be rebased on D68956 as both need the same dominance order check.

Diff Detail

Event Timeline

reames created this revision.Oct 15 2019, 2:56 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 15 2019, 2:56 PM
ebrevnov added inline comments.Oct 16 2019, 1:05 AM
lib/Transforms/Scalar/IndVarSimplify.cpp
2758 ↗(On Diff #225121)

That would be a fourth loop filtering out "bad" exits before actual work. And the method becomes pretty long. I think we need to refactor in this or consequent patch.

2793 ↗(On Diff #225121)

Two notes here. 1) Any reason not to use isKnownViaNonRecursiveReasoning or isKnownPredicate? 2) We can actually eliminate an exit if its exit count not less than exit count of one of its predecessors.

None of these is blocking the current patch though.

reames updated this revision to Diff 225465.Oct 17 2019, 10:42 AM

Rebase over landed loop pred change, and some refactoring to address a few concerns brought up in the review.

reames marked 2 inline comments as done.Oct 17 2019, 10:45 AM
reames added inline comments.
lib/Transforms/Scalar/IndVarSimplify.cpp
2758 ↗(On Diff #225121)

What do you think of the committed NFC reorgs? If you have suggestions, I'm happy to further tweak.

2793 ↗(On Diff #225121)
  1. I believe you're referring not to the EQ case, but to the provably greater then case just above right?
  1. I could generalize, but I don't have an example which illustrates the difference. SCEV tries to canonicalize at construction (as demonstrated by some of the test changes). If you don't mind, I'd like to wait until we have a motivating example before using a more expensive API.
nikic added inline comments.Oct 17 2019, 12:06 PM
lib/Transforms/Scalar/IndVarSimplify.cpp
2804 ↗(On Diff #225465)

This code is already repeated three times now, extract?

reames marked an inline comment as done.Oct 17 2019, 3:00 PM
reames added inline comments.
lib/Transforms/Scalar/IndVarSimplify.cpp
2804 ↗(On Diff #225465)

Not quite. We're folding the branch either to taken or untaken, but yes, it could be factored out. Will do, and rebase.

reames updated this revision to Diff 225548.Oct 17 2019, 4:51 PM

Rebase on requested refactor.

nikic added inline comments.Oct 18 2019, 11:44 AM
lib/Transforms/Scalar/IndVarSimplify.cpp
2796 ↗(On Diff #225548)

Now that we're traversing the exits in dominating order, I think we should consider a slightly different overall approach:

Instead of computing umin({ exit counts }) upfront and then checking for umin({ exit counts }) < this exit count, we can instead build this up incrementally, i.e. take the umin between the current max exit count and the exit count of the currently considered exit at each iteration. This will allow us to check for umin({ already seen exit counts }) <= this exit count (note the <=!) instead.

This should implicitly handle the case of exact equalities, but may also be more powerful in general because we're checking for a weaker predicate.

reames marked an inline comment as done.Oct 19 2019, 10:03 AM
reames added inline comments.
lib/Transforms/Scalar/IndVarSimplify.cpp
2796 ↗(On Diff #225548)

The suggested approach doesn't handle one of the most common cases. If the latch exit is in fact the minimum exit, we want to be able to discharge earlier exits. (i.e. the difference between the dominating set and the total sets is important)

I do agree that your phrasing *might* be more powerful for eliminating exits which SCEV can prove are <= dominating checks (but not either < or ==). However, I don't have a test case which demonstrates that difference, and until I do, I'd like to avoid further complicating the code. (Assuming I'd need both approaches due to the gap described above.)

nikic added inline comments.Oct 19 2019, 1:28 PM
lib/Transforms/Scalar/IndVarSimplify.cpp
2796 ↗(On Diff #225548)

For an example, consider the existing @ult test just using a ule predicate instead: https://godbolt.org/z/j-rZeb This should eliminate the second exit, but doesn't, as we have neither the < predicate nor the strict scev identity (but do have a <= predicate).

I didn't quite follow what you mean regarding the latch exit and why it is special. Is there a test case that shows the issue?

nikic accepted this revision.Oct 19 2019, 2:54 PM

LG

lib/Transforms/Scalar/IndVarSimplify.cpp
2796 ↗(On Diff #225548)

Okay, I see what you mean now. Not specifically the latch, just any future exit. It does seem like we'd have to combine both approaches to get the full coverage, so let's go with your current variant for now.

This revision is now accepted and ready to land.Oct 19 2019, 2:54 PM
This revision was automatically updated to reflect the committed changes.