Page MenuHomePhabricator

[LoopDeletion] Break backedge of loops when known not taken
ClosedPublic

Authored by reames on Tue, Dec 29, 10:41 AM.

Details

Summary

This is an extension to LoopDeletion that came up recently in another review discussion (D93734).

The basic idea is that if SCEV can prove the backedge isn't taken, we can go ahead and get rid of the backedge (and thus the loop) while leaving the rest of the control in place. This nicely handles cases with dispatch between multiple exits and internal side effects.

I'd appreciate a careful review of the LoopInfo handling here. I tried to parallel the existing deleteDeadLoop handling, but this code has subtle invariants and stale comments. Definitely room for error.

Diff Detail

Event Timeline

reames created this revision.Tue, Dec 29, 10:41 AM
reames requested review of this revision.Tue, Dec 29, 10:41 AM
Herald added a project: Restricted Project. · View Herald TranscriptTue, Dec 29, 10:41 AM
nikic added a subscriber: nikic.Sun, Jan 3, 11:41 AM

Isn't this already covered by the zero exit count optimization in IndVars?

jdoerfert accepted this revision.Sun, Jan 3, 11:42 AM

LGTM, one nit. I haven't run it but it looks reasonable. Unclear if there is much we can do by staring at it longer.

llvm/lib/Transforms/Utils/LoopUtils.cpp
770

Nit: Add a message to the assert.

This revision is now accepted and ready to land.Sun, Jan 3, 11:42 AM
fhahn added inline comments.Sun, Jan 3, 12:11 PM
llvm/lib/Transforms/Utils/LoopUtils.cpp
780

I realize this is similar to what is done in deleteDeadLoop, but MSSA is only passed so it can be kept up-to-date, right? Can we just pass a pointer to the updater instead (making the intended use more explicit and avoids a dynamic allocation here)

reames added a comment.Sun, Jan 3, 2:47 PM

Isn't this already covered by the zero exit count optimization in IndVars?

No. I believe you're referring to optimizeLoopExits. That does not modify the CFG, it just folds conditions to constants. This will specifically modify the CFG and remove the loop.

llvm/lib/Transforms/Utils/LoopUtils.cpp
780

Not quite sure I follow your request here. I'm happy to address this in a separate cleanup (if you clarify what you're looking for), but I'm going to land as is since the same pattern is already used in existing code.

This revision was landed with ongoing or failed builds.Mon, Jan 4, 9:25 AM
This revision was automatically updated to reflect the committed changes.
nikic added a comment.Mon, Jan 4, 9:32 AM

Isn't this already covered by the zero exit count optimization in IndVars?

No. I believe you're referring to optimizeLoopExits. That does not modify the CFG, it just folds conditions to constants. This will specifically modify the CFG and remove the loop.

Yes, that's the transform I had in mind. I see the difference now, but I'm not sure I understand the larger picture / motivation behind this. The true/false branches will get folded away by SimplifyCFG -- so is this a phase ordering problem where SimplifyCFG runs too late (if so, can we add a PhaseOrdering test)? Should we also try to fold away (to unreachable) dead exits, rather than just dead backedges?

reames added a comment.Mon, Jan 4, 9:37 AM

Isn't this already covered by the zero exit count optimization in IndVars?

No. I believe you're referring to optimizeLoopExits. That does not modify the CFG, it just folds conditions to constants. This will specifically modify the CFG and remove the loop.

Yes, that's the transform I had in mind. I see the difference now, but I'm not sure I understand the larger picture / motivation behind this. The true/false branches will get folded away by SimplifyCFG -- so is this a phase ordering problem where SimplifyCFG runs too late (if so, can we add a PhaseOrdering test)? Should we also try to fold away (to unreachable) dead exits, rather than just dead backedges?

You can view this as a phase ordering issue, but really I see it as "this pass is supposed to delete dead loops" + "a case came up in discussion which we'd missed" + "easy no-cost fix".

The phase ordering is magnified by the fact that SimplifyCFG is not a loop pass and thus requires a DT/LI rebuild. (The in flight DT work for SimplifyCFG looks like it might help there.)

Also, JFYI, deleting dead exits is actually pretty non-trivial (while preserving loop info). See the code in SimplifyLoopCFG which tries. The basic problem is that sibling loops can become unreachable when removing any exit edge.

reames updated this revision to Diff 315675.Sun, Jan 10, 12:56 PM

Context: This patch was reverted following failures in stage2 builders (only). Still investigating root cause. Reproduction is a bit of a pain.

Rebasing over landed test file to simplify my life.

reames reopened this revision.Sun, Jan 10, 12:56 PM
This revision is now accepted and ready to land.Sun, Jan 10, 12:56 PM
reames planned changes to this revision.Sun, Jan 10, 12:56 PM
This revision was not accepted when it landed; it landed in state Changes Planned.Sun, Jan 10, 4:02 PM
This revision was automatically updated to reflect the committed changes.