[BOLT][Instrumentation] Instrument leaves from spanning tree

[yavtuk]

Summary

For non-conservative instrumentation mode we should insert an instrumentation snippet from STOutSet.
Otherwise, the check size() == 0 makes no sense, because if there is no BB in STOutSet then the default constructor is called and
this BB is added with zero size of successors set.
And it means that we insert an instrumentation snippet to all BBs that originally filtered when constructing the spanning tree.

[yavtuk]

@rafauler @Amir @maksfb Hi folks, what do you thought? Does it make sense?

[rafauler]

Hi @yavtuk! Thanks for the patch.

I was on leave and couldn't get to it earlier, sorry about that.

And it means that we insert an instrumentation snippet to all BBs that originally filtered when constructing the spanning tree.

Here, what do you mean by BBs originally filtered? I might be missing something, so I'll tell you what I know about this code and you correct me if I'm wrong. It is true that this code currently inserts an empty std::set for elements not in STOutSet and triggers the condition that instruments this basic block. So any blocks not in STOutSet will be instrumented. But this is by design, the idea being that we may only omit instrumentation in specific cases, when the node is part of the spanning tree and not a leaf. In these cases, the node will be in STOutSet and we will skip adding instrumentation code to it.

[yavtuk]

Hi Rafael, welcome back, give me some time to remember why I decided so, I’ll be back with an example soon.
Maybe I just misunderstood what’s meant by a non-conservative algorithm

[yavtuk]

@rafauler you’re right, thanks for explanation.
I was confused by the following checking

if (STOutSet[&BB].size() == 0)

Because if for some reason the BB is not in the spanning tree, the default constructor for this base block is called and it is inserted into the STOutSet with 0 number of successros.
Therefore the insturmentation snipet is inserted.
But now there is only one reason for that, a BB is a tree leaf.

bolt/lib/Passes/Instrumentation.cpp

       std::tie(Pred, BB) = Stack.top();
       Stack.pop();
       if (VisitedSet.find(BB) != VisitedSet.end())
         continue;
 
       VisitedSet.insert(BB);
       if (Pred)
         STOutSet[Pred].insert(BB);
