[BOLT] Switch to using layout order in YAML

[Amir]

Summary

Use layout order in YAML profile reading/writing. Preserve old behavior (DFS order)
under -profile-use-dfs option.

[spupyrev]

bolt/lib/Profile/YAMLProfileReader.cpp

109

Is there a reason why the type is not BinaryFunction::BasicBlockOrderType but an explicit SmallVector?

Also I'm not sure if there is any advantage here to use SmallVector over std::vector, as the order is always non-empty.

[Amir]

Use BasicBlockOrderType

[Amir]

bolt/lib/Profile/YAMLProfileReader.cpp

109

You're right, can just use that type alias. I thought to use a SmallVector<const BinaryBasicBlock *, 0> version in YAMLWriter but let's keep them uniform between reader and writer. Regarding std::vector: it used to be it, but Maksim changed to ADT type citing BinaryFunction size reduction.

[maksfb]

Since you are changing the default behavior, retitle the diff to reflect that fact. Otherwise LGTM.

[maksfb]

"Use layout order for YAML profile"?

[maksfb]

It's fine :)

bolt/lib/Profile/YAMLProfileReader.cpp

 extern cl::opt<unsigned> Verbosity;
 extern cl::OptionCategory BoltOptCategory;
 extern cl::opt<bool> InferStaleProfile;
 
 static llvm::cl::opt<bool>
     IgnoreHash("profile-ignore-hash",
                cl::desc("ignore hash while reading function profile"),
                cl::Hidden, cl::cat(BoltOptCategory));
