Using may-alias information

©1997 by Andrew W. Appel

Supplement to the books,

Modern Compiler Implementation in ML Modern Compiler Implementation in C Modern Compiler Implementation in Java

Suppose we have the following program: 

1:    t := p + 12
2:    u := M[t]
3:    M[x] := r
4:    v := p + 12
5:    w := M[v]
6:    a := u+w
First we can perform common-subexpression elimination, using the expression p+12 that is available at line 4: 
1a:    z := p + 12
1b:    t := z
2:    u := M[t]
3:    M[x] := r
4:    v := z
5:    w := M[v]
6:    a := u+w
Lines 1b and 4 can be removed by copy propagation: 
1a:    z := p + 12
2:    u := M[z]
3:    M[x] := r
5:    w := M[z]
6:    a := u+w
Without alias analysis, line 3 would kill the availability of the expression M[z], and we could not eliminate the redundant load instruction.

But suppose alias analysis determines that z may-alias x at 3 is false. Then M[z] is available at line 5, and we can perform common subexpression elimination (followed by copy propagation) to get: 

1a:    z := p + 12
2:    u := M[z]
3:    M[x] := r
6:    a := u+u