Page MenuHomePhabricator

[PassManager] Run Induction Variable Simplification pass *after* Recognize loop idioms pass, not before
ClosedPublic

Authored by lebedev.ri on Nov 19 2020, 8:48 AM.

Details

Summary

Currently, -indvars runs first, and then immediately after -loop-idiom does.
I'm not really sure if -loop-idiom requires -indvars to run beforehand,
but i'm *very* sure that -indvars requires -loop-idiom to run afterwards,
as it can be seen in the phase-ordering test.

LoopIdiom runs on two types of loops: countable ones, and uncountable ones.
For uncountable ones, IndVars obviously didn't make any change to them,
since they are uncountable, so for them the order should be irrelevant.
For countable ones, well, they should have been countable before IndVars
for IndVars to make any change to them, and since SCEV is used on them,
it shouldn't matter if IndVars have already canonicalized them.
So i don't really see why we'd want the current ordering.

While this is quite likely beneficial in-the-wild already,
it's a required part for the full motivational pattern
behind left-shift-until-bittest loop idiom (D91038).

Diff Detail

Event Timeline

lebedev.ri created this revision.Nov 19 2020, 8:48 AM
lebedev.ri requested review of this revision.Nov 19 2020, 8:48 AM
lebedev.ri retitled this revision from [PassManager] Run nduction Variable Simplification pass *after* Recognize loop idioms pass, not before to [PassManager] Run Induction Variable Simplification pass *after* Recognize loop idioms pass, not before.
lebedev.ri edited the summary of this revision. (Show Details)Nov 19 2020, 9:01 AM

Fix one more pipeline structure test.

(adding some more people potentially-relevant people)

TBN i'm personally not *very* sure whether or not loop-idiom benefits from being run after indvars.
If it does, we either need to run indvars twice i guess?

Do we have phase ordering tests for various memset/memcpy loops?

I have certainly seen places where we have managed to recognize a loop as a memcpy/memset, but not remove the remaining now empty loop. Here is some more fuel for your fire if you need it: https://godbolt.org/z/eW4rsY

Do we have phase ordering tests for various memset/memcpy loops?

We clearly do not.

I have certainly seen places where we have managed to recognize a loop as a memcpy/memset, but not remove the remaining now empty loop. Here is some more fuel for your fire if you need it: https://godbolt.org/z/eW4rsY

The change looks very reasonable, though I don't know what motivation was behind the current ordering. There might have been some (arcane) reasons behind it. Fine by me, but please have someone else to take a look.

lebedev.ri edited the summary of this revision. (Show Details)
lebedev.ri added a reviewer: echristo.

I have certainly seen places where we have managed to recognize a loop as a memcpy/memset, but not remove the remaining now empty loop. Here is some more fuel for your fire if you need it: https://godbolt.org/z/eW4rsY

Thank you for the yet another motivational example, test added!

The change looks very reasonable, though I don't know what motivation was behind the current ordering. There might have been some (arcane) reasons behind it. Fine by me, but please have someone else to take a look.

Yep. LoopIdiom runs on two types of loops: countable ones, and uncountable ones.
For uncountable ones, IndVars obviously didn't make any change to them, since they are uncountable, so for them the order should be irrelevant.
For countable ones, well, they should have been countable before IndVars for IndVars to make any change to them,
and since SCEV is used on them, it shouldn't matter if IndVars have already canonicalized them.
So i don't really see why we'd want the current ordering.

With that, does anyone feel confident accepting? :)

dmgreen accepted this revision.Nov 25 2020, 8:08 AM

I ran some more benchmarks, and they look good. Lets give this a try and if someone finds an issue we can always adjust it.

LGTM

This revision is now accepted and ready to land.Nov 25 2020, 8:08 AM

I ran some more benchmarks, and they look good. Lets give this a try and if someone finds an issue we can always adjust it.

LGTM

Thank you.
I'm going to land this now; should this regress some things, we can indeed revert this.

This revision was landed with ongoing or failed builds.Nov 25 2020, 8:20 AM
This revision was automatically updated to reflect the committed changes.