Re: Reassociation

[Stephen L Moshier <moshier at mediaone dot net>]

On Thu, 17 Dec 1998, Gavin Romig-Koch wrote:
> Jeffrey A Law writes:
>  > The obvious way to do that in this case is:
>  > 
>  > 	* Introduce the concept of parens into the tree nodes for
>  > 	  expressions.
>  > 	* Honor parens and perform no associations across them.
>  > 
>  > 	* If a language does not allow reassociations, then it can make the
>  > 	  implicit parents explicit in the tree structure.
> 
> While I agree that the front end needs a way to tell the backend
> about what it can and can't optimize, I'm not sure parens in the
> tree are the best way to do this.  (I've not been able to think this
> completely through, and so it may be bunk, but I wanted to say something
> before I forgot.)

Yes, currently this is analyzed at rtl level in cse.c, which already
knows all about the associative law.  If you look at the rtl dumps for
a*b*c*d versus (a*b)*(c*d) you can see they to have a distinctive
character that might be detected the same way cse.c detects other
situations.  So I think you're probably right that tree level
structures do not have to be involved.



> If an arithmatic operation can't be reassociated using the mathimatical
> reassociation rules, it's because of the possibilty of overflow, or
> underflow, or div-by-zero (are their other?).  Collectively let me
> call these side-effects (though perhaps these aren't necessarly the
> same as C "side-effects").

In general, floating point arithmetic does not obey the associative law.
Pretending that it does involves an informed decision about how to
indicate what you will or will not associate.  In the case exhibited
so far, Fortran, the programmer indicates that by leaving out some
parentheses.  The programmer could leave out whatever he wants, and
the compiler is then permitted to do something with that code.


> If an operation can be reassociated, it's either because the front end
> doesn't care about the effects of these side-effects, or because the
> backend can determine that side-effects won't happen for a particular
> operation, perhaps because of the operation and its operators, or 
> perhaps because the architecture your compiling for doesn't detect
> these side-effects.

As I hear it, it's up to the user.  The compiler doesn't decide what
may or may not be allowed.  The programmer indicates specifically what
operations can be rearranged.  I thought at first the intent
was to let the instruction scheduler decide whether a permitted
change would actually be carried out.  Maybe that is the intent but
I don't think it's been made clear yet.


> So, rather than have the front end insert parens in the tree to
> prevent reassociation, it would be better to have a way for the
> front end to tell the back end wether or not it cares about
> side-effect for a particular operation.

Currently GCC does not allow any reassociation at all for floating
point operations.  This is done by turning off potential associative
law optimizations in cse.c and combine.c.  So maybe you could approach
the new feature as a slight modification of whats's already there.
You would filter the rtl to detect whether parentheses had been
left out and if so, and if the feature flag is on, then the optimization
would proceed.  Probably some new pattern-detecting cases have to be
added also.  Maybe cse.c is not now looking for a*b*c*d, for instance.


> What's not clear to me is whether this "dont-care-about-side-effects"
> flag needs to be specified per individual operation, or per function,
> or per frontend, or per operation type?  Do we need separate flags
> for each kind of side effect (care-about-overflow, dont-care-about-underflow)

At least three people have voted for a command-line flag that turns this whole
feature on and off.  So far we seem to have only the Fortran example
of how the programmer would indicate the specific don't-care code.