How do modern optimizing compilers determine when to optimize?

Question

How do modern optimizing compilers determine when to apply certain optimizations such as loop unrolling and code inlining?

Since both of these affect caching, naively inlining functions with less than X lines, or whatever other simple heuristic, is likely to generate worse performing code. So, how do modern compilers deal with this?

I'm having a hard time finding information on this (especially information thats reasonably easy to understand..), about the best I could find is the wikipedia articles[1]. Any details, links to books/articles/papers are greatly appreciated!

EDIT: Since answers are talking mainly about the two optimizations I mentioned (inlining and loop unrolling) I just wanted to clarify that I'm interested in all and any compiler optimizations, not just those two. I'm also more interested in the optimizations which can be performed during ahead-of-time compilation, though JIT optimization is of interest too (though to a slightly lesser extent).

Thanks!

[1] http://en.wikipedia.org/wiki/Compiler%5Foptimization

Answer 1

You can look a the Spiral project.

On top of that, optimizing is a tough thing to do generically. This is, in part, why there are so many options to the gcc compiler. If you know something about cache and pages you can do some things by hand and request that others be done through the compiler but no two machines are the same so the approach must be adhoc.

Answer 2

Usually by being that naive anyway and hope it is an improvement.

This is why just-in-time compilation is such a winning strategy. Collect statistics then optimize for the common case.

References:

• http://lambda-the-ultimate.org/node/768
• GCC supports Profile Guided Optimization
• And of course the Sun hotspot JVM

Answer 3

For short: Better than we!

You can have a look at this: http://www.linux-kongress.org/2009/slides/compiler%5Fsurvey%5Ffelix%5Fvon%5Fleitner.pdf

Didier

Answer 4

Good question. You are asking about so called speculative optimizations.

Dynamic compilers use both static heuristics and profile information. Static compilers employs heuristics and (off-line) profile information. The last is often referenced as PGO (Profile Guided Optimizations).

There is a lot of articles on inlining policies. The most comprehensive one is

An Empirical Study of Method Inlining for a Java Just-In-Time Compiler

It also contains references to related work and sharp criticism on some of the considered articles (justified).

In general, state-of-the-art compilers try to use impact analysis to estimate potential effect of speculative optimizations before applying them.

P.S. Loop unrolling is old classic stuff which helps only for some tight loops that performs only number crunchng ops (no calls and so on). Method inlining is much more important optimization in the modern compilers.