Homework # 8
due 2006/4/11

Temporaries Attribute Grammar

Write an attribute grammar for Cool expressions and branches that

• Assigns an inherited attribute reg to each expression/branch that indicates which register (a number) to compute the result into: r1, r2, r3, ...; and
• Computes the maximum register number maxreg used in each expression or branch tree as a synthesized attribute.

Don't worry about running out of registers (don't spill registers). Use Figure 9.8 as an inspiration, except that you need to use Cool ASTs, not the book's, and you don't need to generate code. Please don't use a macro like handle_op. For example:

loop(cond,body : Expression)
  cond.reg = reg
  body.reg = reg
  maxreg = max(cond.maxreg,body.maxreg)

integer_constant(token : Symbol)
  maxreg = reg // don't need any others beyond this

Assume that let-bound and case-bound variables will be stored in temporary registers just like operands.

Spilling

The code generated by Figure 9.8 is very poor. In particular it may spill the same register over and over even when the saved value is not changing. A better way to do spilling is to use the ``maximum register needed'' attribute you defined in your attribute grammar, to generate code that spills an intermediate result at the point it is defined, if we know we're going to need the register for a subcomputation. That way, the intermediate value will be spilled and restored only once. This improvement can be accomplished through a few changes in the macro handle_op.

• Assuming the number of available registers $k$ is 4, give an expression that requires 6 registers and will cause register 1 to be spilled multiple times between its original definition and eventual use.

• Indicate in the code which temporary values will be spilled, perhaps multiple times. Circle the binary operators whose left operands will be spilled while evaluating the right operand.

• Figure out how to determine which expressions will be spilled ``ahead of time,'' that is, at the point the temporary is originally defined. Change the macro handle_op and explain what you are doing.