Re: WANTED: Rating of common optimization routines.

> I wonder if there's any published report on the commonly employed
> optimization routines/procedures targeted for scalar-type RISC based
> applications such as:
>
> o register allocation
> o copy propagation
> o common subexpression optimization
> o peephole optimization
> o strength reduction
> o code motion of loop invariants
> o ...
>
> that is, regarding each one's contribution to the percentage of
> improvement on the target execution speed when turned on. I tend to think in
> general that register allocation rates the highest, followed by peephole
> optimization and strength reduction.


You can find some papers along the lines of "My new optimization makes
these programs run 2% faster" in Programming Language Design and
Implementation (PLDI) proceedings, published by SIGPLAN and possibly
in TOPLAS as well. However, these papers don't address simple
(well-known) optimizations.


Which optimizations produce how much will depend upon the program and
the machine. For example, on a RISC machine for scientific
applications, common sub-expression elimination and strength reduction
(of induction expressions) is probably most important. In fact, as
long as you do a merge of common induction expressions, you would not
lose a lot from not doing common subexpression elimination! Also high
on my list would be loop rotation (you want the test at the bottom,
not the top) Register allocation only matters if you spill, and if you
have enough registers your register allocator has to be very broken to
make a difference (not that it is the least bit difficult to write a
register allocator that is badly broken - use basic block granularity,
for example)


On a machine like the 80x86, on the other hand, register allocation is
crucial. On an early mini-computer I once used which had 3 general
purpose registers, one of the few optimizations done by the
"optimizing" Fortran compiler was common subexpression elimination and
this would often make code run slower because the intermediate results
would be spilled to memory and it took longer to store and load them
than it would have to recalculate them (especially as many could be
done as part of an address expression)


If you are implementing an optimizer, the best thing to do is to
examine the code produced by your compiler. It will quickly become
apparent what optimization to add next.


--

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