inlining hint

You may have noticed I added an "inlinehint" attribute to the IR yesterday, to represent user declarations that hint inlining would be a good idea ("inline" keyword). Chris and I have been discussing how to hook it up to the C++ FE. Consider:

class X {
    int A(int x) {....}
    inline int B(int x);
};
inline int X::B(int x) {...}

Per the language standard, A and B are semantically identical, both "inline". It's been suggested that we should omit the inlinehint on A, on the grounds that many C++ programmers do not know this, and therefore misuse the construct. I want to get some other views on this. Do you think it's a good idea?
(For those of you who consider yourselves C++ programmers - and not FE language lawyers, who are supposed to know what the standard says - did you know this?)

You may have noticed I added an "inlinehint" attribute to the IR
yesterday, to represent user declarations that hint inlining would be
a good idea ("inline" keyword). Chris and I have been discussing how
to hook it up to the C++ FE. Consider:

class X {
   int A(int x) {....}
   inline int B(int x);
};
inline int X::B(int x) {...}

Per the language standard, A and B are semantically identical, both
"inline". It's been suggested that we should omit the inlinehint on
A, on the grounds that many C++ programmers do not know this, and
therefore misuse the construct.

On the other hand, many C++ programmers know this and therefore omit the "inline" as redundant :slight_smile:

  I want to get some other views on
this. Do you think it's a good idea?

Yes, I think it is a good idea. Having the "inlinehint" attribute directly tied to the "inline" keyword is easy for users to reason about, and we'll still have heuristics to inline simple functions like accessors.

  - Doug

I recommend following the C++ standard here. Just as there are codebases
where the inline keyword is added to function definitions inside
class bodies with the intent to be meaningful, there are also codebases
where the inline keyword is omitted as redundant. LLVM itself is one
of the latter, for the most part.

For this reason, I'm actually somewhat surprised that you're adding
this hint, because you'll still need heuristics to find functions to
inline that aren't hinted, and to ignore hints on functions which
aren't good candidates. Are you aiming to create inlining heuristics
modeled after those of another compiler? If so, should the answer be
"whatever that other compiler does?"

Dan

Dale Johannesen <dalej@apple.com> writes:

[snip]

Per the language standard, A and B are semantically identical, both
"inline". It's been suggested that we should omit the inlinehint on
A, on the grounds that many C++ programmers do not know this, and
therefore misuse the construct. I want to get some other views on
this. Do you think it's a good idea?
(For those of you who consider yourselves C++ programmers - and not FE
language lawyers, who are supposed to know what the standard says -
did you know this?)

