MachineOutliner.cpp | Explore in Territory

//===---- MachineOutliner.cpp - Outline instructions -----------*- C++ -*-===//
//
// 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
//
//===----------------------------------------------------------------------===//
///
/// \file
/// Replaces repeated sequences of instructions with function calls.
///
/// This works by placing every instruction from every basic block in a
/// suffix tree, and repeatedly querying that tree for repeated sequences of
/// instructions. If a sequence of instructions appears often, then it ought
/// to be beneficial to pull out into a function.
///
/// The MachineOutliner communicates with a given target using hooks defined in
/// TargetInstrInfo.h. The target supplies the outliner with information on how
/// a specific sequence of instructions should be outlined. This information
/// is used to deduce the number of instructions necessary to
///
/// * Create an outlined function
/// * Call that outlined function
///
/// Targets must implement
///   * getOutliningCandidateInfo
///   * buildOutlinedFrame
///   * insertOutlinedCall
///   * isFunctionSafeToOutlineFrom
///
/// in order to make use of the MachineOutliner.
///
/// This was originally presented at the 2016 LLVM Developers' Meeting in the
/// talk "Reducing Code Size Using Outlining". For a high-level overview of
/// how this pass works, the talk is available on YouTube at
///
/// https://www.youtube.com/watch?v=yorld-WSOeU
///
/// The slides for the talk are available at
///
/// http://www.llvm.org/devmtg/2016-11/Slides/Paquette-Outliner.pdf
///
/// The talk provides an overview of how the outliner finds candidates and
/// ultimately outlines them. It describes how the main data structure for this
/// pass, the suffix tree, is queried and purged for candidates. It also gives
/// a simplified suffix tree construction algorithm for suffix trees based off
/// of the algorithm actually used here, Ukkonen's algorithm.
///
/// For the original RFC for this pass, please see
///
/// http://lists.llvm.org/pipermail/llvm-dev/2016-August/104170.html
///
/// For more information on the suffix tree data structure, please see
/// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
///
//===----------------------------------------------------------------------===//
#include "llvm/CodeGen/MachineOutliner.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/Twine.h"
#include "llvm/Analysis/ModuleSummaryAnalysis.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/CGData/CodeGenDataReader.h"
#include "llvm/CodeGen/LivePhysRegs.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/DIBuilder.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Mangler.h"
#include "llvm/IR/Module.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/SuffixTree.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/ModuleUtils.h"
#include <functional>
#include <tuple>
#include <vector>

#define DEBUG_TYPE …

usingnamespacellvm;
usingnamespaceore;
usingnamespaceoutliner;

// Statistics for outlined functions.
STATISTIC(NumOutlined, "Number of candidates outlined");
STATISTIC(FunctionsCreated, "Number of functions created");

// Statistics for instruction mapping.
STATISTIC(NumLegalInUnsignedVec, "Outlinable instructions mapped");
STATISTIC(NumIllegalInUnsignedVec,
          "Unoutlinable instructions mapped + number of sentinel values");
STATISTIC(NumSentinels, "Sentinel values inserted during mapping");
STATISTIC(NumInvisible,
          "Invisible instructions skipped during mapping");
STATISTIC(UnsignedVecSize,
          "Total number of instructions mapped and saved to mapping vector");
STATISTIC(StableHashAttempts,
          "Count of hashing attempts made for outlined functions");
STATISTIC(StableHashDropped,
          "Count of unsuccessful hashing attempts for outlined functions");

// Set to true if the user wants the outliner to run on linkonceodr linkage
// functions. This is false by default because the linker can dedupe linkonceodr
// functions. Since the outliner is confined to a single module (modulo LTO),
// this is off by default. It should, however, be the default behaviour in
// LTO.
static cl::opt<bool> EnableLinkOnceODROutlining(
    "enable-linkonceodr-outlining", cl::Hidden,
    cl::desc("Enable the machine outliner on linkonceodr functions"),
    cl::init(false));

/// Number of times to re-run the outliner. This is not the total number of runs
/// as the outliner will run at least one time. The default value is set to 0,
/// meaning the outliner will run one time and rerun zero times after that.
static cl::opt<unsigned> OutlinerReruns(
    "machine-outliner-reruns", cl::init(0), cl::Hidden,
    cl::desc(
        "Number of times to rerun the outliner after the initial outline"));

