[TTI] Add getInliningThresholdMultiplier.

[jlebar]

Summary

InlineCost's threshold is multiplied by this value. This lets us adjust
the inlining threshold up or down on a per-target basis. For example,
we might want to increase the threshold on targets where calls are
unusually expensive.

[arsenm]

lib/Analysis/TargetTransformInfo.cpp

71–73

I thought using host FP was to be avoided, so I'm surprised this isn't an integer factor. Couldn't you have one assert on isnormal()?

[jlebar]

lib/Analysis/TargetTransformInfo.cpp

71–73

I thought using host FP was to be avoided

No idea. It seems substantially less flexible to use an integer factor (you can't decrease the inlining threshold except to 0), but it works fine for my case, so I have no problem changing it if that's the convention.

Couldn't you have one assert on isnormal()?

isnormal(0) seems to be false, but giving a multiplier of 0 doesn't seem outrageous to me?

[arsenm]

lib/Analysis/TargetTransformInfo.cpp

71–73

You could return a rational numerator + denominator pair

[jlebar]

Specify the inlining threshold multiplier as a fraction.

[eraman]

Wouldn't it be better to use an additive bonus to the threshold instead of multiplicative factor to account for expensive calls?

[jlebar]

In D18560#387488, @eraman wrote:

Wouldn't it be better to use an additive bonus to the threshold instead of multiplicative factor to account for expensive calls?

Not necessarily? It seems not unreasonable that if we e.g. went from an un-multiplied inlining threshold of 10 to 100 that the adjusted threshold should also increase by 10x, rather than increase by +90. Like, it depends on what is the intent behind the 10 --> 100 change.

Given how blunt this is, and given that it's used by exactly one target at the moment, I'm inclined not to bikeshed too hard on the exact form it takes. Like, it would be better to rearrange all of the constants inside InlineCost to better reflect costs on the target machine. But the discussion of exactly what form this should take would probably be much more productive at the point that what we have doesn't work for some new target.

[hfinkel]

In D18560#387502, @jlebar wrote:

In D18560#387488, @eraman wrote:

Wouldn't it be better to use an additive bonus to the threshold instead of multiplicative factor to account for expensive calls?

Not necessarily? It seems not unreasonable that if we e.g. went from an un-multiplied inlining threshold of 10 to 100 that the adjusted threshold should also increase by 10x, rather than increase by +90. Like, it depends on what is the intent behind the 10 --> 100 change.

Given how blunt this is, and given that it's used by exactly one target at the moment, I'm inclined not to bikeshed too hard on the exact form it takes. Like, it would be better to rearrange all of the constants inside InlineCost to better reflect costs on the target machine. But the discussion of exactly what form this should take would probably be much more productive at the point that what we have doesn't work for some new target.

If you'd like a target-specific cost adjustment, which seems perfectly reasonable, it should be additive, and should be a function of the call site (i.e. both the caller and the callee, not just the caller). Also, hopefully the rationale for these numbers can be clearly articulated in comments in the TTI implementation, so we know how to adjust them if we change how TTI.getUserCost works.

[jlebar]

If you'd like a target-specific cost adjustment, which seems perfectly reasonable, it should be additive,

One of the other reasons I think a multiplicative setting makes sense is, there's no way to change the fudge factor. All you can change is the base inlining threshold. So the question is, as a user changing the inlining threshold, what do I expect to happen on a platform that has an inlining threshold adjustment?

Suppose I set the (global, un-fudged) inlining threshold (again, the only thing I can change) to something very small. It seems to me that should imply that relatively little inlining occurs. But of course an additive fudge doesn't accomplish that. And in fact there's no good way for me to set the post-fudge inlining threshold to a small value -- I'd have to set it to a negative number, and I'd have to calculate that specific value by looking at the TTI.

In contrast, if the fudge is multiplicative, then we have the property that a small pre-fudge inlining threshold results in a small post-fudge threshold.

If a multipliciative fudge is off the table, I think I'd feel more comfortable with the TTI giving an absolute inlining threshold that can be overridden on the command line. Is that any more appealing to you, Hal?

should be a function of the call site (i.e. both the caller and the callee, not just the caller).

Sure, I can make that change once we agree on the rest here.

Also, hopefully the rationale for these numbers can be clearly articulated in comments in the TTI implementation, so we know how to adjust them if we change how TTI.getUserCost works.

Haha, just like the current cross-arch threshold is so clearly motivated? :-p I don't have a good rationale other than, this number worked well for many internal benchmarks at Google. It's absolutely not scientifically arrived at; it's just a starting place.

Clearly we want more inlining on nvptx than on other archs, and, anecdotally, I tried a few benchmarks that showed 10% gains from this change. But ptxas does its own inlining, and it's a black box, so this is all very mushy. And more importantly, speed is only half the story -- inlining big functions is a size/speed tradeoff, and that's harder to quantify. Like, GPUs tend to have relatively little code to begin with, so maybe we have more wiggle room on the size end? But how much -- 1.5x, 5x, 100x? Who knows.

[chandlerc]

In D18560#389927, @jlebar wrote:

If you'd like a target-specific cost adjustment, which seems perfectly reasonable, it should be additive,

One of the other reasons I think a multiplicative setting makes sense is, there's no way to change the fudge factor. All you can change is the base inlining threshold. So the question is, as a user changing the inlining threshold, what do I expect to happen on a platform that has an inlining threshold adjustment?

Suppose I set the (global, un-fudged) inlining threshold (again, the only thing I can change) to something very small. It seems to me that should imply that relatively little inlining occurs. But of course an additive fudge doesn't accomplish that. And in fact there's no good way for me to set the post-fudge inlining threshold to a small value -- I'd have to set it to a negative number, and I'd have to calculate that specific value by looking at the TTI.

In contrast, if the fudge is multiplicative, then we have the property that a small pre-fudge inlining threshold results in a small post-fudge threshold.

If a multipliciative fudge is off the table, I think I'd feel more comfortable with the TTI giving an absolute inlining threshold that can be overridden on the command line. Is that any more appealing to you, Hal?

I ended up chatting with Hal about this and he made a really great point about this. I had been thinking that it is really brittle to have the target provided inlining threshold be an absolute number instead of a multiplier / ratio as you have it.

However, Hal pointed out that this creates a coupling that could also be problematic. Consider an out-of-tree target with a carefully tuned inlining threshold multiplier. If lots of targets do this, changing the threshold could become extremely problematic because small changes would would still disturb the target-specific tunings. His suggestion was to use an absolute threshold from the target in the absense of an explicitly specified command line flag.

Thinking about this more, I think it still presents the same problem. Consider a change to the inliner that significantly changes the rate at which we inline things. It might be useful to be able to adjust the threshold when making the change to keep most inlining decisions neutral across targets.

I'm not completely sure that either of these approaches is really resistant to undue coupling...

One possible alternative is to not have the size-based inlining be target configurable, and to make this exclusively handled by the proposed runtime cost estimation based inlining when that is available. Perhaps this could be documented as a temporary hook that will be replaced with the runtime estimation? I'm curious what others think here.

Also, hopefully the rationale for these numbers can be clearly articulated in comments in the TTI implementation, so we know how to adjust them if we change how TTI.getUserCost works.

Haha, just like the current cross-arch threshold is so clearly motivated?

I'm going to write up a document describing the current system since this keeps coming up and causing confusion. I'll also try to sketch how other models would fit into this.

I don't have a good rationale other than, this number worked well for many internal benchmarks at Google. It's absolutely not scientifically arrived at; it's just a starting place.

Clearly we want more inlining on nvptx than on other archs, and, anecdotally, I tried a few benchmarks that showed 10% gains from this change. But ptxas does its own inlining, and it's a black box, so this is all very mushy. And more importantly, speed is only half the story -- inlining big functions is a size/speed tradeoff, and that's harder to quantify. Like, GPUs tend to have relatively little code to begin with, so maybe we have more wiggle room on the size end? But how much -- 1.5x, 5x, 100x? Who knows.

GPUs tend to not have significant icache-style bottlenecks because their kernels are typically small and easily predicted, etc. Still, there remains a fundamental limit on instruction working set size where inlining is profitable.

I think you'll want to do some "science" on this value eventually and document it. Typically we walk the value up and down and try to get an idea of the shape of the aggregate performance curve across a wide range of benchmarks. Then we look for what is usually a large flat mesa in the curve, and go with the small end of that.

-Chandler

[jlebar]

Consider an out-of-tree target with a carefully tuned inlining threshold multiplier. If lots of targets do this, changing the threshold could become extremely problematic because small changes would would still disturb the target-specific tunings.

My thought was, the inlining multiplier is such a coarse knob -- set atop rather coarse heuristics -- that tuning it particularly carefully for a target might not make much sense.

I don't know if that's true or not, but it's at least an argument one could make.

His suggestion was to use an absolute threshold from the target in the absense of an explicitly specified command line flag. Thinking about this more, I think it still presents the same problem. Consider a change to the inliner that significantly changes the rate at which we inline things. It might be useful to be able to adjust the threshold when making the change to keep most inlining decisions neutral across targets.

I guess this (and the previous one, to an extent) are a question of API stability guarantees. To the extent that we don't promise to have a stable API for out-of-tree targets, we could change the inliner and at the same time break compilation for any out-of-tree targets that set the threshold, right. They'll have to fix the error and recompute their inlining threshold.

That doesn't seem so unreasonable to me -- it's not like we'd be doing this once a month, or even every release. And as an out-of-tree target, you'd only be broken if you explicitly opted in to this tuning mechanism, which we could make clear comes with this possibility of future intentional breakage.

I think you'll want to do some "science" on this value eventually and document it.

Yes, absolutely. That change doesn't even appear in this patch, though; let's worry about it separately, if that's OK?

[hfinkel]

In D18560#397232, @jlebar wrote:

Consider an out-of-tree target with a carefully tuned inlining threshold multiplier. If lots of targets do this, changing the threshold could become extremely problematic because small changes would would still disturb the target-specific tunings.

My thought was, the inlining multiplier is such a coarse knob -- set atop rather coarse heuristics -- that tuning it particularly carefully for a target might not make much sense.

I don't know if that's true or not, but it's at least an argument one could make.

His suggestion was to use an absolute threshold from the target in the absense of an explicitly specified command line flag. Thinking about this more, I think it still presents the same problem. Consider a change to the inliner that significantly changes the rate at which we inline things. It might be useful to be able to adjust the threshold when making the change to keep most inlining decisions neutral across targets.

I guess this (and the previous one, to an extent) are a question of API stability guarantees. To the extent that we don't promise to have a stable API for out-of-tree targets, we could change the inliner and at the same time break compilation for any out-of-tree targets that set the threshold, right. They'll have to fix the error and recompute their inlining threshold.

That doesn't seem so unreasonable to me -- it's not like we'd be doing this once a month, or even every release. And as an out-of-tree target, you'd only be broken if you explicitly opted in to this tuning mechanism, which we could make clear comes with this possibility of future intentional breakage.

This is a concern, and you're right that any of the tuning knobs need to be returned in response to upstream changes. Fundamentally, I'm most concerned with sending the right message here, and not unnecessarily constraining our future actions (because while we're certainly free to change whatever we want in the future, regardless of backend tuning, in practice we try to be nice and accommodating because these things take time).

The message we want to send is:

1. This is a temporary hook, and while some mechanism to achieve this affect will be provided in the future, it might look nothing like this.
2. This is a coarse heuristic mechanism, not really backed by any self-consistent model.

After chatting with Chandler about this, my understanding of the current mechanism is this: Our current heuristic is size based (with some exceptions), and aims to answer the following question: Will inlining this function make the caller smaller?

Doing this involves two pieces. The first is constructing an estimate of the size of the inlined function (which is truncated at some point to keep the cost of the analysis from becoming quadratic), accounting for constant propagation via function arguments and resulting simplifications. Then we construct an estimate of the caller's size associated with the call site that can be eliminated by inlining (the call itself, allocas that can be eliminated, etc.).

The second piece is more empirical. How many instructions, on average, will be eliminated in the caller by resulting simplification by inlining a function? This is where the current threshold comes in, it is a (rough) estimate of this. Unfortunately, as currently used, it is also not purely an estimate of this, but also accounts for performance effects (which is why, for instance, we have a bonus for callees with vector instructions, etc.).

Longer term, we really need to separate the performance-based metric from the size-based metric. They're estimating different things, although we're unfortunately conflating them currently (by hiding our performance-based metric inside our estimate of size decrease from resulting caller simplification, and to a lesser extent, things like the call penalty).

For your use case, GPUs, you want to represent the fact that calls are really expensive, and you don't care nearly as much about code size, although you do care about compile time. As a result, your limit is more to limit the compile time from later stages of the compiler (and perhaps the inliner itself) than anything else. That having been said, NVIDIA GPUs do have an icache that holds some kilobytes of compiled code, and spilling out of that will cost you (although often not a huge amount).

In the long term, I imagine we want a more top-down heuristic for this kind of inlining, because we want to keep a function, or group of functions, below some absolute size threshold (unless there is a huge compensating performance speedup). The size based heuristic is also good for your use case, but only if it happens in a more pure sense.

So my conclusion is that all of this is wrong ;) -- but in the name of making progress, I'm fine with a way to bump the threshold for some targets. I think it should be just a number, because that's the simplest possible thing we can do. A number if difficult, however, because cannot directly account for -Os, etc. factors that go into the current threshold. Providing a fraction to be multiplied by the current threshold seems problematic because it sends the message that this is something that should be finely tuned, and it shouldn't be. Could this just be an integer multipler for now? That will prevent fine tuning, send the message that this is a temporary coarse knob, and then we can work on a more principled solution. If that would work for you, I think that is the best solution for now.

I think you'll want to do some "science" on this value eventually and document it.

Yes, absolutely. That change doesn't even appear in this patch, though; let's worry about it separately, if that's OK?

[jlebar]

Could this just be an integer multipler for now? That will prevent fine tuning, send the message that this is a temporary coarse knob, and then we can work on a more principled solution.

That sounds great to me, I will spin a patch. If anyone else disagrees, speak now or forever hold your peace...

[jlebar]

Update patch so that getInliningThresholdMultiplier is just a fixed number.

[jlebar]

Hal, I hope I didn't misunderstand: I took your comment to suggest that the multiplier should be fixed for a particular target -- it shouldn't depend on the caller/callee. I can add that back if that's not what you had in mind.

[hfinkel]

In D18560#401680, @jlebar wrote:

Hal, I hope I didn't misunderstand: I took your comment to suggest that the multiplier should be fixed for a particular target -- it shouldn't depend on the caller/callee. I can add that back if that's not what you had in mind.

This is fine. We can add those things back if we come up with a use case. As discussed, we really need to rework a bunch of this logic. LGTM.

[jlebar]

Thank you very much, everyone!

include/llvm/Analysis/TargetTransformInfo.h

public:
   /// being called in the event it is a library call with special lowering.
   int getCallCost(const Function *F, int NumArgs = -1) const;
 
   /// \brief Estimate the cost of calling a specific function when lowered.
   ///
   /// This overload allows specifying a set of candidate argument values.
   int getCallCost(const Function *F, ArrayRef<const Value *> Arguments) const;
 
+  /// \returns A value by which our inlining threshold should be multiplied, for
+  /// the given caller function.  This is primarily used to bump up the inlining
+  /// threshold wholesale on targets where calls are unusually expensive.
+  /// TODO: This is a rather blunt instrument.  Perhaps altering the costs of
+  /// individual classes of instructions would be better.
+  double getInliningThresholdMultiplier(const Function *Caller) const;
+
   /// \brief Estimate the cost of an intrinsic when lowered.
   ///
   /// Mirrors the \c getCallCost method but uses an intrinsic identifier.
   int getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                        ArrayRef<Type *> ParamTys) const;
 
   /// \brief Estimate the cost of an intrinsic when lowered.
   ///
