[CodeLayout] Refactor std::vector uses, namespace, and EdgeCountT. NFC

[MaskRay]

Summary

• Place types and functions in the llvm::codelayout namespace
• Change EdgeCountT from pair<pair<uint64_t, uint64_t>, uint64_t> to a struct and utilize structured bindings. It is not conventional to use the "T" suffix for structure types.
• Remove a redundant copy in ChainT::merge.
• Change {ExtTSPImpl,CDSortImpl}::run to use return value instead of an output parameter
• Rename applyCDSLayout to computeCacheDirectedLayout: (a) avoid rare abbreviation "CDS" (cache-directed sort) (b) "compute" is more conventional for the specific use case
• Change the parameter types from std::vector to ArrayRef so that SmallVector arguments can be used.
• Similarly, rename applyExtTspLayout to computeExtTspLayout.

[MaskRay]

.

[MaskRay]

remove JumpT

[dblaikie]

llvm/include/llvm/Transforms/Utils/CodeLayout.h

26–31

Might be at the point where this should/could be a struct with named members?

llvm/lib/Transforms/Utils/CodeLayout.cpp

1038

Then this (& elsewhere) wouldn't need a structured binding - it could access the members by name directly?

[ayermolo]

Isn't phabricator deprecated now, and all new reviews should be done on github?

[MaskRay]

In D159526#4647535, @ayermolo wrote:

Isn't phabricator deprecated now, and all new reviews should be done on github?

New reviews will be disabled on Oct 1 (or later, as I may be the operator and I will be out of town...). For this change it is convenient to use Phabricator to link to D152840

[MaskRay]

place functions under llvm::codelayout::

change EdgeCountT to a struct named EdgeCount

[dblaikie]

llvm/lib/Transforms/Utils/CodeLayout.cpp

1402–1404

I probably wouldn't use a structured binding if it's a struct with named members already (obfuscates that fact a bit, risks naming the bindings differently than the members, or having them otherwise get out of sync, etc). (similarly elsewhere in this change)

[MaskRay]

avoid structured bindings

[Amir]

Thank you for the refactoring. Looks good, but let me retrigger testing with the latest changes.
ping @spupyrev

[MaskRay]

Thank you for the stamp. I'll land this soon so that D152840 can rebase on top of it and we can have D152840 soon...

bolt/lib/Passes/ReorderAlgorithm.cpp

void ExtTSPReorderAlgorithm::reorderBasicBlocks(BinaryFunction &BF,
   for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     uint64_t Size = std::max<uint64_t>(BB->estimateSize(Emitter.MCE.get()), 1);
     BlockSizes.push_back(Size);
     BlockCounts.push_back(BB->getKnownExecutionCount());
     OrigOrder.push_back(BB);
   }
 
   // Initialize CFG edges
-  using JumpT = std::pair<uint64_t, uint64_t>;
-  std::vector<std::pair<JumpT, uint64_t>> JumpCounts;
+  std::vector<codelayout::EdgeCount> JumpCounts;
   for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
     auto BI = BB->branch_info_begin();
     for (BinaryBasicBlock *SuccBB : BB->successors()) {
       assert(BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE &&
              "missing profile for a jump");
-      auto It = std::make_pair(BB->getLayoutIndex(), SuccBB->getLayoutIndex());
-      JumpCounts.push_back(std::make_pair(It, BI->Count));
+      JumpCounts.push_back(
+          {BB->getLayoutIndex(), SuccBB->getLayoutIndex(), BI->Count});
       ++BI;
     }
   }
 
   // Run the layout algorithm
-  auto Result = applyExtTspLayout(BlockSizes, BlockCounts, JumpCounts);
+  auto Result =
+      codelayout::computeExtTspLayout(BlockSizes, BlockCounts, JumpCounts);
   Order.reserve(BF.getLayout().block_size());
   for (uint64_t R : Result)
     Order.push_back(OrigOrder[R]);
 }
 
 void OptimizeReorderAlgorithm::reorderBasicBlocks(
     BinaryFunction &BF, BasicBlockOrder &Order) const {
   if (BF.getLayout().block_empty())

bolt/lib/Passes/ReorderFunctions.cpp

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<codelayout::EdgeCount> 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()));
+        CallCounts.push_back({F, Succ, uint64_t(Arc.weight())});
         CallOffsets.push_back(uint64_t(Arc.avgCallOffset()));
       }
     }
 
     // Run the layout algorithm.