+
+llvm::cl::opt<bool> ProfileUseDFS("profile-use-dfs",
+                                  cl::desc("use DFS order for YAML profile"),
+                                  cl::Hidden, cl::cat(BoltOptCategory));
 }
 
 namespace llvm {
 namespace bolt {
 
 bool YAMLProfileReader::isYAML(const StringRef Filename) {
   ErrorOr<std::unique_ptr<MemoryBuffer>> MB =
       MemoryBuffer::getFileOrSTDIN(Filename);
bool YAMLProfileReader::parseFunctionProfile(
   BF.setExecutionCount(YamlBF.ExecCount);
 
   uint64_t FuncRawBranchCount = 0;
   for (const yaml::bolt::BinaryBasicBlockProfile &YamlBB : YamlBF.Blocks)
     for (const yaml::bolt::SuccessorInfo &YamlSI : YamlBB.Successors)
       FuncRawBranchCount += YamlSI.Count;
   BF.setRawBranchCount(FuncRawBranchCount);
 
-  if (!opts::IgnoreHash && YamlBF.Hash != BF.computeHash(/*UseDFS=*/true)) {
+  if (!opts::IgnoreHash && YamlBF.Hash != BF.computeHash(opts::ProfileUseDFS)) {
     if (opts::Verbosity >= 1)
       errs() << "BOLT-WARNING: function hash mismatch\n";
     ProfileMatched = false;
   }
 
   if (YamlBF.NumBasicBlocks != BF.size()) {
     if (opts::Verbosity >= 1)
       errs() << "BOLT-WARNING: number of basic blocks mismatch\n";
     ProfileMatched = false;
   }
 
-  BinaryFunction::BasicBlockOrderType DFSOrder = BF.dfs();
+  SmallVector<BinaryBasicBlock *, 0> Order;
+  if (opts::ProfileUseDFS)
+    llvm::copy(BF.dfs(), std::back_inserter(Order));
+  else
+    llvm::copy(BF.getLayout().blocks(), std::back_inserter(Order));
 
   for (const yaml::bolt::BinaryBasicBlockProfile &YamlBB : YamlBF.Blocks) {
-    if (YamlBB.Index >= DFSOrder.size()) {
+    if (YamlBB.Index >= Order.size()) {
       if (opts::Verbosity >= 2)
         errs() << "BOLT-WARNING: index " << YamlBB.Index
                << " is out of bounds\n";
       ++MismatchedBlocks;
       continue;
     }
 
-    BinaryBasicBlock &BB = *DFSOrder[YamlBB.Index];
+    BinaryBasicBlock &BB = *Order[YamlBB.Index];
 
     // Basic samples profile (without LBR) does not have branches information
     // and needs a special processing.
     if (YamlBP.Header.Flags & BinaryFunction::PF_SAMPLE) {
       if (!YamlBB.EventCount) {
         BB.setExecutionCount(0);
         continue;
       }
for (const yaml::bolt::CallSiteInfo &YamlCSI : YamlBB.CallSites) {
         setAnnotation("CTCTakenCount", YamlCSI.Count);
         setAnnotation("CTCMispredCount", YamlCSI.Mispreds);
       } else {
         setAnnotation("Count", YamlCSI.Count);
       }
     }
 
     for (const yaml::bolt::SuccessorInfo &YamlSI : YamlBB.Successors) {
-      if (YamlSI.Index >= DFSOrder.size()) {
+      if (YamlSI.Index >= Order.size()) {
         if (opts::Verbosity >= 1)
           errs() << "BOLT-WARNING: index out of bounds for profiled block\n";
         ++MismatchedEdges;
         continue;
       }
 
-      BinaryBasicBlock &SuccessorBB = *DFSOrder[YamlSI.Index];
+      BinaryBasicBlock &SuccessorBB = *Order[YamlSI.Index];
       if (!BB.getSuccessor(SuccessorBB.getLabel())) {
         if (opts::Verbosity >= 1)
           errs() << "BOLT-WARNING: no successor for block " << BB.getName()
                  << " that matches index " << YamlSI.Index << " or block "
                  << SuccessorBB.getName() << '\n';
         ++MismatchedEdges;
         continue;
       }
for (auto &BFI : BC.getBinaryFunctions()) {
     BinaryFunction &Function = BFI.second;
 
     // Clear function call count that may have been set while pre-processing
     // the profile.
     Function.setExecutionCount(BinaryFunction::COUNT_NO_PROFILE);
 
     // Recompute hash once per function.
     if (!opts::IgnoreHash)
-      Function.computeHash(/*UseDFS=*/true);
+      Function.computeHash(opts::ProfileUseDFS);
 
     for (StringRef FunctionName : Function.getNames()) {
       auto PI = ProfileNameToProfile.find(FunctionName);
       if (PI == ProfileNameToProfile.end())
         continue;
 
       yaml::bolt::BinaryFunctionProfile &YamlBF = *PI->getValue();
       if (profileMatches(YamlBF, Function))

bolt/lib/Profile/YAMLProfileWriter.cpp

 //===- bolt/Profile/YAMLProfileWriter.cpp - YAML profile serializer -------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "bolt/Profile/YAMLProfileWriter.h"
 #include "bolt/Core/BinaryBasicBlock.h"
 #include "bolt/Core/BinaryFunction.h"
 #include "bolt/Profile/ProfileReaderBase.h"
 #include "bolt/Profile/ProfileYAMLMapping.h"
 #include "bolt/Rewrite/RewriteInstance.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/raw_ostream.h"
 
 #undef  DEBUG_TYPE
 #define DEBUG_TYPE "bolt-prof"
 
+namespace opts {
+extern llvm::cl::opt<bool> ProfileUseDFS;
+} // namespace opts
+
 namespace llvm {
 namespace bolt {
 
 namespace {
 void convert(const BinaryFunction &BF,
              yaml::bolt::BinaryFunctionProfile &YamlBF) {
   const BinaryContext &BC = BF.getBinaryContext();
 
   const uint16_t LBRProfile = BF.getProfileFlags() & BinaryFunction::PF_LBR;
 
   // Prepare function and block hashes
-  BF.computeHash(/*UseDFS=*/true);
+  BF.computeHash(opts::ProfileUseDFS);
   BF.computeBlockHashes();
 
   YamlBF.Name = BF.getPrintName();
   YamlBF.Id = BF.getFunctionNumber();
   YamlBF.Hash = BF.getHash();
   YamlBF.NumBasicBlocks = BF.size();
   YamlBF.ExecCount = BF.getKnownExecutionCount();
 
-  for (const BinaryBasicBlock *BB : BF.dfs()) {
+  SmallVector<const llvm::bolt::BinaryBasicBlock *, 0> Order;
+  llvm::copy(opts::ProfileUseDFS ? BF.dfs() : BF.getLayout().blocks(),
+             std::back_inserter(Order));
+
+  for (const BinaryBasicBlock *BB : Order) {
     yaml::bolt::BinaryBasicBlockProfile YamlBB;
     YamlBB.Index = BB->getLayoutIndex();
     YamlBB.NumInstructions = BB->getNumNonPseudos();
     YamlBB.Hash = BB->getHash();
 
     if (!LBRProfile) {
       YamlBB.EventCount = BB->getKnownExecutionCount();
       if (YamlBB.EventCount)

bolt/test/X86/pre-aggregated-perf.test

 # This script checks that perf2bolt is reading pre-aggregated perf information
 # correctly for a simple example. The perf.data of this example was generated
 # with the following command:
 #
 #  $ perf record -j any,u -e branch -o perf.data -- ./blarge
 #
 #  blarge is the binary for "basicmath large inputs" taken from Mibench.
 
 # Currently failing in MacOS / generating different hash for usqrt
 REQUIRES: system-linux
 
 RUN: yaml2obj %p/Inputs/blarge.yaml &> %t.exe
-RUN: perf2bolt %t.exe -o %t --pa -p %p/Inputs/pre-aggregated.txt -w %t.new
+RUN: perf2bolt %t.exe -o %t --pa -p %p/Inputs/pre-aggregated.txt -w %t.new \
+RUN:   --profile-use-dfs
 RUN: cat %t | sort | FileCheck %s -check-prefix=PERF2BOLT
 RUN: cat %t.new | FileCheck %s -check-prefix=NEWFORMAT
 
 # Test --profile-format option with perf2bolt
 RUN: perf2bolt %t.exe -o %t.fdata --pa -p %p/Inputs/pre-aggregated.txt \
 RUN:   --profile-format=fdata
 RUN: cat %t.fdata | sort | FileCheck %s -check-prefix=PERF2BOLT
 
 RUN: perf2bolt %t.exe -o %t.yaml --pa -p %p/Inputs/pre-aggregated.txt \
-RUN:   --profile-format=yaml
+RUN:   --profile-format=yaml --profile-use-dfs
 RUN: cat %t.yaml | FileCheck %s -check-prefix=NEWFORMAT
 
 # Test --profile-format option with llvm-bolt --aggregate-only
 RUN: llvm-bolt %t.exe -o %t.bolt.fdata --pa -p %p/Inputs/pre-aggregated.txt \
 RUN:   --aggregate-only --profile-format=fdata
 RUN: cat %t.bolt.fdata | sort | FileCheck %s -check-prefix=PERF2BOLT
 
 RUN: llvm-bolt %t.exe -o %t.bolt.yaml --pa -p %p/Inputs/pre-aggregated.txt \
-RUN:   --aggregate-only --profile-format=yaml
+RUN:   --aggregate-only --profile-format=yaml --profile-use-dfs
 RUN: cat %t.bolt.yaml | FileCheck %s -check-prefix=NEWFORMAT
 
 PERF2BOLT: 0 [unknown] 7f36d18d60c0 1 main 53c 0 2
 PERF2BOLT: 1 main 451 1 SolveCubic 0 0 2
 PERF2BOLT: 1 main 490 0 [unknown] 4005f0 0 1
 PERF2BOLT: 1 main 537 0 [unknown] 400610 0 1
 PERF2BOLT: 1 usqrt 30 1 usqrt 32 0 22
 PERF2BOLT: 1 usqrt 30 1 usqrt 39 4 33

bolt/test/X86/reader-stale-yaml.test

 # This script checks that YamlProfileReader in llvm-bolt is reading data
 # correctly and stale data is corrected.
 
 RUN: yaml2obj %p/Inputs/blarge.yaml &> %t.exe
-RUN: llvm-bolt %t.exe -o /dev/null --b %p/Inputs/blarge_profile_stale.yaml --print-cfg --print-only=usqrt --infer-stale-profile=1 --profile-ignore-hash=1 \
-RUN:   2>&1 | FileCheck %s -check-prefix=CHECK
+RUN: llvm-bolt %t.exe -o /dev/null --b %p/Inputs/blarge_profile_stale.yaml \
+RUN:   --print-cfg --print-only=usqrt --infer-stale-profile=1 \
+RUN:   --profile-ignore-hash=1 --profile-use-dfs 2>&1 | FileCheck %s
 
 # Verify that yaml reader works as expected.
 CHECK:  pre-processing profile using YAML profile reader
 
 # Verify the inferred counts of "usqrt" that has stale profile:
 #   - the function has nblocks=6 in the profile, which makes it stale
 #   - block with bid=0 has an incorrect (missing) count, which is inferred
 CHECK:    Binary Function "usqrt" after building cfg {