[FuncSpec] Cost model improvements.

[labrinea]

Summary

• Separate user bonus to Latency and CodeSize.
• Do not re-count the bonus of a visited user (from other arguments).
• Limit the recursion depth when accumulating user bonus.
• Penalize latency of loop nests the deeper we get in the use-def chain.
• Penalize specialization on the same argument.
• Formulate specialization score based on Latency/CodeSize ratio.

[labrinea]

Old cost model (LTO)

Compilation
FnSpecialization: Specialized 1 functions in module test-suite/CTMark/SPASS/terminator.c
FnSpecialization: Specialized 5 functions in module test-suite/CTMark/ClamAV/libclamav_message.c
FnSpecialization: Specialized 1 functions in module test-suite/CTMark/SPASS/rules-inf.c
FnSpecialization: Specialized 1 functions in module test-suite/CTMark/sqlite3/sqlite3.c

Linking
FnSpecialization: Specialized 1 functions in module ld-temp.o (ClamAV)
FnSpecialization: Specialized 1 functions in module ld-temp.o (sqlite3)
FnSpecialization: Specialized 3 functions in module ld-temp.o (lencod)

New cost model (LTO)

Compilation
FnSpecialization: Created 1 specializations in module test-suite/CTMark/ClamAV/libclamav_message.c

Linking
FnSpecialization: Created 2 specializations in module ld-temp.o (ClamAV)
FnSpecialization: Created 2 specializations in module ld-temp.o (sqlite3)
FnSpecialization: Created 3 specializations in module ld-temp.o (lencod)

Instruction Count % delta

ClamAV	+0.381
7zip	-0.012
tramp3d-v4	-0.007
kimwitu++	+0.097
sqlite3	+0.170
mafft	+0.026
lencod	-0.054
SPASS	-0.673
consumer-typeset	+0.054
Bullet	-0.012
geomean	-0.003

(The specializations happening at link time seem to be affecting the total compilation time a lot more than those happening pre-link time).

[labrinea]

llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h

140–141

Oops, forgot to remove it from here

[labrinea]

Changes from last revision:

• Removed redefinition of SpecMap type from the header file.
• Removed @param Cost from the description of findSpecializations() in the header file.
• Decreased the value of MinScore from 100 to 80 as it no longer specialized mcf_r from SPEC2017.

[labrinea]

Adjusted the test output for recursive-penalty.ll. Decreasing MinScore from 100 to 80 translates to 10 instead of 8 specializations being created for the test.

[SjoerdMeijer]

I am wondering if you're trying to do too much in this patch. But I only had a quick look at this, and need to look again.
But my first request is going to be about the cost/bonus calculation. Since this is crucial for this transformation, it would be useful to document and comment the idea/algorithm at some place, with all the formulas and definitions (costs, bonus, latency, code size etc). I think this would greatly improve readability of these changes and the code in general.

[labrinea]

Added a description of the cost model in the header file.

[SjoerdMeijer]

llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h

51

Thanks for adding these descriptions, that is very helpful.

Just trying to understand the initial code size calculation better, the last part:

[number of inline candidates] x [small function size]

why is that not the [number of instructions] for each inline candidate?

[SjoerdMeijer]

llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h

88

It's not clear to me what this range exactly is.

90

Nit: perhaps consider a more informative name for this.

92

Nit: abreviation -> abbreviation
and you can drop shorter, or the comment entirely, up to you.

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

396

Nit: UM is a bit cryptic.

[labrinea]

llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h

51

Because this information is not available in CodeMetrics. We don't know who that inline candidate is at this point, and if we did we would have to compute it's CodeMetrics. So instead we use mall function size as an approximation. Knowing the exact number of instructions does not matter that much. What matters is to increase the codesize hit if there are inline candidates, meaning the entire function might end up even larger than it is now.

88

This typdef is unrelated to this patch, I just grouped all the typedef here. Just ignore it.

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

396

UniqueMap. Was already named as such before this patch, so unrelated. Please ignore on this review.

[SjoerdMeijer]

llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h

51

Thanks, if you can add this explanation to the comments that would help.

88

Okay, so it lived somewhere else before and you just moved it here, but can you explain what the range is while we are at it?

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

396

