Support of CFG dot dump with layout annotation after MBP pass

[davidxl]

Summary

There is currently no way to view CFG graphically with layout decision after MBP pass. Developers currently rely on debug text dump to debug layout related bugs.

This patch adds the capability to dump/view cfg dump file after MBP pass. It enhances the existing MBFI graph dumping with an optional functionality to display the layout order of an machine basic block. The order of a basic block is displayed as a sequence number encoded in brackets [] after the block name string. The graph will also show branch probabilities and frequencies/count information.

The option is:

-mllvm -view-block-layout-with-bfi=[integer|fraction|count]

To filter, do -mllvm -view-bfi-func-name=<name>

Example for CodeGen/PowerPC/tail-dup-layout.ll

1. block layout with tailduplication enabled:

https://reviews.llvm.org/F3024165

2. block layout with tail-dup disabled:

https://reviews.llvm.org/F3024166

[davidxl]

Remove redundant lines.

[vsk]

include/llvm/Analysis/BlockFrequencyInfoImpl.h

1301

'.str()' shouldn't be needed in either branch.

lib/CodeGen/MachineBlockFrequencyInfo.cpp

117

Can we just use Node->getNumber() here? IIUC it's available so long as the MBB is in a MachineFunc, which we appear to be assuming?

[davidxl]

include/llvm/Analysis/BlockFrequencyInfoImpl.h

1301

ok

lib/CodeGen/MachineBlockFrequencyInfo.cpp

117

It is tempting but the requires invoking MF.RenumberBlocks() which has side effects. A debug option should not change optimizer behavior.

[vsk]

LGTM.

lib/CodeGen/MachineBlockFrequencyInfo.cpp

117

Oh, I see, MBB.Number starts off as -1 without RenumberBlocks().

[davidxl]

addressed review feedback.

