This is an archive of the discontinued LLVM Phabricator instance.

Replace all uses of branch weights by branch probabilities on machine code level passes.
AbandonedPublic

Authored by congh on Oct 14 2015, 2:56 PM.

Details

Summary

This patch replaces all uses of branch weights by branch probabilities on machine code level passes. Each machine basic block now stores successors' probabilities, which are represented by fixed points with constant denominator. Therefore there is no additional space overhead as branch probability is also 32-bit. The sum of all successors' probabilities should be approximate one (not exact one due to rounding issues when calculating probabilities). There are several advantages of using probabilities instead of weights:

It is much faster and convenient to calculate branch probability for each successor. Previously, in order to get the branch probability, the sum of weights of all successors is calculated first, which is not quite efficient as the potential overflow is considered. When iterating successors and get their probabilities, the code is usually written as (for performance reason) getting the sum first and use the sum and scale value to calculate each successor's probability, which is odd and inconvenient. With this patch, probabilities are directly stored in each machine basic block and all issues above are gone.
Weights are suffering from some maintenance issues, and probabilities are easier to understand and maintain. David's proposal has stated it clearly: http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20150803/291610.html
It is easier to validate the correctness of probabilities list rather than weights list: the sum of the former should be 1 while there is not restriction to the latter. This is quite useful when checking the probability updates after a CFG transformation are correct or not.

Diff Detail

Event Timeline

congh updated this revision to Diff 37392.Oct 14 2015, 2:56 PM
congh retitled this revision from to Replace all uses of branch weights by branch probabilities on machine code level passes..
congh updated this object.
congh added reviewers: dexonsmith, davidxl.
congh added a subscriber: llvm-commits.
silvas added a subscriber: silvas.Oct 14 2015, 6:55 PM
silvas added inline comments.
include/llvm/Analysis/BranchProbabilityInfo.h
118–121

Can you factor out 1u<<20 into a named constant?

bruno added a subscriber: bruno.Oct 14 2015, 8:06 PM

Hi Cong Hou, very nice! A few comments below.

include/llvm/CodeGen/MachineBasicBlock.h
435

weight => probability

lib/CodeGen/MachineBasicBlock.cpp
511

Update comment about Weight list.

539

Ditto

552

Ditto

congh marked 5 inline comments as done.Oct 15 2015, 10:57 AM
congh added inline comments.
include/llvm/Analysis/BranchProbabilityInfo.h
118–121

OK. I created a static constant variable representing a likely probability.

congh updated this revision to Diff 37499.Oct 15 2015, 11:01 AM
congh marked an inline comment as done.

Update the patch according to silvas and bruno's comments.

davidxl added inline comments.Oct 15 2015, 4:34 PM
include/llvm/Analysis/BranchProbabilityInfo.h
93

Why is this interface still kept? As in MBB, this one should also be deprecated.

100

Same here

102

Same here.

111

Same here. I don't see a a reason to keep both Probability and weight interfaces.

(the only place weight is useful is branch meta data)

138

DenseMap<Edge, BranchProbability> Probabilities;

include/llvm/CodeGen/MachineBasicBlock.h
426

A side note -- I remember you mention in if conversion, duplicate cfg edges do exist?

440

Why do we want to have this interface? If the client does not know what probability to use, it won't be too hard to specify 1/N either.

732

Remove this method.

include/llvm/Support/BranchProbability.h
41

Any reason why Numerator and Denominator can not be uint64_t?

45

It is useful to introduce a static helper method (templatized) to return a default BranchProbability

template<class BlockT> BranchProbability getDefaultProbabillity(BlockT *);

83–84

when can overflow happen? Also should the check really be:

(uint64_t)N + RHS.H > D ?

lib/CodeGen/BranchFolding.cpp
1110

Why don't we make the BranchProbability interface to take uint64_t input parameters? With that, there is no need to compute the scale here.

lib/CodeGen/MIRPrinter.cpp
465

Avoid using the private method getSuccProbability here?

lib/CodeGen/MachineBranchProbabilityInfo.cpp
44

Is this correct? There are cases where the probability is really zero -- you need a better way to tell the difference between this and Probs.empty() case.

How about changing getSuccProbabliy's interface to be

bool getSuccProbability(BranchProbability&);

it returns false when there is no information.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
1498

Use a helper method for this (getDefaultProbability)

I would like to see this patch being separated into smaller ones if possible. We can keep both addSuccessor(..., Weight) and addSuccessor(..., BranchProbability) for a short period of time to ease the transition.

I am mostly concerned about the changes in updating branch weights/probs during transformation (SelectionDAGBuilder, BranchFolding, IfConversion etc). If we can separate the changes, it will be much easier to review and to debug later on if we have a performance issue.

include/llvm/Analysis/BranchProbabilityInfo.h
121

Should we remove getBranchWeightStackProtector after getBranchProbStackProtector is added?

include/llvm/CodeGen/MachineBasicBlock.h
427–433

Can you comment on if the sum of probabilities for all successors is 1, after adding the successor?

440

We seem to normalize the probabilities in this version of addSuccessor, but not the previous one. Any reason?

