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
#defineDEBUG_TYPE"bolt"

usingnamespacellvm;
usingnamespacebolt;

namespaceopts {

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 <classT> inlinevoidhashCombine(size_t &Seed, const T &Val) {
 std::hash<T> Hasher;
 Seed ^= Hasher(Val) + 0x9e3779b9 + (Seed << 6) + (Seed >> 2);
}

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

} // namespace

voidClusterAlgorithm::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;
 }
}

voidClusterAlgorithm::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() << " : ";
constchar *Sep = "";
for (const BinaryBasicBlock *BB : Clusters[I]) {
errs() << Sep << BB->getName();
 Sep = ", ";
 }
errs() << "\n";
 }
}

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

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

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

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

voidGreedyClusterAlgorithm::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");
 }
 }
}

voidGreedyClusterAlgorithm::reset() {
ClusterAlgorithm::reset();
 BBToClusterMap.clear();
}

voidPHGreedyClusterAlgorithm::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) {
constsigned 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);
}

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

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

int64_tMinBranchGreedyClusterAlgorithm::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;
}

voidMinBranchGreedyClusterAlgorithm::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);
}

voidMinBranchGreedyClusterAlgorithm::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]) {
constsigned 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);
}

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

voidMinBranchGreedyClusterAlgorithm::reset() {
GreedyClusterAlgorithm::reset();
 Weight.clear();
}

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

constsize_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(static_cast<size_t>(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);
}

voidExtTSPReorderAlgorithm::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_tSize = 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
 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");
 JumpCounts.push_back(
 {BB->getLayoutIndex(), SuccBB->getLayoutIndex(), BI->Count});
 ++BI;
 }
 }

// Run the layout algorithm
auto Result =
codelayout::computeExtTspLayout(BlockSizes, BlockCounts, JumpCounts);
 Order.reserve(BF.getLayout().block_size());
for (uint64_t R : Result)
 Order.push_back(OrigOrder[R]);
}

voidOptimizeReorderAlgorithm::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());
}

voidOptimizeBranchReorderAlgorithm::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);
constexpruint32_t STACKED = 1;
constexpruint32_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<constuint32_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)
returnfalse;
 P = Parent[P];
 }
 P = Parent[B];
while (Parent[P] != 0) {
if (Parent[P] == A)
returntrue;
 P = Parent[P];
 }
return AvgFreq[A] > AvgFreq[B];
 });

if (opts::PrintClusters) {
errs() << "New cluster order: ";
constchar *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());
 }
}

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

constuint64_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: ";
constchar *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);
 }
}

voidReverseReorderAlgorithm::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);
}

voidRandomClusterReorderAlgorithm::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: ";
constchar *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());
 }
}