-    std::vector<uint64_t> Result =
-        applyCDSLayout(FuncSizes, FuncCounts, CallCounts, CallOffsets);
+    std::vector<uint64_t> Result = codelayout::computeCacheDirectedLayout(
+        FuncSizes, FuncCounts, CallCounts, CallOffsets);
 
     // Create a single cluster from the computed order of hot functions.
     std::vector<CallGraph::NodeId> NodeOrder(Result.begin(), Result.end());
     Clusters.emplace_back(Cluster(NodeOrder, Cg));
   } break;
   case RT_PETTIS_HANSEN:
     Clusters = pettisAndHansen(Cg);
     break;

llvm/include/llvm/Transforms/Utils/CodeLayout.h

 //===- CodeLayout.h - Code layout/placement algorithms  ---------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 /// \file
 /// Declares methods and data structures for code layout algorithms.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_UTILS_CODELAYOUT_H
 #define LLVM_TRANSFORMS_UTILS_CODELAYOUT_H
 
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 
+#include <utility>
 #include <vector>
 
-namespace llvm {
+namespace llvm::codelayout {
 
 using EdgeT = std::pair<uint64_t, uint64_t>;
-using EdgeCountT = std::pair<EdgeT, uint64_t>;
+
+struct EdgeCount {
+  uint64_t src;
+  uint64_t dst;
+  uint64_t count;
+};
 
 /// Find a layout of nodes (basic blocks) of a given CFG optimizing jump
 /// locality and thus processor I-cache utilization. This is achieved via
 /// increasing the number of fall-through jumps and co-locating frequently
 /// executed nodes together.
 /// The nodes are assumed to be indexed by integers from [0, |V|) so that the
 /// current order is the identity permutation.
 /// \p NodeSizes: The sizes of the nodes (in bytes).
 /// \p NodeCounts: The execution counts of the nodes in the profile.
 /// \p EdgeCounts: The execution counts of every edge (jump) in the profile. The
 ///    map also defines the edges in CFG and should include 0-count edges.
 /// \returns The best block order found.
-std::vector<uint64_t>
-applyExtTspLayout(const std::vector<uint64_t> &NodeSizes,
-                  const std::vector<uint64_t> &NodeCounts,
-                  const std::vector<EdgeCountT> &EdgeCounts);
+std::vector<uint64_t> computeExtTspLayout(ArrayRef<uint64_t> NodeSizes,
+                                          ArrayRef<uint64_t> NodeCounts,
+                                          ArrayRef<EdgeCount> EdgeCounts);
 
 /// Estimate the "quality" of a given node order in CFG. The higher the score,
 /// the better the order is. The score is designed to reflect the locality of
 /// the given order, which is anti-correlated with the number of I-cache misses
 /// in a typical execution of the function.
-double calcExtTspScore(const std::vector<uint64_t> &Order,
-                       const std::vector<uint64_t> &NodeSizes,
-                       const std::vector<uint64_t> &NodeCounts,
-                       const std::vector<EdgeCountT> &EdgeCounts);
+double calcExtTspScore(ArrayRef<uint64_t> Order, ArrayRef<uint64_t> NodeSizes,
+                       ArrayRef<uint64_t> NodeCounts,
+                       ArrayRef<EdgeCount> EdgeCounts);
 
 /// Estimate the "quality" of the current node order in CFG.
-double calcExtTspScore(const std::vector<uint64_t> &NodeSizes,
-                       const std::vector<uint64_t> &NodeCounts,
-                       const std::vector<EdgeCountT> &EdgeCounts);
+double calcExtTspScore(ArrayRef<uint64_t> NodeSizes,
+                       ArrayRef<uint64_t> NodeCounts,
+                       ArrayRef<EdgeCount> EdgeCounts);
 
 /// Algorithm-specific params for Cache-Directed Sort. The values are tuned for
 /// the best performance of large-scale front-end bound binaries.
 struct CDSortConfig {
   /// The size of the cache.
   unsigned CacheEntries = 16;
   /// The size of a line in the cache.
   unsigned CacheSize = 2048;
   /// The power exponent for the distance-based locality.
   double DistancePower = 0.25;
   /// The scale factor for the frequency-based locality.
   double FrequencyScale = 0.25;
 };
 
 /// Apply a Cache-Directed Sort for functions represented by a call graph.
 /// The placement is done by optimizing the call locality by co-locating
 /// frequently executed functions.
 /// \p FuncSizes: The sizes of the nodes (in bytes).
 /// \p FuncCounts: The execution counts of the nodes in the profile.
 /// \p CallCounts: The execution counts of every edge (jump) in the profile. The
 ///    map also defines the edges in CFG and should include 0-count edges.
 /// \p CallOffsets: The offsets of the calls from their source nodes.
 /// \returns The best function order found.
-std::vector<uint64_t> applyCDSLayout(const std::vector<uint64_t> &FuncSizes,
-                                     const std::vector<uint64_t> &FuncCounts,
-                                     const std::vector<EdgeCountT> &CallCounts,
-                                     const std::vector<uint64_t> &CallOffsets);
+std::vector<uint64_t> computeCacheDirectedLayout(
+    ArrayRef<uint64_t> FuncSizes, ArrayRef<uint64_t> FuncCounts,
+    ArrayRef<EdgeCount> CallCounts, ArrayRef<uint64_t> CallOffsets);
 
 /// Apply a Cache-Directed Sort with a custom config.
-std::vector<uint64_t> applyCDSLayout(const CDSortConfig &Config,
-                                     const std::vector<uint64_t> &FuncSizes,
-                                     const std::vector<uint64_t> &FuncCounts,
-                                     const std::vector<EdgeCountT> &CallCounts,
-                                     const std::vector<uint64_t> &CallOffsets);
+std::vector<uint64_t> computeCacheDirectedLayout(
+    const CDSortConfig &Config, ArrayRef<uint64_t> FuncSizes,
+    ArrayRef<uint64_t> FuncCounts, ArrayRef<EdgeCount> CallCounts,
+    ArrayRef<uint64_t> CallOffsets);
 
-} // end namespace llvm
+} // namespace llvm::codelayout
 
 #endif // LLVM_TRANSFORMS_UTILS_CODELAYOUT_H

