Re: optimization and compilation speed

debray@CS.Arizona.EDU (Saumya K. Debray) writes:
> I have this impression that various people have observed that some
> amount of (peephole) optimization can lead to an overall reduction in
> compilation time, [...]


> Any pointers to citations would be appreciated.


Markus Armbruster and I observed the same thing with our Fiasco
[Fiasco Is A Sather COmpiler]. Fiasco uses a SSA-based IR similar to
Cliff Click's Omega-graph, which allows for simple and thus fast
implementation of relatively strong optimizations. It's a little bit
faster, when run with all optimizations, Constant Folding, Common
Subexpression Elimination and global Code Motion, where the CSE
becomes global value numbering when the Code Motion is enabled.


The observed gain in speed due to optimization was mostly due to the
in comparison the the rest of the compiler slow BEG-generated backend,
which typically consumed up to a third of the total runtime. The
backend spent about half of its time writing the text-format assembler
file. The parts typically consume: scanner:37.2%, parser:8.2%,
AST-construction:7%, semantic-analysis:12.4%, IR-construction and
optimizations:21.2%, backend including code generation:33.1%,
rest:0.8%


A scenario showing the differences in runtime used by the
optimizations, measured relative in percent of the total runtime of an
unoptimizing compiler-run. The global Code Motion is implemented in
the scheduler [not to be confused with a instruction-scheduler].


enabled CM CM CM CM
optimizations CF CF CF CF
                              CSE CSE CSE CSE
------------------------------------------------------------
CF 1.76 1.66 1.76 1.60
CSE 1.59 2.40 1.59 2.35
sched -0.06 -0.28 -0.34 2.55 2.27 2.14 1.41
CG -0.33 -3.03 -3.50 0.83 -0.36 -1.94 -5.17
rest -0.96 -1.75 -2.66 -0.35 -1.61 -1.91 -3.80


total 0.24 -3.30 -2.44 3.03 1.89 0.05 -3.60




Even if one takes Constant Folding for granted, the compiler still is
about 0.3% faster with global value numbering and global code motion
enabled than without.


We never published our results in a journal, thus I can't give you a
good reference. But, you might be able to get our thesis [which is in
german, sorry] with an in-depth description of the compiler and fine
grained measurements of its behavior from somewhere below
ftp://i44ftp.info.uni-karlsruhe.de/pub/sather/. If you URL is stale,
I'll be happy to mail you a gzipped PostScript file for either DinA4
or letter sized paper and/or a .tar.gz of the GPLed compiler sources.


Christian.

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