Re: finding use-def and def-use chains

uday@kailash.cse.iitb.ernet.in (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


and


Lazy Code Motion
Jens Koop, Oliver Ruthing, Bernhard Steffan
SIGPLAN PLDI 1992


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
--

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