Using `const int' values to size stack arrays

Using `const int' values to size stack arrays

[Daniel Towner]

Hi all,

If I have a variable which I declare in one of the following ways:

  const int MAX_VAL = 12;

or

  static const int MAX_VAL = 12;

and I subsequently use it in expressions, gcc will substitute the value 
`12' wherever MAX_VAL appears, but not in the following case:

void someFn()
{
 int someArray[MAX_VAL];

  // etc...
}

In this case, `someArray' will be treated as a variable sized array, 
with subsequent performance impact. Why can't gcc treat it as an array 
which has 12 elements? Is this a gcc limitation, or a fundamental 
limitation of C?

thanks,

dan.

============================================================================
Daniel Towner
picoChip Designs Ltd., Riverside Buildings, 108, Walcot Street, BATH,
BA1 5BG
daniel.towner@picochip.com
07786 702589 

Re: Using `const int' values to size stack arrays

[Nathan Sidwell]

Daniel Towner wrote:
> Hi all,
> 
> If I have a variable which I declare in one of the following ways:
> 
>  const int MAX_VAL = 12;
> 
> or
> 
>  static const int MAX_VAL = 12;
> 
> and I subsequently use it in expressions, gcc will substitute the value 
> `12' wherever MAX_VAL appears, but not in the following case:
> 
> void someFn()
> {
> int someArray[MAX_VAL];
> 
>  // etc...
> }
> 
> In this case, `someArray' will be treated as a variable sized array, 
> with subsequent performance impact. Why can't gcc treat it as an array 
> which has 12 elements? Is this a gcc limitation, or a fundamental 
> limitation of C?

I presume we're talking C here, and gnu C at that.
MAX_VAL is not an integral constant expression, so int ary[MAX_VAL]
must be a VLA, if it is valid.

C89 disallows both uses,
C99 disallows VLAs at file scope, but allows them at function scope.
GNU C is similar to C99.

In C++, MAX_VAL _is_ an integral constant expression.

nathan


-- 
Nathan Sidwell    ::   http://www.codesourcery.com   ::     CodeSourcery LLC
nathan@codesourcery.com    ::     http://www.planetfall.pwp.blueyonder.co.uk

Re: Using `const int' values to size stack arrays

[Robert Dewar]

Nathan Sidwell wrote:

> I presume we're talking C here, and gnu C at that.
> MAX_VAL is not an integral constant expression, so int ary[MAX_VAL]
> must be a VLA, if it is valid.
> 
> C89 disallows both uses,
> C99 disallows VLAs at file scope, but allows them at function scope.
> GNU C is similar to C99.

Of course, since GNU C allows dynamic arrays, it does allow this
construct, and given that it is allowed, it is perfectly reasonable
to ask that the compiler do this efficiently and not actually treat
it as dynamic at the implementation level (even if it is dynamic at
the semantic level).

Re: Using `const int' values to size stack arrays

[Daniel Towner]

Robert Dewar wrote:

>> I presume we're talking C here, and gnu C at that.
>> MAX_VAL is not an integral constant expression, so int ary[MAX_VAL]
>> must be a VLA, if it is valid.
>>
>> C89 disallows both uses,
>> C99 disallows VLAs at file scope, but allows them at function scope.
>> GNU C is similar to C99.
>
>
> Of course, since GNU C allows dynamic arrays, it does allow this
> construct, and given that it is allowed, it is perfectly reasonable
> to ask that the compiler do this efficiently and not actually treat
> it as dynamic at the implementation level (even if it is dynamic at
> the semantic level).

Absolutely. My port of gcc generates code which initialises a memory 
variable with the value 12, and then in the body of the code which 
handles the variable length array, loads that value into a register, and 
does all the appropriate arithmetic on it (some example code is shown 
below). Can the code not be optimised at the instruction level, so that 
it would recognise that the memory value will always be 12, so the load 
from memory will always be 12, and hence  copy propogation could remove 
large chunks of code?

The main requirement for such an optimisation seems to be whether the 
optimiser can recognise that the load from memory will always be a 
constant value. If the original symbol was declared as `const int', or 
`static const int', and that int is written to memory, can its value 
ever be different to 12? I think that it is allowed to change if the 
variable was marked as volatile, but in the other cases I would have 
thought it could have been optimised?

thanks,

dan

---------------------

Example code. Note that after the initial load from memory all 
subsequent operations could be removed through constant propogation:

.section .data
_MAX_VAL:
.word 12          // Can this value ever change?

.section .text

_main:
        COPY.0 &_MAX_VAL,R5          // Get address of MAX_VAL
        LDW (R5)0,R5                 // R5 now contains constant `12'
        COPY.0 0,R0
        STW R14,(FP)-4
        SUB.0 FP,-(-8),FP
        ADD.0 R5,R5,R5               // Multiply by 2
        STW R3,(FP)1
        ADD.0 R5,6,R5                // Add 6
        COPY.1 FP,R4
        AND.0 R5, -4, R5             // Mask
        ADD.0 FP,R5,FP               // Change FP by constant value.
        etc...

