Lab 3: Control-flow Graphs

Overview

In this lab, you will design and implement a control-flow graph (CFG) intermediate representation for your Tiger compiler, and lower down MiniJava programs to this CFG representation by translating the abstract syntax trees to the intermediate representation you designed.

This lab consists of four parts. In part A, you will design and implement the control-flow graph representation by defining its data structures. In part B, you will eliminate the object-oriented features in MiniJava by leveraging a prefixing algorithm. In part C, you will design and implement a translator to lower down the abstract syntax tree to the control-flow graph. Finally, in part D, your will design and implement several program analysis and optimizations for the CFG.

Getting Started

First check out the source we offered you for lab 3: 

    $ git commit -am 'my solution to lab2'
    $ git checkout -b lab3 origin/lab3

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

Again, you will need to merge your code from lab2 into the new lab3 branch: 

    $ git merge lab2

Do not forget to resolve any conflicts before commiting to the local lab3 branch: 

    $ git commit -am 'lab3 init'

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

    cfg/*:    control-flow graph data structures and operations

Hand-in Procedure

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

Part A: Control-flow Graph

A control-flow graph (CFG) is a directed graph-based program intermediate representation with basic blocks as nodes and control transfers between blocks as directed edges. A control-flow graph is a good intermediate representation as it makes program control properties explicit thus easier to compute and reason about. Furthermore, CFG also provides a foundation for data-flow analysis, as we will examine in lab7. As a result, in modern compilers, CFGs serve as not only carriers for compiler optimizations, but also backbones for more advanced intermediate representations such as static single-assignment forms (SSA).

Data Structures

In this part of the lab, you will first design and implement data structures defining the control-flow graph.

Exercise 1. Read the code in cfg/Cfg.java, make sure you understand the Java code defining CFG data structures we offered you. Your job is to fill in the missing code in the various pp methods.

It is often useful to measure the sizes of the generated CFG, which are useful to estimate the resource occupation including memory footprint as well as compilation time. For example, after you have implemented a compiler optimization to shrink the target CFG, you can evaluate the effectiveness of your optimization by comparing the sizes before and after that optimization.

Exercise 2. Finish the size() methods in the file cfg/Cfg.java, to measure the size of the CFG in terms of the numbers of functions, basic blocks, and statements. The output might consist of a list of triples <numMethods, numBlocks, numStms>, like the following output 
<#methods, #blocks, #statements>
---------------------------------
<"f1()", 5,  300>
<"g()",  30, 400>
...
---------------------------------
subtotal: 10, 140, 25000
This output specifies that the method f1() comprises 5 basic blocks and 300 statements, whereas the method g() contains 30 basic blocks and 400 statements, and so on. In a summary, the program comprises 10 methods, 140 basic blocks, and 25,000 statements.

Graph Visualization

It is nice to visualize a control-flow graph, making subsequent graph analysis and transformations more intuitive. Nevertheless, to draw a figure prettily is a nontrivial task and may require too much programming effort, especially for large and complex graphs. Fortunately, there are many off-the-shelf graph drawing utilities, so that we do not need to reinvent the wheels. Specifically, your Tiger compiler will make use of Graphviz, a very popular graph visualization software, to visualize the control-flow graphs generated by your Tiger compiler.

Exercise 3. Download graphviz and install it on your machine. Do not forget to add it to your PATH. To make sure you have installed graphviz correctly, you can run the following command on your prompt: 
$ dot --help
Usage: dot [-Vv?] [-(GNE)name=val] [-(KTlso)<val>] <dot files>
(additional options for neato)    [-x] [-n<v>]
(additional options for fdp)      [-L(gO)] [-L(nUCT)<val>]
(additional options for config)  [-cv]
...
Moreover, you can take a look at its manual, if you are interested in.

The Tiger compiler has rudimentary support to visualize a CFG bye leveraging Graphviz. Specifically, it can visualize each function in a program by drawing its directed graphs, respectively.

Exercise 4. Finish the code dot() in the file cfg/Cfg.java, to draw the CFG for each function. Specifically, your task is to extend the dot() to draw statements and transfers in each block besides block labels. You should run the test cases to test your implementation. For example, run your code against benchmark/SumRec.java: 
$ java -cp build/libs/Tiger-1.0.jar Tiger ./benchmark/SumRec.java -dot cfg
to draw CFGs.

Do not forget to test your Tiger compiler extensively before continuing. Especially, make sure your Tiger compiler can compile all testcases under the directory benchmark/.

Part B: Class Elimination

The class elimination pass implements object-oriented features in MiniJava by lowering down them to low-level constructs. Specifically, this pass finishes three sub-tasks: 1) it eliminates classes by translating them to C-style structures; 2) it closes each (non-static) method by introducing an explicit this as the first parameter; and 3) it translates each method invocation into a virtual function call. In the following, we will discuss the first two steps in more details and leave the last step to the next section (part C).

The Prefixing Algorithm

The prefixing algorithm builds an inheritance tree, and eliminates class inheritance by a level-order tree walking.

Exercise 5. Finish the method buildInheritTree0() to build an inheritance tree, with each tree node containing a class. When finished, you might visualize the inheritance tree to test your implementation.
Exercise 6. Finish the method prefixOneClass() to implement the prefixing algorithm.

To this point, your Tiger compiler should compile a MiniJava class C into two components: a structure C_S (like struct in C) holding all its instance field, and a virtual function table C_V holding a list of function pointers to all the constituting methods in that class. Test your Tiger compiler and fix any bugs before continuing.

Closing Method

Exercise 7. Extend your implementation of the method prefixOneClass(), to close each method by introducing an extra this argument as its first parameter. Pay special attention to the type of that parameter. For simplicity, you can generate an empty CFG function for each AST method serving as place-holders and fill in that function in subsequent phases.

Part C: CFG Generation

The CFG generation phase generates a CFG representation for the given abstract syntax tree. The generation makes use of a recursive-decedent algorithm.

Exercise 8. Finish the methods doitMethod(), doitStm(), and doitExp(), to translate a given method, statement, and expression to its corresponding CFG representation, respectively.

To inspect the generated CFG data structure, you might compile the test case we provide. For example, you can compile the test case benchmark/SumRec.java to inspect the generated CFG: 

    $ java -cp ./build/libs/tiger-1.0.jar Tiger -trace cfg.Translate.doitProgram <program>

Do not forget to test your Tiger compiler using the test cases in benchmark/ as well as your own ones. Fix any bugs before continuing.

Part D: Program Analysis and Optimizations on CFGs

In this part of the lab, you will familiarize yourself with program analysis and compiler optimizations by writing several classical program analysis (e.g., liveness analysis, reaching definitions, and available expressions), and optimizations (e.g., constant propagation, copy propagation, and dead code elimination).

You will write most data-flow analysis algorithms with the following general template: 

data_flow_analysis()
    calculate the gen and kill information for each statement and transfer;
    calculate the in and out information for each statement and transfer.   // fix-point

For specific data-flow algorithms you will write next, the above general template differs in several aspects: 1) how to define gen and kill information, 2) how to calculate in and out information, 3) in what order to conduct the iteration; and 4) when to stop. Hence, you will need to modify this algorithm template to finish the specific analysis.

Liveness Analysis

A liveness analysis calculates the live-in and live-out variable sets for each statement, transfer, and basic blocks in a function. In liveness analysis, you should calculate gen and kill for a basic block; and leverage the fix-point algorithm to calculate the in and out sets for each basic block in a reverse topo-sort order.

Exercise 9. Finish the liveness analysis code in the source file cfg/Liveness.java by implementing the aforementioned algorithm.

A particularly interesting application of liveness analysis is to detect uninitialized variables. An uninitialized variable refers to a variable that is used before being assigned a value, which might trigger subtle errors during execution.

Exercise 10. Design and implement an algorithm to detect uninitialized variables, by leveraging the liveness information.

Reaching Definitions

A reaching definition analysis analyzes which definition of a variable can reach a specific use of the variable.

Exercise 11. Implement the reaching definition analysis in the file cfg/ReachDef.java, as described by the algorithm in Table 17.2 of the Tiger book. This algorithm is similar to the liveness analysis algorithm, except for it performs the analysis in a forward manner.

Available Expressions

Available expression is a program analysis algorithm that determines for each point in the program the set of expressions that need not be recomputed. Consider the statement x = y op z, if the expression y op z has been computed before this statement, then the expression y op z can reuse the computed result. Hence, you can compute whether the expression y op z is available at a specific program point.

Exercise 12. Finish the available expression analysis in the file cfg/AvailExp.java.

Dead-code Elimination

Dead-code elimination (DCE) is a compiler optimization to remove dead code (that is, code that does not affect the program results). Specifically, an assignment statement x = e is dead, if the variable x does not used anywhere and the expression e has no side effects. To this end, this statement can be safely removed.

Exercise 13. Finish the dead code elimination in cfg/DeadCode.java by implementing the aforementioned algorithm. You should avoid the pitfalls discussed in the Tiger book by not removing live statements. Also note that removing one dead code may have cascading effects to make other code dead, so make sure that your dead-code elimination optimization can eliminate all dead code.

Constant Propagation and Folding

A constant propagation and folding replace an expression by its computed values when all its operands are constant. For example, for any statement s of the form x = y op z, where the variable y and z are defined by y = c_1 and z = c_2, respectively, where c_1 and c_2 are both constants. We can replace x = y op z by x = c, where c = c_1 op c_2.

Exercise 14. Finish the constant propagation and folding algorithm in the file cfg/ConstProp.java. Note that folding and propagating constants may introduce dead code, you should think carefully how to remove these dead code by leveraging existing optimizations.

Copy Propagation

Copy propagation is the process of replacing the occurrences of targets of direct assignments with their values. Suppose, for a statement s x = y or x = y op z, where y is defined by some statement like y = t. Suppose the definition y = t is the unique definition that reaches the statement s. Then we can replace the variable y, in the statement s, by the variable t.

Exercise 15. Finish the constant propagation code in the file cfg/CopyProp.java.

Common Sub-Expression Elimination (CSE)

Common subexpression elimination (CSE) is a compiler optimization that searches for instances of identical expressions (i.e., they all evaluate to the same value), and analyzes whether it is worthwhile replacing them with a single variable holding the computed value. Specifically, for the statement x = y op z, if the expression y op z is available. We can substitute the expression y op z with the most recent definition using y op z. You may refer to the Tiger book section 17.3 for more details of this algorithm.

Exercise 16. Implement common sub-expression elimination optimization in cfg/Cse.java.

Hand-in

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