[com2kid]

Tools already exist for doing run time traces of compiled programs and then optimizing accordingly. A lot of what they focus on is improving locality, moving portions of the executable that are run together near each other so improve the instruction cache hit rate. They also much more aggressively inline, to the point that the overall code size increases but hopefully so does performance.

You actually get a huge amount of perf gains just from improving locality, a lot of in-depth optimizations are possible but I am not sure what compilers now days actually do, it has been a long time since I worked on a compiler team!

[haldean]

Got any links? I'd love to check out the tools you're talking about.

[vilya]

Profile Guided Optimisation is the search term you're looking for. For one example: GCC does it (you may need to use gprof as well, can't really remember).