Path: utzoo!mnetor!uunet!husc6!hao!oddjob!gargoyle!ihnp4!cuuxb!mmengel
From: mmengel@cuuxb.ATT.COM (Marc W. Mengel)
Newsgroups: comp.lang.c
Subject: Re: some objections to 'noalias'
Message-ID: <1453@cuuxb.ATT.COM>
Date: 22 Dec 87 16:36:08 GMT
References: <485@cresswell.quintus.UUCP>
Reply-To: mmengel@cuuxb.UUCP (Marc W. Mengel)
Organization: AT&T-DSD, System Engineering for Resellers, Lisle IL
Lines: 156
Keywords: lines=106, pragmas, compiler hints
Summary: I like it...

<>

In article <485@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes:
...
>'noalias', however, is a promise to the compiler which the
>	compiler cannot check, which it is NOT safe for the
>	compiler to take on faith.
>
Actually, I thought the whole point was to put noalias in simply because
the compiler cannot check it...  That is, there are optimizations possible
if you know that a pointer isn't aliased, and the only person who can
possibly tell this for real is the programmer.  Now you tell me the
compiler cannot "safely" take this "on faith".  Well, the compler can't
"safely" take pointer casts like converting a (char *) to a (float *)
"safely", after all, there could be allignment problems.  A C compiler
*has* to take things like noalias and pointer casts on faith because
there is *not* any way to check for them in the language.

>So we have two problems with "noalias"
>(1) "noalias" does NOT mean "no alias", as Doug Gwyn showed in
>    an example.  It means something like "there may be any number of
>    aliases for this thing, one of which has the noalias property,
>    and some of which, due to casting, have not, but changes will
>    only be done through the version having the noalias property,
>    so the compiler may rely on that version not changing
>    unexpectedly."  Whatever the exact rule is, it is something
>    quite different from and more complex than a simple "no aliases"
>    rule, so the name is misleading.

Mark Twain used to say that "a man who doesn't read is no better off
than a man who can't read".  If there is another pointer to the location
pointed to by a "noalias" pointer that the programmer is certain can't 
end up being used in the scope of the "noalias" pointer, that means the 
programmer knows the optimizations are okay, and the programmer can *tell* 
the compiler he knows that they're okay.

>(2) Believing the programmer is not a safe approximation.
>    Judging from some of the examples so far, the intended property
>    may not be computable.

Right. It is NOT computable. Therfore you (the compiler) *have* to believe 
the programmer, since you can't figure it out yourself.

In C, we believe the programmer about a lot of things:
	Pointer casts
	Function arguments (pre ANSI,anyhow)
	Array Subscripts
	etc.
	etc.
All of a sudden you think we can't believe the programmer anymore.
>
>Having some way of telling a compiler that something has no aliases
>sounds like a really good idea.  (Euclid did this by making all
>aliasing illegal
...
>) But the right way to do this is to come up with some property which the
>compiler (or a separate checker) can verify, and which implies the
>property of interest.  This is a non-trivial task in language
>design, especially in the case of C.  Rushing it in at the last
>minute is not a good idea.
>
>(3) A snag with things like volatile and noalias is that they
>clutter up the language.  There are a great many things that one
>might want to tell a compiler.  There should be one generic
>mechanism for all of them.  The simplest scheme I can think of
>is to replace the rule
...[long discussion of how we should use pragmas for volatile, noalias, etc.]

volatile and noalias are built in to make them mandatory.

pragma is there to allow optional extensions.

>
>If the FORTRAN committee have not found a need to introduce a 'noalias'
>mechanism into that language (aliasing is quite possible in FORTRAN),
>what makes C so special?  I have seen the February '87 draft of the
>FORTRAN 8X (they'd better hurry) standard.  That's getting to be a
>very complicated language indeed (user-defined types, with parameters
>yet!) but they still hadn't put 'noalias' in.

Fortran uses copy-in copy-out address passing, and (in current
implementations) doesn't have an address-of operator. Therefore
aliasing is much less of a problem.  Take the classic example
of complex numbers:

typedef float complex[2];

mult( c1, c2, c3 )
	complex c1, c2, c3;
{
	c3[0] = c1[0] * c2[0] + c1[1] * c2[1];
	c3[1] = c1[1] * c2[0] + c1[1] * c2[0];
}
 
in C this leads to an incorrect complex multiply (by definition) if you 
call it as:

	complex c1, c2;
	...
	mult(c1,c2,c1);

This is due to "aliasing".  Fortran, since it uses copy-in, copy-out
argument passing, does not have this problem. (i.e. you get a correct
complex multiply implementing complex numbers with arrays this way, since
you deal with 3 copies, 2 of c1, one of c2, whose values are copied
back out at the end of the procedure.)

>The approach taken by the majority of other programming languages is
>that if you change one alias of a location and then access it via
>another location it's your own silly fault if you don't get the
>answer you expected.  I can't think of any of my own C programs
>where it would not have been appropriate to declare ALL variables
>'noalias'.  So that's a fourth problem with noalias: it's back to front.

The way C is defined, if p1==&a, and p2==&a, then *p1 == *p2 at any
given time.  This means the compiler is forced to always update 
the location at the end of a pointer, even when it would be more
efficient to hang onto it for a little while, and store it later:

	p1=&a;
	p2=&a;

	*p1 = b;
	*p1 &= 0xff;
	printf("%d\n",*p2);
	*p1 |= 0x100;

would be less code if we didn't have to have the right value for *p2.
The way C is defined, however, we *do* have to have the right value for
*p2 here.  "noalias" gives us a way to tell the compiler that its okay 
not to worry about keeping the memory location at *p1 always in sync, 
to keep that value of b&0xff around in a register until we compute
(b&0xff)|0x100, and then maybe get around to storing it in memory.

>Why not simply say that the compiler is entitled to assume 'noalias'
>for everything, and that if the programmer wants unsafe aliases s/he
>should declare the variables in question to be 'volatile'?  Doesn't
>"volatile" mean that a variable may change behind the compiler's
>back, and isn't that exactly what we want here?

Because it breaks existing code, like that above.
>
>This might perhaps be a "Quiet Change", but nobody ever told me that
>aliasing was supposed to be legal in C, so even that isn't clear.
>I don't see why having noalias as the basic assumption should be any
>more of a burden on me in C than it is in FORTRAN.

It is legal, entirely because of the way address of is defined in C.
Sure nobody told you it was "legal", nobody said it wasn't, and the
operators and syntax allow you to do it.  You just assumed it wasn't
because you have used languages which prohibit it.
-- 
 Marc Mengel	

 attmail!mmengel
 ...!{moss|lll-crg|mtune|ihnp4}!cuuxb!mmengel