Flags for displaying only hot nodes in CFGPrinter graph

[knaumov]

Summary

Added flags to display only the hot nodes (nodes who have at least one a successor who doesn't end
in deopt or unreachable) in the CFGPrinter graph. Before displaying the graph, the first run of the
function isNodeHidden launches a check for every BB in the graph on a matter of being hidden.
Before answering, each node and its successors are being checked for ending in deopt or unreachable
and verified with the corresponding flags ("cfg-hide-unreachable-paths" and "cfg-hide-deoptimize-paths")
being turned on. If the leaf node is such as described before, it is marked to be not shown in the graph.
If any node has all of its successors not being shown, this node is automatically not shown as well. This
check uses post-order traversal to make sure that all of the successors already have been visited before
making the analysis for the said node.

[apilipenko]

LGTM with the renaming addressed.

llvm/lib/Analysis/CFGPrinter.cpp

39–44

Suggest renaming to HideUnreachablePaths, HideDeoptimizePaths.

[davidxl]

what is the use case of these options? Do hidden nodes create too much noise?

[knaumov]

Resolving @apilipenko 's suggestions
As I don't have commit access, can you please commit the change for me?

[knaumov]

Replying to @davidxl
This option is useful when you are analyzing only the "hot" paths on the CFG.
Using these flags you are getting rid of all the unnecessary paths in the graph (the ones that end in deopt or are unreachable)

[apilipenko]

In D74346#1873034, @davidxl wrote:

what is the use case of these options? Do hidden nodes create too much noise?

This is mostly for performance analysis. In our compiler we end up with many code paths resulting in deoptimization. These code paths are supposed to be cold and are not interesting when we are looking for the "fast path" performance. Filtering these has a nice effect of streamlining the CFG to the common path only.

[fedor.sergeev]

In D74346#1877375, @apilipenko wrote:

In D74346#1873034, @davidxl wrote:

what is the use case of these options? Do hidden nodes create too much noise?

This is mostly for performance analysis. In our compiler we end up with many code paths resulting in deoptimization. These code paths are supposed to be cold and are not interesting when we are looking for the "fast path" performance. Filtering these has a nice effect of streamlining the CFG to the common path only.

Makes sense to add rationale like this as a paragraph to revision description.

[davidxl]

lgtm

llvm/include/llvm/Analysis/CFGPrinter.h

class CFGOnlyPrinterPass
     : public PassInfoMixin<CFGOnlyPrinterPass> {
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
 
 template<>
 struct DOTGraphTraits<const Function*> : 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 getSimpleNodeLabel(const BasicBlock *Node,
                                         const Function *) {
ConstantInt *Weight =
         mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(OpNo));
     if (!Weight)
       return "";
 
     // Prepend a 'W' to indicate that this is a weight rather than the actual
     // profile count (due to scaling).
     return ("label=\"W:" + Twine(Weight->getZExtValue()) + "\"").str();
   }
+  bool isNodeHidden(const BasicBlock *Node);
+  void computeHiddenNodes(const Function *F);
 };
 } // End llvm namespace
 
 namespace llvm {
   class FunctionPass;
   FunctionPass *createCFGPrinterLegacyPassPass ();
   FunctionPass *createCFGOnlyPrinterLegacyPassPass ();
 } // End llvm namespace
 
 #endif

llvm/lib/Analysis/CFGPrinter.cpp

 // can be customized as needed.
 //
 // The other main feature of this file is that it implements the
 // Function::viewCFG method, which is useful for debugging passes which operate
 // on the CFG.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/Analysis/CFGPrinter.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/FileSystem.h"
+#include <algorithm>
+
 using namespace llvm;
 
 static cl::opt<std::string> CFGFuncName(
     "cfg-func-name", cl::Hidden,
     cl::desc("The name of a function (or its substring)"
              " whose CFG is viewed/printed."));
 
 static cl::opt<std::string> CFGDotFilenamePrefix(
     "cfg-dot-filename-prefix", cl::Hidden,
     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));
