HotColdSplitting.cpp | Explore in Territory

//===- HotColdSplitting.cpp -- Outline Cold Regions -------------*- 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
/// The goal of hot/cold splitting is to improve the memory locality of code.
/// The splitting pass does this by identifying cold blocks and moving them into
/// separate functions.
///
/// When the splitting pass finds a cold block (referred to as "the sink"), it
/// grows a maximal cold region around that block. The maximal region contains
/// all blocks (post-)dominated by the sink [*]. In theory, these blocks are as
/// cold as the sink. Once a region is found, it's split out of the original
/// function provided it's profitable to do so.
///
/// [*] In practice, there is some added complexity because some blocks are not
/// safe to extract.
///
/// TODO: Use the PM to get domtrees, and preserve BFI/BPI.
/// TODO: Reorder outlined functions.
///
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/IPO/HotColdSplitting.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/BlockFrequencyInfo.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/ProfileSummaryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/EHPersonalities.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/ProfDataUtils.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/IPO.h"
#include "llvm/Transforms/Utils/CodeExtractor.h"
#include <algorithm>
#include <cassert>
#include <limits>
#include <string>

#define DEBUG_TYPE …

STATISTIC(NumColdRegionsFound, "Number of cold regions found.");
STATISTIC(NumColdRegionsOutlined, "Number of cold regions outlined.");

usingnamespacellvm;

static cl::opt<bool> EnableStaticAnalysis("hot-cold-static-analysis",
                                          cl::init(true), cl::Hidden);

static cl::opt<int>
    SplittingThreshold("hotcoldsplit-threshold", cl::init(2), cl::Hidden,
                       cl::desc("Base penalty for splitting cold code (as a "
                                "multiple of TCC_Basic)"));

static cl::opt<bool> EnableColdSection(
    "enable-cold-section", cl::init(false), cl::Hidden,
    cl::desc("Enable placement of extracted cold functions"
             " into a separate section after hot-cold splitting."));

static cl::opt<std::string>
    ColdSectionName("hotcoldsplit-cold-section-name", cl::init("__llvm_cold"),
                    cl::Hidden,
                    cl::desc("Name for the section containing cold functions "
                             "extracted by hot-cold splitting."));

static cl::opt<int> MaxParametersForSplit(
    "hotcoldsplit-max-params", cl::init(4), cl::Hidden,
    cl::desc("Maximum number of parameters for a split function"));

static cl::opt<int> ColdBranchProbDenom(
    "hotcoldsplit-cold-probability-denom", cl::init(100), cl::Hidden,
    cl::desc("Divisor of cold branch probability."
             "BranchProbability = 1/ColdBranchProbDenom"));

namespace {
// Same as blockEndsInUnreachable in CodeGen/BranchFolding.cpp. Do not modify
// this function unless you modify the MBB version as well.
//
/// A no successor, non-return block probably ends in unreachable and is cold.
/// Also consider a block that ends in an indirect branch to be a return block,
/// since many targets use plain indirect branches to return.
bool blockEndsInUnreachable(const BasicBlock &BB) { … }

void analyzeProfMetadata(BasicBlock *BB,
                         BranchProbability ColdProbThresh,
                         SmallPtrSetImpl<BasicBlock *> &AnnotatedColdBlocks) { … }

bool unlikelyExecuted(BasicBlock &BB) { … }

/// Check whether it's safe to outline \p BB.
static bool mayExtractBlock(const BasicBlock &BB) { … }

/// Mark \p F cold. Based on this assumption, also optimize it for minimum size.
/// If \p UpdateEntryCount is true (set when this is a new split function and
/// module has profile data), set entry count to 0 to ensure treated as cold.
/// Return true if the function is changed.
static bool markFunctionCold(Function &F, bool UpdateEntryCount = false) { … }

} // end anonymous namespace

/// Check whether \p F is inherently cold.
bool HotColdSplitting::isFunctionCold(const Function &F) const { … }

bool HotColdSplitting::isBasicBlockCold(
    BasicBlock *BB, BranchProbability ColdProbThresh,
    SmallPtrSetImpl<BasicBlock *> &AnnotatedColdBlocks,
    BlockFrequencyInfo *BFI) const { … }

// Returns false if the function should not be considered for hot-cold split
// optimization.
bool HotColdSplitting::shouldOutlineFrom(const Function &F) const { … }

/// Get the benefit score of outlining \p Region.
static InstructionCost getOutliningBenefit(ArrayRef<BasicBlock *> Region,
                                           TargetTransformInfo &TTI) { … }

/// Get the penalty score for outlining \p Region.
static int getOutliningPenalty(ArrayRef<BasicBlock *> Region,
                               unsigned NumInputs, unsigned NumOutputs) { … }

// Determine if it is beneficial to split the \p Region.
bool HotColdSplitting::isSplittingBeneficial(CodeExtractor &CE,
                                             const BlockSequence &Region,
                                             TargetTransformInfo &TTI) { … }

// Split the single \p EntryPoint cold region. \p CE is the region code
// extractor.
Function *HotColdSplitting::extractColdRegion(
    BasicBlock &EntryPoint, CodeExtractor &CE,
    const CodeExtractorAnalysisCache &CEAC, BlockFrequencyInfo *BFI,
    TargetTransformInfo &TTI, OptimizationRemarkEmitter &ORE) { … }

/// A pair of (basic block, score).
BlockTy;

namespace {
/// A maximal outlining region. This contains all blocks post-dominated by a
/// sink block, the sink block itself, and all blocks dominated by the sink.
/// If sink-predecessors and sink-successors cannot be extracted in one region,
/// the static constructor returns a list of suitable extraction regions.
class OutliningRegion { … };
} // namespace

bool HotColdSplitting::outlineColdRegions(Function &F, bool HasProfileSummary) { … }

bool HotColdSplitting::run(Module &M) { … }

PreservedAnalyses
HotColdSplittingPass::run(Module &M, ModuleAnalysisManager &AM) { … }
llvm/llvm/lib/Transforms/IPO/HotColdSplitting.cpp
