This is an archive of the discontinued LLVM Phabricator instance.

Replace weights by probabilities in BPI.
ClosedPublic

Authored by congh on Dec 14 2015, 10:10 PM.

Details

Summary

This patch removes all weight-related interfaces from BPI and replace them by probability versions. With this patch, we won't use edge weight anymore in either IR or MC passes. Edge probabilitiy is a better representation in terms of CFG update and validation.

Diff Detail

Event Timeline

congh updated this revision to Diff 42818.Dec 14 2015, 10:10 PM
congh retitled this revision from to Replace weights by probabilities in BPI..
congh updated this object.
congh added a reviewer: davidxl.
congh added a subscriber: llvm-commits.
davidxl edited edge metadata.Dec 16 2015, 10:06 AM

Very nice changes -- I will review the patch in more details shortly..

Very nice changes -- I will review the patch in more details shortly..

davidxl added inline comments.Dec 18 2015, 12:39 PM
lib/Analysis/BranchProbabilityInfo.cpp
143–146

Can we unify the code a little more:

BranchProbability UnreachableProb =

( ReachableEdges.empty() ?
        BranchProbability(1, UnreachableEdges.size()) :
        BranchProbability(UR_TAKEN_WEIGHT, (....) * UnreachableEdges.size()));

BranchProbability ReachableProb = (UR_NOTAKEN_WEIGHT, ReachableEdges.size() * ...);

for (...: UnreachableEdges)

set...

for (...)

set ...
265–268

Similarly, the code can be simplified without special case..

349

No need to guard.

352

No need to guard.

355

No need to guard.

362

The original code will adjust the weight if it is too low. Do we need to check Prob here too?

587–590

Is it better just call getEdgeProbability(Src, *I)

congh added inline comments.Dec 18 2015, 2:02 PM
lib/Analysis/BranchProbabilityInfo.cpp
143–146

OK. We can set UnreachableProb to 100% when ReachableEdges is empty.

265–268

Done.

349

This is needed to keep the original behavior: when BackEdges is empty, we don't want to normalize probabilities including the BP in this branch. Part of the reason is that we don't have a function to normalize all BB's successors' probabilities (although we have one for MBB).

352

Ditto.

355

Ditto.

362

I think this is unnecessary: the weight can become too small (like zero) after being divided but we don't have this issue in probabilities.

587–590

We need to take care of the case MapI == Probs.end() so we cannot call getEdgeProbability(Src, *I).

congh added inline comments.Dec 18 2015, 2:23 PM
lib/Analysis/BranchProbabilityInfo.cpp
143–146

I later found that I have to take care of the non-zero divider case here. To make the code more clear, I think the early exit solution might be better.

congh updated this revision to Diff 43270.Dec 18 2015, 2:24 PM
congh edited edge metadata.

Update on David'd comments.

congh updated this revision to Diff 43271.Dec 18 2015, 2:26 PM

Remove an unnecessary std::max<uint32_t>.

davidxl added inline comments.Dec 21 2015, 4:24 PM
lib/Analysis/BranchProbabilityInfo.cpp
143–147

Instead of using division later, why not use the multiplication suggestion in my previous comment? The weight is small enough that there is no risk of overflowing.

349

Does it matter here? As you can see it is guarded later -- so there is no functional change here. Removing the guard makes code look cleaner

congh added inline comments.Dec 21 2015, 4:57 PM
lib/Analysis/BranchProbabilityInfo.cpp
143–147

OK.

349

Here is an example: suppose BackEdges is empty and the other two are not. Then the current behavior is that we will have 0, 124/128 and 4/128 in Probs, which will not change after normalization. If we remove those branches , we will have 124/128, 124/128, and 4/128 in Probs, and after normalization they will become roughly 1/2, 1/2, and a very small prob. Note that we won't normalize probabilities that are assigned to successors anymore. Those two lists are quite different and will result in different behaviors.

congh updated this revision to Diff 43418.Dec 21 2015, 4:58 PM

Update on David's comments.

davidxl added inline comments.Dec 21 2015, 10:24 PM
lib/Analysis/BranchProbabilityInfo.cpp
349

Ok, I now see the normalization is done before prob assignment. However I think we can get rid of the normalization completely by computing the right denorm value in the first place. Say the number of back edges is B, number of In edges is I, and number of exiting edges are E, the denorm is

D = (B? TAKEN_WEIGHT: 0) + (I ? TAKEN_WEIGHT : 0) + (E ? NON_TAKEN_WEIGHT : 0)

So a backedge prob (if exists) is:

Prob(backedge) = TAKEN_WEIGHT/(D*B)

congh updated this revision to Diff 43456.Dec 22 2015, 10:35 AM

Update the patch according to David's comment.

congh added inline comments.Dec 22 2015, 10:38 AM
lib/Analysis/BranchProbabilityInfo.cpp
349

OK. I have updated the patch accordingly.

davidxl accepted this revision.Dec 22 2015, 10:45 AM
davidxl edited edge metadata.

lgtm.

This revision is now accepted and ready to land.Dec 22 2015, 10:45 AM
This revision was automatically updated to reflect the committed changes.