Compilers - Global versus Stack variables

Author

Global versus Stack variables

shrey

2005-11-19, 3:57 am

Hi all
I was wondering if ppl can give their opinion on the following
question. What is the impact of a variable being a global or a local
variable on optimizations. In other words, is it likelier to produce
better code if a variable is local than global. The reason I ask this
is I wonder if register allocation is harder if a variable is global
instead of local. Are there other optimizations which get affected due
to this consideration.

thanks
Shrey
[It depends on your language, but in languages with pointers, the
biggest advantage of stack locals is that the compiler can assume
no aliasing of stack variables that haven't had their address taken.
-John]

oliverhunt@gmail.com

2005-11-22, 4:00 am

shrey wrote:
> Hi all
> I was wondering if ppl can give their opinion on the following
> ...

There are a number of factors that effect the performance of locals and
globals:

* if you are targetting an architecture with enough registers (eg.
not an x86) it becomes possible to keep many locals inside registers,
and reduce the number of memory accesses, etc.

* Dependency and data flow analysis is more practical with local
variables as the compiler doesn't need to worry about the contained
values changing between function calls (same holds for concurrent
modification of variables). C bypasses these problems by assuming
everything is is effectively local (during dependency, etc analysis)
unless a var is declared volatile.

* It may be possible to read a fixed address global faster than a
local depending on architecture, but i would imagine the cache in most
architectures would destroy that advantage nowadays.

There are other things that effect performance, but the first two alone
should give locals a reasonable performance advantage (in my opinion
anyway :) )

> [It depends on your language, but in languages with pointers, the
> biggest advantage of stack locals is that the compiler can assume
> no aliasing of stack variables that haven't had their address taken.
> -John]
but they shouldn't in the happy world of C anything is possible :)
void foo()
{
int b[10], c;
c=5;
for(int i=0; i<=10; i++) b[i]=4;
if(c==4) //a good optimizer should probably
printf("Foo!");
}

Although yes, things like that are *probably* an error (and exceedingly
dependant on the order of vars on the stack) :)

--Oliver
[Things like that are definitely an error if your program purports to be
in ANSI C. -John]

glen herrmannsfeldt

2005-11-22, 4:00 am

shrey wrote:

> I was wondering if ppl can give their opinion on the following
> question. What is the impact of a variable being a global or a local
> variable on optimizations. In other words, is it likelier to produce
> better code if a variable is local than global. The reason I ask this
> is I wonder if register allocation is harder if a variable is global
> instead of local. Are there other optimizations which get affected due
> to this consideration.

> [It depends on your language, but in languages with pointers, the
> biggest advantage of stack locals is that the compiler can assume
> no aliasing of stack variables that haven't had their address taken.
> -John]

Note that Fortran assumes no aliasing in many cases where other
languages might not make that assumption. One common and confusing
case is multiple parameters to the same subroutine, where the compiler
is allowed to assume that they are not aliased.

Fortran does pointers different than other languages, so I am not sure
about the aliasing rules in that case.

As far as execution time, on some machines it takes more instructions,
or more machine cycles to reference a global variable, where they are
indirectly addressed using the appropriate code sequence. That takes
an extra register on some machines. (Load address of variable into a
register, then operate on the value addressed by the register.)

-- glen

Henry Spencer

2005-11-22, 4:00 am

shrey <shreyas76@gmail.com> wrote:
>...What is the impact of a variable being a global or a local
>variable on optimizations. In other words, is it likelier to produce
>better code if a variable is local than global...

Broadly speaking, the more the compiler knows about how and where a
variable is used, the better the code it can produce. Particularly in
compiler systems that support separate compilation, it's often very
difficult to do any real optimization involving global variables, because
when compiling any particular module/procedure/etc., the compiler doesn't
know the whole story of how the variable is used. It's usually much
easier for a compiler to know everything about a local variable.
--
spsystems.net is temporarily off the air; | Henry Spencer
mail to henry at zoo.utoronto.ca instead. | henry@spsystems.net

