lib/Passes/ReorderAlgorithm.cpp

//===- bolt/Passes/ReorderAlgorithm.cpp - Basic block reordering ----------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// This file implements classes used by several basic block reordering
// algorithms.
//
//===----------------------------------------------------------------------===//

#include "bolt/Passes/ReorderAlgorithm.h"
#include "bolt/Core/BinaryBasicBlock.h"
#include "bolt/Core/BinaryFunction.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Transforms/Utils/CodeLayout.h"
#include <queue>
#include <random>
#include <stack>

#undef  DEBUG_TYPE
#define DEBUG_TYPE "bolt"

using namespace llvm;
using namespace bolt;

namespace opts {

extern cl::OptionCategory BoltOptCategory;
extern cl::opt<bool> NoThreads;

static cl::opt<unsigned> ColdThreshold(
    "cold-threshold",
    cl::desc("tenths of percents of main entry frequency to use as a "
             "threshold when evaluating whether a basic block is cold "
             "(0 means it is only considered cold if the block has zero "
             "samples). Default: 0 "),
    cl::init(0), cl::ZeroOrMore, cl::Hidden, cl::cat(BoltOptCategory));

static cl::opt<bool> PrintClusters("print-clusters", cl::desc("print clusters"),
                                   cl::Hidden, cl::cat(BoltOptCategory));

cl::opt<uint32_t> RandomSeed("bolt-seed", cl::desc("seed for randomization"),
                             cl::init(42), cl::Hidden,
                             cl::cat(BoltOptCategory));

} // namespace opts

namespace {

template <class T> inline void hashCombine(size_t &Seed, const T &Val) {
  std::hash<T> Hasher;
  Seed ^= Hasher(Val) + 0x9e3779b9 + (Seed << 6) + (Seed >> 2);
}

template <typename A, typename B> struct HashPair {
  size_t operator()(const std::pair<A, B> &Val) const {
    std::hash<A> Hasher;
    size_t Seed = Hasher(Val.first);
    hashCombine(Seed, Val.second);
    return Seed;
  }
};

} // namespace

void ClusterAlgorithm::computeClusterAverageFrequency(const BinaryContext &BC) {
  // Create a separate MCCodeEmitter to allow lock-free execution
  BinaryContext::IndependentCodeEmitter Emitter;
  if (!opts::NoThreads)
    Emitter = BC.createIndependentMCCodeEmitter();

  AvgFreq.resize(Clusters.size(), 0.0);
  for (uint32_t I = 0, E = Clusters.size(); I < E; ++I) {
    double Freq = 0.0;
    uint64_t ClusterSize = 0;
    for (const BinaryBasicBlock *BB : Clusters[I]) {
      if (BB->getNumNonPseudos() > 0) {
        Freq += BB->getExecutionCount();
        // Estimate the size of a block in bytes at run time
        // NOTE: This might be inaccurate
        ClusterSize += BB->estimateSize(Emitter.MCE.get());
      }
    }
    AvgFreq[I] = ClusterSize == 0 ? 0 : Freq / ClusterSize;
  }
}

void ClusterAlgorithm::printClusters() const {
  for (uint32_t I = 0, E = Clusters.size(); I < E; ++I) {
    errs() << "Cluster number " << I;
    if (AvgFreq.size() == Clusters.size())
      errs() << " (frequency: " << AvgFreq[I] << ")";
    errs() << " : ";
    const char *Sep = "";
    for (const BinaryBasicBlock *BB : Clusters[I]) {
      errs() << Sep << BB->getName();
      Sep = ", ";
    }
    errs() << "\n";
  }
}

void ClusterAlgorithm::reset() {
  Clusters.clear();
  ClusterEdges.clear();
  AvgFreq.clear();
}

void GreedyClusterAlgorithm::EdgeTy::print(raw_ostream &OS) const {
  OS << Src->getName() << " -> " << Dst->getName() << ", count: " << Count;
}

size_t GreedyClusterAlgorithm::EdgeHash::operator()(const EdgeTy &E) const {
  HashPair<const BinaryBasicBlock *, const BinaryBasicBlock *> Hasher;
  return Hasher(std::make_pair(E.Src, E.Dst));
}

bool GreedyClusterAlgorithm::EdgeEqual::operator()(const EdgeTy &A,
                                                   const EdgeTy &B) const {
  return A.Src == B.Src && A.Dst == B.Dst;
}

void GreedyClusterAlgorithm::clusterBasicBlocks(BinaryFunction &BF,
                                                bool ComputeEdges) {
  reset();

  // Greedy heuristic implementation for the TSP, applied to BB layout. Try to
  // maximize weight during a path traversing all BBs. In this way, we will
  // convert the hottest branches into fall-throughs.

  // This is the queue of edges from which we will pop edges and use them to
  // cluster basic blocks in a greedy fashion.
  std::vector<EdgeTy> Queue;

  // Initialize inter-cluster weights.
  if (ComputeEdges)
    ClusterEdges.resize(BF.getLayout().block_size());

  // Initialize clusters and edge queue.
  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
    // Create a cluster for this BB.
    uint32_t I = Clusters.size();
    Clusters.emplace_back();
    std::vector<BinaryBasicBlock *> &Cluster = Clusters.back();
    Cluster.push_back(BB);
    BBToClusterMap[BB] = I;
    // Populate priority queue with edges.
    auto BI = BB->branch_info_begin();
    for (const BinaryBasicBlock *I : BB->successors()) {
      assert(BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE &&
             "attempted reordering blocks of function with no profile data");
      Queue.emplace_back(EdgeTy(BB, I, BI->Count));
      ++BI;
    }
  }
  // Sort and adjust the edge queue.
  initQueue(Queue, BF);

  // Grow clusters in a greedy fashion.
  while (!Queue.empty()) {
    EdgeTy E = Queue.back();
    Queue.pop_back();

    const BinaryBasicBlock *SrcBB = E.Src;
    const BinaryBasicBlock *DstBB = E.Dst;

    LLVM_DEBUG(dbgs() << "Popped edge "; E.print(dbgs()); dbgs() << "\n");

    // Case 1: BBSrc and BBDst are the same. Ignore this edge
    if (SrcBB == DstBB || DstBB == *BF.getLayout().block_begin()) {
      LLVM_DEBUG(dbgs() << "\tIgnored (same src, dst)\n");
      continue;
    }

    int I = BBToClusterMap[SrcBB];
    int J = BBToClusterMap[DstBB];

    // Case 2: If they are already allocated at the same cluster, just increase
    // the weight of this cluster
    if (I == J) {
      if (ComputeEdges)
        ClusterEdges[I][I] += E.Count;
      LLVM_DEBUG(dbgs() << "\tIgnored (src, dst belong to the same cluster)\n");
      continue;
    }

    std::vector<BinaryBasicBlock *> &ClusterA = Clusters[I];
    std::vector<BinaryBasicBlock *> &ClusterB = Clusters[J];
    if (areClustersCompatible(ClusterA, ClusterB, E)) {
      // Case 3: SrcBB is at the end of a cluster and DstBB is at the start,
      // allowing us to merge two clusters.
      for (const BinaryBasicBlock *BB : ClusterB)
        BBToClusterMap[BB] = I;
      ClusterA.insert(ClusterA.end(), ClusterB.begin(), ClusterB.end());
      ClusterB.clear();
      if (ComputeEdges) {
        // Increase the intra-cluster edge count of cluster A with the count of
        // this edge as well as with the total count of previously visited edges
        // from cluster B cluster A.
        ClusterEdges[I][I] += E.Count;
        ClusterEdges[I][I] += ClusterEdges[J][I];
        // Iterate through all inter-cluster edges and transfer edges targeting
        // cluster B to cluster A.
        for (uint32_t K = 0, E = ClusterEdges.size(); K != E; ++K)
          ClusterEdges[K][I] += ClusterEdges[K][J];
      }
      // Adjust the weights of the remaining edges and re-sort the queue.
      adjustQueue(Queue, BF);
      LLVM_DEBUG(dbgs() << "\tMerged clusters of src, dst\n");
    } else {
      // Case 4: Both SrcBB and DstBB are allocated in positions we cannot
      // merge them. Add the count of this edge to the inter-cluster edge count
      // between clusters A and B to help us decide ordering between these
      // clusters.
      if (ComputeEdges)
        ClusterEdges[I][J] += E.Count;
      LLVM_DEBUG(
          dbgs() << "\tIgnored (src, dst belong to incompatible clusters)\n");
    }
  }
}

