Alias Analysis

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).