[net.unix-wizards] Optimizing Compilers

BostonU SysMgr <root%bostonu.csnet@csnet-relay.arpa> (01/02/85)

	Ok, enough of this silliness that
	an optimizer must NEVER change the
	effect of a piece of code. Consider
	the following:

	for(i=0 ; i < MAX ; i++)
		x[i] = y/z ;

	now, obviously y/z is loop invariant...
	the optimizer decides to compute
	it once:

	temp = y/z ;
	for(i=0; i < n ; i++) x[i] = temp ;

	reasonable, but what the optimizer
	does not know is I did a:

		signal(SIGFPE,print_msg_and_ignore) ;

	earlier. W/o the optimizer the msg gets printed
	n times, with it only once.

	OK, you say, that's a special case of an error.
	The point is where do you draw the line? Not
	that an optimizer should NEVER change an effect.

		-Barry Shein, Boston University

rcd@opus.UUCP (Dick Dunn) (01/09/85)

[From Barry Shein, Boston U.]
> 	Ok, enough of this silliness that an optimizer must NEVER change the
> 	effect of a piece of code. Consider the following:
> 
> 	for(i=0 ; i < MAX ; i++)
> 		x[i] = y/z ;
> 
> 	now, obviously y/z is loop invariant...the optimizer decides to compute
> 	it once...

As long as we're about it, bear in mind that if y and z were constants, the
computation of y/z might even be done at compilation time.

> ...   reasonable, but what the optimizer does not know is I did a:
> 
> 		signal(SIGFPE,print_msg_and_ignore) ;
> 
> 	earlier. W/o the optimizer the msg gets printed
> 	n times, with it only once.

A couple of problems here.  First, the whole `signal' mechanism is
completely outside the definition of C.  Second, if the computation of y/z
would generate SIGFPE, that means that the result is not well-defined--in
other words, according to C the program is erroneous and it is only by
extra-lingual means that the program gets past the y/z problem.  You can
look long and hard without finding anything in the definition of C which
indicates that a division operation can produce a function call as a side
effect of bad operands.  The optimizer is well within its bounds in
removing the invariant computation from the loop; the problem is in
understanding the definition of the signal mechanism and how it interacts
with C code.

Consider the case where y and z are constants and z is zero; in this case
the compiler may reject the program, optimized or not!
-- 
Dick Dunn	{hao,ucbvax,allegra}!nbires!rcd		(303)444-5710 x3086
   ...I'm not cynical - just experienced.

ka@cbosgd.UUCP (Kenneth Almquist) (01/11/85)

> 	The point is where do you draw the line? Not
> 	that an optimizer should NEVER change an effect.

Normally, the rule is that an optimizing compiler should conform
to the language standard.  In C, for example, the order of evaluation
of expressions is explicitly undefined in most cases.  Thus an optimizer
may reorder expressions to improve efficiency, even if this changes the
behavior of the program.

The case under discussion involved moving a division by zero out of a
loop so that only 1 exception rather than 100 exceptions are generated.
For many languages this would be OK because the effects of of a program
that performs divisions by zero are left undefined.  In the case of C,
the situation is somewhat different because C is used for a variety
of systems programming type jobs which require that the code generated
by the compiler be unsurprising.  The proposed ANSI standard for C
makes this optimization invalid.
					Kenneth Almquist