Lab 7: Static Single-Assignment Form

Overview

In this lab, you will build a static single-assignment form (SSA) for your Tiger compiler to perform optimizations. SSA is a state-of-the-art IR also used in production compilers such as GCC or LLVM.

This lab consists of two parts: first, in part A, you will design and implement data structures defining the static single-assigment form. You will also implement translations from CFG to SSA as well as translations from SSA back to CFG. Second, in part B, you will implement several classic data-flow analysis and optimizations on SSA.

Getting Started

First check out the source we offered you for lab7: 

    $ git commit -am 'my solution to lab6'
    $ git checkout -b lab7 origin/lab7

these commands will first commit your changes to the lab6 branch of your local Git repository, and then create a local lab7 branch and check out the remote lab7 branch into the new local lab7 branch.

Again, you will need to merge your code from lab6 into the new lab7 branch: 

    $ git merge lab6

Do not forget to resolve any conflicts before commit to the local lab7 branch: 

    $ git commit -am 'lab7 init'

You should first import the new lab7 code into your favorite IDE, and make sure the code compiles. There are a bunch of new files that you should browse through: 

    ssa/*:    static single-assignment form and its operations

Hand-in Procedure

When you finished your lab, zip you code and submit to the online teaching system.

Part A: Static Single-Assignment Form (SSA)

The static single-assignment form (SSA) is an important compiler intermediate representation, in which each variable is assigned (statically) at most once. SSA is more advantageous over other compiler IRs in that its single-assignment property makes program analysis and optimization simpler and more efficient. As a result, SSA has become a de-factor IR in modern optimizing compilers for imperative, OO, or even functional languages.

In this part of the lab, you will build a static single-assigment form for your Tiger compiler, and conduct optimizations based on your SSA IR. To aid in your implementation, we have given some hints for most exercises, but keep in mind that these hints are not mandatory, and you are free (and encouraged) to propose your own ideas.

SSA Data Structure

To better reuse your existing code base, you will implement SSA by leveraging data structures already designed for the control-flow graph. This design decision makes the interfaces cleaner and more elegant hence simplifying subsequent compilation phases.

Exercise 1. Read the code defining the SSA data structures in the file cfg/Cfg.java. A basic block b might contain a list of φ-instructions, which reside at the top of a block. Syntactically, a φ-function 
        x = φ((B_1, x_1), (B_2, x_2), ..., (B_p, x_p))
takes a list of tuples (B_i, x_i), 1≤ i ≤ p as arguments and selects one of the variable x_j from these tuples as its value to assign to the left-side x, when the control-flow reach the current basic block from its predecessor B_j. Your task is to extend the SSA data structures with other necessary syntactic features, to support the compilation of full MiniJava.
Exercise 2. Finish the code, in the file cfg/Cfg.java, to visualize an SSA graph, that is, to draw the SSA graph with dot.

Dominator Trees

You will be constructing the SSA form with the following 5 steps: 1) calculate dominators; 2) build dominator trees; 3) calculate dominance frontiers; 4) place φ-functions; and 5) rename variables.

In this part, you will finish the first two steps, that is, you will first calculate dominators then build a dominator tree for a given CFG.

Exercise 3. Calculate, for each node n in the control-flow graph, the dominators DOM[n] for the node n. You should finish this exercise by filling in the method dominators() in the file util/Graph.java.
Hint: to keep your implementation simple, you might use the following data-flow equation to compute dominators directly: 
        DOM[n] = {n} ⋃ (⋂p∈ pred[n] DOM[p])
where DOM[n0] = {n0} for the entry block n0.
Hint: you might first topological-sort the control-flow graph to speed up the calculation, as this equation is forward in nature.
Challenge. While the data-flow equation based algorithm is easy to engineer, it is worst-time complexity is O(n2) due to its use of iterations to reach the fixpoint. Implement a more efficient algorithm to calculate dominators. You might consider the Cooper's algorithm as a starting point.
Exercise 4. Calculate, for a control-flow graph g, its dominator tree t. You should finish this exercise by filling in the method dominatorTree() in the file util/Graph.java.
Hint: you should make use of the dominators DOM[n] already calculated for the node n, and think carefully about the basic data structure design to implement this algorithm.
Exercise 5. Calculate, for a node n in control-flow graph g, its immediate dominator IDOM[n]. You should finish this exercise by filling in the method idom() in the file util/Graph.java.
Hint: you might extend the tree data structure to implement this algorithm.

Dominance Frontier

In this part of the lab, you will be implementing the third step to build an SSA, that is, you will calculate the dominance frontier for each node. The dominance frontier DF[n] of a node n is the set of all nodes d such that n dominates an immediate predecessor of d, but n does not strictly dominate d. Intuitively, the dominance frontier DF[n] for a node n is the set of nodes where n's dominance stops.

Exercise 6. Implement the algorithm calculating dominance frontiers DF[n] for any node n in the CFG. You should finish this exercise by filling in the method dominanceFrontier() in the file util/Graph.java.
Hint: to keep your implementation simpler, you may use the following algorithm to calculate dominance frontier: 
    dominanceFrontier()
        foreach(node n ∈ CFG)
            DF[n] = ∅  // initialized to an empty set
        foreach(node n ∈ CFG)
            if(n has multiple predecessors)
                foreach(predecessor p of n)
                    runner = p
                    while(runner ≠ IDOM[n])
                        DF[runner] ⋃= {n}
                        runner = IDOM[runner]
where IDOM[n] represents the immediate dominator for the node n.

φ-function Placement

In this part, you will implement the fourth step to build an SSA, that is, you will be implementing the φ-function placement. The φ-function placement algorithm places φ-functions at the top of corresponding blocks. Specifically, for a definition 

x = ...

to a variable x in a basic block n, this algorithm will place a φ-function 

x = φ(x, ..., x)

at the top of each n's dominance frontier d ∈ DF[n].

Exercise 7. Implement the algorithm to place the φ-functions, as described by Algorithm 19.6 in the Tiger book. You should finish this exercise by filling in the method placePhiFunctions() in the file cfg/Cfg.java.
Hint: for any basic block b, take care not to place φ-functions more than once for a same variable x.
Hint: φ-function placement has a cascaded effect, that is, placing a φ-function for a variable x at a basic block b also makes b a definition block for x.

Renaming the Variables

In this part of the lab, you will be implementing the fifth and last step to build an SSA, that is, you will rename variables to make its definition unique.

Exercise 8. Implement the algorithm to rename the variables, as described by Algorithm 19.7 in the Tiger book. You should finish this exercise by filling in the method renameVariables() in the file cfg/Cfg.java.
Hint: think carefully about basic data structure design (e.g., variable versions, and stacks).
Hint: to keep your implementation simple, you might want to use a functional programming style, that is, you should construct a new function from an old one instead of modifying the old one in place.

To this point, your Tiger compiler can convert all legal MiniJava programs to SSA forms. Do regression test your Tiger compiler and fix potential bugs.

Translation Out of SSA Forms

Modern machines do not support the φ-functions directly, hence φ-functions must be eliminated before execution. This task is accomplished by the translation out of SSA forms.

Exercise 9. Implement the algorithm to translate a program out of SSA form. Specifically, to avoid the lost-copy problem and the swap problem, you might use the following algorithm: 
    outSSA(ssa)
        splitCriticalEdges(ssa);
        foreach(basic block b, with p predecessors b1, ..., bp)
            suppose b contains m φ-functions:
                x1 = φ(x11, ..., x1p);
                ...
                xm = φ(xm1, ..., xmp);
            generate m fresh variables: t1, ..., tm;
            foreach(b's predecessor block bi, 1≤ i ≤p)
                append these assignment statements at the tail of block bi:
                    t1 = x1i
                    ...
                    tm = xmi
            append these assigment statements at the top of block b:
                x1 = t1
                ...
                xm = tm
where the function splitCriticalEdges() splits critical edges in a directed graph. You should finish this exercise by filling in the method splitCriticalEdges() in the file util/Graph.java, and by filling in the method outSsa() in the file cfg/Cfg.java.

To this point, your Tiger compiler can convert any SSA form back to a corresponding CFG. Do not forget to regression test your Tiger compiler.

Part B: SSA-based Optimizations

SSA makes compiler optimizations not only easier to engineer but also more efficient to execute, largely due to its single-assignment property. This nice property make it much easier to calculate the data-flow information required to perform optimizations.

In this part of the lab, you will re-implement several optimizations that we have done on the CFG on SSA again: dead code-elimination, constant propagation, copy propagation, among others. And you will also implement several novel optimizations that are particularly suitable for SSA: conditional constant propagation, global value numbering, among others.

Dead-code Elimination

In SSA, a statement x = e is dead, if the variable x is not used by any other statement (and e does not have side effects). As a result, this statement x = e can be safely eliminated.

Exercise 10. Implement the dead-code optimization on SSA. You should finish this exercise by filling in methods in the file ssa/DeadCode.java. Note that φ-functions are also assignment statements hence candidates for dead-code elimination.

Constant Propagation

In SSA, given a statement of the form x = c in which c is a constant, we can propagate the constant c to any use of variable x.

Exercise 11. Implement the constant propagation optimization on SSA. You should finish this exercise by filling in methods in the file ssa/ConstProp.java. Note that after the constant propagation optimizations, the assigment statement x = c might become dead statement, manifesting opportunities for dead-code elimination optimizations.

Copy Propagation

In SSA, given a copy statement x = y, then any use of x can be replaced by y.

Exercise 12. Implement the copy propagation algorithm on SSA. You should finish this exercise by filling in methods in the file ssa/CopyProp.java.

φ-function Elimination

In SSA, if a φ-function is of a special form taking a list of same arguments: 

x = φ(c, c, ..., c)

where c is a constant, then this φ-function can be eliminated by rewriting it to a normal assignment to x: 

x = c

Note that, often the time, this special form of φ-function x = φ(c, c, ..., c) might be generated by constant propagation optimizations, which substituted φ-function arguments by constants.

Similarly, the φ-function: 

x = φ(y, y, ..., y)

can be eliminated by rewriting it to an assignment statement: 

x = y

where y is a variable.

Exercise 13. Implement the φ-function elimination optimization on SSA. You should finish this exercise by filling in methods in the file ssa/PhiElim.java.

Conditional Constant Propagation

Challenge. Implement the conditional constant propagation optimization, using the lattice-based approach. You might refer to this paper to start with.

Global Value Numbering

Challenge. Implement the global value numbering optimization. You might refer to this paper to start with.

Partial Redundancy Elimination

Challenge. Implement the partial redundancy elimination optimization. You might refer to this paper to start with.

Do not forget to test Tiger compiler after finishing all these optimizations.

Hand-in

This completes the lab. Remember to hand in your solution to the online teaching system.