public:
   virtual const DataLayout &getDataLayout() const = 0;
   virtual int getOperationCost(unsigned Opcode, Type *Ty, Type *OpTy) = 0;
   virtual int getGEPCost(Type *PointeeType, const Value *Ptr,
                          ArrayRef<const Value *> Operands) = 0;
   virtual int getCallCost(FunctionType *FTy, int NumArgs) = 0;
   virtual int getCallCost(const Function *F, int NumArgs) = 0;
   virtual int getCallCost(const Function *F,
                           ArrayRef<const Value *> Arguments) = 0;
+  virtual double getInliningThresholdMultiplier(const Function *Caller) = 0;
   virtual int getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                                ArrayRef<Type *> ParamTys) = 0;
   virtual int getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                                ArrayRef<const Value *> Arguments) = 0;
   virtual int getUserCost(const User *U) = 0;
   virtual bool hasBranchDivergence() = 0;
   virtual bool isSourceOfDivergence(const Value *V) = 0;
   virtual bool isLoweredToCall(const Function *F) = 0;
public:
   }
   int getCallCost(const Function *F, int NumArgs) override {
     return Impl.getCallCost(F, NumArgs);
   }
   int getCallCost(const Function *F,
                   ArrayRef<const Value *> Arguments) override {
     return Impl.getCallCost(F, Arguments);
   }
