Inlining fails on very simple code

Inlining fails on very simple code

[degger]

[-- Attachment #1: Type: TEXT/plain, Size: 1028 bytes --]

Hija,

I've just discovered a strange phenomenon on ppc-gnu-linux 
and a trunk gcc from 3 days ago: The attached preprocessed
code contains an idct code with 3 functions:
One to calculate an IDCT row, one for a column and one
to put them together.

Although the row and column code is specified to be static inline
and called exactly in one place there's no option on earth
I can convince gcc to inline it although it is clearly a win
situation as it removes the function call overhead and it is used 
exactly once which is a fact that gcc knows (or at least has the chance
to). I would have suspected that gcc uses the opportunity to at least
spare the overhead for the call if not even beat the crap out of this
situation and optimize over the border of the call.

Indeed if I directly move the codeblock in the row and col functions 
directly into the loops the compiler does a much better job which
results in a smaller objectfile and 15% faster execution. 

Anyone having an idea what's going on?

--
Servus,
       Daniel

[-- Attachment #2: simple_idct.i --]
[-- Type: TEXT/plain, Size: 7930 bytes --]

# 1 "simple_idct.c"
# 1 "<builtin>"
# 1 "<command line>"
# 1 "simple_idct.c"
# 23 "simple_idct.c"
# 1 "/usr/include/inttypes.h" 1 3
# 26 "/usr/include/inttypes.h" 3
# 1 "/usr/include/features.h" 1 3
# 283 "/usr/include/features.h" 3
# 1 "/usr/include/sys/cdefs.h" 1 3
# 284 "/usr/include/features.h" 2 3
# 312 "/usr/include/features.h" 3
# 1 "/usr/include/gnu/stubs.h" 1 3
# 313 "/usr/include/features.h" 2 3
# 27 "/usr/include/inttypes.h" 2 3

# 1 "/usr/include/stdint.h" 1 3
# 28 "/usr/include/stdint.h" 3
# 1 "/opt/gcc-7400/lib/gcc-lib/powerpc-unknown-linux-gnu/3.1/include/stddef.h" 1 3
# 293 "/opt/gcc-7400/lib/gcc-lib/powerpc-unknown-linux-gnu/3.1/include/stddef.h" 3
typedef long int wchar_t;
# 29 "/usr/include/stdint.h" 2 3
# 1 "/usr/include/bits/wchar.h" 1 3
# 30 "/usr/include/stdint.h" 2 3
# 1 "/usr/include/bits/wordsize.h" 1 3
# 31 "/usr/include/stdint.h" 2 3
# 39 "/usr/include/stdint.h" 3
typedef signed char int8_t;
typedef short int int16_t;
typedef int int32_t;



__extension__
typedef long long int int64_t;




typedef unsigned char uint8_t;
typedef unsigned short int uint16_t;

typedef unsigned int uint32_t;





__extension__
typedef unsigned long long int uint64_t;






typedef signed char int_least8_t;
typedef short int int_least16_t;
typedef int int_least32_t;



__extension__
typedef long long int int_least64_t;



typedef unsigned char uint_least8_t;
typedef unsigned short int uint_least16_t;
typedef unsigned int uint_least32_t;



__extension__
typedef unsigned long long int uint_least64_t;






typedef signed char int_fast8_t;





typedef int int_fast16_t;
typedef int int_fast32_t;
__extension__
typedef long long int int_fast64_t;



typedef unsigned char uint_fast8_t;





typedef unsigned int uint_fast16_t;
typedef unsigned int uint_fast32_t;
__extension__
typedef unsigned long long int uint_fast64_t;
# 128 "/usr/include/stdint.h" 3
typedef int intptr_t;


typedef unsigned int uintptr_t;
# 140 "/usr/include/stdint.h" 3
__extension__
typedef long long int intmax_t;
__extension__
typedef unsigned long long int uintmax_t;
# 29 "/usr/include/inttypes.h" 2 3
# 260 "/usr/include/inttypes.h" 3

# 274 "/usr/include/inttypes.h" 3
typedef struct
  {
    long long int quot;
    long long int rem;
  } imaxdiv_t;





extern intmax_t imaxabs (intmax_t __n) __attribute__ ((__const__));


extern imaxdiv_t imaxdiv (intmax_t __numer, intmax_t __denom)
      __attribute__ ((__const__));


extern intmax_t strtoimax (__const char *__restrict __nptr,
                           char **__restrict __endptr, int __base) ;


extern uintmax_t strtoumax (__const char * __restrict __nptr,
                            char ** __restrict __endptr, int __base) ;


extern intmax_t wcstoimax (__const wchar_t * __restrict __nptr,
                           wchar_t **__restrict __endptr, int __base) ;


extern uintmax_t wcstoumax (__const wchar_t * __restrict __nptr,
                            wchar_t ** __restrict __endptr, int __base) ;
# 374 "/usr/include/inttypes.h" 3
__extension__
extern long long int __strtoll_internal (__const char *__restrict __nptr,
                                         char **__restrict __endptr,
                                         int __base, int __group) ;


extern __inline intmax_t
strtoimax (__const char *__restrict nptr, char **__restrict endptr,
           int base)
{
  return __strtoll_internal (nptr, endptr, base, 0);
}



__extension__
extern unsigned long long int __strtoull_internal (__const char *
                                                   __restrict __nptr,
                                                   char **
                                                   __restrict __endptr,
                                                   int __base,
                                                   int __group) ;


extern __inline uintmax_t
strtoumax (__const char *__restrict nptr, char **__restrict endptr,
           int base)
{
  return __strtoull_internal (nptr, endptr, base, 0);
}



__extension__
extern long long int __wcstoll_internal (__const wchar_t *
                                         __restrict __nptr,
                                         wchar_t **__restrict __endptr,
                                         int __base, int __group) ;


extern __inline intmax_t
wcstoimax (__const wchar_t *__restrict nptr, wchar_t **__restrict endptr,
           int base)
{
  return __wcstoll_internal (nptr, endptr, base, 0);
}




__extension__
extern unsigned long long int __wcstoull_internal (__const wchar_t *
                                                   __restrict __nptr,
                                                   wchar_t **
                                                   __restrict __endptr,
                                                   int __base,
                                                   int __group) ;


extern __inline uintmax_t
wcstoumax (__const wchar_t *__restrict nptr, wchar_t **__restrict endptr,
           int base)
{
  return __wcstoull_internal (nptr, endptr, base, 0);
}





# 24 "simple_idct.c" 2

# 1 "simple_idct.h" 1
# 19 "simple_idct.h"
void simple_idct(short *block);
void simple_idct_mmx(short *block);
# 26 "simple_idct.c" 2
# 49 "simple_idct.c"
static inline void
idctRow (int16_t * row)
{
        int a0, a1, a2, a3, b0, b1, b2, b3;
        const int C1 =22725;
        const int C2 =21407;
        const int C3 =19266;
        const int C4 =16384;
        const int C5 =12873;
        const int C6 =8867;
        const int C7 =4520;

        if( !(row[1] | row[2] |row[3] |row[4] |row[5] |row[6] | row[7])) {
                row[0] = row[1] = row[2] = row[3] = row[4] =
                        row[5] = row[6] = row[7] = row[0]<<3;
                return;
        }

        a0 = C4*row[0] + C2*row[2] + C4*row[4] + C6*row[6] + (1<<(11 -1));
        a1 = C4*row[0] + C6*row[2] - C4*row[4] - C2*row[6] + (1<<(11 -1));
        a2 = C4*row[0] - C6*row[2] - C4*row[4] + C2*row[6] + (1<<(11 -1));
        a3 = C4*row[0] - C2*row[2] + C4*row[4] - C6*row[6] + (1<<(11 -1));

        b0 = C1*row[1] + C3*row[3] + C5*row[5] + C7*row[7];
        b1 = C3*row[1] - C7*row[3] - C1*row[5] - C5*row[7];
        b2 = C5*row[1] - C1*row[3] + C7*row[5] + C3*row[7];
        b3 = C7*row[1] - C5*row[3] + C3*row[5] - C1*row[7];

        row[0] = (a0 + b0) >> 11;
        row[1] = (a1 + b1) >> 11;
        row[2] = (a2 + b2) >> 11;
        row[3] = (a3 + b3) >> 11;
        row[4] = (a3 - b3) >> 11;
        row[5] = (a2 - b2) >> 11;
        row[6] = (a1 - b1) >> 11;
        row[7] = (a0 - b0) >> 11;
}

static inline void
idctCol (int16_t * col)
{
        int a0, a1, a2, a3, b0, b1, b2, b3;
        const int C1 =22725;
        const int C2 =21407;
        const int C3 =19266;
        const int C4 =16384;
        const int C5 =12873;
        const int C6 =8867;
        const int C7 =4520;






        col[0] += (1<<(20 -1))/16384;
        a0 = C4*col[8*0] + C2*col[8*2] + C4*col[8*4] + C6*col[8*6];
        a1 = C4*col[8*0] + C6*col[8*2] - C4*col[8*4] - C2*col[8*6];
        a2 = C4*col[8*0] - C6*col[8*2] - C4*col[8*4] + C2*col[8*6];
        a3 = C4*col[8*0] - C2*col[8*2] + C4*col[8*4] - C6*col[8*6];

        b0 = C1*col[8*1] + C3*col[8*3] + C5*col[8*5] + C7*col[8*7];
        b1 = C3*col[8*1] - C7*col[8*3] - C1*col[8*5] - C5*col[8*7];
        b2 = C5*col[8*1] - C1*col[8*3] + C7*col[8*5] + C3*col[8*7];
        b3 = C7*col[8*1] - C5*col[8*3] + C3*col[8*5] - C1*col[8*7];

        col[8*0] = (a0 + b0) >> 20;
        col[8*1] = (a1 + b1) >> 20;
        col[8*2] = (a2 + b2) >> 20;
        col[8*3] = (a3 + b3) >> 20;
        col[8*4] = (a3 - b3) >> 20;
        col[8*5] = (a2 - b2) >> 20;
        col[8*6] = (a1 - b1) >> 20;
        col[8*7] = (a0 - b0) >> 20;
}

void simple_idct (short *block)
{
        int i;
        for(i=0; i<8; i++)
                idctRow(block + 8*i);

        for(i=0; i<8; i++)
                idctCol(block + i);

}

Re: Inlining fails on very simple code

[Andreas Schwab]

degger@fhm.edu writes:

|> Hija,
|> 
|> I've just discovered a strange phenomenon on ppc-gnu-linux 
|> and a trunk gcc from 3 days ago: The attached preprocessed
|> code contains an idct code with 3 functions:
|> One to calculate an IDCT row, one for a column and one
|> to put them together.
|> 
|> Although the row and column code is specified to be static inline
|> and called exactly in one place there's no option on earth
|> I can convince gcc to inline it

Please try --param max-inline-insns=xxx, default is 600.

Andreas.

-- 
Andreas Schwab                                  "And now for something
Andreas.Schwab@suse.de				completely different."
SuSE Labs, SuSE GmbH, Schanzäckerstr. 10, D-90443 Nürnberg
Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5

Re: Inlining fails on very simple code

[degger]

On 10 Dec, Andreas Schwab wrote:

> |> Although the row and column code is specified to be static inline
> |> and called exactly in one place there's no option on earth
> |> I can convince gcc to inline it
 
> Please try --param max-inline-insns=xxx, default is 600.

From my understanding gcc should inline whenever it seems benefitial.
To tell gcc where the programmer sees the border the above mentioned
option was introduced however with the knowledge that a static inline
function is used exactly once there should be no doubt about what might
be benefitial or not.

--
Servus,
       Daniel

Re: Inlining fails on very simple code

[degger]

On 11 Dec, Alexandre Oliva wrote:

> The fact that a function is used only once could only be used to
> decide whether to inline it if we did a global analysis of the
> program.  We don't have infrastructure in place for this kind of
> analysis, since we often emit code for functions before having seen
> the whole program.

I understand. This also explains why I had troubles to find the spot
where gcc tries to analyse how often a function is used. Would it be
possible to use the bitfield variable behind the TREE_USED macro to
count the number of callers or would that already be to late for
the treeinliner to work with that data? Also I think it might be
benefitial to generally inline the tree if the inline keyword is
given or the inlining criteria are met but also keep the copy of
the function alone around, do the optimisation passes on the code with
the inlined function and both the callee and caller alone and then
compare them and decide whether the glued code shows an improvement
over both functions alone. It seems to me that mr. Hubicka and mr.
Zlomek are trying that for loops and general statement; duplicating
code and checking for improvements that is.

--
Servus,
       Daniel 

Re: Inlining fails on very simple code

[Alexandre Oliva]

On Dec 10, 2001, degger@fhm.edu wrote:

> From my understanding gcc should inline whenever it seems benefitial.
> To tell gcc where the programmer sees the border the above mentioned
> option was introduced however with the knowledge that a static inline
> function is used exactly once there should be no doubt about what might
> be benefitial or not.

The fact that a function is used only once could only be used to
decide whether to inline it if we did a global analysis of the
program.  We don't have infrastructure in place for this kind of
analysis, since we often emit code for functions before having seen
the whole program.

-- 
Alexandre Oliva   Enjoy Guarana', see http://www.ic.unicamp.br/~oliva/
Red Hat GCC Developer                  aoliva@{cygnus.com, redhat.com}
CS PhD student at IC-Unicamp        oliva@{lsd.ic.unicamp.br, gnu.org}
Free Software Evangelist    *Please* write to mailing lists, not to me

Re: Inlining fails on very simple code

[Alexandre Oliva]

On Dec 11, 2001, degger@fhm.edu wrote:

> Would it be possible to use the bitfield variable behind the
> TREE_USED macro to count the number of callers or would that already
> be to late for the treeinliner to work with that data?

Well, considering that it's a single bit, you wouldn't be able to take
much information out of it.  Besides, it would only be sensible to use
it after you get the whole translation unit processed, and GCC emits
code for functions *before* it gets the whole translation unit.

Also, sometimes optimizing a function may get you rid of references to
other functions (think unreachable code), and then, you'd have to
somehow go back and update the counter, or risk making imperfect
choices.

> Also I think it might be benefitial to generally inline the tree if
> the inline keyword is given or the inlining criteria are met but
> also keep the copy of the function alone around, do the optimisation
> passes on the code with the inlined function and both the callee and
> caller alone and then compare them and decide whether the glued code
> shows an improvement over both functions alone.

And what if you have n function calls that you could inline, do you
try 2^n combinations of inlining, optimize them all the way through to
assembly code, and then pick the best?  This may indeed get you a
compiler that generates fast code, but it's going to be unbearably
slow.

-- 
Alexandre Oliva   Enjoy Guarana', see http://www.ic.unicamp.br/~oliva/
Red Hat GCC Developer                  aoliva@{cygnus.com, redhat.com}
CS PhD student at IC-Unicamp        oliva@{lsd.ic.unicamp.br, gnu.org}
Free Software Evangelist    *Please* write to mailing lists, not to me

Re: Inlining fails on very simple code

[degger]

On 11 Dec, Alexandre Oliva wrote:

>> Would it be possible to use the bitfield variable behind the
>> TREE_USED macro to count the number of callers or would that already
>> be to late for the treeinliner to work with that data?
 
> Well, considering that it's a single bit, you wouldn't be able to take
> much information out of it.

I should have been a bit more verbose. Of course I was thinking of using
a complete type instead of the bit to do the counting. From what I've
seen it wouldn't even break existing code...

> Besides, it would only be sensible to use it after you get the whole
> translation unit processed, and GCC emits code for functions *before*
> it gets the whole translation unit.

That's what I feared, thanks for clarifying this.

> Also, sometimes optimizing a function may get you rid of references to
> other functions (think unreachable code), and then, you'd have to
> somehow go back and update the counter, or risk making imperfect
> choices.

So you don't think it's possible to reverse the growth of the counter?

> And what if you have n function calls that you could inline, do you
> try 2^n combinations of inlining, optimize them all the way through to
> assembly code, and then pick the best?

What about a depth limitation here to prevent exponential growth? If a
developer or user really wants superoptimized code she/he could simply
increase that limit, wait half a day and get the best distilled code 
gcc can come up with.

> This may indeed get you a compiler that generates fast code, but it's
> going to be unbearably slow.

After all the current inlining code and the heuristic limit has some
severe drawbacks: There's probably no code on earth for which the limit
will be right; set it to low and the compiler will miss important
opportunities to speedup the code, set it to high and you'll have
bloated applications with suboptimal performance due to cache trashing
and number increased memory accesses. And what's even worse: If you have
more then just a pathetic testcase there's no chance to get it right
because modifying the limits will likely improve efficiency there while
deterioriating it in another place.

Still, I have no clue why I cannot get gcc to inline the functions in
the mentioned code since 
a) it is declared inline
b) I use -O3 (which enables -finline-functions)
c) I use -Winline and don't get a warning that they couldn't be inlined
d) gcc 2.95.3 does inline it when using -O3

