llvm/bolt/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 …

usingnamespacellvm;
usingnamespacebolt;

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) { … }

template <typename A, typename B> struct HashPair { … };

} // namespace

void ClusterAlgorithm::computeClusterAverageFrequency(const BinaryContext &BC) { … }

void ClusterAlgorithm::printClusters() const { … }

void ClusterAlgorithm::reset() { … }

void GreedyClusterAlgorithm::EdgeTy::print(raw_ostream &OS) const { … }

size_t GreedyClusterAlgorithm::EdgeHash::operator()(const EdgeTy &E) const { … }

bool GreedyClusterAlgorithm::EdgeEqual::operator()(const EdgeTy &A,
                                                   const EdgeTy &B) const { … }

void GreedyClusterAlgorithm::clusterBasicBlocks(BinaryFunction &BF,
                                                bool ComputeEdges) { … }

void GreedyClusterAlgorithm::reset() { … }

void PHGreedyClusterAlgorithm::initQueue(std::vector<EdgeTy> &Queue,
                                         const BinaryFunction &BF) { … }

void PHGreedyClusterAlgorithm::adjustQueue(std::vector<EdgeTy> &Queue,
                                           const BinaryFunction &BF) { … }

bool PHGreedyClusterAlgorithm::areClustersCompatible(const ClusterTy &Front,
                                                     const ClusterTy &Back,
                                                     const EdgeTy &E) const { … }

int64_t MinBranchGreedyClusterAlgorithm::calculateWeight(
    const EdgeTy &E, const BinaryFunction &BF) const { … }

void MinBranchGreedyClusterAlgorithm::initQueue(std::vector<EdgeTy> &Queue,
                                                const BinaryFunction &BF) { … }

void MinBranchGreedyClusterAlgorithm::adjustQueue(std::vector<EdgeTy> &Queue,
                                                  const BinaryFunction &BF) { … }

bool MinBranchGreedyClusterAlgorithm::areClustersCompatible(
    const ClusterTy &Front, const ClusterTy &Back, const EdgeTy &E) const { … }

void MinBranchGreedyClusterAlgorithm::reset() { … }

void TSPReorderAlgorithm::reorderBasicBlocks(BinaryFunction &BF,
                                             BasicBlockOrder &Order) const { … }

void ExtTSPReorderAlgorithm::reorderBasicBlocks(BinaryFunction &BF,
                                                BasicBlockOrder &Order) const { … }

void OptimizeReorderAlgorithm::reorderBasicBlocks(
    BinaryFunction &BF, BasicBlockOrder &Order) const { … }

void OptimizeBranchReorderAlgorithm::reorderBasicBlocks(
    BinaryFunction &BF, BasicBlockOrder &Order) const { … }

void OptimizeCacheReorderAlgorithm::reorderBasicBlocks(
    BinaryFunction &BF, BasicBlockOrder &Order) const { … }

void ReverseReorderAlgorithm::reorderBasicBlocks(BinaryFunction &BF,
                                                 BasicBlockOrder &Order) const { … }

void RandomClusterReorderAlgorithm::reorderBasicBlocks(
    BinaryFunction &BF, BasicBlockOrder &Order) const { … }