stack grow direction wrongly detected

stack grow direction wrongly detected

[Marco Atzeri]

Hi Guys,
noted trying to rebuild guile 1.8.8.

The following piece of code in the past
was setting SCM_I_GSC_STACK_GROWS_UP=0
and now produces SCM_I_GSC_STACK_GROWS_UP=1

I assume some change in the gcc compiler is causing the issue.
I presume most of the programs and libraries do not care,
but some special one like guile crashes during build for this issue,
so be aware.

Regards
Marco


#--------------------------------------------------------------------
#
# Which way does the stack grow?
#
# Following code comes from Autoconf 2.61's internal _AC_LIBOBJ_ALLOCA
# macro (/usr/share/autoconf/autoconf/functions.m4).  Gnulib has
# very similar code, so in future we could look at using that.
#
# An important detail is that the code involves find_stack_direction
# calling _itself_ - which means that find_stack_direction (or at
# least the second find_stack_direction() call) cannot be inlined.
# If the code could be inlined, that might cause the test to give
# an incorrect answer.
#--------------------------------------------------------------------

SCM_I_GSC_STACK_GROWS_UP=0
AC_RUN_IFELSE([AC_LANG_SOURCE(
[AC_INCLUDES_DEFAULT
int
find_stack_direction ()
{
   static char *addr = 0;
   auto char dummy;
   if (addr == 0)
     {
       addr = &dummy;
       return find_stack_direction ();
     }
   else
     return (&dummy > addr) ? 1 : -1;
}

int
main ()
{
   return find_stack_direction () < 0;
}])],
                [SCM_I_GSC_STACK_GROWS_UP=1],
                [],
                [AC_MSG_WARN(Guessing that stack grows down -- see 
scmconfig.h)])

Re: stack grow direction wrongly detected

[Takashi Yano]

On Fri, 5 Mar 2021 13:18:38 +0100
Marco Atzeri wrote:
> Hi Guys,
> noted trying to rebuild guile 1.8.8.
> 
> The following piece of code in the past
> was setting SCM_I_GSC_STACK_GROWS_UP=0
> and now produces SCM_I_GSC_STACK_GROWS_UP=1
> 
> I assume some change in the gcc compiler is causing the issue.
> I presume most of the programs and libraries do not care,
> but some special one like guile crashes during build for this issue,
> so be aware.
> 
> Regards
> Marco
> 
> 
> #--------------------------------------------------------------------
> #
> # Which way does the stack grow?
> #
> # Following code comes from Autoconf 2.61's internal _AC_LIBOBJ_ALLOCA
> # macro (/usr/share/autoconf/autoconf/functions.m4).  Gnulib has
> # very similar code, so in future we could look at using that.
> #
> # An important detail is that the code involves find_stack_direction
> # calling _itself_ - which means that find_stack_direction (or at
> # least the second find_stack_direction() call) cannot be inlined.
> # If the code could be inlined, that might cause the test to give
> # an incorrect answer.
> #--------------------------------------------------------------------
> 
> SCM_I_GSC_STACK_GROWS_UP=0
> AC_RUN_IFELSE([AC_LANG_SOURCE(
> [AC_INCLUDES_DEFAULT
> int
> find_stack_direction ()
> {
>    static char *addr = 0;
>    auto char dummy;
>    if (addr == 0)
>      {
>        addr = &dummy;
>        return find_stack_direction ();
>      }
>    else
>      return (&dummy > addr) ? 1 : -1;
> }
> 
> int
> main ()
> {
>    return find_stack_direction () < 0;
> }])],
>                 [SCM_I_GSC_STACK_GROWS_UP=1],
>                 [],
>                 [AC_MSG_WARN(Guessing that stack grows down -- see 
> scmconfig.h)])

This seems to be a result of optimization. With gcc v10.2.0,
the return value of the code is:
-O0: 1
-O1: 1
-O2: 0
-O3: 1
-O4: 1

If find_stack_direction() is implemented as recursive call,
and auto variable is allocated in the stack every time,
in the first call, addr is initialized to the first stack
position, and in the second call, second address of dummy
is reduced because stack of x86 is reverse direction.
Therefore (&dummy > addr) ? 1 : -1; returns -1.
As a result, the return value find_stack_direction() < 0
is 1. With -O0 or -O1 this implemented as recursive call,
so the return value is 1.

