[FuncSpec] Don't specialize function which are easy to inline

[ChuanqiXu]

Summary

It would waste time to specialize a function which would inline finally.
This patch did two things:

• Don't specialize functions which are always-inline.
• Don't spescialize functions whose lines of code are less than threshold (100 by default).

For spec2017int, this patch could reduce the number of specialized functions by 33%. Then the compile time didn't increase for every benchmark.

Test Plan: check-llvm, spec2017

[SjoerdMeijer]

For spec2017int, this patch could reduce the number of specialized functions by 33%. Then the compile time didn't increase for every benchmark.

Do you mean that with this new default of 100, we see less function specialising for SPEC2017?

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

70

Nit: don't think "small" adds anything as it it is just the function threshold. Also the naming is inconsistent with other options (there is already some, but no need to make it worse), so can suggest:

-func-specialization-function-size-threshold

but because that's a bit verbose, perhaps shorter and still descriptive is:

-func-specialization-size-threshold

72

Typo: sepcializations

About the description, I am not sure about "redundant". Don't think redundant is the right description, and I would guess it's a profitability / compile-time trade-off, and we do not want to consider too small functions?

444

Typo: sepcialize

llvm/test/Transforms/FunctionSpecialization/function-specialization2.ll

5

Perhaps change one these -func-spec-small-function-threshold=10 additions into -force-function-specialization to check that interaction and behaviour.

[snehasish]

I think this patch raises the question whether the pass today is running at the right place in the pipeline with respect to the inliner. To me it seems that either the cost modeling should leverage the InlineCost heuristics (rather than arbitrary constants tuned on SPEC) or specialize post-inlining where such decision-making may no longer be necessary. This is particularly important with the presence of PGO information which significantly affects inlining decisions. It would be appreciated if we could spend some time studying the impact of timing of the pass before committing to this direction.

[xbolva00]

I fully agree @snehasish, this seems very hackish way - better to rethink it and make it more “general” instead of implementing some arbitrary limits.

[ChuanqiXu]

In D107897#2939299, @SjoerdMeijer wrote:

For spec2017int, this patch could reduce the number of specialized functions by 33%. Then the compile time didn't increase for every benchmark.

Do you mean that with this new default of 100, we see less function specialising for SPEC2017?

Yes. And the improved benchmarks could still get the improvement.

In D107897#2939910, @snehasish wrote:

I think this patch raises the question whether the pass today is running at the right place in the pipeline with respect to the inliner. To me it seems that either the cost modeling should leverage the InlineCost heuristics (rather than arbitrary constants tuned on SPEC) or specialize post-inlining where such decision-making may no longer be necessary. This is particularly important with the presence of PGO information which significantly affects inlining decisions. It would be appreciated if we could spend some time studying the impact of timing of the pass before committing to this direction.

Yes, this is the key question. Let me elaborate it more. The reason why we put this in the front of the inliner is that we could find opportunities to covert indirect call to direct call by function specialization. Then the inliner could make big benefit for that. And if we put function specialization after the inliner, we could only get the profit for constant passing.
BTW it looks like a common opportunity for me to convert indirect call to direct call since there are many functions being passed in actual codes. (Although the implementation for function specialization don't scale to be so powerful, that's our future direction).
So here is the decision point:

• Put function specialization in the front of the inliner.
  • We have the chance to convert indirect call to direct call.
  • There may be unuseful specialization which would be covered by the inliner. And this is what this patch tries to mitigate.
• Put function specialization in the back of the inliner.
  • We would miss the opportunity to convert indirect call to direct call.
  • We could avoid unuseful specialization totally.

From my perspective, it looks not bad after we add heuristics (no-matter simple constant or inline cost) to avoid specializing functions which would be inlined finally. Since we get the optimization opportunity and avoid many unused specialization.

For this topic about pass order, I have a more crazy idea:
inliner --> function specializer --> inliner (may be a new inliner pass)
To avoid wasting the time, we could add special attribute in function specializer. And let the second inliner to decide whether or not to inline these functions. The second inliner is also responsible to remove the attributes.

But the question why I didn't implement this is : is it really much better than this simple patch? On the one hand, we need write much more codes and it means more compile time generally. On the other hand, would the generated code be so different?
The reason I prefer this patch is the simplicity and effectiveness in a degree.

