Cost/Benefit of compiler optimization techniques?

Ira Baxter <baxter@zola.ICS.UCI.EDU>
28 Nov 90 13:11:25 GMT

          From comp.compilers

Related articles
Cost/Benefit of compiler optimization techniques? baxter@zola.ICS.UCI.EDU (Ira Baxter) (1990-11-28)
Re: Cost/Benefit of compiler optimization techniques? (1990-11-28)
Re: Cost/Benefit of compiler optimization techniques? (1990-11-28)
Re: Cost/Benefit of compiler optimization techniques? (1990-11-29)
Re: Cost/Benefit of compiler optimization techniques? (1990-11-29)
| List of all articles for this month |

Newsgroups: comp.compilers,
From: Ira Baxter <baxter@zola.ICS.UCI.EDU>
Keywords: optimize, design
Organization: Compilers Central
Date: 28 Nov 90 13:11:25 GMT

Compiler optimizations for conventional procedural languages on
conventional architectures (for sake of argument, consider both CISC
and RISC in this class) seem to come at two levels:

      Machine-independent optimizations
      Machine-dependent optimizations

Aho's Dragon book suggests "some of the most useful optimizations" that
fall into the machine-independent class are:
    Function-preserving optimizations:
        Common subexpression elimination
        Use of algebraic identities
        Copy propagation
        Dead-code elimination
        Constant folding
    Loop Optimizations:
        Code Motion
        Induction-variable elimination
        Reduction in Strength
Others come to mind:
        Use of programmer-supplied data assertions or branch-probabilities
        Trace scheduling
        Procedure inlining
        Partial evaluation
        <fill in your favorites>

For code generation, some optimizations beyond a vanilla code generator are:
      Careful use of machine idioms
      Register allocation (by hueristic methods, graph coloring, etc.)
      JMP-chain elimination
      Peephole optimization
      Dynamic-programming for optimal code generation
      <fill in your favorites>

But there is little information about the relative utility of each of
these techniques.

I am interested in finding out the "most useful" optimizations (at both
levels) for conventional procedural languages (FORTRAN, C, etc.), by
comparing average quantitative payoffs which rank them (say, reduction in
execution time measured over some large suite of user programs) to some
measure of the average effort to implement that optimization (measured in
man-somethings). Essentially what I am asking is, "What are the
cost/benefit ratios of various techniques"? Additional useful information
would be something like conditional utility, i.e., if technique A is used,
then technique B is X% less useful. Surely enough compilers have been built
so this information is known and documented.

Pointers to literature, knowledgeable sources, and even corrections to
the form of the question would be appreciated. I'll summarize.
Thanks in advance.

[Do I want to build a compiler? Not this week. But this information
is clearly something every would-be compiler writer should have.]

(714) 856-6693 ICS Dept/ UC Irvine, Irvine CA 92717

Post a followup to this message

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