Headers for basic blocks in control flow dot graphs

[mark-sed]

Summary

This is 3. out of 3 changes to the CFG pass that aims to make graphs more readable and contain more information.

• 1. Change - D154092
• 2. Change - D154096
• 3. Change - D154102

This change adds separators for basic block names, which makes it easier to find a basic block based on its name and separates it from the code. Currently there is also a chance that the basic block label will be present twice, that is in case the basic block has explicit numbering, this change does not contain this bug.

If all 3 changes will be accepted the final graphs should look as in the attached image:

[mark-sed]

Fixed polly test to contain the new header.

[knaumov]

llvm/include/llvm/Analysis/CFGPrinter.h

150

Haven't you changed the logic of the OS argument here? It seems that now it is always empty.

157

Nit: Typo in "Prepend"

[mark-sed]

llvm/include/llvm/Analysis/CFGPrinter.h

150

So the previous code was a cause for a bug, where basic blocks with numbered label got their label displayed twice in the CFG. getName() will be empty in case of implicit and also explicit numbered name, but the explicit will get it inserted in the HandleBasicBlock. So the solution here is to prepend the name only if the HandleBasicBlock did not already do it.

[mark-sed]

Fixed typo in a comment.

[mark-sed]

llvm/include/llvm/Analysis/CFGPrinter.h

157

Fixed.

[apilipenko]

I think a better structure would be:

• Don't emit the block name in HandleBasicBlock. Instead of printing the BB, just iterate through the instructions and print them 1 by 1.
• Unconditionally prepend the block name in CompleteNodeLabelString.

llvm/include/llvm/Analysis/CFGPrinter.h

138

Please, avoid unrelated whiteline changes

[mark-sed]

Added changes requested by apilipenko, where the HandleBasicBlock now prepends the BB name and then appends instructions instead of using << operator on the whole BB.

[mark-sed]

Fixed tests that were failing. The new implementation does not leave extra whitespace.

llvm/include/llvm/Analysis/CFGPrinter.h