To me it seems that either the cost modeling should leverage the InlineCost heuristics (rather than arbitrary constants tuned on SPEC)

The InlineCost heuristics is for callsites instead of functions. If we decide to use InlineCost as a filter, we need run InlineCost for every callsite with constant parameter. It looks expensive to me since the calculation of InlineCost is not simple actually. And the estimation for functions is much cheaper.

[snehasish]

So here is the decision point:

• Put function specialization in the front of the inliner.
  • We have the chance to convert indirect call to direct call.
  • There may be unuseful specialization which would be covered by the inliner. And this is what this patch tries to mitigate.
• Put function specialization in the back of the inliner.
  • We would miss the opportunity to convert indirect call to direct call.
  • We could avoid unuseful specialization totally.

Thanks for elaborating on the motivation. At a high level it makes sense to me for plain builds which do not use PGO. With PGO, the situation is a little different - there is no longer any need to convert indirect call to direct call for subsequent inlining using this pass since indirect call promotion is very effective with profile information. However, even for plain builds we should not underestimate the negative impact of useless specializations particularly for large binaries. I think we may go towards a different pass timing for plain vs pgo optimization pipelines.

From my perspective, it looks not bad after we add heuristics (no-matter simple constant or inline cost) to avoid specializing functions which would be inlined finally. Since we get the optimization opportunity and avoid many unused specialization.

For this topic about pass order, I have a more crazy idea:
inliner --> function specializer --> inliner (may be a new inliner pass)
To avoid wasting the time, we could add special attribute in function specializer. And let the second inliner to decide whether or not to inline these functions. The second inliner is also responsible to remove the attributes.

This seems related to the approach you proposed in https://reviews.llvm.org/D105524 (incl. generalizing across to ThinLTO)?

But the question why I didn't implement this is : is it really much better than this simple patch? On the one hand, we need write much more codes and it means more compile time generally. On the other hand, would the generated code be so different?
The reason I prefer this patch is the simplicity and effectiveness in a degree.

Can you share what was the compile time degradation without this patch on SPEC?
Also we would be interested in any data you may have on code size increases and performance improvements on SPEC.

To me it seems that either the cost modeling should leverage the InlineCost heuristics (rather than arbitrary constants tuned on SPEC)

The InlineCost heuristics is for callsites instead of functions. If we decide to use InlineCost as a filter, we need run InlineCost for every callsite with constant parameter. It looks expensive to me since the calculation of InlineCost is not simple actually. And the estimation for functions is much cheaper.

Thats true, however again with PGO information not all functions need to be considered. For large binaries with a highly skewed ratio of hot to cold functions, it's possible a callsite oriented approach is less expensive while generalizing better? I am not fundamentally opposed to this patch for now as it benefits plain builds. However, in the longer run with a goal to enable this by default we are interested in how this will generalize to PGO builds as well as leveraging ThinLTO.

[ChuanqiXu]

In D107897#2943003, @snehasish wrote:

So here is the decision point:

• Put function specialization in the front of the inliner.
  • We have the chance to convert indirect call to direct call.
  • There may be unuseful specialization which would be covered by the inliner. And this is what this patch tries to mitigate.
• Put function specialization in the back of the inliner.
  • We would miss the opportunity to convert indirect call to direct call.
  • We could avoid unuseful specialization totally.

Thanks for elaborating on the motivation. At a high level it makes sense to me for plain builds which do not use PGO. With PGO, the situation is a little different - there is no longer any need to convert indirect call to direct call for subsequent inlining using this pass since indirect call promotion is very effective with profile information. However, even for plain builds we should not underestimate the negative impact of useless specializations particularly for large binaries. I think we may go towards a different pass timing for plain vs pgo optimization pipelines.

Yes, it's a key and good question: with PGO, how many benefit could the function specialization get? In fact, the main profit of function specialization could be covered by PGO according to the discussion from D93838. Although it is easy to image cases that function specialization could still benefit after applying PGO, it is hard to give realistic example and numbers for me now. But at least I think we could get in consensus in following:

• Function Specialization could be valuable without PGO.
• With PGO, the effect of function specialization may be questionable. But we need to experiment it more.

I think the topic of PGO and function specialization is much beyond the scope of this patch. It is a good question and it may be better to discuss it in llvm-dev.

