CS 6013 - Modern Compilers, Theory and Practice

Assignment 4: Constant Propagation.

This assignment is the third part of a multi part project to write an optimizing compiler for Minijava. We start with MiniIR programs and after doing constant propagation (ConstProp), generate programs in MiniIR format.

Use JTB and JavaCC, to write in Java one or more visitors which implement (a) Intra procedural constant propagation (Kildall style) and (b) Interprocedural constant propagation (similar to Callahan, Cooper Kennedy Torczon). Your main file should be called ConstProp.java, if P.miniIR contains a program to be optimized in miniIR form, and P.CG contains the call graph of the program in simpleCG form, then

java ConstProp P.CG < P.miniIR > Pc.miniIR

should create Pc.miniIR in MiniIR form and is semantically equivalent to P.miniIR with some of the variables replaced with constants. The P.CG file is used for inter-procedural constant propagation. Note, your program must take input program from standard input, the call graph information in an input file and write to standard output (so that we can use redirection). To check that a program is in MiniIR form, you could tie the MiniIR.jj and Main.java to build a parser. To ensure that your MiniIR program is semantically equivalent to the Minijava program, you can use the MiniIR interpreter (download) to compare the output of P.miniIR with the output of the Pc.miniIR program generated by ConstProp; say the generated miniIR code is stored in Pc.miniIR, then to invoke the interpreter use: java -jar pgi.jar < Pc.miniIR ].

To avoid overwriting of visitor directories:

$ ls
M.java miniIR.jj simplecgGen

$ jtb miniIR.jj; javacc jtb.out.jj

$ ls simplecgGen
simplecg.jj

$ cd simplecgGen
$ jtb -p simplecgGen simplecg.jj
$ javacc jtb.out.jj
$ vim *.java

Edit all javacc generated files and add package simplecgGen; If it has an import statement of the form import syntaxtree.*; Replace it with: import simplecgGen.syntaxtree.*

$ cd ..

$ javac M.java # works fine. A sample M.java can be found here.

Grading policy
Your homework will be graded for a total of 100 marks. 20 marks for the contributed testcases and 80 marks for the TAs testcases. Students can get upto 10 bonus points by contributing good testcases. Details can be found here.
[ under development ]