llvm/lib/CodeGen/MachineBlockPlacement.cpp

void MachineBlockPlacement::applyExtTsp() {
   size_t NumBlocks = 0;
   for (const MachineBasicBlock &MBB : *F) {
     BlockIndex[&MBB] = NumBlocks++;
     CurrentBlockOrder.push_back(&MBB);
   }
 
   auto BlockSizes = std::vector<uint64_t>(F->size());
   auto BlockCounts = std::vector<uint64_t>(F->size());
-  std::vector<EdgeCountT> JumpCounts;
+  std::vector<codelayout::EdgeCount> JumpCounts;
   for (MachineBasicBlock &MBB : *F) {
     // Getting the block frequency.
     BlockFrequency BlockFreq = MBFI->getBlockFreq(&MBB);
     BlockCounts[BlockIndex[&MBB]] = BlockFreq.getFrequency();
     // Getting the block size:
     // - approximate the size of an instruction by 4 bytes, and
     // - ignore debug instructions.
     // Note: getting the exact size of each block is target-dependent and can be
     // done by extending the interface of MCCodeEmitter. Experimentally we do
     // not see a perf improvement with the exact block sizes.
     auto NonDbgInsts =
         instructionsWithoutDebug(MBB.instr_begin(), MBB.instr_end());
     int NumInsts = std::distance(NonDbgInsts.begin(), NonDbgInsts.end());
     BlockSizes[BlockIndex[&MBB]] = 4 * NumInsts;
     // Getting jump frequencies.
     for (MachineBasicBlock *Succ : MBB.successors()) {
       auto EP = MBPI->getEdgeProbability(&MBB, Succ);
       BlockFrequency JumpFreq = BlockFreq * EP;
-      auto Jump = std::make_pair(BlockIndex[&MBB], BlockIndex[Succ]);
-      JumpCounts.push_back(std::make_pair(Jump, JumpFreq.getFrequency()));
+      JumpCounts.push_back(
+          {BlockIndex[&MBB], BlockIndex[Succ], JumpFreq.getFrequency()});
     }
   }
 
   LLVM_DEBUG(dbgs() << "Applying ext-tsp layout for |V| = " << F->size()
                     << " with profile = " << F->getFunction().hasProfileData()
                     << " (" << F->getName().str() << ")"
                     << "\n");
   LLVM_DEBUG(
       dbgs() << format("  original  layout score: %0.2f\n",
                        calcExtTspScore(BlockSizes, BlockCounts, JumpCounts)));
 
   // Run the layout algorithm.
-  auto NewOrder = applyExtTspLayout(BlockSizes, BlockCounts, JumpCounts);
+  auto NewOrder = computeExtTspLayout(BlockSizes, BlockCounts, JumpCounts);
   std::vector<const MachineBasicBlock *> NewBlockOrder;
   NewBlockOrder.reserve(F->size());
   for (uint64_t Node : NewOrder) {
     NewBlockOrder.push_back(CurrentBlockOrder[Node]);
   }
   LLVM_DEBUG(dbgs() << format("  optimized layout score: %0.2f\n",
                               calcExtTspScore(NewOrder, BlockSizes, BlockCounts,
                                               JumpCounts)));

llvm/lib/Transforms/Utils/CodeLayout.cpp

 #include "llvm/Transforms/Utils/CodeLayout.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 
 #include <cmath>
 #include <set>
 
 using namespace llvm;
+using namespace llvm::codelayout;
+
 #define DEBUG_TYPE "code-layout"
 
 namespace llvm {
 cl::opt<bool> EnableExtTspBlockPlacement(
     "enable-ext-tsp-block-placement", cl::Hidden, cl::init(false),
     cl::desc("Enable machine block placement based on the ext-tsp model, "
              "optimizing I-cache utilization."));
 
while (It != Edges.end()) {
       It++;
     }
   }
 
   void addEdge(ChainT *Other, ChainEdge *Edge) {
     Edges.push_back(std::make_pair(Other, Edge));
   }
 
-  void merge(ChainT *Other, const std::vector<NodeT *> &MergedBlocks) {
-    Nodes = MergedBlocks;
+  void merge(ChainT *Other, std::vector<NodeT *> MergedBlocks) {
+    Nodes = std::move(MergedBlocks);
     // Update the chain's data.
     ExecutionCount += Other->ExecutionCount;
     Size += Other->Size;
     Id = Nodes[0]->Index;
     // Update the node's data.
     for (size_t Idx = 0; Idx < Nodes.size(); Idx++) {
       Nodes[Idx]->CurChain = this;
       Nodes[Idx]->CurIndex = Idx;
case MergeTypeT::X2_X1_Y:
     return MergedChain(BeginX2, EndX2, BeginX1, EndX1, BeginY, EndY);
   }
   llvm_unreachable("unexpected chain merge type");
 }
 
 /// The implementation of the ExtTSP algorithm.
 class ExtTSPImpl {
 public:
-  ExtTSPImpl(const std::vector<uint64_t> &NodeSizes,
-             const std::vector<uint64_t> &NodeCounts,
-             const std::vector<EdgeCountT> &EdgeCounts)
+  ExtTSPImpl(ArrayRef<uint64_t> NodeSizes, ArrayRef<uint64_t> NodeCounts,
+             ArrayRef<EdgeCount> EdgeCounts)
       : NumNodes(NodeSizes.size()) {
     initialize(NodeSizes, NodeCounts, EdgeCounts);
   }
 
   /// Run the algorithm and return an optimized ordering of nodes.
-  void run(std::vector<uint64_t> &Result) {
+  std::vector<uint64_t> run() {
     // Pass 1: Merge nodes with their mutually forced successors
     mergeForcedPairs();
 
     // Pass 2: Merge pairs of chains while improving the ExtTSP objective
     mergeChainPairs();
 
     // Pass 3: Merge cold nodes to reduce code size
     mergeColdChains();
 
     // Collect nodes from all chains
-    concatChains(Result);
+    return concatChains();
   }
 
 private:
   /// Initialize the algorithm's data structures.
-  void initialize(const std::vector<uint64_t> &NodeSizes,
-                  const std::vector<uint64_t> &NodeCounts,
-                  const std::vector<EdgeCountT> &EdgeCounts) {
+  void initialize(const ArrayRef<uint64_t> &NodeSizes,
+                  const ArrayRef<uint64_t> &NodeCounts,
+                  const ArrayRef<EdgeCount> &EdgeCounts) {
     // Initialize nodes
     AllNodes.reserve(NumNodes);
     for (uint64_t Idx = 0; Idx < NumNodes; Idx++) {
       uint64_t Size = std::max<uint64_t>(NodeSizes[Idx], 1ULL);
       uint64_t ExecutionCount = NodeCounts[Idx];
       // The execution count of the entry node is set to at least one.
       if (Idx == 0 && ExecutionCount == 0)
         ExecutionCount = 1;
       AllNodes.emplace_back(Idx, Size, ExecutionCount);
     }
 
     // Initialize jumps between nodes
     SuccNodes.resize(NumNodes);
     PredNodes.resize(NumNodes);
     std::vector<uint64_t> OutDegree(NumNodes, 0);
     AllJumps.reserve(EdgeCounts.size());
-    for (auto It : EdgeCounts) {
-      uint64_t Pred = It.first.first;
-      uint64_t Succ = It.first.second;
-      OutDegree[Pred]++;
+    for (auto Edge : EdgeCounts) {
+      ++OutDegree[Edge.src];
       // Ignore self-edges.
-      if (Pred == Succ)
+      if (Edge.src == Edge.dst)
         continue;
 
-      SuccNodes[Pred].push_back(Succ);
-      PredNodes[Succ].push_back(Pred);
-      uint64_t ExecutionCount = It.second;
-      if (ExecutionCount > 0) {
-        NodeT &PredNode = AllNodes[Pred];
-        NodeT &SuccNode = AllNodes[Succ];
-        AllJumps.emplace_back(&PredNode, &SuccNode, ExecutionCount);
+      SuccNodes[Edge.src].push_back(Edge.dst);
+      PredNodes[Edge.dst].push_back(Edge.src);
+      if (Edge.count > 0) {
+        NodeT &PredNode = AllNodes[Edge.src];
+        NodeT &SuccNode = AllNodes[Edge.dst];
+        AllJumps.emplace_back(&PredNode, &SuccNode, Edge.count);
         SuccNode.InJumps.push_back(&AllJumps.back());
         PredNode.OutJumps.push_back(&AllJumps.back());
       }
     }
     for (JumpT &Jump : AllJumps) {
       assert(OutDegree[Jump.Source->Index] > 0);
       Jump.IsConditional = OutDegree[Jump.Source->Index] > 1;
     }
void mergeChains(ChainT *Into, ChainT *From, size_t MergeOffset,
     llvm::erase_value(HotChains, From);
 
     // Invalidate caches.
     for (auto EdgeIt : Into->Edges)
       EdgeIt.second->invalidateCache();
   }
 
   /// Concatenate all chains into the final order.
-  void concatChains(std::vector<uint64_t> &Order) {
+  std::vector<uint64_t> concatChains() {
     // Collect chains and calculate density stats for their sorting.
     std::vector<const ChainT *> SortedChains;
     DenseMap<const ChainT *, double> ChainDensity;
     for (ChainT &Chain : AllChains) {
       if (!Chain.Nodes.empty()) {
         SortedChains.push_back(&Chain);
         // Using doubles to avoid overflow of ExecutionCounts.
         double Size = 0;
std::sort(SortedChains.begin(), SortedChains.end(),
                 const double DL = ChainDensity[L];
                 const double DR = ChainDensity[R];
                 // Compare by density and break ties by chain identifiers.
                 return std::make_tuple(-DL, L->Id) <
                        std::make_tuple(-DR, R->Id);
               });
 
     // Collect the nodes in the order specified by their chains.
+    std::vector<uint64_t> Order;
     Order.reserve(NumNodes);
-    for (const ChainT *Chain : SortedChains) {
-      for (NodeT *Node : Chain->Nodes) {
+    for (const ChainT *Chain : SortedChains)
+      for (NodeT *Node : Chain->Nodes)
         Order.push_back(Node->Index);
-      }
-    }
+    return Order;
   }
 
 private:
   /// The number of nodes in the graph.
   const size_t NumNodes;
 
   /// Successors of each node.
   std::vector<std::vector<uint64_t>> SuccNodes;
private:
   /// Active chains. The vector gets updated at runtime when chains are merged.
   std::vector<ChainT *> HotChains;
 };
 
 /// The implementation of the Cache-Directed Sort (CDS) algorithm for ordering
 /// functions represented by a call graph.
 class CDSortImpl {
 public:
-  CDSortImpl(const CDSortConfig &Config, const std::vector<uint64_t> &NodeSizes,
-             const std::vector<uint64_t> &NodeCounts,
-             const std::vector<EdgeCountT> &EdgeCounts,
-             const std::vector<uint64_t> &EdgeOffsets)
+  CDSortImpl(const CDSortConfig &Config, ArrayRef<uint64_t> NodeSizes,
+             ArrayRef<uint64_t> NodeCounts, ArrayRef<EdgeCount> EdgeCounts,
+             ArrayRef<uint64_t> EdgeOffsets)
       : Config(Config), NumNodes(NodeSizes.size()) {
     initialize(NodeSizes, NodeCounts, EdgeCounts, EdgeOffsets);
   }
 
   /// Run the algorithm and return an ordered set of function clusters.
-  void run(std::vector<uint64_t> &Result) {
+  std::vector<uint64_t> run() {
     // Merge pairs of chains while improving the objective.
     mergeChainPairs();
 
     LLVM_DEBUG(dbgs() << "Cache-directed function sorting reduced the number"
                       << " of chains from " << NumNodes << " to "
                       << HotChains.size() << "\n");
 
     // Collect nodes from all the chains.
-    concatChains(Result);
+    return concatChains();
   }
 
 private:
   /// Initialize the algorithm's data structures.
-  void initialize(const std::vector<uint64_t> &NodeSizes,
-                  const std::vector<uint64_t> &NodeCounts,
-                  const std::vector<EdgeCountT> &EdgeCounts,
-                  const std::vector<uint64_t> &EdgeOffsets) {
+  void initialize(const ArrayRef<uint64_t> &NodeSizes,
+                  const ArrayRef<uint64_t> &NodeCounts,
+                  const ArrayRef<EdgeCount> &EdgeCounts,
+                  const ArrayRef<uint64_t> &EdgeOffsets) {
     // Initialize nodes.
     AllNodes.reserve(NumNodes);
     for (uint64_t Node = 0; Node < NumNodes; Node++) {
       uint64_t Size = std::max<uint64_t>(NodeSizes[Node], 1ULL);
       uint64_t ExecutionCount = NodeCounts[Node];
       AllNodes.emplace_back(Node, Size, ExecutionCount);
       TotalSamples += ExecutionCount;
       if (ExecutionCount > 0)
         TotalSize += Size;
     }
 
     // Initialize jumps between the nodes.
     SuccNodes.resize(NumNodes);
     PredNodes.resize(NumNodes);
     AllJumps.reserve(EdgeCounts.size());
     for (size_t I = 0; I < EdgeCounts.size(); I++) {
-      auto It = EdgeCounts[I];
-      uint64_t Pred = It.first.first;
-      uint64_t Succ = It.first.second;
+      auto [Pred, Succ, Count] = EdgeCounts[I];
       // Ignore recursive calls.
       if (Pred == Succ)
         continue;
 
       SuccNodes[Pred].push_back(Succ);
       PredNodes[Succ].push_back(Pred);
-      uint64_t ExecutionCount = It.second;
-      if (ExecutionCount > 0) {
+      if (Count > 0) {
         NodeT &PredNode = AllNodes[Pred];
         NodeT &SuccNode = AllNodes[Succ];
-        AllJumps.emplace_back(&PredNode, &SuccNode, ExecutionCount);
+        AllJumps.emplace_back(&PredNode, &SuccNode, Count);
         AllJumps.back().Offset = EdgeOffsets[I];
         SuccNode.InJumps.push_back(&AllJumps.back());
         PredNode.OutJumps.push_back(&AllJumps.back());
       }
     }
 
     // Initialize chains.
     AllChains.reserve(NumNodes);
void mergeChains(ChainT *Into, ChainT *From, size_t MergeOffset,
     Into->mergeEdges(From);
     From->clear();
 
     // Remove the chain from the list of active chains.
     llvm::erase_value(HotChains, From);
   }
 
   /// Concatenate all chains into the final order.
-  void concatChains(std::vector<uint64_t> &Order) {
+  std::vector<uint64_t> concatChains() {
     // Collect chains and calculate density stats for their sorting.
     std::vector<const ChainT *> SortedChains;
     DenseMap<const ChainT *, double> ChainDensity;
     for (ChainT &Chain : AllChains) {
       if (!Chain.Nodes.empty()) {
         SortedChains.push_back(&Chain);
         // Using doubles to avoid overflow of ExecutionCounts.
         double Size = 0;
std::sort(SortedChains.begin(), SortedChains.end(),
                 const double DL = ChainDensity[L];
                 const double DR = ChainDensity[R];
                 // Compare by density and break ties by chain identifiers.
                 return std::make_tuple(-DL, L->Id) <
                        std::make_tuple(-DR, R->Id);
               });
 
     // Collect the nodes in the order specified by their chains.
+    std::vector<uint64_t> Order;
     Order.reserve(NumNodes);
     for (const ChainT *Chain : SortedChains)
       for (NodeT *Node : Chain->Nodes)
         Order.push_back(Node->Index);
+    return Order;
   }
 
 private:
   /// Config for the algorithm.
   const CDSortConfig Config;
 
   /// The number of nodes in the graph.
   const size_t NumNodes;
private:
 
   /// The total size of the nodes in the graph.
   uint64_t TotalSize{0};
 };
 
 } // end of anonymous namespace
 
 std::vector<uint64_t>
-llvm::applyExtTspLayout(const std::vector<uint64_t> &NodeSizes,
-                        const std::vector<uint64_t> &NodeCounts,
-                        const std::vector<EdgeCountT> &EdgeCounts) {
+codelayout::computeExtTspLayout(ArrayRef<uint64_t> NodeSizes,
+                                ArrayRef<uint64_t> NodeCounts,
+                                ArrayRef<EdgeCount> EdgeCounts) {
   // Verify correctness of the input data.
   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);
+  std::vector<uint64_t> Result = Alg.run();
 
   // 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,
-                             const std::vector<EdgeCountT> &EdgeCounts) {
+double codelayout::calcExtTspScore(ArrayRef<uint64_t> Order,
+                                   ArrayRef<uint64_t> NodeSizes,
+                                   ArrayRef<uint64_t> NodeCounts,
+                                   ArrayRef<EdgeCount> EdgeCounts) {
   // Estimate addresses of the blocks in memory.
   std::vector<uint64_t> Addr(NodeSizes.size(), 0);
   for (size_t Idx = 1; Idx < Order.size(); Idx++) {
     Addr[Order[Idx]] = Addr[Order[Idx - 1]] + NodeSizes[Order[Idx - 1]];
   }
   std::vector<uint64_t> OutDegree(NodeSizes.size(), 0);
-  for (auto It : EdgeCounts) {
-    uint64_t Pred = It.first.first;
-    OutDegree[Pred]++;
-  }
+  for (auto Edge : EdgeCounts)
+    ++OutDegree[Edge.src];
 
   // Increase the score for each jump.
   double Score = 0;
-  for (auto It : EdgeCounts) {
-    uint64_t Pred = It.first.first;
-    uint64_t Succ = It.first.second;
-    uint64_t Count = It.second;
-    bool IsConditional = OutDegree[Pred] > 1;
-    Score += ::extTSPScore(Addr[Pred], NodeSizes[Pred], Addr[Succ], Count,
-                           IsConditional);
+  for (auto Edge : EdgeCounts) {
+    bool IsConditional = OutDegree[Edge.src] > 1;
+    Score += ::extTSPScore(Addr[Edge.src], NodeSizes[Edge.src], Addr[Edge.dst],
+                           Edge.count, IsConditional);
   }
   return Score;
 }
 
-double llvm::calcExtTspScore(const std::vector<uint64_t> &NodeSizes,
-                             const std::vector<uint64_t> &NodeCounts,
-                             const std::vector<EdgeCountT> &EdgeCounts) {
+double codelayout::calcExtTspScore(ArrayRef<uint64_t> NodeSizes,
+                                   ArrayRef<uint64_t> NodeCounts,
+                                   ArrayRef<EdgeCount> EdgeCounts) {
   std::vector<uint64_t> Order(NodeSizes.size());
   for (size_t Idx = 0; Idx < NodeSizes.size(); Idx++) {
     Order[Idx] = Idx;
   }
   return calcExtTspScore(Order, NodeSizes, NodeCounts, EdgeCounts);
 }
 
-std::vector<uint64_t>
-llvm::applyCDSLayout(const CDSortConfig &Config,
-                     const std::vector<uint64_t> &FuncSizes,
-                     const std::vector<uint64_t> &FuncCounts,
-                     const std::vector<EdgeCountT> &CallCounts,
-                     const std::vector<uint64_t> &CallOffsets) {
+std::vector<uint64_t> codelayout::computeCacheDirectedLayout(
+    const CDSortConfig &Config, ArrayRef<uint64_t> FuncSizes,
+    ArrayRef<uint64_t> FuncCounts, ArrayRef<EdgeCount> CallCounts,
+    ArrayRef<uint64_t> CallOffsets) {
   // Verify correctness of the input data.
   assert(FuncCounts.size() == FuncSizes.size() && "Incorrect input");
 
   // Apply the reordering algorithm.
   CDSortImpl Alg(Config, FuncSizes, FuncCounts, CallCounts, CallOffsets);
-  std::vector<uint64_t> Result;
-  Alg.run(Result);
-
-  // Verify correctness of the output.
+  std::vector<uint64_t> Result = Alg.run();
   assert(Result.size() == FuncSizes.size() && "Incorrect size of layout");
   return Result;
 }
 
-std::vector<uint64_t>
-llvm::applyCDSLayout(const std::vector<uint64_t> &FuncSizes,
-                     const std::vector<uint64_t> &FuncCounts,
-                     const std::vector<EdgeCountT> &CallCounts,
-                     const std::vector<uint64_t> &CallOffsets) {
+std::vector<uint64_t> codelayout::computeCacheDirectedLayout(
+    ArrayRef<uint64_t> FuncSizes, ArrayRef<uint64_t> FuncCounts,
+    ArrayRef<EdgeCount> CallCounts, ArrayRef<uint64_t> CallOffsets) {
   CDSortConfig Config;
   // Populate the config from the command-line options.
   if (CacheEntries.getNumOccurrences() > 0)
     Config.CacheEntries = CacheEntries;
   if (CacheSize.getNumOccurrences() > 0)
     Config.CacheSize = CacheSize;
   if (DistancePower.getNumOccurrences() > 0)
     Config.DistancePower = DistancePower;
   if (FrequencyScale.getNumOccurrences() > 0)
     Config.FrequencyScale = FrequencyScale;
-  return applyCDSLayout(Config, FuncSizes, FuncCounts, CallCounts, CallOffsets);
+  return computeCacheDirectedLayout(Config, FuncSizes, FuncCounts, CallCounts,
+                                    CallOffsets);
 }