Noalias trivia question

[Prescott K. Turner]

In article <14522 at brl-adm.ARPA> dsill at nswc-oas.arpa (Dave Sill) writes:
>From: "T. William Wells" <bill at 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.  

Such a reduction should be no surprise.

>However, even if the "noalias", or value caching, problem is unsolvable in
>general, that does not mean that an optimizer can never determine when
>it is safe to cache. 

Yes, exactly.

>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.

Your argument has some validity, but from a practical point of view,
a compiler has no hope of determining all that the programmer knows
about the program.  The programmer does not have to apply an algorithm
that determines where "noalias" can be used based on just the source
code -- many design ideas and properties of the program are available
to guide the programmer's verification that "noalias" is used correctly.
By comparison, the compiler would have to start by proving all relevant
properties of the program.

>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?

OK, an optimizer has the potential to make use of all "safe" assumptions.
But what real-life optimizer is going to make all the right assumptions 
about what happens when a program calls one of the standard library 
functions?  The programmer has an advantage.

There is a real need which "noalias" attempted to satisfy.  Though as an
implementer I was relieved to see it go.
--
Prescott K. Turner, Jr.
Software Development Technologies, Inc.
375 Dutton Rd., Sudbury, MA 01776 USA        (617) 443-5779
UUCP:genrad!mrst!sdti!turner