So, IIUC, the setting SCM_I_GSC_STACK_GROUS_UP is completly
oposite.

With the following modified code,

#include <stdio.h>
int
find_stack_direction (int n)
{
  static char *addr = 0;
  char dummy;
  printf("%p\n", &dummy);
  if (addr == 0)
    addr = &dummy;
  if (n)
    return find_stack_direction (n - 1);
  else
    return (&dummy > addr) ? 1 : -1;
}

int
main ()
{
  int ret = find_stack_direction (10) < 0;
  printf("%d\n", ret);
  return ret;
}

the result with -O0 is
0x62cc2f
0x62cbff
0x62cbcf
0x62cb9f
0x62cb6f
0x62cb3f
0x62cb0f
0x62cadf
0x62caaf
0x62ca7f
0x62ca4f
1

This looks very reasonable. However, with -O2
0x62cc3d
0x62cc3e
0x62cc3f
0x62cc0d
0x62cc0e
0x62cc0f
0x62cbdd
0x62cbde
0x62cbdf
0x62cbad
0x62cbae
1

This is very strange. The address is not decreased uniformly.

Therefore, using -O0 and setting SCM_I_GSC_STACK_GROUS_UP
reversely is the right thing, I think.

-- 
Takashi Yano <takashi.yano@nifty.ne.jp>

Re: stack grow direction wrongly detected

[gs-cygwin.com]

On Fri, Mar 05, 2021 at 11:31:04PM +0900, Takashi Yano via Cygwin wrote:
> On Fri, 5 Mar 2021 13:18:38 +0100
> Marco Atzeri wrote:
> > Hi Guys,
> > noted trying to rebuild guile 1.8.8.
> > 
> > The following piece of code in the past
> > was setting SCM_I_GSC_STACK_GROWS_UP=0
> > and now produces SCM_I_GSC_STACK_GROWS_UP=1
> > 
> > I assume some change in the gcc compiler is causing the issue.
> > I presume most of the programs and libraries do not care,
> > but some special one like guile crashes during build for this issue,
> > so be aware.
> > 
> > Regards
> > Marco
> > 
> > 
> > #--------------------------------------------------------------------
> > #
> > # Which way does the stack grow?
> > #
> > # Following code comes from Autoconf 2.61's internal _AC_LIBOBJ_ALLOCA
> > # macro (/usr/share/autoconf/autoconf/functions.m4).  Gnulib has
> > # very similar code, so in future we could look at using that.
> > #
> > # An important detail is that the code involves find_stack_direction
> > # calling _itself_ - which means that find_stack_direction (or at
> > # least the second find_stack_direction() call) cannot be inlined.
> > # If the code could be inlined, that might cause the test to give
> > # an incorrect answer.
> > #--------------------------------------------------------------------
> > 
> > SCM_I_GSC_STACK_GROWS_UP=0
> > AC_RUN_IFELSE([AC_LANG_SOURCE(
> > [AC_INCLUDES_DEFAULT
> > int
> > find_stack_direction ()
> > {
> >    static char *addr = 0;
> >    auto char dummy;
> >    if (addr == 0)
> >      {
> >        addr = &dummy;
> >        return find_stack_direction ();
> >      }
> >    else
> >      return (&dummy > addr) ? 1 : -1;
> > }
> > 
> > int
> > main ()
> > {
> >    return find_stack_direction () < 0;
> > }])],
> >                 [SCM_I_GSC_STACK_GROWS_UP=1],
> >                 [],
> >                 [AC_MSG_WARN(Guessing that stack grows down -- see 
> > scmconfig.h)])
> 
> This seems to be a result of optimization. With gcc v10.2.0,
> the return value of the code is:
> -O0: 1
> -O1: 1
> -O2: 0
> -O3: 1
> -O4: 1
> 
> If find_stack_direction() is implemented as recursive call,
> and auto variable is allocated in the stack every time,
> in the first call, addr is initialized to the first stack
> position, and in the second call, second address of dummy
> is reduced because stack of x86 is reverse direction.
> Therefore (&dummy > addr) ? 1 : -1; returns -1.
> As a result, the return value find_stack_direction() < 0
> is 1. With -O0 or -O1 this implemented as recursive call,
> so the return value is 1.

