This is an archive of the discontinued LLVM Phabricator instance.

[BPI] Ignore tail while distributing the remaining probability from unreachanble
ClosedPublic

Authored by skatkov on Apr 16 2017, 11:47 PM.

Details

Summary

This is a follow up patch for https://reviews.llvm.org/rL300440
to address a comment.

To make implementation to be consistent with other cases we just
ignore the tail after distribution of remaining probability between
reachable edges.

If we reduced the probability of some edges coming to unreachable
blocks we should distribute the remaining part across other edges
coming to reachable blocks to satisfy the condition that sum of all
probabilities should be equal to one. If this remaining part is not
divided by number of "reachable" edges then we get this tail.
This tail probability should be pretty small. Other cases just ignore
if the some of probabilities is not equal to one so we do the same.

Diff Detail

Event Timeline

skatkov created this revision.Apr 16 2017, 11:47 PM

Please review.

vsk edited edge metadata.Apr 19 2017, 10:18 AM

Thanks for the cleanup.

One note is that it would help to explicitly explain what your patch changes, and why, in your description (the title would be a very condensed version of this). This would make your patch easier to review.

lib/Analysis/BranchProbabilityInfo.cpp
336–338

IIUC, the "tail" is supposed to be some small, non-negative epsilon value. Maybe it's worth asserting this? E.g assert(tail >= 0 && tail < 1).

skatkov updated this revision to Diff 95893.Apr 19 2017, 11:35 PM
skatkov retitled this revision from [BPI] Follow up rL300440. NFC to [BPI] Move tail computation out of the loop. NFC.
skatkov edited the summary of this revision. (Show Details)
skatkov marked an inline comment as done.
chandlerc edited edge metadata.Apr 20 2017, 12:03 AM

Thanks for the updated patch description! Another minor request here.

include/llvm/Support/BranchProbability.h
115–121

Add a unittest? I know that much of BranchProbability isn't well covered by unittests, but we should really have good coverage for basic primitives like this and you can start covering the mutation operators.

Sure, will do.

skatkov updated this revision to Diff 95931.Apr 20 2017, 4:28 AM

Some test added.

skatkov marked an inline comment as done.Apr 20 2017, 4:29 AM

BTW, probably we should not add the tail to any edge at all... It might be that the information that two edges have exactly the same probability is mot important than the requirement that the sum of all probabilities should be 1. it seems that sum == 1 is not a strict requirement. For example, if we have three edges with the same weight then as a result the sum of probabilities will not be equal to one. What do you think?

Some test added.

The tests and added operators are awesome.

If you want, split that off into a separate change just to the BranchProbability stuff and go ahead and submit that?

BTW, probably we should not add the tail to any edge at all... It might be that the information that two edges have exactly the same probability is mot important than the requirement that the sum of all probabilities should be 1. it seems that sum == 1 is not a strict requirement. For example, if we have three edges with the same weight then as a result the sum of probabilities will not be equal to one. What do you think?

I think we already handle this kind of case in a few places in BPI and we should be consistent there. I can go digging for it but you may already know where it is...

skatkov updated this revision to Diff 96090.Apr 20 2017, 9:00 PM

BTW, probably we should not add the tail to any edge at all... It might be that the information that two edges have exactly the same probability is mot important than the requirement that the sum of all probabilities should be 1. it seems that sum == 1 is not a strict requirement. For example, if we have three edges with the same weight then as a result the sum of probabilities will not be equal to one. What do you think?

I think we already handle this kind of case in a few places in BPI and we should be consistent there. I can go digging for it but you may already know where it is...

Hi Chandler, I'm not sure what exactly you mean but take a look into the last test @test_unreachable_with_switch_prof4 in test/Analysis/BranchProbabilityInfo/basic.ll:
For the five unreachable edges with the same weight we generate the following probability
; CHECK: edge entry -> case_a probability is 0x1999999a / 0x80000000 = 20.00%
; CHECK: edge entry -> case_b probability is 0x1999999a / 0x80000000 = 20.00%
; CHECK: edge entry -> case_c probability is 0x1999999a / 0x80000000 = 20.00%
; CHECK: edge entry -> case_d probability is 0x1999999a / 0x80000000 = 20.00%
; CHECK: edge entry -> case_e probability is 0x1999999a / 0x80000000 = 20.00%

and 0x1999999a * 5 = 0x80000002 > 0x80000000, so the sum of probabilities is greater than 1.

After reading of the code a bit more I would say that in general no one worries about sum of probabilities is equal to 1. They follow it when operating on weights. But the trouble is that after weights are transformed to probabilities there are rounding errors which breaks the restriction.

skatkov updated this revision to Diff 97406.May 2 2017, 1:26 AM
skatkov retitled this revision from [BPI] Move tail computation out of the loop. NFC to [BPI] Ignore tail while distributing the remaining probability from unreachanble.
skatkov edited the summary of this revision. (Show Details)

Please review.

Ping, could please review this change.

reames accepted this revision.May 10 2017, 9:40 PM
reames added a subscriber: reames.

LGTM w/comment addressed.

lib/Analysis/BranchProbabilityInfo.cpp
333

I would suggest leaving the decrement in the loop and asserting after the loop that the remainder is less than the number of edges. A comment stating that we explicitly drop the remainder to be consistent with other code seems called for as well.

This revision is now accepted and ready to land.May 10 2017, 9:40 PM
reames added inline comments.May 10 2017, 9:43 PM
lib/Analysis/BranchProbabilityInfo.cpp
333

Actually, don't bother with this. The assert would follow trivially from the code just above it, that's fine. Thus, LGTM w/out comments. :)

This revision was automatically updated to reflect the committed changes.