Page MenuHomePhabricator

Let edge weight be always greater than zero in both BPI and MBPI.
AbandonedPublic

Authored by congh on Aug 10 2015, 11:37 AM.

Details

Summary

Currently BPI requires that edge weights must be greater than 0, but MBPI doesn't have this requirement. In MBPI, when an edge weight is zero, it is treated as there is no weight info for that edge. At runtime, such a zero edge weight will be turned into a DEFAULT edge weight 16. This may lead to incorrect edge weights ratio when we originally have 0 and 1 as edge weights from the same block and later get 16 and 1. Zero weights can either mean no info or obtained from BPI or calculated by users, making it ambiguous. When we have all out-edges with zero weights from the same block, it is awkward to compute edge probabilities. Though this is worked-around by using default edge weights. However, if we require edge weights in MBPI also should be greater than zero, we won't have the issues above.

In addition, although BPI requires edge weights to be greater than zero, it doesn't guarantee this when weights are read from metadata. So we need to normalize edge weights when we read zero weight from metadata. For example, if we have 0 and 1 edge weights from the same block (assume it only has two out-edges), we can normalize them into 1 and UINT32_MAX - 1.

This patch contains the following changes:

  1. Normalize edge weights in BPI to guarantee that they are greater than 0.
  2. In MBPI don't turn zero edge weights into default weights as we should not have zero weights anymore.
  3. (To discuss) Weight list can be empty previously when it is not used at all. I found it difficult to make weight list and successor list always synchronized so this patch will always update weight list whether it is used or not. Is this acceptable?
  4. Adjust use and test cases accordingly.

Diff Detail

Event Timeline

congh updated this revision to Diff 31689.Aug 10 2015, 11:37 AM
congh retitled this revision from to Let edge weight be always greater than zero in both BPI and MBPI..
congh updated this object.
congh added reviewers: dexonsmith, davidxl.
congh added a subscriber: llvm-commits.
davidxl edited edge metadata.Aug 11 2015, 9:19 AM

Since we plan to change [M]MPI interfaces to hide weight which is internal, can we minimize this patch? My understanding is that minimal change is needed to make the weight normalization patch work well with zero weights.

include/llvm/CodeGen/MachineBasicBlock.h
386 ↗(On Diff #31689)

Is 16 a good default value to indicate missing information?

The current underlying (without this patch) assumption in MBPI is that if the weight list is empty, 0 weight represents 'unknown' weight -- otherwise it will be treated as a real zero value weight. This assumption is of course very weak and can break down at any time.

All these needs to be considered in the new design when weight is eliminated from the profiling related interfaces -- i.e., reserve a special value for unknown 'probability'.

lib/Analysis/BranchProbabilityInfo.cpp
210

Which clients produce zero weights ? It seems that Clang FE does not do that. See scaleBranchWeight in tools/clang/lib/CodeGen/CodeGenPGO.cpp

Since we plan to change [M]MPI interfaces to hide weight which is internal, can we minimize this patch? My understanding is that minimal change is needed to make the weight normalization patch work well with zero weights.

Yes, I can reduce the size of this patch so that we only need to make sure there is no zero weight from BPI. This should make edge weights normalization work.

include/llvm/CodeGen/MachineBasicBlock.h
386 ↗(On Diff #31689)

Both BPI and MBPI use 16 as default weight and that is why I also use 16 here. I agree with you. This doesn't matter now and we need to find out how to assign a default probability to a new successor if it is indicated explicitly.

lib/Analysis/BranchProbabilityInfo.cpp
210

It happens in test cases where the branch weight is explicitly assigned as zero.

congh updated this revision to Diff 31841.Aug 11 2015, 11:31 AM
congh edited edge metadata.

Reduce the patch by only eliminating zero weights in BPI.

I thought we need to fix MBPI to handle bad interactions of with weight normalization and zero weight. Why do we need to fix BPI?

test/Analysis/BlockFrequencyInfo/bad_input.ll
12

Do we know what the original intention of the test case is?

I thought we need to fix MBPI to handle bad interactions of with weight normalization and zero weight. Why do we need to fix BPI?

Zero weights have two meanings in MBPI: 1. It is a real zero weight that is from BPI. 2. It is an unknown weight. If we require that all weights from BPI cannot be zero, then it now only has the second meaning. The test failures on the weight normalization patch can now be fixed (note that those tests contains prof_data with 0 edge weights, which are eliminated in BPI now).

test/Analysis/BlockFrequencyInfo/bad_input.ll
12

This is testing if we have MD with 0, 3 as branch weights, in BFI we will get 1, 4 instead of 0, 3 as branch weights. In this patch we have eliminated zero weights so we should get 1 and a very large integer (around UINT32_MAX) as edge weights.

davidxl added inline comments.Aug 11 2015, 12:08 PM
test/Analysis/BlockFrequencyInfo/bad_input.ll
12

What existing code in BPI/BFI changes 0,3 into 1,4?

congh added inline comments.Aug 11 2015, 12:28 PM
test/Analysis/BlockFrequencyInfo/bad_input.ll
12

It is done in lib/Analysis/BlockFrequencyInfoImpl.cpp:265. Actually this turns the edge weights from 0,3 into 1, 3, and then the frequency ratio of the loop body over the exit now becomes 1:4.

Ok -- it is a very messy situation that need lots of cleanup (summarized below). For now, since the only producer of zero weight for BPI is from 'opt' by reading developer's hand writing .ll file, I suggest simply set zero weight to 1 in calcMetaDataWeights to match BlockFrequencyInfoImpl's behavior.


Current situation:

  1. there is no client (other than opt) producing zero weight for BPI
  2. BPI can have missing weights (empty map entry) -- in which case, the edge weight returned is DEFAULT_WEIGHT= 16

for MBPI

  1. the default weight in the setter interface is '0' -- which can not be differentiated with real zero weight
  2. when Weight list for a BB is empty, the getter interface returns 16 as the default weight.
  3. the getter interface also unconditionally change 0 weight into DEFAULT_WEIGHT == 16
  4. the weight list and successor list can be out of sync.
congh added a comment.Aug 11 2015, 3:07 PM

Ok -- it is a very messy situation that need lots of cleanup (summarized below). For now, since the only producer of zero weight for BPI is from 'opt' by reading developer's hand writing .ll file, I suggest simply set zero weight to 1 in calcMetaDataWeights to match BlockFrequencyInfoImpl's behavior.

Assume the user uses weights 0 and 1 to represent that one edge is very very cold and another one is very very hot, then this modification makes them to 1 and 1, which has the totally different meaning.


Current situation:

  1. there is no client (other than opt) producing zero weight for BPI
  2. BPI can have missing weights (empty map entry) -- in which case, the edge weight returned is DEFAULT_WEIGHT= 16 for MBPI

I think you mean MBB&MBPI as 3) & 6) below are for MBB.

  1. the default weight in the setter interface is '0' -- which can not be differentiated with real zero weight
  2. when Weight list for a BB is empty, the getter interface returns 16 as the default weight.

Here MBB returns 0 but MBPI turns it into 16.

  1. the getter interface also unconditionally change 0 weight into DEFAULT_WEIGHT == 16
  2. the weight list and successor list can be out of sync.
congh abandoned this revision.Oct 2 2015, 11:22 AM