How to write an optimizer

This section will dive into the pecularities on how to implement an optimizer scheme. The optimizer will be an IR optimizer, in the sense that is transforms IR-code into new (and improved) IR-code. This makes the optimizer both programming language and target architecture independent.

The optimization

The optimizer we will implement in this example is an optimization that deletes redundant branching. For example, in the following code, branch b is never taken:

module optimizable;

function i32 add(i32 z) {
  entry: {
    i32 x = 1;
    i32 y = 2;
    cjmp x < y ? a : b;
  }
  a: {
    jmp c;
  }
  b: {
    jmp c;
  }
  c: {
    return x;
  }
}

It can be easily seen that b is never jumped to, because x < y is always true. Time to write an optimization that simplifies this!

The implementation

To implement an optimalisation, the ppci.opt.transform.ModulePass must be subclassed. For this example, ppci.opt.transform.InstructionPass will be used.

import operator
from ppci.opt.transform import InstructionPass
from ppci import ir

class SimpleComparePass(InstructionPass):
    def on_instruction(self, instruction):
        if isinstance(instruction, ir.CJump) and \
                isinstance(instruction.a, ir.Const) and \
                isinstance(instruction.b, ir.Const):
            a = instruction.a.value
            b = instruction.b.value
            mp = {
                '==': operator.eq,
                '<': operator.lt, '>': operator.gt,
                '>=': operator.ge, '<=': operator.le,
                '!=': operator.ne
                }
            if mp[instruction.cond](a, b):
                label = instruction.lab_yes
            else:
                label = instruction.lab_no
            block = instruction.block
            block.remove_instruction(instruction)
            block.add_instruction(ir.Jump(label))
            instruction.delete()

The implementation first checks if the instruction is a conditional jump and if both inputs are constant. Then the constants are compared using the operator module. Finally a ppci.ir.Jump instruction is created. This instruction is added to the block after the ppci.ir.CJump instruction is removed.

First load the IR-module from file. To do this, first create an in memory file with io.StringIO. Then load this file with ppci.irutils.Reader.

>>> import io
>>> f = io.StringIO("""
... module optimizable;
... global function i32 add(i32 z) {
...   entry: {
...     i32 x = 1;
...     i32 y = 2;
...     cjmp x < y ? a : b;
...   }
...   a: {
...     jmp c;
...   }
...   b: {
...     jmp c;
...   }
...   c: {
...     return x;
...   }
... }
... """)
>>> from ppci import irutils
>>> mod = irutils.Reader().read(f)
>>> print(mod)
module optimizable

Now run the optimizer pass:

>>> opt_pass = SimpleComparePass()
>>> opt_pass.run(mod)

Next delete all unreachable blocks to make sure the module is valid again:

>>> mod.functions[0].delete_unreachable()

Now print the optimized module:

>>> f2 = io.StringIO()
>>> irutils.Writer(f2).write(mod)
>>> print(f2.getvalue())
module optimizable;

global function i32 add(i32 z) {
  entry: {
    i32 x = 1;
    i32 y = 2;
    jmp a;
  }

  a: {
    jmp c;
  }

  c: {
    return x;
  }

}

This optimization is implemented in ppci.opt.cjmp.CJumpPass.