Lesson 3: Local Analysis & Optimization

Gist

Intro & Simple DCE Passes

Contrasting local vs. global vs. interprocedural analysis.

Then, our first optimizations!

You can see my implementation in tdce.py in the examples directory in the Bril repository.

Local Value Numbering

Here’s the pseudocode from the video:

table = mapping from value tuples to canonical variables,
  with each row numbered
var2num = mapping from variable names to their current
  value numbers (i.e., rows in table)

for instr in block:
    value = (instr.op, var2num[instr.args[0]], ...)

    if value in table:
        # The value has been computed before; reuse it.
        num, var = table[value]
        replace instr with copy of var

    else:
        # A newly computed value.
        num = fresh value number

        dest = instr.dest
        if instr will be overwritten later:
             dest = fresh variable name
             instr.dest = dest
        else:
             dest = instr.dest

        table[value] = num, dest

        for a in instr.args:
            replace a with table[var2num[a]].var

    var2num[instr.dest] = num

You can see my implementation in lvn.py in the examples directory in the Bril repository. But seriously, don’t be tempted! You want to write your implementation without looking at mine!

Tasks