Class 28: Translating Declarations and Expressions

Held Friday, November 8, 2002

Summary

Today we begin our serious consideration of the back end. In particular, we begin our consideration of the techniques used to translate expressions and assignment statements.

Notes

• You should start working on phase 3 of the project (type checking).
• I visited the Des Moines Art Museum yesterday. I'd recommend it to anyone who likes modern art. (I only had time for the Iowa artists exhibition and some of the modern art sections, but they were quite interesting.)

Overview

• Translating ...
  • Assignments
  • Basic Operations

Translating Assignment

• Typical form: var := exp.
• Two alternative techniques:
  • One lets each subexpression choose its own memory location.
  • One tells each subexpression where to put the result.
• Version one: Choose your own memory location
  • 1. Build the code for the expression.
  • 2. Check the types of the expression and the variable.
    • a. If they're the same, do nothing.
    • b. If they're different, add code to coerce the result of the expression to the appropriate type. (The result will probably be in a new temporary.)
  • 3. Copy the value from the memory location associated with the result to the memory location associated with the variable.
• Version two:
  • 1. Make sure that the epxression computes the correct type of result. If not, extend it (e.g., with a coerce node) to do so.
  • 2. Build the code for the expression, telling it to put the result in the correct location.

Complicating Factors

• We want to leave the copy fairly generic at this stage, since the result and the variable can be in memory or registers.
• You may want to think about what it means for the variable and the expression to be compound types, like arrays or records. What copying should you then do?
• We'll come back to some of these issues when we deal with procedure calls.
• Note that you can better handle the coercion by changing the structure of the parse tree when you do type checking (to insert a "coerce-to-xxx" node).

Translating Basic Expressions

• Let's consider how we might translate a variety of kinds of operations, using the two strategies described earlier
  • Version one: Expressions return addresses.
  • Version two: Expressions must put their results in a particular address.

Example: Adding two Expressions

• Consider an expression of the form exp + exp1
• Version one: Each expression describes its own result location.
  • 0. Verify the types of both parameters are compatible and coerce if necessary. (Should probably have been done in the type checking phase.)
  • 1. Translate the first argument, remember the location of the result.
  • 2. Translate the second argument, remember the location of the result.
  • 3. Call the appropriate operation, putting the result in an appropriate place.
    • Some architectures provide three-argument arithmetic operations in which you store the result in one of the three arguments.
    • Other architectures provide two-argument arithmetic operations in which the result is stored in one of the two arguments.
    • Still others require you to work with a special result register.
    • For now, it may be better to pretend you have the three-argument version and implement it using the two-argument version by a copy and then assign. The optimization phase should clean things up.
• Version two: Each expression must put its result in a specific location.
  • 0. Verify the types of both parameters are compatible and coerce if necessary. (Should probably have been done in the type checking phase.)
  • 1. Decide on a location for the result of the first expression.
  • 2. Decide on a location for the result of the second expression.
  • 3. Translate the first expression, telling it to put its result in the first location.
  • 4. Translate the second expression, telling it to put its result in the second location.
  • 5. Add the two together, putting the result in the specified location.

Example: Translating a Variable Experession

• Consider an expression of the form id, where id names a variable.
• Version one: Expressions return addresses
  • 1. Memory location: symbols.lookup(id).memloc; Code: none
• Version 2:
  • 1. Code: copy from symbols.lookup(id).memloc to result

Example: Translating a Constant Expression

• Consider an expression of the form constant (e.g., a numeric constant)
• Version one: Expressions return addresses
  • Hmmm ...
• Version two: Expressions take addresses as paraemters
  • Code: Store the constant into result location

Reflection

• Note that the problems with extra potential allocation suggest a hybrid strategy in which you tell an expression where its result should go, but also allow a put the result wherever you'd like parameter.