gccs doc says:
"If all calls to a given function are integrated, and the function is
declared @code{static}, then the function is normally not output as
assembler code in its own right." for -finline-functions.

And it also says:
"Defining inline functions (as fast as macros)."
which is simply not true because I cannot force gcc to inline 
the function without increasing the general limit which I cannot
afford while with macros (although ugly) I can exactly control
which code I'd like to have expanded where. Maybe we can introduce some
__attribute__ ((i_really_want_this_inline)) to get the desired effect
of finegrained control if the compiler cannot be made clever enough
to even catch simple and obvious win cases.

--
Servus,
       Daniel 

Re: Inlining fails on very simple code

[Peter Barada]

>And it also says:
>"Defining inline functions (as fast as macros)."
>which is simply not true because I cannot force gcc to inline 
>the function without increasing the general limit which I cannot
>afford while with macros (although ugly) I can exactly control
>which code I'd like to have expanded where. Maybe we can introduce some
>__attribute__ ((i_really_want_this_inline)) to get the desired effect
>of finegrained control if the compiler cannot be made clever enough
>to even catch simple and obvious win cases.

From section 4.32 of the documentation (version 2.95):

If you specify both 'inline' and 'extern' in the fuction definition,
then the definition used only for inlining.  In no case is the
function compiled on its own, not even if you refer to its address
explicitly.  Such an address becomes an external reference, as if you
had only declared the function, and had not defined it.


