Lesson 3: Local Analysis & Optimization
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.
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
wcto 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], ...) 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!
- 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.