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

[congh]

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.

[davidxl]

include/llvm/Analysis/BranchProbabilityInfo.h

165

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

[congh]

include/llvm/Analysis/BranchProbabilityInfo.h

165

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]

include/llvm/Analysis/BranchProbabilityInfo.h

165

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]

include/llvm/Analysis/BranchProbabilityInfo.h

165

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

[congh]

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]

include/llvm/CodeGen/MachineBasicBlock.h

83 ↗

(On Diff #30953)

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

[congh]

include/llvm/CodeGen/MachineBasicBlock.h

83 ↗

(On Diff #30953)

OK. Updated.

[congh]

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

[davidxl]

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 ↗

(On Diff #30958)

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

[congh]

In D11442#215298, @davidxl wrote:

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]

lib/CodeGen/IfConversion.cpp

1245 ↗

(On Diff #30958)

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.

[congh]

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

[davidxl]

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]

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]

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?

include/llvm/Analysis/BranchProbabilityInfo.h

public:
   /// weights are calculated carefully before using!
   void setEdgeWeight(const BasicBlock *Src, unsigned IndexInSuccessors,
                      uint32_t Weight);
 
   static uint32_t getBranchWeightStackProtector(bool IsLikely) {
     return IsLikely ? (1u << 20) - 1 : 1;
   }
 
+  /// Normalize a list of weights by scaling them down so that the sum of them
+  /// doesn't exceed UINT32_MAX. Return the scale.
+  template <class WeightVec>
+  static uint32_t normalizeEdgeWeights(WeightVec &Weights);
+
   void calculate(Function &F, const LoopInfo& LI);
 
 private:
   // Since we allow duplicate edges from one basic block to another, we use
   // a pair (PredBlock and an index in the successors) to specify an edge.
   typedef std::pair<const BasicBlock *, unsigned> Edge;
 
   // Default weight value. Used when we don't have information about the edge.
private:
   bool calcColdCallHeuristics(BasicBlock *BB);
   bool calcPointerHeuristics(BasicBlock *BB);
   bool calcLoopBranchHeuristics(BasicBlock *BB, const LoopInfo &LI);
   bool calcZeroHeuristics(BasicBlock *BB);
   bool calcFloatingPointHeuristics(BasicBlock *BB);
   bool calcInvokeHeuristics(BasicBlock *BB);
 };
 
+template <class WeightVec>
+uint32_t BranchProbabilityInfo::normalizeEdgeWeights(WeightVec &Weights) {
+  // First we compute the sum with 64-bits of precision.
+  uint64_t Sum = std::accumulate(Weights.begin(), Weights.end(), uint64_t(0));
+
+  // If the computed sum fits in 32-bits, we're done.
+  if (Sum <= UINT32_MAX)
+    return 1;
+
+  // Otherwise, compute the scale necessary to cause the weights to fit, and
+  // re-sum with that scale applied.
+  assert((Sum / UINT32_MAX) < UINT32_MAX);
+  uint32_t Scale = (Sum / UINT32_MAX) + 1;
+  for (auto &W : Weights)
+    W /= Scale;
+  return Scale;
+}
+
 /// \brief Legacy analysis pass which computes \c BranchProbabilityInfo.
 class BranchProbabilityInfoWrapperPass : public FunctionPass {
   BranchProbabilityInfo BPI;
 
 public:
   static char ID;
 
   BranchProbabilityInfoWrapperPass() : FunctionPass(ID) {

lib/CodeGen/MachineBranchProbabilityInfo.cpp

 //===- MachineBranchProbabilityInfo.cpp - Machine Branch Probability Info -===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This analysis uses probability info stored in Machine Basic Blocks.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 INITIALIZE_PASS_BEGIN(MachineBranchProbabilityInfo, "machine-branch-prob",
                       "Machine Branch Probability Analysis", false, true)
 INITIALIZE_PASS_END(MachineBranchProbabilityInfo, "machine-branch-prob",
                     "Machine Branch Probability Analysis", false, true)
 
 char MachineBranchProbabilityInfo::ID = 0;
 
 void MachineBranchProbabilityInfo::anchor() { }
 
 uint32_t MachineBranchProbabilityInfo::
 getSumForBlock(const MachineBasicBlock *MBB, uint32_t &Scale) const {
-  // First we compute the sum with 64-bits of precision, ensuring that cannot
-  // overflow by bounding the number of weights considered. Hopefully no one
-  // actually needs 2^32 successors.
   assert(MBB->succ_size() < UINT32_MAX);
-  uint64_t Sum = 0;
-  Scale = 1;
+  SmallVector<uint32_t, 8> Weights;
   for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
-       E = MBB->succ_end(); I != E; ++I) {
-    uint32_t Weight = getEdgeWeight(MBB, I);
-    Sum += Weight;
-  }
+       E = MBB->succ_end(); I != E; ++I)
+    Weights.push_back(getEdgeWeight(MBB, I));
 
-  // If the computed sum fits in 32-bits, we're done.
-  if (Sum <= UINT32_MAX)
-    return Sum;
-
-  // Otherwise, compute the scale necessary to cause the weights to fit, and
-  // re-sum with that scale applied.
-  assert((Sum / UINT32_MAX) < UINT32_MAX);
-  Scale = (Sum / UINT32_MAX) + 1;
-  Sum = 0;
-  for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
-       E = MBB->succ_end(); I != E; ++I) {
-    uint32_t Weight = getEdgeWeight(MBB, I);
-    Sum += Weight / Scale;
-  }
-  assert(Sum <= UINT32_MAX);
-  return Sum;
+  Scale = BranchProbabilityInfo::normalizeEdgeWeights(Weights);
+  return std::accumulate(Weights.begin(), Weights.end(), 0u);
 }
 
 uint32_t MachineBranchProbabilityInfo::
 getEdgeWeight(const MachineBasicBlock *Src,
               MachineBasicBlock::const_succ_iterator Dst) const {
   uint32_t Weight = Src->getSuccWeight(Dst);
   if (!Weight)
     return DEFAULT_WEIGHT;