Maybe I'm not understanding your question, but for me methods defined
inside the class definition are inline and I would be dissapointed if
the compiler thinks otherwise (unless it knows that inlining would cause
inferior performance or is technically unfeasible: the Borland compiler
used to refuse inlining on some circunstances, such as when the function
contained a `throw').

After all, `inline' is like `register': just a wish that the compiler
can ignore, but a compiler shouldn't disregard the standard just for not
creating surprises to uninformed users, IMO.

Not necessarily, I'm going to be experimenting. A compiler can't possibly do optimal inlining without help, since the right inlining choices depend heavily on which calls and functions actually get executed, and the compiler can't know that. The inline hint is there in the languages so the inliner can give higher priority to inlining functions so marked; it seems advisable to make it available to our inliner. It may be that people misuse it so badly that it's ineffective, although I doubt that.

I do not understand how the "inlinehint" will help. How will it
influence the inliner ?

The hint should make it more attractive to inline. I don't know the details yet and they will require some experimenting.

In that case you want to add hint to A also. AFAIU, attractiveness of
A and B should match and inliner won't know whether the function body
is inside the class definition or not.

For background it is useful to know that a lot of this discussion is based on the assumption that the inliner will be making the wrong decisions. Dale comes at this from the premise that the inliner will always make the wrong decision and therefore it is useful to give the user some way to influence the inliners heuristic (other than attr(noinline/alwaysinline)).

There are three questions to consider:
1. whether a function is "semantically inline" should make it more attractive to inline.
2. whether a function that is "syntactically inline" should make it more attractive to inline.
3. whether neither should matter and the inliner should just look at the structure and size of the code, ignoring both syntactic and semantic inline hints (But still listening to always and noinline attributes of course).

To me personally, I have a hard time believing that either hint is really trustworthy and would rather invest effort into seeing how far we can get with #3. My reason for thinking this is twofold: first, many people slap the inline keyword on stuff without really thinking about how big the code will be. In the case of C++, because of abstraction and other things, the code may be compiled to something much larger than the source looks.

The second part of this is that there are a lot of reasons for things to be defined inline in C++ even if we don't want it to actually be inlined. For example, lib/VMCore/ConstantsContext.h:349 has a massive inline function that is there because it is part of a template specialization and *it is more convenient* to define it inline. I really don't think that method should be inlined, but it makes the source code tidier to do that. There are several other "good" examples in that file as well.

Since templates all have to be defined in header files for them to be instantiated, we frequently get large functions defined inline even though they shouldn't. One trivial example is SmallVector::insert(iterator,size_t, T).

I know/hope that the proposal isn't for the inlinehint to be a synonym for "force inline", it would just raise the threshold to increase the likeliness that it would be inlined. The question is whether "something being c++ inline" in any way is really trustworthy, and if so, whether we should look at syntactic vs semantic inline.

-Chris

Sorry "will always make the wrong decision *in some cases* and therefore..."

-Chris

[...]

The second part of this is that there are a lot of reasons for things
to be defined inline in C++ even if we don't want it to actually be
inlined.

I don't think those are _good_ reasons though: If one doesn't want a C++ function to be inlined, one shouldn't define it inline.

For example, lib/VMCore/ConstantsContext.h:349 has a
massive inline function that is there because it is part of a template
specialization and *it is more convenient* to define it inline. I
really don't think that method should be inlined, but it makes the
source code tidier to do that. There are several other "good"
examples in that file as well.

Since templates all have to be defined in header files for them to be
instantiated, we frequently get large functions defined inline even
though they shouldn't. One trivial example is
SmallVector::insert(iterator,size_t, T).

I think that's the same issue as above: If you don't think it's a good candidate for inlining, it shouldn't be defined inline.

I know/hope that the proposal isn't for the inlinehint to be a synonym
for "force inline", it would just raise the threshold to increase the
likeliness that it would be inlined. The question is whether
"something being c++ inline" in any way is really trustworthy, and if
so, whether we should look at syntactic vs semantic inline.

FWIW, I've been involved in a couple of attempts by commercial compilers to relegate "inline" to the same status as "register" -- an obsolete hint ignored by the compiler -- and so far that always proved to be unpractical because some critical calls that were previously inlined were no longer being inlined after the change. (That's just annecdotal, of course: LLVM may have gotten good enough to make it practical. If that's the case, I still think it's too early to write C++ code with that assumption.)

  Daveed

I know/hope that the proposal isn't for the inlinehint to be a synonym for
"force inline", it would just raise the threshold to increase the likeliness
that it would be inlined.

One alternative is to give the functions with hint first chance but
not change the threshold. Inliner works in two phase. In first phase,
only use function with inlinehint as candidates.

Truthfully, I think we need a thorough discussion our current inlining
heuristics before we try to consider what inlinehint adds to the
picture. The inlining code has been mostly untouched for a very long
time.

Some limitations I can think of off the top of my head:
Inlining doesn't take into account whether a load from a constant
pointer is constant.
Inlining is purely bottom-up: we inline large functions into small
functions when it would be better to inline the small function.
The cost metrics for constant-propagating into a branch or switch are
extremely imprecise.
Cost metrics can easily end up being negative (i.e. we always inline)
in cases where inlining will lead to arbitrarily large increases in
code size.
We only use one inlining pass normally; IIRC, the gcc devs found that
an additional early inlining pass is beneficial.

There are probably other issues which aren't obvious to me because I'm
not an expert in this sort of thing...

-Eli

I know/hope that the proposal isn't for the inlinehint to be a synonym
for "force inline", it would just raise the threshold to increase the
likeliness that it would be inlined. The question is whether
"something being c++ inline" in any way is really trustworthy, and if
so, whether we should look at syntactic vs semantic inline.

