partial redundancy

Last summer I took a compiler class in Portland, Oregon. In the class we
discussed compiler optimizations, register allocation and code scheduling
for scalar/ sequential machines. I was rereading some of the notes from
the class recently (it was a cold night, I couldn't sleep, the TV was
busted and no beer in the refrigerator :-), and I came across a topic on
partial redundancy elimination. I began reading the notes more closely and
found it interesting. I'm in the process of getting the original articles:


    "Global Optimization by Suppression of Partial
      Redundancies" by Morel and Renvoise in CACM 2/79, and
    "Lazy Code Motion" by Koop, Ruthing and Steffen in
      SIGPLAN PLDI '92.


What I was wondering about is how effective is this (type of) algorithm
for global code motion verses something like 'invariant hoisting' in
loops. Could partial redundancy suppression be considered as a
generalization of invariant hoisting?


For compilers writers that have implemented one or both of these
algorithms, which technique produces better code in terms of loops and
straight line code - i.e. does the theory match the reality? (With all
the data flow calculations going on I wonder how many redundant
expressions are really suppressed with this algorithm verses simpler
methods.)
---------------------------------------------------------------
Henry McNair hmcnair@urbana.mcd.mot.com
Motorola, Inc.
1101 E. University Aveune (217)384-8583
Urbana, Ill. 61801 (217)384-8550 (FAX)
--

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