Path: utzoo!dciem!nrcaer!scs!spl1!laidbak!att!pacbell!ames!umd5!brl-adm!adm!dsill@nswc-oas.arpa
From: dsill@nswc-oas.arpa (Dave Sill)
Newsgroups: comp.lang.c
Subject: Re: Noalias trivia question
Message-ID: <15857@brl-adm.ARPA>
Date: 3 Jun 88 17:31:12 GMT
Article-I.D.: brl-adm.15857
Sender: news@brl-adm.ARPA
Lines: 70

From: Peter J Desnoyers <peter@athena.mit.edu>
>In article <14522@brl-adm.ARPA> dsill@nswc-oas.arpa (Dave Sill) writes:
>>From: "T. William Wells" <bill@proxftl.uucp>
>>>Noalias
>>>solves a problem which CANNOT be solved by an optimizer (yes,
>>>this is another problem which can be shown to be equivalent to a
>>>halting problem).
>>
>>That's a new one on me.  I'd like to see that reduction.  
>
>Try add_vector( foo(x), bar(y), n). It looks uncommonly like the 
>halting problem to me.

I had something a little more rigorous in mind.  What do foo(), bar(),
and add_vector() do *exactly*?  What are x, y, and n?  In what *exact*
context is add_vector() called?  Let me have all the information the
compiler would have, at least. 

If your point is that, in general, we can't tell if two pointers
overlap, then I'll concede that point.  But the fact that a problem is
unsolvable in general does not mean that the problem can never be
solved.  We can't expect a compiler to determine with 100% accuracy
if aliasing is occurring, but we can expect a compiler to spot 90% of
the cases where aliasing can't occur, and to optimize them accordingly.

>>You are implying that programmers can solve unsolvable problems but
>>that programs cannot, which is simply not true.  The algorithm the
>>programmer applies to determine when "noalias" can be used could be
>>used by an optimizer. 
>
>You forget that programmers use often faulty and heuristic algorithms,
>and then debug their code. A compiler that generates bugs as often as
>I do (or any other programmer) would be worthless.

Oh, good methodology!  Write buggy code but debug it thoroughly.  My
point is that if the compiler can't make an optimization safely, then
the optimization is unsafe.  My next sentence, which you didn't
include, says:

>>  If this caching algorithm requires information
>>not available to the optimizer, such as the ranges of all pointers
>>(which may be limited by assumptions about the input to the program),
>>then it's not safe.  What happens when the input assumptions change?

Well?  Should we let programmers make assumptions that may or may not
be true?  I'd rather require such assumptions be made explicit using
the "assert" macro, #pragmas, or some other mechanism, so that the
compiler could make use of them for optimization and error checking.
There's no reason we should be withholding information from the compiler. 

>Not only that, programmers do not use an algorithm to determine if a
>variable is noalias/volatile/whatever. They use coding practices to
>generate code that does not disobey such constraints. Then they debug
>their code to remove any unintentional aliasing or whatever. These are
>both procedures far out of the domain of any compiler.

And thank your local deity for that.  I really can't believe you'd
advocate such an approach.  Programmers who don't use some sort
algorithm for determining the storage requirements for their data
deserve what they get.  Do you start out by declaring all variables in
your programs as ints and fixing the syntax errors?  How can you ever
be confidant that code is correct?  Aren't you always wondering if
there might be just one more undiscovered bug?

=========
The opinions expressed above are mine.

"We must remove the TV-induced stupor that lies like a fog across the
 land."
					-- Ted Nelson