void GreedyClusterAlgorithm::reset() {
  ClusterAlgorithm::reset();
  BBToClusterMap.clear();
}

void PHGreedyClusterAlgorithm::initQueue(std::vector<EdgeTy> &Queue,
                                         const BinaryFunction &BF) {
  // Define a comparison function to establish SWO between edges.
  auto Comp = [&BF](const EdgeTy &A, const EdgeTy &B) {
    // With equal weights, prioritize branches with lower index
    // source/destination. This helps to keep original block order for blocks
    // when optimal order cannot be deducted from a profile.
    if (A.Count == B.Count) {
      const signed SrcOrder = BF.getOriginalLayoutRelativeOrder(A.Src, B.Src);
      return (SrcOrder != 0)
                 ? SrcOrder > 0
                 : BF.getOriginalLayoutRelativeOrder(A.Dst, B.Dst) > 0;
    }
    return A.Count < B.Count;
  };

  // Sort edges in increasing profile count order.
  llvm::sort(Queue, Comp);
}

void PHGreedyClusterAlgorithm::adjustQueue(std::vector<EdgeTy> &Queue,
                                           const BinaryFunction &BF) {
  // Nothing to do.
}

bool PHGreedyClusterAlgorithm::areClustersCompatible(const ClusterTy &Front,
                                                     const ClusterTy &Back,
                                                     const EdgeTy &E) const {
  return Front.back() == E.Src && Back.front() == E.Dst;
}

int64_t MinBranchGreedyClusterAlgorithm::calculateWeight(
    const EdgeTy &E, const BinaryFunction &BF) const {
  const BinaryBasicBlock *SrcBB = E.Src;
  const BinaryBasicBlock *DstBB = E.Dst;

  // Initial weight value.
  int64_t W = (int64_t)E.Count;

  // Adjust the weight by taking into account other edges with the same source.
  auto BI = SrcBB->branch_info_begin();
  for (const BinaryBasicBlock *SuccBB : SrcBB->successors()) {
    assert(BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE &&
           "attempted reordering blocks of function with no profile data");
    assert(BI->Count <= std::numeric_limits<int64_t>::max() &&
           "overflow detected");
    // Ignore edges with same source and destination, edges that target the
    // entry block as well as the edge E itself.
    if (SuccBB != SrcBB && SuccBB != *BF.getLayout().block_begin() &&
        SuccBB != DstBB)
      W -= (int64_t)BI->Count;
    ++BI;
  }

  // Adjust the weight by taking into account other edges with the same
  // destination.
  for (const BinaryBasicBlock *PredBB : DstBB->predecessors()) {
    // Ignore edges with same source and destination as well as the edge E
    // itself.
    if (PredBB == DstBB || PredBB == SrcBB)
      continue;
    auto BI = PredBB->branch_info_begin();
    for (const BinaryBasicBlock *SuccBB : PredBB->successors()) {
      if (SuccBB == DstBB)
        break;
      ++BI;
    }
    assert(BI != PredBB->branch_info_end() && "invalid control flow graph");
    assert(BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE &&
           "attempted reordering blocks of function with no profile data");
    assert(BI->Count <= std::numeric_limits<int64_t>::max() &&
           "overflow detected");
    W -= (int64_t)BI->Count;
  }

  return W;
}

void MinBranchGreedyClusterAlgorithm::initQueue(std::vector<EdgeTy> &Queue,
                                                const BinaryFunction &BF) {
  // Initialize edge weights.
  for (const EdgeTy &E : Queue)
    Weight.emplace(std::make_pair(E, calculateWeight(E, BF)));

  // Sort edges in increasing weight order.
  adjustQueue(Queue, BF);
}

void MinBranchGreedyClusterAlgorithm::adjustQueue(std::vector<EdgeTy> &Queue,
                                                  const BinaryFunction &BF) {
  // Define a comparison function to establish SWO between edges.
  auto Comp = [&](const EdgeTy &A, const EdgeTy &B) {
    // With equal weights, prioritize branches with lower index
    // source/destination. This helps to keep original block order for blocks
    // when optimal order cannot be deduced from a profile.
    if (Weight[A] == Weight[B]) {
      const signed SrcOrder = BF.getOriginalLayoutRelativeOrder(A.Src, B.Src);
      return (SrcOrder != 0)
                 ? SrcOrder > 0
                 : BF.getOriginalLayoutRelativeOrder(A.Dst, B.Dst) > 0;
    }
    return Weight[A] < Weight[B];
  };

  // Iterate through all remaining edges to find edges that have their
  // source and destination in the same cluster.
  std::vector<EdgeTy> NewQueue;
  for (const EdgeTy &E : Queue) {
    const BinaryBasicBlock *SrcBB = E.Src;
    const BinaryBasicBlock *DstBB = E.Dst;

    // Case 1: SrcBB and DstBB are the same or DstBB is the entry block. Ignore
    // this edge.
    if (SrcBB == DstBB || DstBB == *BF.getLayout().block_begin()) {
      LLVM_DEBUG(dbgs() << "\tAdjustment: Ignored edge "; E.print(dbgs());
                 dbgs() << " (same src, dst)\n");
      continue;
    }

    int I = BBToClusterMap[SrcBB];
    int J = BBToClusterMap[DstBB];
    std::vector<BinaryBasicBlock *> &ClusterA = Clusters[I];
    std::vector<BinaryBasicBlock *> &ClusterB = Clusters[J];

    // Case 2: They are already allocated at the same cluster or incompatible
    // clusters. Adjust the weights of edges with the same source or
    // destination, so that this edge has no effect on them any more, and ignore
    // this edge. Also increase the intra- (or inter-) cluster edge count.
    if (I == J || !areClustersCompatible(ClusterA, ClusterB, E)) {
      if (!ClusterEdges.empty())
        ClusterEdges[I][J] += E.Count;
      LLVM_DEBUG(dbgs() << "\tAdjustment: Ignored edge "; E.print(dbgs());
                 dbgs() << " (src, dst belong to same cluster or incompatible "
                           "clusters)\n");
      for (const BinaryBasicBlock *SuccBB : SrcBB->successors()) {
        if (SuccBB == DstBB)
          continue;
        auto WI = Weight.find(EdgeTy(SrcBB, SuccBB, 0));
        assert(WI != Weight.end() && "CFG edge not found in Weight map");
        WI->second += (int64_t)E.Count;
      }
      for (const BinaryBasicBlock *PredBB : DstBB->predecessors()) {
        if (PredBB == SrcBB)
          continue;
        auto WI = Weight.find(EdgeTy(PredBB, DstBB, 0));
        assert(WI != Weight.end() && "CFG edge not found in Weight map");
        WI->second += (int64_t)E.Count;
      }
      continue;
    }

    // Case 3: None of the previous cases is true, so just keep this edge in
    // the queue.
    NewQueue.emplace_back(E);
  }

  // Sort remaining edges in increasing weight order.
  Queue.swap(NewQueue);
  llvm::sort(Queue, Comp);
}

bool MinBranchGreedyClusterAlgorithm::areClustersCompatible(
    const ClusterTy &Front, const ClusterTy &Back, const EdgeTy &E) const {
  return Front.back() == E.Src && Back.front() == E.Dst;
}

void MinBranchGreedyClusterAlgorithm::reset() {
  GreedyClusterAlgorithm::reset();
  Weight.clear();
}

void TSPReorderAlgorithm::reorderBasicBlocks(BinaryFunction &BF,
                                             BasicBlockOrder &Order) const {
  std::vector<std::vector<uint64_t>> Weight;
  std::vector<BinaryBasicBlock *> IndexToBB;

  const size_t N = BF.getLayout().block_size();
  assert(N <= std::numeric_limits<uint64_t>::digits &&
         "cannot use TSP solution for sizes larger than bits in uint64_t");

  // Populating weight map and index map
  for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
    BB->setLayoutIndex(IndexToBB.size());
    IndexToBB.push_back(BB);
  }
  Weight.resize(N);
  for (const BinaryBasicBlock *BB : BF.getLayout().blocks()) {
    auto BI = BB->branch_info_begin();
    Weight[BB->getLayoutIndex()].resize(N);
    for (BinaryBasicBlock *SuccBB : BB->successors()) {
      if (BI->Count != BinaryBasicBlock::COUNT_NO_PROFILE)
        Weight[BB->getLayoutIndex()][SuccBB->getLayoutIndex()] = BI->Count;
      ++BI;
    }
  }

  std::vector<std::vector<int64_t>> DP;
  DP.resize(1 << N);
  for (std::vector<int64_t> &Elmt : DP)
    Elmt.resize(N, -1);

  // Start with the entry basic block being allocated with cost zero
  DP[1][0] = 0;
  // Walk through TSP solutions using a bitmask to represent state (current set
  // of BBs in the layout)
  uint64_t BestSet = 1;
  uint64_t BestLast = 0;
  int64_t BestWeight = 0;
  for (uint64_t Set = 1; Set < (1ULL << N); ++Set) {
    // Traverse each possibility of Last BB visited in this layout
    for (uint64_t Last = 0; Last < N; ++Last) {
      // Case 1: There is no possible layout with this BB as Last
      if (DP[Set][Last] == -1)
        continue;

      // Case 2: There is a layout with this Set and this Last, and we try
      // to expand this set with New
      for (uint64_t New = 1; New < N; ++New) {
        // Case 2a: BB "New" is already in this Set
        if ((Set & (1ULL << New)) != 0)
          continue;

        // Case 2b: BB "New" is not in this set and we add it to this Set and
        // record total weight of this layout with "New" as the last BB.
        uint64_t NewSet = (Set | (1ULL << New));
        if (DP[NewSet][New] == -1)
          DP[NewSet][New] = DP[Set][Last] + (int64_t)Weight[Last][New];
        DP[NewSet][New] = std::max(DP[NewSet][New],
                                   DP[Set][Last] + (int64_t)Weight[Last][New]);

        if (DP[NewSet][New] > BestWeight) {
          BestWeight = DP[NewSet][New];
          BestSet = NewSet;
          BestLast = New;
        }
      }
    }
  }

  // Define final function layout based on layout that maximizes weight
  uint64_t Last = BestLast;
  uint64_t Set = BestSet;
  BitVector Visited;
  Visited.resize(N);
  Visited[Last] = true;
  Order.push_back(IndexToBB[Last]);
  Set = Set & ~(1ULL << Last);
  while (Set != 0) {
    int64_t Best = -1;
    uint64_t NewLast;
    for (uint64_t I = 0; I < N; ++I) {
      if (DP[Set][I] == -1)
        continue;
      int64_t AdjWeight = Weight[I][Last] > 0 ? Weight[I][Last] : 0;
      if (DP[Set][I] + AdjWeight > Best) {
        NewLast = I;
        Best = DP[Set][I] + AdjWeight;
      }
    }
    Last = NewLast;
    Visited[Last] = true;
    Order.push_back(IndexToBB[Last]);
    Set = Set & ~(1ULL << Last);
  }
  std::reverse(Order.begin(), Order.end());

  // Finalize layout with BBs that weren't assigned to the layout using the
  // input layout.
  for (BinaryBasicBlock *BB : BF.getLayout().blocks())
    if (Visited[BB->getLayoutIndex()] == false)
      Order.push_back(BB);
}

void ExtTSPReorderAlgorithm::reorderBasicBlocks(BinaryFunction &BF,
                                                BasicBlockOrder &Order) const {
  if (BF.getLayout().block_empty())
    return;

  // Do not change layout of functions w/o profile information
  if (!BF.hasValidProfile() || BF.getLayout().block_size() <= 2) {
    for (BinaryBasicBlock *BB : BF.getLayout().blocks())
      Order.push_back(BB);
    return;
  }

  // Create a separate MCCodeEmitter to allow lock-free execution
  BinaryContext::IndependentCodeEmitter Emitter;
  if (!opts::NoThreads)
    Emitter = BF.getBinaryContext().createIndependentMCCodeEmitter();

  // Initialize CFG nodes and their data
  std::vector<uint64_t> BlockSizes;
  std::vector<uint64_t> BlockCounts;
  BasicBlockOrder OrigOrder;
  BF.getLayout().updateLayoutIndices();
  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;
  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));
      ++BI;
    }
  }

  // Run the layout algorithm
  auto Result = applyExtTspLayout(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())
    return;

  // Cluster basic blocks.
  CAlgo->clusterBasicBlocks(BF);

  if (opts::PrintClusters)
    CAlgo->printClusters();

  // Arrange basic blocks according to clusters.
  for (ClusterAlgorithm::ClusterTy &Cluster : CAlgo->Clusters)
    Order.insert(Order.end(), Cluster.begin(), Cluster.end());
}

void OptimizeBranchReorderAlgorithm::reorderBasicBlocks(
    BinaryFunction &BF, BasicBlockOrder &Order) const {
  if (BF.getLayout().block_empty())
    return;

  // Cluster basic blocks.
  CAlgo->clusterBasicBlocks(BF, /* ComputeEdges = */ true);
  std::vector<ClusterAlgorithm::ClusterTy> &Clusters = CAlgo->Clusters;
  std::vector<std::unordered_map<uint32_t, uint64_t>> &ClusterEdges =
      CAlgo->ClusterEdges;

  // Compute clusters' average frequencies.
  CAlgo->computeClusterAverageFrequency(BF.getBinaryContext());
  std::vector<double> &AvgFreq = CAlgo->AvgFreq;

  if (opts::PrintClusters)
    CAlgo->printClusters();

  // Cluster layout order
  std::vector<uint32_t> ClusterOrder;

  // Do a topological sort for clusters, prioritizing frequently-executed BBs
  // during the traversal.
  std::stack<uint32_t> Stack;
  std::vector<uint32_t> Status;
  std::vector<uint32_t> Parent;
  Status.resize(Clusters.size(), 0);
  Parent.resize(Clusters.size(), 0);
  constexpr uint32_t STACKED = 1;
  constexpr uint32_t VISITED = 2;
  Status[0] = STACKED;
  Stack.push(0);
  while (!Stack.empty()) {
    uint32_t I = Stack.top();
    if (!(Status[I] & VISITED)) {
      Status[I] |= VISITED;
      // Order successors by weight
      auto ClusterComp = [&ClusterEdges, I](uint32_t A, uint32_t B) {
        return ClusterEdges[I][A] > ClusterEdges[I][B];
      };
      std::priority_queue<uint32_t, std::vector<uint32_t>,
                          decltype(ClusterComp)>
          SuccQueue(ClusterComp);
      for (std::pair<const uint32_t, uint64_t> &Target : ClusterEdges[I]) {
        if (Target.second > 0 && !(Status[Target.first] & STACKED) &&
            !Clusters[Target.first].empty()) {
          Parent[Target.first] = I;
          Status[Target.first] = STACKED;
          SuccQueue.push(Target.first);
        }
      }
      while (!SuccQueue.empty()) {
        Stack.push(SuccQueue.top());
        SuccQueue.pop();
      }
      continue;
    }
    // Already visited this node
    Stack.pop();
    ClusterOrder.push_back(I);
  }
  std::reverse(ClusterOrder.begin(), ClusterOrder.end());
  // Put unreachable clusters at the end
  for (uint32_t I = 0, E = Clusters.size(); I < E; ++I)
    if (!(Status[I] & VISITED) && !Clusters[I].empty())
      ClusterOrder.push_back(I);

  // Sort nodes with equal precedence
  auto Beg = ClusterOrder.begin();
  // Don't reorder the first cluster, which contains the function entry point
  ++Beg;
  std::stable_sort(Beg, ClusterOrder.end(),
                   [&AvgFreq, &Parent](uint32_t A, uint32_t B) {
                     uint32_t P = Parent[A];
                     while (Parent[P] != 0) {
                       if (Parent[P] == B)
                         return false;
                       P = Parent[P];
                     }
                     P = Parent[B];
                     while (Parent[P] != 0) {
                       if (Parent[P] == A)
                         return true;
                       P = Parent[P];
                     }
                     return AvgFreq[A] > AvgFreq[B];
                   });

  if (opts::PrintClusters) {
    errs() << "New cluster order: ";
    const char *Sep = "";
    for (uint32_t O : ClusterOrder) {
      errs() << Sep << O;
      Sep = ", ";
    }
    errs() << '\n';
  }

  // Arrange basic blocks according to cluster order.
  for (uint32_t ClusterIndex : ClusterOrder) {
    ClusterAlgorithm::ClusterTy &Cluster = Clusters[ClusterIndex];
    Order.insert(Order.end(), Cluster.begin(), Cluster.end());
  }
}

