[BlockFrequencyInfo] NFC. Add DEBUG output for irregular CFG handling

[kula]

Summary

Add DEBUG output for irregular CFG handling

[dexonsmith]

I missed this until now; if this still applies, it LGTM.

include/llvm/Analysis/BlockFrequencyInfoImpl.h

 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/Support/BlockFrequency.h"
 #include "llvm/Support/BranchProbability.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/Format.h"
 #include "llvm/Support/ScaledNumber.h"
 #include "llvm/Support/raw_ostream.h"
 #include <deque>
 #include <list>
 #include <map>
 #include <string>
 #include <vector>
 
for (auto I = Successor::child_begin(BB), E = Successor::child_end(BB);
       G.addEdge(Irr, BFI.getNode(*I), OuterLoop);
   }
 };
 }
 template <class BT>
 void BlockFrequencyInfoImpl<BT>::computeStartTerm(
     GeometricMeanInfo &HeaderData, LoopData *Loop, SCCLoopVecTy &SubLoops,
     NodeVecTy &LeftSCCs, std::list<LoopData>::iterator Insert) {
+  DEBUG(dbgs() << "compute start terms\n");
   for (auto &S : SubLoops) {
     // First propagate mass on subloop's dependence nodes.
     for (const auto Node : S.second)
       if (!propagateMassToSuccessors(Loop, Node, true))
         llvm_unreachable("unhandled irreducible control flow");
 
     // Save accumulated header mass of current subloop. After local mass of
     // current subloop is recursively computed, we use this total mass to
void BlockFrequencyInfoImpl<BT>::computeStartTerm(
   for (const auto &I : Loop->BackedgeMass)
     Working[I.first.Index].getMass() += I.second;
 
   // Save all start terms
   for (uint32_t H = 0; H < Loop->NumHeaders; ++H) {
     auto &HeaderNode = Loop->Nodes[H];
     auto &HeaderMass = Working[HeaderNode.Index].getMass();
     HeaderData[HeaderNode].first = HeaderMass;
+    DEBUG(dbgs() << "header start term mass = " << HeaderMass << " ["
+                 << HeaderMass.toScaled() << "] (" << getBlockName(HeaderNode)
+                 << ")\n");
   }
 }
 
 template <class BT>
 void BlockFrequencyInfoImpl<BT>::computeGeometricRatio(
     GeometricMeanInfo &HeaderData, LoopData &Loop) {
+  DEBUG(dbgs() << "compute geometric ratio\n");
   Loop.Scale = BlockMass::getFull().toScaled();
   LoopData::NodeList SortedNodes = Loop.Nodes;
   std::sort(SortedNodes.begin(), SortedNodes.end());
   for (uint32_t H = 0; H < Loop.NumHeaders; ++H) {
     Loop.BackedgeMass.clear();
     for (auto N : SortedNodes)
       Working[N.Index].getMass() = BlockMass::getEmpty();
 
for (const auto &I : Loop.BackedgeMass)
         HeaderData[HeaderNode].second += I.second;
 
     // compute ratio to find loop scale.
     // TODO use a(1-r^n)/(1-r) requires n, which a the loop scale we could have
     // computed during start term computing propagation. Here it is simplified
     // to use a/(1-r).
     BlockMass LeftMass = BlockMass::getFull() - HeaderData[HeaderNode].second;
     Scaled64 S = LeftMass.toScaled().inverse();
+    DEBUG(dbgs() << "header ratio = " << S << " (" << getBlockName(HeaderNode)
+                 << ")\n");
     if (S > Loop.Scale)
       Loop.Scale = S;
   }
 }
 
 template <class BT>
 void BlockFrequencyInfoImpl<BT>::computeScaledBlockMass(
     GeometricMeanInfo &HeaderData, LoopData &Loop) {
void BlockFrequencyInfoImpl<BT>::computeIrreducibleMass(
   SCCLoopVecTy SubLoops;
   createSCCLoop(Loop, G, Insert, LeftSCCs, SubLoops);
 
   // To calculate the geometirc series, we need start term(a) and ratio(r). The
   // final block freq is a/(1-r).
   GeometricMeanInfo HeaderData;
 
   // Distribute mass among headers according to their input relative weight.
+  DEBUG(dbgs() << "distribute full mass among headers\n");
+  for (const Weight &W : Dist.Weights)
+    DEBUG(dbgs() << "  header weight = "
+                 << format("%*" PRIu64,
+                           std::snprintf(nullptr, 0, "%" PRIu64,
+                                         std::numeric_limits<uint64_t>::max()),
+                           W.Amount)
+                 << " (" << getBlockName(W.TargetNode) << ")\n");
   distributeMass(BlockMass::getFull(), nullptr, Dist);
 
   computeStartTerm(HeaderData, Loop, SubLoops, LeftSCCs, Insert);
   if (!Loop)
     return;
   if (Loop->isIrreducible()) {
     computeGeometricRatio(HeaderData, *Loop);
     computeScaledBlockMass(HeaderData, *Loop);

lib/Analysis/BlockFrequencyInfoImpl.cpp

 /// \brief Package up a loop.
 void BlockFrequencyInfoImplBase::packageLoop(LoopData &Loop) {
   DEBUG(dbgs() << "packaging-loop: " << getLoopName(Loop) << "\n");
 
   // Clear the subloop exits to prevent quadratic memory usage.
   for (const BlockNode &M : Loop.Nodes) {
     if (auto *Loop = Working[M.Index].getPackagedLoop())
       Loop->Exits.clear();
-    DEBUG(dbgs() << " - node: " << getBlockName(M.Index) << "\n");
+    DEBUG(dbgs() << " *- node: " << getBlockName(M.Index) << "\n");
   }
   Loop.IsPackaged = true;
 }
 
 #ifndef NDEBUG
 static void debugAssign(const BlockFrequencyInfoImplBase &BFI,
                         const DitheringDistributer &D, const BlockNode &T,
                         const BlockMass &M, const char *Desc) {
if (OuterLoop && !I->second)
           break;
         }
 
     if (I->second) {
       Headers.push_back(Irr.Node);
       DEBUG(dbgs() << "  => entry = " << BFI.getBlockName(Irr.Node) << "\n");
     } else {
       Others.push_back(Irr.Node);
+      DEBUG(dbgs() << "  => other = " << BFI.getBlockName(Irr.Node) << "\n");
     }
   }
   assert(Headers.size() >= 2 &&
          "Expected irreducible CFG; -loop-info is likely invalid");
   std::sort(Headers.begin(), Headers.end());
   std::sort(Others.begin(), Others.end());
 }
 
void BlockFrequencyInfoImplBase::createSCCLoop(
     SCCLoopVecTy &SubSCCs) {
   // Must get all sccs before descend since SCCIterator returns inverse
   // topological order.
   LoopData *PrevLoop = nullptr;
   NodeVecTy SingleSCCs;
   for (auto I = scc_begin(G); !I.isAtEnd(); ++I)
     if (I->size() < 2) {
       assert(I->size() == 1);
+      DEBUG(dbgs() << " - found-trivial-scc " << getBlockName((*I)[0]->Node)
+                   << "\n");
       SingleSCCs.insert(SingleSCCs.begin(), (*I)[0]->Node);
     } else {
       // Translate the SCC into RPO.
       auto L = createIrreducibleLoop(*this, G, OuterLoop, Insert, *I);
       // SCCIterator gives reverse topological order, make it normal
       if (PrevLoop)
         SubSCCs.insert(SubSCCs.begin(), std::make_pair(PrevLoop, SingleSCCs));
       else