Alias-free parameters in C using multibodies
                                    by
                           Medhat Galal Assaad
                          Iowa State University

                                 Abstract

Aliasing may cause problems for both optimization and reasoning about programs.
Since static alias analysis is expensive, and sometimes, even impossible, 
compilers tend to be conservative. This usually leads to missing some 
optimization opportunities. Furthermore, when trying to understand code, one 
must consider all possible aliasing patterns. This can make reasonning about 
code difficult and non-trivial.

We have implemented an approach for having alias-free parameters in C.  This 
approach allows aliasing between the arguments at the call site, but 
guarantees that there will be no aliasing between arguments and between 
arguments and globals inside procedure bodies.  This is done by having 
multiple bodies, up to one for each aliasing pattern.  Procedure calls will be 
dispatched to the body that matches the aliasing pattern at the call site.  By 
having alias-free parameters in the bodies, good optimization can be achieved.
Furthermore, verification and reasoning about the code is easier when there is 
no aliasing.  The main advantages of our approach are that code to determine 
the aliasing pattern is automatically generated, and the programmer does not 
have to code it by hand.

We tested our implementation, and found that using this approach can be very 
practical. It is easy to convert already-existing code to use it. And in some 
cases, we had run-time execution speedup as much as 29%.

keywords: pointer parameter aliasing, global variable aliasing, multi-body 
          procedures, dynamic dispatch, static dispatch, ACL language, 
          C/ACL, alias-free programs, compiler opti-mizations, GCC.

2000 CR Categories: 
D.3.1 [Programming Languages] 
      Formal Definitions and Theory --- sematics; 
D.3.3 [Programming Languages] 
      Language Constructs and Features ---  control structures, procedures, 
      functions, and subroutines; 
D.3.4 [Programming Languages] 
      Processors --- compilers, optimization, experimentation, performance; 
D.3.m [Programming Languages] 
      Miscellaneous --- dynamic dispatch, multiple dispatch; 
F.3.1 [Logics and Meanings of Programs] 
      Specifying and Verifying and Reasoning about Programs --- logics of 
      programs.

Copyright (c) 2001 by Medhat G. Assaad