From my perspective, it looks not bad after we add heuristics (no-matter simple constant or inline cost) to avoid specializing functions which would be inlined finally. Since we get the optimization opportunity and avoid many unused specialization.

For this topic about pass order, I have a more crazy idea:
inliner --> function specializer --> inliner (may be a new inliner pass)
To avoid wasting the time, we could add special attribute in function specializer. And let the second inliner to decide whether or not to inline these functions. The second inliner is also responsible to remove the attributes.

This seems related to the approach you proposed in https://reviews.llvm.org/D105524 (incl. generalizing across to ThinLTO)?

Not actually. What I mean is to make function specialization run after the inliner and we could write another inline pass to consider inlining the specialized functions. I think it could solve the useless-specialize problem totally. The reason why I didn't implement it is that I think it may be much complex than this one.

But the question why I didn't implement this is : is it really much better than this simple patch? On the one hand, we need write much more codes and it means more compile time generally. On the other hand, would the generated code be so different?
The reason I prefer this patch is the simplicity and effectiveness in a degree.

Can you share what was the compile time degradation without this patch on SPEC?
Also we would be interested in any data you may have on code size increases and performance improvements on SPEC.

Let me sure if I understand your words correctly. It looks like that you are asking: with function specialization, how the compile-time, code-sizes and performance changes?
There are results in D93838. Simply, the compile-time and code-size change is not aggressive. And the performance change mainly good for 500.mcf_r by 10%.

To me it seems that either the cost modeling should leverage the InlineCost heuristics (rather than arbitrary constants tuned on SPEC)

The InlineCost heuristics is for callsites instead of functions. If we decide to use InlineCost as a filter, we need run InlineCost for every callsite with constant parameter. It looks expensive to me since the calculation of InlineCost is not simple actually. And the estimation for functions is much cheaper.

Thats true, however again with PGO information not all functions need to be considered. For large binaries with a highly skewed ratio of hot to cold functions, it's possible a callsite oriented approach is less expensive while generalizing better? I am not fundamentally opposed to this patch for now as it benefits plain builds. However, in the longer run with a goal to enable this by default we are interested in how this will generalize to PGO builds as well as leveraging ThinLTO.

Yeah, it should use profiling information for the decision of this patch. I think it must be the future direction. For example, we would give up to specialize a function which is too hot.

[SjoerdMeijer]

Interesting discussion, and fair points have been raised. So there's definitely the question of phase ordering, and/or also PGO. But the way I look at this is that function specialisation is hot off the press, and there's a lot of unexplored territory, these 2 topics mentioned earlier included, and then we have also the ThinLTO question.

As explained, there's a reason for the current pipeline organisation, and this minor addition, this one-liner to check AlwaysInline makes sense in this context. This allows us to get a better baseline, i.e. an function specialisation version for which we can measure compile-time increases compared to clang with function specialisation, and GCC which has this enabled by default. This is my short/mid term objective: see if we can get a first version enabled by default to reach parity with GCC.

Like I said, I feel PGO is another topic that is indeed totally unexplored, and I can also easily imagine that for PGO things looks very different and is a different use case. And if I understood this correctly, that the pass ordering may look different:

I think we may go towards a different pass timing for plain vs pgo optimization pipelines.

[snehasish]

• Function Specialization could be valuable without PGO.
• With PGO, the effect of function specialization may be questionable. But we need to experiment it more.

I think the topic of PGO and function specialization is much beyond the scope of this patch. It is a good question and it may be better to discuss it in llvm-dev.

Agreed, since the focus is currently on plain builds we can continue this approach. In the future, we can share some information on impact with PGO.
@apostolakis @LilyZhong

Let me sure if I understand your words correctly. It looks like that you are asking: with function specialization, how the compile-time, code-sizes and performance changes?
There are results in D93838. Simply, the compile-time and code-size change is not aggressive. And the performance change mainly good for 500.mcf_r by 10%.

I was asking if there is a broader characterization for this work like the 2017 patch contained.

In D107897#2943236, @SjoerdMeijer wrote:

As explained, there's a reason for the current pipeline organisation, and this minor addition, this one-liner to check AlwaysInline makes sense in this context. This allows us to get a better baseline, i.e. an function specialisation version for which we can measure compile-time increases compared to clang with function specialisation, and GCC which has this enabled by default. This is my short/mid term objective: see if we can get a first version enabled by default to reach parity with GCC.