if (!Node->getName().empty())
     return Node->getName().str();
 
   std::string Str;
   raw_string_ostream OS(Str);
 
   Node->printAsOperand(OS, false);
   return OS.str();
 }
 
 template <typename BasicBlockT>
 std::string CompleteNodeLabelString(
     const BasicBlockT *Node,
     function_ref<void(raw_string_ostream &, const BasicBlockT &)>
         HandleBasicBlock,
     function_ref<void(std::string &, unsigned &, unsigned)>
         HandleComment) {
 
   enum { MaxColumns = 80 };
   std::string Str;
   raw_string_ostream OS(Str);
-
-  if (Node->getName().empty()) {
-    Node->printAsOperand(OS, false);
-    OS << ':';
-  }
-
   HandleBasicBlock(OS, *Node);
   std::string OutStr = OS.str();
-  if (OutStr[0] == '\n')
+  // Remove "%" from BB name
+  if (OutStr[0] == '%') {
     OutStr.erase(OutStr.begin());
+  }
 
   unsigned ColNum = 0;
   unsigned LastSpace = 0;
   for (unsigned i = 0; i != OutStr.length(); ++i) {
     if (OutStr[i] == '\n') { // Left justify
       OutStr[i] = '\\';
       OutStr.insert(OutStr.begin() + i + 1, 'l');
       ColNum = 0;
       LastSpace = 0;
     } else if (OutStr[i] == ';') {             // Delete comments!
       unsigned Idx = OutStr.find('\n', i + 1); // Find end of line
       HandleComment(OutStr, i, Idx);
     } else if (ColNum == MaxColumns) { // Wrap lines.
       // Wrap very long names even though we can't find a space.
       if (!LastSpace)
         LastSpace = i;
       OutStr.insert(LastSpace, "\\l...");
       ColNum = i - LastSpace;
       LastSpace = 0;
       i += 3; // The loop will advance 'i' again.
     } else
       ++ColNum;
     if (OutStr[i] == ' ')
       LastSpace = i;
   }
+
+  // Replace \l after BB name with | to separate it into header
+  OutStr.replace(OutStr.find_first_of('\\') + 1, 1, "|");
   return OutStr;
 }
 
 template <>
 struct DOTGraphTraits<DOTFuncInfo *> : public DefaultDOTGraphTraits {
 
   // Cache for is hidden property
   DenseMap<const BasicBlock *, bool> isOnDeoptOrUnreachablePath;
 
   DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
 
   static void eraseComment(std::string &OutStr, unsigned &I, unsigned Idx) {
     OutStr.erase(OutStr.begin() + I, OutStr.begin() + Idx);
     --I;
   }
 
   static std::string getGraphName(DOTFuncInfo *CFGInfo) {
     return "CFG for '" + CFGInfo->getFunction()->getName().str() + "' function";
   }
 
   static std::string getSimpleNodeLabel(const BasicBlock *Node, DOTFuncInfo *) {
     return SimpleNodeLabelString(Node);
   }
 
+  static void printBasicBlock(raw_string_ostream &OS, const BasicBlock &Node) {
+    // Prepend label name
+    Node.printAsOperand(OS, false);
+    OS << ":\n";
+    for (auto J = Node.begin(), JE = Node.end(); J != JE; ++J) {
+      const Instruction *Inst = &*J;
+      OS << *Inst << "\n";
+    }
+  }
+
   static std::string getCompleteNodeLabel(
       const BasicBlock *Node, DOTFuncInfo *,
       function_ref<void(raw_string_ostream &, const BasicBlock &)>
-          HandleBasicBlock = [](raw_string_ostream &OS,
-                                const BasicBlock &Node) -> void { OS << Node; },
+          HandleBasicBlock = printBasicBlock,
       function_ref<void(std::string &, unsigned &, unsigned)>
           HandleComment = eraseComment) {
     return CompleteNodeLabelString(Node, HandleBasicBlock, HandleComment);
   }
 
   std::string getNodeLabel(const BasicBlock *Node, DOTFuncInfo *CFGInfo) {
 
     if (isSimple())

llvm/test/Analysis/DotMachineCFG/AMDGPU/functions.mir

 # RUN: llc -mtriple=amdgcn-- -run-pass=dot-machine-cfg  -mcfg-dot-filename-prefix=%t -mcfg-func-name=func2 -o -  %s 2>&1 > /dev/null
 # RUN: FileCheck %s -input-file=%t.func2.dot --check-prefix=MCFG
 
 # MCFG-NOT: digraph "Machine CFG for 'func1' function"
 name: func1
 body: |
   bb.0:
     $sgpr0 = S_LOAD_DWORD_IMM $sgpr10_sgpr11, 0, 0
     $sgpr1 = S_LOAD_DWORD_IMM $sgpr12_sgpr13, 0, 0
     S_ENDPGM 0
 ...
 
 # MCFG: digraph "Machine CFG for 'func2' function"
 # MCFG-NEXT: label="Machine CFG for 'func2' function"
-# MCFG: Node{{[0-9A-Za-z]*}} [shape=record,label="{%bb.0:bb.0:\l  $sgpr0 = S_LOAD_DWORD_IMM $sgpr12_sgpr13, 0, 0\l  $sgpr1 = S_LOAD_DWORD_IMM $sgpr6_sgpr7, 0, 0\l  $sgpr2 = S_LOAD_DWORD_IMM $sgpr14_sgpr15, 0, 0\l  S_ENDPGM 0\l}"];
+# MCFG: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.0:|bb.0:\l  $sgpr0 = S_LOAD_DWORD_IMM $sgpr12_sgpr13, 0, 0\l  $sgpr1 = S_LOAD_DWORD_IMM $sgpr6_sgpr7, 0, 0\l  $sgpr2 = S_LOAD_DWORD_IMM $sgpr14_sgpr15, 0, 0\l  S_ENDPGM 0\l}"];
 ---
 name: func2
 body: |
   bb.0:
     $sgpr0 = S_LOAD_DWORD_IMM $sgpr12_sgpr13, 0, 0
     $sgpr1 = S_LOAD_DWORD_IMM $sgpr6_sgpr7, 0, 0
     $sgpr2 = S_LOAD_DWORD_IMM $sgpr14_sgpr15, 0, 0
     S_ENDPGM 0
 ...

llvm/test/Analysis/DotMachineCFG/AMDGPU/irreducible.mir

 # RUN: llc -mtriple=amdgcn-- -run-pass=dot-machine-cfg  -mcfg-dot-filename-prefix=%t -o -  %s 2>&1 > /dev/null
 # RUN: FileCheck %s -input-file=%t.irreducible.dot --check-prefix=MCFG
 # RUN: llc -mtriple=amdgcn-- -run-pass=dot-machine-cfg  -mcfg-dot-filename-prefix=%t -dot-mcfg-only -o -  %s 2>&1 > /dev/null
 # RUN: FileCheck %s -input-file=%t.irreducible.dot --check-prefix=MCFG-ONLY
 
 # MCFG: digraph "Machine CFG for 'irreducible' function"
 # MCFG-NEXT: label="Machine CFG for 'irreducible' function"
-# MCFG: Node{{[0-9A-Za-z]*}} [shape=record,label="{%bb.0:bb.0:\l  successors: %bb.1(0x40000000), %bb.2(0x40000000)\l  liveins: $vgpr0, $vgpr1, $vgpr2, $sgpr4_sgpr5, $sgpr6_sgpr7, $sgpr8_sgpr9,\l... $sgpr10_sgpr11, $sgpr14, $sgpr15, $sgpr16\l  %0:sreg_32 = IMPLICIT_DEF\l  %1:vgpr_32 = COPY $vgpr0\l  %2:vgpr_32 = V_MOV_B32_e32 0, implicit $exec\l  S_CMP_EQ_U32 %0:sreg_32, 0, implicit-def $scc\l  S_CBRANCH_SCC1 %bb.1, implicit $scc\l  S_BRANCH %bb.2\l}"];
+# MCFG: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.0:|bb.0:\l  successors: %bb.1(0x40000000), %bb.2(0x40000000)\l  liveins: $vgpr0, $vgpr1, $vgpr2, $sgpr4_sgpr5, $sgpr6_sgpr7, $sgpr8_sgpr9,\l... $sgpr10_sgpr11, $sgpr14, $sgpr15, $sgpr16\l  %0:sreg_32 = IMPLICIT_DEF\l  %1:vgpr_32 = COPY $vgpr0\l  %2:vgpr_32 = V_MOV_B32_e32 0, implicit $exec\l  S_CMP_EQ_U32 %0:sreg_32, 0, implicit-def $scc\l  S_CBRANCH_SCC1 %bb.1, implicit $scc\l  S_BRANCH %bb.2\l}"];
 # MCFG-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
 # MCFG-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
-# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{%bb.1:bb.1:\l\l  successors: %bb.3(0x80000000)\l\l  %3:vgpr_32 = PHI %2:vgpr_32, %bb.0, %4:vgpr_32, %bb.5\l  %5:vgpr_32 = V_ADD_U32_e64 %3:vgpr_32, 1, 0, implicit $exec\l  S_BRANCH %bb.3\l}"];
+# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.1:|bb.1:\l\l  successors: %bb.3(0x80000000)\l\l  %3:vgpr_32 = PHI %2:vgpr_32, %bb.0, %4:vgpr_32, %bb.5\l  %5:vgpr_32 = V_ADD_U32_e64 %3:vgpr_32, 1, 0, implicit $exec\l  S_BRANCH %bb.3\l}"];
 # MCFG-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
-# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{%bb.2:bb.2:\l\l  successors: %bb.3(0x80000000)\l\l  %6:vgpr_32 = PHI %2:vgpr_32, %bb.0, %4:vgpr_32, %bb.4\l  %7:vgpr_32 = V_ADD_U32_e64 %6:vgpr_32, 2, 0, implicit $exec\l}"];
+# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.2:|bb.2:\l\l  successors: %bb.3(0x80000000)\l\l  %6:vgpr_32 = PHI %2:vgpr_32, %bb.0, %4:vgpr_32, %bb.4\l  %7:vgpr_32 = V_ADD_U32_e64 %6:vgpr_32, 2, 0, implicit $exec\l}"];
 # MCFG-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
-# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{%bb.3:bb.3:\l\l  successors: %bb.4(0x80000000)\l\l  %4:vgpr_32 = PHI %5:vgpr_32, %bb.1, %7:vgpr_32, %bb.2\l}"];
+# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.3:|bb.3:\l\l  successors: %bb.4(0x80000000)\l\l  %4:vgpr_32 = PHI %5:vgpr_32, %bb.1, %7:vgpr_32, %bb.2\l}"];
 # MCFG-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
-# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{%bb.4:bb.4:\l\l  successors: %bb.2(0x40000000), %bb.5(0x40000000)\l\l  %8:vgpr_32 = V_AND_B32_e32 3, %1:vgpr_32, implicit $exec\l  %9:sreg_64 = V_CMP_EQ_U32_e64 %8:vgpr_32, 2, implicit $exec\l  %10:sreg_64 = SI_IF killed %9:sreg_64, %bb.2, implicit-def dead $exec,\l... implicit-def dead $scc, implicit $exec\l}"];
+# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.4:|bb.4:\l\l  successors: %bb.2(0x40000000), %bb.5(0x40000000)\l\l  %8:vgpr_32 = V_AND_B32_e32 3, %1:vgpr_32, implicit $exec\l  %9:sreg_64 = V_CMP_EQ_U32_e64 %8:vgpr_32, 2, implicit $exec\l  %10:sreg_64 = SI_IF killed %9:sreg_64, %bb.2, implicit-def dead $exec,\l... implicit-def dead $scc, implicit $exec\l}"];
 # MCFG-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
 # MCFG-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
-# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{%bb.5:bb.5:\l\l  successors: %bb.1(0x40000000), %bb.6(0x40000000)\l\l  %11:sreg_64 = V_CMP_EQ_U32_e64 %8:vgpr_32, 1, implicit $exec\l  %12:sreg_64 = SI_IF killed %11:sreg_64, %bb.1, implicit-def dead $exec,\l... implicit-def dead $scc, implicit $exec\l}"];
+# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.5:|bb.5:\l\l  successors: %bb.1(0x40000000), %bb.6(0x40000000)\l\l  %11:sreg_64 = V_CMP_EQ_U32_e64 %8:vgpr_32, 1, implicit $exec\l  %12:sreg_64 = SI_IF killed %11:sreg_64, %bb.1, implicit-def dead $exec,\l... implicit-def dead $scc, implicit $exec\l}"];
 # MCFG-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
 # MCFG-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
-# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{%bb.6:bb.6:\l\l\l  S_ENDPGM 0\l}"];
+# MCFG-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{bb.6:|bb.6:\l\l\l  S_ENDPGM 0\l}"];
 
 # MCFG-ONLY: digraph "Machine CFG for 'irreducible' function"
 # MCFG-ONLY-NEXT: label="Machine CFG for 'irreducible' function"
 # MCFG-ONLY: Node{{[0-9A-Za-z]*}} [shape=record,label="{%bb.0}"];
 # MCFG-ONLY-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
 # MCFG-ONLY-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};
 # MCFG-ONLY-NEXT: Node{{[0-9A-Za-z]*}} [shape=record,label="{%bb.1}"];
 # MCFG-ONLY-NEXT: Node{{[0-9A-Za-z]*}} -> Node{{[0-9A-Za-z]*}};

llvm/test/Other/cfg_deopt_unreach.ll

 ; RUN: rm -rf %t
 ; RUN: mkdir -p %t
 ; RUN: opt < %s -passes=dot-cfg -cfg-hide-unreachable-paths -cfg-dot-filename-prefix=%t/unreach 2>/dev/null > /dev/null
 ; RUN: FileCheck %s -input-file=%t/unreach.callee.dot -check-prefix=UNREACH
 ; RUN: opt < %s -passes=dot-cfg -cfg-hide-deoptimize-paths -cfg-dot-filename-prefix=%t/deopt 2>/dev/null > /dev/null
 ; RUN: FileCheck %s -input-file=%t/deopt.callee.dot -check-prefix=DEOPT
 ; RUN: opt < %s -passes=dot-cfg -cfg-dot-filename-prefix=%t/no-flags 2>/dev/null > /dev/null
 ; RUN: FileCheck %s -input-file=%t/no-flags.callee.dot -check-prefix=NO-FLAGS
 ; RUN: opt < %s -passes=dot-cfg -cfg-hide-unreachable-paths -cfg-hide-deoptimize-paths -cfg-dot-filename-prefix=%t/both-flags 2>/dev/null > /dev/null
 ; RUN: FileCheck %s -input-file=%t/both-flags.callee.dot -check-prefix=BOTH-FLAGS
 
 declare i8 @llvm.experimental.deoptimize.i8(...)
 
 define i8 @callee(ptr %c) alwaysinline {
   %c0 = load volatile i1, ptr %c
   br i1 %c0, label %lleft, label %lright
-; NO-FLAGS: label="{lleft:                                            \l  %v0 = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ \"deopt\"(i32 1)\l... ]\l  ret i8 %v0\l}"
-; DEOPT-NOT: label="{lleft:                                            \l  %v0 = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ \"deopt\"(i32 1)\l... ]\l  ret i8 %v0\l}"
-; UNREACH: label="{lleft:                                            \l  %v0 = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ \"deopt\"(i32 1)\l... ]\l  ret i8 %v0\l}"
-; BOTH-FLAGS-NOT: label="{lleft:                                            \l  %v0 = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ \"deopt\"(i32 1)\l... ]\l  ret i8 %v0\l}"
+; NO-FLAGS: label="{lleft:                                            |  %v0 = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ \"deopt\"(i32 1)\l... ]\l  ret i8 %v0\l}"
+; DEOPT-NOT: label="{lleft:                                            |  %v0 = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ \"deopt\"(i32 1)\l... ]\l  ret i8 %v0\l}"
+; UNREACH: label="{lleft:                                            |  %v0 = call i8 (...) @llvm.experimental.deoptimize.i8(i32 1) [ \"deopt\"(i32 1)\l... ]\l  ret i8 %v0\l}"
+; BOTH-FLAGS-NOT: label="{lleft:                                            |  %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: label="{lright:                                           \l  unreachable\l}"
-; DEOPT: label="{lright:                                           \l  unreachable\l}"
-; UNREACH-NOT: label="{lright:                                           \l  unreachable\l}"
-; BOTH-FLAGS-NOT: label="{lright:                                           \l  unreachable\l}"
+; NO-FLAGS: label="{lright:                                           |  unreachable\l}"
+; DEOPT: label="{lright:                                           |  unreachable\l}"
+; UNREACH-NOT: label="{lright:                                           |  unreachable\l}"
+; BOTH-FLAGS-NOT: label="{lright:                                           |  unreachable\l}"
 lright:
   unreachable
 }

polly/test/ScopDetect/dot-scops-npm.ll

 ;        function name and printing a dot file there will be a race condition
 ;        when running tests in parallel.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @func_npm(i32 %n, i32 %m, ptr noalias nonnull %A) {
 ; CHECK:      digraph "Scop Graph for 'func_npm' function"
 ; CHECK-NEXT: label="Scop Graph for 'func_npm' function"
-; CHECK:      Node0x[[EntryID:.*]] [shape=record,label="{entry:\l  br label %outer.for\l}"];
+; CHECK:      Node0x[[EntryID:.*]] [shape=record,label="{entry:|  br label %outer.for\l}"];
 ; CHECK-NEXT: Node0x[[EntryID]] -> Node0x[[OUTER_FOR_ID:.*]];
 ; CHECK-NEXT: Node0x[[OUTER_FOR_ID]] [shape=record,label="{outer.for:
 ; CHECK-NEXT: Node0x[[OUTER_FOR_ID]] -> Node0x[[INNER_FOR_ID:.*]];
 ; CHECK-NEXT: Node0x[[OUTER_FOR_ID]] -> Node0x[[OUTER_EXIT:.*]];
 ; CHECK-NEXT: Node0x[[INNER_FOR_ID]] [shape=record,label="{inner.for:
 ; CHECK-NEXT: Node0x[[INNER_FOR_ID]] -> Node0x[[BABY1_ID:.*]];
 ; CHECK-NEXT: Node0x[[INNER_FOR_ID]] -> Node0x[[INNER_EXIT_ID:.*]];
 ; CHECK-NEXT: Node0x[[BABY1_ID]] [shape=record,label="{body1: