Mark BB as annotated if its weight is > 0

[danielcdh]

Summary

Mark BB as annotated if its weight is > 0, otherwise the propagation algorithm will not be able to propagate edge weights.

[dnovillo]

LGTM with a test case.

Thanks.

[danielcdh]

Update reviewer

[danielcdh]

Add reviewers.

[danielcdh]

Add unittest to fix propagation. This equivalence class based method is still incorrect. I will have a separate patch to fix equivalence class bug.

[davidxl]

lib/Transforms/IPO/SampleProfile.cpp

242

I think it is clearer to rename this method 'setBlockWeight' -- what it does is to read from the samples and set the cached weight for BB and mark it as annotated.

486

Should use annotated EC's weight.

580

There seems to be a missing step to propagate weights from annotated BBs to their equivalence classes -- the later should be used in Edge propagation

[danielcdh]

lib/Transforms/IPO/SampleProfile.cpp

242

In another patch http://reviews.llvm.org/D13231, I changed getBlockWeight as a const member function and removed the caching (because there is no reuse), and move the setting of BlockWeights outside this function.

486

That's correct. I'll have a separate patch to fix the EC's propagation.

[dnovillo]

Let me back up a little bit. If getBlockWeight() marks the block visited all the time, then how can propagation work? getBlockWeight is only used when computing the *initial* weight of the blocks (I agree with David, it should be renamed to setBlockWeight()).

But, in looking at the code again, it doesn't seem correct to mark the block visited there. We mark them visited when we are assigning equivalence classes.

I think I'm missing something here.

[danielcdh]

computeBlockWeights assigns weights to basic blocks that has profile data and mark them as annotated. But after this step, there will still be basic blocks that are not annotated. So the propagation step works on 3 things:

• set edge weights and mark it as annotated
• set basic block weights for those unannotated basic blocks and mark them as annotated
• adjust basic block weights for those annotated basic blocks which has apparently incorrect weights

Equivalence class is not the place to set the annotated flag, it just sets the equivalence class for each basic block. In later propagation algorithm, instead of checking "IsAnnotated(BB)", we should check "IsAnnotated(BB->equivalence_class)".

Dehao

[dnovillo]

lib/Transforms/IPO/SampleProfile.cpp

310

clang-format this? I think it will now fit on the same line.

[danielcdh]

clang-format

[danielcdh]

rerun clang-format.

[dnovillo]

LGTM

[danielcdh]

This change exposed many errors in the original test input. Thus I integrated the EC related change into this patch so that I only need to update the test input once.

Diego and David, please help take another look at the patch. With this patch, the propagation should be very robust now.

[dnovillo]

Patch looks fine. Just a couple of final questions.

include/llvm/ProfileData/SampleProf.h

221 ↗

