llvm/bolt/lib/Passes/HFSort.cpp

//===- bolt/Passes/HFSort.cpp - Cluster functions by hotness --------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// Implementation of HFSort algorithm for function ordering:
// https://research.fb.com/wp-content/uploads/2017/01/cgo2017-hfsort-final1.pdf
//
//===----------------------------------------------------------------------===//

#include "bolt/Passes/HFSort.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/raw_ostream.h"
#include <unordered_set>

#define DEBUG_TYPE …

namespace opts {
extern llvm::cl::opt<unsigned> Verbosity;
}

namespace llvm {
namespace bolt {

NodeId;
Arc;
Node;

namespace {

// The number of pages to reserve for the functions with highest
// density (samples / size).  The functions put in these pages are not
// considered for clustering.
constexpr uint32_t FrozenPages = …;

// The minimum approximate probability of a callee being called from a
// particular arc to consider merging with the caller's cluster.
constexpr double MinArcProbability = …;

// This is a factor to determine by how much a caller cluster is
// willing to degrade it's density by merging a callee.
constexpr int CallerDegradeFactor = …;

} // namespace

////////////////////////////////////////////////////////////////////////////////

Cluster::Cluster(NodeId Id, const Node &Func)
    : … { … }

Cluster::Cluster(const std::vector<NodeId> &Nodes, const CallGraph &Cg) { … }

std::string Cluster::toString() const { … }

namespace {

void freezeClusters(const CallGraph &Cg, std::vector<Cluster> &Clusters) { … }

} // namespace

void Cluster::reverseTargets() { … }

void Cluster::merge(const Cluster &Other, const double Aw) { … }

void Cluster::merge(const Cluster &Other,
                    const std::vector<CallGraph::NodeId> &Targets_) { … }

void Cluster::clear() { … }

std::vector<Cluster> clusterize(const CallGraph &Cg) { … }

std::vector<Cluster> randomClusters(const CallGraph &Cg) { … }

} // namespace bolt
} // namespace llvm