lib/CodeGen/MIRParser/MIParser.cpp
462

Can you add a comment for using 100? Because it is printed out as percentile?
It is kind of weird to print out as (0xbb / 0xbb = 33.0%), and to parse as (33).
Can you round-trip the printout?

congh added inline comments.Oct 15 2015, 5:38 PM
include/llvm/Analysis/BranchProbabilityInfo.h
93

This is needed in BlockFrequencyInfoImpl. Note that in this patch I only changed edge weights into probabilities in MBB but not in BranchProbabilityInfo. Do you think if we should also do this in BranchProbabilityInfo?

include/llvm/CodeGen/MachineBasicBlock.h
426

I am not quite sure about it.

440

This interface will do probability normalization which makes sure that the sum of them is around 1. Then other interface won't do this.

include/llvm/Support/BranchProbability.h
41

If we add an overload constructor with type uint64_t, there will be many compilation errors of ambiguous overloads when we pass arguments of int types.

45

I doubt if this is useful. Before we add a new successor, the number of successors n is an old number, and the default probability we need is actually 1/(n+1). Returning 1/(n+1) from this function is confusing.

83–84

When we construct a branch probability we do rounding to get the numerator. If the denominator is odd, then 1/2 + 1/2 will exceed 1 using BranchProbability representation. That is when overflow happens.

I forgot to update this part as when it is written we were using UINT32_MAX as denominator. I will update it.

lib/CodeGen/BranchFolding.cpp
1110

This is explained above.

lib/CodeGen/MIRPrinter.cpp
465

I will try to replace it with another method in another patch.

lib/CodeGen/MachineBranchProbabilityInfo.cpp
44

This interface looks good. Let me see if I could return a default probability if there is no information from getSuccProbability(). Or can we represent zero probability by using 1 as numerator?

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
1498

It seems that there is no other places that need this helper. If I found other places I will create a helper.

davidxl edited edge metadata.Oct 15 2015, 5:54 PM

Can you proceed with what Manman suggested (split it into smaller patches)? Here is my suggestion:

Patch-1: new interfaces -- no functional changes
Patch-2.1: SelectionDAG builder change to use new interfaces
Patch-2.2: rest of the clients
Patch-3: remove old weight based interfaces (no functional change expected)

include/llvm/Analysis/BranchProbabilityInfo.h
93

yes, this should also be done for BPI -- but in another patch after this one gets in and stablizes.

include/llvm/Support/BranchProbability.h
41

How about removing the interface with 32bit parameter and just keep the 64bit one?

83–84

ok -- but the check does not handle the case when the resulting Prob > 1.

lib/CodeGen/BranchFolding.cpp
1110

What if only 64bit interface is used?

Thanks for the review!

I would like to see this patch being separated into smaller ones if possible. We can keep both addSuccessor(..., Weight) and addSuccessor(..., BranchProbability) for a short period of time to ease the transition.

OK, this sounds good. I will produce another patch that keeps both interfaces.

I am mostly concerned about the changes in updating branch weights/probs during transformation (SelectionDAGBuilder, BranchFolding, IfConversion etc). If we can separate the changes, it will be much easier to review and to debug later on if we have a performance issue.

Sounds good.

include/llvm/Analysis/BranchProbabilityInfo.h
121

It is still used in StackProtector to build MDNode.

include/llvm/CodeGen/MachineBasicBlock.h
427–433

OK. The answer is no. This interface will be called several times when adding many successors so during any intermediate state the sum of probabilities of all successors is not 1. I will state it clearly in the comment.

440

When we don't pass a branch probability when adding a successor, we don't have enough information or intentionally want to use a "default" probability. Here we use 1/n as a "default" probability, where n is the new number of successors. To make sure this works, we need to normalize the probabilities of all successors.

lib/CodeGen/MIRParser/MIParser.cpp
462

OK. Yes, this should be fixed buy using the percentage representation in print.

congh added a comment.Oct 19 2015, 1:08 PM

Can you proceed with what Manman suggested (split it into smaller patches)? Here is my suggestion:

Patch-1: new interfaces -- no functional changes

This may increase the storage space of some classes like MBB which will store both weights and probabilities. Is that OK?

Patch-2.1: SelectionDAG builder change to use new interfaces

So for other users we just treat probabilities (which is built in SelectionDAGBuilder by using the new interfaces) as weights, right?

Patch-2.2: rest of the clients
Patch-3: remove old weight based interfaces (no functional change expected)

include/llvm/Analysis/BranchProbabilityInfo.h
93

OK.

include/llvm/Support/BranchProbability.h
41

At this momenta it seems that we only need 64-bit as input in one place. So is it worthwhile to do this? This may bring overhead when constructing probabilities. Another solution is creating a static builder function that takes 64-bit as inputs.

83–84

We don't allow a probability to be greater than 1, so here we use the saturating operation:

N = ((uint64_t)N + RHS.N > D) ? D : N + RHS.N;

This is basically done -- can you close this one?

congh abandoned this revision.Jan 22 2016, 10:44 AM

OK, I am abandoning this patch now..