Sounds good to me, we can refine the PGO aspects if we find some opportunities.
Additionally, we would be happy to evaluate the impact (compile time, code size) on some large Google workloads once this pass is more mature.

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

70

+1 on consistent naming.

71

I think number of insts != lines of code where I assume Metrics.NumInsts enumerates the IR instruction count. Perhaps rephrase to make it more accurate?

llvm/test/Transforms/FunctionSpecialization/function-specialization-always-inline.ll

3–4

Perhaps this can be collapsed into a single CHECK-NOT: foo.{{[0-9]+}}

[ChuanqiXu]

Address the comments.

[ChuanqiXu]

In D107897#2944565, @snehasish wrote:

Let me sure if I understand your words correctly. It looks like that you are asking: with function specialization, how the compile-time, code-sizes and performance changes?
There are results in D93838. Simply, the compile-time and code-size change is not aggressive. And the performance change mainly good for 500.mcf_r by 10%.

I was asking if there is a broader characterization for this work like the 2017 patch contained.

Here is the result:

benchamrk	specialized number before this patch	specialized number after this patch
500.perlbench_r	7	5
502.gcc_r	45	28
505.mcf_r	2	2
525.x264_r	2	0
557.xz_r	4	4

[snehasish]

Thanks! I'm ok with this patch and revisiting the phase ordering and inlining interaction in the future. @xbolva00 what do you think?

[xbolva00]

As this improves the current state, go for it. In the future this check can be reworked and more sofisticated.

[ChuanqiXu]

@SjoerdMeijer Do you feel good with this?

[SjoerdMeijer]

LGTM

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

static cl::opt<unsigned> FuncSpecializationMaxIters(
     cl::init(1));
 
 static cl::opt<unsigned> MaxConstantsThreshold(
     "func-specialization-max-constants", cl::Hidden,
     cl::desc("The maximum number of clones allowed for a single function "
              "specialization"),
     cl::init(3));
 
+static cl::opt<unsigned> SmallFunctionThreshold(
+    "func-specialization-size-threshold", cl::Hidden,
+    cl::desc("For functions whose IR instruction count below this threshold, "
+             " they wouldn't be specialized to avoid useless sepcializations."),
+    cl::init(100));
+
 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<bool> EnableSpecializationForLiteralConstant(
     "function-specialization-for-literal-constant", cl::init(false), cl::Hidden,
     cl::desc("Make function specialization available for literal constant."));
if (F->hasOptSize() ||
         shouldOptimizeForSize(F, nullptr, nullptr, PGSOQueryType::IRPass))
       return false;
 
     // Exit if the function is not executable. There's no point in specializing
     // a dead function.
     if (!Solver.isBlockExecutable(&F->getEntryBlock()))
       return false;
 