If the compiler is gcc or clang:

__attribute__(__noinline__)
int
find_stack_direction ()
{
...
}

Cheers, Glenn

Re: stack grow direction wrongly detected

[Thomas Wolff]

Am 05.03.2021 um 15:31 schrieb Takashi Yano via Cygwin:
> On Fri, 5 Mar 2021 13:18:38 +0100
> Marco Atzeri wrote:
>> Hi Guys,
>> noted trying to rebuild guile 1.8.8.
>>
>> The following piece of code in the past
>> was setting SCM_I_GSC_STACK_GROWS_UP=0
>> and now produces SCM_I_GSC_STACK_GROWS_UP=1
>>
>> I assume some change in the gcc compiler is causing the issue.
>> I presume most of the programs and libraries do not care,
>> but some special one like guile crashes during build for this issue,
>> so be aware.
>>
>> Regards
>> Marco
>>
>>
>> #--------------------------------------------------------------------
>> #
>> # Which way does the stack grow?
>> #
>> # Following code comes from Autoconf 2.61's internal _AC_LIBOBJ_ALLOCA
>> # macro (/usr/share/autoconf/autoconf/functions.m4).  Gnulib has
>> # very similar code, so in future we could look at using that.
>> #
>> # An important detail is that the code involves find_stack_direction
>> # calling _itself_ - which means that find_stack_direction (or at
>> # least the second find_stack_direction() call) cannot be inlined.
>> # If the code could be inlined, that might cause the test to give
>> # an incorrect answer.
>> #--------------------------------------------------------------------
>>
>> SCM_I_GSC_STACK_GROWS_UP=0
>> AC_RUN_IFELSE([AC_LANG_SOURCE(
>> [AC_INCLUDES_DEFAULT
>> int
>> find_stack_direction ()
>> {
>>     static char *addr = 0;
>>     auto char dummy;
>>     if (addr == 0)
>>       {
>>         addr = &dummy;
>>         return find_stack_direction ();
>>       }
>>     else
>>       return (&dummy > addr) ? 1 : -1;
>> }
>>
>> int
>> main ()
>> {
>>     return find_stack_direction () < 0;
>> }])],
>>                  [SCM_I_GSC_STACK_GROWS_UP=1],
>>                  [],
>>                  [AC_MSG_WARN(Guessing that stack grows down -- see
>> scmconfig.h)])
> This seems to be a result of optimization. With gcc v10.2.0,
> the return value of the code is:
> -O0: 1
> -O1: 1
> -O2: 0
> -O3: 1
> -O4: 1
>
> If find_stack_direction() is implemented as recursive call,
> and auto variable is allocated in the stack every time,
> in the first call, addr is initialized to the first stack
> position, and in the second call, second address of dummy
> is reduced because stack of x86 is reverse direction.
> Therefore (&dummy > addr) ? 1 : -1; returns -1.
> As a result, the return value find_stack_direction() < 0
> is 1. With -O0 or -O1 this implemented as recursive call,
> so the return value is 1.
>
> So, IIUC, the setting SCM_I_GSC_STACK_GROUS_UP is completly
> oposite.
>
> With the following modified code,
>
> #include <stdio.h>
> int
> find_stack_direction (int n)
> {
>    static char *addr = 0;
>    char dummy;
>    printf("%p\n", &dummy);
>    if (addr == 0)
>      addr = &dummy;
>    if (n)
>      return find_stack_direction (n - 1);
>    else
>      return (&dummy > addr) ? 1 : -1;
> }
>
> int
> main ()
> {
>    int ret = find_stack_direction (10) < 0;
>    printf("%d\n", ret);
>    return ret;
> }
>
> the result with -O0 is
> 0x62cc2f
> 0x62cbff
> 0x62cbcf
> 0x62cb9f
> 0x62cb6f
> 0x62cb3f
> 0x62cb0f
> 0x62cadf
> 0x62caaf
> 0x62ca7f
> 0x62ca4f
> 1
>
> This looks very reasonable. However, with -O2
> 0x62cc3d
> 0x62cc3e
> 0x62cc3f
> 0x62cc0d
> 0x62cc0e
> 0x62cc0f
> 0x62cbdd
> 0x62cbde
> 0x62cbdf
> 0x62cbad
> 0x62cbae
> 1
>
> This is very strange. The address is not decreased uniformly.
>
> Therefore, using -O0 and setting SCM_I_GSC_STACK_GROUS_UP
> reversely is the right thing, I think.
>
The function calls for tail recursion optimization, so it's not really 
suitable to make observations on recursion.
However, with real tail recursion easily performed, the address of the 
local variable should actually not change at all, unlike here. The 
reason for that is beyond me.

