This is an archive of the discontinued LLVM Phabricator instance.

Provide an interface normalizeSuccWeights in MachineBasicBlock to normalize its successors' weights and use it in other places.
ClosedPublic

Authored by congh on Jul 22 2015, 5:56 PM.

Details

Summary

The implementation of the new function is borrowed from MachineBranchProbabilityInfo::getSumForBlock. The type of weight list is a template parameter so that we can pass weights in either uint32_t or uint64_t.

This function can be useful when we need to normalize a list of edge weights.

Diff Detail

Event Timeline

congh updated this revision to Diff 30436.Jul 22 2015, 5:56 PM
congh retitled this revision from to Create a utility function normalizeEdgeWeights() in BranchProbabilityInfo that is used to normalize a list of weights so that the sum of them does not exceed UINT32_MAX..
congh updated this object.
congh added a reviewer: dexonsmith.
congh added subscribers: llvm-commits, davidxl.
davidxl added inline comments.Jul 23 2015, 12:30 PM
include/llvm/Analysis/BranchProbabilityInfo.h
165 ↗(On Diff #30436)

Why not doing normalization unconditionally to avoid precision loss introduced by incremental update (for small weights)?

congh added inline comments.Jul 23 2015, 1:38 PM
include/llvm/Analysis/BranchProbabilityInfo.h
165 ↗(On Diff #30436)

The incremental update itself can deal with precision loss, then this function can be called to guarantee that the sum of weights won't exceed UINT32_MAX.

If we decide to normalize all edge weights with scaling up, we should call this normalization function every time we set or update the edge weight. Have we decided this?

davidxl added inline comments.Jul 23 2015, 2:01 PM
include/llvm/Analysis/BranchProbabilityInfo.h
165 ↗(On Diff #30436)

You will be needing this for precision preservation purpose, so this interface needs to take an extra argument to decide if up-scaling needs to be done -- by default it can be off.

congh added inline comments.Jul 23 2015, 2:13 PM
include/llvm/Analysis/BranchProbabilityInfo.h
165 ↗(On Diff #30436)

OK. But I am wondering how to tell if the returned scale is for scaling up or down? This is the difficult part...

congh updated this revision to Diff 30953.Jul 29 2015, 3:16 PM
congh retitled this revision from Create a utility function normalizeEdgeWeights() in BranchProbabilityInfo that is used to normalize a list of weights so that the sum of them does not exceed UINT32_MAX. to Provide an interface normalizeSuccWeights in MachineBasicBlock to normalize its successors' weights and use it in other places..
congh added a reviewer: chandlerc.

Several updates:

  1. Move normalizeEdgeWeights() from BranchProbabilityInfo to MachineBranchProbabilityInfo.
  2. Provide an interface in MachineBasicBlock to normalize its successors' weights.
  3. Add a flag int MachineBasicBlock that tracks whether its successors' weights are normalized.
  4. Provide an overload of getSumForBlock that accepts a non-const pointer to a MBB so that it can force normalizing this MBB's successors' weights.
  5. Update several uses of getSumForBlock() by eliminating the once needed weight scale.
davidxl added inline comments.Jul 29 2015, 3:24 PM
include/llvm/CodeGen/MachineBasicBlock.h
88

Put this field after int Number field so that the padding space can be used (for 64bit).

congh marked an inline comment as done.Jul 29 2015, 3:28 PM
congh added inline comments.
include/llvm/CodeGen/MachineBasicBlock.h
88

OK. Updated.

congh updated this revision to Diff 30958.Jul 29 2015, 3:29 PM
congh marked an inline comment as done.

Reduce the size of MachineBasicBlock by relocating SuccWeightsNormalized which is a boolean.

In general, I find doing normalization like this is error prone. Once the weights gets normalized, the new weight added in later may become meaningless and there is no good way to check against it.

I suggest using this opportunity to use edge weight to represent fixed point representation of the branch probability (aka scaled probability). We can pick a large scale factor such as 100000. It has the nice property that the sum of all 'weights' will guarantee to be always '100000'. Another nice side effect is that the computation of getEdgeProbability is now super fast -- there is no need to keep the getSumWeight interface any more.

The addSuccessor interface will also need to be modified such that instead of passing raw 'weight', it needs to pass in BranchProbablity(N,M).

In the longer term, we should remove uses of getEdgeWeight interface completely and replace it with getEdgeProbabity instead (as it is already efficient). Weight will simply be an implementation detail that does not need to be exposed to users.

lib/CodeGen/IfConversion.cpp
1245

why not move this before getEdgeWeight so that the explicit call to normalize weight is not needed?

In general, I find doing normalization like this is error prone. Once the weights gets normalized, the new weight added in later may become meaningless and there is no good way to check against it.

Yes, but this depends on when the normalization is applied. If the user calls it explicitly, he/she should be aware that the edge weights are already changed so the newly added one needs to be adjusted. Otherwise, the user also needs to check the current normalized weights to determine the new successor's weight (otherwise how to assign weight to a new successor?). But this design can still bring potential errors.

I suggest using this opportunity to use edge weight to represent fixed point representation of the branch probability (aka scaled probability). We can pick a large scale factor such as 100000. It has the nice property that the sum of all 'weights' will guarantee to be always '100000'. Another nice side effect is that the computation of getEdgeProbability is now super fast -- there is no need to keep the getSumWeight interface any more.

I agree this design: the only use of weights is to compute edge probabilities. We should adjust the edge "weight" in terms of probabilities instead of an absolute weight. This is a more flexible representation.

The addSuccessor interface will also need to be modified such that instead of passing raw 'weight', it needs to pass in BranchProbablity(N,M).

So the probabilities of old successors can be adjusted accordingly.

In the longer term, we should remove uses of getEdgeWeight interface completely and replace it with getEdgeProbabity instead (as it is already efficient). Weight will simply be an implementation detail that does not need to be exposed to users.

congh added inline comments.Jul 30 2015, 10:57 AM
lib/CodeGen/IfConversion.cpp
1245

This is to explicitly stating that we should normalize the edge weights then get them. I am afraid if we just simply put getSumForBlock() before getEdgeWeight(), some people who are not aware that getSumForBlock() does weights normalization may switch them later by mistake.

This revision was automatically updated to reflect the committed changes.
congh updated this revision to Diff 31882.Aug 11 2015, 4:43 PM
congh removed rL LLVM as the repository for this revision.

Update the patch by turning zero edge weights into one in BPI so that we won't get zero weights in BPI anymore.

davidxl added inline comments.Aug 20 2015, 12:27 PM
test/Transforms/SampleProfile/branch.ll
41 ↗(On Diff #31882)

Since BFI always ignores zero weight which leads to inconsistency (as BPI did not ignore zero weight before this fix, only BFI does it).

If the test case really intend to test a highly biased branch here, I think the test case should be modified to not use zero weight after this fix (as it now will be completely ignored). Changing the the results to 50% may violate what is intended by the test.

congh added inline comments.Aug 20 2015, 2:56 PM
test/Transforms/SampleProfile/branch.ll
41 ↗(On Diff #31882)

I did an investigation on this. The weight 0 and 1 are not indicated in this test cased but are read from a sample profile file, in which most lines have zero weights except two which are large weights. Where does 1 come from? When a zero weight is read from sample profile, it is converted to 1 (see include/llvm/ProfileData/SampleProf.h:175). In the comment, it says that the weight is set to 0 if the profile data is missing. If the profile data exist and the number of samples is zero, it will be converted to 1 to differentiate those two different cases. However, this will lead to a possible result that two edges from the same block have weight 0 and 1 (0 for missing profile and 1 for 0 sample): now how to interpret them? I think here it is a good idea to convert 0 to 1 in BPI for this case. For the original test case the probability 0 and 100% are quite wrong, but 50% and 50% as in the updated test case is more reasonable.

davidxl added inline comments.Aug 21 2015, 3:13 PM
test/Transforms/SampleProfile/branch.ll
41 ↗(On Diff #31882)

In AutoFDO, lines with instructions generated but without any samples are annotated with 0 counts -- they actually should not be converted to 1 as 0 counts are strong signals of coldness.

One the other hand, lines that do not have any instructions associated (due to CSE, PRE, IVOPT etc) do not have any counts either, but they should not be marked with 0 counts and should be specially handled. It seems current implementation tries to overload zero weight again to represent this state which is wrong because zero weight does not do what it thinks it does.

At this point, I think this test does not matters that much (Dehao and Diego are working to overhaul SampleFDO support anyway) -- so I am ok with this change.

Duncan, WDYT?