Peephole optimization

This page describes peephole optimization. The basic idea of peephole optimization is to take a small window (a peephole), and slide it over the instructions. Then, looking at this small sequence of say two or three instructions, check if this machine code sequence can be optimized.

For example, if we generated code in a previous pass which contains code like this:

jmp my_label
my_label:

It is easy to see that the jump instruction is not required. This kind of code can easily be generated by generating code for parts of the program and then concatenating them into the final code. The goal of the peephole optimizer is to detect these kind of constructions and in this case, remove the jump instruction, so that the final code will be like this:

my_label:

Another example is this code for the msp430 architecture:

These two instructions can be combined into one instruction which has the same effect:

Combiner

One way to implement a peephole optimizer is to write a lot of patterns and try all these patterns in turn. If a pattern matches a specific sequence of instructions, the pattern can be applied, and the instructions are substituted by the pattern substitute.

Another way, is to define per instruction the effects of the instruction, and for each pair of instructions that are evaulated, combine the effects of these instructions. If there exist an instruction which has the same effect as the combined effect of the two original instructions, the substitution can be made. This is the combiner approach as described by [Davidson1980].

The advantage of having the combiner, is that only per instructions the effects of the instruction must be defined. After this, all instructions with effects can be potentially combined. This reduces the amount of work to define peephole optimization patterns from N * N to N. Namely, not all instruction combinations must be described, but only the effects per instruction.

Module reference

Peephole optimization using the pipe-filter approach.

We face a certain stream of instructions. We take a look at a very specific window and check if we can apply the optimization. It’s like scrolling over a sequence of instructions and checking for possible optimizations.

class ppci.codegen.peephole.PeepHoleOptimization

Inherit this class to implement a peephole optimization.

class ppci.codegen.peephole.PeepHoleStream(downstream)

This is a peephole optimizing output stream.

Having the peep hole optimizer as an output stream allows to use the peephole optimizer in several places.

clip_window(size)

Flush items, until we have size items in scope.

do_emit(item)

Actual emit implementation

flush()

Flush remaining items in the peephole window.