Use getEdgeProbability() instead of getEdgeWeight() in BFI and remove getEdgeWeight() interfaces from MBPI.

[congh]

Summary

This patch remove all getEdgeWeight() interfaces from CodeGen directory. As getEdgeProbability() is a little more expensive than getEdgeWeight(), I will compose a patch soon in which BPI only stores probabilities instead of edge weights so that getEdgeProbability() will have O(1) time.

[davidxl]

include/llvm/Analysis/BlockFrequencyInfoImpl.h

1193 ↗

(On Diff #42696)

Can you add a file local wrapper function in this file

inline static uint32_t getEdgeWeight(... ) { return ... getNumerator()...)

test/Analysis/BlockFrequencyInfo/bad_input.ll

13 ↗

(On Diff #42696)

What makes this diff?

[congh]

Update the patch according to David's comment.

include/llvm/Analysis/BlockFrequencyInfoImpl.h

1193 ↗

(On Diff #42696)

This function will have some weird parameters like successor iterator and BPI, I instead created a wrapper convertBranchProbabilityToWeight() to convert BP into weight.

test/Analysis/BlockFrequencyInfo/bad_input.ll

13 ↗

(On Diff #42696)

The weights 0 will be transformed into 1 in BFI so we will get 1 and 3 as the actual weights that are used to calculate frequencies. With this patch the numerators of BP are used as weight so we will get 0 and 1<<31 (representing BP 0% and 100%) as edge weights, which are then transformed into 1 and 1<<31 later.

[davidxl]

include/llvm/Analysis/BlockFrequencyInfoImpl.h

1178 ↗

(On Diff #42793)

The name is too long. How about just getWeightFromBranchProb?

test/Analysis/BlockFrequencyInfo/bad_input.ll

13 ↗

(On Diff #42793)

The original code also calls into Src->getSuccProbability(Dst).getNumerator() eventually -- so the change looks like NFC -- I missed something obvious here ..

[congh]

include/llvm/Analysis/BlockFrequencyInfoImpl.h

1178 ↗

(On Diff #42793)

OK.

test/Analysis/BlockFrequencyInfo/bad_input.ll

13 ↗

(On Diff #42793)

The original code doesn't call Src->getSuccProbability(Dst).getNumerator(). Note that here we are using BPI not MBPI, and MBPI does have an interface getEdgeWeight() that calls getNumerator() from BP. But for BPI we don't do similar things.

[congh]

Change the name convertBranchProbabilityToWeight() into getWeightFromBranchProb().

[davidxl]

test/Analysis/BlockFrequencyInfo/bad_input.ll

13 ↗

(On Diff #42795)

I know FE does that (0->1) when creating MD_prof metadata. Where in BFI that does similar thing?

[congh]

test/Analysis/BlockFrequencyInfo/bad_input.ll

13 ↗

(On Diff #42795)

It is done in BlockFrequencyInfoImplBase::addToDist():

bool BlockFrequencyInfoImplBase::addToDist(Distribution &Dist,

                                         const LoopData *OuterLoop,
                                         const BlockNode &Pred,
                                         const BlockNode &Succ,
                                         uint64_t Weight) {
if (!Weight)
  Weight = 1;

auto isLoopHeader = [&OuterLoop](const BlockNode &Node) {
  return OuterLoop && OuterLoop->isHeader(Node);
};

...

[davidxl]

Ok. This is a case where loop exit edge is 'never' taken where the loop backedge is executed. With instrumentation based PGO, even without FE fix up of the 0 weight edge, such as scenario (aka, bad meta data) will never occur, so whatever output of BFI will be fine.

However, with AutoFDO, such MD_prof data can actually be generated . For instance, the function has a single BB loop, and only the BB in the loop has some samples but the entry/exit BB has none.

The BFI result before this patch will most likely under-estimate the loop trip count, while with this patch, it will most likely over-estimate it. I think neither results are ideal, and AutoFDO needs to do something (apply some heuristic) to prevent such case from being generated. +dehao and +dnovillo for comments.

[danielcdh]

For the following CFG:

BB1(weight:100)
BB2(weight:1000)
BB3(weight:100)

BB1->BB2(probability: 0%)
BB1->BB3(probability: 100%)
BB2->BB2(probability: 100%)
BB2->BB3(probability: 0%)

Is there a way we can rebuild BB weights from probability?
Dehao

[davidxl]

Looks good to me, but make sure AutoFDO handles (0 weight) case as well.

[congh]

In D15489#313974, @davidxl wrote:

Looks good to me, but make sure AutoFDO handles (0 weight) case as well.

I will work with Dehao to make sure this will be done.

llvm/trunk/include/llvm/Analysis/BlockFrequencyInfoImpl.h

void BlockFrequencyInfoImpl<BT>::computeIrreducibleMass(
   for (auto &L : analyzeIrreducible(G, OuterLoop, Insert))
     computeMassInLoop(L);
 
   if (!OuterLoop)
     return;
   updateLoopWithIrreducible(*OuterLoop);
 }
 
+namespace {
+// A helper function that converts a branch probability into weight.
+inline uint32_t getWeightFromBranchProb(const BranchProbability Prob) {
+  return Prob.getNumerator();
+}
+} // namespace
+
 template <class BT>
 bool
 BlockFrequencyInfoImpl<BT>::propagateMassToSuccessors(LoopData *OuterLoop,
                                                       const BlockNode &Node) {
   DEBUG(dbgs() << " - node: " << getBlockName(Node) << "\n");
   // Calculate probability for successors.
   Distribution Dist;
   if (auto *Loop = Working[Node.Index].getPackagedLoop()) {
     assert(Loop != OuterLoop && "Cannot propagate mass in a packaged loop");
     if (!addLoopSuccessorsToDist(OuterLoop, *Loop, Dist))
       // Irreducible backedge.
       return false;
   } else {
     const BlockT *BB = getBlock(Node);
     for (auto SI = Successor::child_begin(BB), SE = Successor::child_end(BB);
          SI != SE; ++SI)
-      // Do not dereference SI, or getEdgeWeight() is linear in the number of
-      // successors.
       if (!addToDist(Dist, OuterLoop, Node, getNode(*SI),
-                     BPI->getEdgeWeight(BB, SI)))
+                     getWeightFromBranchProb(BPI->getEdgeProbability(BB, SI))))
         // Irreducible backedge.
         return false;
   }
 
   // Distribute mass to successors, saving exit and backedge data in the
   // loop header.
   distributeMass(Node, OuterLoop, Dist);
   return true;

llvm/trunk/include/llvm/CodeGen/MachineBranchProbabilityInfo.h

MachineBranchProbabilityInfo() : ImmutablePass(ID) {
     PassRegistry &Registry = *PassRegistry::getPassRegistry();
     initializeMachineBranchProbabilityInfoPass(Registry);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesAll();
   }
 
-  // Return edge weight. If we don't have any informations about it - return
-  // DEFAULT_WEIGHT.
-  uint32_t getEdgeWeight(const MachineBasicBlock *Src,
-                         const MachineBasicBlock *Dst) const;
-
-  // Same thing, but using a const_succ_iterator from Src. This is faster when
-  // the iterator is already available.
-  uint32_t getEdgeWeight(const MachineBasicBlock *Src,
-                         MachineBasicBlock::const_succ_iterator Dst) const;
-
   // Return edge probability.
   BranchProbability getEdgeProbability(const MachineBasicBlock *Src,
                                        const MachineBasicBlock *Dst) const;
 
   // Same as above, but using a const_succ_iterator from Src. This is faster
   // when the iterator is already available.
   BranchProbability
   getEdgeProbability(const MachineBasicBlock *Src,

llvm/trunk/lib/CodeGen/MachineBranchProbabilityInfo.cpp

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::getEdgeWeight(
-    const MachineBasicBlock *Src,
-    MachineBasicBlock::const_succ_iterator Dst) const {
-  return Src->getSuccProbability(Dst).getNumerator();
-}
-
-uint32_t MachineBranchProbabilityInfo::getEdgeWeight(
-    const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const {
-  // This is a linear search. Try to use the const_succ_iterator version when
-  // possible.
-  return getEdgeWeight(Src, std::find(Src->succ_begin(), Src->succ_end(), Dst));
-}
-
 BranchProbability MachineBranchProbabilityInfo::getEdgeProbability(
     const MachineBasicBlock *Src,
     MachineBasicBlock::const_succ_iterator Dst) const {
   return Src->getSuccProbability(Dst);
 }
 
 BranchProbability MachineBranchProbabilityInfo::getEdgeProbability(
     const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const {

llvm/trunk/test/Analysis/BlockFrequencyInfo/bad_input.ll

 ; RUN: opt < %s -analyze -block-freq | FileCheck %s
 
 declare void @g(i32 %x)
 
 ; CHECK-LABEL: Printing analysis {{.*}} for function 'branch_weight_0':
 ; CHECK-NEXT: block-frequency-info: branch_weight_0
 define void @branch_weight_0(i32 %a) {
 ; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 entry:
   br label %for.body
 
-; Check that we get 1,4 instead of 0,3.
-; CHECK-NEXT: for.body: float = 4.0,
+; Check that we get 1 and a huge frequency instead of 0,3.
+; CHECK-NEXT: for.body: float = 2147483647.8,
 for.body:
   %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   call void @g(i32 %i)
   %inc = add i32 %i, 1
   %cmp = icmp ugt i32 %inc, %a
   br i1 %cmp, label %for.end, label %for.body, !prof !0
 
 ; CHECK-NEXT: for.end: float = 1.0, int = [[ENTRY]]