This is an archive of the discontinued LLVM Phabricator instance.

[SelectOpti][5/5] Optimize select-to-branch transformation
ClosedPublic

Authored by apostolakis on Feb 20 2022, 10:54 PM.

Details

Summary

This patch optimizes the transformation of selects to a branch when the heuristics deemed it profitable.
It aggressively sinks eligible instructions to the newly created true/false blocks to prevent their
execution on the common path and interleaves dependence slices to maximize ILP.

Depends on D120232

Diff Detail

Event Timeline

apostolakis created this revision.Feb 20 2022, 10:54 PM
apostolakis published this revision for review.Feb 23 2022, 10:14 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 23 2022, 10:14 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 6 2022, 10:05 PM
Herald added a subscriber: pengfei. · View Herald Transcript
bsmith added a subscriber: bsmith.Mar 21 2022, 7:59 AM

Rebase and adjust tests

apostolakis retitled this revision from [SelectOpti][4/4] Select-to-branch transformation to [SelectOpti][5/5] Optimize select-to-branch transformation.Mar 22 2022, 2:49 PM
apostolakis edited the summary of this revision. (Show Details)
modimo added a subscriber: modimo.Mar 23 2022, 2:44 PM

Use opt tests instead of llc ones

lkail added a subscriber: lkail.Mar 23 2022, 11:50 PM
davidxl added inline comments.May 10 2022, 12:09 PM
llvm/lib/CodeGen/SelectOptimize.cpp
313

Is it better to assert that TrueSlices and FalseSlices are not *both* empty? If that is that case, the transformation may be hurtful.

llvm/test/CodeGen/X86/select-optimize.ll
152 ↗(On Diff #427116)

It is better to add a test case showing sinking for SI group with more than one selects.

apostolakis added inline comments.May 10 2022, 7:39 PM
llvm/lib/CodeGen/SelectOptimize.cpp
313

Sinking is an added optimization on top of the benefit of breaking data dependences.
Even without any sinking, there are many cases where the transformation is still profitable.

For example, consider two dependence chains that include a load.
critical path: .... -> load -> select -> .....
non-critical path \> store
The first one is a long chain and it is the critical path while the second one is a much shorter one.
The load cannot be sunk if the select is converted to a branch since it is used by another instruction (in the other path), but the conversion to a branch breaks a data dependence that reduces the critical path and thus it is still profitable.

llvm/test/CodeGen/X86/select-optimize.ll
152 ↗(On Diff #427116)

Modified an existing test case with a two-select SI group to include sinking (and an instruction that shouldn't be sunk).

Add select-group sinking testing

davidxl added inline comments.May 10 2022, 8:33 PM
llvm/lib/CodeGen/SelectOptimize.cpp
313

Ok. I see that cost analysis already considers the 'sinkability' of the select operands in cost analysis.

620

Should 'ForSinking' be removed? The cost analysis and the actual sinking should be in sync.

apostolakis added inline comments.May 11 2022, 8:56 AM
llvm/lib/CodeGen/SelectOptimize.cpp
620

I think 'ForSinking' should remain. There are instructions that we don't want to sink but could be expensive and add to a dependence chain that might render a conditional move too expensive. For example, a call instruction that might have side effects cannot be sunk, but converting the select to a branch could allow us to avoid blocking on the execution of this call instruction (even if it is on the common path and is scheduled for execution). Thus, it is better to consider the call instruction in the cost analysis.

Additionally, it just happens that one heuristic (base heuristic looking for expensive instructions) shares code with the sinking optimization. Other heuristics (e.g., loop-level, predictable branches) have different cost analyses. If a conversion is deemed profitable we always use the same sinking transformation logic regardless of the used heuristic.

davidxl accepted this revision.May 12 2022, 9:34 AM

lgtm

This revision is now accepted and ready to land.May 12 2022, 9:34 AM
This revision was landed with ongoing or failed builds.May 23 2022, 8:34 PM
This revision was automatically updated to reflect the committed changes.
thakis added a subscriber: thakis.May 23 2022, 8:41 PM

This breaks building on windows: http://45.33.8.238/win/58678/step_4.txt

Please take a look and revert for now if it takes a while to fix.