diff options
Diffstat (limited to 'llvm/lib/Transforms/IPO/FunctionSpecialization.cpp')
| -rw-r--r-- | llvm/lib/Transforms/IPO/FunctionSpecialization.cpp | 707 |
1 files changed, 484 insertions, 223 deletions
diff --git a/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp b/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp index 4a7efb28e853..3d6c501e4596 100644 --- a/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp +++ b/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp @@ -48,11 +48,13 @@ #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/LoopInfo.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" @@ -64,42 +66,324 @@ using namespace llvm; #define DEBUG_TYPE "function-specialization" -STATISTIC(NumFuncSpecialized, "Number of functions specialized"); +STATISTIC(NumSpecsCreated, "Number of specializations created"); -static cl::opt<bool> ForceFunctionSpecialization( - "force-function-specialization", cl::init(false), cl::Hidden, - cl::desc("Force function specialization for every call site with a " - "constant argument")); +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> MaxClonesThreshold( - "func-specialization-max-clones", cl::Hidden, - cl::desc("The maximum number of clones allowed for a single function " - "specialization"), - cl::init(3)); +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> SmallFunctionThreshold( - "func-specialization-size-threshold", cl::Hidden, - cl::desc("Don't specialize functions that have less than this theshold " - "number of instructions"), - cl::init(100)); +static cl::opt<unsigned> MaxIncomingPhiValues( + "funcspec-max-incoming-phi-values", cl::init(4), 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> - AvgLoopIterationCount("func-specialization-avg-iters-cost", cl::Hidden, - cl::desc("Average loop iteration count cost"), - cl::init(10)); +static cl::opt<unsigned> MinFunctionSize( + "funcspec-min-function-size", cl::init(100), cl::Hidden, cl::desc( + "Don't specialize functions that have less than this number of " + "instructions")); -static cl::opt<bool> SpecializeOnAddresses( - "func-specialization-on-address", cl::init(false), cl::Hidden, - cl::desc("Enable function specialization on the address of global values")); +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> EnableSpecializationForLiteralConstant( - "function-specialization-for-literal-constant", cl::init(false), cl::Hidden, - cl::desc("Enable specialization of functions that take a literal constant " - "as an argument.")); +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")); + +// Estimates the instruction cost of all the basic blocks in \p WorkList. +// The successors of such blocks are added to the list as long as they are +// executable and they have a unique predecessor. \p WorkList represents +// the basic blocks of a specialization which become dead once we replace +// instructions that are known to be constants. The aim here is to estimate +// the combination of size and latency savings in comparison to the non +// specialized version of the function. +static Cost estimateBasicBlocks(SmallVectorImpl<BasicBlock *> &WorkList, + DenseSet<BasicBlock *> &DeadBlocks, + ConstMap &KnownConstants, SCCPSolver &Solver, + BlockFrequencyInfo &BFI, + TargetTransformInfo &TTI) { + Cost Bonus = 0; + + // Accumulate the instruction cost of each basic block weighted by frequency. + while (!WorkList.empty()) { + BasicBlock *BB = WorkList.pop_back_val(); + + uint64_t Weight = BFI.getBlockFreq(BB).getFrequency() / + BFI.getEntryFreq(); + if (!Weight) + continue; + + // These blocks are considered dead as far as the InstCostVisitor is + // concerned. They haven't been proven dead yet by the Solver, but + // may become if we propagate the constant specialization arguments. + if (!DeadBlocks.insert(BB).second) + continue; + + for (Instruction &I : *BB) { + // Disregard SSA copies. + if (auto *II = dyn_cast<IntrinsicInst>(&I)) + if (II->getIntrinsicID() == Intrinsic::ssa_copy) + continue; + // If it's a known constant we have already accounted for it. + if (KnownConstants.contains(&I)) + continue; + + Bonus += Weight * + TTI.getInstructionCost(&I, TargetTransformInfo::TCK_SizeAndLatency); + + LLVM_DEBUG(dbgs() << "FnSpecialization: Bonus " << Bonus + << " after user " << I << "\n"); + } + + // Keep adding dead successors to the list as long as they are + // executable and they have a unique predecessor. + for (BasicBlock *SuccBB : successors(BB)) + if (Solver.isBlockExecutable(SuccBB) && + SuccBB->getUniquePredecessor() == BB) + WorkList.push_back(SuccBB); + } + return Bonus; +} + +static Constant *findConstantFor(Value *V, ConstMap &KnownConstants) { + if (auto *C = dyn_cast<Constant>(V)) + return C; + if (auto It = KnownConstants.find(V); It != KnownConstants.end()) + return It->second; + return nullptr; +} + +Cost InstCostVisitor::getBonusFromPendingPHIs() { + Cost Bonus = 0; + while (!PendingPHIs.empty()) { + Instruction *Phi = PendingPHIs.pop_back_val(); + Bonus += getUserBonus(Phi); + } + return Bonus; +} + +Cost InstCostVisitor::getUserBonus(Instruction *User, Value *Use, Constant *C) { + // Cache the iterator before visiting. + LastVisited = Use ? KnownConstants.insert({Use, C}).first + : KnownConstants.end(); + + if (auto *I = dyn_cast<SwitchInst>(User)) + return estimateSwitchInst(*I); + + if (auto *I = dyn_cast<BranchInst>(User)) + return estimateBranchInst(*I); + + C = visit(*User); + if (!C) + return 0; + + KnownConstants.insert({User, C}); + + uint64_t Weight = BFI.getBlockFreq(User->getParent()).getFrequency() / + BFI.getEntryFreq(); + if (!Weight) + return 0; + + Cost Bonus = Weight * + TTI.getInstructionCost(User, TargetTransformInfo::TCK_SizeAndLatency); + + LLVM_DEBUG(dbgs() << "FnSpecialization: Bonus " << Bonus + << " for user " << *User << "\n"); + + for (auto *U : User->users()) + if (auto *UI = dyn_cast<Instruction>(U)) + if (UI != User && Solver.isBlockExecutable(UI->getParent())) + Bonus += getUserBonus(UI, User, C); + + return Bonus; +} + +Cost InstCostVisitor::estimateSwitchInst(SwitchInst &I) { + assert(LastVisited != KnownConstants.end() && "Invalid iterator!"); + + if (I.getCondition() != LastVisited->first) + return 0; + + auto *C = dyn_cast<ConstantInt>(LastVisited->second); + if (!C) + return 0; + + BasicBlock *Succ = I.findCaseValue(C)->getCaseSuccessor(); + // Initialize the worklist with the dead basic blocks. These are the + // destination labels which are different from the one corresponding + // to \p C. They should be executable and have a unique predecessor. + SmallVector<BasicBlock *> WorkList; + for (const auto &Case : I.cases()) { + BasicBlock *BB = Case.getCaseSuccessor(); + if (BB == Succ || !Solver.isBlockExecutable(BB) || + BB->getUniquePredecessor() != I.getParent()) + continue; + WorkList.push_back(BB); + } + + return estimateBasicBlocks(WorkList, DeadBlocks, KnownConstants, Solver, BFI, + TTI); +} + +Cost InstCostVisitor::estimateBranchInst(BranchInst &I) { + assert(LastVisited != KnownConstants.end() && "Invalid iterator!"); + + if (I.getCondition() != LastVisited->first) + return 0; + + BasicBlock *Succ = I.getSuccessor(LastVisited->second->isOneValue()); + // Initialize the worklist with the dead successor as long as + // it is executable and has a unique predecessor. + SmallVector<BasicBlock *> WorkList; + if (Solver.isBlockExecutable(Succ) && + Succ->getUniquePredecessor() == I.getParent()) + WorkList.push_back(Succ); + + return estimateBasicBlocks(WorkList, DeadBlocks, KnownConstants, Solver, BFI, + TTI); +} + +Constant *InstCostVisitor::visitPHINode(PHINode &I) { + if (I.getNumIncomingValues() > MaxIncomingPhiValues) + return nullptr; + + bool Inserted = VisitedPHIs.insert(&I).second; + Constant *Const = nullptr; + + for (unsigned Idx = 0, E = I.getNumIncomingValues(); Idx != E; ++Idx) { + Value *V = I.getIncomingValue(Idx); + if (auto *Inst = dyn_cast<Instruction>(V)) + if (Inst == &I || DeadBlocks.contains(I.getIncomingBlock(Idx))) + continue; + Constant *C = findConstantFor(V, KnownConstants); + if (!C) { + if (Inserted) + PendingPHIs.push_back(&I); + return nullptr; + } + if (!Const) + Const = C; + else if (C != Const) + return nullptr; + } + return Const; +} + +Constant *InstCostVisitor::visitFreezeInst(FreezeInst &I) { + assert(LastVisited != KnownConstants.end() && "Invalid iterator!"); + + if (isGuaranteedNotToBeUndefOrPoison(LastVisited->second)) + return LastVisited->second; + return nullptr; +} + +Constant *InstCostVisitor::visitCallBase(CallBase &I) { + Function *F = I.getCalledFunction(); + if (!F || !canConstantFoldCallTo(&I, F)) + return nullptr; + + SmallVector<Constant *, 8> Operands; + Operands.reserve(I.getNumOperands()); + + for (unsigned Idx = 0, E = I.getNumOperands() - 1; Idx != E; ++Idx) { + Value *V = I.getOperand(Idx); + Constant *C = findConstantFor(V, KnownConstants); + if (!C) + return nullptr; + Operands.push_back(C); + } + + auto Ops = ArrayRef(Operands.begin(), Operands.end()); + return ConstantFoldCall(&I, F, Ops); +} + +Constant *InstCostVisitor::visitLoadInst(LoadInst &I) { + assert(LastVisited != KnownConstants.end() && "Invalid iterator!"); + + if (isa<ConstantPointerNull>(LastVisited->second)) + return nullptr; + return ConstantFoldLoadFromConstPtr(LastVisited->second, I.getType(), DL); +} + +Constant *InstCostVisitor::visitGetElementPtrInst(GetElementPtrInst &I) { + SmallVector<Constant *, 8> Operands; + Operands.reserve(I.getNumOperands()); + + for (unsigned Idx = 0, E = I.getNumOperands(); Idx != E; ++Idx) { + Value *V = I.getOperand(Idx); + Constant *C = findConstantFor(V, KnownConstants); + if (!C) + return nullptr; + Operands.push_back(C); + } + + auto Ops = ArrayRef(Operands.begin(), Operands.end()); + return ConstantFoldInstOperands(&I, Ops, DL); +} + +Constant *InstCostVisitor::visitSelectInst(SelectInst &I) { + assert(LastVisited != KnownConstants.end() && "Invalid iterator!"); + + if (I.getCondition() != LastVisited->first) + return nullptr; + + Value *V = LastVisited->second->isZeroValue() ? I.getFalseValue() + : I.getTrueValue(); + Constant *C = findConstantFor(V, KnownConstants); + return C; +} + +Constant *InstCostVisitor::visitCastInst(CastInst &I) { + return ConstantFoldCastOperand(I.getOpcode(), LastVisited->second, + I.getType(), DL); +} + +Constant *InstCostVisitor::visitCmpInst(CmpInst &I) { + assert(LastVisited != KnownConstants.end() && "Invalid iterator!"); + + bool Swap = I.getOperand(1) == LastVisited->first; + Value *V = Swap ? I.getOperand(0) : I.getOperand(1); + Constant *Other = findConstantFor(V, KnownConstants); + if (!Other) + return nullptr; + + Constant *Const = LastVisited->second; + return Swap ? + ConstantFoldCompareInstOperands(I.getPredicate(), Other, Const, DL) + : ConstantFoldCompareInstOperands(I.getPredicate(), Const, Other, DL); +} + +Constant *InstCostVisitor::visitUnaryOperator(UnaryOperator &I) { + assert(LastVisited != KnownConstants.end() && "Invalid iterator!"); + + return ConstantFoldUnaryOpOperand(I.getOpcode(), LastVisited->second, DL); +} + +Constant *InstCostVisitor::visitBinaryOperator(BinaryOperator &I) { + assert(LastVisited != KnownConstants.end() && "Invalid iterator!"); + + bool Swap = I.getOperand(1) == LastVisited->first; + Value *V = Swap ? I.getOperand(0) : I.getOperand(1); + Constant *Other = findConstantFor(V, KnownConstants); + if (!Other) + return nullptr; + + Constant *Const = LastVisited->second; + return dyn_cast_or_null<Constant>(Swap ? + simplifyBinOp(I.getOpcode(), Other, Const, SimplifyQuery(DL)) + : simplifyBinOp(I.getOpcode(), Const, Other, SimplifyQuery(DL))); +} Constant *FunctionSpecializer::getPromotableAlloca(AllocaInst *Alloca, CallInst *Call) { @@ -125,6 +409,10 @@ Constant *FunctionSpecializer::getPromotableAlloca(AllocaInst *Alloca, // Bail if there is any other unknown usage. return nullptr; } + + if (!StoreValue) + return nullptr; + return getCandidateConstant(StoreValue); } @@ -165,49 +453,37 @@ Constant *FunctionSpecializer::getConstantStackValue(CallInst *Call, // ret void // } // -void FunctionSpecializer::promoteConstantStackValues() { - // Iterate over the argument tracked functions see if there - // are any new constant values for the call instruction via - // stack variables. - for (Function &F : M) { - if (!Solver.isArgumentTrackedFunction(&F)) +// 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) { + for (User *U : F->users()) { + + auto *Call = dyn_cast<CallInst>(U); + if (!Call) continue; - for (auto *User : F.users()) { + if (!Solver.isBlockExecutable(Call->getParent())) + continue; - auto *Call = dyn_cast<CallInst>(User); - if (!Call) - continue; + for (const Use &U : Call->args()) { + unsigned Idx = Call->getArgOperandNo(&U); + Value *ArgOp = Call->getArgOperand(Idx); + Type *ArgOpType = ArgOp->getType(); - if (!Solver.isBlockExecutable(Call->getParent())) + if (!Call->onlyReadsMemory(Idx) || !ArgOpType->isPointerTy()) continue; - bool Changed = false; - for (const Use &U : Call->args()) { - unsigned Idx = Call->getArgOperandNo(&U); - Value *ArgOp = Call->getArgOperand(Idx); - Type *ArgOpType = ArgOp->getType(); - - if (!Call->onlyReadsMemory(Idx) || !ArgOpType->isPointerTy()) - continue; - - auto *ConstVal = getConstantStackValue(Call, ArgOp); - if (!ConstVal) - continue; - - Value *GV = new GlobalVariable(M, ConstVal->getType(), true, - GlobalValue::InternalLinkage, ConstVal, - "funcspec.arg"); - if (ArgOpType != ConstVal->getType()) - GV = ConstantExpr::getBitCast(cast<Constant>(GV), ArgOpType); + auto *ConstVal = getConstantStackValue(Call, ArgOp); + if (!ConstVal) + continue; - Call->setArgOperand(Idx, GV); - Changed = true; - } + Value *GV = new GlobalVariable(M, ConstVal->getType(), true, + GlobalValue::InternalLinkage, ConstVal, + "funcspec.arg"); + if (ArgOpType != ConstVal->getType()) + GV = ConstantExpr::getBitCast(cast<Constant>(GV), ArgOpType); - // Add the changed CallInst to Solver Worklist - if (Changed) - Solver.visitCall(*Call); + Call->setArgOperand(Idx, GV); } } } @@ -230,7 +506,7 @@ static void removeSSACopy(Function &F) { /// Remove any ssa_copy intrinsics that may have been introduced. void FunctionSpecializer::cleanUpSSA() { - for (Function *F : SpecializedFuncs) + for (Function *F : Specializations) removeSSACopy(*F); } @@ -249,6 +525,16 @@ template <> struct llvm::DenseMapInfo<SpecSig> { } }; +FunctionSpecializer::~FunctionSpecializer() { + LLVM_DEBUG( + if (NumSpecsCreated > 0) + dbgs() << "FnSpecialization: Created " << NumSpecsCreated + << " specializations in module " << M.getName() << "\n"); + // Eliminate dead code. + removeDeadFunctions(); + cleanUpSSA(); +} + /// Attempt to specialize functions in the module to enable constant /// propagation across function boundaries. /// @@ -262,17 +548,37 @@ bool FunctionSpecializer::run() { if (!isCandidateFunction(&F)) continue; - auto Cost = getSpecializationCost(&F); - if (!Cost.isValid()) { - LLVM_DEBUG(dbgs() << "FnSpecialization: Invalid specialization cost for " - << F.getName() << "\n"); - continue; + auto [It, Inserted] = FunctionMetrics.try_emplace(&F); + CodeMetrics &Metrics = It->second; + //Analyze the function. + if (Inserted) { + SmallPtrSet<const Value *, 32> EphValues; + CodeMetrics::collectEphemeralValues(&F, &GetAC(F), EphValues); + for (BasicBlock &BB : F) + Metrics.analyzeBasicBlock(&BB, GetTTI(F), EphValues); } + // If the code metrics reveal that we shouldn't duplicate the function, + // or if the code size implies that this function is easy to get inlined, + // then we shouldn't specialize it. + if (Metrics.notDuplicatable || !Metrics.NumInsts.isValid() || + (!ForceSpecialization && !F.hasFnAttribute(Attribute::NoInline) && + Metrics.NumInsts < MinFunctionSize)) + continue; + + // TODO: For now only consider recursive functions when running multiple + // times. This should change if specialization on literal constants gets + // enabled. + if (!Inserted && !Metrics.isRecursive && !SpecializeLiteralConstant) + continue; + LLVM_DEBUG(dbgs() << "FnSpecialization: Specialization cost for " - << F.getName() << " is " << Cost << "\n"); + << F.getName() << " is " << Metrics.NumInsts << "\n"); + + if (Inserted && Metrics.isRecursive) + promoteConstantStackValues(&F); - if (!findSpecializations(&F, Cost, AllSpecs, SM)) { + if (!findSpecializations(&F, Metrics.NumInsts, AllSpecs, SM)) { LLVM_DEBUG( dbgs() << "FnSpecialization: No possible specializations found for " << F.getName() << "\n"); @@ -292,11 +598,11 @@ bool FunctionSpecializer::run() { // Choose the most profitable specialisations, which fit in the module // specialization budget, which is derived from maximum number of // specializations per specialization candidate function. - auto CompareGain = [&AllSpecs](unsigned I, unsigned J) { - return AllSpecs[I].Gain > AllSpecs[J].Gain; + auto CompareScore = [&AllSpecs](unsigned I, unsigned J) { + return AllSpecs[I].Score > AllSpecs[J].Score; }; const unsigned NSpecs = - std::min(NumCandidates * MaxClonesThreshold, unsigned(AllSpecs.size())); + std::min(NumCandidates * MaxClones, unsigned(AllSpecs.size())); SmallVector<unsigned> BestSpecs(NSpecs + 1); std::iota(BestSpecs.begin(), BestSpecs.begin() + NSpecs, 0); if (AllSpecs.size() > NSpecs) { @@ -305,11 +611,11 @@ bool FunctionSpecializer::run() { << "FnSpecialization: Specializing the " << NSpecs << " most profitable candidates.\n"); - std::make_heap(BestSpecs.begin(), BestSpecs.begin() + NSpecs, CompareGain); + std::make_heap(BestSpecs.begin(), BestSpecs.begin() + NSpecs, CompareScore); for (unsigned I = NSpecs, N = AllSpecs.size(); I < N; ++I) { BestSpecs[NSpecs] = I; - std::push_heap(BestSpecs.begin(), BestSpecs.end(), CompareGain); - std::pop_heap(BestSpecs.begin(), BestSpecs.end(), CompareGain); + std::push_heap(BestSpecs.begin(), BestSpecs.end(), CompareScore); + std::pop_heap(BestSpecs.begin(), BestSpecs.end(), CompareScore); } } @@ -317,7 +623,7 @@ bool FunctionSpecializer::run() { for (unsigned I = 0; I < NSpecs; ++I) { const Spec &S = AllSpecs[BestSpecs[I]]; dbgs() << "FnSpecialization: Function " << S.F->getName() - << " , gain " << S.Gain << "\n"; + << " , score " << S.Score << "\n"; for (const ArgInfo &Arg : S.Sig.Args) dbgs() << "FnSpecialization: FormalArg = " << Arg.Formal->getNameOrAsOperand() @@ -353,12 +659,37 @@ bool FunctionSpecializer::run() { updateCallSites(F, AllSpecs.begin() + Begin, AllSpecs.begin() + End); } - promoteConstantStackValues(); - LLVM_DEBUG(if (NbFunctionsSpecialized) dbgs() - << "FnSpecialization: Specialized " << NbFunctionsSpecialized - << " functions in module " << M.getName() << "\n"); + for (Function *F : Clones) { + if (F->getReturnType()->isVoidTy()) + continue; + if (F->getReturnType()->isStructTy()) { + auto *STy = cast<StructType>(F->getReturnType()); + if (!Solver.isStructLatticeConstant(F, STy)) + continue; + } else { + auto It = Solver.getTrackedRetVals().find(F); + assert(It != Solver.getTrackedRetVals().end() && + "Return value ought to be tracked"); + if (SCCPSolver::isOverdefined(It->second)) + continue; + } + for (User *U : F->users()) { + if (auto *CS = dyn_cast<CallBase>(U)) { + //The user instruction does not call our function. + if (CS->getCalledFunction() != F) + continue; + Solver.resetLatticeValueFor(CS); + } + } + } + + // Rerun the solver to notify the users of the modified callsites. + Solver.solveWhileResolvedUndefs(); + + for (Function *F : OriginalFuncs) + if (FunctionMetrics[F].isRecursive) + promoteConstantStackValues(F); - NumFuncSpecialized += NbFunctionsSpecialized; return true; } @@ -373,24 +704,6 @@ void FunctionSpecializer::removeDeadFunctions() { FullySpecialized.clear(); } -// Compute the code metrics for function \p F. -CodeMetrics &FunctionSpecializer::analyzeFunction(Function *F) { - auto I = FunctionMetrics.insert({F, CodeMetrics()}); - CodeMetrics &Metrics = I.first->second; - if (I.second) { - // The code metrics were not cached. - SmallPtrSet<const Value *, 32> EphValues; - CodeMetrics::collectEphemeralValues(F, &(GetAC)(*F), EphValues); - for (BasicBlock &BB : *F) - Metrics.analyzeBasicBlock(&BB, (GetTTI)(*F), EphValues); - - LLVM_DEBUG(dbgs() << "FnSpecialization: Code size of function " - << F->getName() << " is " << Metrics.NumInsts - << " instructions\n"); - } - return Metrics; -} - /// Clone the function \p F and remove the ssa_copy intrinsics added by /// the SCCPSolver in the cloned version. static Function *cloneCandidateFunction(Function *F) { @@ -400,13 +713,13 @@ static Function *cloneCandidateFunction(Function *F) { return Clone; } -bool FunctionSpecializer::findSpecializations(Function *F, InstructionCost Cost, +bool FunctionSpecializer::findSpecializations(Function *F, Cost SpecCost, SmallVectorImpl<Spec> &AllSpecs, SpecMap &SM) { // A mapping from a specialisation signature to the index of the respective // entry in the all specialisation array. Used to ensure uniqueness of // specialisations. - DenseMap<SpecSig, unsigned> UM; + DenseMap<SpecSig, unsigned> UniqueSpecs; // Get a list of interesting arguments. SmallVector<Argument *> Args; @@ -417,7 +730,6 @@ bool FunctionSpecializer::findSpecializations(Function *F, InstructionCost Cost, if (Args.empty()) return false; - bool Found = false; for (User *U : F->users()) { if (!isa<CallInst>(U) && !isa<InvokeInst>(U)) continue; @@ -454,7 +766,7 @@ bool FunctionSpecializer::findSpecializations(Function *F, InstructionCost Cost, continue; // Check if we have encountered the same specialisation already. - if (auto It = UM.find(S); It != UM.end()) { + if (auto It = UniqueSpecs.find(S); It != UniqueSpecs.end()) { // Existing specialisation. Add the call to the list to rewrite, unless // it's a recursive call. A specialisation, generated because of a // recursive call may end up as not the best specialisation for all @@ -467,42 +779,42 @@ bool FunctionSpecializer::findSpecializations(Function *F, InstructionCost Cost, AllSpecs[Index].CallSites.push_back(&CS); } else { // Calculate the specialisation gain. - InstructionCost Gain = 0 - Cost; + Cost Score = 0; + InstCostVisitor Visitor = getInstCostVisitorFor(F); for (ArgInfo &A : S.Args) - Gain += - getSpecializationBonus(A.Formal, A.Actual, Solver.getLoopInfo(*F)); + Score += getSpecializationBonus(A.Formal, A.Actual, Visitor); + Score += Visitor.getBonusFromPendingPHIs(); + + LLVM_DEBUG(dbgs() << "FnSpecialization: Specialization score = " + << Score << "\n"); // Discard unprofitable specialisations. - if (!ForceFunctionSpecialization && Gain <= 0) + if (!ForceSpecialization && Score <= SpecCost) continue; // Create a new specialisation entry. - auto &Spec = AllSpecs.emplace_back(F, S, Gain); + auto &Spec = AllSpecs.emplace_back(F, S, Score); if (CS.getFunction() != F) Spec.CallSites.push_back(&CS); const unsigned Index = AllSpecs.size() - 1; - UM[S] = Index; + UniqueSpecs[S] = Index; if (auto [It, Inserted] = SM.try_emplace(F, Index, Index + 1); !Inserted) It->second.second = Index + 1; - Found = true; } } - return Found; + return !UniqueSpecs.empty(); } bool FunctionSpecializer::isCandidateFunction(Function *F) { - if (F->isDeclaration()) + if (F->isDeclaration() || F->arg_empty()) return false; if (F->hasFnAttribute(Attribute::NoDuplicate)) return false; - if (!Solver.isArgumentTrackedFunction(F)) - return false; - // Do not specialize the cloned function again. - if (SpecializedFuncs.contains(F)) + if (Specializations.contains(F)) return false; // If we're optimizing the function for size, we shouldn't specialize it. @@ -524,86 +836,50 @@ bool FunctionSpecializer::isCandidateFunction(Function *F) { return true; } -Function *FunctionSpecializer::createSpecialization(Function *F, const SpecSig &S) { +Function *FunctionSpecializer::createSpecialization(Function *F, + const SpecSig &S) { Function *Clone = cloneCandidateFunction(F); + // The original function does not neccessarily have internal linkage, but the + // clone must. + Clone->setLinkage(GlobalValue::InternalLinkage); + // Initialize the lattice state of the arguments of the function clone, // marking the argument on which we specialized the function constant // with the given value. - Solver.markArgInFuncSpecialization(Clone, S.Args); - - Solver.addArgumentTrackedFunction(Clone); + Solver.setLatticeValueForSpecializationArguments(Clone, S.Args); Solver.markBlockExecutable(&Clone->front()); + Solver.addArgumentTrackedFunction(Clone); + Solver.addTrackedFunction(Clone); // Mark all the specialized functions - SpecializedFuncs.insert(Clone); - NbFunctionsSpecialized++; + Specializations.insert(Clone); + ++NumSpecsCreated; return Clone; } -/// Compute and return the cost of specializing function \p F. -InstructionCost FunctionSpecializer::getSpecializationCost(Function *F) { - CodeMetrics &Metrics = analyzeFunction(F); - // If the code metrics reveal that we shouldn't duplicate the function, we - // shouldn't specialize it. Set the specialization cost to Invalid. - // Or if the lines of codes implies that this function is easy to get - // inlined so that we shouldn't specialize it. - if (Metrics.notDuplicatable || !Metrics.NumInsts.isValid() || - (!ForceFunctionSpecialization && - !F->hasFnAttribute(Attribute::NoInline) && - Metrics.NumInsts < SmallFunctionThreshold)) - return InstructionCost::getInvalid(); - - // Otherwise, set the specialization cost to be the cost of all the - // instructions in the function. - return Metrics.NumInsts * InlineConstants::getInstrCost(); -} - -static InstructionCost getUserBonus(User *U, llvm::TargetTransformInfo &TTI, - const LoopInfo &LI) { - auto *I = dyn_cast_or_null<Instruction>(U); - // If not an instruction we do not know how to evaluate. - // Keep minimum possible cost for now so that it doesnt affect - // specialization. - if (!I) - return std::numeric_limits<unsigned>::min(); - - InstructionCost Cost = - TTI.getInstructionCost(U, TargetTransformInfo::TCK_SizeAndLatency); - - // Increase the cost if it is inside the loop. - unsigned LoopDepth = LI.getLoopDepth(I->getParent()); - Cost *= std::pow((double)AvgLoopIterationCount, LoopDepth); - - // Traverse recursively if there are more uses. - // TODO: Any other instructions to be added here? - if (I->mayReadFromMemory() || I->isCast()) - for (auto *User : I->users()) - Cost += getUserBonus(User, TTI, LI); - - return Cost; -} - /// Compute a bonus for replacing argument \p A with constant \p C. -InstructionCost -FunctionSpecializer::getSpecializationBonus(Argument *A, Constant *C, - const LoopInfo &LI) { - Function *F = A->getParent(); - auto &TTI = (GetTTI)(*F); +Cost FunctionSpecializer::getSpecializationBonus(Argument *A, Constant *C, + InstCostVisitor &Visitor) { LLVM_DEBUG(dbgs() << "FnSpecialization: Analysing bonus for constant: " << C->getNameOrAsOperand() << "\n"); - InstructionCost TotalCost = 0; - for (auto *U : A->users()) { - TotalCost += getUserBonus(U, TTI, LI); - LLVM_DEBUG(dbgs() << "FnSpecialization: User cost "; - TotalCost.print(dbgs()); dbgs() << " for: " << *U << "\n"); - } + Cost TotalCost = 0; + for (auto *U : A->users()) + if (auto *UI = dyn_cast<Instruction>(U)) + if (Solver.isBlockExecutable(UI->getParent())) + TotalCost += Visitor.getUserBonus(UI, A, C); + + LLVM_DEBUG(dbgs() << "FnSpecialization: Accumulated user bonus " + << TotalCost << " for argument " << *A << "\n"); // 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. + // + // TODO: Perhaps we should consider checking such inlining opportunities + // while traversing the users of the specialization arguments ? Function *CalledFunction = dyn_cast<Function>(C->stripPointerCasts()); if (!CalledFunction) return TotalCost; @@ -661,16 +937,9 @@ bool FunctionSpecializer::isArgumentInteresting(Argument *A) { if (A->user_empty()) return false; - // For now, don't attempt to specialize functions based on the values of - // composite types. - Type *ArgTy = A->getType(); - if (!ArgTy->isSingleValueType()) - return false; - - // Specialization of integer and floating point types needs to be explicitly - // enabled. - if (!EnableSpecializationForLiteralConstant && - (ArgTy->isIntegerTy() || ArgTy->isFloatingPointTy())) + Type *Ty = A->getType(); + if (!Ty->isPointerTy() && (!SpecializeLiteralConstant || + (!Ty->isIntegerTy() && !Ty->isFloatingPointTy() && !Ty->isStructTy()))) return false; // SCCP solver does not record an argument that will be constructed on @@ -678,54 +947,46 @@ bool FunctionSpecializer::isArgumentInteresting(Argument *A) { if (A->hasByValAttr() && !A->getParent()->onlyReadsMemory()) return false; + // For non-argument-tracked functions every argument is overdefined. + if (!Solver.isArgumentTrackedFunction(A->getParent())) + return true; + // Check the lattice value and decide if we should attemt to specialize, // based on this argument. No point in specialization, if the lattice value // is already a constant. - const ValueLatticeElement &LV = Solver.getLatticeValueFor(A); - if (LV.isUnknownOrUndef() || LV.isConstant() || - (LV.isConstantRange() && LV.getConstantRange().isSingleElement())) { - LLVM_DEBUG(dbgs() << "FnSpecialization: Nothing to do, parameter " - << A->getNameOrAsOperand() << " is already constant\n"); - return false; - } - - LLVM_DEBUG(dbgs() << "FnSpecialization: Found interesting parameter " - << A->getNameOrAsOperand() << "\n"); - - return true; + bool IsOverdefined = Ty->isStructTy() + ? any_of(Solver.getStructLatticeValueFor(A), SCCPSolver::isOverdefined) + : SCCPSolver::isOverdefined(Solver.getLatticeValueFor(A)); + + LLVM_DEBUG( + if (IsOverdefined) + dbgs() << "FnSpecialization: Found interesting parameter " + << A->getNameOrAsOperand() << "\n"; + else + dbgs() << "FnSpecialization: Nothing to do, parameter " + << A->getNameOrAsOperand() << " is already constant\n"; + ); + return IsOverdefined; } -/// Check if the valuy \p V (an actual argument) is a constant or can only +/// 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) { if (isa<PoisonValue>(V)) return nullptr; - // TrackValueOfGlobalVariable only tracks scalar global variables. - if (auto *GV = dyn_cast<GlobalVariable>(V)) { - // Check if we want to specialize on the address of non-constant - // global values. - if (!GV->isConstant() && !SpecializeOnAddresses) - return nullptr; - - if (!GV->getValueType()->isSingleValueType()) - return nullptr; - } - // Select for possible specialisation values that are constants or // are deduced to be constants or constant ranges with a single element. Constant *C = dyn_cast<Constant>(V); - if (!C) { - const ValueLatticeElement &LV = Solver.getLatticeValueFor(V); - if (LV.isConstant()) - C = LV.getConstant(); - else if (LV.isConstantRange() && LV.getConstantRange().isSingleElement()) { - assert(V->getType()->isIntegerTy() && "Non-integral constant range"); - C = Constant::getIntegerValue(V->getType(), - *LV.getConstantRange().getSingleElement()); - } else + if (!C) + C = Solver.getConstantOrNull(V); + + // Don't specialize on (anything derived from) the address of a non-constant + // global variable, unless explicitly enabled. + if (C && C->getType()->isPointerTy() && !C->isNullValue()) + if (auto *GV = dyn_cast<GlobalVariable>(getUnderlyingObject(C)); + GV && !(GV->isConstant() || SpecializeOnAddress)) return nullptr; - } return C; } @@ -747,7 +1008,7 @@ void FunctionSpecializer::updateCallSites(Function *F, const Spec *Begin, // Find the best matching specialisation. const Spec *BestSpec = nullptr; for (const Spec &S : make_range(Begin, End)) { - if (!S.Clone || (BestSpec && S.Gain <= BestSpec->Gain)) + if (!S.Clone || (BestSpec && S.Score <= BestSpec->Score)) continue; if (any_of(S.Sig.Args, [CS, this](const ArgInfo &Arg) { @@ -772,7 +1033,7 @@ void FunctionSpecializer::updateCallSites(Function *F, const Spec *Begin, // If the function has been completely specialized, the original function // is no longer needed. Mark it unreachable. - if (NCallsLeft == 0) { + if (NCallsLeft == 0 && Solver.isArgumentTrackedFunction(F)) { Solver.markFunctionUnreachable(F); FullySpecialized.insert(F); } |