Naming is difficult, but it would be a shame if we cannot come up with something better while we are at it.

543–544

Bit of duplication here with the comment above.

567–568

We are not calculating one bonus anymore, but two values latency and code size.

588

I don't quite get why we are subtracting UserSize here. I guess something related to double or recounting, but after a quick look it wasn't clear to me, perhaps a comment would be helpful here.

llvm/test/Transforms/FunctionSpecialization/recursive-penalty.ll

10

Do we want to check the resulting IR too?

[chill]

llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h

88

Isn't that clear from the comment above?

We have a vector of specializations. In this vector the specializations of any one function are adjacent to one another, IOW "form a contiguous range".
For example, if specializations of foo are at indices 4, 5, 6, 7 in the vector, we keep just 4 and 8,
to save space. The range is [4, 8).

A somewhat longer description of the data structures is given in the commit message: in https://reviews.llvm.org/rGe6b9fc4c8be00660c5e1f1605a6a5d92475bdba7

[SjoerdMeijer]

llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h

88

Isn't that clear from the comment above?

No, sorry, it wasn't for me. This however, is crystal clear to me:

We have a vector of specializations. In this vector the specializations of any one function are adjacent to one another, IOW "form a contiguous range". For example, if specializations of foo are at indices 4, 5, 6, 7 in the vector, we keep just 4 and 8, to save space. The range is [4, 8).

As it also answers my follow up question, i.e. what is the relevance/rationale of this. I think exactly this should be part of the comment/explanation here.

A somewhat longer description of the data structures is given in the commit message: in https://reviews.llvm.org/rGe6b9fc4c8be00660c5e1f1605a6a5d92475bdba7

So I missed that review, i.e. didn't have time to look into it, but am now dipping back into FuncSpec, which is why I am missing some rationale. But I think this is an excellent write-up, that should be, or parts of it, should be part of the write up to make this self contained (i.e. it's a bit of a missed opportunity this explanation is only in the commit message).

[labrinea]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

543–544

Good point, I forgot to remove these comments.

567–568

Will update the wording.

588

We start from Cost CodeSize = Metrics.NumInsts + Metrics.NumInlineCandidates * MinFunctionSize; (see the invocation of getSpecializationBonus). Then we start decreasing it by the footprint of each user.

llvm/test/Transforms/FunctionSpecialization/recursive-penalty.ll

10

Not really. All we care about in this test is to show that the number of specializations created is not linear to funcspec-max-iters.

[labrinea]

llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h

51

Will do.

88

I disagree with repeating the write-up in a comment as it may become irrelevant at some point. I think git blame should suffice. I find the existing comment already quite extensive/informative.

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

396

Agreed. I'll update it.

[SjoerdMeijer]

Cheers, LGTM

[labrinea]

I am having second thoughts about this change. I will merge the trivial NFC changes (variable renaming, type aliasing) and will raise new tickets for the remaining parts. So abandoning the cost model improvements for now.

llvm/include/llvm/Transforms/IPO/FunctionSpecialization.h

 //
 // Ideas:
 // - With a function specialization attribute for arguments, we could have
 //   a direct way to steer function specialization, avoiding the cost-model,
 //   and thus control compile-times / code-size.
 //
 // Todos:
 // - Specializing recursive functions relies on running the transformation a
