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:

.. code-block:: asm

    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:

.. code-block:: asm

    my_label:

Another example is this code for the msp430 architecture:

.. code-block::

    mov.w @r3, r2    ; load from address pointed to by r3 into r2
    add.w #2, r3     ; increment r3 by 2.

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

.. code-block::

    mov.w @r3+, r2  ; post increment r3 by 2 after load

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
----------------

.. automodule:: ppci.codegen.peephole
    :members: