====== Labs 11 ======

Today, Nov 26th, you hand in a working MiniJava+ to JVM compiler, congratulations! Hopefully it will do well in the [[race|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 [[http://www.graphviz.org/|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.

===== Statements, expressions, simple values and variables =====

  * 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 [[lab11-cfgtrees|CFGTrees.scala]] for details.
  * We have two kinds of identifiers:
    - 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.
    - 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 [[MiniJavaPlus|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.





===== Output =====

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:

| <code java>//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 ;
    }

}
</code>  |  {{compilation:fac-computefac.dot.jpg?200 }}  |

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 [[http://graphviz.org|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:
  - understand the stubs
  - write the translation function from ASTs to CFGs






===== Stubs =====

Since this is a one week assignment, we give you all the code except for the translation function itself. This includes:
  * [[lab11-ldg|LabeledDirectedGraph.scala]] --- a class defining graphs and some operations on it
  * [[lab11-cfg|CFG.scala]] --- a concrete class to represent control flow graphs using the previous class
  * [[lab11-cfgtrees|CFGTrees.scala]] --- a hierarchy of statements and expressions to use as labels in the CFGs
  * [[lab11-asttocfgstub|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:
<code bash>
rm -f *.ps
for d in *.dot; do
    dot $d -Tps -o ${d}.ps
done

for p in *.ps; do
    gv $p &
done
</code>

Also, you will need to update your ''Compiler.scala'' file with [[lab11-compmods|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)


===== Deliverables =====

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