include/llvm/Analysis/BlockFrequencyInfoImpl.h

 
     raw_string_ostream OS(Result);
     OS << "color=\"red\"";
     OS.flush();
     return Result;
   }
 
   std::string getNodeLabel(NodeRef Node, const BlockFrequencyInfoT *Graph,
-                           GVDAGType GType) {
+                           GVDAGType GType, int layout_order = -1) {
     std::string Result;
     raw_string_ostream OS(Result);
 
-    OS << Node->getName().str() << " : ";
+    if (layout_order != -1)
+      OS << Node->getName() << "[" << layout_order << "] : ";
+    else
+      OS << Node->getName() << " : ";
     switch (GType) {
     case GVDT_Fraction:
       Graph->printBlockFreq(OS, Node);
       break;
     case GVDT_Integer:
       OS << Graph->getBlockFreq(Node).getFrequency();
       break;
     case GVDT_Count: {

include/llvm/CodeGen/MachineBlockFrequencyInfo.h

public:
   ///
   BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const;
 
   Optional<uint64_t> getBlockProfileCount(const MachineBasicBlock *MBB) const;
   Optional<uint64_t> getProfileCountFromFreq(uint64_t Freq) const;
 
   const MachineFunction *getFunction() const;
   const MachineBranchProbabilityInfo *getMBPI() const;
-  void view() const;
+  void view(bool isSimple = true) const;
 
   // Print the block frequency Freq to OS using the current functions entry
   // frequency to convert freq into a relative decimal form.
   raw_ostream &printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const;
 
   // Convenience method that attempts to look up the frequency associated with
   // BB and print it to OS.
   raw_ostream &printBlockFreq(raw_ostream &OS,

lib/CodeGen/BranchFolding.h

public:
     public:
       MBFIWrapper(const MachineBlockFrequencyInfo &I) : MBFI(I) {}
       BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const;
       void setBlockFreq(const MachineBasicBlock *MBB, BlockFrequency F);
       raw_ostream &printBlockFreq(raw_ostream &OS,
                                   const MachineBasicBlock *MBB) const;
       raw_ostream &printBlockFreq(raw_ostream &OS,
                                   const BlockFrequency Freq) const;
+      void view(bool isSimple = true);
 
     private:
       const MachineBlockFrequencyInfo &MBFI;
       DenseMap<const MachineBasicBlock *, BlockFrequency> MergedBBFreq;
     };
 
   private:
     MBFIWrapper &MBBFreqInfo;

lib/CodeGen/BranchFolding.cpp

 }
 
 raw_ostream &
 BranchFolder::MBFIWrapper::printBlockFreq(raw_ostream &OS,
                                           const BlockFrequency Freq) const {
   return MBFI.printBlockFreq(OS, Freq);
 }
 
+void BranchFolder::MBFIWrapper::view(bool isSimple) { MBFI.view(isSimple); }
+
 /// CountTerminators - Count the number of terminators in the given
 /// block and set I to the position of the first non-terminator, if there
 /// is one, or MBB->end() otherwise.
 static unsigned CountTerminators(MachineBasicBlock *MBB,
                                  MachineBasicBlock::iterator &I) {
   I = MBB->end();
   unsigned NumTerms = 0;
   for (;;) {

lib/CodeGen/MachineBlockFrequencyInfo.cpp

cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."),
                clEnumValN(GVDT_Fraction, "fraction",
                           "display a graph using the "
                           "fractional block frequency representation."),
                clEnumValN(GVDT_Integer, "integer",
                           "display a graph using the raw "
                           "integer fractional block frequency representation."),
                clEnumValN(GVDT_Count, "count", "display a graph using the real "
                                                "profile count if available.")));
+// Similar option above, but used to control BFI display only after MBP pass
+cl::opt<GVDAGType> ViewBlockLayoutWithBFI(
+    "view-block-layout-with-bfi", cl::Hidden,
+    cl::desc(
+        "Pop up a window to show a dag displaying MBP layout and associated "
+        "block frequencies of the CFG."),
+    cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."),
+               clEnumValN(GVDT_Fraction, "fraction",
+                          "display a graph using the "
+                          "fractional block frequency representation."),
+               clEnumValN(GVDT_Integer, "integer",
+                          "display a graph using the raw "
+                          "integer fractional block frequency representation."),
+               clEnumValN(GVDT_Count, "count",
+                          "display a graph using the real "
+                          "profile count if available.")));
 
 extern cl::opt<std::string> ViewBlockFreqFuncName;
 extern cl::opt<unsigned> ViewHotFreqPercent;
 
+static GVDAGType getGVDT() {
+  if (ViewBlockLayoutWithBFI != GVDT_None)
+    return ViewBlockLayoutWithBFI;
+
+  return ViewMachineBlockFreqPropagationDAG;
+}
+
 namespace llvm {
 
 template <> struct GraphTraits<MachineBlockFrequencyInfo *> {
   typedef const MachineBasicBlock *NodeRef;
   typedef MachineBasicBlock::const_succ_iterator ChildIteratorType;
   typedef pointer_iterator<MachineFunction::const_iterator> nodes_iterator;
 
   static NodeRef getEntryNode(const MachineBlockFrequencyInfo *G) {

 
 typedef BFIDOTGraphTraitsBase<MachineBlockFrequencyInfo,
                               MachineBranchProbabilityInfo>
     MBFIDOTGraphTraitsBase;
 template <>
 struct DOTGraphTraits<MachineBlockFrequencyInfo *>
     : public MBFIDOTGraphTraitsBase {
   explicit DOTGraphTraits(bool isSimple = false)
-      : MBFIDOTGraphTraitsBase(isSimple) {}
+      : MBFIDOTGraphTraitsBase(isSimple), CurFunc(nullptr), LayoutOrderMap() {}
+
+  const MachineFunction *CurFunc;
+  DenseMap<const MachineBasicBlock *, int> LayoutOrderMap;
 
   std::string getNodeLabel(const MachineBasicBlock *Node,
                            const MachineBlockFrequencyInfo *Graph) {
-    return MBFIDOTGraphTraitsBase::getNodeLabel(
-        Node, Graph, ViewMachineBlockFreqPropagationDAG);
+
+    int layout_order = -1;
+    // Attach additional ordering information if 'isSimple' is false.
+    if (!isSimple()) {
+      const MachineFunction *F = Node->getParent();
+      if (!CurFunc || F != CurFunc) {
+        if (CurFunc)
+          LayoutOrderMap.clear();
+
+        CurFunc = F;
+        int O = 0;
+        for (auto MBI = F->begin(); MBI != F->end(); ++MBI, ++O) {
+          LayoutOrderMap[&*MBI] = O;
+        }
+      }
+      layout_order = LayoutOrderMap[Node];
+    }
+    return MBFIDOTGraphTraitsBase::getNodeLabel(Node, Graph, getGVDT(),
+                                                layout_order);
   }
 
   std::string getNodeAttributes(const MachineBasicBlock *Node,
                                 const MachineBlockFrequencyInfo *Graph) {
     return MBFIDOTGraphTraitsBase::getNodeAttributes(Node, Graph,
                                                      ViewHotFreqPercent);
   }
 

 #endif
   return false;
 }
 
 void MachineBlockFrequencyInfo::releaseMemory() { MBFI.reset(); }
 
 /// Pop up a ghostview window with the current block frequency propagation
 /// rendered using dot.
-void MachineBlockFrequencyInfo::view() const {
+void MachineBlockFrequencyInfo::view(bool isSimple) const {
 // This code is only for debugging.
 #ifndef NDEBUG
   ViewGraph(const_cast<MachineBlockFrequencyInfo *>(this),
-            "MachineBlockFrequencyDAGs");
+            "MachineBlockFrequencyDAGs", isSimple);
 #else
   errs() << "MachineBlockFrequencyInfo::view is only available in debug builds "
             "on systems with Graphviz or gv!\n";
 #endif // NDEBUG
 }
 
 BlockFrequency
 MachineBlockFrequencyInfo::getBlockFreq(const MachineBasicBlock *MBB) const {

lib/CodeGen/MachineBlockPlacement.cpp

 
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "BranchFolding.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/BlockFrequencyInfoImpl.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
static cl::opt<unsigned> TailDuplicatePlacementThreshold(
     cl::desc("Instruction cutoff for tail duplication during layout. "
              "Tail merging during layout is forced to have a threshold "
              "that won't conflict."), cl::init(2),
     cl::Hidden);
 
 extern cl::opt<unsigned> StaticLikelyProb;
 extern cl::opt<unsigned> ProfileLikelyProb;
 
+#ifndef NDEBUG
+extern cl::opt<GVDAGType> ViewBlockLayoutWithBFI;
+extern cl::opt<std::string> ViewBlockFreqFuncName;
+#endif
+
 namespace {
 class BlockChain;
 /// \brief Type for our function-wide basic block -> block chain mapping.
 typedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType;
 }
 
 namespace {
 /// \brief A chain of blocks which will be laid out contiguously.
else if (AlignAllNonFallThruBlocks) {
     // Align all of the blocks that have no fall-through predecessors to a
     // specific alignment.
     for (auto MBI = std::next(MF.begin()), MBE = MF.end(); MBI != MBE; ++MBI) {
       auto LayoutPred = std::prev(MBI);
       if (!LayoutPred->isSuccessor(&*MBI))
         MBI->setAlignment(AlignAllNonFallThruBlocks);
     }
   }
+#ifndef NDEBUG
+  if (ViewBlockLayoutWithBFI != GVDT_None &&
+      (ViewBlockFreqFuncName.empty() ||
+       F->getFunction()->getName().equals(ViewBlockFreqFuncName))) {
+    MBFI->view(false);
+  }
+#endif
+
 
   // We always return true as we have no way to track whether the final order
   // differs from the original order.
   return true;
 }
 
 namespace {
 /// \brief A pass to compute block placement statistics.