+
 namespace {
   struct CFGViewerLegacyPass : public FunctionPass {
     static char ID; // Pass identifcation, replacement for typeid
     CFGViewerLegacyPass() : FunctionPass(ID) {
       initializeCFGViewerLegacyPassPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override {

 FunctionPass *llvm::createCFGPrinterLegacyPassPass () {
   return new CFGPrinterLegacyPass();
 }
 
 FunctionPass *llvm::createCFGOnlyPrinterLegacyPassPass () {
   return new CFGOnlyPrinterLegacyPass();
 }
 
+void DOTGraphTraits<const Function *>::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) {
+  // 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/test/Other/cfg_deopt_unreach.ll

+; RUN: opt < %s -analyze -dot-cfg -cfg-hide-unreachable-paths -cfg-dot-filename-prefix=unreach 2>/dev/null
+; RUN: FileCheck %s -input-file=unreach.callee.dot -check-prefix=UNREACH
+; RUN: opt < %s -analyze -dot-cfg -cfg-hide-deoptimize-paths -cfg-dot-filename-prefix=deopt 2>/dev/null
+; RUN: FileCheck %s -input-file=deopt.callee.dot -check-prefix=DEOPT
+; RUN: opt < %s -analyze -dot-cfg -cfg-dot-filename-prefix=no-flags 2>/dev/null
+; RUN: FileCheck %s -input-file=no-flags.callee.dot -check-prefix=NO-FLAGS
+; RUN: opt < %s -analyze -dot-cfg -cfg-hide-unreachable-paths -cfg-hide-deoptimize-paths -cfg-dot-filename-prefix=both-flags 2>/dev/null
+; RUN: FileCheck %s -input-file=both-flags.callee.dot -check-prefix=BOTH-FLAGS
+
+declare i8 @llvm.experimental.deoptimize.i8(...)
+
+define i8 @callee(i1* %c) alwaysinline {
+; NO-FLAGS: [shape=record,label="{%0:\l  %c0 = load volatile i1, i1* %c\l  br i1 %c0, label %lleft, label %lright\l|{<s0>T|<s1>F}}"];
+; DEOPT: [shape=record,label="{%0:\l  %c0 = load volatile i1, i1* %c\l  br i1 %c0, label %lleft, label %lright\l|{<s0>T|<s1>F}}"];
+; UNREACH: [shape=record,label="{%0:\l  %c0 = load volatile i1, i1* %c\l  br i1 %c0, label %lleft, label %lright\l|{<s0>T|<s1>F}}"];
+; BOTH-FLAGS-NOT: [shape=record,label="{%0:\l  %c0 = load volatile i1, i1* %c\l  br i1 %c0, label %lleft, label %lright\l|{<s0>T|<s1>F}}"];
+  %c0 = load volatile i1, i1* %c
+  br i1 %c0, label %lleft, label %lright
+; NO-FLAGS: [shape=record,label="{lleft:                                            \l  %v0 = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ \"deopt\"(i32 1)\l... ]\l  ret i8 %v0\l}"];
+; DEOPT-NOT: [shape=record,label="{lleft:                                            \l  %v0 = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ \"deopt\"(i32 1)\l... ]\l  ret i8 %v0\l}"];
+; UNREACH: [shape=record,label="{lleft:                                            \l  %v0 = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ \"deopt\"(i32 1)\l... ]\l  ret i8 %v0\l}"];
+; BOTH-FLAGS-NOT: [shape=record,label="{lleft:                                            \l  %v0 = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ \"deopt\"(i32 1)\l... ]\l  ret i8 %v0\l}"];
+lleft:
+  %v0 = call i8(...) @llvm.experimental.deoptimize.i8(i32 1) [ "deopt"(i32 1) ]
+  ret i8 %v0
+
+; NO-FLAGS: [shape=record,label="{lright:                                           \l  unreachable\l}"];
+; DEOPT: [shape=record,label="{lright:                                           \l  unreachable\l}"];
+; UNREACH-NOT: [shape=record,label="{lright:                                           \l  unreachable\l}"];
+; BOTH-FLAGS-NOT: [shape=record,label="{lright:                                           \l  unreachable\l}"];
+lright:
+  unreachable
+}