Re: stack grow direction wrongly detected

[Brian Inglis]

On 2021-03-05 05:18, Marco Atzeri via Cygwin wrote:
> Hi Guys,
> noted trying to rebuild guile 1.8.8.
> 
> The following piece of code in the past
> was setting SCM_I_GSC_STACK_GROWS_UP=0
> and now produces SCM_I_GSC_STACK_GROWS_UP=1
> 
> I assume some change in the gcc compiler is causing the issue.
> I presume most of the programs and libraries do not care,
> but some special one like guile crashes during build for this issue,
> so be aware.
> 
> Regards
> Marco
> 
> 
> #--------------------------------------------------------------------
> #
> # Which way does the stack grow?
> #
> # Following code comes from Autoconf 2.61's internal _AC_LIBOBJ_ALLOCA
> # macro (/usr/share/autoconf/autoconf/functions.m4).  Gnulib has
> # very similar code, so in future we could look at using that.
> #
> # An important detail is that the code involves find_stack_direction
> # calling _itself_ - which means that find_stack_direction (or at
> # least the second find_stack_direction() call) cannot be inlined.
> # If the code could be inlined, that might cause the test to give
> # an incorrect answer.
> #--------------------------------------------------------------------
> 
> SCM_I_GSC_STACK_GROWS_UP=0
> AC_RUN_IFELSE([AC_LANG_SOURCE(
> [AC_INCLUDES_DEFAULT
> int
> find_stack_direction ()
> {
>    static char *addr = 0;
>    auto char dummy;
>    if (addr == 0)
>      {
>        addr = &dummy;
>        return find_stack_direction ();
>      }
>    else
>      return (&dummy > addr) ? 1 : -1;
> }
> 
> int
> main ()
> {
>    return find_stack_direction () < 0;
> }])],
>                 [SCM_I_GSC_STACK_GROWS_UP=1],
>                 [],
>                 [AC_MSG_WARN(Guessing that stack grows down -- see scmconfig.h)])

Report it upstream to guile and [better] autoconf for correction - suggest a 
patch or not as you feel appropriate.

It's an issue that the code does not assume --push and pop++ as that is the 
common implementation -- then do adequate due diligence to inhibit optimizations 
that avoid stack usage, eliminate tail recursion, and generate inline code, to 
prove the opposite. Some implementations (used to?) not natively support or use 
stacks and emulated them with dynamically allocated memory blocks.

I am surprised that this has not occurred previously, and wonder if someone 
recently replaced, eliminated, or "optimized" code, or some necessary settings, 
that allow such autoconf tests to do their jobs properly.

We all love the advantage such transformations provide our code at large compile 
time and space costs, but most are unaware of the effort that detection code 
like the above now has to go thru to avoid being rendered useless.

-- 
Take care. Thanks, Brian Inglis, Calgary, Alberta, Canada

This email may be disturbing to some readers as it contains
too much technical detail. Reader discretion is advised.
[Data in binary units and prefixes, physical quantities in SI.]

Re: stack grow direction wrongly detected

[Marco Atzeri]