(On Diff #36060)

Sadly, I don't think there is a test case for this check I had added. With your new changes, we can now distinguish 0 from missing sample all the time, right?

lib/Transforms/IPO/SampleProfile.cpp

375

Not sure why we don't process blocks post-dominated by BB1 anymore?

[danielcdh]

include/llvm/ProfileData/SampleProf.h

221 ↗

(On Diff #36060)

Yes, now GetBlockCount will return std::error_code if there is no profile.

lib/Transforms/IPO/SampleProfile.cpp

375

Processing dominators should be able to cover all ECs, this is because if BB1 dominates BB2, and BB1 and BB2 are in the same EC, then BB2 also post-dominates BB1.

[danielcdh]

submitted

lib/Transforms/IPO/SampleProfile.cpp

 ///
 /// The weight of basic block \p BB is the maximum weight of all the
 /// instructions in BB. The weight of \p BB is computed and cached in
 /// the BlockWeights map.
 ///
 /// \param BB The basic block to query.
 ///
 /// \returns The computed weight of BB.
 unsigned SampleProfileLoader::getBlockWeight(BasicBlock *BB) {
   // If we've computed BB's weight before, return it.
   std::pair<BlockWeightMap::iterator, bool> Entry =
       BlockWeights.insert(std::make_pair(BB, 0));
   if (!Entry.second)
     return Entry.first->second;
 
   // Otherwise, compute and cache BB's weight.
   unsigned Weight = 0;
   for (auto &I : BB->getInstList()) {
     unsigned InstWeight = getInstWeight(I);
     if (InstWeight > Weight)
       Weight = InstWeight;
   }
+  if (Weight > 0)
+    VisitedBlocks.insert(BB);
   Entry.first->second = Weight;
   return Weight;
 }
 
 /// \brief Compute and store the weights of every basic block.
 ///
 /// This populates the BlockWeights map by computing
 /// the weights of every basic block in the CFG.

 ///                 this is the post-dominator tree, and vice versa.
 void SampleProfileLoader::findEquivalencesFor(
     BasicBlock *BB1, SmallVector<BasicBlock *, 8> Descendants,
     DominatorTreeBase<BasicBlock> *DomTree) {
   for (auto *BB2 : Descendants) {
     bool IsDomParent = DomTree->dominates(BB2, BB1);
     bool IsInSameLoop = LI->getLoopFor(BB1) == LI->getLoopFor(BB2);
     if (BB1 != BB2 && VisitedBlocks.insert(BB2).second && IsDomParent &&
         IsInSameLoop) {
       EquivalenceClass[BB2] = BB1;
 
       // If BB2 is heavier than BB1, make BB2 have the same weight
       // as BB1.
       //
       // Note that we don't worry about the opposite situation here
       // (when BB2 is lighter than BB1). We will deal with this
       // during the propagation phase. Right now, we just want to
for (auto &BB : F) {
     //
     // 1- BB1 post-dominates BB2.
     // 2- BB2 dominates BB1.
     // 3- BB1 and BB2 are in the same loop nest.
     //
     // If all those conditions hold, BB2's equivalence class is BB1.
     DominatedBBs.clear();
     PDT->getDescendants(BB1, DominatedBBs);
     findEquivalencesFor(BB1, DominatedBBs, DT.get());
 
     DEBUG(printBlockEquivalence(dbgs(), BB1));
   }
 
   // Assign weights to equivalence classes.
   //
   // All the basic blocks in the same equivalence class will execute
   // the same number of times. Since we know that the head block in
for (unsigned i = 0; i < 2; i++) {
       //   known. In this case, this edge can be based on BB's weight.
       //   We add up all the other known edges and set the weight on
       //   the self-referential edge as we did in the previous case.
       //
       // In any other case, we must continue iterating. Eventually,
       // all edges will get a weight, or iteration will stop when
       // it reaches SampleProfileMaxPropagateIterations.
       if (NumUnknownEdges <= 1) {
         unsigned &BBWeight = BlockWeights[BB];
         if (NumUnknownEdges == 0) {
           // If we already know the weight of all edges, the weight of the
           // basic block can be computed. It should be no larger than the sum
           // of all edge weights.
           if (TotalWeight > BBWeight) {
             BBWeight = TotalWeight;
             Changed = true;
             DEBUG(dbgs() << "All edge weights for " << BB->getName()

 ///
 /// - If there is a self-referential edge, and the weight of the block is
 ///   known, the weight for that edge is set to the weight of the block
 ///   minus the weight of the other incoming edges to that block (if
 ///   known).
 void SampleProfileLoader::propagateWeights(Function &F) {
   bool Changed = true;
   unsigned i = 0;
 
   // Add an entry count to the function using the samples gathered
   // at the function entry.
   F.setEntryCount(Samples->getHeadSamples());
 
   // Before propagation starts, build, for each block, a list of
   // unique predecessors and successors. This is necessary to handle
   // identical edges in multiway branches. Since we visit all blocks and all
   // edges of the CFG, it is cleaner to build these lists once at the start