+  double getInliningThresholdMultiplier(const Function *Caller) override {
+    return Impl.getInliningThresholdMultiplier(Caller);
+  }
   int getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                        ArrayRef<Type *> ParamTys) override {
     return Impl.getIntrinsicCost(IID, RetTy, ParamTys);
   }
   int getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                        ArrayRef<const Value *> Arguments) override {
     return Impl.getIntrinsicCost(IID, RetTy, Arguments);
   }

include/llvm/Analysis/TargetTransformInfoImpl.h

unsigned getCallCost(FunctionType *FTy, int NumArgs) {
     if (NumArgs < 0)
       // Set the argument number to the number of explicit arguments in the
       // function.
       NumArgs = FTy->getNumParams();
 
     return TTI::TCC_Basic * (NumArgs + 1);
   }
 
+  double getInliningThresholdMultiplier(const Function * /* Caller */) {
+    return 1;
+  }
+
   unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                             ArrayRef<Type *> ParamTys) {
     switch (IID) {
     default:
       // Intrinsics rarely (if ever) have normal argument setup constraints.
       // Model them as having a basic instruction cost.
       // FIXME: This is wrong for libc intrinsics.
       return TTI::TCC_Basic;

include/llvm/CodeGen/BasicTTIImpl.h

case Instruction::ZExt: {
         return TargetTransformInfo::TCC_Free;
       return TargetTransformInfo::TCC_Basic;
     }
     }
 
     return BaseT::getOperationCost(Opcode, Ty, OpTy);
   }
 
