Re: finding use-def and def-use chains (Preston Briggs)
Fri, 7 Aug 1992 15:18:28 GMT

          From comp.compilers

Related articles
def-use and use-def chain... (V.C. Sreedhar) (1992-07-12)
re: finding use-def and def-use chains (1992-08-05)
Re: finding use-def and def-use chains (1992-08-07)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Preston Briggs)
Organization: Rice University, Houston
Date: Fri, 7 Aug 1992 15:18:28 GMT
References: 92-07-025 92-08-024
Keywords: optimize, bibliography (Uday P Khedkar) writes:

>Sometime back I had posted an article to gather information on
> the use of bidirectional data flow problems in production compilers.
> I got only one reply from Bill Leonard of Harris Computer Systems
> Division which mentioned that the Harris Night Hawk compilers for C,
> FORTRAN, and Ada use the Morel-Renvoise algorithm for CSE detection.
> Are the bidirectional folks not tuned on, or is it that the interest
> in bidirectional flows is its infacy ??? :-(

A common complaint about bi-directional analysis is that there are no
proofs of complexity (time to converge). I believe lots of people in
industry and academia use variations of Morel-Renvoise (e.g., the IBM PL.8
compiler, the MIPS compilers, our Fortran compiler, ...); however, many of
the common variations use only single-directional data-flow analysis to
achieve the same effects (at least, that's the claim). For example, see

A Solution to a Problem with Morel and Renvoise's
                      "Global Optimization by Suppression of Partial Redundancies"
Karl-Heinz Drechsler and Manfred P. Stadel
TOPLAS, 10(4), October 1988


Lazy Code Motion
Jens Koop, Oliver Ruthing, Bernhard Steffan

These same authors also have a paper called "Lazy Strength Reduction"
wherin they describe a version of Dhamdhere's work that accomplishes the
same form of strength reduction using uni-directional analysis.

Finally, it's important to note that this form of strength reduction
(based on extensions of Morel and Renvoise) has significant weaknesses
when compared to algorithms presented by Allen, Cocke, and Kennedy.

Preston Briggs

Post a followup to this message

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