Advanced Compilers at the Orthogonal School

Welcome to the my one-week introduction to the wonders of language implementation! The materials this week are based on the first few lessons of CS 6120, so check out those materials for more details or ways to continue the fun after this week.

The main purpose of this page is to remind you of the assigned tasks for each lecture. I’ll keep it updated throughout the BOOST week; the schedule may shift depending on how quickly we’re able to move.

Monday: Representing Programs

We’ll start by thinking about what language implementation encompasses and then survey the different ways that implementations can represent programs. I’ll also introduce Bril, the instruction-based program representation we’ll use this week.

Your Task

Tuesday Morning: Local Analysis & Optimization

We’ll introduce our first optimizations: dead code elimination (as a warm-up) and local value numbering (the main event). I’ll demonstrate some approaches to testing.

LVN Pseudocode

Here’s the pseudocode from the slide:

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

Your Task

Tuesday Afternoon: Data Flow

The data flow framework is a powerful and general mechanism for analyzing entire functions in a control-flow-sensitive way. You can think of it as a way to take local analyses and give them global superpowers.

For more on the theory, I recommend Chapter 5 of Static Program Analysis by Møller and Schwartzbach.

Worklist Algorithm Pseudocode

Here’s the pseudocode for solving a forward data flow problem with a worklist algorithm:

in[entry] = init
out[*] = init

worklist = all blocks
while worklist is not empty:
    b = pick any block from worklist
    in[b] = merge(out[p] for every predecessor p of b)
    out[b] = transfer(b, in[b])
    if out[b] changed:
        worklist += successors of b

For the backward version, flip predecessors & successors, and flip in and out.

Your Task

Wednesday: Global Analysis

We’ll talk about control flow graphs (CFGs) and define many things we want to deduce about them.

Your Task

Thursday: Static Single Assignment

Static single assignment (SSA) form is an incredibly popular program representation that makes code easier to reason about and analyses easier to write. We’ll talk about how SSA works and some algorithms for converting a standard program to and from SSA form.

See Bril’s documentation for its SSA extension.

Efficient SSA Pseudocode

First, insert ϕ-nodes:

for v in vars:
   for d in Defs[v]:  # Blocks where v is assigned.
     for block in DF[d]:  # Dominance frontier.
       Add a ϕ-node to block,
         unless we have done so already.
       Add block to Defs[v] (because it now writes to v!),
         unless it's already in there.

Then, rename variables:

stack[v] is a stack of variable names (for every variable v)

def rename(block):
  for instr in block:
    replace each argument to instr with stack[old name]

    replace instr's destination with a new name
    push that new name onto stack[old name]

  for s in block's successors:
    for p in s's ϕ-nodes:
      Assuming p is for a variable v, make it read from stack[v].

  for b in blocks immediately dominated by block:
    # That is, children in the dominance tree.
    rename(b)

  pop all the names we just pushed onto the stacks

rename(entry)

Your Task