FWIW, I've been involved in a couple of attempts by commercial
compilers to relegate "inline" to the same status as "register" -- an
obsolete hint ignored by the compiler -- and so far that always proved
to be unpractical because some critical calls that were previously
inlined were no longer being inlined after the change. (That's just
annecdotal, of course: LLVM may have gotten good enough to make it
practical. If that's the case, I still think it's too early to write C
++ code with that assumption.)

It's actually the other way around. llvm has always ignored the "inline" keyword and now we are finding out we are missing some important cases.

Obviously the only correct solution is to make the inliner smarter so it can identify cases which are profitable that's currently ignoring. No one is arguing against that. On the other hand, that is most definitely not a simple solution. So we need an intermediate step.

The current plan is to make it behave a bit more like gcc (yeah I know it's not exactly where we want to go) so the "inline" keyword only impacts -O2 compilation. We should make conservative changes and then re-evaluate once we have more data. That means people who use llvm to compile C++ programs should definitely report any kind of performance changes once this change goes into effect.

Evan

It would help this discussion if you could post some examples.

-Eli

I know/hope that the proposal isn't for the inlinehint to be a
synonym
for "force inline", it would just raise the threshold to increase the
likeliness that it would be inlined. The question is whether
"something being c++ inline" in any way is really trustworthy, and if
so, whether we should look at syntactic vs semantic inline.

FWIW, I've been involved in a couple of attempts by commercial
compilers to relegate "inline" to the same status as "register" -- an
obsolete hint ignored by the compiler -- and so far that always proved
to be unpractical because some critical calls that were previously
inlined were no longer being inlined after the change. (That's just
annecdotal, of course: LLVM may have gotten good enough to make it
practical. If that's the case, I still think it's too early to
write C
++ code with that assumption.)

It's actually the other way around. llvm has always ignored the
"inline" keyword and now we are finding out we are missing some
important cases.

It would help this discussion if you could post some examples.

We know for a fact WebKit suffered when we turned off gcc inliner: pr2353. Dale is looking at this. Unfortunately it's a huge code base, it has not been easy to extract out smaller test cases. It's all part of the investigation that's going on right now.

Evan

I know/hope that the proposal isn't for the inlinehint to be a
synonym
for "force inline", it would just raise the threshold to increase the
likeliness that it would be inlined. The question is whether
"something being c++ inline" in any way is really trustworthy, and if
so, whether we should look at syntactic vs semantic inline.

FWIW, I've been involved in a couple of attempts by commercial
compilers to relegate "inline" to the same status as "register" -- an
obsolete hint ignored by the compiler -- and so far that always proved
to be unpractical because some critical calls that were previously
inlined were no longer being inlined after the change. (That's just
annecdotal, of course: LLVM may have gotten good enough to make it
practical. If that's the case, I still think it's too early to
write C
++ code with that assumption.)

It's actually the other way around. llvm has always ignored the
"inline" keyword and now we are finding out we are missing some
important cases.

Okay. It's the "other way around" in terms of history, but it looks like the conclusion might be the same: Purely heuristics-based inlining hasn't been proven entirely competitive yet (for C++)?

I read in your reply to Eli Friedman that there previously was another inliner (part of GCC) that presumably did take the C++ inline property into account? In at least two of the cases I was involved in, the scenario was similar: Really dumb "front end" inliners (that only inlined inline functions) ended up making a difference that couldn't be absorbed by improvements in the back end inliner (within the resource/schedule constraints of those subprojects).

Obviously the only correct solution is to make the inliner smarter so
it can identify cases which are profitable that's currently ignoring.

Is that really obvious? It would be nice to have such a correct solution, but I'm not positive there exists one. (There may be just as there turned out to be for register allocators -- I'm just not sure.)

No one is arguing against that. On the other hand, that is most
definitely not a simple solution. So we need an intermediate step.

