 # Homework Assignments Week 2.4: Code Generation

### Compilation Schemas

The following assignments have you derive from a definition of the dynamic semantics of a construct of the Tiger language, a compilation schema for that construct that translates it to a JVM byte code. The full definition can be found on github. The definitions for abstractions such as `lookup` and `allocate` where discussed in Lecture 14. The compilation schema is discussed in Lecture 13.

#### Arithmetic Expressions

Consider the following

``````rules // integers

Int(i) --> IntV(parseI(i))

Uminus(e) --> Minus(Int("0"), e)

Leq(IntV(i), IntV(j)) --> IntV(leqI(i, j))
``````

#### Function Calls

Consider the following DynSem definition of the execution of Tiger function calls. Design a compilation schema that translates a function call to JVM bytecode. What assumptions do you make on the translation of function definitions?

``````rules // function call

Call(f : Id, args) --> v
where
evalArgs(params, args) --> E';
E {E', E} |- e --> v

evalArgs([], []) --> {}

evalArgs([FArg(x : Id, _) | args], [v | es]) --> {x |--> a, E}
where
allocate(v) --> a;
evalArgs(args, es) --> E
``````

#### Nested Functions

Tiger has nested function definitions. Design a compilation schema for compiling such functions to JVM byte code

``````let
function power(x: int, n: int): int =
let
function pow(n: int): int =
if n = 0 then 1 else x * pow(n - 1)
in pow(n)
in
power(3, 4)
``````

Nested functions may mutate the local variables of their parent function:

``````let
function power(x: int, n: int): int =
let
var p : int := 1
function pow(n: int): int =
if n = 0 then p
else (
p := x * p;
pow(n - 1)
)
in pow(n)
in
power(3, 4)
``````

#### Records

Consider the following DynSem definition of the execution semantics of Tiger records creation and record access. Design a compilation schema that translates a record to JVM bytecode.

``````signature
constructors
NilV : V
RecordV : Env * Int -> V
arrows
initFields(List(InitField)) --> Env

rules // records

NilExp() --> NilV()

Record(_, fields) --> RecordV(E, fresh)
where initFields(fields) --> E

initFields([]) --> {}

initFields([InitField(f : Id, v) | fields]) --> {f |--> a, E}
where
allocate(v) --> a; initFields(fields) --> E

FieldVar(lv, x : Id) -lval-> a
where
read(lv) --> RecordV(E, _); E |- lookup(x) --> a
``````

#### Other Compilation Schemas

Similarly consider compilation schemas for other Tiger constructs, such as:

• Let bindings with local variables
• For loop with bound iteration variable
• Break statement in for/while loop
• Array types, creation and access

### Code Generation Mechanics

#### String Generation

• List three techniques for generating strings directly

#### AST Generation

• What is the advantage of AST generation over string generation?
• What does it require to guarantee syntactic correctness of generated code?
• How does Stratego guarantee syntactic correctness of generated code?

#### Concrete Object Syntax

• What is concrete object syntax?
• What is the general architecture for implementation of concrete object syntax?
• What properties of generated code does concrete object syntax guarantee?

### Optimization

#### Peephole Optimization

Byte code can be optimized by considering patterns of subsequent instructions and rewriting them to more efficient instructions. Study the following Jasmin code and its sequence of optimizations on the slides of Lecture 13. What peephole optimization rules can you infer from that sequence?

``````.method public static fac0(I)I
ldc 0
if_icmpeq label0
ldc 0
goto label1
label0: ldc 1
label1: ifeq else0
ldc 1
goto end0