June 29, 1998
We are pleased to announce that Mark Mitchell Consulting, as part of a continuing contract with the Accelerated Strategic Computing Initiative (ASCI) program at Los Alamos National Laboratory, has contributed a framework to improve alias analysis in the compiler. It is currently used to propagate alias information provided by the language front ends into the optimization passes of the compiler. Typically this information is based on the type assigned to an object by the programmer.
This code is an excellent complement to the "base address" alias analysis code contributed by John Carr last year. The compiler uses information from both Mark and John's contributions during its optimization passes to improve code.
Here's some code which shows the benefit of Mark's contribution:
double u_m; double v_m; typedef struct s { int n_m; double* x_m; double* a_m; double* b_m; } s; void f(struct s* s) { int i; for (i=0; i < s->n_m; ++i) s->x_m[i] = (u_m * s->a_m[i]) + (v_m * s->b_m[i]); }
This is a boiled-down C version of a C++ scientific computation
program. In the old days, the compiler would reload s->n_m
,
s->a_m
, s->b_m
, and s->x_m
inside
the loop, for fear that the store into s->x_m[i]
might have
altered them. Now, however, since s->x_m[i]
is a
double
, and s->a_m
is a double*
,
those loads are hoisted out of the loop. Here is a side by side comparison
of MIPS code generated for the loop.
OLD NEW .L8: sll $4,$5,3 addu $3,$4,$3 l.d $f1,0($3) l.d $f0,0($4) #nop #nop mul.d $f1,$f3,$f1 mul.d $f0,$f3,$f0 lw $2,12($6) # s->b_m #nop addu $2,$4,$2 l.d $f0,0($2) l.d $f1,0($5) #nop #nop mul.d $f0,$f2,$f0 mul.d $f1,$f2,$f1 lw $3,4($6) # s->x_m add.d $f1,$f1,$f0 addu $5,$5,8 addu $4,$4,$3 add.d $f0,$f0,$f1 addu $4,$4,8 s.d $f1,0($4) lw $2,0($6) # s->n_m addu $5,$5,1 addu $3,$3,1 slt $2,$5,$2 slt $2,$3,$7 s.d $f0,0($6) .set noreorder .set noreorder .set nomacro .set nomacro bnel $2,$0,.L8 bne $2,$0,.L8 lw $3,8($6) # s->a_m addu $6,$6,8
In addition to removal of redundant loads, the scheduler has more freedom to rearrange instructions to avoid pipeline stalls and the resulting code is scheduled better.
Mark will implement the C9x restrict
keyword using
this framework. In addition, we plan on using the framework Mark has
built to propagate aliasing information for memory references
generated by the compiler for prologue/epilogue code, register spills,
and other memory references.
To enable the new alias code use the argument -fstrict-aliasing; in the future this option will be enabled by default.
John's alias code will remain in the compiler as it provides another way to determine what memory addresses conflict. John's code attempts to track what base value is used by memory references. Depending on the base values it may be possible to determine that two memory references can not conflict. For example, memory references into the static store can not conflict with stack or heap accesses.
John's code actually tracks values as they migrate from one register to another or are altered in safe ways (for example, addition of a constant does not change a base value).
Copyright (C) Free Software Foundation, Inc. Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.
These pages are maintained by the GCC team. Last modified 2022-10-26.