FunctionSpecialization.cpp | Explore in Territory

//===- FunctionSpecialization.cpp - Function Specialization ---------------===//
//
// 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
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/IPO/FunctionSpecialization.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/CodeMetrics.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InlineCost.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueLattice.h"
#include "llvm/Analysis/ValueLatticeUtils.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/Transforms/Scalar/SCCP.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/SCCPSolver.h"
#include "llvm/Transforms/Utils/SizeOpts.h"
#include <cmath>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumSpecsCreated, "Number of specializations created");

static cl::opt<bool> ForceSpecialization(
    "force-specialization", cl::init(false), cl::Hidden, cl::desc(
    "Force function specialization for every call site with a constant "
    "argument"));

static cl::opt<unsigned> MaxClones(
    "funcspec-max-clones", cl::init(3), cl::Hidden, cl::desc(
    "The maximum number of clones allowed for a single function "
    "specialization"));

static cl::opt<unsigned>
    MaxDiscoveryIterations("funcspec-max-discovery-iterations", cl::init(100),
                           cl::Hidden,
                           cl::desc("The maximum number of iterations allowed "
                                    "when searching for transitive "
                                    "phis"));

static cl::opt<unsigned> MaxIncomingPhiValues(
    "funcspec-max-incoming-phi-values", cl::init(8), cl::Hidden,
    cl::desc("The maximum number of incoming values a PHI node can have to be "
             "considered during the specialization bonus estimation"));

static cl::opt<unsigned> MaxBlockPredecessors(
    "funcspec-max-block-predecessors", cl::init(2), cl::Hidden, cl::desc(
    "The maximum number of predecessors a basic block can have to be "
    "considered during the estimation of dead code"));

static cl::opt<unsigned> MinFunctionSize(
    "funcspec-min-function-size", cl::init(300), cl::Hidden, cl::desc(
    "Don't specialize functions that have less than this number of "
    "instructions"));

static cl::opt<unsigned> MaxCodeSizeGrowth(
    "funcspec-max-codesize-growth", cl::init(3), cl::Hidden, cl::desc(
    "Maximum codesize growth allowed per function"));

static cl::opt<unsigned> MinCodeSizeSavings(
    "funcspec-min-codesize-savings", cl::init(20), cl::Hidden, cl::desc(
    "Reject specializations whose codesize savings are less than this"
    "much percent of the original function size"));

static cl::opt<unsigned> MinLatencySavings(
    "funcspec-min-latency-savings", cl::init(40), cl::Hidden,
    cl::desc("Reject specializations whose latency savings are less than this"
             "much percent of the original function size"));

static cl::opt<unsigned> MinInliningBonus(
    "funcspec-min-inlining-bonus", cl::init(300), cl::Hidden, cl::desc(
    "Reject specializations whose inlining bonus is less than this"
    "much percent of the original function size"));

static cl::opt<bool> SpecializeOnAddress(
    "funcspec-on-address", cl::init(false), cl::Hidden, cl::desc(
    "Enable function specialization on the address of global values"));

// Disabled by default as it can significantly increase compilation times.
//
// https://llvm-compile-time-tracker.com
// https://github.com/nikic/llvm-compile-time-tracker
static cl::opt<bool> SpecializeLiteralConstant(
    "funcspec-for-literal-constant", cl::init(false), cl::Hidden, cl::desc(
    "Enable specialization of functions that take a literal constant as an "
    "argument"));

bool InstCostVisitor::canEliminateSuccessor(BasicBlock *BB, BasicBlock *Succ,
                                         DenseSet<BasicBlock *> &DeadBlocks) { … }

// Estimates the codesize savings due to dead code after constant propagation.
// \p WorkList represents the basic blocks of a specialization which will
// eventually become dead once we replace instructions that are known to be
// constants. The successors of such blocks are added to the list as long as
// the \p Solver found they were executable prior to specialization, and only
// if all their predecessors are dead.
Cost InstCostVisitor::estimateBasicBlocks(
                          SmallVectorImpl<BasicBlock *> &WorkList) { … }

static Constant *findConstantFor(Value *V, ConstMap &KnownConstants) { … }

Bonus InstCostVisitor::getBonusFromPendingPHIs() { … }

/// Compute a bonus for replacing argument \p A with constant \p C.
Bonus InstCostVisitor::getSpecializationBonus(Argument *A, Constant *C) { … }

Bonus InstCostVisitor::getUserBonus(Instruction *User, Value *Use, Constant *C) { … }

