Re: -fobey-inline (was Re: gcc and inlining)

[dewar at gnat dot com (Robert Dewar)]

> We can give users the choice.  In the past, "-finline-functions" let the
> compiler decide, and the "inline" keyword let the user decide.  There is
> no other possible use for the an "inline" keyword that makes any sense -
> if the compiler can randomly decide that it will override it, it is no
> longer serving a useful purpose [*]

That's an odd thing to say, given that both the Ada and the C standards find
that it serves a useful purpose even if the compiler can override. Of course
the randomly here is just rhetoric. You might as well say "if multiplication
can randomly be implemented by repeated addition, then it no longer serves
a useful purpose" [note that of course the language standard certainly permits
this implementation of multiplication].

What the inline keyword means is

"Speed is really important when calling this small function, you can if you
like use more space if it helps execution speed.

 I am guessing that a good idea would be to
inline the code at the point of each call and that this would help execution
speed. I base this guess on a naive view that the function likely generates
only a few instructions, so that the overhead of the instructions for
calling and returning will be significant, and this kind of inlining can
get rid of this overhead"

Now the compiler should react to this by actually doing the inlining if
indeed doing so can reasonbly be expected to improve execution time. But
there are a number of reasons why this may not be the case, often very
target dependent. Some examples:

  1. Increasing code space can increase instruction cache pressure, which
     is often a key element in execution efficiency.

  2. In some architectures, the call can help improve efficiency. For
     example, on the IBM 360, code has to be based, calling a function
     automatically bases the code, avoiding the need for allocating an
     extra base register and mucking with it.

  3. On some machines calls are particularly fast. For example, on the
     INMOS transputer, a call is remarkably fast, often close to free.

  4. A call is an unconditional jump, so is a simple return. On an
     architecture with good branch prediction and plenty of ILP it
     may well be the case that the call is operationally close to free

On the other side of the equation you have to worry about cache effects
requiring constant icache swapping. This occurs most often on a machine
with a one way direct icache. In fact this is such a potentially serious
effect that I would say that on such a machine, inline should almost
always be obeyed, but there are very few such machines around any more
(are there any?). Certainly a C programmer cannot be expected to mess
with inline directives based on the cache architecture, that sort of
thing is unreasonable and undesirable.

How does inline compare with register? The meaning of register is that
in the programmer's estimation, it is worth keeping a given variable in
a register. More accurately, the programmer is saying that references to
the variable will be frequent. Why do the above arguments for inline
not apply to register. Several reasons:

  Although we can enumerate the four points above, the fact of the matter
  is that the decision to inline is far more target independent than the
  selection of registers, which is so dependent on number of registers and
  ABI rules for register usage.

  Register allocation is for the most part a matter of local decision within
  a unit, whereas inlining is important across units. Compilers are rather
  good at decision making within a unit, much worse at interunit decisions.
  Indeed the best argument for register declarations is when they apply
  globally across units.

  We have really good algorithms in practice for figuring out what to put
  in registers. Partly this is because the problem is more studied than
  the inlining case, partly it is because it is more tractable.

  The register declaration is all or nothing, but a good compiler will
  decide to keep something in a register for some particular region
  of code and in memory for another part of the code.

So in practice, most compilers ignore register keywords, and I have not
seen programmers being outraged that their register variables are not
always in registers (they sure would get outraged a lot on the x86 if
they thought this, unless their code was desigfned for a PDP-11 :-)

It is indicative, as someone has pointed out, that the register keyword
was there early on in C compilers, allowing very small naive C compilers
to generate reasonable code without optimization or elaborate register
allocation algorithms.

On the other hand, the inline keyword is much more recent. Pragma Inline
has always been in Ada, and there was absolutely not even a slight
suggestion that it should be removed or deprecated in Ada 95, since in
practice it has proved very useful. It does not guarantee inlining, but
with reasonable Ada compilers that have appeared (including GNAT) it
does indeed provide a very useful tool for Ada programmers. There is the
additional issue in Ada of generating extra dependencies.

An interesting note is that in classical Ada compilers, you can only inline
from units that have already been compiled (analogous to the quite annoying
restriction of only inlining bodies that you have already seen). This means
that two mutually recursive packages cannot inline in both directions
(worse, the code you get depends on the order of compilation). In GNAT,
using the source based approach (for which we have rms to thank, see below)
we can fully respect inlining even in this mutually recursive case and the
code never depends on the order of compilation.

Robert

(post note). The source based approach in Ada comes from a discussion around
1991 with RMS. He was outraged at the idea that the meaning of a program
depended on the order of compilation. We patiently explained (thinking from
the point of view of a traditional library based Ada compiler, which the
Ada standard seems to expect) that this was required in Ada. Well RMS was
not the kind of person to be convinced that a point is wrong when the only
counter argument is to wave a standard around :-) He felt that not only
was it pragmatically undesirable that the meaning of a program depends on
the order of compilation, but also that it was fundamentally philosphically
unacceptable, since the result is that the sources of a program do not
embody its meaning without the additional non-source information of what
order to compile in. After a long to-and-fro discussion (which should
have been preserved but unfortunately was not) we devised the sources based
compilation approach and realized that it was as-if conformant to the Ada 83
standard (the Ada 95 standard has been rewritten to make this approach more
clearly conformant, and other Ada compilers have "borrowed" this source
based approach from GNAT :-)