# Lesson 3: Local Analysis & Optimization

## 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!