void OptimizeCacheReorderAlgorithm::reorderBasicBlocks(
    BinaryFunction &BF, BasicBlockOrder &Order) const {
  if (BF.getLayout().block_empty())
    return;

  const uint64_t ColdThreshold =
      opts::ColdThreshold *
      (*BF.getLayout().block_begin())->getExecutionCount() / 1000;

  // Cluster basic blocks.
  CAlgo->clusterBasicBlocks(BF);
  std::vector<ClusterAlgorithm::ClusterTy> &Clusters = CAlgo->Clusters;

  // Compute clusters' average frequencies.
  CAlgo->computeClusterAverageFrequency(BF.getBinaryContext());
  std::vector<double> &AvgFreq = CAlgo->AvgFreq;

  if (opts::PrintClusters)
    CAlgo->printClusters();

  // Cluster layout order
  std::vector<uint32_t> ClusterOrder;

  // Order clusters based on average instruction execution frequency
  for (uint32_t I = 0, E = Clusters.size(); I < E; ++I)
    if (!Clusters[I].empty())
      ClusterOrder.push_back(I);
  // Don't reorder the first cluster, which contains the function entry point
  std::stable_sort(
      std::next(ClusterOrder.begin()), ClusterOrder.end(),
      [&AvgFreq](uint32_t A, uint32_t B) { return AvgFreq[A] > AvgFreq[B]; });

  if (opts::PrintClusters) {
    errs() << "New cluster order: ";
    const char *Sep = "";
    for (uint32_t O : ClusterOrder) {
      errs() << Sep << O;
      Sep = ", ";
    }
    errs() << '\n';
  }

  // Arrange basic blocks according to cluster order.
  for (uint32_t ClusterIndex : ClusterOrder) {
    ClusterAlgorithm::ClusterTy &Cluster = Clusters[ClusterIndex];
    Order.insert(Order.end(), Cluster.begin(), Cluster.end());
    // Force zero execution count on clusters that do not meet the cut off
    // specified by --cold-threshold.
    if (AvgFreq[ClusterIndex] < static_cast<double>(ColdThreshold))
      for (BinaryBasicBlock *BBPtr : Cluster)
        BBPtr->setExecutionCount(0);
  }
}

void ReverseReorderAlgorithm::reorderBasicBlocks(BinaryFunction &BF,
                                                 BasicBlockOrder &Order) const {
  if (BF.getLayout().block_empty())
    return;

  BinaryBasicBlock *FirstBB = *BF.getLayout().block_begin();
  Order.push_back(FirstBB);
  for (auto RLI = BF.getLayout().block_rbegin(); *RLI != FirstBB; ++RLI)
    Order.push_back(*RLI);
}

void RandomClusterReorderAlgorithm::reorderBasicBlocks(
    BinaryFunction &BF, BasicBlockOrder &Order) const {
  if (BF.getLayout().block_empty())
    return;

  // Cluster basic blocks.
  CAlgo->clusterBasicBlocks(BF);
  std::vector<ClusterAlgorithm::ClusterTy> &Clusters = CAlgo->Clusters;

  if (opts::PrintClusters)
    CAlgo->printClusters();

  // Cluster layout order
  std::vector<uint32_t> ClusterOrder;

  // Order clusters based on average instruction execution frequency
  for (uint32_t I = 0, E = Clusters.size(); I < E; ++I)
    if (!Clusters[I].empty())
      ClusterOrder.push_back(I);

  std::shuffle(std::next(ClusterOrder.begin()), ClusterOrder.end(),
               std::default_random_engine(opts::RandomSeed.getValue()));

  if (opts::PrintClusters) {
    errs() << "New cluster order: ";
    const char *Sep = "";
    for (uint32_t O : ClusterOrder) {
      errs() << Sep << O;
      Sep = ", ";
    }
    errs() << '\n';
  }

  // Arrange basic blocks according to cluster order.
  for (uint32_t ClusterIndex : ClusterOrder) {
    ClusterAlgorithm::ClusterTy &Cluster = Clusters[ClusterIndex];
    Order.insert(Order.end(), Cluster.begin(), Cluster.end());
  }
}