Re: Efficacy of compiler optimizations

<kernel_learner@yahoo.com> wrote:
> I had a general question about compiler optimizations and believe
> this is a great place to ask!
>
> First of all there are numerous number of compiler optimizations and
> they each have their own characteristics..my questions is two-fold:
>
> 1. What is the cost/benefit ratio of these optimizations.


I don't feel confident to give a succinct answer to this one, but
Steven Muchnick's book, _Advanced Compiler Design_ includes a nice
chapter on this topic, along with a couple of useful diagrams.


> 2. How do these compiler optimizations interact? i.e. does one
> optimization negate the effect of another optimization if done in a
> particular order?


I'm not aware of any "negating" each other, but it has been known for
a few years that certain analyses and transformations, when combined
produce better results than what you'd get if you ran them
sequentially, in either order. For example, consider constant
propagation and unreachable-code elimination, applied to something
like the following toy code:


      x = 5;
      if (x < 4)
          y = x * x;
      else
          y = x + 1;
      x = y;


Applied together, we can use constant propagation to replace the
if-test with "false", and hence prune the true-branch entirely (since
the assigment "y = x * x" will never be used), and hence propagate the
constants <(x,5), (y,6)> to the final line. It is easy to see that
running the analyses sequentially, in either order, will fail to
discover that we can asign x the value 6 on the last line.


This is a toy, of course, and there are much deeper examples out
there, but it should serve to illustrate. Two nice papers on the
subject:


C. Click & K. D. Cooper, "Combining Analyses, Combining Optimizations",
ACM Transactions on Programming Lanugages and Systems, 17(2):181-196
(March 1995)


S.Lerner, D. Grove, and C. Chambers, "Composing dataflow analyses and
Transformations", 29th ACM SIGPLAN-SIGACT Symposium on Principles of
Programming Languages, ACM Pr. 2002, pp. 270 - 282


The Click paper was, I believe, the first one to introduce this topic
into the academic literature. The Lerner paper has a much nicer (and
more realistic) example of this interaction phenomenon.




Hope that helps.


John
----------------------------------------------------------------------
John Fiskio-Lasseter
    * Phd. Student, CIS Dept., University of Oregon
    * Deschutes 234 x6-1385 johnfl@cs.uoregon.edu
    * http://www.cs.uoregon.edu/~johnfl

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