This is an archive of the discontinued LLVM Phabricator instance.

[unroll] Prune all but first copy of invariant exit
AbandonedPublic

Authored by reames on Jan 2 2022, 9:39 AM.

Details

Summary

If we have an exit which is controlled by a loop invariant condition and which dominates the latch, we know only the copy in the first unrolled iteration can be taken. All other copies are dead.

The change itself is pretty straight forward, but let me add two points of context:

  • I'd have expected other transform passes to catch this after unrolling, but I'm seeing multiple examples where we get to the end of O2/O3 without simplifying.
  • I'd like to do a stronger change which did CSE during unroll and accounted for invariant expressions (as defined by SCEV instead of trivial ones from LoopInfo), but that doesn't fit cleanly into the current code structure.

Diff Detail

Event Timeline

reames created this revision.Jan 2 2022, 9:39 AM
reames requested review of this revision.Jan 2 2022, 9:39 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 2 2022, 9:39 AM
nikic added a reviewer: nikic.Jan 2 2022, 9:47 AM
nikic added a subscriber: nikic.

This generally makes sense to me, but I think you need to adjust some of the tests to make the condition non-invariant, because I doubt that this is what they were intending to test. Replace an argument with a call return value.

This generally makes sense to me, but I think you need to adjust some of the tests to make the condition non-invariant, because I doubt that this is what they were intending to test. Replace an argument with a call return value.

Did you have any particular tests in mind? I skimmed the tests and don't see any where the change obviously breaks intent of the test author.

nikic added a comment.Jan 2 2022, 12:54 PM

This generally makes sense to me, but I think you need to adjust some of the tests to make the condition non-invariant, because I doubt that this is what they were intending to test. Replace an argument with a call return value.

Did you have any particular tests in mind? I skimmed the tests and don't see any where the change obviously breaks intent of the test author.

Always hard to say, but pr31718.ll is apparently a test for LCSSA and simplification interaction, which might not be representative if some of the exits (with LCSSA phi nodes) are dropped. I don't know what specifically runtime-loop-multiexit-dom-verify.ll is testing, but the relevant domtree pattern might not be present with some of the edges gone.

nikic accepted this revision.Jan 3 2022, 1:11 AM

LG apart from the previous note on tests. I think unrolling is an area where it is worthwhile to do cleanup as part of the transform (as long as it remains simple), because we may be producing a large amount of code, and this reduces the amount of work follow-on transforms have to do. Additionally, it is worth noting that runtime unrolling is performed very late in the pipeline, and we generally cannot expect any non-trivial redundancies exposed by that to be optimized away.

This revision is now accepted and ready to land.Jan 3 2022, 1:11 AM
This revision was landed with ongoing or failed builds.Jan 3 2022, 9:59 AM
This revision was automatically updated to reflect the committed changes.
reames reopened this revision.Jan 3 2022, 12:20 PM

Reverted due to bot failure investigation.

This revision is now accepted and ready to land.Jan 3 2022, 12:20 PM
reames added a comment.Jan 3 2022, 5:28 PM

Pretty sure I know the cause of the issue, though I haven't yet managed to reproduce it.

If we runtime unroll a loop with a invariant condition as the latch exit condition, this patch combined with the existing code will cause all copies of the latch in the main loop to be folded to untaken. This is correct - the main loop is dynamically dead whether we use prolog or epilogue - but can result in exits becoming unreachable when unrolling the main loop. (And thus loop info being in potentially bad state.)

I have not yet been able to actually get the runtime unroll code to unroll such a loop. I'll try a bit further tomorrow, but if I can't come up with a reproducer, I plan to recommit with a bailout for runtime unrolling and see if any other failures come up.

lebedev.ri resigned from this revision.Jan 12 2023, 5:43 PM

This review seems to be stuck/dead, consider abandoning if no longer relevant.

Herald added a project: Restricted Project. · View Herald TranscriptJan 12 2023, 5:43 PM
Herald added a subscriber: StephenFan. · View Herald Transcript
reames abandoned this revision.Sun, Nov 26, 11:51 AM

Closing stale phabricator review. No longer actively working on this, if someone wants to pick it up, feel free.