[BOLT] A new code layout algorithm for function reordering [3b/3]

[spupyrev]

Summary

This is a new algorithm for function layout (reordering) based on the call graph
extracted from a profile data; see diffs down the stack for more details.

This layout is very similar to the existing hfsort+, but perhaps a little better
on some benchmarks. The goals of the change is as follows:

(i) rename and replace hfsort+ with a newer (hopefully better) implementation.
I'd prefer to keep both algs together for some time to simplify evaluation and
transition, but do want to remove hfsort+ once we're confident that there are
no regressions.

(ii) unify the implementation of code layout algorithms across LLVM. Currently
Passes/HfsortPlus.cpp and Utils/CodeLayout.cpp share many implementation-specific
details; this diff unifies the code.

[spupyrev]

Since the upstream diffs have landed, this is now ready for review

[spupyrev]

nit

[spupyrev]

clang-format

[Amir]

I just pushed formatting the file as 2b642926b40b1f5d2e9525332a60d9502a289383, please rebase on top of that.

[spupyrev]

rebased past formatting

[Amir]

Thanks! Can we add any tests for the expected layout, using either in-tree or upstream bolt-tests binaries and profiles? I don't see any for hfsort/hfsort+ but I think we want to avoid regressing the layout.

bolt/lib/Passes/ReorderFunctions.cpp

346

I assume the definition lives in llvm/Transforms and we include the required component in CMakeLists?

[spupyrev]

I am adding an internal test for CDS

bolt/lib/Passes/ReorderFunctions.cpp

346

Yes, ReorderAlgorithm.cpp already uses on llvm/Transforms so it's not a new dependency.

[thakis]

Looks like this doesn't build on macOS: http://45.33.8.238/macm1/66080/step_4.txt

[spupyrev]

Sorry for overlooking this; here is a fix: https://reviews.llvm.org/D156734

[thakis]

Thanks!

bolt/include/bolt/Passes/ReorderFunctions.h

void printStats(const std::vector<Cluster> &Clusters,
                   const std::vector<uint64_t> &FuncAddr);
 
 public:
   enum ReorderType : char {
     RT_NONE = 0,
     RT_EXEC_COUNT,
     RT_HFSORT,
     RT_HFSORT_PLUS,
+    RT_CDS,
     RT_PETTIS_HANSEN,
     RT_RANDOM,
     RT_USER
   };
 
   explicit ReorderFunctions(const cl::opt<bool> &PrintPass)
       : BinaryFunctionPass(PrintPass) {}
 

