CSC362, Class 33: Translating Expressions (Trying Again)

Admin:
* Advising signup going through class

Overview:
* Background
* Translating assignments
* Translate basic expressions
  * Variables
  * Constants
* Translate compound expressions
* Arrays

Observation: We're now at the stage in which we can generate some stuff
that's pretty close to assembly
* For ease of translation, we'll build trees rather than lists
* For ease of translation, we'll allow a wide variety of addressing modes
  * Fixed location
  * Offset from stack pointer
  * Offset from register (offset of 0 is a nice simple pointer)
  * MEM[MEM[XXX]]
* PAL, the pseudo-assembly language, will be our "target" language
  * Examples will often be in higher-level constructs

Translation is a lot like type checking
* You generate a code attribute for each node
* The code for a node typically depends on the type of the node and the code for its children

Where to start?  Variables, expressions and assignment

Variables: We should be able to determine a location in memory for each variable
* Stored as an attribute in the symbol table
* Global variables: Stack frame or in "static memory" (e.g., x is a MEM[132])
* Local variables: Stack frame (offset NNN from current FP/BP)
* Semi-local (in enclosing procedure): Double indirection (get the start of the ancestor frame, offset from there)
  * If the parent pointer is at offset 8 from the base of the frame and variable x is at offset 24 from our grandparent, we use
   MEM[fp+8] - Address of the start of the frame of the parent
   MEM[MEM[fp+8]+8] - Address of the start of the frame of the grandparent
   MEM[MEM[MEM[fp+8]+8]+24] - Address of the start of the frame of the grandparent
* Parameters (like local)
* Temporaries (new locations needed for intermediate results)
  * For now, we have an almost unbounded number
  * Later, we'll turn each temp into a register or shove it on the stack

Related problem: 
* Dealing with user-defined types (skipped)
* Keeping track of scope (

When you call a procedure, what do you put in the parent pointer?  Depends on relationship:
* If the callee is a child, put the current fp in the "parent pointer"
* If the callee is a sibling, copy the current "parent pointer"
* If the callee is a parent or ancestor, follow links upwards

Assignment statement
  var := expression
Two strategies for translation
* Strategy one
  * Determine the address associated with the variable (and any code needed to compute it)
  * Determine the address associated with the result of the expression (and code needed to evaluate the expression)
  * Code for assignment: Concatenate(code-for-var, code-for-expression, "MOVE address-of-exp-result into address-of-variable")
* Strategy two
  * Determine the address associated with the variable (and any code needed to compute it)
  * Translate the expression, telling the translator to store the result in the address just given
  * Concatenate
x := a + b
Strategy one:
	ADD MEM[a] MEM[b] -> temp
	MOV temp -> MEM[x]
Strategy two
	ADD MEM[a] MEM[b] -> MEM[x] 
Experience suggests that strategy one plus post-optimization is better

More kinds of expressions
* Constant
* Exp OP Exp  
* OP Exp 
* ( Exp )
* Var[Exp]

How do we translate variables?
* Look 'em up in the symbol table; No code needed

How do we translate constants?
* Option 1
  * Generate a new temporary, t1
  * Generate MOVE constant, t1
  * Return address: t1, code: (see above)
* Option 2
  * At compile time, generate introductory instructions to store each constant in static memory (and the symbol table)
  * Return that address (no code)

How do we translate Exp0 + Exp1
* Allocate a new temporary, tresult
* Generate code and address for Exp0 (code0, result0)
* Generate code and address for Exp1 (code1, result1)
* Return address = tresult, code concatenate(code0, code1, "ADD result0, result1, tresult")
  * Complicated part: What kind of addition is it?

How do we translate OP Exp?
* Similar

How do we translate ( Exp )?
How do we translate ( ( Exp ) )?
How do we translate ( ( ( Exp ) ) )?
* Translate the expression
* Return those results directly

How do we translate Var[Exp]?
* Determine the code and address for Var (codev, addressv)
* Determine the code and address for Exp (codee, addresse)
* Determine the size of values stored in the array
* We want to MEM[addressv + size*addresse]
  Generate a new temp, t
  return code = concatenate(codev, codee, "IMULT SIZE, ADDRESSE -> t")
  return address = MEM[addressv + t]
previous assumes 0-based arrays
What if the user has set a starting index to, say, 5?
* Need to subtract 5 from ADDRESS_E before doing the multiplication