The current plan is to make it behave a bit more like gcc (yeah I know
it's not exactly where we want to go) so the "inline" keyword only
impacts -O2 compilation. We should make conservative changes and then
re-evaluate once we have more data. That means people who use llvm to
compile C++ programs should definitely report any kind of performance
changes once this change goes into effect.

My GCC installation here appears to inline g in the following example:

  inline int g(int x) { return x; }

  int main() {
          return g(3);
  }

with just "-O1", but it doesn't do so when I drop the "inline" keyword.

$ g++ --version
g++43 (GCC) 4.3.1
Copyright (C) 2008 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

FWIW,

  Daveed

It's actually the other way around. llvm has always ignored the
"inline" keyword and now we are finding out we are missing some
important cases.

Okay. It's the "other way around" in terms of history, but it looks
like the conclusion might be the same: Purely heuristics-based
inlining hasn't been proven entirely competitive yet (for C++)?

That is what is unclear. We have no empirical evidence that listening to inline will improve the situation more than just increasing the inlining threshold across the board. Even if we did, I would still be uncomfortable with this: "hasn't been proven entirely competitive yet" implies that we've pursued the current inliner and tried hard to make it better without listening to inline. In fact, the current inliner is almost completely untuned and has many known problems.

I am concerned that "listening to inline" will paper over other things that could be solved in much better ways. If the inlining heuristics were already considered to be well tuned and a study showed that 'listening to inline' was better than increasing the threshold, then I'd be a believer.

I am also much more pessimistic about the world's C++ code than some. It turns out that not all c++ programmers are totally awesome :slight_smile:

My GCC installation here appears to inline g in the following example:

  inline int g(int x) { return x; }

  int main() {
          return g(3);
  }

with just "-O1", but it doesn't do so when I drop the "inline" keyword.

LLVM already does that at -O1 without listening to inline because the code is obviously smaller with the inline.

-Chris

It's actually the other way around. llvm has always ignored the
"inline" keyword and now we are finding out we are missing some
important cases.

Okay. It's the "other way around" in terms of history, but it looks
like the conclusion might be the same: Purely heuristics-based
inlining hasn't been proven entirely competitive yet (for C++)?

That is what is unclear. We have no empirical evidence that listening to inline will improve the situation more than just increasing the inlining threshold across the board. Even if we did, I would still be uncomfortable with this: "hasn't been proven entirely competitive yet" implies that we've pursued the current inliner and tried hard to make it better without listening to inline. In fact, the current inliner is almost completely untuned and has many known problems.

Definitely: Efforts in this area are almost certainly not a waste. Even if it turns out you need to take "inline" into account, a better (back end) inliner is likely to be an appreciable improvement.

My point is mostly that I'm not aware of an existing, competitive C++ compiler that always ignores the "this is a C++ inline function" bit. That doesn't mean it's not possible, and in fact I'm all for pursuing it. I _do_ believe that it means that current C++ programs should only define functions inline if there is good reason to think that inlining the typical call to that function is a plus.

(P.S., I _have_ worked with a compiler that had a separate flag to ignore "inline" because a customer has gone inline-crazy and ignoring inline became a competitive advantage at that point.)

I am concerned that "listening to inline" will paper over other things that could be solved in much better ways. If the inlining heuristics were already considered to be well tuned and a study showed that 'listening to inline' was better than increasing the threshold, then I'd be a believer.

Skepticism is good...

I am also much more pessimistic about the world's C++ code than some. It turns out that not all c++ programmers are totally awesome :slight_smile:

?? Shocked! I'm shocked!!

My GCC installation here appears to inline g in the following example:

  inline int g(int x) { return x; }

  int main() {
          return g(3);
  }

with just "-O1", but it doesn't do so when I drop the "inline" keyword.

LLVM already does that at -O1 without listening to inline because the code is obviously smaller with the inline.

I just wanted to make sure that the observation that GCC ignores "inline" (implicit or explicit) until -O2 is double-checked (if it turns out to matter).

  Daveed

David Vandevoorde a écrit :

I don't think those are _good_ reasons though: If one doesn't want a C+ + function to be inlined, one shouldn't define it inline.

You must not have written a lot of C++ template then. You don't have the choice in this case, just check your STL header.

FWIW, I've been involved in a couple of attempts by commercial compilers to relegate "inline" to the same status as "register" -- an obsolete hint ignored by the compiler -- and so far that always proved to be unpractical because some critical calls that were previously inlined were no longer being inlined after the change. (That's just annecdotal, of course: LLVM may have gotten good enough to make it practical. If that's the case, I still think it's too early to write C ++ code with that assumption.)
  
There is often a keyword force_inline or alwais_inline if needed

Cédric