Alias-free Parameters in C for Better Reasoning and Optimization
				  by
		 Medhat G. Assaad and Gary T. Leavens

			       Abstract

Aliasing among formal parameters and among formals and globals causes
problems for both reasoning and optimization.  Whole-program static
analysis could provide some knowledge about such aliasing, but this is
not usually done, and in any case would have to be conservative.  All
aliasing patterns that are not ruled out by an analysis have to be
considered possible both by a person reasoning about correctness and
by a compiler trying to optimize code.  For compilers, the
conservative nature of the static analysis leads to missed
optimization opportunities.

We have designed and implemented a small extension to C that partially
solves the reasoning problem and leads to significantly better
optimization.  The extension guarantees that there will be no direct
aliasing among arguments and globals inside procedure bodies, and yet
allows aliasing among arguments and globals at the call site.  This is
done by having multiple bodies for each procedure, up to one for each
aliasing pattern.  Procedure calls are automatically dispatched to the
body that matches the run-time aliasing pattern among the actual
parameters and the globals.

We present experimental evidence that this approach is practical.  It
is easy to convert existing C code, because not every procedure in a
program has to be converted, and because converted code can call code
that has not been converted and vice versa.  By following simple
guidelines, one can convert a program in a way that usually makes it
run faster than before.  In our experiments with 6 of the SPEC 2000
integer benchmarks we found an average speedup of about 5%.  In one
case, we had a speedup of about 29%.


Keywords: Aliasing, multibody procedures, dynamic dispatch, static dispatch,
program verification, alias-free programs, compiler optimizations, ACL
approach, C/ACL language, C language.

2000 CR Categories:
D.2.4 [Software Engineering]
	Software/Program Verificaiton --- formal methods;
D.3.3 [Programming Languages]
	Language Constructs and Features --- control structures,
        procedures, functions, and subroutines;
D.3.4 [Programming Languages]
	Processors --- compilers, measurement, optimization, 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;
F.3.3 [Logics and Meanings of Programs]
        Studies of Program Constructs ---
                control primitives, functional constructs.