This is an archive of the discontinued LLVM Phabricator instance.

[LoopUnswitch] Improve loop unswitch pass to find trivial unswitch conditions more effectively
ClosedPublic

Authored by chenli on Jul 23 2015, 4:29 PM.

Details

Summary

This patch improves trivial loop unswitch.

The current trivial loop unswitch only checks if loop header's terminator contains a trivial unswitch condition. But if the loop header only has one reachable successor (due to intentionally or unintentionally missed code simplification), we should consider the successor as part of the loop header. Therefore, instead of stopping at loop header's terminator, we should keep traversing its successors within loop until reach a *real* conditional branch or switch (whose condition can not be constant folded). This change will enable a single -loop-unswitch pass to unswitch multiple trivial conditions (unswitch one trivial condition could open opportunity to unswitch another one in the same loop), while the old implementation can unswitch only one per pass.

Diff Detail

Event Timeline

chenli updated this revision to Diff 30537.Jul 23 2015, 4:29 PM
chenli retitled this revision from to [LoopUnswitch] Improve loop unswitch pass to find trivial unswitch conditions more effectively.
chenli updated this object.
chenli added reviewers: reames, broune.
chenli added a subscriber: llvm-commits.
broune added inline comments.Jul 23 2015, 5:55 PM
lib/Transforms/Scalar/LoopUnswitch.cpp
784

It's not necessarily possible to combine the header with its successor even if it is an unconditional branch, since there might be other predecessors of the successor. It might also be good to point out that unswitching generates branches with constant conditions, so this is expected and not just some corner case.

791

Set can make an allocation per insertion, which is slow. I'd consider SmallSet instead.

http://llvm.org/docs/ProgrammersManual.html#set-like-containers-std-set-smallset-setvector-etc

817

space missing after the colon.

819

This loop is duplicated from outside the loop. Would it make sense to move this loop to the top to to avoid the duplication? It would require a slightly different loop condition. The insert into Visited could also be de-duplicated.

chenli added inline comments.Jul 23 2015, 9:28 PM
lib/Transforms/Scalar/LoopUnswitch.cpp
784

Well, I think you can always combine them with some kind of successor duplications if it has multiple predecessors. But it will add too much complexity and it's not worth taking that approach :)

I will add you second comment in code.

791

Will do.

817

Will do.

819

Will do.

chenli marked 3 inline comments as done.

Update patch w.r.t broune's comments.

chenli marked an inline comment as done.Jul 23 2015, 10:42 PM
broune added inline comments.Jul 24 2015, 11:12 AM
lib/Transforms/Scalar/LoopUnswitch.cpp
749

This comment is correct if we consider the header to extend across several basic blocks, as you do later on in a comment. I suspect that that's not a standard definition of the loop header (correct me if I'm wrong?), making this comment tricky to understand correctly. I think it would be clearer to explain this in terms of the first non-constant branch in the loop. Then probably the "Header" variable should be renamed to something else, like BB. Though this is subjective, so if you prefer the current way, I'll LGTM that.

761

until find -> until it finds

789

This wording suggests that the header is changed in some way, though that's not the case. I'm not sure you need a comment here, but if you keep it, maybe word it as something like "For this function, we consider the header to extend to its successor if ..." and add a full stop at the end.

797

Find -> Found. Add full stop at the end.

801

Nit: This is not necessarily a switch. I think it would be OK without a comment here.

805

Nit: HeaderTerm is set twice and only used twice. I would use Header->getTerminator() directly for the two uses instead, as then there's one variable less to keep track of.

chenli added inline comments.Jul 24 2015, 11:32 AM
lib/Transforms/Scalar/LoopUnswitch.cpp
749

Thanks for the suggestion. I should have made the comments consistent with each other. I will revise this :)

chenli added inline comments.Jul 24 2015, 11:44 AM
lib/Transforms/Scalar/LoopUnswitch.cpp
805

There are a few uses in the later code as well. I would prefer to keep the variable.

broune added inline comments.Jul 24 2015, 11:55 AM
lib/Transforms/Scalar/LoopUnswitch.cpp
805

You're right, I thought the function ended before it actually does.

chenli marked 6 inline comments as done.

Update patch w.r.t broune's comments.

broune accepted this revision.Jul 24 2015, 12:29 PM
broune edited edge metadata.

LGTM.

lib/Transforms/Scalar/LoopUnswitch.cpp
744

Nit: This is correct in the sense of "starting from", but could also be read as "from within". I'd use "starting from" to clarify it.

760

Nit: Now that you are not specifying that this function only looks in the loop header, there is no need to justify looking at successors by saying that they could be seen as part of the loop header.

This revision is now accepted and ready to land.Jul 24 2015, 12:29 PM
chenli marked 2 inline comments as done.Jul 24 2015, 7:44 PM
chenli closed this revision.Jul 24 2015, 8:21 PM