On 05.03.2021 19:58, Brian Inglis wrote:
> On 2021-03-05 05:18, Marco Atzeri via Cygwin wrote:
>> Hi Guys,
>> noted trying to rebuild guile 1.8.8.
>>
>> The following piece of code in the past
>> was setting SCM_I_GSC_STACK_GROWS_UP=0
>> and now produces SCM_I_GSC_STACK_GROWS_UP=1
>>
>> I assume some change in the gcc compiler is causing the issue.
>> I presume most of the programs and libraries do not care,
>> but some special one like guile crashes during build for this issue,
>> so be aware.
>>
>> Regards
>> Marco
>>
>>
>> #--------------------------------------------------------------------
>> #
>> # Which way does the stack grow?
>> #
>> # Following code comes from Autoconf 2.61's internal _AC_LIBOBJ_ALLOCA
>> # macro (/usr/share/autoconf/autoconf/functions.m4).  Gnulib has
>> # very similar code, so in future we could look at using that.
>> #
>> # An important detail is that the code involves find_stack_direction
>> # calling _itself_ - which means that find_stack_direction (or at
>> # least the second find_stack_direction() call) cannot be inlined.
>> # If the code could be inlined, that might cause the test to give
>> # an incorrect answer.
>> #--------------------------------------------------------------------
>>
>> SCM_I_GSC_STACK_GROWS_UP=0
>> AC_RUN_IFELSE([AC_LANG_SOURCE(
>> [AC_INCLUDES_DEFAULT
>> int
>> find_stack_direction ()
>> {
>>    static char *addr = 0;
>>    auto char dummy;
>>    if (addr == 0)
>>      {
>>        addr = &dummy;
>>        return find_stack_direction ();
>>      }
>>    else
>>      return (&dummy > addr) ? 1 : -1;
>> }
>>
>> int
>> main ()
>> {
>>    return find_stack_direction () < 0;
>> }])],
>>                 [SCM_I_GSC_STACK_GROWS_UP=1],
>>                 [],
>>                 [AC_MSG_WARN(Guessing that stack grows down -- see 
>> scmconfig.h)])
> 
> Report it upstream to guile and [better] autoconf for correction - 
> suggest a patch or not as you feel appropriate.
> 
> It's an issue that the code does not assume --push and pop++ as that is 
> the common implementation -- then do adequate due diligence to inhibit 
> optimizations that avoid stack usage, eliminate tail recursion, and 
> generate inline code, to prove the opposite. Some implementations (used 
> to?) not natively support or use stacks and emulated them with 
> dynamically allocated memory blocks.
> 
> I am surprised that this has not occurred previously, and wonder if 
> someone recently replaced, eliminated, or "optimized" code, or some 
> necessary settings, that allow such autoconf tests to do their jobs 
> properly.


guile 1.8.8 is 10 years old, but it is still used by some programs
as all the guile 2.x series were slower.
the code on recent guile 3.0.x is different, with no recursion at all.