-- 
Peter Barada                                   Peter.Barada@motorola.com
Wizard                                         781-852-2768 (direct)
WaveMark Solutions(wholly owned by Motorola)   781-270-0193 (fax)

RE: Inlining fails on very simple code

[Bernard Dautrevaux]

> -----Original Message-----
> From: Peter Barada [mailto:pbarada@mail.wm.sps.mot.com]
> Sent: Wednesday, December 12, 2001 4:37 PM
> To: degger@fhm.edu
> Cc: aoliva@redhat.com; gcc@gcc.gnu.org
> Subject: Re: Inlining fails on very simple code
> 
> 
> 
> >And it also says:
> >"Defining inline functions (as fast as macros)."
> >which is simply not true because I cannot force gcc to inline 
> >the function without increasing the general limit which I cannot
> >afford while with macros (although ugly) I can exactly control
> >which code I'd like to have expanded where. Maybe we can 
> introduce some
> >__attribute__ ((i_really_want_this_inline)) to get the desired effect
> >of finegrained control if the compiler cannot be made clever enough
> >to even catch simple and obvious win cases.
> 
> From section 4.32 of the documentation (version 2.95):
> 
> If you specify both 'inline' and 'extern' in the fuction definition,
> then the definition used only for inlining.  In no case is the
> function compiled on its own, not even if you refer to its address
> explicitly.  Such an address becomes an external reference, as if you
> had only declared the function, and had not defined it.