Cost InstCostVisitor::estimateSwitchInst(SwitchInst &I) { … }

Cost InstCostVisitor::estimateBranchInst(BranchInst &I) { … }

bool InstCostVisitor::discoverTransitivelyIncomingValues(
    Constant *Const, PHINode *Root, DenseSet<PHINode *> &TransitivePHIs) { … }

Constant *InstCostVisitor::visitPHINode(PHINode &I) { … }

Constant *InstCostVisitor::visitFreezeInst(FreezeInst &I) { … }

Constant *InstCostVisitor::visitCallBase(CallBase &I) { … }

Constant *InstCostVisitor::visitLoadInst(LoadInst &I) { … }

Constant *InstCostVisitor::visitGetElementPtrInst(GetElementPtrInst &I) { … }

Constant *InstCostVisitor::visitSelectInst(SelectInst &I) { … }

Constant *InstCostVisitor::visitCastInst(CastInst &I) { … }

Constant *InstCostVisitor::visitCmpInst(CmpInst &I) { … }

Constant *InstCostVisitor::visitUnaryOperator(UnaryOperator &I) { … }

Constant *InstCostVisitor::visitBinaryOperator(BinaryOperator &I) { … }

Constant *FunctionSpecializer::getPromotableAlloca(AllocaInst *Alloca,
                                                   CallInst *Call) { … }

// A constant stack value is an AllocaInst that has a single constant
// value stored to it. Return this constant if such an alloca stack value
// is a function argument.
Constant *FunctionSpecializer::getConstantStackValue(CallInst *Call,
                                                     Value *Val) { … }

// To support specializing recursive functions, it is important to propagate
// constant arguments because after a first iteration of specialisation, a
// reduced example may look like this:
//
//     define internal void @RecursiveFn(i32* arg1) {
//       %temp = alloca i32, align 4
//       store i32 2 i32* %temp, align 4
//       call void @RecursiveFn.1(i32* nonnull %temp)
//       ret void
//     }
//
// Before a next iteration, we need to propagate the constant like so
// which allows further specialization in next iterations.
//
//     @funcspec.arg = internal constant i32 2
//
//     define internal void @someFunc(i32* arg1) {
//       call void @otherFunc(i32* nonnull @funcspec.arg)
//       ret void
//     }
//
// See if there are any new constant values for the callers of \p F via
// stack variables and promote them to global variables.
void FunctionSpecializer::promoteConstantStackValues(Function *F) { … }

// ssa_copy intrinsics are introduced by the SCCP solver. These intrinsics
// interfere with the promoteConstantStackValues() optimization.
static void removeSSACopy(Function &F) { … }

/// Remove any ssa_copy intrinsics that may have been introduced.
void FunctionSpecializer::cleanUpSSA() { … }


template <> struct llvm::DenseMapInfo<SpecSig> { … };

FunctionSpecializer::~FunctionSpecializer() { … }

/// Attempt to specialize functions in the module to enable constant
/// propagation across function boundaries.
///
/// \returns true if at least one function is specialized.
bool FunctionSpecializer::run() { … }

void FunctionSpecializer::removeDeadFunctions() { … }

/// Clone the function \p F and remove the ssa_copy intrinsics added by
/// the SCCPSolver in the cloned version.
static Function *cloneCandidateFunction(Function *F, unsigned NSpecs) { … }

bool FunctionSpecializer::findSpecializations(Function *F, unsigned FuncSize,
                                              SmallVectorImpl<Spec> &AllSpecs,
                                              SpecMap &SM) { … }

bool FunctionSpecializer::isCandidateFunction(Function *F) { … }

Function *FunctionSpecializer::createSpecialization(Function *F,
                                                    const SpecSig &S) { … }

/// Compute the inlining bonus for replacing argument \p A with constant \p C.
/// The below heuristic is only concerned with exposing inlining
/// opportunities via indirect call promotion. If the argument is not a
/// (potentially casted) function pointer, give up.
unsigned FunctionSpecializer::getInliningBonus(Argument *A, Constant *C) { … }

/// Determine if it is possible to specialise the function for constant values
/// of the formal parameter \p A.
bool FunctionSpecializer::isArgumentInteresting(Argument *A) { … }

/// Check if the value \p V  (an actual argument) is a constant or can only
/// have a constant value. Return that constant.
Constant *FunctionSpecializer::getCandidateConstant(Value *V) { … }

void FunctionSpecializer::updateCallSites(Function *F, const Spec *Begin,
                                          const Spec *End) { … }
llvm/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp
