Assignment #6: IR Translation

Due: .

Do "Chapter 6: Frames", page 132. You may assume that no variable escapes and that all procedures have less than six parameters. There is no output for this part, the main goal is to prepare an interface for building activation records that is independent of the back-end. We will add "Chapter 7: Translation to Trees", page 169. Create a jar file named translate.jar. Submit as usual.

"To simplify the implementation of Translate, you may do without the Ex, Nx, and Cx constructors."

Revisions of the Java class files are found in the jar file support.jar. Avoid modifying the given packages.

An overview of the data structure is given below:

abstract class Exp
  class CONST (int value)
  class NAME  (NameOfLabel label)
  class TEMP  (NameOfTemp temp)
  class BINOP (int binop, Exp left, Exp right)
  class MEM   (Exp exp)
  class CALL  (Exp fun, List args)
  class ESEQ  (Stm stm, Exp exp)

abstract class Stm
  class MOVE  (Exp dst, Exp src)
  class EVAL  (Exp exp)
  class JUMP  (Exp exp, List

Temps and Labels

Somewhat confusing are the following Java classes to be used as is. TEMP is an IR Exp of a name as a temp (NameOfTemp). NAME if an IR Exp of a name as a label (NameofLabel). LABEL is an IR Stmt of a name as a label (NameOfLabel).

Lazy IR Trees

If you do use an abstract representation of the IR trees, you may wish to rename the class.

/*
 * This abstract class is given in its entirety in Appel, Section 7.2, page 159.
 * But the class name 'Exp' seems a particularly bad choice; so do the method names.
 *
 */

package translate;
import tree.Label;
import tree.Exp;
import tree.Stm;

// Lazy view of intermediate representation trees
abstract public class LazyIRTree {
   abstract Exp asExp();                      // ESEQ (asStm(), CONST(0))
   abstract Stm asStm();                      // EVAL (asExp())
   abstract Stm asCond (Label t, Label f);    // CJUMP (=, asExp(), CONST(0), t, f)
}

Lazy IR trees have the advantage of delaying the generation of the actual IR instructions until the context of their use is known. Three different contexts are distinguished: 1) for its value, 2) for its side-effect, and 3) for control flow. These distinctions are especially important for the conditional statement. A boolean expression may be used to evaluate to a value---zero or one---or may be used to control the flow of control. The most efficient IR instructions for these are completely different.

package translate;

import tree.*;

/*
   A specification of this class appears in Appel, 2nd, Chapter 7, page 150.
*/

class IfThenElseExp extends LazyIRTree {

   private final LazyIRTree cond, e2, e3;
   final Label t    = new Label("if","then");
   final Label f    = new Label("if","else");
   final Label join = new Label("if","end");

   IfThenElseExp (final LazyIRTree c, final LazyIRTree thenClause, final LazyIRTree elseClause) {
      assert cond!=null; assert e2!=null;
      cond = c; e2 = thenClause; e3 = elseClause;

   }

   // No if-then-else expression (_?_:_) in MiniJava
   public Exp asExp() {
      throw new UnSupportedException();
   }

   // if-then-else statement as a statment
   public Stm asStm() {
      final Stm seq;
      if (e3 == null) {
         seq = SEQ.fromList (
                  cond.asCond(t, f),
                  new LABEL(t),                 // T:
                  e2.asStm(),                   //     then stmt
                  new LABEL(f)                  // F:
               );
      } else {
         seq = SEQ.fromList (
               cond.asCond(t, f),
               new LABEL(t),                    // T:
               e2.asStm(),                      //      then stmt
               new JUMP(join),                  //      goto join
               new LABEL(f),                    // F:
               e3.asStm(),                      //      else stmt
               new LABEL(join)                  // join:
         );
      }
      return seq;
   }

   public Stm asCond (Label tt, Label ff) { /* ... */ }
}

Output

The main program of the compiler may look something like this:
	 final Exp e = (Exp) parser.parse().value;
	 is.close();
	 if (errorMsg.getErrors()==0) {
	    // Continue only if no syntax errors were encountered
	    final Semantics s = new Semantics (errorMsg);
	    final List frags = s.transProg (e);

	    // Print fragments, even if semantic errors were encountered
	    for (Iterator i=frags.iterator(); i.hasNext(); ) {
	       print ((Fragment) i.next());
	    }
	 }

.PHONY default compiler
default :  compiler

compiler : translate.jar

translate.jar : ...
In this way there are several equivalent ways to initiate the creation of the compiler from the source code:
make                # first target
make default        # the name of the first target perhaps
make compiler       # 
make translate.jar  # the target we want made in asgn #6
I will override the variable SUPPORT as usual.

Turn in the source code for the project using the submission server. The submit project tag for this assignment is . For your convenience, here is a submission form for this assignment.