static cl::opt<unsigned> OutlinerBenefitThreshold(
    "outliner-benefit-threshold", cl::init(1), cl::Hidden,
    cl::desc(
        "The minimum size in bytes before an outlining candidate is accepted"));

static cl::opt<bool> OutlinerLeafDescendants(
    "outliner-leaf-descendants", cl::init(true), cl::Hidden,
    cl::desc("Consider all leaf descendants of internal nodes of the suffix "
             "tree as candidates for outlining (if false, only leaf children "
             "are considered)"));

static cl::opt<bool>
    DisableGlobalOutlining("disable-global-outlining", cl::Hidden,
                           cl::desc("Disable global outlining only by ignoring "
                                    "the codegen data generation or use"),
                           cl::init(false));

static cl::opt<bool> AppendContentHashToOutlinedName(
    "append-content-hash-outlined-name", cl::Hidden,
    cl::desc("This appends the content hash to the globally outlined function "
             "name. It's beneficial for enhancing the precision of the stable "
             "hash and for ordering the outlined functions."),
    cl::init(true));

namespace {

/// Maps \p MachineInstrs to unsigned integers and stores the mappings.
struct InstructionMapper { … };

/// An interprocedural pass which finds repeated sequences of
/// instructions and replaces them with calls to functions.
///
/// Each instruction is mapped to an unsigned integer and placed in a string.
/// The resulting mapping is then placed in a \p SuffixTree. The \p SuffixTree
/// is then repeatedly queried for repeated sequences of instructions. Each
/// non-overlapping repeated sequence is then placed in its own
/// \p MachineFunction and each instance is then replaced with a call to that
/// function.
struct MachineOutliner : public ModulePass { … };
} // Anonymous namespace.

char MachineOutliner::ID = …;

namespace llvm {
ModulePass *createMachineOutlinerPass(bool RunOnAllFunctions) { … }

} // namespace llvm

INITIALIZE_PASS(…)

void MachineOutliner::emitNotOutliningCheaperRemark(
    unsigned StringLen, std::vector<Candidate> &CandidatesForRepeatedSeq,
    OutlinedFunction &OF) { … }

void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction &OF) { … }

struct MatchedEntry { … };

// Find all matches in the global outlined hash tree.
// It's quadratic complexity in theory, but it's nearly linear in practice
// since the length of outlined sequences are small within a block.
static SmallVector<MatchedEntry> getMatchedEntries(InstructionMapper &Mapper) { … }

void MachineOutliner::findGlobalCandidates(
    InstructionMapper &Mapper,
    std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList) { … }

void MachineOutliner::findCandidates(
    InstructionMapper &Mapper,
    std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList) { … }

void MachineOutliner::computeAndPublishHashSequence(MachineFunction &MF,
                                                    unsigned CandSize) { … }

MachineFunction *MachineOutliner::createOutlinedFunction(
    Module &M, OutlinedFunction &OF, InstructionMapper &Mapper, unsigned Name) { … }

bool MachineOutliner::outline(
    Module &M, std::vector<std::unique_ptr<OutlinedFunction>> &FunctionList,
    InstructionMapper &Mapper, unsigned &OutlinedFunctionNum) { … }

void MachineOutliner::populateMapper(InstructionMapper &Mapper, Module &M) { … }

void MachineOutliner::initSizeRemarkInfo(
    const Module &M, StringMap<unsigned> &FunctionToInstrCount) { … }

void MachineOutliner::emitInstrCountChangedRemark(
    const Module &M, const StringMap<unsigned> &FunctionToInstrCount) { … }

void MachineOutliner::initializeOutlinerMode(const Module &M) { … }

void MachineOutliner::emitOutlinedHashTree(Module &M) { … }

bool MachineOutliner::runOnModule(Module &M) { … }

bool MachineOutliner::doOutline(Module &M, unsigned &OutlinedFunctionNum) { … }
llvm/llvm/lib/CodeGen/MachineOutliner.cpp