bolt/lib/Passes/ReorderFunctions.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "bolt/Passes/ReorderFunctions.h"
 #include "bolt/Passes/HFSort.h"
 #include "bolt/Utils/Utils.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Transforms/Utils/CodeLayout.h"
 #include <fstream>
 
 #define DEBUG_TYPE "hfsort"
 
 using namespace llvm;
 
 namespace opts {
 
 extern cl::OptionCategory BoltOptCategory;
 extern cl::opt<unsigned> Verbosity;
 extern cl::opt<uint32_t> RandomSeed;
 
 extern size_t padFunction(const bolt::BinaryFunction &Function);
 
-cl::opt<bolt::ReorderFunctions::ReorderType>
-ReorderFunctions("reorder-functions",
+cl::opt<bolt::ReorderFunctions::ReorderType> ReorderFunctions(
+    "reorder-functions",
     cl::desc("reorder and cluster functions (works only with relocations)"),
     cl::init(bolt::ReorderFunctions::RT_NONE),
-  cl::values(clEnumValN(bolt::ReorderFunctions::RT_NONE,
-      "none",
+    cl::values(clEnumValN(bolt::ReorderFunctions::RT_NONE, "none",
                           "do not reorder functions"),
-    clEnumValN(bolt::ReorderFunctions::RT_EXEC_COUNT,
-      "exec-count",
+               clEnumValN(bolt::ReorderFunctions::RT_EXEC_COUNT, "exec-count",
                           "order by execution count"),
-    clEnumValN(bolt::ReorderFunctions::RT_HFSORT,
-      "hfsort",
+               clEnumValN(bolt::ReorderFunctions::RT_HFSORT, "hfsort",
                           "use hfsort algorithm"),
-    clEnumValN(bolt::ReorderFunctions::RT_HFSORT_PLUS,
-      "hfsort+",
+               clEnumValN(bolt::ReorderFunctions::RT_HFSORT_PLUS, "hfsort+",
                           "use hfsort+ algorithm"),
+               clEnumValN(bolt::ReorderFunctions::RT_CDS, "cds",
+                          "use cache-directed sort"),
                clEnumValN(bolt::ReorderFunctions::RT_PETTIS_HANSEN,
-      "pettis-hansen",
-      "use Pettis-Hansen algorithm"),
-    clEnumValN(bolt::ReorderFunctions::RT_RANDOM,
-      "random",
+                          "pettis-hansen", "use Pettis-Hansen algorithm"),
+               clEnumValN(bolt::ReorderFunctions::RT_RANDOM, "random",
                           "reorder functions randomly"),
-    clEnumValN(bolt::ReorderFunctions::RT_USER,
-      "user",
+               clEnumValN(bolt::ReorderFunctions::RT_USER, "user",
                           "use function order specified by -function-order")),
-  cl::ZeroOrMore,
-  cl::cat(BoltOptCategory));
+    cl::ZeroOrMore, cl::cat(BoltOptCategory));
 
 static cl::opt<bool> ReorderFunctionsUseHotSize(
     "reorder-functions-use-hot-size",
     cl::desc("use a function's hot size when doing clustering"), cl::init(true),
     cl::cat(BoltOptCategory));
 
 static cl::opt<std::string>
 FunctionOrderFile("function-order",
case RT_EXEC_COUNT:
     }
     break;
   case RT_HFSORT:
     Clusters = clusterize(Cg);
     break;
   case RT_HFSORT_PLUS:
     Clusters = hfsortPlus(Cg);
     break;
+  case RT_CDS: {
+    // It is required that the sum of incoming arc weights is not greater
+    // than the number of samples for every function. Ensuring the call graph
+    // obeys the property before running the algorithm.
+    Cg.adjustArcWeights();
+
+    // Initialize CFG nodes and their data
+    std::vector<uint64_t> FuncSizes;
+    std::vector<uint64_t> FuncCounts;
+    using JumpT = std::pair<uint64_t, uint64_t>;
+    std::vector<std::pair<JumpT, uint64_t>> CallCounts;
+    std::vector<uint64_t> CallOffsets;
+    for (NodeId F = 0; F < Cg.numNodes(); ++F) {
+      FuncSizes.push_back(Cg.size(F));
+      FuncCounts.push_back(Cg.samples(F));
+      for (NodeId Succ : Cg.successors(F)) {
+        const Arc &Arc = *Cg.findArc(F, Succ);
+        auto It = std::make_pair(F, Succ);
+        CallCounts.push_back(std::make_pair(It, Arc.weight()));
+        CallOffsets.push_back(uint64_t(Arc.avgCallOffset()));
+      }
+    }
+
+    // Run the layout algorithm.
+    std::vector<uint64_t> Result =
+        applyCDSLayout(FuncSizes, FuncCounts, CallCounts, CallOffsets);
+
+    // Set the order of hot functions based on the layout
+    uint32_t Index = 0;
+    for (uint64_t FuncId : Result)
+      Cg.nodeIdToFunc(FuncId)->setIndex(Index++);
+  } break;
   case RT_PETTIS_HANSEN:
     Clusters = pettisAndHansen(Cg);
     break;
   case RT_RANDOM:
     std::srand(opts::RandomSeed);
     Clusters = randomClusters(Cg);
     break;
   case RT_USER:

llvm/lib/Transforms/Utils/CodeLayout.cpp

llvm::applyExtTspLayout(const std::vector<uint64_t> &NodeSizes,
   assert(NodeCounts.size() == NodeSizes.size() && "Incorrect input");
   assert(NodeSizes.size() > 2 && "Incorrect input");
 
   // Apply the reordering algorithm.
   ExtTSPImpl Alg(NodeSizes, NodeCounts, EdgeCounts);
   std::vector<uint64_t> Result;
   Alg.run(Result);
 
-  // Verify correctness of the output.
+  // Verify correctness of the output
   assert(Result.front() == 0 && "Original entry point is not preserved");
   assert(Result.size() == NodeSizes.size() && "Incorrect size of layout");
   return Result;
 }
 
 double llvm::calcExtTspScore(const std::vector<uint64_t> &Order,
                              const std::vector<uint64_t> &NodeSizes,
                              const std::vector<uint64_t> &NodeCounts,