Re: Common subexpression analysis

mernst@theory.lcs.mit.edu (Michael Ernst) writes:
>Is the topic of common subexpression analysis considered a mature field?
>A search through the ACM and INSPEC collections revealed almost no work in
>recent years; the topic seems to have died off after the mid-70s.


This was what I found when I did a literature search about a year ago.


>Is there literature on computing common subexpressions on three-address
>machines with a finite, non-unity number of registers?


I don't recall seeing any.


>What is the current state of the art in common subexpression elimination?
>Most authors (and GCC) take an expression forest (or three-address code)
>representing the computations of a basic block and walk from the bottom
>up, looking for equivalent subexpressions to identify, so the forest
>becomes a multiply-rooted dag.


This is does appear to be the standard approach for CSE detection.
At least as far as I've been able to tell. I didn't find much recent
literature...


> x = a + b + c + d
> y = b + c + d + e
>
>No matter how these are parsed into binary trees (left-associative,
>right-associative, minimum-height tree), the standard methods won't find
>any common subexpressions.


Ah, perhaps the tree representation is not correct for expressions? This
was the conclusion I came to in an unpublished paper I wrote about a year
ago & occationally polish when I have time. I too was dissatisfied with
what appeared to be the current technology & I developed a system
(hopefully not reinventing someone else's wheel) that was capable of
normalizing and detecting commonality between expressions. I also
implemented a prototype detection system. However, I never did get around
to actually coding the heuristics which finally chose which CSEs were
'best'. The actual output of the prototype as it now stands is a list of
possible CSEs within a set of expressions.


The technique is capable of detecting commonality in the presence of both
associativity and commutativity. I chose to not touch distribution
because I wanted the user to have a 'out' in specifying the exact order of
evaluation. Finally, I've recently been of the opinion that, while this
does _far_ better than the current approach in terms of numbers of CSE
detected, it is expensive in terms of computational time and what it
yields may not be worth the amount of work.


(possibly the right solution to the wrong problem? What this really wound
up being was a pattern matching system which was able to take advantage of
certain algebraic properties of the input language...)


>I am interested in learning of any work relevant to CSE.


I'll run off and get a tech. report # for my work. Send me some e-mail in
a about 1.5weeks & I'll try to get a copy of the work to you.


--Mike
--
Michael D. Sharp msharp@cs.ulowell.edu
Univserity of Mass/Lowell (508)934-3649
Computer Science Dept
--

Return to the comp.compilers page.
Search the comp.compilers archives again.