Lesson 3: Local Analysis & Optimization

• discussion
• simple dead code elimination
• local value numbering
• slides from Phil Gibbons at CMU
  for more details and context on LVN
• tasks due September 21

Gist

Intro & Simple DCE Passes

Contrasting local vs. global vs. interprocedural analysis.

Then, our first optimizations!

• Definition of dead code elimination (DCE).
• Globally unused instructions.
  • Derive an algorithm for deleting them.
  • Iterating to convergence.
  • Then implement it.
• Locally killed instructions.
  • The limits of local reasoning: why can't we do this globally?
  • Derive an algorithm for removing them.
  • Then implement that too.
• Let's try our new optimization pass out on the Bril benchmarks.

  • When working on your implementations, try them on simple.bril, reassign.bril, and other examples in the DCE test directory to see if they actually work.

  • First, combine all your implementations into one command somehow (including iterating to convergence). Try out your pass—something like this:

    $ bril2json < bench.bril | python3 tdce.py | bril2txt
    

  • Next, try using wc to check static code size differences:

    $ bril2json < bench.bril | wc -l
    $ bril2json < bench.bril | python3 tdce.py | wc -l
    

  • Then profiling to measure dynamic instruction count:

    $ bril2json < bench.bril | brili -p 5
    $ bril2json < bench.bril | python3 tdce.py | brili -p 5
    

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

Local Value Numbering

• Local value numbering.
  • Consider the common thread between dead code elimination (DCE), copy propagation, and common subexpression elimination. In some compilers classes/textbooks, these are all individual optimizations.
  • Value numbering is a general framework for understanding & optimizing computations.
  • If you can deeply understand the mystical metaphysics of value numbering, you will have gotten most of what you need to get out of this part of 6120.
• Extending LVN.
  • LVN can subsume constant folding, copy propagation, and algebraic identities. You will need to extend it with language semantics.
  • Write complete pseudocode for the base LVN algorithm, and work out where the "extension points" need to be to capture those optimizations.

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

• Implement "trivial" dead code elimination, in which you delete instructions that are never used before they are reassigned. Remember to iterate to convergence. (This should not take you long.)
• Implement local value numbering. Make sure it eliminates some common subexpressions. Try pairing it with trivial dead code elimination as a post-processing step. (This might take you quite a while.)
• In your README, briefly write up the evidence you have that your LVN implementation is correct and actually optimizes programs.
• For bonus "points," extend your LVN implementation to optimize the trickier examples given in class.