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

Adds basic support for rotation loops with a switch terminator. This mainly involves making sure that multi edges to the exit block are handled correctly.

This does not yet fix https://bugs.llvm.org/show_bug.cgi?id=44461, because we require that there is only a single edge from the original header into the loop, while that case would require handling the multi edge case. That part is blocked on D72519.

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 ↗(On Diff #237182)

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

llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp
326–327

I'm surprised nobody else has run into this.

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp
684–685

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
326–327

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
266–267

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.EditedNov 19 2020, 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.Nov 19 2020, 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.

FWIW, when applying this patch on a LLVM10-based rustc, the rustc build fails with:

PHI node has multiple entries for the same basic block with different incoming values!
  %35 = phi { i64*, i32 }* [ %83, %77 ], [ %84, %77 ], [ %33, %2 ]
label %77
  %83 = getelementptr { i64*, i32 }, { i64*, i32 }* %35, i64 -1
  %84 = getelementptr { i64*, i32 }, { i64*, i32 }* %35, i64 -1
in function _ZN80_$LT$alloc..vec..Vec$LT$T$GT$$u20$as$u20$alloc..vec..SpecExtend$LT$T$C$I$GT$$GT$9from_iter17h62b0d0798a862a64E
LLVM ERROR: Broken function found, compilation aborted!
error: could not compile `rustc_typeck`.
nikic planned changes to this revision.Jan 23 2021, 2:42 PM

This is currently blocked on D72519.

nikic updated this revision to Diff 321967.Feb 6 2021, 3:21 PM
nikic edited the summary of this revision. (Show Details)

Make this patch independent of D72519, by not handling multi-edges from the header into the loop yet. This means this patch doesn't address my motivating case anymore, but it would be a one line change to support it after D72519.

nikic added inline comments.Feb 6 2021, 3:24 PM
llvm/lib/Transforms/Utils/LoopRotationUtils.cpp
266–267

Unconditional branches will be rejected by the next check (!L->isLoopExiting(OrigHeader)) already, so it's not necessary to explicitly check for them. As this code no longer stores the BranchInst, I found it nicer to omit the check here.