Optimization

1. Peephole Optimization

Peephole optimization involves scanning asssembly code to replace obviously inane combinations of instructions with more efficient ones. For example, the following sequence:

peep :: [Instruction] -> [Instruction]
peep (Store r1 dest : Load r2 src : is)
  | src == dest = Store r1 dest : (peep (Load r2 r1 : rest))
  | otherwise   = Store r1 dest : (peep (Load r2 src : rest))

There are endless possibilities, but we get a phase ordering problem - in which sequence should optimizations be applied.

1.1 Loop Optimizations

• An instruction is loop invariant if its operands can only arrive from outside the loop. We can hoist these instructions out of the loop.
• Strength reduction involves replacing an induction variable (one whos value increases/decreases by a loop-invariant amount each iteration) with a simpler expression.
• Control varialbe selection involves replacing a loop control variable (like i in a for loop) with one of the induction variables used in the loop.

1.2 Dead Code Elimination

We can remove code that has no effect on the program's output.

2. Data Flow Analysis

Optimisation consists of analysis and transformation. Let's consider a control flow graph:

1data CFG = CFG [CFGNode]
2-- Id, The instruction, Uses Registers, Defs Registers, Successors
3data CFGNode = Node Id Instruction [Register] [Register] [Id]
4
5type Id = Int
6data Register = D Int | T Int
7buildCFG :: [Instruction] -> CFG

Each node in the CFG corresponds to an insturction, and stores the using registers and the defs registers, as well as successor Ids.

We can define:

• : The set of registers live immediately before node .
• : The set of registers live immediately after node .

A variable is live immediately after node if it is live before any of 's successors.

A variable is live immediately before node if:

• It is live after node , unless it is overwritten by node .
• Or, it is used by node .

Hence:

Essentially, when trying to find and for all , we end up with large number of simultaneous equations. We can solve this by iterating over the CFG until a fixed point is reached:

1for (Node n : cfg) {
2  Var[] IN = [];
3  Var[] OUT = [];
4}
5
6do {
7  for (Node n : cfg) {
8    Var[] oldIN = IN[n];
9    Var[] oldOUT = OUT[n];
10    IN[n] = uses[n] + (OUT[n] - defs[n]);
11    OUT[n] = succ(n).map(s -> IN[s]).reduce((a, b) -> a + b);
12  }
13} while (IN[n] != oldIN || OUT[n] != oldOUT);

From the live ranges, we can derive the interference graph, which we can then colour, and update the register allocation.