criteria for aliasing proposals

[Bill Homer]

One of the action items from the September session on aliasing was to
develop a list of criteria against which to judge proposals.  Linda
Stanberry was kind enough to get the ball rolling by submitting a list
which reflected, to the best of her knowledge, the opinions of
colleagues at her site.  I edited that list, added more items, and
asked Tom MacDonald and other interested parties here at Cray to review
it.  They felt the version below would serve as a basis for discussion by
readers of this mailing list.  If we can arrive at a consensus, I will
prepare a draft for distribution at the next meeting.

Bill Homer		Cray Research, Inc.
(612) 683-5606		655F Lone Oak Drive
homeracray.com		Eagan, MN 55121


	Criteria for a solution to the aliasing problem

The problem:

    In C, aliasing through pointers inhibits many compiler optimizations,
    yet pointers must be used to pass array arguments to functions and for
    dynamically allocated storage (and pointers are preferred by some
    programmers even when not required).

The solution should:

1.  Allow effective alias analysis for an isolated function with
    uses of pointers including (roughly in descending order of priority)
    a.  pointer parameters
    b.  pointers explicitly used to form aliases (e.g., temporary
	pointers used to step through arrays)
    c.  pointers in structures, unions, and arrays
    d.  file scope pointers
    e.  block scope pointers (including blocks from function inlining)

2.  Be based on a simple yet general concept.
    a.  Have a precise specification with no subtleties or surprises. 
    b.  Be applicable to different contexts in a consistent manner.
    c.  Be consistent with the semantics of the library memory management
	and string handling functions.

3.  Express appropriate non-aliasing assertions.
    a.  Apply both within loops and outside loops.
    b.  Reflect the principle that what matters for optimization is
	the aliasing of modified objects.
    c.  Avoid restrictions that do not yield opportunities for
	optimization.
    d.  Be compatible with (possibly incomplete) information obtained
	from interprocedural analysis.
 
4.  Be portable, in two senses:
    a.  Aim to be supported by all vendors who address the aliasing problem,
	i.e., minimize the incentive to support other solutions (apart from
	continued support for preexisting vendor constructs).  See point 5.
    b.  Permit a natural style of use that is easily ported to environments
	which do not support this solution.

5.  Minimize the cost of implementation.
    a.  Have a simple syntax.
    b.  Allow levels of support, with relatively inexpensive
	implementations for the lower levels.
    c.  Be independent of other issues (such as array syntax).

6.  Be analogous to the Fortran 77 restrictions on association of
    entities through dummy arguments, for the benefit of:
    a.  Programmers who know, or program in, both languages.
    b.  Compilers for the two languages which share optimization
	phases.