Path: utzoo!mnetor!uunet!husc6!think!barmar
From: barmar@think.COM (Barry Margolin)
Newsgroups: comp.lang.c
Subject: Re: X3J11 meeting notes
Message-ID: <13899@think.UUCP>
Date: 17 Dec 87 21:25:28 GMT
References: <6829@brl-smoke.ARPA> <406@mn-at1.UUCP> <6852@brl-smoke.ARPA>
Sender: usenet@think.UUCP
Reply-To: barmar@sauron.think.com.UUCP (Barry Margolin)
Organization: Thinking Machines Corporation, Cambridge, MA
Lines: 81
Keywords: ANSI C standard

In article <6852@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes:
>The only actual operational change is the removal of the Ritchie
>sentence that permitted rearrangement of adjacent mathematically
>commutative and associative operations.  The parse tree you build
>is no different from before, just certain optimizations may have
>to be disabled.  Parentheses still affect just the parsing.

This doesn't sound correct to me.  I think most parsers internally
convert formulae into binary trees, so they would typically parse both

	a + b + c   and   (a + b) + c

into

		+
	       / \
	      +   c
	     / \
	    a   b

and then rearrange the tree for optimization purposes.  The new
restriction requires the parenthesization to be explicitly represented
in the parse tree, perhaps as a flag in the operator node, so that the
second expression would be parsed into

		+
	       / \
	     (+)  c
	     / \
	    a   b

The code generator would know that operations below a (<op>) node
cannot be moved above it.

Of course, this type of parse tree node was already necessitated by
unary plus.  It is just a matter of changing the parsers to create it
for all parenthesized expressions.

>In fact, in many cases (for example, 2's complement machine with
>no integer overflow trapping), those sort of optimizations can
>still be performed.  The key is that the result must be the same
>"as if" the strict virtual machine operations had been performed
>in the non-rearranged order.  Constant folding, for example, often
>will not affect the result.  Implementations that trap integer
>overflow are prohibited from causing it by rearrangement now;
>that actually helps the programmer obtain reliable behavior.

If overflow trapping exists, and equivalent behavior is required, very
little optimization can be done.  Consider

	(a + 1) - 1

When a is the highest value it can assume, this will cause overflow
under the new rules, but the old rules allow constant folding across
the parens, which translates the above to "a", which can never cause
overflow.

The biggest problem I see with this requirement is due to macros.  In
order to implement macros that expand into arithmetic operations and
guarantee that they are well behaved it is necessary to use a level of
parentheses, e.g.

#define one_more_than(x) (x + 1)

If the parentheses are omitted, as in

#define one_more_than(x) x + 1

then things like this happen:

	(2 * one_more_than(3)) != (one_more_than(3) * 2)

This standard change effectively disallows many optimizations of
expressions that make use of macros.

---
Barry Margolin
Thinking Machines Corp.

barmar@think.com
seismo!think!barmar