This is an archive of the discontinued LLVM Phabricator instance.

[BrachProbablityInfo] Set edge probabilities at once.
ClosedPublic

Authored by yrouban on May 4 2020, 11:04 PM.

Details

Summary

Hide the method that allows setting probability for particular edge and introduce a public method that sets probabilities for all outgoing edges at once.
Setting individual edge probability is error prone. More over it is difficult to check that the total probability is 1.0 because there is no easy way to know when the user finished setting all the probabilities.

One bug is fixed in BranchProbabilityInfo::calcMetadataWeights(). Changing unreachable branch probabilities to raw(1) and distributing the rest (oldProbability - raw(1)) over the reachable branches could introduce total probability inaccuracy bigger than 1/numOfBranches.

Diff Detail

Event Timeline

yrouban created this revision.May 4 2020, 11:04 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 4 2020, 11:04 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
hjyamauchi added inline comments.
llvm/include/llvm/Analysis/BranchProbabilityInfo.h
135

Can you add a short general comment for this public setEdgeProbability?

llvm/lib/Analysis/BranchProbabilityInfo.cpp
993–994

Looks like simply checking "TotalNumerator == BranchProbability::getDenominator()" won't work probably because of rounding errors. Can you add a brief comment?

yrouban updated this revision to Diff 262812.May 7 2020, 9:53 PM
yrouban marked 2 inline comments as done.

added comments

I think the new API of setting probabilities for all edges "atomically" is a good move. There is one suggestion though. In fact, there is no need to "repack" vector of probabilities into map. We can simply copy or even move (in most cases we have rvalue) entire vector into a map. This can be done as a separate change though.

This revision is now accepted and ready to land.May 8 2020, 9:44 AM
This revision was automatically updated to reflect the committed changes.
rnk added a subscriber: rnk.May 13 2020, 8:09 AM
rnk added inline comments.
llvm/lib/Analysis/BranchProbabilityInfo.cpp
1000

This assert doesn't appear to hold:
https://ci.chromium.org/p/chrome/builders/ci/ToTWin/6284
Assertion failed: TotalNumerator >= BranchProbability::getDenominator() - Probs.size(), file C:\b\s\w\ir\cache\builder\src\third_party\llvm\llvm\lib\Analysis\BranchProbabilityInfo.cpp, line 995

I will gather more information.

rnk added inline comments.May 13 2020, 8:22 AM
llvm/lib/Analysis/BranchProbabilityInfo.cpp
1000

These are the relevant values:

TotalNumerator 2147483624
BranchProbability::getDenominator() 2147483648
Probs.size() 21

This is the IR switch:

switch i32 %0, label %sw.epilog.i [
  i32 20, label %sw.bb20.i
  i32 1, label %sw.bb1.i
  i32 2, label %sw.bb2.i
  i32 3, label %sw.bb3.i
  i32 4, label %sw.bb4.i
  i32 5, label %sw.bb5.i
  i32 6, label %sw.bb6.i
  i32 11, label %sw.bb7.i
  i32 12, label %sw.bb8.i
  i32 13, label %sw.bb9.i
  i32 7, label %sw.bb10.i
  i32 9, label %"?SkColorTypeToGrColorType@@YA?AW4GrColorType@@W4SkColorType@@@Z.exit"
  i32 8, label %sw.bb12.i
  i32 10, label %"?SkColorTypeToGrColorType@@YA?AW4GrColorType@@W4SkColorType@@@Z.exit"
  i32 14, label %sw.bb14.i
  i32 15, label %sw.bb15.i
  i32 18, label %sw.bb16.i
  i32 19, label %sw.bb17.i
  i32 16, label %sw.bb18.i
  i32 17, label %sw.bb19.i
], !dbg !77, !prof !81

I think it comes from this source construct:
https://source.chromium.org/chromium/chromium/src/+/master:third_party/skia/include/private/GrTypesPriv.h;drc=2f11470d7ad8963a9add116df64d2edd1b85d3a4;l=869?originalUrl=https:%2F%2Fcs.chromium.org%2F
Inlined into this function:
https://source.chromium.org/chromium/chromium/src/+/master:third_party/skia/src/image/SkSurface_Gpu.cpp;l=342?q=MakeRenderTarget&ss=chromium&originalUrl=https:%2F%2Fcs.chromium.org%2F

