[FuncSpec] Increase the maximum number of times the specializer can run.

[labrinea]

Summary

• Changes the default value of FuncSpecMaxIters from 1 to 10. This allows specialization of recursive functions.
• Adds an option to control the maximum codesize growth per function.
• Measured ~45% performance uplift for SPEC2017:548.exchange2_r on AWS Graviton3.

[labrinea]

Bumps the score of 548.exchange2_r from SPEC2017 by about 60% on Neoverse N1.

[xbolva00]

In D145819#4186533, @labrinea wrote:

Bumps the score of 548.exchange2_r from SPEC2017 by about 60% on Neoverse N1.

Can we achieve this with lower FuncSpecMaxIters than 10 as 10 could be quite constly in terms of compile times?

[labrinea]

In D145819#4186807, @xbolva00 wrote:

In D145819#4186533, @labrinea wrote:

Bumps the score of 548.exchange2_r from SPEC2017 by about 60% on Neoverse N1.

Can we achieve this with lower FuncSpecMaxIters than 10 as 10 could be quite constly in terms of compile times?

Exchange requires 8 iterations, but we should be making the specializer as generic as possible. Note that FuncSpecMaxIters is the maximum number of times the specializer will run as long as each previous iteration has found specializations. As described in the summary we only consider callsites which reside in the bodies of previous specializations after the propagation of constant arguments. For now, that specialization on literal constants is disabled, this only triggers for recursive functions through promotion of constant stack values to globals which is quite rare. Therefore the impact in compilation times is zero for the general case. Only in code like exchange I would expect significant regression. That said I will post some numbers from the compile time tracker on the LLVM test suite.

Another important observation is that the compile time hit is attributed to the number of clones (the more, the higher) which suggests that the time is not spent on the specializer but on other optimization passes.

[labrinea]

Metric: Instruction Count
Comparison with base (parent of D145374 - top of the chain)

• Non LTO

testname	delta %
ClamAV	-0.101
7zip	+0.030
tramp3d-v4	-0.027
kimwitu++	-0.068
sqlite3	-0.213
mafft	-0.030
lencod	+0.020
SPASS	-0.324
consumer-typeset	+0.016
Bullet	+0.029
geomean	-0.067

• LTO

testname	delta %
ClamAV	+0.221
7zip	-0.034
tramp3d-v4	-0.003
kimwitu++	-0.128
sqlite3	+0.081
mafft	-0.039
lencod	-0.016
SPASS	-0.795
consumer-typeset	-0.001
Bullet	-0.044
geomean	-0.076

As I said the compile time hit is attributed to the number of clones so these changes are coming from D145379 (added one extra specialization for sqlite3 and one for ClamAV when linking) and from D145394 (removed all the specializations for SPASS).

[kiranchandramohan]

@labrinea Is this patch the top-level patch for recursive function-specialization that benefits exchange2? Is there any setting required or would this perform specialization by default? Also, assuming this is with llvm-project/flang.

[labrinea]

In D145819#4192593, @kiranchandramohan wrote:

@labrinea Is this patch the top-level patch for recursive function-specialization that benefits exchange2? Is there any setting required or would this perform specialization by default? Also, assuming this is with llvm-project/flang.

You can see the patch dependencies in the chain. Some of them are merged, others are pending review. I will rebase it once the chain is ready. The patch benefits exchange2_r when compiled with flang. No other changes are necessary.

[SjoerdMeijer]

High level question first, it looks like that geomean compile-times improve, and that is very surprising.
My guess is that one of the functional changes in findSpecialization is a good improvement on itself. Or maybe it is the caching of the CodeMetrics? Anyway, that's my question, just curious if you know what it is?

[labrinea]

@SjoerdMeijer

As I said the compile time hit is attributed to the number of clones so these changes are coming from D145379 (added one extra specialization for sqlite3 and one for ClamAV when linking) and from D145394 (removed all the specializations for SPASS).

(the compile time data include other patches of this chain, not just this one)

[labrinea]

Discarded most changes from previous revisions since the refactoring didn't seem necessary for keeping the compile times low.

[labrinea]

Ping!

[bjope]

In D145819#4375747, @labrinea wrote:

Ping!

@labrinea : Have you seen that there are problems with https://reviews.llvm.org/D150375 ?

[labrinea]

This comment was removed by labrinea.

[labrinea]

• rebased on D152799
• added an option to control max clones per function across multiple iterations

[labrinea]

I think this revision makes more sense than the previous attempts. Perhaps it also makes the option MaxClones redundant, and so we could save some compile time by avoiding the heap-sort of the specialization candidates. But that's an improvement to consider for the future.

