-Wstack-usage and alloca in loops

[Dmitry Antipov]

For the following translation unit:

#include stdlib.h

int
foo (unsigned n)
{
  int *p;

  if (n  1024)
p = alloca (n * sizeof (int));
  else
p = malloc (n * sizeof (int));

  return g (p, n);
}

int
bar (unsigned n)
{
  int x, i, *p;

  for (x = 0, i = 0; i  n; i++)
{
  if (n  1024)
p = alloca (n * sizeof (int));
  else
p = malloc (n * sizeof (int));

  x += h (p, n);

  if (n = 1024)
free (p);
}

  return x;
}

compiling with -Wstack-usage=32 produces (as of 4.9.1):

test.c: In function 'foo':
test.c:14:1: warning: stack usage might be unbounded [-Wstack-usage=]
 }
 ^
test.c: In function 'bar':
test.c:35:1: warning: stack usage might be unbounded [-Wstack-usage=]
 }
 ^

1) I'm just curious why it's unbounded for foo().  It shouldn't be too
hard to find that alloca() is never requested to allocate more than
1024 * sizeof (int), and never called more than once, isn't it?

2) In bar(), stack usage is unbounded unless bar() is always inline with
a compile-time constant argument N.

IIUC good detection of 2) is much harder to implement, but is it
reasonable/possible to make -Wstack-usage more accurate in 1)?

Dmitry

Re: -Wstack-usage and alloca in loops

[Jeff Law]

On 09/22/14 09:56, Dmitry Antipov wrote:

For the following translation unit:

#include stdlib.h

int
foo (unsigned n)
{
   int *p;

   if (n  1024)
 p = alloca (n * sizeof (int));
   else
 p = malloc (n * sizeof (int));

   return g (p, n);
}

int
bar (unsigned n)
{
   int x, i, *p;

   for (x = 0, i = 0; i  n; i++)
 {
   if (n  1024)
 p = alloca (n * sizeof (int));
   else
 p = malloc (n * sizeof (int));

   x += h (p, n);

   if (n = 1024)
 free (p);
 }

   return x;
}

compiling with -Wstack-usage=32 produces (as of 4.9.1):

test.c: In function 'foo':
test.c:14:1: warning: stack usage might be unbounded [-Wstack-usage=]
  }
  ^
test.c: In function 'bar':
test.c:35:1: warning: stack usage might be unbounded [-Wstack-usage=]
  }
  ^

1) I'm just curious why it's unbounded for foo().  It shouldn't be too
hard to find that alloca() is never requested to allocate more than
1024 * sizeof (int), and never called more than once, isn't it?

2) In bar(), stack usage is unbounded unless bar() is always inline with
a compile-time constant argument N.

IIUC good detection of 2) is much harder to implement, but is it
reasonable/possible to make -Wstack-usage more accurate in 1)?
The implementation of -Wstack-usage is a bit lame in that it does not do 
any flow analysis or tie into the range information computed by VRP.


In  the first example it sees an dynamic alloca and considers the 
allocation potentially unbounded -- even though range information would 
indicate that n  1024 and thus the total allocation is  1024 * sizeof 
(int).


Moving the stack usage computation into its own analysis phase which has 
access to VRP bounds and such would be a a significant improvement and 
one which I think would be quite useful.


Jeff

Re: -Wstack-usage and alloca in loops

[Eric Botcazou]

 The implementation of -Wstack-usage is a bit lame in that it does not do
 any flow analysis or tie into the range information computed by VRP.

Right, that was by design in order to be conservatively correct.  May I remind 
you of where we came from with -Wframe-larger-than? :-)

 Moving the stack usage computation into its own analysis phase which has
 access to VRP bounds and such would be a a significant improvement and
 one which I think would be quite useful.

Yes, provided the outcome is still guaranteed to be conservatively correct.

-- 
Eric Botcazou