5

I've been reading up on local optimization compiler techniques but I keep not getting how they're implemented. The idea is that the optimizer looks at a 'window' of the code every time and somehow detects patterns and replaces them with more optimized versions.

My question is, how does one discover these patterns? (let's say your platform is a VM that outputs assembly code for a made-up computer, like Schocken's Hack).

Do people actually inspect code manually (using Control Flow Graphs or DAGs or whatever) and then gather up all the patterns identified and code them into the optimizer? Or is there an automatic way.

For example, you feed the code-to-be-optimized in an analyzer, and it spews out said patterns. If so, how can one start writing one ?

Paul Sweatte
  • 24,148
  • 7
  • 127
  • 265
gfountis
  • 51
  • 4
  • I think this is generally called `inline caching`. You will find much literature for recent JavaScript engines using this technique at runtime. See http://wingolog.org/archives/2012/05/29/inline-cache-applications-in-scheme. – leppie Aug 05 '12 at 16:32
  • That's interesting, first time I bump into this. I was generally thinking for operations like strength reduction, constant evaluation, control flow opt., etc.. – gfountis Aug 05 '12 at 16:40
  • This seems to be targeted at 'runtime' yes? Or is it used to generate more tight assembly code? – gfountis Aug 05 '12 at 16:44
  • You can apply it at compile time if you are only interested in static compilation (iow no runtime incremental compilation/interpretation), but you will have to analyse all the call sites. – leppie Aug 05 '12 at 16:49
  • Thanks for the comments! However I still don't understand how the optimization rules are generated. Everywhere I keep seeing optimization tables of rules like "when you encounter this pattern, replace it with that one" but no one seems to explain HOW do you come up with these patterns in the first place! I've seen some papers that are describing automatic peephole optimizers so I'm guessing they are out there, but the common practice is to somehow do it by hand.. ? – gfountis Aug 05 '12 at 17:10
  • From what I gather (not having had to take to this route myself), it like linktime optimization. Obviously, in a static context will mean you need to apply this info to the compiler and do a second pass (compile and link), and perhaps again up to some point. – leppie Aug 05 '12 at 17:15

2 Answers2

3

The classic peephole optimizations aren't about strength reduction and the other things you name. They are 2-3 instruction sequences like for example

BRANCH FALSE $1
BRANCH $2
$1:

which can be reduced to

BRANCH TRUE $2

Sequences like this can arise in naive code generators such as come with single-pass compilers that don't generate ASTs, such as some COBOL compilers I have worked on.

user207421
  • 305,947
  • 44
  • 307
  • 483
  • I see, but how one can discover these sequences? is there a list of patterns somewhere published? Do people compile random code and then start searching them by themselves? – gfountis Aug 05 '12 at 21:56
  • Also, wasn't that a control flow optimization example? =) – gfountis Aug 05 '12 at 21:59
  • 1
    @gfountis Sure it was but the compilers I am speaking of don't do flow analysis. The peephole sequences would be obvious to any decent assembly programmer, if there are any of those left. You just inspect the output and think 'hmm ...'. This is all in the usual books. – user207421 Aug 06 '12 at 00:08
  • So it's just experience ? isn't there any "formal" way of doing the analysis? Thanks for your comments! – gfountis Aug 06 '12 at 00:13
1

It depends on you whether to write your own analyzer or use the existing ones. In either case your analyzer keeps checking the code until it is not more optimize. If you take an example of GCC, it has specific passes for optimization. Intermediate code of your program is given to these passes which executes one after another and optimize your code. Also any pass can execute more than once.
If you really want to go through how to write these optimizations, just go through passes.h file in GCC.

neel
  • 8,399
  • 7
  • 36
  • 50
  • So, in the case of wanting to optimize for non-x86 code generation (for a toy platform) the only way is to either write your own analyzer, or do it by "hand" right? – gfountis Aug 06 '12 at 09:01
  • The question is about peephole optimization, and you haven't answered it. – user207421 Jan 05 '16 at 08:24