This is an archive of the discontinued LLVM Phabricator instance.

[JumpThreading] Propagate branch hint metadata in more cases
Needs ReviewPublic

Authored by inouehrs on Apr 3 2017, 11:01 PM.

Details

Summary

updatePredecessorProfileMetadata propagates branch metadata to keep the information after jump-threading eliminates the branch with metadata.
This patch extends updatePredecessorProfileMetadata in two ways:

  1. The current updatePredecessorProfileMetadata propagates metadata only when the boolean value used in the conditional branch directly comes from comes from previous blocks. E.g. it supports conditional branch such as if (__builtin_expect(foo(), 0)).

This patch allows one additional icmp node before the conditional branch to catch common cases. E.g. this patch supports if (__builtin_expect(bar() == nullptr, 0)) as well.

  1. This patch enhances GetPredOutEdge to find the branch to be associated with the metadata in general control flow case. The original GetPredOutEdge lambda only allows the simplest cases.

Diff Detail

Event Timeline

inouehrs created this revision.Apr 3 2017, 11:01 PM
nemanjai added inline comments.May 14 2017, 4:07 AM
lib/Transforms/Scalar/JumpThreading.cpp
70

Maybe a comment mentioning why this default value (i.e. there's a bunch of mentions of 1:2000 identifying cold blocks, but this is set to 1000).

278

Please add an inline comment about the requirement for the MD having 3 operands.

283

Explicit comparisons against NULL seem at odds with other null checks added here.

300

I think nullptr is a more common way to initialize a null pointer. Same goes for other uses of NULL.

315

In general, I would recommend that a function with output parameters only set those output parameters on success. If there's a compelling reason to set WeightHot and WeightCold when returning nullptr, I think the comment at the top of the function should mention that behaviour.

325

Nit: please be careful with line length.

328

The logic in the function seems straightforward enough - looks like the cold region is all blocks dominated by ColdBlock and blocks post-dominated by ColdBlock (unless I'm misreading something). Then we set the branch weight on branches into that region.
Just seems like we should just be able to use the Dominators/PostDominators analyses for this kind of thing, but I very well may be missing something. In any case, if the existing analyses can't be used (even if it is an issue of analyses dependency) I think you should add a comment as to why that is.

1457

s/upword/upward

1458

This formatting looks odd. I almost missed the else.

inouehrs updated this revision to Diff 99131.May 16 2017, 6:16 AM

Updated based on Nemanja's comments. Also rebased to the latest code base.

inouehrs added inline comments.May 16 2017, 6:22 AM
lib/Transforms/Scalar/JumpThreading.cpp
70

For the default threshold, I modify to use 2000 (instead of 1000 in the previous patch) as the default value based on the _builtin_expect handling.

278

Added comment.

283

Thank you. I changed the style.

315

I modified the code to set WeightHot and WeightCold only when it returns the non-null pointer as the return value.

325

Fixed.

328

I added the comments. I use my simple implementation of dominance analysis because the CFG may be already modified if we have multiple branches with biased branch weights.
Also, a method with branch weight metadata is relatively rare and so I avoid requesting dominance analysis only for this purpose.

1457

Oops. Fixed.

1458

Fixed the style.

Gentle ping. I appreciate any suggestions.

inouehrs updated this revision to Diff 102774.Jun 15 2017, 8:01 PM
inouehrs edited the summary of this revision. (Show Details)
  • rebased to the latest source tree.
  • fixed coding style issues
inouehrs edited the summary of this revision. (Show Details)Jun 16 2017, 4:30 AM

Gentle ping.
Thank you.

inouehrs updated this revision to Diff 106004.Jul 11 2017, 8:28 AM
  • rebased to the latest source tree.
  • fixed build break
inouehrs updated this revision to Diff 119283.Oct 17 2017, 3:44 AM
  • rebased to the latest codebase
inouehrs updated this revision to Diff 121681.Nov 5 2017, 9:20 PM
  • fixed build break with the latest source
davidxl added a subscriber: davidxl.Nov 6 2017, 2:00 PM

I have not looked at this patch in details, but from the test case, it seems that the problem should be handled by the updatePredecessorProfileMetadata () method. Have you checked why the existing update does not kick in?

@davidxl Thank you for the comment. I have never realized your patch D36864 added similar functionality.
I will investigate updatePredecessorProfileMetadata.

inouehrs updated this revision to Diff 126094.Dec 8 2017, 12:31 AM
inouehrs retitled this revision from [JumpThreading] Propagate branch hint (biased branch weight) metadata to [JumpThreading] Propagate branch hint metadata in more cases.
inouehrs edited the summary of this revision. (Show Details)
inouehrs added reviewers: davidxl, chandlerc.

@davidxl I reimplemented functionality of my patch by enhancing your code. I appreciate any comments. Thanks!

inouehrs updated this revision to Diff 139779.Mar 26 2018, 5:46 AM
  • rebased to the latest tree and tested again
  • minor touch up
inouehrs updated this revision to Diff 142124.Apr 12 2018, 12:46 AM
  • rebase to the latest
  • code cleanup
sanjoy resigned from this revision.Jan 29 2022, 5:34 PM