Re: common subexpressions elimination

[EMAIL PROTECTED] (Toby Thain) writes:
>[EMAIL PROTECTED] (N. Paschedag) wrote in message news:<[EMAIL PROTECTED]>...
>> [EMAIL PROTECTED] (Abhijit Ray) wrote in message news:<[EMAIL PROTECTED]>...
>> > for a piece of code like 
>> > 
>> > c = a + b + d 
>> > 
>> > f = a + k + b  
>> 
>> No. Lcc only eliminates expressions that can be implemented as 
>> identical trees. The above expressions, however, result in
>>    add( add( a, b ), d )
>> and 
>>    add( add( a, k ), b )
>> i.e. there is no overlap.
>
>The trees may not be identical, but the semantics are - and CSE should
>realise this.

True *in this case* but the simplify code in LCC is very simple (thankfully) so is
unlikely to spot this.

In the general case, CSE on anything other than schematically-equivalent code is
difficult (cf. Herbrand equivalence).

>Mathematica is clever enough to "try all orderings" of a series of
>commutative operators when matching them to patterns.

*Ouch*!!!  That is rather computationally expensive considering the number of possible
combinations.  Look up Catalan numbers to see how many combinations there are of trees 
of
commutable operations (hint: its exponential).

>Something
>similar could be achieved by sorting operands before checking for
>common expressions.

Yes, that is a common trick, which can also be applied to function arguments in C 
(compute
the hardest first, then the easiest).  It is tricky to get it right and make sure all 
the
dependencies and sequence points are valid.

> A strictly binary tree representation may make
>this trickier. I'm sure this is a many times solved problem in
>compiler construction...

Many problems are actually unsolvable, but we can usually get pretty close with
heuristics and luck.

Cheers,
Neil

-- 
Neil Johnson         :::::::::::::::::       University of Cambridge
PhD Research Student                             Computer Laboratory    
http://www.cl.cam.ac.uk/~nej22               http://www.cl.cam.ac.uk