+  double getInliningThresholdMultiplier(const Function * /* Caller */) {
+    return 1;
+  }
+
   void getUnrollingPreferences(Loop *L, TTI::UnrollingPreferences &UP) {
     // This unrolling functionality is target independent, but to provide some
     // motivation for its intended use, for x86:
 
     // According to the Intel 64 and IA-32 Architectures Optimization Reference
     // Manual, Intel Core models and later have a loop stream detector (and
     // associated uop queue) that can benefit from partial unrolling.
     // The relevant requirements are:

lib/Analysis/InlineCost.cpp

bool ColdCallee =
        FunctionCount <= (uint64_t)(0.01 * (double)MaxFunctionCount));
   // Command line argument for DefaultInlineThreshold will override the default
   // ColdThreshold. If we have -inline-threshold but no -inlinecold-threshold,
   // do not use the default cold threshold even if it is smaller.
   if ((DefaultInlineThreshold.getNumOccurrences() == 0 ||
        ColdThreshold.getNumOccurrences() > 0) &&
       ColdCallee && ColdThreshold < Threshold)
     Threshold = ColdThreshold;
+
+  // Finally, take the target-specific inlining threshold multiplier into
+  // account.
+  Threshold =
+      std::round(Threshold * TTI.getInliningThresholdMultiplier(Caller));
 }
 
 bool CallAnalyzer::visitCmpInst(CmpInst &I) {
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
   // First try to handle simplified comparisons.
   if (!isa<Constant>(LHS))
     if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
       LHS = SimpleLHS;

lib/Analysis/TargetTransformInfo.cpp

 
 int TargetTransformInfo::getCallCost(const Function *F,
                                      ArrayRef<const Value *> Arguments) const {
   int Cost = TTIImpl->getCallCost(F, Arguments);
   assert(Cost >= 0 && "TTI should not produce negative costs!");
   return Cost;
 }
 
+double TargetTransformInfo::getInliningThresholdMultiplier(
+    const Function *Caller) const {
+  double Multiplier = TTIImpl->getInliningThresholdMultiplier(Caller);
+  assert(!std::isnan(Multiplier) && "Multiplier cannot be nan");
+  assert(!std::isinf(Multiplier) && "Multiplier cannot be infinity");
+  return Multiplier;
+}
+
 int TargetTransformInfo::getIntrinsicCost(
     Intrinsic::ID IID, Type *RetTy, ArrayRef<const Value *> Arguments) const {
   int Cost = TTIImpl->getIntrinsicCost(IID, RetTy, Arguments);
   assert(Cost >= 0 && "TTI should not produce negative costs!");
   return Cost;
 }
 
 int TargetTransformInfo::getUserCost(const User *U) const {