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