Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!mips!dimacs.rutgers.edu!rutgers!modus!gear!cadlab!martelli
From: martelli@cadlab.sublink.ORG (Alex Martelli)
Newsgroups: comp.lang.c
Subject: aliasing woes (was: low level optimization)
Message-ID: <810@cadlab.sublink.ORG>
Date: 2 May 91 12:06:43 GMT
References: <1991Apr17.225944.15261@zoo.toronto.edu> <22839@lanl.gov> <5475@goanna.cs.rmit.oz.au> <22983@lanl.gov>
Organization: CAD.LAB, Bologna, Italia
Lines: 45

jlg@cochiti.lanl.gov (Jim Giles) writes:
	...
:Quite so.  I have always criticized Fortran implementations for this.
:Especially since it does not require a run-time test.  If the compiler
:were to put the proper information into the object code, the loader
:could propagate the identities of procedure arguments through the 
:call chain and detect all such illegal aliasing at load-time.  It is,
:in fact, almost the same algorithm that I've been recommending for use
:to optimize C code at load-time.

It's unfortunately not true that aliasing can always be detected at load time.
Consider:
	int a[100], numitems;
	scanf("%d",&numitems);	/* no flames for the scanf...! */
	increm(a, a+10, numitems);

and:	increm(a,b,n) int *a,*b,n; {int i;for(i=0;i<n;i++)a[i]+=b[i];}

This has deep and troublesome aliasing iff numitems as read at RUN time
is large enough.  I guess any C compiler would simply give up any
optimization in this case.  What should a Fortran compiler do, given
that aliasing is to be forbidden and warned against?  Maybe numitems
comes from some complex calculation that "guarantees" it is <10... and
maybe the "guarantee" does not hold... but surely any warning in this
case would be just as out of place as warning at compile/load time
that A=SQRT(B) may fail, because the compiler can't guarantee/check
here that B.ge.0...

What I'd like to see would be more widespread and aggressive use of
*assertions* (I like the Eiffel approach about them).  The programmer
would just insert something like  'iswearthat(numitems<10)', and the
compiler could optionally insert a runtime check and/or take advantage
of whatever optimization opportunities are afforded by assuming that
the assertion holds (I'm not using assert() because it does not seem
to me that the standard would allow this dual usage, i.e. that a
failing assert() with no-debugging set be allowed to potentially alter
the semantics of an otherwise correct program... is that right?).
Nonaliasing of pointers could ALMOST be expressed this way - it could,
if comparisons of arbitrary pointers were allowed!  I could then say
iswearthat(a<b || a>b+33)...
-- 
Alex Martelli - CAD.LAB s.p.a., v. Stalingrado 53, Bologna, Italia
Email: (work:) martelli@cadlab.sublink.org, (home:) alex@am.sublink.org
Phone: (work:) ++39 (51) 371099, (home:) ++39 (51) 250434; 
Fax: ++39 (51) 366964 (work only), Fidonet: 332/401.3 (home only).