[FuncSpec] Enabling specializing direct constant

[ChuanqiXu]

Summary

I surprisingly find that FuncSpec pass can't specialize calls with direct constant.
An example is given as the test case.
I checked that the original pass couldn't pass that.

Test Plan: check-llvm

[ChuanqiXu]

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

491

I removed the check for ' V != A' since I think it should be true all the way.

[ChuanqiXu]

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

16–32 ↗

(On Diff #352373)

Loops here is to enhance the benefit for specializing 'foo'. I find that it is hard to specialize a function whose user are not in the loop.

[SjoerdMeijer]

Supporting integer constants opens up a whole new set of opportunities for function specialisation. This will have a big impact on compile-times, which is the main concern of this pass.
I suggest we take one step at a time, and add support for integer constants under an option that is off by default. Just for testing purposes this would be convenient, but it also allows to measure the impact on compile-times by toggling this option on/off.

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

15

Well, it is not really surprising, it was documented here as a limitation, so you can change that line. I.e., remove 'integer constants', keep the 'integer ranges'.

In your subject and description, you use the term 'direct constant', but better to keep the same terminology, which I think is 'integer constant'.

[ChuanqiXu]

In D104365#2821547, @SjoerdMeijer wrote:

Supporting integer constants opens up a whole new set of opportunities for function specialisation. This will have a big impact on compile-times, which is the main concern of this pass.
I suggest we take one step at a time, and add support for integer constants under an option that is off by default. Just for testing purposes this would be convenient, but it also allows to measure the impact on compile-times by toggling this option on/off.

Yeah, I forgot to measure the compile-time. I would measure it later. But I guess it may be OK since we control the cost to specialize function incrementally (implemented in getSpecializationCost()). So the amount of new specialized functions wouldn't be much larger.

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

15

Yeah, I missed it. And I think the terminology 'integer constants' may not be accurate. Since it seems like that float constant would be supported by this patch too.

[SjoerdMeijer]

But I guess it may be OK since we control the cost to specialize function incrementally (implemented in getSpecializationCost()). So the amount of new specialized functions wouldn't be much larger.

Why would we not specialise more? getSpecializationCost() just returns the cost for specialising a function. If we start doing this for functions with integer constants, I don't see why we could not start specialising more. But will double check if I missed anything.

I still think some fine gain control what to specialise will be convenient (for testing/experimenting). I will add an option for function pointers and globals.

[ChuanqiXu]

In D104365#2821718, @SjoerdMeijer wrote:

But I guess it may be OK since we control the cost to specialize function incrementally (implemented in getSpecializationCost()). So the amount of new specialized functions wouldn't be much larger.

Why would we not specialise more? getSpecializationCost() just returns the cost for specialising a function. If we start doing this for functions with integer constants, I don't see why we could not start specialising more. But will double check if I missed anything.

I still think some fine gain control what to specialise will be convenient (for testing/experimenting). I will add an option for function pointers and globals.

Since the cost of specializing a function would be multiplied by a penalty, which is the number of function specialized. So within the process of function specialized, the penalty would be larger and larger. So the number of new specialized functions wouldn't much more. It should be convergent.

[ChuanqiXu]

I would test the impact on compilation-time when I am available.

[ChuanqiXu]

I tested the compile time overhead on SPEC2017 intrate. The results show that this change wouldn't increase the compile-time with significant change. And the improvement for 505.mcf_r is remained.
So this patch looks good to me from my side.

[SjoerdMeijer]

Let me explain why I am a bit pushing back at this: I would like to see function specialisation enabled by default one day, and therefore I am interested to know how much more difficult that is going to be when we also specialise on integer constants. In previous comments you mentioned:

So the amount of new specialized functions wouldn't be much larger.

If we are going to specialise on integers, we are going to specialise more, even though the cost-model indeed takes the number of specialised functions into account. I don't think there's another way of looking at it.

The results show that this change wouldn't increase the compile-time with significant change.

I don't think we can draw this conclusion because we know that for SPEC function pointers are important. To understand what is happening, I would like to know how many functions were specialised on integer constants. Only then we can say something about this. And in order to get these numbers, it is probably convenient:

• to split the statistics up and have a counter for the constant globals and another for the constant integers,
• have command line options to toggle on/off this different behaviour.

Regardless whether this triggers or not in SPEC, I also think we need a few more data points to draw any conclusions. Because it is easy and relevant, I would suggest at least a bootstrap build and sqlite.

[ChuanqiXu]

In D104365#2829836, @SjoerdMeijer wrote:

Let me explain why I am a bit pushing back at this: I would like to see function specialisation enabled by default one day,。

Yeah, that's my wish too.

I don't think we can draw this conclusion because we know that for SPEC function pointers are important. To understand what is happening, I would like to know how many functions were specialised on integer constants. Only then we can say something about this. And in order to get these numbers, it is probably convenient:
to split the statistics up and have a counter for the constant globals and another for the constant integers, have command line options to toggle on/off this different behaviour. Regardless whether this triggers or not in SPEC, I also think we need a few more data points to draw any conclusions. Because it is easy and relevant, I would suggest at least a bootstrap build and sqlite.

I understand that it is always better to be careful and require an option to control the behavior. I could add an option and do more stats. But I think that it is a little bit counter-intuitive that function specialization wouldn't specialize integer constants. For a general example:

void foo(..., bool cond) {
    if (cond) {

    } else {

    }
}

From my mind, every one should think cond could be handled by function specialization. My point is that function specialization should support for constant integers. Even we add options, the ability to handle constant integers should be the default behavior too.
Of course, I would do other stats to support it.

But even the stats shows that this may incur some CT increasement, I would still think function specialization pass should handle the constant integers. Since it should be. On the other hand, I think the main part we should focus on is the cost model. In other words, even the CT increases due to this patch, we should investigate on the cost model instead of turn this off simply. I hope that we can get a consensus on this.

[SjoerdMeijer]

Specialising on constant integers would definitely be good, and is indeed what we want. But it's early days for function specialisation, and there are quite a few limitations, and this is just one of them.

I disagree with this:

But even the stats shows that this may incur some CT increasement, I would still think function specialization pass should handle the constant integers. Since it should be.

First of all, because we first need to know what the increase is. Second, when we know the increase, only then we can say if it should or not.

On the other hand, I think the main part we should focus on is the cost model. In other words, even the CT increases due to this patch, we should investigate on the cost model instead of turn this off simply. I hope that we can get a consensus on this.

Agreed on this. At the moment, we lack insights and data what this patch is doing. If we are going to build on top function specialisation and add more features, I would like to see the the new features and the cost-model to be developed hand in hand, otherwise it is only going to be harder later.

Repeating what I said earlier, I think the order of events should be this: I would like to see more fine-grain stats and options, compile time data for a few different code bases, and then a discussion on the cost-model before we add this.

We would like to achieve parity with GCC which has this enabled by default and is the reason I would like to get this enabled by default. My preferred approach would be to try this for constant globals and function pointers, because if we don't succeed in that, we are definitely not going to succeed if we also specialise on constant integers. Thus, I would like to do this step by step, by address some existing TODOs first to get the code in shape for this enabling this by default, then flip a switch to also specialise on constant integers. Thus, if you do this under an option that is off by default first, I have no problems at all with adding thi, while perhaps in the mean time you work on getting numbers and the cost-model.

[ChuanqiXu]

First of all, because we first need to know what the increase is. Second, when we know the increase, only then we can say if it should or not.
Repeating what I said earlier, I think the order of events should be this: I would like to see more fine-grain stats and options, compile time data for a few different code bases, and then a discussion on the cost-model before we add this.

Agreed. Although it seems like that the process of improving in this way would be much slower than I thought before, it would be much more stable. I could understand it.

thus, if you do this under an option that is off by default first, I have no problems at all with adding thi, while perhaps in the mean time you work on getting numbers and the cost-model.

Would do.

[ChuanqiXu]

Add an option to control the behavior.

Then I did some statistics for SPEC2017int

The total number of specialized functions increased about 18% (from 49 to 58)

Then I didn't find significant compile-time change with turning option on.

I wonder if this means that we can turn this option on by default.

[SjoerdMeijer]

In D104365#2843823, @ChuanqiXu wrote:

Add an option to control the behavior.

Then I did some statistics for SPEC2017int

The total number of specialized functions increased about 18% (from 49 to 58)

Then I didn't find significant compile-time change with turning option on.

I wonder if this means that we can turn this option on by default.

This looks good to me. Let's start with having this off by default. Like I mentioned earlier, for this to be enabled too by default we probably need some more numbers than only SPEC, but also e.g. a bootstrap build, llvm test suite, sqlite, etc. But now that we have this option, we can experiment with this, get more numbers, and also address some other TODOs before we try to enable function specialisation by default.

Before committing, can you rephrase the subject "Enabling specializing direct constant", make the description a bit more descriptive, and look at the inlined nits.

The total number of specialized functions increased about 18% (from 49 to 58)

I am surprised by this big number of specialisations. I remember seeing only 4 specialisations for SPEC2017int.

llvm/lib/Transforms/IPO/FunctionSpecialization.cpp

15

Nit: we can remove the "integer constants", but keep the integer ranges.

67

Nit: perhaps EnableSpecializeForLiteralConstant -> EnableSpecializationForLiteralConstant

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

4

Nit: perhaps direct constant -> literal constant

[ChuanqiXu]

Address the comments.

[ChuanqiXu]

In D104365#2847333, @SjoerdMeijer wrote:

In D104365#2843823, @ChuanqiXu wrote:

Add an option to control the behavior.

Then I did some statistics for SPEC2017int

The total number of specialized functions increased about 18% (from 49 to 58)

Then I didn't find significant compile-time change with turning option on.

I wonder if this means that we can turn this option on by default.

This looks good to me. Let's start with having this off by default. Like I mentioned earlier, for this to be enabled too by default we probably need some more numbers than only SPEC, but also e.g. a bootstrap build, llvm test suite, sqlite, etc. But now that we have this option, we can experiment with this, get more numbers, and also address some other TODOs before we try to enable function specialisation by default.

Sure.

The total number of specialized functions increased about 18% (from 49 to 58)

I am surprised by this big number of specialisations. I remember seeing only 4 specialisations for SPEC2017int.

It's surprising. My codebase is trunk with LTO. And I printed log for every function specialized. So I am pretty sure that I got the right number.

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 (e.g. functions,
 // globals). Constant parameters like function pointers and constant globals
 // are propagated to the callee by specializing the function.
 //
 // Current limitations:
 // - It does not handle specialization of recursive functions,
-// - It does not yet handle integer constants, and integer ranges,
+// - It does not yet handle integer ranges.
 // - Only 1 argument per function is specialised,
 // - The cost-model could be further looked into,
 // - We are not yet caching analysis results.
 //
 // 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.
cl::desc("The maximum number of clones allowed for a single function "
              "specialization"),
     cl::init(3));
 
 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."));
+
 // Helper to check if \p LV is either overdefined or a constant int.
 static bool isOverdefined(const ValueLatticeElement &LV) {
   return !LV.isUnknownOrUndef() && !LV.isConstant();
 }
 
 class FunctionSpecializer {
 
   /// The IPSCCP Solver.
for (User *U : F->users()) {
       auto *V = CS.getArgOperand(A->getArgNo());
       // TrackValueOfGlobalVariable only tracks scalar global variables.
       if (auto *GV = dyn_cast<GlobalVariable>(V)) {
         if (!GV->getValueType()->isSingleValueType()) {
           return false;
         }
       }
 
-      // Get the lattice value for the value the call site passes to the
-      // argument. If this value is not constant, move on to the next call
-      // site. Additionally, set the AllConstant flag to false.
-      if (V != A && !Solver.getLatticeValueFor(V).isConstant()) {
+      if (isa<Constant>(V) && (Solver.getLatticeValueFor(V).isConstant() ||
+                               EnableSpecializationForLiteralConstant))
+        Constants.push_back(cast<Constant>(V));
+      else
         AllConstant = false;
-        continue;
-      }
-
-      // Add the constant to the set.
-      if (auto *C = dyn_cast<Constant>(CS.getArgOperand(A->getArgNo())))
-        Constants.push_back(C);
     }
 
     // If the argument can only take on constant values, AllConstant will be
     // true.
     return AllConstant;
   }
 
   /// Rewrite calls to function \p F to call function \p Clone instead.

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

+; RUN: opt -function-specialization -function-specialization-for-literal-constant=true -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()
+declare i1 @getCond()
+
+define internal i32 @foo(i1 %break_cond) {
+entry:
+  br label %loop.entry
+
+loop.entry:
+  br label %loop2.entry
+
+loop2.entry:
+  br label %loop2.body
+
+loop2.body:
+  %value = call i32 @getValue()
+  br i1 %break_cond, label %loop2.end, label %return
+
+loop2.end:
+  %cond.end = call i1 @getCond()
+  br i1 %cond.end, label %loop2.entry, label %loop.end
+
+loop.end:
+  %cond2.end = call i1 @getCond()
+  br i1 %cond2.end, label %loop.entry, label %return
+
+return:
+  ret i32 %value
+}
+
+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