Heat Coloring (1/3): Adding distinct structure for CFGDOTInfo

[knaumov]

Summary

This patch is the first in the sequence of three patches related to the following diff (https://reviews.llvm.org/D73142). It introduces the system to distinctively store the information needed for the Control Flow Graph as well as the instrumentary needed for the follow-up changes: BlockFrequencyInfo and BranchProbabilityInfo.
It is the biggest review from the three as it also changes the code that is related to CFG from other files.

[davidxl]

llvm/include/llvm/Analysis/CFGPrinter.h

56–99

nit: this class just wraps function pointer and function level information in it. Maybe name it DOTFuncInfo?

[knaumov]

Renamed the structure:
CFGDOTInfo -> DOTFuncInfo

[davidxl]

lgtm

[knaumov]

Excellent!
Can anyone with the commit access make a push of this patch?

[davidxl]

Given that you have series of patches to be pushed, perhaps just get the write permission?

llvm/include/llvm/Analysis/CFGPrinter.h

 // This file defines external functions that can be called to explicitly
 // instantiate the CFG printer.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_CFGPRINTER_H
 #define LLVM_ANALYSIS_CFGPRINTER_H
 
+#include "llvm/Analysis/BlockFrequencyInfo.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/GraphWriter.h"
 
 namespace llvm {
 class CFGViewerPass
     : public PassInfoMixin<CFGViewerPass> {
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };

 };
 
 class CFGOnlyPrinterPass
     : public PassInfoMixin<CFGOnlyPrinterPass> {
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
 
-template<>
-struct DOTGraphTraits<const Function*> : public DefaultDOTGraphTraits {
+class DOTFuncInfo {
+private:
+  const Function *F;
+  const BlockFrequencyInfo *BFI;
+  const BranchProbabilityInfo *BPI;
+
+public:
+  DOTFuncInfo(const Function *F) : DOTFuncInfo(F, nullptr, nullptr) {}
+
+  DOTFuncInfo(const Function *F, const BlockFrequencyInfo *BFI,
+             BranchProbabilityInfo *BPI)
+      : F(F), BFI(BFI), BPI(BPI) {
+  }
+
+  const BlockFrequencyInfo *getBFI() { return BFI; }
+
+  const BranchProbabilityInfo *getBPI() { return BPI; }
+
+  const Function *getFunction() { return this->F; }
+};
+
+template <>
+struct GraphTraits<DOTFuncInfo *> : public GraphTraits<const BasicBlock *> {
+  static NodeRef getEntryNode(DOTFuncInfo *CFGInfo) {
+    return &(CFGInfo->getFunction()->getEntryBlock());
+  }
+
+  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
+  using nodes_iterator = pointer_iterator<Function::const_iterator>;
+
+  static nodes_iterator nodes_begin(DOTFuncInfo *CFGInfo) {
+    return nodes_iterator(CFGInfo->getFunction()->begin());
+  }
+
+  static nodes_iterator nodes_end(DOTFuncInfo *CFGInfo) {
+    return nodes_iterator(CFGInfo->getFunction()->end());
+  }
+
+  static size_t size(DOTFuncInfo *CFGInfo) {
+    return CFGInfo->getFunction()->size();
+  }
+};
+
+template <> struct DOTGraphTraits<DOTFuncInfo *> : public DefaultDOTGraphTraits {
 
   // Cache for is hidden property
   llvm::DenseMap <const BasicBlock *, bool> isHiddenBasicBlock;
 
   DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
 
-  static std::string getGraphName(const Function *F) {
-    return "CFG for '" + F->getName().str() + "' function";
+  static std::string getGraphName(DOTFuncInfo *CFGInfo) {
+    return "CFG for '" + CFGInfo->getFunction()->getName().str() + "' function";
   }
 
-  static std::string getSimpleNodeLabel(const BasicBlock *Node,
-                                        const Function *) {
+  static std::string getSimpleNodeLabel(const BasicBlock *Node, DOTFuncInfo *) {
     if (!Node->getName().empty())
       return Node->getName().str();
 
     std::string Str;
     raw_string_ostream OS(Str);
 
     Node->printAsOperand(OS, false);
     return OS.str();
   }
 
   static std::string getCompleteNodeLabel(const BasicBlock *Node,
-                                          const Function *) {
+                                          DOTFuncInfo *) {
     enum { MaxColumns = 80 };
     std::string Str;
     raw_string_ostream OS(Str);
 
     if (Node->getName().empty()) {
       Node->printAsOperand(OS, false);
       OS << ":";
     }
for (unsigned i = 0; i != OutStr.length(); ++i) {
         ++ColNum;
       if (OutStr[i] == ' ')
         LastSpace = i;
     }
     return OutStr;
   }
 
   std::string getNodeLabel(const BasicBlock *Node,
-                           const Function *Graph) {
+                           DOTFuncInfo *CFGInfo) {
+
     if (isSimple())
-      return getSimpleNodeLabel(Node, Graph);
+      return getSimpleNodeLabel(Node, CFGInfo);
     else
-      return getCompleteNodeLabel(Node, Graph);
+      return getCompleteNodeLabel(Node, CFGInfo);
   }
 
   static std::string getEdgeSourceLabel(const BasicBlock *Node,
                                         const_succ_iterator I) {
     // Label source of conditional branches with "T" or "F"
     if (const BranchInst *BI = dyn_cast<BranchInst>(Node->getTerminator()))
       if (BI->isConditional())
         return (I == succ_begin(Node)) ? "T" : "F";
if (const SwitchInst *SI = dyn_cast<SwitchInst>(Node->getTerminator())) {
       OS << Case.getCaseValue()->getValue();
       return OS.str();
     }
     return "";
   }
 
   /// Display the raw branch weights from PGO.
   std::string getEdgeAttributes(const BasicBlock *Node, const_succ_iterator I,
-                                const Function *F) {
+                                DOTFuncInfo *CFGInfo) {
     const Instruction *TI = Node->getTerminator();
     if (TI->getNumSuccessors() == 1)
       return "";
-
     MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
     if (!WeightsNode)
       return "";
 
     MDString *MDName = cast<MDString>(WeightsNode->getOperand(0));
     if (MDName->getString() != "branch_weights")
       return "";
-
     unsigned OpNo = I.getSuccessorIndex() + 1;
     if (OpNo >= WeightsNode->getNumOperands())
       return "";
     ConstantInt *Weight =
         mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(OpNo));
     if (!Weight)
       return "";
 

llvm/lib/Analysis/CFGPrinter.cpp

static cl::opt<std::string> CFGDotFilenamePrefix(
     cl::desc("The prefix used for the CFG dot file names."));
 
 static cl::opt<bool> HideUnreachablePaths("cfg-hide-unreachable-paths",
             cl::init(false));
 
 static cl::opt<bool> HideDeoptimizePaths("cfg-hide-deoptimize-paths",
             cl::init(false));
 
+static void writeCFGToDotFile(Function &F, BlockFrequencyInfo *BFI,
+                                 BranchProbabilityInfo *BPI,
+                                 bool isSimple) {
+  std::string Filename =
+      (CFGDotFilenamePrefix + "." + F.getName() + ".dot").str();
+  errs() << "Writing '" << Filename << "'...";
+
+  std::error_code EC;
+  raw_fd_ostream File(Filename, EC, sys::fs::F_Text);
+
+  DOTFuncInfo CFGInfo(&F, BFI, BPI);
+  if (!EC)
+    WriteGraph(File, &CFGInfo, isSimple);
+  else
+    errs() << "  error opening file for writing!";
+  errs() << "\n";
+}
+
+static void viewCFG(Function &F, BlockFrequencyInfo *BFI,
+                                 BranchProbabilityInfo *BPI,
+                                 bool isSimple) {
+  DOTFuncInfo CFGInfo(&F, BFI, BPI);
+  ViewGraph(&CFGInfo, "cfg." + F.getName(), isSimple);
+}
+
 namespace {
   struct CFGViewerLegacyPass : public FunctionPass {
     static char ID; // Pass identifcation, replacement for typeid
     CFGViewerLegacyPass() : FunctionPass(ID) {
       initializeCFGViewerLegacyPassPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override {
-      F.viewCFG();
+      auto *BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
+      auto *BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
+      viewCFG(F, BFI, BPI, /*isSimple=*/false);
       return false;
     }
 
     void print(raw_ostream &OS, const Module* = nullptr) const override {}
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
+      FunctionPass::getAnalysisUsage(AU); // Maybe Change to FunctionPass::...
+      AU.addRequired<BlockFrequencyInfoWrapperPass>();
+      AU.addRequired<BranchProbabilityInfoWrapperPass>();
       AU.setPreservesAll();
     }
   };
 }
 
 char CFGViewerLegacyPass::ID = 0;
 INITIALIZE_PASS(CFGViewerLegacyPass, "view-cfg", "View CFG of function", false, true)
 
 PreservedAnalyses CFGViewerPass::run(Function &F,
                                      FunctionAnalysisManager &AM) {
-  F.viewCFG();
+  auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
+  auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
+  viewCFG(F, BFI, BPI, /*isSimple=*/false);
   return PreservedAnalyses::all();
 }
 
 
 namespace {
   struct CFGOnlyViewerLegacyPass : public FunctionPass {
     static char ID; // Pass identifcation, replacement for typeid
     CFGOnlyViewerLegacyPass() : FunctionPass(ID) {
       initializeCFGOnlyViewerLegacyPassPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override {
-      F.viewCFGOnly();
+      auto *BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
+      auto *BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
+      viewCFG(F, BFI, BPI, /*isSimple=*/false);
       return false;
     }
 
     void print(raw_ostream &OS, const Module* = nullptr) const override {}
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
+      FunctionPass::getAnalysisUsage(AU);
+      AU.addRequired<BlockFrequencyInfoWrapperPass>();
+      AU.addRequired<BranchProbabilityInfoWrapperPass>();
       AU.setPreservesAll();
     }
   };
 }
 
 char CFGOnlyViewerLegacyPass::ID = 0;
 INITIALIZE_PASS(CFGOnlyViewerLegacyPass, "view-cfg-only",
                 "View CFG of function (with no function bodies)", false, true)
 
 PreservedAnalyses CFGOnlyViewerPass::run(Function &F,
                                          FunctionAnalysisManager &AM) {
-  F.viewCFGOnly();
+  auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
+  auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
+  viewCFG(F, BFI, BPI, /*isSimple=*/false);
   return PreservedAnalyses::all();
 }
 
-static void writeCFGToDotFile(Function &F, bool CFGOnly = false) {
-  if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
-     return;
-  std::string Filename =
-      (CFGDotFilenamePrefix + "." + F.getName() + ".dot").str();
-  errs() << "Writing '" << Filename << "'...";
-
-  std::error_code EC;
-  raw_fd_ostream File(Filename, EC, sys::fs::OF_Text);
-
-  if (!EC)
-    WriteGraph(File, (const Function*)&F, CFGOnly);
-  else
-    errs() << "  error opening file for writing!";
-  errs() << "\n";
-}
-
 namespace {
   struct CFGPrinterLegacyPass : public FunctionPass {
     static char ID; // Pass identification, replacement for typeid
     CFGPrinterLegacyPass() : FunctionPass(ID) {
       initializeCFGPrinterLegacyPassPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override {
-      writeCFGToDotFile(F);
+      auto *BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
+      auto *BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
+      writeCFGToDotFile(F, BFI, BPI, /*isSimple=*/false);
       return false;
     }
 
     void print(raw_ostream &OS, const Module* = nullptr) const override {}
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
+      FunctionPass::getAnalysisUsage(AU);
+      AU.addRequired<BlockFrequencyInfoWrapperPass>();
+      AU.addRequired<BranchProbabilityInfoWrapperPass>();
       AU.setPreservesAll();
     }
   };
 }
 
 char CFGPrinterLegacyPass::ID = 0;
 INITIALIZE_PASS(CFGPrinterLegacyPass, "dot-cfg", "Print CFG of function to 'dot' file",
                 false, true)
 
 PreservedAnalyses CFGPrinterPass::run(Function &F,
                                       FunctionAnalysisManager &AM) {
-  writeCFGToDotFile(F);
+  auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
+  auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
+  writeCFGToDotFile(F, BFI, BPI, /*isSimple=*/false);
   return PreservedAnalyses::all();
 }
 
 namespace {
   struct CFGOnlyPrinterLegacyPass : public FunctionPass {
     static char ID; // Pass identification, replacement for typeid
     CFGOnlyPrinterLegacyPass() : FunctionPass(ID) {
       initializeCFGOnlyPrinterLegacyPassPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override {
-      writeCFGToDotFile(F, /*CFGOnly=*/true);
+      auto *BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
+      auto *BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
+      writeCFGToDotFile(F, BFI, BPI, /*isSimple=*/false);
       return false;
     }
     void print(raw_ostream &OS, const Module* = nullptr) const override {}
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
+      FunctionPass::getAnalysisUsage(AU);
+      AU.addRequired<BlockFrequencyInfoWrapperPass>();
+      AU.addRequired<BranchProbabilityInfoWrapperPass>();
       AU.setPreservesAll();
     }
   };
 }
 
 char CFGOnlyPrinterLegacyPass::ID = 0;
 INITIALIZE_PASS(CFGOnlyPrinterLegacyPass, "dot-cfg-only",
    "Print CFG of function to 'dot' file (with no function bodies)",
    false, true)
 
 PreservedAnalyses CFGOnlyPrinterPass::run(Function &F,
                                           FunctionAnalysisManager &AM) {
-  writeCFGToDotFile(F, /*CFGOnly=*/true);
+  auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
+  auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
+  writeCFGToDotFile(F, BFI, BPI, /*isSimple=*/false);
   return PreservedAnalyses::all();
 }
 
 /// viewCFG - This function is meant for use from the debugger.  You can just
 /// say 'call F->viewCFG()' and a ghostview window should pop up from the
 /// program, displaying the CFG of the current function.  This depends on there
 /// being a 'dot' and 'gv' program in your path.
 ///
 void Function::viewCFG() const {
   if (!CFGFuncName.empty() && !getName().contains(CFGFuncName))
      return;
-  ViewGraph(this, "cfg" + getName());
+  DOTFuncInfo CFGInfo(this);
+  ViewGraph(&CFGInfo, "cfg" + getName());
 }
 
 /// viewCFGOnly - This function is meant for use from the debugger.  It works
 /// just like viewCFG, but it does not include the contents of basic blocks
 /// into the nodes, just the label.  If you are only interested in the CFG
 /// this can make the graph smaller.
 ///
 void Function::viewCFGOnly() const {
   if (!CFGFuncName.empty() && !getName().contains(CFGFuncName))
      return;
-  ViewGraph(this, "cfg" + getName(), true);
+  DOTFuncInfo CFGInfo(this);
+  ViewGraph(&CFGInfo, "cfg" + getName(), true);
 }
 
 FunctionPass *llvm::createCFGPrinterLegacyPassPass () {
   return new CFGPrinterLegacyPass();
 }
 
 FunctionPass *llvm::createCFGOnlyPrinterLegacyPassPass () {
   return new CFGOnlyPrinterLegacyPass();
 }
 
-void DOTGraphTraits<const Function *>::computeHiddenNodes(const Function *F) {
+void DOTGraphTraits<DOTFuncInfo *>::computeHiddenNodes(const Function *F) {
   auto evaluateBB = [&](const BasicBlock *Node) {
     if (succ_begin(Node) == succ_end(Node)) {
       const Instruction *TI = Node->getTerminator();
       isHiddenBasicBlock[Node] =
         (HideUnreachablePaths && isa<UnreachableInst>(TI)) ||
         (HideDeoptimizePaths && Node->getTerminatingDeoptimizeCall());
       return;
     }
     isHiddenBasicBlock[Node] = std::all_of(
         succ_begin(Node), succ_end(Node),
         [this](const BasicBlock *BB) { return isHiddenBasicBlock[BB]; });
   };
   /// The post order traversal iteration is done to know the status of
   /// isHiddenBasicBlock for all the successors on the current BB.
   for_each(po_begin(&F->getEntryBlock()), po_end(&F->getEntryBlock()),
            evaluateBB);
 }
 
-bool DOTGraphTraits<const Function *>::isNodeHidden(const BasicBlock *Node) {
+bool DOTGraphTraits<DOTFuncInfo *>::isNodeHidden(const BasicBlock *Node) {
   // If both restricting flags are false, all nodes are displayed.
   if (!HideUnreachablePaths && !HideDeoptimizePaths)
     return false;
   if (isHiddenBasicBlock.find(Node) == isHiddenBasicBlock.end())
     computeHiddenNodes(Node->getParent());
   return isHiddenBasicBlock[Node];
 }

llvm/lib/Analysis/DomPrinter.cpp

std::string getNodeLabel(DomTreeNode *Node, DomTreeNode *Graph) {
 
     BasicBlock *BB = Node->getBlock();
 
     if (!BB)
       return "Post dominance root node";
 
 
     if (isSimple())
-      return DOTGraphTraits<const Function*>
-        ::getSimpleNodeLabel(BB, BB->getParent());
+      return DOTGraphTraits<DOTFuncInfo *>
+        ::getSimpleNodeLabel(BB, nullptr);
     else
-      return DOTGraphTraits<const Function*>
-        ::getCompleteNodeLabel(BB, BB->getParent());
+      return DOTGraphTraits<DOTFuncInfo *>
+        ::getCompleteNodeLabel(BB, nullptr);
   }
 };
 
 template<>
 struct DOTGraphTraits<DominatorTree*> : public DOTGraphTraits<DomTreeNode*> {
 
   DOTGraphTraits (bool isSimple=false)
     : DOTGraphTraits<DomTreeNode*>(isSimple) {}

llvm/lib/Analysis/RegionPrinter.cpp

DOTGraphTraits (bool isSimple=false)
     : DefaultDOTGraphTraits(isSimple) {}
 
   std::string getNodeLabel(RegionNode *Node, RegionNode *Graph) {
 
     if (!Node->isSubRegion()) {
       BasicBlock *BB = Node->getNodeAs<BasicBlock>();
 
       if (isSimple())
-        return DOTGraphTraits<const Function*>
-          ::getSimpleNodeLabel(BB, BB->getParent());
+        return DOTGraphTraits<DOTFuncInfo *>
+          ::getSimpleNodeLabel(BB, nullptr);
       else
-        return DOTGraphTraits<const Function*>
-          ::getCompleteNodeLabel(BB, BB->getParent());
+        return DOTGraphTraits<DOTFuncInfo *>
+          ::getCompleteNodeLabel(BB, nullptr);
     }
 
     return "Not implemented";
   }
 };
 
 template <>
 struct DOTGraphTraits<RegionInfo *> : public DOTGraphTraits<RegionNode *> {

llvm/lib/Transforms/Scalar/NewGVN.cpp

 bool NewGVN::isBackedge(BasicBlock *From, BasicBlock *To) const {
   return From == To ||
          RPOOrdering.lookup(DT->getNode(From)) >=
              RPOOrdering.lookup(DT->getNode(To));
 }
 
 #ifndef NDEBUG
 static std::string getBlockName(const BasicBlock *B) {
-  return DOTGraphTraits<const Function *>::getSimpleNodeLabel(B, nullptr);
+  return DOTGraphTraits<DOTFuncInfo *>::getSimpleNodeLabel(B, nullptr);
 }
 #endif
 
 // Get a MemoryAccess for an instruction, fake or real.
 MemoryUseOrDef *NewGVN::getMemoryAccess(const Instruction *I) const {
   auto *Result = MSSA->getMemoryAccess(I);
   return Result ? Result : TempToMemory.lookup(I);
 }

polly/lib/Analysis/ScopGraphPrinter.cpp

 template <> struct DOTGraphTraits<RegionNode *> : public DefaultDOTGraphTraits {
   DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
 
   std::string getNodeLabel(RegionNode *Node, RegionNode *Graph) {
     if (!Node->isSubRegion()) {
       BasicBlock *BB = Node->getNodeAs<BasicBlock>();
 
       if (isSimple())
-        return DOTGraphTraits<const Function *>::getSimpleNodeLabel(
-            BB, BB->getParent());
+        return DOTGraphTraits<DOTFuncInfo *>::getSimpleNodeLabel(BB, nullptr);
+
       else
-        return DOTGraphTraits<const Function *>::getCompleteNodeLabel(
-            BB, BB->getParent());
+        return DOTGraphTraits<DOTFuncInfo *>::getCompleteNodeLabel(BB, nullptr);
     }
 
     return "Not implemented";
   }
 };
 
 template <>
 struct DOTGraphTraits<ScopDetectionWrapperPass *>