This is an archive of the discontinued LLVM Phabricator instance.

[IndVars] An implementation of loop predication without a need for speculation
ClosedPublic

Authored by reames on Sep 10 2019, 10:43 AM.

Details

Summary

This patch implements a variation of a well known techniques for JIT compilers - we have an implementation in tree as LoopPredication - but with an interesting twist. This version does not assume the ability to execute a path which wasn't taken in the original program (such as a guard or widenable.condition intrinsic). The benefit is that this works for arbitrary IR from any frontend (including C/C++/Fortran). The tradeoff is that it's restricted to read only loops without implicit exits.

This builds on SCEV, and can thus eliminate the loop varying portion of the any early exit where all exits are understandable by SCEV. A key advantage is that fixing deficiency exposed in SCEV - already found one while writing test cases - will also benefit all of full redundancy elimination (and most other loop transforms).

I haven't seen anything in the literature which quite matches this. Given that, I'm not entirely sure that keeping the name "loop predication" is helpful. Anyone have suggestions for a better name? This is analogous to partial redundancy elimination - since we remove the condition flowing around the backedge - and has some parallels to our existing transforms which try to make conditions invariant in loops.

Factoring wise, I chose to put this in IndVarSimplify since it's a generally applicable to all workloads. I could split this off into it's own pass, but we'd then probably want to add that new pass every place we use IndVars.

One solid argument for splitting it off into it's own pass is that this transform is "too good". It breaks a huge number of existing IndVars test cases as they tend to be simple read only loops. At the moment, I've opted it off by default, but if we add this to IndVars and enable, we'll have to update around 20 test files to add side effects or disable this transform.

Diff Detail

Repository
rL LLVM

Event Timeline

reames created this revision.Sep 10 2019, 10:43 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 10 2019, 10:43 AM
reames planned changes to this revision.Sep 11 2019, 8:48 AM

I somehow uploaded the wrong patch. Ignored until I can fix.

reames updated this revision to Diff 219725.Sep 11 2019, 8:49 AM

Correct patch this time...

I haven't seen anything in the literature which quite matches this. Given that, I'm not entirely sure that keeping the name "loop predication" is helpful. Anyone have suggestions for a better name? This is analogous to partial redundancy elimination - since we remove the condition flowing around the backedge - and has some parallels to our existing transforms which try to make conditions invariant in loops.

Maybe this is because I don't have context on previous work related to LoopPredication but it sounds not quite what the transformation is doing. At least it doesn't generate any explicit predicate for the loop. I don't have anything better to suggest at this time though.

lib/Transforms/Scalar/IndVarSimplify.cpp
2750 ↗(On Diff #219725)

I can't find a place where this prerequisite is actually checked. Am I just missing it?

2758 ↗(On Diff #219725)

Returning at this point means no other code (other than loop predication) can be added bellow this point in future. I think we better structure it in a more independent way. Taking into account this function becomes pretty large I would suggest factoring out new code to a separate function?

2769 ↗(On Diff #219725)

Looks like many steps in this filter are common with the existing code above. I think it make sense to unify these two pieces. Ideally ExitingBB better be const to prevent unintended influence but not sure this is doable with out a copy.

2827 ↗(On Diff #219725)

No need to call mayThrow explicitly since mayHaveSideEffects covers this.

2835 ↗(On Diff #219725)

The first sentence sounds a little odd to me. Would you mind rephrasing it.

2837 ↗(On Diff #219725)

Could you clarify this sentence for me. Did not catch.

reames marked 5 inline comments as done.Sep 12 2019, 11:34 AM
reames added inline comments.
lib/Transforms/Scalar/IndVarSimplify.cpp
2750 ↗(On Diff #219725)

The code is assuming lcssa, so the lack of phis in the exist block is what you're looking for.

2758 ↗(On Diff #219725)

I'm completely fine factoring this out into it's own function, but let's hold off until we decide on pass placement and algorithmic questions.

2769 ↗(On Diff #219725)

While there are commonalities, there are enough differences that combining the two is going to end up being extremely confusing. I'd be willing to play around with code structure to see if this works better than I think it would, but I'd like to land and then refactor in that direction if it's okay.

2835 ↗(On Diff #219725)

The comment is also stale. I will simply remove it.

2837 ↗(On Diff #219725)

Again, stale.

I was originally inserting comparisons at the branch under the logic that the exit count might not be invariant. I then realized that was non-sensical when I couldn't construct a test for it, and moved to the bail out scheme now in the code. I forgot to remove the comment.

ebrevnov added inline comments.Sep 13 2019, 3:37 AM
lib/Transforms/Scalar/IndVarSimplify.cpp
2750 ↗(On Diff #219725)

Got it. Thanks!

2816 ↗(On Diff #219725)

consistents->consists or constituents?

2824 ↗(On Diff #219725)

Did you consider adding support for llvm.experimental.widenable.condition in this or one of the next patches? My understanding is semantics of llvm.experimental.widenable.condition allows us to assume that exist is taken on the first hit thus we can ignore side effects and live outs coming from the code dominated by the intrinsic.

test/Transforms/IndVarSimplify/loop-predication.ll
714 ↗(On Diff #219725)

Any plan to support that soon?

reames marked 2 inline comments as done.Sep 13 2019, 9:06 AM
reames added inline comments.
lib/Transforms/Scalar/IndVarSimplify.cpp
2824 ↗(On Diff #219725)

WC is a planned follow up. It's a little tricky because the way we structure the WC comparisons currently breaks getExitCount and getBackedgeTakenCount. I definitely want this landed and tested before I start making any of the tweaks for WC.

test/Transforms/IndVarSimplify/loop-predication.ll
714 ↗(On Diff #219725)

At some point. If it's a case which bites someone, I'll prioritize it.

apilipenko accepted this revision.Sep 25 2019, 5:13 PM

LGTM.

It looks like you successfully avoid the pitfall the original original loop predication fell into by filtering implicit exits and using trip counts. It makes me think that we can revisit loop predication again and go back to SCEV based implementation.

lib/Transforms/Scalar/IndVarSimplify.cpp
2763 ↗(On Diff #219725)

It looks like you need to check hasLoopInvariantBackedgeTakenCount first. Excerpt from getBackedgeTakenCount description:

/// Note that it is not valid to call this method on a loop without a
/// loop-invariant backedge-taken count (see
/// hasLoopInvariantBackedgeTakenCount).
2770 ↗(On Diff #219725)

Typo. exitting - exiting

2770–2772 ↗(On Diff #219725)

I don't think I quite follow this comment. Can you please elaborate? Is there a test demonstrating the problem?

2856 ↗(On Diff #219725)

What is the situation when they have different types?

This revision is now accepted and ready to land.Sep 25 2019, 5:13 PM
This revision was automatically updated to reflect the committed changes.
reames marked 2 inline comments as done.