Hpc Translation To IR

Tiger in Stratego -- Compilation by Program Transformation
Translation to Intermediate Representation

This is the second set of HpcExercises. These will teach you to write a more complex transformation (translation to IR) in Stratego.

  1. Download the new version (0.3) of WebHome and install it. (There is a distribution with precompiled binaries for Suns.)

  1. Finish the desugaring component (sig/Tiger-Desugar.r) and test it. (See ApplyingTisComponents? for instructions on how to use the components of the TigerCompiler.)

  1. Use the Tiger-Abstract-Syntax-Format checker to check that the output of your desugarer conforms to the format by making prog.tas.check.

  1. Use the typechecker to typecheck some Tiger programs (by calling gmake prog.tc.tas).

  1. Extend the translation of expressions in modules Translate-Expressions.r and Translate-Statements.r to cover all constructs of the language. This entails writing a rule TrExp? for each expression construct in the language. Note that the translation of declarations is covered in Translate-Declarations.r.


Note that the typechecker annotates the constructors for array subscription (Subscript), record field selection (FieldVar?), array creation (Array) and record creation (Record) with the types of the data structures. This is necessary for the translator to know the size of these data structures (in particular offsets into records).

When you first define the translation don't be concerned with optimizing chains of jumps. Just evaluate an expression to its boolean value and then compare to 0 to make a jump as in

CJUMP(NE, e, CONST(0), t, f)

Also don't be concerned about putting arguments of function calls in parameters. All formal parameters and local variables are stored in the stack frame.

The MEM operator of the IR works both as fetch and store. (See section 7.2: Structured L-values.)

Sometimes it is useful to mix IR and Tiger abstract syntax, for example when translating the For statement.

When you got the basic translation to work try to introduce short circuit evaluation of Boolean expressiosn by using the Cx constructor. If some (sub-)expression 'e' should be interpreted as a Boolean expression, wrap a 'Cx(e, t, f)' around it to indicate that there should be a jump to 't' when the expression evaluates to true and to 'f' otherwise. This pseudo construct can then be optimized if possible. The default case should just do what you were doing al along:

TrCx? : Cx(e, t, f) -> CJUMP(NE, e, CONST(0), t, f)

The next exercise is to do escaping variables analysis to determine which variables can be stored in registers.