I will revert for now, since this prevents us from seeing other ToT issues on PGO builders, but feel free to reland with a fix.

yrouban marked an inline comment as done.May 13 2020, 8:49 AM
yrouban added inline comments.
llvm/lib/Analysis/BranchProbabilityInfo.cpp
1000

please give me the !prof branch_weights so I can reproduce.

rnk added inline comments.May 13 2020, 4:27 PM
llvm/lib/Analysis/BranchProbabilityInfo.cpp
1000

<0xd3589a0> = !{!"branch_weights", i32 1, i32 1, i32 1, i32 1, i32 1, i32 451, i32 1, i32 12, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1}

Dumping them produced this:
0x00000001 / 0x80000000 = 0.00%
0x004761ef / 0x80000000 = 0.22%
0x004761ef / 0x80000000 = 0.22%
0x004761ef / 0x80000000 = 0.22%
0x004761ef / 0x80000000 = 0.22%
0x77c7e9e7 / 0x80000000 = 93.58%
0x004761ef / 0x80000000 = 0.22%
0x03333332 / 0x80000000 = 2.50%
0x004761ef / 0x80000000 = 0.22%
0x004761ef / 0x80000000 = 0.22%
0x004761ef / 0x80000000 = 0.22%
0x004761ef / 0x80000000 = 0.22%
0x004761ef / 0x80000000 = 0.22%
0x004761ef / 0x80000000 = 0.22%
0x004761ef / 0x80000000 = 0.22%
0x004761ef / 0x80000000 = 0.22%
0x004761ef / 0x80000000 = 0.22%
0x004761ef / 0x80000000 = 0.22%
0x004761ef / 0x80000000 = 0.22%
0x004761ef / 0x80000000 = 0.22%
0x004761ef / 0x80000000 = 0.22%

yrouban marked an inline comment as done.May 14 2020, 4:58 AM
yrouban added inline comments.
llvm/lib/Analysis/BranchProbabilityInfo.cpp
1000

Great! we have found a bug in calcMetadataWeights(). I will fix and add a test case.

yrouban updated this revision to Diff 264160.EditedMay 14 2020, 10:45 PM
yrouban retitled this revision from [BrachProbablityInfo] Set edge probabilities at once. NFC. to [BrachProbablityInfo] Set edge probabilities at once..
yrouban edited the summary of this revision. (Show Details)

Fixed bug in BranchProbabilityInfo::calcMetadataWeights() to keep total probability close to 1.0. Added a new testcase for this and fixed another one.

yrouban reopened this revision.May 15 2020, 4:02 AM

Please review again.

This revision is now accepted and ready to land.May 15 2020, 4:02 AM
yrouban marked an inline comment as done.May 17 2020, 11:57 PM
yrouban added inline comments.
llvm/lib/Analysis/BranchProbabilityInfo.cpp
369

TODO: This spreads ToDistribute evenly upon the reachable edges. A better distribution would be proportional. So the relation between weights of the reachable edges would be kept unchanged:

For any reachable edges i and j:
newBP[i] / newBP[j] == oldBP[i] / oldBP[j]
newBP[i] / oldBP[i] == newBP[j] / oldBP[j] == Denominator / (Denominator - ToDistribute)
newBP[i] = oldBP[i] * Denominator / (Denominator - ToDistribute)

ebrevnov added inline comments.May 19 2020, 12:01 AM
llvm/lib/Analysis/BranchProbabilityInfo.cpp
362

It's really hard to parse the comment since it heavily depends on old code which will be unavailable. Please try to rephrase.

369

I think it makes sense to put that comment into the code directly

yrouban updated this revision to Diff 265191.May 20 2020, 3:01 AM

In BranchProbabilityInfo::calcMetadataWeights() rephrased one comment and added one TODO.

ebrevnov accepted this revision.May 20 2020, 9:42 AM

Thanks! LGTM.

This revision was automatically updated to reflect the committed changes.