1260 lines · cpp
1//===- FunctionSpecialization.cpp - Function Specialization ---------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/Transforms/IPO/FunctionSpecialization.h"10#include "llvm/ADT/Statistic.h"11#include "llvm/Analysis/CodeMetrics.h"12#include "llvm/Analysis/ConstantFolding.h"13#include "llvm/Analysis/InlineCost.h"14#include "llvm/Analysis/InstructionSimplify.h"15#include "llvm/Analysis/TargetTransformInfo.h"16#include "llvm/Analysis/ValueLattice.h"17#include "llvm/Analysis/ValueLatticeUtils.h"18#include "llvm/Analysis/ValueTracking.h"19#include "llvm/Transforms/Scalar/SCCP.h"20#include "llvm/Transforms/Utils/Cloning.h"21#include "llvm/Transforms/Utils/SCCPSolver.h"22#include "llvm/Transforms/Utils/SizeOpts.h"23#include <cmath>24 25using namespace llvm;26 27#define DEBUG_TYPE "function-specialization"28 29STATISTIC(NumSpecsCreated, "Number of specializations created");30 31namespace llvm {32 33static cl::opt<bool> ForceSpecialization(34 "force-specialization", cl::init(false), cl::Hidden,35 cl::desc(36 "Force function specialization for every call site with a constant "37 "argument"));38 39static cl::opt<unsigned> MaxClones(40 "funcspec-max-clones", cl::init(3), cl::Hidden, cl::desc(41 "The maximum number of clones allowed for a single function "42 "specialization"));43 44static cl::opt<unsigned>45 MaxDiscoveryIterations("funcspec-max-discovery-iterations", cl::init(100),46 cl::Hidden,47 cl::desc("The maximum number of iterations allowed "48 "when searching for transitive "49 "phis"));50 51static cl::opt<unsigned> MaxIncomingPhiValues(52 "funcspec-max-incoming-phi-values", cl::init(8), cl::Hidden,53 cl::desc("The maximum number of incoming values a PHI node can have to be "54 "considered during the specialization bonus estimation"));55 56static cl::opt<unsigned> MaxBlockPredecessors(57 "funcspec-max-block-predecessors", cl::init(2), cl::Hidden, cl::desc(58 "The maximum number of predecessors a basic block can have to be "59 "considered during the estimation of dead code"));60 61static cl::opt<unsigned> MinFunctionSize(62 "funcspec-min-function-size", cl::init(500), cl::Hidden,63 cl::desc("Don't specialize functions that have less than this number of "64 "instructions"));65 66static cl::opt<unsigned> MaxCodeSizeGrowth(67 "funcspec-max-codesize-growth", cl::init(3), cl::Hidden, cl::desc(68 "Maximum codesize growth allowed per function"));69 70static cl::opt<unsigned> MinCodeSizeSavings(71 "funcspec-min-codesize-savings", cl::init(20), cl::Hidden,72 cl::desc("Reject specializations whose codesize savings are less than this "73 "much percent of the original function size"));74 75static cl::opt<unsigned> MinLatencySavings(76 "funcspec-min-latency-savings", cl::init(20), cl::Hidden,77 cl::desc("Reject specializations whose latency savings are less than this "78 "much percent of the original function size"));79 80static cl::opt<unsigned> MinInliningBonus(81 "funcspec-min-inlining-bonus", cl::init(300), cl::Hidden,82 cl::desc("Reject specializations whose inlining bonus is less than this "83 "much percent of the original function size"));84 85static cl::opt<bool> SpecializeOnAddress(86 "funcspec-on-address", cl::init(false), cl::Hidden, cl::desc(87 "Enable function specialization on the address of global values"));88 89static cl::opt<bool> SpecializeLiteralConstant(90 "funcspec-for-literal-constant", cl::init(true), cl::Hidden,91 cl::desc(92 "Enable specialization of functions that take a literal constant as an "93 "argument"));94 95extern cl::opt<bool> ProfcheckDisableMetadataFixes;96 97} // end namespace llvm98 99bool InstCostVisitor::canEliminateSuccessor(BasicBlock *BB,100 BasicBlock *Succ) const {101 unsigned I = 0;102 return all_of(predecessors(Succ), [&I, BB, Succ, this](BasicBlock *Pred) {103 return I++ < MaxBlockPredecessors &&104 (Pred == BB || Pred == Succ || !isBlockExecutable(Pred));105 });106}107 108// Estimates the codesize savings due to dead code after constant propagation.109// \p WorkList represents the basic blocks of a specialization which will110// eventually become dead once we replace instructions that are known to be111// constants. The successors of such blocks are added to the list as long as112// the \p Solver found they were executable prior to specialization, and only113// if all their predecessors are dead.114Cost InstCostVisitor::estimateBasicBlocks(115 SmallVectorImpl<BasicBlock *> &WorkList) {116 Cost CodeSize = 0;117 // Accumulate the codesize savings of each basic block.118 while (!WorkList.empty()) {119 BasicBlock *BB = WorkList.pop_back_val();120 121 // These blocks are considered dead as far as the InstCostVisitor122 // is concerned. They haven't been proven dead yet by the Solver,123 // but may become if we propagate the specialization arguments.124 assert(Solver.isBlockExecutable(BB) && "BB already found dead by IPSCCP!");125 if (!DeadBlocks.insert(BB).second)126 continue;127 128 for (Instruction &I : *BB) {129 // If it's a known constant we have already accounted for it.130 if (KnownConstants.contains(&I))131 continue;132 133 Cost C = TTI.getInstructionCost(&I, TargetTransformInfo::TCK_CodeSize);134 135 LLVM_DEBUG(dbgs() << "FnSpecialization: CodeSize " << C136 << " for user " << I << "\n");137 CodeSize += C;138 }139 140 // Keep adding dead successors to the list as long as they are141 // executable and only reachable from dead blocks.142 for (BasicBlock *SuccBB : successors(BB))143 if (isBlockExecutable(SuccBB) && canEliminateSuccessor(BB, SuccBB))144 WorkList.push_back(SuccBB);145 }146 return CodeSize;147}148 149Constant *InstCostVisitor::findConstantFor(Value *V) const {150 if (auto *C = dyn_cast<Constant>(V))151 return C;152 if (auto *C = Solver.getConstantOrNull(V))153 return C;154 return KnownConstants.lookup(V);155}156 157Cost InstCostVisitor::getCodeSizeSavingsFromPendingPHIs() {158 Cost CodeSize;159 while (!PendingPHIs.empty()) {160 Instruction *Phi = PendingPHIs.pop_back_val();161 // The pending PHIs could have been proven dead by now.162 if (isBlockExecutable(Phi->getParent()))163 CodeSize += getCodeSizeSavingsForUser(Phi);164 }165 return CodeSize;166}167 168/// Compute the codesize savings for replacing argument \p A with constant \p C.169Cost InstCostVisitor::getCodeSizeSavingsForArg(Argument *A, Constant *C) {170 LLVM_DEBUG(dbgs() << "FnSpecialization: Analysing bonus for constant: "171 << C->getNameOrAsOperand() << "\n");172 Cost CodeSize;173 for (auto *U : A->users())174 if (auto *UI = dyn_cast<Instruction>(U))175 if (isBlockExecutable(UI->getParent()))176 CodeSize += getCodeSizeSavingsForUser(UI, A, C);177 178 LLVM_DEBUG(dbgs() << "FnSpecialization: Accumulated bonus {CodeSize = "179 << CodeSize << "} for argument " << *A << "\n");180 return CodeSize;181}182 183/// Compute the latency savings from replacing all arguments with constants for184/// a specialization candidate. As this function computes the latency savings185/// for all Instructions in KnownConstants at once, it should be called only186/// after every instruction has been visited, i.e. after:187///188/// * getCodeSizeSavingsForArg has been run for every constant argument of a189/// specialization candidate190///191/// * getCodeSizeSavingsFromPendingPHIs has been run192///193/// to ensure that the latency savings are calculated for all Instructions we194/// have visited and found to be constant.195Cost InstCostVisitor::getLatencySavingsForKnownConstants() {196 auto &BFI = GetBFI(*F);197 Cost TotalLatency = 0;198 199 for (auto Pair : KnownConstants) {200 Instruction *I = dyn_cast<Instruction>(Pair.first);201 if (!I)202 continue;203 204 uint64_t Weight = BFI.getBlockFreq(I->getParent()).getFrequency() /205 BFI.getEntryFreq().getFrequency();206 207 Cost Latency =208 Weight * TTI.getInstructionCost(I, TargetTransformInfo::TCK_Latency);209 210 LLVM_DEBUG(dbgs() << "FnSpecialization: {Latency = " << Latency211 << "} for instruction " << *I << "\n");212 213 TotalLatency += Latency;214 }215 216 return TotalLatency;217}218 219Cost InstCostVisitor::getCodeSizeSavingsForUser(Instruction *User, Value *Use,220 Constant *C) {221 // We have already propagated a constant for this user.222 if (KnownConstants.contains(User))223 return 0;224 225 // Cache the iterator before visiting.226 LastVisited = Use ? KnownConstants.insert({Use, C}).first227 : KnownConstants.end();228 229 Cost CodeSize = 0;230 if (auto *I = dyn_cast<SwitchInst>(User)) {231 CodeSize = estimateSwitchInst(*I);232 } else if (auto *I = dyn_cast<BranchInst>(User)) {233 CodeSize = estimateBranchInst(*I);234 } else {235 C = visit(*User);236 if (!C)237 return 0;238 }239 240 // Even though it doesn't make sense to bind switch and branch instructions241 // with a constant, unlike any other instruction type, it prevents estimating242 // their bonus multiple times.243 KnownConstants.insert({User, C});244 245 CodeSize += TTI.getInstructionCost(User, TargetTransformInfo::TCK_CodeSize);246 247 LLVM_DEBUG(dbgs() << "FnSpecialization: {CodeSize = " << CodeSize248 << "} for user " << *User << "\n");249 250 for (auto *U : User->users())251 if (auto *UI = dyn_cast<Instruction>(U))252 if (UI != User && isBlockExecutable(UI->getParent()))253 CodeSize += getCodeSizeSavingsForUser(UI, User, C);254 255 return CodeSize;256}257 258Cost InstCostVisitor::estimateSwitchInst(SwitchInst &I) {259 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");260 261 if (I.getCondition() != LastVisited->first)262 return 0;263 264 auto *C = dyn_cast<ConstantInt>(LastVisited->second);265 if (!C)266 return 0;267 268 BasicBlock *Succ = I.findCaseValue(C)->getCaseSuccessor();269 // Initialize the worklist with the dead basic blocks. These are the270 // destination labels which are different from the one corresponding271 // to \p C. They should be executable and have a unique predecessor.272 SmallVector<BasicBlock *> WorkList;273 for (const auto &Case : I.cases()) {274 BasicBlock *BB = Case.getCaseSuccessor();275 if (BB != Succ && isBlockExecutable(BB) &&276 canEliminateSuccessor(I.getParent(), BB))277 WorkList.push_back(BB);278 }279 280 return estimateBasicBlocks(WorkList);281}282 283Cost InstCostVisitor::estimateBranchInst(BranchInst &I) {284 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");285 286 if (I.getCondition() != LastVisited->first)287 return 0;288 289 BasicBlock *Succ = I.getSuccessor(LastVisited->second->isOneValue());290 // Initialize the worklist with the dead successor as long as291 // it is executable and has a unique predecessor.292 SmallVector<BasicBlock *> WorkList;293 if (isBlockExecutable(Succ) && canEliminateSuccessor(I.getParent(), Succ))294 WorkList.push_back(Succ);295 296 return estimateBasicBlocks(WorkList);297}298 299bool InstCostVisitor::discoverTransitivelyIncomingValues(300 Constant *Const, PHINode *Root, DenseSet<PHINode *> &TransitivePHIs) {301 302 SmallVector<PHINode *, 64> WorkList;303 WorkList.push_back(Root);304 unsigned Iter = 0;305 306 while (!WorkList.empty()) {307 PHINode *PN = WorkList.pop_back_val();308 309 if (++Iter > MaxDiscoveryIterations ||310 PN->getNumIncomingValues() > MaxIncomingPhiValues)311 return false;312 313 if (!TransitivePHIs.insert(PN).second)314 continue;315 316 for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) {317 Value *V = PN->getIncomingValue(I);318 319 // Disregard self-references and dead incoming values.320 if (auto *Inst = dyn_cast<Instruction>(V))321 if (Inst == PN || !isBlockExecutable(PN->getIncomingBlock(I)))322 continue;323 324 if (Constant *C = findConstantFor(V)) {325 // Not all incoming values are the same constant. Bail immediately.326 if (C != Const)327 return false;328 continue;329 }330 331 if (auto *Phi = dyn_cast<PHINode>(V)) {332 WorkList.push_back(Phi);333 continue;334 }335 336 // We can't reason about anything else.337 return false;338 }339 }340 return true;341}342 343Constant *InstCostVisitor::visitPHINode(PHINode &I) {344 if (I.getNumIncomingValues() > MaxIncomingPhiValues)345 return nullptr;346 347 bool Inserted = VisitedPHIs.insert(&I).second;348 Constant *Const = nullptr;349 bool HaveSeenIncomingPHI = false;350 351 for (unsigned Idx = 0, E = I.getNumIncomingValues(); Idx != E; ++Idx) {352 Value *V = I.getIncomingValue(Idx);353 354 // Disregard self-references and dead incoming values.355 if (auto *Inst = dyn_cast<Instruction>(V))356 if (Inst == &I || !isBlockExecutable(I.getIncomingBlock(Idx)))357 continue;358 359 if (Constant *C = findConstantFor(V)) {360 if (!Const)361 Const = C;362 // Not all incoming values are the same constant. Bail immediately.363 if (C != Const)364 return nullptr;365 continue;366 }367 368 if (Inserted) {369 // First time we are seeing this phi. We will retry later, after370 // all the constant arguments have been propagated. Bail for now.371 PendingPHIs.push_back(&I);372 return nullptr;373 }374 375 if (isa<PHINode>(V)) {376 // Perhaps it is a Transitive Phi. We will confirm later.377 HaveSeenIncomingPHI = true;378 continue;379 }380 381 // We can't reason about anything else.382 return nullptr;383 }384 385 if (!Const)386 return nullptr;387 388 if (!HaveSeenIncomingPHI)389 return Const;390 391 DenseSet<PHINode *> TransitivePHIs;392 if (!discoverTransitivelyIncomingValues(Const, &I, TransitivePHIs))393 return nullptr;394 395 return Const;396}397 398Constant *InstCostVisitor::visitFreezeInst(FreezeInst &I) {399 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");400 401 if (isGuaranteedNotToBeUndefOrPoison(LastVisited->second))402 return LastVisited->second;403 return nullptr;404}405 406Constant *InstCostVisitor::visitCallBase(CallBase &I) {407 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");408 409 Function *F = I.getCalledFunction();410 if (!F || !canConstantFoldCallTo(&I, F))411 return nullptr;412 413 SmallVector<Constant *, 8> Operands;414 Operands.reserve(I.getNumOperands());415 416 for (unsigned Idx = 0, E = I.getNumOperands() - 1; Idx != E; ++Idx) {417 Value *V = I.getOperand(Idx);418 if (isa<MetadataAsValue>(V))419 return nullptr;420 Constant *C = findConstantFor(V);421 if (!C)422 return nullptr;423 Operands.push_back(C);424 }425 426 auto Ops = ArrayRef(Operands.begin(), Operands.end());427 return ConstantFoldCall(&I, F, Ops);428}429 430Constant *InstCostVisitor::visitLoadInst(LoadInst &I) {431 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");432 433 if (isa<ConstantPointerNull>(LastVisited->second))434 return nullptr;435 return ConstantFoldLoadFromConstPtr(LastVisited->second, I.getType(), DL);436}437 438Constant *InstCostVisitor::visitGetElementPtrInst(GetElementPtrInst &I) {439 SmallVector<Constant *, 8> Operands;440 Operands.reserve(I.getNumOperands());441 442 for (unsigned Idx = 0, E = I.getNumOperands(); Idx != E; ++Idx) {443 Value *V = I.getOperand(Idx);444 Constant *C = findConstantFor(V);445 if (!C)446 return nullptr;447 Operands.push_back(C);448 }449 450 auto Ops = ArrayRef(Operands.begin(), Operands.end());451 return ConstantFoldInstOperands(&I, Ops, DL);452}453 454Constant *InstCostVisitor::visitSelectInst(SelectInst &I) {455 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");456 457 if (I.getCondition() == LastVisited->first) {458 Value *V = LastVisited->second->isZeroValue() ? I.getFalseValue()459 : I.getTrueValue();460 return findConstantFor(V);461 }462 if (Constant *Condition = findConstantFor(I.getCondition()))463 if ((I.getTrueValue() == LastVisited->first && Condition->isOneValue()) ||464 (I.getFalseValue() == LastVisited->first && Condition->isZeroValue()))465 return LastVisited->second;466 return nullptr;467}468 469Constant *InstCostVisitor::visitCastInst(CastInst &I) {470 return ConstantFoldCastOperand(I.getOpcode(), LastVisited->second,471 I.getType(), DL);472}473 474Constant *InstCostVisitor::visitCmpInst(CmpInst &I) {475 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");476 477 Constant *Const = LastVisited->second;478 bool ConstOnRHS = I.getOperand(1) == LastVisited->first;479 Value *V = ConstOnRHS ? I.getOperand(0) : I.getOperand(1);480 Constant *Other = findConstantFor(V);481 482 if (Other) {483 if (ConstOnRHS)484 std::swap(Const, Other);485 return ConstantFoldCompareInstOperands(I.getPredicate(), Const, Other, DL);486 }487 488 // If we haven't found Other to be a specific constant value, we may still be489 // able to constant fold using information from the lattice value.490 const ValueLatticeElement &ConstLV = ValueLatticeElement::get(Const);491 const ValueLatticeElement &OtherLV = Solver.getLatticeValueFor(V);492 auto &V1State = ConstOnRHS ? OtherLV : ConstLV;493 auto &V2State = ConstOnRHS ? ConstLV : OtherLV;494 return V1State.getCompare(I.getPredicate(), I.getType(), V2State, DL);495}496 497Constant *InstCostVisitor::visitUnaryOperator(UnaryOperator &I) {498 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");499 500 return ConstantFoldUnaryOpOperand(I.getOpcode(), LastVisited->second, DL);501}502 503Constant *InstCostVisitor::visitBinaryOperator(BinaryOperator &I) {504 assert(LastVisited != KnownConstants.end() && "Invalid iterator!");505 506 bool ConstOnRHS = I.getOperand(1) == LastVisited->first;507 Value *V = ConstOnRHS ? I.getOperand(0) : I.getOperand(1);508 Constant *Other = findConstantFor(V);509 Value *OtherVal = Other ? Other : V;510 Value *ConstVal = LastVisited->second;511 512 if (ConstOnRHS)513 std::swap(ConstVal, OtherVal);514 515 return dyn_cast_or_null<Constant>(516 simplifyBinOp(I.getOpcode(), ConstVal, OtherVal, SimplifyQuery(DL)));517}518 519Constant *FunctionSpecializer::getPromotableAlloca(AllocaInst *Alloca,520 CallInst *Call) {521 Value *StoreValue = nullptr;522 for (auto *User : Alloca->users()) {523 // We can't use llvm::isAllocaPromotable() as that would fail because of524 // the usage in the CallInst, which is what we check here.525 if (User == Call)526 continue;527 528 if (auto *Store = dyn_cast<StoreInst>(User)) {529 // This is a duplicate store, bail out.530 if (StoreValue || Store->isVolatile())531 return nullptr;532 StoreValue = Store->getValueOperand();533 continue;534 }535 // Bail if there is any other unknown usage.536 return nullptr;537 }538 539 if (!StoreValue)540 return nullptr;541 542 return getCandidateConstant(StoreValue);543}544 545// A constant stack value is an AllocaInst that has a single constant546// value stored to it. Return this constant if such an alloca stack value547// is a function argument.548Constant *FunctionSpecializer::getConstantStackValue(CallInst *Call,549 Value *Val) {550 if (!Val)551 return nullptr;552 Val = Val->stripPointerCasts();553 if (auto *ConstVal = dyn_cast<ConstantInt>(Val))554 return ConstVal;555 auto *Alloca = dyn_cast<AllocaInst>(Val);556 if (!Alloca || !Alloca->getAllocatedType()->isIntegerTy())557 return nullptr;558 return getPromotableAlloca(Alloca, Call);559}560 561// To support specializing recursive functions, it is important to propagate562// constant arguments because after a first iteration of specialisation, a563// reduced example may look like this:564//565// define internal void @RecursiveFn(i32* arg1) {566// %temp = alloca i32, align 4567// store i32 2 i32* %temp, align 4568// call void @RecursiveFn.1(i32* nonnull %temp)569// ret void570// }571//572// Before a next iteration, we need to propagate the constant like so573// which allows further specialization in next iterations.574//575// @funcspec.arg = internal constant i32 2576//577// define internal void @someFunc(i32* arg1) {578// call void @otherFunc(i32* nonnull @funcspec.arg)579// ret void580// }581//582// See if there are any new constant values for the callers of \p F via583// stack variables and promote them to global variables.584void FunctionSpecializer::promoteConstantStackValues(Function *F) {585 for (User *U : F->users()) {586 587 auto *Call = dyn_cast<CallInst>(U);588 if (!Call)589 continue;590 591 if (!Solver.isBlockExecutable(Call->getParent()))592 continue;593 594 for (const Use &U : Call->args()) {595 unsigned Idx = Call->getArgOperandNo(&U);596 Value *ArgOp = Call->getArgOperand(Idx);597 Type *ArgOpType = ArgOp->getType();598 599 if (!Call->onlyReadsMemory(Idx) || !ArgOpType->isPointerTy())600 continue;601 602 auto *ConstVal = getConstantStackValue(Call, ArgOp);603 if (!ConstVal)604 continue;605 606 Value *GV = new GlobalVariable(M, ConstVal->getType(), true,607 GlobalValue::InternalLinkage, ConstVal,608 "specialized.arg." + Twine(++NGlobals));609 Call->setArgOperand(Idx, GV);610 }611 }612}613 614// The SCCP solver inserts bitcasts for PredicateInfo. These interfere with the615// promoteConstantStackValues() optimization.616static void removeSSACopy(Function &F) {617 for (BasicBlock &BB : F) {618 for (Instruction &Inst : llvm::make_early_inc_range(BB)) {619 auto *BC = dyn_cast<BitCastInst>(&Inst);620 if (!BC || BC->getType() != BC->getOperand(0)->getType())621 continue;622 Inst.replaceAllUsesWith(BC->getOperand(0));623 Inst.eraseFromParent();624 }625 }626}627 628/// Remove any ssa_copy intrinsics that may have been introduced.629void FunctionSpecializer::cleanUpSSA() {630 for (Function *F : Specializations)631 removeSSACopy(*F);632}633 634 635template <> struct llvm::DenseMapInfo<SpecSig> {636 static inline SpecSig getEmptyKey() { return {~0U, {}}; }637 638 static inline SpecSig getTombstoneKey() { return {~1U, {}}; }639 640 static unsigned getHashValue(const SpecSig &S) {641 return static_cast<unsigned>(hash_value(S));642 }643 644 static bool isEqual(const SpecSig &LHS, const SpecSig &RHS) {645 return LHS == RHS;646 }647};648 649FunctionSpecializer::~FunctionSpecializer() {650 LLVM_DEBUG(651 if (NumSpecsCreated > 0)652 dbgs() << "FnSpecialization: Created " << NumSpecsCreated653 << " specializations in module " << M.getName() << "\n");654 // Eliminate dead code.655 removeDeadFunctions();656 cleanUpSSA();657}658 659/// Get the unsigned Value of given Cost object. Assumes the Cost is always660/// non-negative, which is true for both TCK_CodeSize and TCK_Latency, and661/// always Valid.662static unsigned getCostValue(const Cost &C) {663 int64_t Value = C.getValue();664 665 assert(Value >= 0 && "CodeSize and Latency cannot be negative");666 // It is safe to down cast since we know the arguments cannot be negative and667 // Cost is of type int64_t.668 return static_cast<unsigned>(Value);669}670 671/// Attempt to specialize functions in the module to enable constant672/// propagation across function boundaries.673///674/// \returns true if at least one function is specialized.675bool FunctionSpecializer::run() {676 // Find possible specializations for each function.677 SpecMap SM;678 SmallVector<Spec, 32> AllSpecs;679 unsigned NumCandidates = 0;680 for (Function &F : M) {681 if (!isCandidateFunction(&F))682 continue;683 684 auto [It, Inserted] = FunctionMetrics.try_emplace(&F);685 CodeMetrics &Metrics = It->second;686 //Analyze the function.687 if (Inserted) {688 SmallPtrSet<const Value *, 32> EphValues;689 CodeMetrics::collectEphemeralValues(&F, &GetAC(F), EphValues);690 for (BasicBlock &BB : F)691 Metrics.analyzeBasicBlock(&BB, GetTTI(F), EphValues);692 }693 694 // When specializing literal constants is enabled, always require functions695 // to be larger than MinFunctionSize, to prevent excessive specialization.696 const bool RequireMinSize =697 !ForceSpecialization &&698 (SpecializeLiteralConstant || !F.hasFnAttribute(Attribute::NoInline));699 700 // If the code metrics reveal that we shouldn't duplicate the function,701 // or if the code size implies that this function is easy to get inlined,702 // then we shouldn't specialize it.703 if (Metrics.notDuplicatable || !Metrics.NumInsts.isValid() ||704 (RequireMinSize && Metrics.NumInsts < MinFunctionSize))705 continue;706 707 // When specialization on literal constants is disabled, only consider708 // recursive functions when running multiple times to save wasted analysis,709 // as we will not be able to specialize on any newly found literal constant710 // return values.711 if (!SpecializeLiteralConstant && !Inserted && !Metrics.isRecursive)712 continue;713 714 int64_t Sz = Metrics.NumInsts.getValue();715 assert(Sz > 0 && "CodeSize should be positive");716 // It is safe to down cast from int64_t, NumInsts is always positive.717 unsigned FuncSize = static_cast<unsigned>(Sz);718 719 LLVM_DEBUG(dbgs() << "FnSpecialization: Specialization cost for "720 << F.getName() << " is " << FuncSize << "\n");721 722 if (Inserted && Metrics.isRecursive)723 promoteConstantStackValues(&F);724 725 if (!findSpecializations(&F, FuncSize, AllSpecs, SM)) {726 LLVM_DEBUG(727 dbgs() << "FnSpecialization: No possible specializations found for "728 << F.getName() << "\n");729 continue;730 }731 732 ++NumCandidates;733 }734 735 if (!NumCandidates) {736 LLVM_DEBUG(737 dbgs()738 << "FnSpecialization: No possible specializations found in module\n");739 return false;740 }741 742 // Choose the most profitable specialisations, which fit in the module743 // specialization budget, which is derived from maximum number of744 // specializations per specialization candidate function.745 auto CompareScore = [&AllSpecs](unsigned I, unsigned J) {746 if (AllSpecs[I].Score != AllSpecs[J].Score)747 return AllSpecs[I].Score > AllSpecs[J].Score;748 return I > J;749 };750 const unsigned NSpecs =751 std::min(NumCandidates * MaxClones, unsigned(AllSpecs.size()));752 SmallVector<unsigned> BestSpecs(NSpecs + 1);753 std::iota(BestSpecs.begin(), BestSpecs.begin() + NSpecs, 0);754 if (AllSpecs.size() > NSpecs) {755 LLVM_DEBUG(dbgs() << "FnSpecialization: Number of candidates exceed "756 << "the maximum number of clones threshold.\n"757 << "FnSpecialization: Specializing the "758 << NSpecs759 << " most profitable candidates.\n");760 std::make_heap(BestSpecs.begin(), BestSpecs.begin() + NSpecs, CompareScore);761 for (unsigned I = NSpecs, N = AllSpecs.size(); I < N; ++I) {762 BestSpecs[NSpecs] = I;763 std::push_heap(BestSpecs.begin(), BestSpecs.end(), CompareScore);764 std::pop_heap(BestSpecs.begin(), BestSpecs.end(), CompareScore);765 }766 }767 768 LLVM_DEBUG(dbgs() << "FnSpecialization: List of specializations \n";769 for (unsigned I = 0; I < NSpecs; ++I) {770 const Spec &S = AllSpecs[BestSpecs[I]];771 dbgs() << "FnSpecialization: Function " << S.F->getName()772 << " , score " << S.Score << "\n";773 for (const ArgInfo &Arg : S.Sig.Args)774 dbgs() << "FnSpecialization: FormalArg = "775 << Arg.Formal->getNameOrAsOperand()776 << ", ActualArg = " << Arg.Actual->getNameOrAsOperand()777 << "\n";778 });779 780 // Create the chosen specializations.781 SmallPtrSet<Function *, 8> OriginalFuncs;782 SmallVector<Function *> Clones;783 for (unsigned I = 0; I < NSpecs; ++I) {784 Spec &S = AllSpecs[BestSpecs[I]];785 786 // Accumulate the codesize growth for the function, now we are creating the787 // specialization.788 FunctionGrowth[S.F] += S.CodeSize;789 790 S.Clone = createSpecialization(S.F, S.Sig);791 792 // Update the known call sites to call the clone.793 for (CallBase *Call : S.CallSites) {794 Function *Clone = S.Clone;795 LLVM_DEBUG(dbgs() << "FnSpecialization: Redirecting " << *Call796 << " to call " << Clone->getName() << "\n");797 Call->setCalledFunction(S.Clone);798 auto &BFI = GetBFI(*Call->getFunction());799 std::optional<uint64_t> Count =800 BFI.getBlockProfileCount(Call->getParent());801 if (Count && !ProfcheckDisableMetadataFixes) {802 std::optional<llvm::Function::ProfileCount> MaybeCloneCount =803 Clone->getEntryCount();804 if (MaybeCloneCount) {805 uint64_t CallCount = *Count + MaybeCloneCount->getCount();806 Clone->setEntryCount(CallCount);807 if (std::optional<llvm::Function::ProfileCount> MaybeOriginalCount =808 S.F->getEntryCount()) {809 uint64_t OriginalCount = MaybeOriginalCount->getCount();810 if (OriginalCount >= *Count) {811 S.F->setEntryCount(OriginalCount - *Count);812 } else {813 // This should generally not happen as that would mean there are814 // more computed calls to the function than what was recorded.815 LLVM_DEBUG(S.F->setEntryCount(0));816 }817 }818 }819 }820 }821 822 Clones.push_back(S.Clone);823 OriginalFuncs.insert(S.F);824 }825 826 Solver.solveWhileResolvedUndefsIn(Clones);827 828 // Update the rest of the call sites - these are the recursive calls, calls829 // to discarded specialisations and calls that may match a specialisation830 // after the solver runs.831 for (Function *F : OriginalFuncs) {832 auto [Begin, End] = SM[F];833 updateCallSites(F, AllSpecs.begin() + Begin, AllSpecs.begin() + End);834 }835 836 for (Function *F : Clones) {837 if (F->getReturnType()->isVoidTy())838 continue;839 if (F->getReturnType()->isStructTy()) {840 auto *STy = cast<StructType>(F->getReturnType());841 if (!Solver.isStructLatticeConstant(F, STy))842 continue;843 } else {844 auto It = Solver.getTrackedRetVals().find(F);845 assert(It != Solver.getTrackedRetVals().end() &&846 "Return value ought to be tracked");847 if (SCCPSolver::isOverdefined(It->second))848 continue;849 }850 for (User *U : F->users()) {851 if (auto *CS = dyn_cast<CallBase>(U)) {852 //The user instruction does not call our function.853 if (CS->getCalledFunction() != F)854 continue;855 Solver.resetLatticeValueFor(CS);856 }857 }858 }859 860 // Rerun the solver to notify the users of the modified callsites.861 Solver.solveWhileResolvedUndefs();862 863 for (Function *F : OriginalFuncs)864 if (FunctionMetrics[F].isRecursive)865 promoteConstantStackValues(F);866 867 return true;868}869 870void FunctionSpecializer::removeDeadFunctions() {871 for (Function *F : DeadFunctions) {872 LLVM_DEBUG(dbgs() << "FnSpecialization: Removing dead function "873 << F->getName() << "\n");874 if (FAM)875 FAM->clear(*F, F->getName());876 877 // Remove all the callsites that were proven unreachable once, and replace878 // them with poison.879 for (User *U : make_early_inc_range(F->users())) {880 assert((isa<CallInst>(U) || isa<InvokeInst>(U)) &&881 "User of dead function must be call or invoke");882 Instruction *CS = cast<Instruction>(U);883 CS->replaceAllUsesWith(PoisonValue::get(CS->getType()));884 CS->eraseFromParent();885 }886 F->eraseFromParent();887 }888 DeadFunctions.clear();889}890 891/// Clone the function \p F and remove the ssa_copy intrinsics added by892/// the SCCPSolver in the cloned version.893static Function *cloneCandidateFunction(Function *F, unsigned NSpecs) {894 ValueToValueMapTy Mappings;895 Function *Clone = CloneFunction(F, Mappings);896 Clone->setName(F->getName() + ".specialized." + Twine(NSpecs));897 removeSSACopy(*Clone);898 return Clone;899}900 901bool FunctionSpecializer::findSpecializations(Function *F, unsigned FuncSize,902 SmallVectorImpl<Spec> &AllSpecs,903 SpecMap &SM) {904 // A mapping from a specialisation signature to the index of the respective905 // entry in the all specialisation array. Used to ensure uniqueness of906 // specialisations.907 DenseMap<SpecSig, unsigned> UniqueSpecs;908 909 // Get a list of interesting arguments.910 SmallVector<Argument *> Args;911 for (Argument &Arg : F->args())912 if (isArgumentInteresting(&Arg))913 Args.push_back(&Arg);914 915 if (Args.empty())916 return false;917 918 for (User *U : F->users()) {919 if (!isa<CallInst>(U) && !isa<InvokeInst>(U))920 continue;921 auto &CS = *cast<CallBase>(U);922 923 // The user instruction does not call our function.924 if (CS.getCalledFunction() != F)925 continue;926 927 // If the call site has attribute minsize set, that callsite won't be928 // specialized.929 if (CS.hasFnAttr(Attribute::MinSize))930 continue;931 932 // If the parent of the call site will never be executed, we don't need933 // to worry about the passed value.934 if (!Solver.isBlockExecutable(CS.getParent()))935 continue;936 937 // Examine arguments and create a specialisation candidate from the938 // constant operands of this call site.939 SpecSig S;940 for (Argument *A : Args) {941 Constant *C = getCandidateConstant(CS.getArgOperand(A->getArgNo()));942 if (!C)943 continue;944 LLVM_DEBUG(dbgs() << "FnSpecialization: Found interesting argument "945 << A->getName() << " : " << C->getNameOrAsOperand()946 << "\n");947 S.Args.push_back({A, C});948 }949 950 if (S.Args.empty())951 continue;952 953 // Check if we have encountered the same specialisation already.954 if (auto It = UniqueSpecs.find(S); It != UniqueSpecs.end()) {955 // Existing specialisation. Add the call to the list to rewrite, unless956 // it's a recursive call. A specialisation, generated because of a957 // recursive call may end up as not the best specialisation for all958 // the cloned instances of this call, which result from specialising959 // functions. Hence we don't rewrite the call directly, but match it with960 // the best specialisation once all specialisations are known.961 if (CS.getFunction() == F)962 continue;963 const unsigned Index = It->second;964 AllSpecs[Index].CallSites.push_back(&CS);965 } else {966 // Calculate the specialisation gain.967 Cost CodeSize;968 unsigned Score = 0;969 InstCostVisitor Visitor = getInstCostVisitorFor(F);970 for (ArgInfo &A : S.Args) {971 CodeSize += Visitor.getCodeSizeSavingsForArg(A.Formal, A.Actual);972 Score += getInliningBonus(A.Formal, A.Actual);973 }974 CodeSize += Visitor.getCodeSizeSavingsFromPendingPHIs();975 976 unsigned CodeSizeSavings = getCostValue(CodeSize);977 unsigned SpecSize = FuncSize - CodeSizeSavings;978 979 auto IsProfitable = [&]() -> bool {980 // No check required.981 if (ForceSpecialization)982 return true;983 984 LLVM_DEBUG(985 dbgs() << "FnSpecialization: Specialization bonus {Inlining = "986 << Score << " (" << (Score * 100 / FuncSize) << "%)}\n");987 988 // Minimum inlining bonus.989 if (Score > MinInliningBonus * FuncSize / 100)990 return true;991 992 LLVM_DEBUG(993 dbgs() << "FnSpecialization: Specialization bonus {CodeSize = "994 << CodeSizeSavings << " ("995 << (CodeSizeSavings * 100 / FuncSize) << "%)}\n");996 997 // Minimum codesize savings.998 if (CodeSizeSavings < MinCodeSizeSavings * FuncSize / 100)999 return false;1000 1001 // Lazily compute the Latency, to avoid unnecessarily computing BFI.1002 unsigned LatencySavings =1003 getCostValue(Visitor.getLatencySavingsForKnownConstants());1004 1005 LLVM_DEBUG(1006 dbgs() << "FnSpecialization: Specialization bonus {Latency = "1007 << LatencySavings << " ("1008 << (LatencySavings * 100 / FuncSize) << "%)}\n");1009 1010 // Minimum latency savings.1011 if (LatencySavings < MinLatencySavings * FuncSize / 100)1012 return false;1013 // Maximum codesize growth.1014 if ((FunctionGrowth[F] + SpecSize) / FuncSize > MaxCodeSizeGrowth)1015 return false;1016 1017 Score += std::max(CodeSizeSavings, LatencySavings);1018 return true;1019 };1020 1021 // Discard unprofitable specialisations.1022 if (!IsProfitable())1023 continue;1024 1025 // Create a new specialisation entry.1026 auto &Spec = AllSpecs.emplace_back(F, S, Score, SpecSize);1027 if (CS.getFunction() != F)1028 Spec.CallSites.push_back(&CS);1029 const unsigned Index = AllSpecs.size() - 1;1030 UniqueSpecs[S] = Index;1031 if (auto [It, Inserted] = SM.try_emplace(F, Index, Index + 1); !Inserted)1032 It->second.second = Index + 1;1033 }1034 }1035 1036 return !UniqueSpecs.empty();1037}1038 1039bool FunctionSpecializer::isCandidateFunction(Function *F) {1040 if (F->isDeclaration() || F->arg_empty())1041 return false;1042 1043 if (F->hasFnAttribute(Attribute::NoDuplicate))1044 return false;1045 1046 // Do not specialize the cloned function again.1047 if (Specializations.contains(F))1048 return false;1049 1050 // If we're optimizing the function for size, we shouldn't specialize it.1051 if (shouldOptimizeForSize(F, nullptr, nullptr, PGSOQueryType::IRPass))1052 return false;1053 1054 // Exit if the function is not executable. There's no point in specializing1055 // a dead function.1056 if (!Solver.isBlockExecutable(&F->getEntryBlock()))1057 return false;1058 1059 // It wastes time to specialize a function which would get inlined finally.1060 if (F->hasFnAttribute(Attribute::AlwaysInline))1061 return false;1062 1063 LLVM_DEBUG(dbgs() << "FnSpecialization: Try function: " << F->getName()1064 << "\n");1065 return true;1066}1067 1068Function *FunctionSpecializer::createSpecialization(Function *F,1069 const SpecSig &S) {1070 Function *Clone = cloneCandidateFunction(F, Specializations.size() + 1);1071 1072 // The original function does not neccessarily have internal linkage, but the1073 // clone must.1074 Clone->setLinkage(GlobalValue::InternalLinkage);1075 1076 if (F->getEntryCount() && !ProfcheckDisableMetadataFixes)1077 Clone->setEntryCount(0);1078 1079 // Initialize the lattice state of the arguments of the function clone,1080 // marking the argument on which we specialized the function constant1081 // with the given value.1082 Solver.setLatticeValueForSpecializationArguments(Clone, S.Args);1083 Solver.markBlockExecutable(&Clone->front());1084 Solver.addArgumentTrackedFunction(Clone);1085 Solver.addTrackedFunction(Clone);1086 1087 // Mark all the specialized functions1088 Specializations.insert(Clone);1089 ++NumSpecsCreated;1090 1091 return Clone;1092}1093 1094/// Compute the inlining bonus for replacing argument \p A with constant \p C.1095/// The below heuristic is only concerned with exposing inlining1096/// opportunities via indirect call promotion. If the argument is not a1097/// (potentially casted) function pointer, give up.1098unsigned FunctionSpecializer::getInliningBonus(Argument *A, Constant *C) {1099 Function *CalledFunction = dyn_cast<Function>(C->stripPointerCasts());1100 if (!CalledFunction)1101 return 0;1102 1103 // Get TTI for the called function (used for the inline cost).1104 auto &CalleeTTI = (GetTTI)(*CalledFunction);1105 1106 // Look at all the call sites whose called value is the argument.1107 // Specializing the function on the argument would allow these indirect1108 // calls to be promoted to direct calls. If the indirect call promotion1109 // would likely enable the called function to be inlined, specializing is a1110 // good idea.1111 int InliningBonus = 0;1112 for (User *U : A->users()) {1113 if (!isa<CallInst>(U) && !isa<InvokeInst>(U))1114 continue;1115 auto *CS = cast<CallBase>(U);1116 if (CS->getCalledOperand() != A)1117 continue;1118 if (CS->getFunctionType() != CalledFunction->getFunctionType())1119 continue;1120 1121 // Get the cost of inlining the called function at this call site. Note1122 // that this is only an estimate. The called function may eventually1123 // change in a way that leads to it not being inlined here, even though1124 // inlining looks profitable now. For example, one of its called1125 // functions may be inlined into it, making the called function too large1126 // to be inlined into this call site.1127 //1128 // We apply a boost for performing indirect call promotion by increasing1129 // the default threshold by the threshold for indirect calls.1130 auto Params = getInlineParams();1131 Params.DefaultThreshold += InlineConstants::IndirectCallThreshold;1132 InlineCost IC =1133 getInlineCost(*CS, CalledFunction, Params, CalleeTTI, GetAC, GetTLI);1134 1135 // We clamp the bonus for this call to be between zero and the default1136 // threshold.1137 if (IC.isAlways())1138 InliningBonus += Params.DefaultThreshold;1139 else if (IC.isVariable() && IC.getCostDelta() > 0)1140 InliningBonus += IC.getCostDelta();1141 1142 LLVM_DEBUG(dbgs() << "FnSpecialization: Inlining bonus " << InliningBonus1143 << " for user " << *U << "\n");1144 }1145 1146 return InliningBonus > 0 ? static_cast<unsigned>(InliningBonus) : 0;1147}1148 1149/// Determine if it is possible to specialise the function for constant values1150/// of the formal parameter \p A.1151bool FunctionSpecializer::isArgumentInteresting(Argument *A) {1152 // No point in specialization if the argument is unused.1153 if (A->user_empty())1154 return false;1155 1156 Type *Ty = A->getType();1157 if (!Ty->isPointerTy() && (!SpecializeLiteralConstant ||1158 (!Ty->isIntegerTy() && !Ty->isFloatingPointTy() && !Ty->isStructTy())))1159 return false;1160 1161 // SCCP solver does not record an argument that will be constructed on1162 // stack.1163 if (A->hasByValAttr() && !A->getParent()->onlyReadsMemory())1164 return false;1165 1166 // For non-argument-tracked functions every argument is overdefined.1167 if (!Solver.isArgumentTrackedFunction(A->getParent()))1168 return true;1169 1170 // Check the lattice value and decide if we should attemt to specialize,1171 // based on this argument. No point in specialization, if the lattice value1172 // is already a constant.1173 bool IsOverdefined = Ty->isStructTy()1174 ? any_of(Solver.getStructLatticeValueFor(A), SCCPSolver::isOverdefined)1175 : SCCPSolver::isOverdefined(Solver.getLatticeValueFor(A));1176 1177 LLVM_DEBUG(1178 if (IsOverdefined)1179 dbgs() << "FnSpecialization: Found interesting parameter "1180 << A->getNameOrAsOperand() << "\n";1181 else1182 dbgs() << "FnSpecialization: Nothing to do, parameter "1183 << A->getNameOrAsOperand() << " is already constant\n";1184 );1185 return IsOverdefined;1186}1187 1188/// Check if the value \p V (an actual argument) is a constant or can only1189/// have a constant value. Return that constant.1190Constant *FunctionSpecializer::getCandidateConstant(Value *V) {1191 if (isa<PoisonValue>(V))1192 return nullptr;1193 1194 // Select for possible specialisation values that are constants or1195 // are deduced to be constants or constant ranges with a single element.1196 Constant *C = dyn_cast<Constant>(V);1197 if (!C)1198 C = Solver.getConstantOrNull(V);1199 1200 // Don't specialize on (anything derived from) the address of a non-constant1201 // global variable, unless explicitly enabled.1202 if (C && C->getType()->isPointerTy() && !C->isNullValue())1203 if (auto *GV = dyn_cast<GlobalVariable>(getUnderlyingObject(C));1204 GV && !(GV->isConstant() || SpecializeOnAddress))1205 return nullptr;1206 1207 return C;1208}1209 1210void FunctionSpecializer::updateCallSites(Function *F, const Spec *Begin,1211 const Spec *End) {1212 // Collect the call sites that need updating.1213 SmallVector<CallBase *> ToUpdate;1214 for (User *U : F->users())1215 if (auto *CS = dyn_cast<CallBase>(U);1216 CS && CS->getCalledFunction() == F &&1217 Solver.isBlockExecutable(CS->getParent()))1218 ToUpdate.push_back(CS);1219 1220 unsigned NCallsLeft = ToUpdate.size();1221 for (CallBase *CS : ToUpdate) {1222 bool ShouldDecrementCount = CS->getFunction() == F;1223 1224 // Find the best matching specialisation.1225 const Spec *BestSpec = nullptr;1226 for (const Spec &S : make_range(Begin, End)) {1227 if (!S.Clone || (BestSpec && S.Score <= BestSpec->Score))1228 continue;1229 1230 if (any_of(S.Sig.Args, [CS, this](const ArgInfo &Arg) {1231 unsigned ArgNo = Arg.Formal->getArgNo();1232 return getCandidateConstant(CS->getArgOperand(ArgNo)) != Arg.Actual;1233 }))1234 continue;1235 1236 BestSpec = &S;1237 }1238 1239 if (BestSpec) {1240 LLVM_DEBUG(dbgs() << "FnSpecialization: Redirecting " << *CS1241 << " to call " << BestSpec->Clone->getName() << "\n");1242 CS->setCalledFunction(BestSpec->Clone);1243 ShouldDecrementCount = true;1244 }1245 1246 if (ShouldDecrementCount)1247 --NCallsLeft;1248 }1249 1250 // If the function has been completely specialized, the original function1251 // is no longer needed. Mark it unreachable.1252 // NOTE: If the address of a function is taken, we cannot treat it as dead1253 // function.1254 if (NCallsLeft == 0 && Solver.isArgumentTrackedFunction(F) &&1255 !F->hasAddressTaken()) {1256 Solver.markFunctionUnreachable(F);1257 DeadFunctions.insert(F);1258 }1259}1260