+    // It wastes time to specialize a function which would get inlined finally.
+    if (F->hasFnAttribute(Attribute::AlwaysInline))
+      return false;
+
     LLVM_DEBUG(dbgs() << "FnSpecialization: Try function: " << F->getName()
                       << "\n");
 
     // Determine if it would be profitable to create a specialization of the
     // function where the argument takes on the given constant value. If so,
     // add the constant to Constants.
     auto FnSpecCost = getSpecializationCost(F);
     if (!FnSpecCost.isValid()) {
InstructionCost getSpecializationCost(Function *F) {
     SmallPtrSet<const Value *, 32> EphValues;
     CodeMetrics::collectEphemeralValues(F, &(GetAC)(*F), EphValues);
     CodeMetrics Metrics;
     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.
-    if (Metrics.notDuplicatable) {
+    // 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 ||
+        (!ForceFunctionSpecialization &&
+         Metrics.NumInsts < SmallFunctionThreshold)) {
       InstructionCost C{};
       C.setInvalid();
       return C;
     }
 
     // Otherwise, set the specialization cost to be the cost of all the
     // instructions in the function and penalty for specializing more functions.
     unsigned Penalty = NbFunctionsSpecialized + 1;

llvm/test/Transforms/FunctionSpecialization/function-specialization-always-inline.ll

-; RUN: opt -function-specialization -func-specialization-avg-iters-cost=3 -S < %s | FileCheck %s
+; RUN: opt -function-specialization -func-specialization-avg-iters-cost=3 -func-specialization-size-threshold=10 -S < %s | FileCheck %s
 
-; Check that the loop depth results in a larger specialization bonus.
-; CHECK: @foo.1(
-; CHECK: @foo.2(
+; CHECK-NOT: foo.{{[0-9]+}}
 
 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
 @B = external dso_local constant i32, align 4
 @C = external dso_local constant i32, align 4
 @D = external dso_local constant i32, align 4
 
 declare i1 @cond_begin()
 declare i1 @cond_end()
 declare i1 @getCond()
 
-define internal i32 @foo(i32 %x, i32* %b, i32* %c) {
+define internal i32 @foo(i32 %x, i32* %b, i32* %c) alwaysinline {
 entry:
   br label %loop.entry
 
 loop.entry:
   br label %loop2.entry
 
 loop2.entry:
   br label %loop2.body

 if.else:
   %call1 = call i32 @foo(i32 %y, i32* @B, i32* @D)
   br label %return
 
 return:
   %retval.0 = phi i32 [ %call, %if.then ], [ %call1, %if.else ]
   ret i32 %retval.0
 }
 No newline at end of file

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

-; RUN: opt -function-specialization -function-specialization-for-literal-constant=true -S < %s | FileCheck %s
+; RUN: opt -function-specialization -function-specialization-for-literal-constant=true -func-specialization-size-threshold=10 -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()

 
 define dso_local i32 @bar(i32 %x, i32 %y) {
 entry:
   %retval.1 = call i32 @foo(i1 1)
   %retval.2 = call i32 @foo(i1 0)
   %retval = add nsw i32 %retval.1, %retval.2
   ret i32 %retval
 }
 No newline at end of file

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

-; RUN: opt -function-specialization -func-specialization-avg-iters-cost=3 -S < %s | FileCheck %s
+; RUN: opt -function-specialization -func-specialization-avg-iters-cost=3 -func-specialization-size-threshold=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

 if.else:
   %call1 = call i32 @foo(i32 %y, i32* @B, i32* @D)
   br label %return
 
 return:
   %retval.0 = phi i32 [ %call, %if.then ], [ %call1, %if.else ]
   ret i32 %retval.0
 }
 No newline at end of file

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

 ; REQUIRES: asserts
-; RUN: opt -stats -function-specialization -S < %s 2>&1 | FileCheck %s
+; RUN: opt -stats -function-specialization -S -force-function-specialization < %s 2>&1 | FileCheck %s
 
 ; CHECK: 2 function-specialization - Number of functions specialized
 
 define i64 @main(i64 %x, i1 %flag) {
 entry:
   br i1 %flag, label %plus, label %minus
 
 plus:

llvm/test/Transforms/FunctionSpecialization/function-specialization2.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -function-specialization -deadargelim -S < %s | FileCheck %s
-; RUN: opt -function-specialization -func-specialization-max-iters=1 -deadargelim -S < %s | FileCheck %s
-; RUN: opt -function-specialization -func-specialization-max-iters=0 -deadargelim -S < %s | FileCheck %s --check-prefix=DISABLED
-; RUN: opt -function-specialization -func-specialization-avg-iters-cost=1 -deadargelim -S < %s | FileCheck %s
+; RUN: opt -function-specialization -deadargelim -force-function-specialization -S < %s | FileCheck %s
+; RUN: opt -function-specialization -func-specialization-max-iters=1 -deadargelim -force-function-specialization -S < %s | FileCheck %s
+; RUN: opt -function-specialization -func-specialization-max-iters=0 -deadargelim -force-function-specialization -S < %s | FileCheck %s --check-prefix=DISABLED
+; RUN: opt -function-specialization -func-specialization-avg-iters-cost=1 -deadargelim -force-function-specialization -S < %s | FileCheck %s
 
 ; DISABLED-NOT: @func.1(
 ; DISABLED-NOT: @func.2(
 
 define internal i32 @func(i32* %0, i32 %1, void (i32*)* nocapture %2) {
   %4 = alloca i32, align 4
   store i32 %1, i32* %4, align 4
   %5 = load i32, i32* %4, align 4