Lab 5: Optimizations

Lab Overview

Getting Started

  $ git commit -am 'my solution to lab4'
  $ git checkout -b Lab5 origin/Lab5

Again, you will need to merge your code from Lab4 into the new Lab5 branch:

  $ git merge Lab4

  $ git commit -am 'lab5 init'

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

  ast.optimizations.*         various optimization on the AST
  cfg.*                       control-flow graph on optimizations on it

Hand-in Procedure

Part A: Optimizations on the AST

Optimizations are highly dependent on the specific intermediate representation (IR) used: an optimization may be easy to perform on some kinds of IRs but difficult, if not impossible, on other kinds of IRs. Strictly speaking, as a high-level intermediate representation, abstract syntax trees are not a good IR for the purpose of optimizations, because the control/data flow information are obscure on an AST. As a result, only a few optimization are eligible for ASTs. However, it's not a bad idea for you to write optimizations on the AST as a starting point: first, it will give you some general ideas about how the functional-style optimization strategy work throughout this lab; second, the optimizations you will write on the ASTs, on some cases, will simplify the AST dramatically and thus make later phases of the compiler simpler.

Compiler Passes, Timing and Tracing

For this, we have offered you, in lab 5 code, more command line arguments to control your Tiger compiler more handily. You can find the new arguments by running:

  $ java Tiger -

As an example, read the code in the file ast.optimizations.Main.java, there is the top-level code for the 4 different optimizations you will write on ASTs: dead class elimination, dead code elimination, algebraic simplifications, and constant folding. For now, you don't need to read other files in the directory ast.optimizations, you only need to understand the relative order of these optimizations and how to control them.

Dead Class Elimination

You can use a work-list algorithm to perform dead classes elimination in a given Java program. First, introduce a work-list to hold all live classes. You can read the code in the package ast.optimization.DeadClass.java for the work-list algorithm. Initially, push onto the work-list the Main class which contains the static Java main method, because this class will never be dead. Everytime, if you pop a class A from the work-list and analyze the code of class A, push all classes used in A onto the work-list, repeat this process until the work-list becomes empty.

  $ java Tiger -testFac -trace ast.DeadClass

Dead Code Elimination

Algebraic Simplification

Constant Folding

Part B: Control-flow Graph (CFG)

Control-flow Graph (CFG)

Basic Blocks (BBs)

So what are basic blocks? A basic block is a sequence of code that can only enter from the first instruction and exit from the last instruction. So, intuitively, you can only enter a basic block from the first instruction and executes each instruction contained therein in turn, until reach the last instruction; you can NOT enter or exit from the middle of a basic block.

The statements in a CFG (code cfg.stm.*) are different from those in a C AST (code codegen.C.stm.*). The representation for the CFG statements makes use of three address code (TAC), a widely used compiler intermediate representation in many production compilers.

The name three-address code reflects one important property of this intermediate representation: in general, most statements contain at most three operands (addresses) (although variants of TACs may contain more or less addresses). For instance, consider the add statement defined in cfg.stm.Add.java, the syntax for this statement should be dst = left + right, in which both left and right are operands, and dst is the destination of this assignment to store the addition result. Furthermore, you can see that the types for both left and right are cfg.operand.T, which is either a variable or an integer literal. So if we treat an integer literal as a general form of address, there are totally 3 addresses. Besides the three addresses left, right, dst, there is also one operator +, so, for this reason, TAC is also called a 4-tuple in some literatures.

In the package cfg.stm, there are now a bunch of different definitions for statements: addition, virtual method invocation, less than, value movement, object allocation, printing, subtraction, and multiplication. Again, these statement are only enough to compile the test/Fac.java test case. In the remaining part of this lab, you will add more statements to compile the full MiniJava.

  $ java -cp bin Tiger -testFac -dump C

  // Control-flow Graph

Graph Visualization

  $ dot -?

Usage: dot [-Vv?] [-(GNE)name=val] [-(KTlso)] 
(additional options for neato)    [-x] [-n]
(additional options for fdp)      [-L(gO)] [-L(nUCT)]
(additional options for memtest)  [-m]
(additional options for config)  [-cv]
...

  $ java Tiger -testFac -visualize jpg

Your code here:

CFG Generation

You can find this code generator in the visitor cfg.TranslateVisitor.java, which traverses a C AST and generates a CFG AST.

Part C: CFG-based Optimizations

In this part of the lab, you will write several classical program analysis: liveness analysis, reaching definitions, available expressions, and so on. And you will also write several classical optimizations (based on these analysis): constant propagation, copy propagation, dead code elimination, etc..

Liveness Analysis

You will write your liveness analysis algorithm (in fact, most data-flow analysis algorithms) on a block granularity, so you should take a look at the general steps in such an algorithm:

data_flow()
  calculate the gen and kill sets for each statement and transfer;
  calculate the gen and kill sets for each basic block;
  calculate the in and out sets for each basic block;   // fix-point
  calculate the in and out sets for each statement and transfer.

  $ java -cp bin Tiger -testFac -trace liveness.step1

Dead-code Elimination

Reaching Definitions

Constant Propagation

Copy Propagation

Available Expressions

Common Sub-Expression Elimination (CSE)

Safe Points and Precise GC

Recall that, in lab 4, you have written the Gimple garbage collector. To help Gimple find the roots, the Tiger compiler will generate GC stack frames telling Gimple where to locate the roots. One key point to note is that the GC stack frames is a one-to-one correspondence to the call stack frames, that is, there is just one GC stack frame on one call stack frame (and thus one function).

Though simple to implement, this approach has serious drawbacks, it can not collect garbage precisely. Consider one challenge problem from the previous lab:

  A f (){
    A x, y;
    x = new A();
    // suppose that Java heap is out of space here...
    y = new A();
    return y;
  }

In order to perform a much precise garbage collection, we can introduce the concept of safe points: positions which are safe to emit GC stack frames. Because the MiniJava language you are compiling is single-threaded, so the safe points are function invocations (including constructor invocations). The basic idea is to emit different GC stack frames before each function invocation, and each GC stack frame only contains the live references at that point (that is: the live in set of that function invocation). To better understand this, consider the code fragment above, you can generate two different GC stack frame for the two method invocations, like this:

  A f (){
    A x, y;
    // generate the first frame (empty):  {}
    x = new A();
    // generate the second frame: {y}
    y = new A();
    return y;
  }

Handin