============================================================================
Daniel Towner
picoChip Designs Ltd., Riverside Buildings, 108, Walcot Street, BATH,
BA1 5BG
daniel.towner@picochip.com
07786 702589 

Re: Using `const int' values to size stack arrays

[Robert Dewar]

Daniel Towner wrote:

> Absolutely. My port of gcc generates code which initialises a memory 
> variable with the value 12, and then in the body of the code which 
> handles the variable length array, loads that value into a register, and 
> does all the appropriate arithmetic on it (some example code is shown 
> below). Can the code not be optimised at the instruction level, so that 
> it would recognise that the memory value will always be 12, so the load 
> from memory will always be 12, and hence  copy propogation could remove 
> large chunks of code?
> 
> The main requirement for such an optimisation seems to be whether the 
> optimiser can recognise that the load from memory will always be a 
> constant value. If the original symbol was declared as `const int', or 
> `static const int', and that int is written to memory, can its value 
> ever be different to 12? I think that it is allowed to change if the 
> variable was marked as volatile, but in the other cases I would have 
> thought it could have been optimised?

This is certainly a possible optimization, but a bit of a marginal one,
since it only comes into play with a GNU C extension that we know is
very little used.

Re: Using `const int' values to size stack arrays

[Nathan Sidwell]

Daniel Towner wrote:

> Absolutely. My port of gcc generates code which initialises a memory 
> variable with the value 12, and then in the body of the code which 
> handles the variable length array, loads that value into a register, and 
> does all the appropriate arithmetic on it (some example code is shown 
> below). Can the code not be optimised at the instruction level, so that 
> it would recognise that the memory value will always be 12, so the load 
> from memory will always be 12, and hence  copy propogation could remove 
> large chunks of code?
sorry, I missed this point of your email.  I don't think we can arbitrarily
remove the dynamic allocation of a VLA, because I think the following
is required to work

static const int SIZE = SOME_HUGE_VALUE_THAT_CAUSES_STACK_OVERFLOW;

void Foo ()
{
   if (SOME_EXPR_THAT_IS_FALSE_AT_RUNTIME)
     {
	char ary[SIZE];
     }
}

If ary was promoted to a regular array, and therefore stack-frame
allocated at compile time, this function would fail when called, rather
than fail when the if block is entered.  (A pathelogical example)

> The main requirement for such an optimisation seems to be whether the 
> optimiser can recognise that the load from memory will always be a 
> constant value. If the original symbol was declared as `const int', or 
> `static const int', and that int is written to memory, can its value 
> ever be different to 12? I think that it is allowed to change if the 
> variable was marked as volatile, but in the other cases I would have 
> thought it could have been optimised?



> ---------------------
> 
> Example code. Note that after the initial load from memory all 
> subsequent operations could be removed through constant propogation:
what version of gcc is your port based on? Does the current development
tree do better?

I notice that MAX_VAL has been placed in .data, not .rodata -- is that
your port, or does GCC not think it constant?

nathan

-- 
Nathan Sidwell    ::   http://www.codesourcery.com   ::     CodeSourcery LLC
nathan@codesourcery.com    ::     http://www.planetfall.pwp.blueyonder.co.uk

Re: Using `const int' values to size stack arrays

[Robert Dewar]

Nathan Sidwell wrote:

> sorry, I missed this point of your email.  I don't think we can arbitrarily
> remove the dynamic allocation of a VLA, because I think the following
> is required to work
> 
> static const int SIZE = SOME_HUGE_VALUE_THAT_CAUSES_STACK_OVERFLOW;
> 
> void Foo ()
> {
>   if (SOME_EXPR_THAT_IS_FALSE_AT_RUNTIME)
>     {
>     char ary[SIZE];
>     }
> }
> 
> If ary was promoted to a regular array, and therefore stack-frame
> allocated at compile time, this function would fail when called, rather
> than fail when the if block is entered.  (A pathelogical example)

OK, so if this pathology is worrying you, limit the optimization to cases
where the array is "small" (after all these are cases where the compiler
does in fact know the size :-)

Re: Using `const int' values to size stack arrays

[Daniel Towner]

>>
> what version of gcc is your port based on? Does the current development
> tree do better?

Its based on 3.4.0. I've run the same example through 3.4.3 on the x86 
port and it doesn't seem to do any better.

> I notice that MAX_VAL has been placed in .data, not .rodata -- is that
> your port, or does GCC not think it constant? 

Hmm. Not sure. I haven't told the port that the .rodata section exists, 
so maybe it defaults to .data?

regards,

dan.

============================================================================
Daniel Towner
picoChip Designs Ltd., Riverside Buildings, 108, Walcot Street, BATH,
BA1 5BG
daniel.towner@picochip.com
07786 702589