[labrinea]

Ping @ChuanqiXu

[ChuanqiXu]

The patch itself looks pretty simple and the numbers look good too. So I think there may not be reason to block this.

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

713–715

It looks a little better to remove the variable.

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

class FunctionSpecializer {
   std::function<BlockFrequencyInfo &(Function &)> GetBFI;
   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<BlockFrequencyInfo &(Function &)> GetBFI,
       std::function<const TargetLibraryInfo &(Function &)> GetTLI,
       std::function<TargetTransformInfo &(Function &)> GetTTI,
       std::function<AssumptionCache &(Function &)> GetAC)

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

 
 STATISTIC(NumSpecsCreated, "Number of specializations created");
 
 static cl::opt<bool> ForceSpecialization(
     "force-specialization", cl::init(false), cl::Hidden, cl::desc(
     "Force function specialization for every call site with a constant "
     "argument"));
 
+static cl::opt<unsigned> MaxTotalClones(
+    "funcspec-max-total-clones", cl::init(8), cl::Hidden, cl::desc(
+    "The maximum number of clones allowed for a single function "
+    "specialization across multiple iterations"));
+
 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> MinFunctionSize(
     "funcspec-min-function-size", cl::init(100), cl::Hidden, cl::desc(
     "Don't specialize functions that have less than this number of "
if (auto It = UniqueSpecs.find(S); It != UniqueSpecs.end()) {
       // 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.
-      Cost Score = 0 - SpecCost;
+      Cost Score = 0;
       InstCostVisitor Visitor = getInstCostVisitorFor(F);
       for (ArgInfo &A : S.Args)
         Score += getSpecializationBonus(A.Formal, A.Actual, Visitor);
 
       // Discard unprofitable specialisations.
-      if (!ForceSpecialization && Score <= 0)
+      if (!ForceSpecialization && Score <= SpecCost)
         continue;
 
       // Create a new specialisation entry.
       auto &Spec = AllSpecs.emplace_back(F, S, Score);
       if (CS.getFunction() != F)
         Spec.CallSites.push_back(&CS);
       const unsigned Index = AllSpecs.size() - 1;
       UniqueSpecs[S] = Index;
       if (auto [It, Inserted] = SM.try_emplace(F, Index, Index + 1); !Inserted)
         It->second.second = Index + 1;
     }
   }
 
   return !UniqueSpecs.empty();
Function *FunctionSpecializer::createSpecialization(Function *F,
   // with the given value.
   Solver.setLatticeValueForSpecializationArguments(Clone, S.Args);
   Solver.markBlockExecutable(&Clone->front());
   Solver.addArgumentTrackedFunction(Clone);
   Solver.addTrackedFunction(Clone);
 
   // Mark all the specialized functions
   Specializations.insert(Clone);
+
+  // Update the cost model.
+  for (const ArgInfo &A : S.Args)
+    ++NumSpecs[A.Formal];
+
   ++NumSpecsCreated;
 
   return Clone;
 }
 
 /// Compute a bonus for replacing argument \p A with constant \p C.
 Cost FunctionSpecializer::getSpecializationBonus(Argument *A, Constant *C,
                                                  InstCostVisitor &Visitor) {
+  // Maximum number of clones reached.
+  if (NumSpecs[A] == MaxTotalClones)
+    return 0;
+
   LLVM_DEBUG(dbgs() << "FnSpecialization: Analysing bonus for constant: "
                     << C->getNameOrAsOperand() << "\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/lib/Transforms/IPO/SCCP.cpp

 STATISTIC(NumInstRemoved, "Number of instructions removed");
 STATISTIC(NumArgsElimed ,"Number of arguments constant propagated");
 STATISTIC(NumGlobalConst, "Number of globals found to be constant");
 STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
 STATISTIC(NumInstReplaced,
           "Number of instructions replaced with (simpler) instruction");
 
 static cl::opt<unsigned> FuncSpecMaxIters(
-    "funcspec-max-iters", cl::init(1), cl::Hidden, cl::desc(
+    "funcspec-max-iters", cl::init(10), cl::Hidden, cl::desc(
     "The maximum number of iterations function specialization is run"));
 
 static void findReturnsToZap(Function &F,
                              SmallVector<ReturnInst *, 8> &ReturnsToZap,
                              SCCPSolver &Solver) {
   // We can only do this if we know that nothing else can call the function.
   if (!Solver.isArgumentTrackedFunction(&F))
     return;

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 8 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()