# Lecture 32, Peephole Optimization

## Without Optimization

Consider code generation for the ARM using a simple stack-based code generator interface. Given this input (where i is a local variable):

```i = i + 1;
```

The code generator might generate this intermediate code, perhaps in the form of a sequence of calls to code generation routines and not an actual intermediate code:

```pushla i
pushla i
pushi  1
pop
```

The code generator for an ARM machine might respond to this as follows:

```        sub     r3, fp, #8    -- pushla i
sub     r4, fp, #8    -- pushla i
ldr     r4, [r4, #0]  -- load
mov     r5, #1        -- pushi 1
str     r4, [r3, #0]  -- pop
```

This is, of course, very inefficient! Any decent assembly language programmer would have written the following code to increment the local variable i:

```        ldr     r3, [fp, #-8] -- load i
add     r3, r3, #1    -- add 1
str     r3, [fp, #-8] -- store i
```

The problem we will ask here is: How can we get this quality of code without being very smart?

## An Aside: Which Way Does the Arm Stack Grow?

Those negative displacements from the frame pointer seem odd? Which way does the stack grow on the Arm? A quick empirical test suffices to answer this question:

```void f( int * p ){
int q;
if (p < &q) {
puts("stack grows by incrementing the stack pointer\n");
} else {
puts("stack grows by decrementing the stack pointer\n");
}
}
int main(){
int p;
f( &p );
}
```

Run this, and you get this output:

```stack grows by decrementing the stack pointer
```

## Peephole Optimization

Peephole optimization involves examination of code at a very local level, attempting to find patterns of instructions that can be replaced with more efficient patterns of instructions. Here is a typical peephole optimization rule:

When you see this pattern:

```        mov     |a|, #|b|
add     |c|, |d|, |e|
```

Where |a| = |e|, replace it with this:

```        add     |c|, |d|, #|b|
```

Here is a second rule:

When you see this pattern:

```        sub     |a|, |b|, #|c|
ldr     |d|, [|e|, #0]
```

Where |a| = |e|, replace it with this:

```        ldr     |d|, [|b|, #-|c|]
```

Searching the output of our compiler for instances that match this pattern and then making the indicated substitutions, we get the following code:

```        sub     r3, fp, #8    -- pushla i
ldr     r4, [fp, #-8] -- pushla i / load
add     r4, r4, #1    -- pushi 1 / add
str     r4, [r3, #0]  -- pop
```

This code is almost optimal. Peephole optimization cannot easily find the final optimization, combining the initial sub with the final str, because these are far apart in the code and separated by other operations. Peephole optimization is, in effect, looking at the code through a very small window, a peephole. Our rules required a window that was only two instructions long, yet is created pretty good code.

Note that our peephole optimization rules are not necessarily universal rules. For example, neither of our patterns could be used with any safety in general contexts because, in each case, we eliminated the initialization of a register. What would happen, for example, if r4 has been used at a later point in the code? The peephole rules we have presented above are based on the assumption that the code generator is very limited in the optimizations it does, such that it will never generate sequences of instructions that match our patterns except when those patters apply.

## Implementing Peephole Optimization

Obviously, peephole optimizers can be written in languages with strong pattern matching tools. The Unix tools SED and AWK, along with programming languages such as PERL can express the rules required for peephole optimizations very compactly.

Nonetheless, using such a language to do the peephole optimization for a production compiler would be silly. As with many other issues, it is easier to do this optimization earlier in the code generation process. For example, consider the following idea:

Instead of emitting code as text strings, for example, "mov r5, #1", consider, instead, emitting the code from the code generator as a tuple such as <"mov","r5","#1","">. The code generator can emit these tuples directly into the peephole optimizer, where a fixed-size set of tuples can be buffered. As new tuples are pushed into the peephole mechanism, it can emit tuples as needed (in text form) to make space, but each time a new tuple is pushed in, the peephole mechanism can compare the component fields to see if an optimizing rule applies. Since the fields are pre-parsed (having never been converted to text) the necessary comparisons can be very simple.

## Peephole Optimization Applied to Pipelined Processors

Note that all modern processors of any quality at all are pipelined. A typical pipeline has 4 stages (some have more, some fewer):

1. IF Instruction Fetch
2. OG Operand Gather (from registers and instruction fields)
3. OP Operate on the ALU or Memory (do the actual work)
4. RS Result Store (back to a register)

Note that many processors also incorporate result forwarding -- this is work done in the operand gather stage where, if a source operand is in a register and the result store stage is currently trying to store a result in that same register, the operand gather stage takes the result instead of waiting for the store to register to complete. The mechanism by which this is done does not matter to us as much as the fact that it can be done.

Consider the impact of this on the code of the example used above:

```INSTRUCTION            TIME
ldr     r3, [fp, #-8]  | IF | OG | OP | RS |
add     r3, r3, #1          | IF |////| OG | OP | RS |
str     r3, [fp, #-8]                 | IF |////| OG | OP | RS |
| 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  |
```

What could have been done in 6 clock cycles had there been no operand dependencies between these three instructions now takes 8 clock cycles. In each of the second two instrucitons, one clock cycle of delay was added to force the operand gather phase of that instruction to wait until the result computed by the operate phase of the previous instruction was available. Two cycles would have been added had it not been for the result forwarding logic typical of modern pipelined machines.

Now, suppose we have a sequence of two unrelated statements such as:

```i = i + 1;
j = j - 1;
```

If we convert these to the following assembly language code, we will incur 4 clock-cycles worth of delay because of operand dependencies:

```        ldr     r3, [fp, #-8]  -- load i
add     r3, r3, #1     -- add 1
str     r3, [fp, #-8]  -- store i
ldr     r3, [fp, #-12] -- load j
sub     r3, r3, #1     -- sub 1
str     r3, [fp, #-12] -- store j
```

In contrast, if we allocate different registers and interleave the two sequences, we can eliminate all of the operand delays:

```        ldr     r3, [fp, #-8]  -- load i
ldr     r4, [fp, #-12] -- load j
add     r3, r3, #1     -- add 1
sub     r4, r4, #1     -- sub 1
str     r3, [fp, #-8]  -- store i
str     r4, [fp, #-12] -- store j
```

Of course, the penalty for such interleaving is very hard to read code. This is why good compilers can frequently generate faster code than the average assembly-language programmer who may be more interested in writing readable and maintanable code than in writing code that is as fast as possible.

Peephole optimization cannot take the two blocks of code given originally and interleave them this fully, but there are some simple peephole rules that can eliminate many delay slots. Consider the following peephole optimization rule:

When you see this pattern:

```        str     |a|, [fp, #|b|]
ldr     |c|, [fp, #|d|]
```

Where |a| ≠ |c|, and |b| ≠ |d|, replace it with this:

```        ldr     |c|, [fp, #|d|]
str     |a|, [fp, #|b|]
```

In short, where you see a store to a local variable followed by a load from a different local variable, swap them so long as different registers are used.

Why restrict this to local variables (that is, those indexed off of the frame pointer)? Because in the case of Falcon programs, we can guarantee that there are no aliases for local variables. Non-local variables could have been passed to the current routine as reference parameters, and this creates the possibility that for arbitrary loads and stores, two different names, for example, a direct reference to a global variable and the use of a reference parameter, could refer to the same actual variable. Switching the order of loads and stores to a single particular variable would change the meaning of a program.

Of course, this optimization only works if the compiler's code generator allocates different registers for the different variables. This is difficult if a pure stack-oriented code generator where registers assignment depends on the level in the stack, while it works well with pure LRU allocation of registers.