SCM_I_GSC_STACK_GROWS_UP=0
AC_RUN_IFELSE([AC_LANG_SOURCE(
[AC_INCLUDES_DEFAULT
int
find_stack_direction (int *addr, int depth)
{
   int dir, dummy = 0;
   if (! addr)
     addr = &dummy;
   *addr = addr < &dummy ? 1 : addr == &dummy ? 0 : -1;
   dir = depth ? find_stack_direction (addr, depth - 1) : 0;
   return dir + dummy;
}

int
main (int argc, char **argv)
{
   return find_stack_direction (0, argc + !argv + 20) < 0;
}])],


> We all love the advantage such transformations provide our code at large 
> compile time and space costs, but most are unaware of the effort that 
> detection code like the above now has to go thru to avoid being rendered 
> useless.

it is always impossible to guess in which direction programming
paradigms evolve, due to the large number of elements involved.
But testing for functionality remain much more resistent to hard coded 
solution.

Regards
Marco

Re: stack grow direction wrongly detected

[Takashi Yano]

On Fri, 5 Mar 2021 21:29:49 +0100
Marco Atzeri wrote:
> guile 1.8.8 is 10 years old, but it is still used by some programs
> as all the guile 2.x series were slower.
> the code on recent guile 3.0.x is different, with no recursion at all.
> 
> SCM_I_GSC_STACK_GROWS_UP=0
> AC_RUN_IFELSE([AC_LANG_SOURCE(
> [AC_INCLUDES_DEFAULT
> int
> find_stack_direction (int *addr, int depth)
> {
>    int dir, dummy = 0;
>    if (! addr)
>      addr = &dummy;
>    *addr = addr < &dummy ? 1 : addr == &dummy ? 0 : -1;
>    dir = depth ? find_stack_direction (addr, depth - 1) : 0;
                   ^^^^^^^^^^^^^^^^^^^^
This calls find_stack_direction() recursively, isn't it?

>    return dir + dummy;
> }
> 
> int
> main (int argc, char **argv)
> {
>    return find_stack_direction (0, argc + !argv + 20) < 0;
> }])],

Recursion depth seems to be increased to more than 20.

-- 
Takashi Yano <takashi.yano@nifty.ne.jp>

Re: stack grow direction wrongly detected

[Marco Atzeri]

On 05.03.2021 15:43, gs-cygwin.com@gluelogic.com wrote:
> On Fri, Mar 05, 2021 at 11:31:04PM +0900, Takashi Yano via Cygwin wrote:
>> On Fri, 5 Mar 2021 13:18:38 +0100
>> Marco Atzeri wrote:
>>> Hi Guys,
>>> noted trying to rebuild guile 1.8.8.
>>>
>>> The following piece of code in the past
>>> was setting SCM_I_GSC_STACK_GROWS_UP=0
>>> and now produces SCM_I_GSC_STACK_GROWS_UP=1
>>>
>>> I assume some change in the gcc compiler is causing the issue.
>>> I presume most of the programs and libraries do not care,
>>> but some special one like guile crashes during build for this issue,
>>> so be aware.
>>>
>>> Regards
>>> Marco
>>>

> 
> If the compiler is gcc or clang:
> 
> __attribute__(__noinline__)

thanks Glenn,

as
__attribute__((__noinline__))

it seems to work
for all variant of -Ox

> int
> find_stack_direction ()
> {
> ...
> }
> 
> Cheers, Glenn

Regards
Marco

Re: stack grow direction wrongly detected

[Marco Atzeri]

On 06.03.2021 02:06, Takashi Yano via Cygwin wrote:
> On Fri, 5 Mar 2021 21:29:49 +0100
> Marco Atzeri wrote:

>>     dir = depth ? find_stack_direction (addr, depth - 1) : 0;
>                     ^^^^^^^^^^^^^^^^^^^^
> This calls find_stack_direction() recursively, isn't it?

yeah. Never write when tired ...

> 
>>     return dir + dummy;
>> }
>>
>> int
>> main (int argc, char **argv)
>> {
>>     return find_stack_direction (0, argc + !argv + 20) < 0;
>> }])],
> 
> Recursion depth seems to be increased to more than 20.

probably to produce a portable result without going inline

Re: stack grow direction wrongly detected

[Thomas Wolff]

Am 06.03.2021 um 09:29 schrieb Marco Atzeri via Cygwin:
> On 05.03.2021 15:43, gs-cygwin.com@gluelogic.com wrote:
>> On Fri, Mar 05, 2021 at 11:31:04PM +0900, Takashi Yano via Cygwin wrote:
>>> On Fri, 5 Mar 2021 13:18:38 +0100
>>> Marco Atzeri wrote:
>>>> Hi Guys,
>>>> noted trying to rebuild guile 1.8.8.
>>>>
>>>> The following piece of code in the past
>>>> was setting SCM_I_GSC_STACK_GROWS_UP=0
>>>> and now produces SCM_I_GSC_STACK_GROWS_UP=1
>>>>
>>>> I assume some change in the gcc compiler is causing the issue.
>>>> I presume most of the programs and libraries do not care,
>>>> but some special one like guile crashes during build for this issue,
>>>> so be aware.
>>>>
>>>> Regards
>>>> Marco
>>>>
>
>>
>> If the compiler is gcc or clang:
>>
>> __attribute__(__noinline__)
>
> thanks Glenn,
>
> as
> __attribute__((__noinline__))
>
> it seems to work
> for all variant of -Ox
>
>> int
>> find_stack_direction ()
>> {
>> ...
>> }
>>
>> Cheers, Glenn
Can somebody explain the weird behaviour previously described, address 
of the char going up 1 byte a few times, then skipping down, etc, and 
why recursive calls are affected at all by inline, and what gcc thinks 
it can optimize in that case?