llvm/lld/MachO/SectionPriorities.cpp

//===- SectionPriorities.cpp ----------------------------------------------===//
//
// 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 is based on the ELF port, see ELF/CallGraphSort.cpp for the details
/// about the algorithm.
///
//===----------------------------------------------------------------------===//

#include "SectionPriorities.h"
#include "BPSectionOrderer.h"
#include "Config.h"
#include "InputFiles.h"
#include "Symbols.h"
#include "Target.h"

#include "lld/Common/Args.h"
#include "lld/Common/CommonLinkerContext.h"
#include "lld/Common/ErrorHandler.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/Support/Path.h"
#include "llvm/Support/TimeProfiler.h"
#include "llvm/Support/raw_ostream.h"

#include <numeric>

usingnamespacellvm;
usingnamespacellvm::MachO;
usingnamespacellvm::sys;
usingnamespacelld;
usingnamespacelld::macho;

PriorityBuilder macho::priorityBuilder;

namespace {

size_t highestAvailablePriority = …;

struct Edge { … };

struct Cluster { … };

class CallGraphSort { … };
// Maximum amount the combined cluster density can be worse than the original
// cluster to consider merging.
constexpr int MAX_DENSITY_DEGRADATION = …;
} // end anonymous namespace

// Take the edge list in callGraphProfile, resolve symbol names to Symbols, and
// generate a graph between InputSections with the provided weights.
CallGraphSort::CallGraphSort(const MapVector<SectionPair, uint64_t> &profile) { … }

// It's bad to merge clusters which would degrade the density too much.
static bool isNewDensityBad(Cluster &a, Cluster &b) { … }

// Find the leader of V's belonged cluster (represented as an equivalence
// class). We apply union-find path-halving technique (simple to implement) in
// the meantime as it decreases depths and the time complexity.
static int getLeader(std::vector<int> &leaders, int v) { … }

static void mergeClusters(std::vector<Cluster> &cs, Cluster &into, int intoIdx,
                          Cluster &from, int fromIdx) { … }

// Group InputSections into clusters using the Call-Chain Clustering heuristic
// then sort the clusters by density.
DenseMap<const InputSection *, size_t> CallGraphSort::run() { … }

std::optional<size_t>
macho::PriorityBuilder::getSymbolPriority(const Defined *sym) { … }

void macho::PriorityBuilder::extractCallGraphProfile() { … }

void macho::PriorityBuilder::parseOrderFile(StringRef path) { … }

DenseMap<const InputSection *, size_t>
macho::PriorityBuilder::buildInputSectionPriorities() { … }