Safe optimization

[dsill at nswc-oas.arpa]

"T. William Wells" <bill at proxftl.uucp> writes:
>In article <14522 at brl-adm.ARPA>, dsill at nswc-oas.arpa (Dave Sill) writes:
>> You are implying that programmers can solve unsolvable problems but
>> that programs cannot, which is simply not true.
>
>Actually, you should keep your referents straight.  I might be
>implying that humans can solve problems that are unsolvable by
>COMPUTERS.  The truth of that is a matter of conjecture.

You're absolutely right.  I *have* been assuming that the
computational power of the human brain is subject to the Church-Turing
Thesis.  I have no reason to believe that that is an incorrect
assumption.

>This of course ignores the fact that aliasing is a property of
>the DESIGN of the program, not just of the program itself.  It is
>entirely possible to design a program which has some particular
>aliasing property which can't be found by inspecting the code.
>Consider this contrived example:
>
>	scanf("%d %d", &i, &j);
>	p = &a[i];
>	q = &a[j];
>
>Can p and q point to the same object?  In the general case, yes.
>However, the programmer might intend this to be in a system where
>the two numbers can never be the same.  So, the noalias keyword
>would add information that is not present in the program.

Yes, we've been through all this before.  Your example is exactly the
kind of thing I've been preaching against.  It is too likely that
somebody will port such code to a system where the same assumptions
aren't true.  And without something in the code stronger than a
comment like "/* of course i can never equal j */", a bug will be
silently introduced.  I propose something along the lines of 

	scanf("%d %d", &i, &j);
	assert (i != j);
	p = &a[i];
	q = &a[j];

which makes the compiler aware of the assumptions made by the
programmer in a rigorous and verifiable manner.  The advantages of
this over the storage-class/keyword approach are many:

	- when testing a port on a new system, the `assert' macro can
	  be enabled, alerting the developers/porters when a
	  previously made assumption fails.

	- the programmer is unable to introduce subtle bugs through
	  incorrect use of `noalias'.

	- the language is kept smaller, simpler, and cleaner.

	- the optimization is available to all users of the language
	  that take the time to "document" the assumptions they make,
	  not just those that understand the aliasing problem.

	- other types of optimization can be enabled by the same
	  method without requiring the introduction of new keywords.

The only disadvantages of this approach that I'm aware of are:

	- it requires smarter compilers.

	- it is not able to enable all kinds of optimization that the
	  storage-class approach can.  (how would one indicate that a
	  variable is or is not volatile?) 

Unfortunately, X3J11, or ANSI (I don't know which), has simultaneously
enabled and precluded possibly the best solution: standardized
pragmas.  How hard would it have been for them to set up a system for
registering the syntax and semantics of various vendor-implemented
pragmas?  Maybe it's not too late for a secondary organization to
provide this service.

In conclusion, although the storage-class method is, in my opinion, a
poor method of enabling optimizations, it will probably be the method
of choice for compiler implementors because it is easier than adding
the necessary smarts to their compiler.

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

Thus spake the master programmer:

"Though a program be but three lines long,
 someday it will have to be maintained."

					-- The Tao of Programming