Page MenuHomePhabricator

[SimplifyCFG] propagate branch metadata when creating select
ClosedPublic

Authored by spatel on Apr 28 2016, 11:00 AM.

Diff Detail

Repository
rL LLVM

Event Timeline

spatel updated this revision to Diff 55444.Apr 28 2016, 11:00 AM
spatel retitled this revision from to [SimplifyCFG] propagate branch metadata when creating select.
spatel updated this object.
spatel added reviewers: davidxl, hfinkel, bkramer.
spatel added a subscriber: llvm-commits.
davidxl edited edge metadata.Apr 29 2016, 12:28 PM

looks fine, but can you write another more direct test case for better checking if the profile update is correct or not.

spatel updated this revision to Diff 55690.Apr 29 2016, 5:22 PM
spatel edited edge metadata.

Patch updated:
Minimize test case to show that existing metadata on a select isn't changed and the missing weights fixed by this patch are correct.

davidxl added inline comments.Apr 29 2016, 8:31 PM
test/Transforms/SimplifyCFG/preserve-branchweights.ll
422 ↗(On Diff #55690)

If I read the code correctly, should the weights for select be 9:5 ? !11 does not look correct.

423 ↗(On Diff #55690)

This one is correct.

spatel added inline comments.Apr 29 2016, 8:53 PM
test/Transforms/SimplifyCFG/preserve-branchweights.ll
422 ↗(On Diff #55690)

I thought the weights for the select would be equal to the weights of the original branch because they have the same comparison condition (%cmpb), 3:5. How do you calculate 9:5?

davidxl added inline comments.Apr 29 2016, 9:01 PM
test/Transforms/SimplifyCFG/preserve-branchweights.ll
422 ↗(On Diff #55690)

Should it be 3 : 5 * (1/3) which 9 : 5? When block 2 is entered, there is only 1/3 probability it reaches block3.

spatel added inline comments.May 1 2016, 7:47 AM
test/Transforms/SimplifyCFG/preserve-branchweights.ll
422 ↗(On Diff #55690)

Aha - yes. Although it's the same comparison operand, we have changed the program structure - we are speculatively executing the select, so the original branch weights no longer apply.

This brings up my question from the original summary then - do you know if there's a reason not to use the BranchProbability class for calculating the new weights?

davidxl added inline comments.May 1 2016, 11:23 PM
test/Transforms/SimplifyCFG/preserve-branchweights.ll
422 ↗(On Diff #55690)

BPI provides general APIs to access/read branch probability information that is either from profile data, or from static branch prediction.

Here the transformation just needs to update the profile data, using low level meta data interfaces is fine (Besides BPI does not have complete update APIs either).

spatel updated this revision to Diff 56069.May 3 2016, 3:14 PM

Patch updated:
The branch weights of the first select are recalculated based on the new program structure.

davidxl accepted this revision.May 3 2016, 10:20 PM
davidxl edited edge metadata.

lgtm

lib/Transforms/Utils/SimplifyCFG.cpp
2882 ↗(On Diff #56069)

The select is newly created instruction that does not exist before -- it sits at the same BB where the original phi, so it is not 'speculatively' executed.

The original PBI's branch weights do not apply because the select's 'logical' edges are incoming edges of the phi that is eliminated, not the out edges of PBI.

This revision is now accepted and ready to land.May 3 2016, 10:20 PM
This revision was automatically updated to reflect the committed changes.
spatel added a comment.May 4 2016, 1:56 PM

Thanks, David. I think that was the last of the branch --> select branch_weights drops in SimplifyCFG.
Still need to look at switch --> select and other transforms.

I am going to revert.

Reverted in r268577

spatel added a comment.May 4 2016, 7:32 PM

Reverted in r268577

Thanks, Vitaly. I'll try to get this debugged tomorrow.

spatel added a comment.May 5 2016, 3:40 PM

Reverted in r268577

Thanks, Vitaly. I'll try to get this debugged tomorrow.

I've tried to reproduce the error using sanitized builds of opt/llc as well as running under valgrind, but I don't see it. How do I find the exact steps used by the bot to induce the bug?