Torben Ægidius Mogensen

2005-11-22, 4:01 am

"shrey" <shreyas76@gmail.com> writes:

> I was wondering if ppl can give their opinion on the following
> question. What is the impact of a variable being a global or a local
> variable on optimizations. In other words, is it likelier to produce
> better code if a variable is local than global. The reason I ask this
> is I wonder if register allocation is harder if a variable is global
> instead of local. Are there other optimizations which get affected due
> to this consideration.

As John said, it depends on your language and your compiler. But in
C-like languages on modern CPU's (with modern compilers), local
variables tend to be register allocated (unless their address is
taken) where global variables are memory allocated. This means that
access to gobal variables usually require a memory reference, though a
function can sometimes make a temporary copy in a register and use
this for several accesses. It must write back before returning,
calling another function or accessing a variable that might be aliased
with the global variable.

Local variables sometimes also need to be stored across function
calls, though, but you can often reduce the need for this by expoiting
the caller-saves/callee-saves division of registers.

Torben

Jatin Bhateja

2005-11-26, 3:58 am

Hi,

>As John said, it depends on your language and your compiler. But in
>C-like languages on modern CPU's (with modern compilers), local
>variables tend to be register allocated (unless their address is
>taken) where global variables are memory allocated. This means that
>access to gobal variables usually require a memory reference, though a
>function can sometimes make a temporary copy in a register and use
>this for several accesses. It must write back before returning,
>calling another function or accessing a variable that might be aliased
>with the global variable.

I feel that accessing both local and global variables requires some memory
access, but it again depends on the architecture and complier.

Kindly consider the following code

#include "stdio.h"

int i = 10;

int main() {
i = i + 75;
return i;
}

Now consider the assembly corresponding to it (Turbo compiler)

__DATA segment word public 'DATA'
_i label word
dw 10
_DATA ends
_TEXT segment byte public 'CODE'
; ?debug L 5
_main proc near
; ?debug L 6
mov ax,word ptr DGROUP:_i #<---- Here we can see that some memory
access to data segment is made initially
add ax,75
mov word ptr DGROUP:_i,ax
; ?debug L 7
mov ax,word ptr DGROUP:_i
jmp short @1
@1:
; ?debug L 8
ret
_main endp
_TEXT ends

Similarly consider following code snippet

#include "stdio.h"

int main() {
int i = 10;
i = i + 75;
return i;
}

Consider the assembly corresponding to it (Turbo compiler)

_TEXT segment byte public 'CODE
; ?debug L 3
_main proc near
push si#<--- Here we directly allocate the register to the
corresponding local (i).
; ?debug L 4
mov si,10
; ?debug L 5
mov ax,si
add ax,75
mov si,ax
; ?debug L 6
mov ax,si
jmp short @1
@1:
; ?debug L 7
pop si
ret
_main endp
_TEXT ends

But when the number of locals are more for eg. Consider the following code
snippet

#include "stdio.h"

int main() {
int i = 10,j=6,k=6,l=5
i = i + j + k + l;
return i;
}

Consider its assembly

_TEXT segment byte public 'CODE'
; ?debug L 3
_main proc near
push bp
mov bp,sp
sub sp,4
push si
push di
; ?debug L 4
mov si,10 #<--- i and j are allocated registers
mov di,6
mov word ptr [bp-4],6 #<----- k and l are accessed from stack.
mov word ptr [bp-2],5
; ?debug L 5
mov ax,si
add ax,di
add ax,word ptr [bp-4]
add ax,word ptr [bp-2]
mov si,ax
; ?debug L 6
mov ax,si
jmp short @1
@1:
; ?debug L 7
pop di
pop si
mov sp,bp
pop bp
ret
_main endp
_TEXT ends