-//   number of times, which is controlled by option
-//   `func-specialization-max-iters`. Thus, increasing this value and the
-//   number of iterations, will linearly increase the number of times recursive
-//   functions get specialized, see also the discussion in
-//   https://reviews.llvm.org/D106426 for details. Perhaps there is a
-//   compile-time friendlier way to control/limit the number of specialisations
-//   for recursive functions.
-// - Don't transform the function if function specialization does not trigger;
-//   the SCCPSolver may make IR changes.
+//   number of times, which is controlled by the option `funcspec-max-iters`.
+//   Perhaps there is a compile-time friendlier way for such specializations.
+//   (see also the discussion in https://reviews.llvm.org/D106426 for details)
+//
+// Cost Model:
+// -----------
+// To determine whether a specialization is profitable, we compute its score as
+// the ratio of latency savings over codesize increase. The score must exceed
+// a minimum threshold, which is controlled by the option `funcspec-min-score`.
+//
+// To compute the latency savings attributed to each of the constant arguments,
+// we traverse the use-def chain (ignoring ssa copies) up to a maximum depth
+// controlled by the option `funcspec-max-user-depth`. The latency of a user is
+// exponentiated if inside a loop nest, but the deeper in the use-def chain we
+// are the less the latency is "worth". The average loop iteration count is
+// controlled by the option `funcspec-avg-loop-iters`. Inlining benefits are
+// estimated as part of the latency savings.
+//
+// To compute the codesize increase, we first estimate the initial codesize of
+// the function as [number of instructions] + [number of inline candidates] x
+// [small function size] since the exact number of instructions per inline
+// candidate is unknown. "Small function size" corresponds to the minimum size
+// a function needs to have to be considered for specialization. This is
+// controlled by the option `funcspec-min-function-size`. Similarly to latency
+// savings, we accumulate the codesize reduction attributed to the users of a
+// constant argument. To prevent a function from being specialized linearly to
+// the number of times the Specializer runs (controlled by `funcspec-max-iters`)
+// we penalize specialization on the same argument. The penalty is reflected on
+// the codesize increase.
+//
+// When accumulating latency and codesize savings of constant arguments, we keep
+// a set of visited users to avoid accounting for the same gains multiple times.
 //
 // References:
 // - 2021 LLVM Dev Mtg “Introducing function specialisation, and can we enable
 //   it by default?”, https://www.youtube.com/watch?v=zJiCjeXgV5Q
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_IPO_FUNCTIONSPECIALIZATION_H
 #define LLVM_TRANSFORMS_IPO_FUNCTIONSPECIALIZATION_H
 
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.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"
 
 using namespace llvm;
 
 namespace llvm {
+// Map of potential specializations for each function. The FunctionSpecializer
+// keeps the discovered specialisation opportunities for the module in a single
+// vector, where the specialisations of each function form a contiguous range.
+// This map's value is the beginning and the end of that range.
+using SpecMap = DenseMap<Function *, std::pair<unsigned, unsigned>>;
+
+// Just a shorter abbreviation to improve indentation.
+using Cost = InstructionCost;
+
 // Specialization signature, used to uniquely designate a specialization within
 // a function.
 struct SpecSig {
   // Hashing support, used to distinguish between ordinary, empty, or tombstone
   // keys.
   unsigned Key = 0;
   SmallVector<ArgInfo, 4> Args;
 
struct Spec {
 
   // Cloned function, a specialized version of the original one.
   Function *Clone = nullptr;
 
   // Specialization signature.
   SpecSig Sig;
 
   // Profitability of the specialization.
-  InstructionCost Gain;
+  Cost Score;
 
   // List of call sites, matching this specialization.
   SmallVector<CallBase *> CallSites;
 
-  Spec(Function *F, const SpecSig &S, InstructionCost G)
-      : F(F), Sig(S), Gain(G) {}
-  Spec(Function *F, const SpecSig &&S, InstructionCost G)
-      : F(F), Sig(S), Gain(G) {}
+  Spec(Function *F, const SpecSig &S, Cost Score)
+      : F(F), Sig(S), Score(Score) {}
+  Spec(Function *F, const SpecSig &&S, Cost Score)
+      : F(F), Sig(S), Score(Score) {}
 };
 
-// Map of potential specializations for each function. The FunctionSpecializer
-// keeps the discovered specialisation opportunities for the module in a single
-// vector, where the specialisations of each function form a contiguous range.
-// This map's value is the beginning and the end of that range.
-using SpecMap = DenseMap<Function *, std::pair<unsigned, unsigned>>;
-
 class FunctionSpecializer {
 
   /// The IPSCCP Solver.
   SCCPSolver &Solver;
 
   Module &M;
 
   /// Analysis manager, needed to invalidate analyses.
   FunctionAnalysisManager *FAM;
 
   /// Analyses used to help determine if a function should be specialized.
   std::function<const TargetLibraryInfo &(Function &)> GetTLI;
   std::function<TargetTransformInfo &(Function &)> GetTTI;
   std::function<AssumptionCache &(Function &)> GetAC;
 
   SmallPtrSet<Function *, 32> Specializations;
   SmallPtrSet<Function *, 32> FullySpecialized;
   DenseMap<Function *, CodeMetrics> FunctionMetrics;
+  DenseMap<Argument *, unsigned> NumSpecs;
 
 public:
   FunctionSpecializer(
       SCCPSolver &Solver, Module &M, FunctionAnalysisManager *FAM,
       std::function<const TargetLibraryInfo &(Function &)> GetTLI,
       std::function<TargetTransformInfo &(Function &)> GetTTI,
       std::function<AssumptionCache &(Function &)> GetAC)
       : Solver(Solver), M(M), FAM(FAM), GetTLI(GetTLI), GetTTI(GetTTI),
private:
   void promoteConstantStackValues();
 
   /// Clean up fully specialized functions.
   void removeDeadFunctions();
 
   /// Remove any ssa_copy intrinsics that may have been introduced.
   void cleanUpSSA();
 
-  // Compute the code metrics for function \p F.
-  CodeMetrics &analyzeFunction(Function *F);
-
   /// @brief  Find potential specialization opportunities.
   /// @param F Function to specialize
-  /// @param Cost Cost of specializing a function. Final gain is this cost
-  /// minus benefit
   /// @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, InstructionCost Cost,
-                           SmallVectorImpl<Spec> &AllSpecs, SpecMap &SM);
+  bool findSpecializations(Function *F, SpecMap &SM,
+                           SmallVectorImpl<Spec> &AllSpecs);
 
   bool isCandidateFunction(Function *F);
 
   /// @brief Create a specialization of \p F and prime the SCCPSolver
   /// @param F Function to specialize
   /// @param S Which specialization to create
   /// @return The new, cloned function
   Function *createSpecialization(Function *F, const SpecSig &S);
 
-  /// Compute and return the cost of specializing function \p F.
-  InstructionCost getSpecializationCost(Function *F);
-
-  /// Compute a bonus for replacing argument \p A with constant \p C.
-  InstructionCost getSpecializationBonus(Argument *A, Constant *C,
-                                         const LoopInfo &LI);
+  /// Compute latency and codesize savings resulting from the replacement of
+  /// argument \p A with constant \p C.
+  void getSpecializationBonus(Argument *A, Constant *C, const LoopInfo &LI,
+                              Cost &Latency, Cost &CodeSize,
+                              DenseSet<User *> &Visited);
 
   /// Determine if it is possible to specialise the function for constant values
   /// of the formal parameter \p A.
   bool 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 *getCandidateConstant(Value *V);

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

 //===- 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
 //
 //===----------------------------------------------------------------------===//
-//
-// This specialises functions with constant parameters. Constant parameters
-// like function pointers and constant globals are propagated to the callee by
-// specializing the function. The main benefit of this pass at the moment is
-// that indirect calls are transformed into direct calls, which provides inline
-// opportunities that the inliner would not have been able to achieve. That's
-// why function specialisation is run before the inliner in the optimisation
-// pipeline; that is by design. Otherwise, we would only benefit from constant
-// passing, which is a valid use-case too, but hasn't been explored much in
-// terms of performance uplifts, cost-model and compile-time impact.
-//
-// Current limitations:
-// - It does not yet handle integer ranges. We do support "literal constants",
-//   but that's off by default under an option.
-// - The cost-model could be further looked into (it mainly focuses on inlining
-//   benefits),
-//
-// Ideas:
-// - With a function specialization attribute for arguments, we could have
-//   a direct way to steer function specialization, avoiding the cost-model,
-//   and thus control compile-times / code-size.
-//
-// Todos:
-// - Specializing recursive functions relies on running the transformation a
-//   number of times, which is controlled by option
-//   `func-specialization-max-iters`. Thus, increasing this value and the
-//   number of iterations, will linearly increase the number of times recursive
-//   functions get specialized, see also the discussion in
-//   https://reviews.llvm.org/D106426 for details. Perhaps there is a
-//   compile-time friendlier way to control/limit the number of specialisations
-//   for recursive functions.
-// - Don't transform the function if function specialization does not trigger;
-//   the SCCPSolver may make IR changes.
-//
-// References:
-// - 2021 LLVM Dev Mtg “Introducing function specialisation, and can we enable
-//   it by default?”, https://www.youtube.com/watch?v=zJiCjeXgV5Q
-//
-//===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/FunctionSpecialization.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueLattice.h"
static cl::opt<bool> ForceSpecialization(
     "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> MaxUserDepth(
+    "funcspec-max-user-depth", cl::init(3), cl::Hidden, cl::desc(
+    "The maximum recursion depth on a use-def chain for calculating "
+    "the specialization bonus of a constant argument"));
+
+static cl::opt<unsigned> MinScore(
+    "funcspec-min-score", cl::init(80), cl::Hidden, cl::desc(
+    "Do not specialize functions with score lower than this value "
+    "(the ratio of latency gains over codesize increase)"));
+
 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<unsigned> AvgLoopIters(
     "funcspec-avg-loop-iters", cl::init(10), cl::Hidden, cl::desc(
     "Average loop iteration count"));
bool FunctionSpecializer::run() {
   // Find possible specializations for each function.
   SpecMap SM;
   SmallVector<Spec, 32> AllSpecs;
   unsigned NumCandidates = 0;
   for (Function &F : M) {
     if (!isCandidateFunction(&F))
       continue;
 
-    auto Cost = getSpecializationCost(&F);
-    if (!Cost.isValid()) {
-      LLVM_DEBUG(dbgs() << "FnSpecialization: Invalid specialization cost for "
-                        << F.getName() << "\n");
-      continue;
-    }
-
-    LLVM_DEBUG(dbgs() << "FnSpecialization: Specialization cost for "
-                      << F.getName() << " is " << Cost << "\n");
-
-    if (!findSpecializations(&F, Cost, AllSpecs, SM)) {
+    if (!findSpecializations(&F, SM, AllSpecs)) {
       LLVM_DEBUG(
           dbgs() << "FnSpecialization: No possible specializations found for "
                  << F.getName() << "\n");
       continue;
     }
 
     ++NumCandidates;
   }
 
   if (!NumCandidates) {
     LLVM_DEBUG(
         dbgs()
         << "FnSpecialization: No possible specializations found in module\n");
     return false;
   }
 
   // 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 * MaxClones, unsigned(AllSpecs.size()));
   SmallVector<unsigned> BestSpecs(NSpecs + 1);
   std::iota(BestSpecs.begin(), BestSpecs.begin() + NSpecs, 0);
   if (AllSpecs.size() > NSpecs) {
     LLVM_DEBUG(dbgs() << "FnSpecialization: Number of candidates exceed "
                       << "the maximum number of clones threshold.\n"
                       << "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);
     }
   }
 
   LLVM_DEBUG(dbgs() << "FnSpecialization: List of specializations \n";
              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()
                         << ", ActualArg = " << Arg.Actual->getNameOrAsOperand()
                         << "\n";
              });
 
   // Create the chosen specializations.
LLVM_DEBUG(dbgs() << "FnSpecialization: Removing dead function "
                       << F->getName() << "\n");
     if (FAM)
       FAM->clear(*F, F->getName());
     F->eraseFromParent();
   }
   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) {
   ValueToValueMapTy Mappings;
   Function *Clone = CloneFunction(F, Mappings);
   removeSSACopy(*Clone);
   return Clone;
 }
 
-bool FunctionSpecializer::findSpecializations(Function *F, InstructionCost Cost,
-                                              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;
+bool FunctionSpecializer::findSpecializations(Function *F, SpecMap &SM,
+                                              SmallVectorImpl<Spec> &AllSpecs) {
+  // Analyze the function if not done yet.
+  auto [It, Inserted] = FunctionMetrics.try_emplace(F, CodeMetrics());
+  CodeMetrics &Metrics = It->second;
+  if (Inserted) {
+    // 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);
+  }
+  // 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() ||
+      (!ForceSpecialization && !F->hasFnAttribute(Attribute::NoInline) &&
+       Metrics.NumInsts < MinFunctionSize))
+    return false;
 
   // Get a list of interesting arguments.
   SmallVector<Argument *> Args;
   for (Argument &Arg : F->args())
     if (isArgumentInteresting(&Arg))
       Args.push_back(&Arg);
 
   if (Args.empty())
     return false;
 
+  // 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> UniqueSpecs;
+
+  // LoopInfo is required for the bonus estimation of each argument's users.
+  const LoopInfo &LI = Solver.getLoopInfo(*F);
+
   bool Found = false;
   for (User *U : F->users()) {
     if (!isa<CallInst>(U) && !isa<InvokeInst>(U))
       continue;
     auto &CS = *cast<CallBase>(U);
 
     // The user instruction does not call our function.
     if (CS.getCalledFunction() != F)
for (Argument *A : Args) {
                         << "\n");
       S.Args.push_back({A, C});
     }
 
     if (S.Args.empty())
       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
       // the cloned instances of this call, which result from specialising
       // functions. Hence we don't rewrite the call directly, but match it with
       // the best specialisation once all specialisations are known.
       if (CS.getFunction() == F)
         continue;
       const unsigned Index = It->second;
       AllSpecs[Index].CallSites.push_back(&CS);
     } else {
       // Calculate the specialisation gain.
-      InstructionCost Gain = 0 - Cost;
+      Cost Latency = 0;
+      Cost CodeSize = Metrics.NumInsts +
+                      Metrics.NumInlineCandidates * MinFunctionSize;
+      DenseSet<User *> Visited;
       for (ArgInfo &A : S.Args)
-        Gain +=
-            getSpecializationBonus(A.Formal, A.Actual, Solver.getLoopInfo(*F));
+        getSpecializationBonus(A.Formal, A.Actual, LI, Latency, CodeSize,
+                               Visited);
+      assert (CodeSize >= 0 &&
+              "The code size bonus cannot be larger than the function");
+      Cost Score = Latency / (CodeSize + 1);
 
+      LLVM_DEBUG(dbgs() << "FnSpecialization: Score {Latency " << Latency
+                        << ", CodeSize " << CodeSize << "} = " << Score
+                        << "\n");
       // Discard unprofitable specialisations.
-      if (!ForceSpecialization && Gain <= 0)
+      if (!ForceSpecialization && Score < MinScore)
         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;
 }

 Function *FunctionSpecializer::createSpecialization(Function *F, const SpecSig &S) {
   Function *Clone = cloneCandidateFunction(F);
 
   Solver.addArgumentTrackedFunction(Clone);
   Solver.addTrackedFunction(Clone);
 
   // Mark all the specialized functions
   Specializations.insert(Clone);
-  ++NumSpecsCreated;
 
-  return Clone;
-}
+  // Update the cost model.
+  for (const ArgInfo &A : S.Args)
+    ++NumSpecs[A.Formal];
 
-/// 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() ||
-      (!ForceSpecialization && !F->hasFnAttribute(Attribute::NoInline) &&
-       Metrics.NumInsts < MinFunctionSize))
-    return InstructionCost::getInvalid();
+  ++NumSpecsCreated;
 
