diff --git a/llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h b/llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h --- a/llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h +++ b/llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h @@ -176,8 +176,7 @@ return Solver.isBlockExecutable(BB) && !DeadBlocks.contains(BB); } - Bonus getUserBonus(Instruction *User, Value *Use = nullptr, - Constant *C = nullptr); + Bonus getSpecializationBonus(Argument *A, Constant *C); Bonus getBonusFromPendingPHIs(); @@ -187,6 +186,9 @@ static bool canEliminateSuccessor(BasicBlock *BB, BasicBlock *Succ, DenseSet &DeadBlocks); + Bonus getUserBonus(Instruction *User, Value *Use = nullptr, + Constant *C = nullptr); + Cost estimateBasicBlocks(SmallVectorImpl &WorkList); Cost estimateSwitchInst(SwitchInst &I); Cost estimateBranchInst(BranchInst &I); @@ -244,10 +246,6 @@ return InstCostVisitor(M.getDataLayout(), BFI, TTI, Solver); } - /// Compute a bonus for replacing argument \p A with constant \p C. - Bonus getSpecializationBonus(Argument *A, Constant *C, - InstCostVisitor &Visitor); - private: Constant *getPromotableAlloca(AllocaInst *Alloca, CallInst *Call); @@ -268,14 +266,16 @@ /// @brief Find potential specialization opportunities. /// @param F Function to specialize - /// @param SpecCost Cost of specializing a function. Final score is benefit - /// minus this cost. + /// @param FuncSize Cost of specializing a function. /// @param AllSpecs A vector to add potential specializations to. /// @param SM A map for a function's specialisation range /// @return True, if any potential specializations were found - bool findSpecializations(Function *F, unsigned SpecCost, + bool findSpecializations(Function *F, unsigned FuncSize, SmallVectorImpl &AllSpecs, SpecMap &SM); + /// Compute the inlining bonus for replacing argument \p A with constant \p C. + unsigned getInliningBonus(Argument *A, Constant *C); + bool isCandidateFunction(Function *F); /// @brief Create a specialization of \p F and prime the SCCPSolver diff --git a/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp b/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp --- a/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp +++ b/llvm/lib/Transforms/IPO/FunctionSpecialization.cpp @@ -89,10 +89,25 @@ "considered during the estimation of dead code")); static cl::opt MinFunctionSize( - "funcspec-min-function-size", cl::init(100), cl::Hidden, cl::desc( + "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 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 MinLatencySavings( + "funcspec-min-latency-savings", cl::init(70), cl::Hidden, cl::desc( + "Reject specializations whose latency savings are less than this" + "much percent of the original function size")); + +static cl::opt 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 SpecializeOnAddress( "funcspec-on-address", cl::init(false), cl::Hidden, cl::desc( "Enable function specialization on the address of global values")); @@ -180,6 +195,22 @@ return B; } +/// Compute a bonus for replacing argument \p A with constant \p C. +Bonus InstCostVisitor::getSpecializationBonus(Argument *A, Constant *C) { + LLVM_DEBUG(dbgs() << "FnSpecialization: Analysing bonus for constant: " + << C->getNameOrAsOperand() << "\n"); + Bonus B; + for (auto *U : A->users()) + if (auto *UI = dyn_cast(U)) + if (isBlockExecutable(UI->getParent())) + B += getUserBonus(UI, A, C); + + LLVM_DEBUG(dbgs() << "FnSpecialization: Accumulated bonus {CodeSize = " + << B.CodeSize << ", Latency = " << B.Latency + << "} for argument " << *A << "\n"); + return B; +} + Bonus InstCostVisitor::getUserBonus(Instruction *User, Value *Use, Constant *C) { // We have already propagated a constant for this user. if (KnownConstants.contains(User)) @@ -589,15 +620,15 @@ int64_t Sz = *Metrics.NumInsts.getValue(); assert(Sz > 0 && "CodeSize should be positive"); // It is safe to down cast from int64_t, NumInsts is always positive. - unsigned SpecCost = static_cast(Sz); + unsigned FuncSize = static_cast(Sz); LLVM_DEBUG(dbgs() << "FnSpecialization: Specialization cost for " - << F.getName() << " is " << SpecCost << "\n"); + << F.getName() << " is " << FuncSize << "\n"); if (Inserted && Metrics.isRecursive) promoteConstantStackValues(&F); - if (!findSpecializations(&F, SpecCost, AllSpecs, SM)) { + if (!findSpecializations(&F, FuncSize, AllSpecs, SM)) { LLVM_DEBUG( dbgs() << "FnSpecialization: No possible specializations found for " << F.getName() << "\n"); @@ -732,7 +763,7 @@ return Clone; } -bool FunctionSpecializer::findSpecializations(Function *F, unsigned SpecCost, +bool FunctionSpecializer::findSpecializations(Function *F, unsigned FuncSize, SmallVectorImpl &AllSpecs, SpecMap &SM) { // A mapping from a specialisation signature to the index of the respective @@ -799,21 +830,42 @@ } else { // Calculate the specialisation gain. Bonus B; + unsigned Score = 0; InstCostVisitor Visitor = getInstCostVisitorFor(F); - for (ArgInfo &A : S.Args) - B += getSpecializationBonus(A.Formal, A.Actual, Visitor); + for (ArgInfo &A : S.Args) { + B += Visitor.getSpecializationBonus(A.Formal, A.Actual); + Score += getInliningBonus(A.Formal, A.Actual); + } B += Visitor.getBonusFromPendingPHIs(); - LLVM_DEBUG(dbgs() << "FnSpecialization: Specialization score {CodeSize = " + + LLVM_DEBUG(dbgs() << "FnSpecialization: Specialization bonus {CodeSize = " << B.CodeSize << ", Latency = " << B.Latency - << "}\n"); + << ", Inlining = " << Score << "}\n"); + + auto IsProfitable = [&FuncSize](Bonus &B, unsigned Score) -> bool { + // No check required. + if (ForceSpecialization) + return true; + // Minimum inlining bonus. + if (Score > MinInliningBonus * FuncSize / 100) + return true; + // Minimum codesize savings. + if (B.CodeSize < MinCodeSizeSavings * FuncSize / 100) + return false; + // Minimum latency savings. + if (B.Latency < MinLatencySavings * FuncSize / 100) + return false; + return true; + }; // Discard unprofitable specialisations. - if (!ForceSpecialization && B.Latency <= SpecCost - B.CodeSize) + if (!IsProfitable(B, Score)) continue; // Create a new specialisation entry. - auto &Spec = AllSpecs.emplace_back(F, S, B.Latency); + Score += std::max(B.CodeSize, B.Latency); + auto &Spec = AllSpecs.emplace_back(F, S, Score); if (CS.getFunction() != F) Spec.CallSites.push_back(&CS); const unsigned Index = AllSpecs.size() - 1; @@ -879,31 +931,14 @@ return Clone; } -/// Compute a bonus for replacing argument \p A with constant \p C. -Bonus FunctionSpecializer::getSpecializationBonus(Argument *A, Constant *C, - InstCostVisitor &Visitor) { - LLVM_DEBUG(dbgs() << "FnSpecialization: Analysing bonus for constant: " - << C->getNameOrAsOperand() << "\n"); - - Bonus B; - for (auto *U : A->users()) - if (auto *UI = dyn_cast(U)) - if (Visitor.isBlockExecutable(UI->getParent())) - B += Visitor.getUserBonus(UI, A, C); - - LLVM_DEBUG(dbgs() << "FnSpecialization: Accumulated bonus {CodeSize = " - << B.CodeSize << ", Latency = " << B.Latency - << "} 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 ? +/// 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) { Function *CalledFunction = dyn_cast(C->stripPointerCasts()); if (!CalledFunction) - return B; + return 0; // Get TTI for the called function (used for the inline cost). auto &CalleeTTI = (GetTTI)(*CalledFunction); @@ -948,7 +983,7 @@ << " for user " << *U << "\n"); } - return B += {0, InliningBonus}; + return InliningBonus > 0 ? static_cast(InliningBonus) : 0; } /// Determine if it is possible to specialise the function for constant values diff --git a/llvm/unittests/Transforms/IPO/FunctionSpecializationTest.cpp b/llvm/unittests/Transforms/IPO/FunctionSpecializationTest.cpp --- a/llvm/unittests/Transforms/IPO/FunctionSpecializationTest.cpp +++ b/llvm/unittests/Transforms/IPO/FunctionSpecializationTest.cpp @@ -168,13 +168,13 @@ // mul Bonus Ref = getInstCost(Mul); - Bonus Test = Specializer.getSpecializationBonus(F->getArg(0), One, Visitor); + Bonus Test = Visitor.getSpecializationBonus(F->getArg(0), One); EXPECT_EQ(Test, Ref); EXPECT_TRUE(Test.CodeSize > 0 && Test.Latency > 0); // and + or + add Ref = getInstCost(And) + getInstCost(Or) + getInstCost(Add); - Test = Specializer.getSpecializationBonus(F->getArg(1), One, Visitor); + Test = Visitor.getSpecializationBonus(F->getArg(1), One); EXPECT_EQ(Test, Ref); EXPECT_TRUE(Test.CodeSize > 0 && Test.Latency > 0); @@ -183,7 +183,7 @@ getInstCost(Sdiv, /*SizeOnly =*/ true) + getInstCost(BrBB2, /*SizeOnly =*/ true) + getInstCost(BrLoop, /*SizeOnly =*/ true); - Test = Specializer.getSpecializationBonus(F->getArg(2), One, Visitor); + Test = Visitor.getSpecializationBonus(F->getArg(2), One); EXPECT_EQ(Test, Ref); EXPECT_TRUE(Test.CodeSize > 0 && Test.Latency > 0); } @@ -235,13 +235,13 @@ // mul Bonus Ref = getInstCost(Mul); - Bonus Test = Specializer.getSpecializationBonus(F->getArg(0), One, Visitor); + Bonus Test = Visitor.getSpecializationBonus(F->getArg(0), One); EXPECT_EQ(Test, Ref); EXPECT_TRUE(Test.CodeSize > 0 && Test.Latency > 0); // add Ref = getInstCost(Add); - Test = Specializer.getSpecializationBonus(F->getArg(1), One, Visitor); + Test = Visitor.getSpecializationBonus(F->getArg(1), One); EXPECT_EQ(Test, Ref); EXPECT_TRUE(Test.CodeSize > 0 && Test.Latency > 0); @@ -252,7 +252,7 @@ getInstCost(Sdiv, /*SizeOnly =*/ true) + getInstCost(BrBB2, /*SizeOnly =*/ true) + getInstCost(BrLoop, /*SizeOnly =*/ true); - Test = Specializer.getSpecializationBonus(F->getArg(2), False, Visitor); + Test = Visitor.getSpecializationBonus(F->getArg(2), False); EXPECT_EQ(Test, Ref); EXPECT_TRUE(Test.CodeSize > 0 && Test.Latency > 0); } @@ -301,24 +301,24 @@ // icmp + zext Bonus Ref = getInstCost(Icmp) + getInstCost(Zext); - Bonus Test = Specializer.getSpecializationBonus(F->getArg(0), One, Visitor); + Bonus Test = Visitor.getSpecializationBonus(F->getArg(0), One); EXPECT_EQ(Test, Ref); EXPECT_TRUE(Test.CodeSize > 0 && Test.Latency > 0); // select Ref = getInstCost(Select); - Test = Specializer.getSpecializationBonus(F->getArg(1), True, Visitor); + Test = Visitor.getSpecializationBonus(F->getArg(1), True); EXPECT_EQ(Test, Ref); EXPECT_TRUE(Test.CodeSize > 0 && Test.Latency > 0); // gep + load + freeze + smax Ref = getInstCost(Gep) + getInstCost(Load) + getInstCost(Freeze) + getInstCost(Smax); - Test = Specializer.getSpecializationBonus(F->getArg(2), GV, Visitor); + Test = Visitor.getSpecializationBonus(F->getArg(2), GV); EXPECT_EQ(Test, Ref); EXPECT_TRUE(Test.CodeSize > 0 && Test.Latency > 0); - Test = Specializer.getSpecializationBonus(F->getArg(3), Undef, Visitor); + Test = Visitor.getSpecializationBonus(F->getArg(3), Undef); EXPECT_TRUE(Test.CodeSize == 0 && Test.Latency == 0); } @@ -369,17 +369,17 @@ Instruction &Icmp = *++BB.begin(); Instruction &Branch = BB.back(); - Bonus Test = Specializer.getSpecializationBonus(F->getArg(0), One, Visitor); + Bonus Test = Visitor.getSpecializationBonus(F->getArg(0), One); EXPECT_TRUE(Test.CodeSize == 0 && Test.Latency == 0); - Test = Specializer.getSpecializationBonus(F->getArg(1), One, Visitor); + Test = Visitor.getSpecializationBonus(F->getArg(1), One); EXPECT_TRUE(Test.CodeSize == 0 && Test.Latency == 0); // switch + phi + br Bonus Ref = getInstCost(Switch) + getInstCost(PhiCase2, /*SizeOnly =*/ true) + getInstCost(BrBB, /*SizeOnly =*/ true); - Test = Specializer.getSpecializationBonus(F->getArg(2), One, Visitor); + Test = Visitor.getSpecializationBonus(F->getArg(2), One); EXPECT_EQ(Test, Ref); EXPECT_TRUE(Test.CodeSize > 0 && Test.Latency > 0);