Labs 11

Today, Nov 26th, you hand in a working MiniJava+ to JVM compiler, congratulations! Hopefully it will do well in the cc08 competition.

This week you will write a translation from your MiniJava+ ASTs to Control Flow Graphs (CFGs), similarly to what was shown for the while language in Lecture 11. You will be able to inspect these graphs visually using GraphViz. The CFGs will then be used in the following labs to perform analyses on MiniJava+ code.

This is a one week assignment. It is due on Wednesday, Dec. 3rd, 8.15am.

• Flow-control constructs disappear as they get encoded into the, well, control-flow graph. Instead, we add the Assume statement. We also add a Skip statement which can be useful during the construction of the CFG, but which should then be eliminated at a later stage.
• We have a distinction between expressions and simple values:
  • A simple values is whatever cannot be flattened more (identifiers and constants, essentially)
  • An expression combines simple values: we have binary operations, unary operations and (n+1)-ary operations (method calls). Note that an array read is simply a binary operation with a funny syntax. Similarly, creating a new array of integers is a unary function. Oh, and simple values are nothing but 0-ary functions, when you think about it (or constants). See CFGTrees.scala for details.
• We have two kinds of identifiers:
  1. The ones we “reuse” from the original AST. We can attach symbols —and types— to them, which will be useful to output warnings or error messages about them as a result of future analyses. For the same reason, they are also positional objects.
  2. New, “temporary” ones that we introduce to flatten out expressions. These are typed but not attached to symbols.
• We don't bother attaching types to general expressions. We assume that type checking already eliminated all type-incorrect programs, and that our new transformation will preserve this correctness.
• We define the special variable result# which always corresponds to the returned value of the method. Given that in MiniJava+ there can only be exactly one return statement per method, our CFGs will always have a value assigned to result# as their last transition into the exit point.

Your compiler should generate one .dot file per method in the input file (all methods of all classes, that is), except for the main method which we won't bother analyzing. Here is for instance the graph generated for the method ComputeFac of our good old Factorial.java example:

//Factorial class Factorial{ public static void main(String[] a){ System.out.println(new Fac().ComputeFac(10)); } }   class Fac {   public int ComputeFac(int num){ int num_aux ; if (num < 1) num_aux = 1 ; else num_aux = num * (this.ComputeFac(num-1)) ; return num_aux ; }   }

You can view .dot files using dotty from the GraphViz suite, or by converting them to .ps or .jpg files using:

dot file.dot -Tps -o out.ps

or:

dot file.dot -Tjpg -o out.jpg

If you are using Windows, you can download a user interface from the GraphViz website to produce similar results.

Note that the code to generate the graphs is already given. All you have to do in this lab is:

1. understand the stubs
2. write the translation function from ASTs to CFGs

Since this is a one week assignment, we give you all the code except for the translation function itself. This includes:

• LabeledDirectedGraph.scala — a class defining graphs and some operations on it
• CFG.scala — a concrete class to represent control flow graphs using the previous class
• CFGTrees.scala — a hierarchy of statements and expressions to use as labels in the CFGs
• ASTtoCFG.scala — a stub of the translation function from ASTs to CFGs. Use the material in Lecture 11 to figure out how to complete it.

You may also find the following bash code useful to visualize all the graphs:

rm -f *.ps
for d in *.dot; do
    dot $d -Tps -o ${d}.ps
done
 
for p in *.ps; do
    gv $p &
done

Also, you will need to update your Compiler.scala file with this code.

Finally, this wouldn't really be a compiler construction lab without the little schema at the end, so here you go:

src
 └── minijava
      ├── Compiler.scala                    (update to generate .dot files)
      ├── Main.scala                        (given in the Code Generation lab)
      ├── Positional.scala                  (given in the Lexer lab)
      ├── Reporter.scala                    (given in the Lexer lab)
      ├── TreePrinter.scala                 (completed in the Analyzer lab)
      │
      ├── analyzer
      │    ├── Analyzer.scala               (completed in the Type Checker lab)
      │    ├── Symbols.scala                (completed in the Type Checker lab)
      │    ├── TypeChecker.scala            (completed in the Type Checker lab)
      │    └── Types.scala                  (completed in the Type Checker lab)
      │
      ├── code
      │    └── CodeGenerator.scala          (completed in the Code Generation lab)
      │
      ├── controlflow
      │    ├── ASTtoCFG.scala               (stub given this week)
      │    ├── CFG.scala                    (given this week)
      │    ├── CFGTrees.scala               (given this week)
      │    └── LabeledDirectedGraph.scala   (given this week)
      │
      ├── lexer
      │    ├── Lexer.scala                  (completed in the Parser lab)
      │    └── Tokens.scala                 (completed in the Parser lab)
      │
      └── parser 
           ├── Parser.scala                 (completed in the Parser lab)
           └── Trees.scala                  (completed in the Type Checker lab)

As usual, submit your compressed src directory through Moodle, before Wednesday, Dec. 3rd, 8.15am.