Thus if the architecture does not have large number of GPRs (general purpose
registers)
then the locals are assigned the correct offset in the activation record and
when the activation record is pushed onto the stack then access to these
locals are made by using the base (frame pointer) + offset mechanism thus
memory access is made.

Thanks and Best Regards,
_
Jatin Bhateja
Subject Matter Expert

Mohd Hanafiah Abdullah

2005-11-26, 3:58 am

shrey <shreyas76@gmail.com> wrote:
> I was wondering if ppl can give their opinion on the following
>question. What is the impact of a variable being a global or a local
>variable on optimizations. In other words, is it likelier to produce
>better code if a variable is local than global. The reason I ask this
>is I wonder if register allocation is harder if a variable is global
>instead of local. Are there other optimizations which get affected due
>to this consideration.

>[It depends on your language, but in languages with pointers, the
>biggest advantage of stack locals is that the compiler can assume
>no aliasing of stack variables that haven't had their address taken.
>-John]

And for local variables you need to do some cost-analysis in order to not
over-allocate them to registers. Sometime it's better to keep them in memory
instead of registers if there are too many instances of calls to functions
that will require saving the register content in memory (callee/caller saves)
each time. This register-moves cost-analysis is explained in the paper by
Fred Chow and John Hennessy on Priority-based Graph Coloring Register
Allocation technique.

To allocate global variables to registers requires inter-module alias analysis
(for separate compilation) which I haven't tried. With faster CPU and memory
nowadays the performance gap between saving data in registers vs memory is
getting very narrow. But, there will always be instances where fast is better
than less fast, especially in hard real-time systems requirements.

Napi
--
http://www.axiomsol.com
http://www.cs.indiana.edu/hyplan/napi.html

Dave Thompson

2005-12-05, 3:57 am

On 21 Nov 2005 22:40:47 -0500, "oliverhunt@gmail.com"
<oliverhunt@gmail.com> wrote:

> * Dependency and data flow analysis is more practical with local
> variables as the compiler doesn't need to worry about the contained
> values changing between function calls (same holds for concurrent

It needs to worry _less_ about hidden changes. In algolian languages
other than C's immediate family, if a routine P calls its child C, or
another descendant S of P does so, locals in P can change.

> modification of variables). C bypasses these problems by assuming
> everything is is effectively local (during dependency, etc analysis)
> unless a var is declared volatile.

If by 'effectively local' you mean unaliasable, not true. Classical C
(following BCPL) assumed a classic global memory; standard C adds only
the restriction that accesses must use the correct type (within small
variations such as unsigned versus signed integer of the same rank)
_or_ a character (which in C means byte) type. E.g. an 'int' pointer
target (or object) can be assumed nonaliased with a 'float' one.

'volatile' was originally intended for things like memory-mapped I/O,
and may also be useful for multi-threading and particularly
multi-processing, although most if not all threading schemes (now)
have their own memory controls instead.

The 99 revision adds a new type of pointer qualification 'restrict'
which explicitly promises something is not aliased, effectively like
Fortran dummies/formals but for actual variables as well.

<snip>
> int b[10], c;
> c=5;
> for(int i=0; i<=10; i++) b[i]=4;
> if(c==4) //a good optimizer should probably
> printf("Foo!");

A barely adequate optimizer should put c in a register or elide it
entirely and _not_ print Foo. And probably b[] and the loop, since
there are provably no reads from it in this trivial case.

Aside: standard C allows an implementation to require (because some
platforms do) that the last output to a text file, which stdout is,
end with a newline \n. But your example wasn't a whole program, and
this is irrelevant to the point at issue.

> Although yes, things like that are *probably* an error (and exceedingly
> dependant on the order of vars on the stack) :)
>
And alignment. Or more generally layout.

> --Oliver
> [Things like that are definitely an error if your program purports to be
> in ANSI C. -John]

Right. Or even just portable C, since stack layout has always been up
to the implementation and has in fact varied.

- David.Thompson1 at worldnet.att.net

Sponsored Links