True, but that does not help FORCING gcc to inline the function: if it can't
inline it it generates it, but never emit the code but expect that some
magic was used to have it emit elsewhere like compiling just the extern
inline declaration after #defining inline as empty :-)

In fact I think the problem is that one parameter (max-inline-insns) is used
for two purposes:

1) Limiting the size of functions the compiler will decide *by itself* to
inline (that is functions that were NOT declared as inline, but nevertheless
expanded inline as this seems beneficial). For this use we must keep a
reasonably low value for max-inline-insns or we get uncontrolled code bloat.

2) Limiting the absolute size of any inline function. In fact here I think
GCC is trying to be smarter than the programmer: even while the programmer
says that he wants the function to be inlined, GCC thinks it knows better
and refuse to do it if the function is bigger than max-inline-insns.

IMHO use (1) is a Good Thing (TM) while (2) is at least debatable; if we
think it's needed then we should have two parameters:
max-automatic-inline-insns, that would take care of case (1), while
max-inline-insns will be used for case (2). In this case I would suggest
keeping the actual max-inline-insns default for max-automatic-inline-insns
and use a much bigger default for max-inline-insns.

This would in fact bring what was expected: by default only small enough
functions are auto-inlined but only very big/complex one can't be; and we
can adjust both limits, takeing into account the fact that an explicit
"inline" keyword, if used, indicates the programmer expect inlining to be a
win.


--------------------------------------------
Bernard Dautrevaux
Microprocess Ingenierie
97 bis, rue de Colombes
92400 COURBEVOIE
FRANCE
Tel:	+33 (0) 1 47 68 80 80
Fax:	+33 (0) 1 47 88 97 85
e-mail:	dautrevaux@microprocess.com
		b.dautrevaux@usa.net
--------------------------------------------