+      else if (BB->succ_empty()) {
+        // Add BB directly if the one doesn't have pred and successors
+        // example, main function in file basic-instrumentation.s
+        STOutSet[BB];
+      }
 
       for (BinaryBasicBlock *SuccBB : BB->successors())
         Stack.push(std::make_pair(BB, SuccBB));
     }
   }
 
   // Determine whether this is a leaf function, which needs special
   // instructions to protect the red zone

                           FromOffset, Function, FTBB, FTBB->getInputOffset(),
                           IsLeafFunction, IsInvokeBlock, FuncDesc, BBToID[&BB],
                           BBToID[FTBB]);
     }
   } // End of BBs loop
 
   // Instrument spanning tree leaves
   if (!opts::ConservativeInstrumentation) {
-    for (auto BBI = Function.begin(), BBE = Function.end(); BBI != BBE; ++BBI) {
-      BinaryBasicBlock &BB = *BBI;
-      if (STOutSet[&BB].size() == 0)
-        instrumentLeafNode(BB, BB.begin(), IsLeafFunction, *FuncDesc,
-                           BBToID[&BB]);
+    using STOutSetTy = std::unordered_map<const BinaryBasicBlock *,
+                                          std::set<const BinaryBasicBlock *>>;
+    for (STOutSetTy::iterator it = STOutSet.begin(); it != STOutSet.end();
+         ++it) {
+      BinaryBasicBlock *BB = const_cast<BinaryBasicBlock *>(it->first);
+      std::set<const BinaryBasicBlock *> SuccBBs = it->second;
+      if (SuccBBs.size() == 0) {
+        instrumentLeafNode(*BB, BB->begin(), IsLeafFunction, *FuncDesc,
+                           BBToID[BB]);
+      }
     }
   }
 
   // Consume list of critical edges: split them and add instrumentation to the
   // newly created BBs
   auto Iter = SplitInstrs.begin();
   for (std::pair<BinaryBasicBlock *, BinaryBasicBlock *> &BBPair :
        SplitWorklist) {

bolt/test/X86/asm-dump.c

 /**
  * Test for asm-dump functionality.
  *
  * REQUIRES: system-linux,bolt-runtime
  *
  * Compile the source
  * RUN: %clang -fPIC %s -o %t.exe -Wl,-q
  *
  * Profile collection: instrument the binary
- * RUN: llvm-bolt %t.exe --instrument --instrumentation-file=%t.fdata -o %t.instr
+ * RUN: llvm-bolt %t.exe --instrument --conservative-instrumentation \
+ * RUN:   --instrumentation-file=%t.fdata -o %t.instr
  *
  * Profile collection: run instrumented binary (and capture output)
  * RUN: %t.instr > %t.result
  *
  * Run BOLT with asm-dump
  * RUN: llvm-bolt %t.exe -p %t.fdata --funcs=main --asm-dump=%t -o /dev/null \
  * RUN:   | FileCheck %s --check-prefix=CHECK-BOLT
  *

bolt/test/runtime/X86/fdata-escape-chars.ll

 
 ; REQUIRES: system-linux,bolt-runtime
 
 ; RUN: llc %s -o %t.s
 ; RUN: %clang %cflags -O0 %t.s -o %t.exe -Wl,-q
 ; RUN: llvm-objcopy --redefine-syms=%p/Inputs/fdata-escape-chars-syms.txt %t.exe
 ;
 ; RUN: llvm-bolt %t.exe -o %t.exe.instrumented --instrument  \
-; RUN:   --instrumentation-file=%t.fdata
+; RUN:   --conservative-instrumentation --instrumentation-file=%t.fdata
 ; RUN: %t.exe.instrumented
 ; RUN: cat %t.fdata | \
 ; RUN:   FileCheck --check-prefix="FDATA_CHECK" %s
 ; RUN: llvm-bolt %t.exe -o %t.fdata.exe --data %t.fdata --print-finalized | \
 ; RUN:   FileCheck --check-prefix="INSTR_CHECK" %s
 ;
 ; RUN: link_fdata %p/Inputs/fdata-escape-chars.txt %t.exe %t.pre "PREAGR"
 ; RUN: perf2bolt %t.exe -o %t.pre.fdata -pa -p %t.pre

bolt/test/runtime/X86/instrumentation-dup-jts.s

 # RUN:  llvm-bolt %t.exe -o %t.bolted --data %t.fdata \
 # RUN:    --reorder-blocks=ext-tsp --reorder-functions=hfsort+ \
 # RUN:    --print-only=interp --print-finalized | FileCheck %s
 
 # RUN: %t.bolted 120
 
 # Check that our two indirect jumps are recorded in the fdata file and that
 # each has its own independent profile
-# CHECK:  Successors: .Ltmp1 (mispreds: 0, count: 1), .Ltmp0 (mispreds: 0, count: 0), .Ltmp2 (mispreds: 0, count: 0)
-# CHECK:  Successors: .Ltmp0 (mispreds: 0, count: 1), .Ltmp2 (mispreds: 0, count: 1), .Ltmp1 (mispreds: 0, count: 0)
+# CHECK:  Successors: .Ltmp{{[0-2]}} {{.*}}, .Ltmp{{[0-2]}} {{.*}}, .Ltmp{{[0-2]}} {{.*}}
+# CHECK:  Successors: .Ltmp{{[0-2]}} {{.*}}, .Ltmp{{[0-2]}} {{.*}}, .Ltmp{{[0-2]}} {{.*}}
 
   .file "test.c"
   .text
   .section  .rodata.str1.1,"aMS",@progbits,1
 .LC0:
   .string "%d\n"
   .text
   .p2align 4,,15