Page MenuHomePhabricator

[LoopRotate] Add support for rotating loops with switch exit
Needs ReviewPublic

Authored by nikic on Jan 8 2020, 3:01 PM.

Details

Summary

Fixes https://bugs.llvm.org/show_bug.cgi?id=44461 by supporting loop rotations for loops where the header terminator is a switch rather than a branch. This mainly involves making sure that "multi edges" are handled correctly.

This is currently restricted to the case where there is a unique successor in the loop (a requirement of the transform) and a unique exit target (an artificial limitation to keep things closer to how things were). Unlike with branches, there can be multiple edges to each of those blocks though.

Diff Detail

Event Timeline

nikic created this revision.Jan 8 2020, 3:01 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 8 2020, 3:01 PM
nikic updated this revision to Diff 237182.Jan 9 2020, 1:19 PM

Add tests

nikic edited the summary of this revision. (Show Details)Jan 9 2020, 1:30 PM
nikic added reviewers: efriedma, reames, asbirlea.
nikic set the repository for this revision to rG LLVM Github Monorepo.
efriedma added inline comments.Jan 9 2020, 5:58 PM
llvm/include/llvm/Analysis/LoopInfoImpl.h
215

Move the new check out to avoid the extra contains() call?

llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp
283–284

I'm surprised nobody else has run into this.

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp
489

This is going to cause non-deterministic code generation.

nikic updated this revision to Diff 237358.Jan 10 2020, 9:15 AM

Extract condition. Use SetVector to avoid non-determinism.

nikic marked 3 inline comments as done.Jan 10 2020, 9:23 AM
nikic added inline comments.
llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp
283–284

Probably this is the first time PreserveLCSSA + MergeIdenticalEdges are used together.

Thank you, this looks like a great missed optimization.

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp
222

I'm missing why not keep the check&exit if Term is a branch and it's unconditional.

alex added a subscriber: alex.Mar 26 2020, 2:01 PM
G2P added a subscriber: G2P.Apr 10 2020, 11:24 AM
Gankra added a subscriber: Gankra.EditedThu, Nov 19, 8:29 AM

@nikic Is this patch still something that can/should be rebased and landed? (Investigating whether it can fix some issues we're seeing in Firefox related to Rust upgrading to llvm 10)

nikic added a comment.Thu, Nov 19, 9:29 AM

I'm not sure. It might make more sense to make SimplifyCFG be less aggressive about forming switches in this case. Pretty sure that converting if (a == C || B == C2) into a switch is pretty much a strict regression in optimization power, because a lot more passes support branches than switches.