-  // Otherwise, set the specialization cost to be the cost of all the
-  // instructions in the function.
-  return Metrics.NumInsts * InlineConstants::getInstrCost();
+  return Clone;
 }
 
-static InstructionCost getUserBonus(User *U, llvm::TargetTransformInfo &TTI,
-                                    const LoopInfo &LI) {
+static void getUserBonus(User *U, TargetTransformInfo &TTI,
+                         const LoopInfo &LI, unsigned UserDepth,
+                         Cost &Latency, Cost &CodeSize,
+                         DenseSet<User *> &Visited) {
+  // If the user is not an instruction we do not know how to evaluate.
+  // If we have already visited this user there's nothing to do.
+  // If the user is deep in the use-def chain then stop traversing.
+  auto [It, Inserted] = Visited.insert(U);
   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();
+  if (!I || !Inserted || UserDepth > MaxUserDepth)
+    return;
 
-  InstructionCost Cost =
-      TTI.getInstructionCost(U, TargetTransformInfo::TCK_SizeAndLatency);
+  // Ignore SSA copies.
+  auto *II = dyn_cast<IntrinsicInst>(I);
+  bool IsSSACopy = II && II->getIntrinsicID() == Intrinsic::ssa_copy;
 
-  // Increase the cost if it is inside the loop.
+  if (!IsSSACopy) {
+    // Increase the Latency if inside a loop and modulate by UserDepth.
     unsigned LoopDepth = LI.getLoopDepth(I->getParent());
-  Cost *= std::pow((double)AvgLoopIters, LoopDepth);
+    Latency += (TTI.getInstructionCost(U, TargetTransformInfo::TCK_Latency) *
+                std::pow((double)AvgLoopIters, LoopDepth)) / UserDepth;
+    CodeSize += TTI.getInstructionCost(U, TargetTransformInfo::TCK_CodeSize);
 
+    LLVM_DEBUG(dbgs() << "FnSpecialization:     Bonus { Latency = " << Latency
+                      << ", CodeSize = " << CodeSize << "} after user " << *U
+                      << "\n");
+    ++UserDepth;
+  }
   // 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;
+  for (User *User : I->users())
+    getUserBonus(User, TTI, LI, UserDepth, Latency, CodeSize, Visited);
 }
 
-/// Compute a bonus for replacing argument \p A with constant \p C.
-InstructionCost
-FunctionSpecializer::getSpecializationBonus(Argument *A, Constant *C,
-                                            const LoopInfo &LI) {
+/// Compute latency and codesize savings resulting from the replacement of
+/// argument \p A with constant \p C.
+void FunctionSpecializer::getSpecializationBonus(Argument *A, Constant *C,
+                              const LoopInfo &LI, Cost &Latency, Cost &CodeSize,
+                              DenseSet<User *> &Visited) {
   Function *F = A->getParent();
   auto &TTI = (GetTTI)(*F);
   LLVM_DEBUG(dbgs() << "FnSpecialization: Analysing bonus for constant: "
                     << C->getNameOrAsOperand() << "\n");
+  // The more we specialize an argument, the more expensive it gets.
+  CodeSize *= NumSpecs[A] + 1;
 
-  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");
+  for (User *U : A->users()) {
+    Cost UserLatency = 0;
+    Cost UserSize = 0;
+    getUserBonus(U, TTI, LI, /*UserDepth=*/1, UserLatency, UserSize, Visited);
+    LLVM_DEBUG(dbgs() << "FnSpecialization:   Accumulated bonus { Latency = "
+                      << UserLatency << ", CodeSize = " << UserSize
+                      << "} for user " << *U << "\n");
+    // Decrease the codesize penalty by the footprint of each user.
+    Latency += UserLatency;
+    CodeSize -= UserSize;
   }
 
   // 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.
   Function *CalledFunction = dyn_cast<Function>(C->stripPointerCasts());
   if (!CalledFunction)
-    return TotalCost;
+    return;
 
   // Get TTI for the called function (used for the inline cost).
   auto &CalleeTTI = (GetTTI)(*CalledFunction);
 
   // Look at all the call sites whose called value is the argument.
   // Specializing the function on the argument would allow these indirect
   // calls to be promoted to direct calls. If the indirect call promotion
   // would likely enable the called function to be inlined, specializing is a
for (User *U : A->users()) {
     // threshold.
     if (IC.isAlways())
       Bonus += Params.DefaultThreshold;
     else if (IC.isVariable() && IC.getCostDelta() > 0)
       Bonus += IC.getCostDelta();
 
     LLVM_DEBUG(dbgs() << "FnSpecialization:   Inlining bonus " << Bonus
                       << " for user " << *U << "\n");
+    Latency += Bonus;
   }
-
-  return TotalCost + Bonus;
 }
 
 static bool isValidArgumentType(Type *Ty) {
   return Ty->isPointerTy() || (SpecializeLiteralConstant &&
         (Ty->isIntegerTy() || Ty->isFloatingPointTy() || Ty->isStructTy()));
 }
 
 /// Determine if it is possible to specialise the function for constant values
void FunctionSpecializer::updateCallSites(Function *F, const Spec *Begin,
 
   unsigned NCallsLeft = ToUpdate.size();
   for (CallBase *CS : ToUpdate) {
     bool ShouldDecrementCount = CS->getFunction() == F;
 
     // 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) {
             unsigned ArgNo = Arg.Formal->getArgNo();
             return getCandidateConstant(CS->getArgOperand(ArgNo)) != Arg.Actual;
           }))
         continue;
 

llvm/test/Transforms/FunctionSpecialization/function-specialization-constant-integers.ll

-; RUN: opt -passes="ipsccp<func-spec>" -funcspec-for-literal-constant=true -funcspec-min-function-size=10 -S < %s | FileCheck %s
+; RUN: opt -passes="ipsccp<func-spec>" -funcspec-for-literal-constant=true -force-specialization -S < %s | FileCheck %s
 
 ; Check that the literal constant parameter could be specialized.
 ; CHECK: @foo.1(
 ; CHECK: @foo.2(
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 
 declare i32 @getValue()

llvm/test/Transforms/FunctionSpecialization/function-specialization-loop.ll

-; RUN: opt -passes="ipsccp<func-spec>" -funcspec-avg-loop-iters=5 -funcspec-min-function-size=10 -S < %s | FileCheck %s
+; RUN: opt -passes="ipsccp<func-spec>" -funcspec-avg-loop-iters=11 -funcspec-min-function-size=10 -S < %s | FileCheck %s
 
 ; Check that the loop depth results in a larger specialization bonus.
 ; CHECK: @foo.1(
 ; CHECK: @foo.2(
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 
 @A = external dso_local constant i32, align 4

llvm/test/Transforms/FunctionSpecialization/get-possible-constants.ll

-; RUN: opt -S --passes="ipsccp<func-spec>" < %s | FileCheck %s
+; RUN: opt -S --passes="ipsccp<func-spec>" -force-specialization < %s | FileCheck %s
 define dso_local i32 @p0(i32 noundef %x) {
 entry:
   %add = add nsw i32 %x, 1
   ret i32 %add
 }
 
 define dso_local i32 @p1(i32 noundef %x) {
 entry:

llvm/test/Transforms/FunctionSpecialization/recursive-penalty.ll

+; REQUIRES: asserts
+; RUN: opt -passes="ipsccp<func-spec>,inline,instcombine,simplifycfg" -S \
+; RUN:     -funcspec-min-function-size=23 -funcspec-max-iters=100 \
+; RUN:     -debug-only=function-specialization < %s 2>&1 | FileCheck %s
+
+; Make sure the number of specializations created are not
+; linear to the number of iterations (funcspec-max-iters).
+
+; CHECK: FnSpecialization: Created 10 specializations in module
+
+@Global = internal constant i32 1, align 4
+
+define internal void @recursiveFunc(ptr readonly %arg) {
+  %temp = alloca i32, align 4
+  %arg.load = load i32, ptr %arg, align 4
+  %arg.cmp = icmp slt i32 %arg.load, 10000
+  br i1 %arg.cmp, label %loop1, label %ret.block
+
+loop1:
+  br label %loop2
+
+loop2:
+  br label %loop3
+
+loop3:
+  br label %loop4
+
+loop4:
+  br label %block6
+
+block6:
+  call void @print_val(i32 %arg.load)
+  %arg.add = add nsw i32 %arg.load, 1
+  store i32 %arg.add, ptr %temp, align 4
+  call void @recursiveFunc(ptr %temp)
+  br label %loop4.end
+
+loop4.end:
+  %exit_cond1 = call i1 @exit_cond()
+  br i1 %exit_cond1, label %loop4, label %loop3.end
+
+loop3.end:
+  %exit_cond2 = call i1 @exit_cond()
+  br i1 %exit_cond2, label %loop3, label %loop2.end
+
+loop2.end:
+  %exit_cond3 = call i1 @exit_cond()
+  br i1 %exit_cond3, label %loop2, label %loop1.end
+
+loop1.end:
+  %exit_cond4 = call i1 @exit_cond()
+  br i1 %exit_cond4, label %loop1, label %ret.block
+
+ret.block:
+  ret void
+}
+
+define i32 @main() {
+  call void @recursiveFunc(ptr @Global)
+  ret i32 0
+}
+
+declare dso_local void @print_val(i32)
+declare dso_local i1 @exit_cond()

llvm/test/Transforms/FunctionSpecialization/remove-dead-recursive-function.ll

-; RUN: opt -passes="ipsccp<func-spec>" -funcspec-min-function-size=3 -S < %s | FileCheck %s
+; RUN: opt -passes="ipsccp<func-spec>" -force-specialization -S < %s | FileCheck %s
 
 define i64 @main(i64 %x, i1 %flag) {
 entry:
   br i1 %flag, label %plus, label %minus
 
 plus:
   %tmp0 = call i64 @compute(i64 %x, ptr @plus)
   br label %merge