Held: Monday, 19 April 2004
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:
- Come watch Jim speak today at 4:30!
- Sign up for the picnic!
- New groups for final project.
Overview:
- Translating assignments
- Translating basic operations
- 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.
- The types of the variable and expression should be the same (you've inserted a coercion node already if they're not).
- Version one: Choose your own memory location
- 1. Build the code for the expression.
- 2. Copy the value from the memory location associated with the result
to the memory location associated with the variable.
- Version two:
- 1. Build the code for the expression, telling it to put the
result in the correct location.
- 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).
- 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.
- Consider an expression of the form
exp_{0} + exp_{1}
- Version one: Each expression describes its own result location.
- 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.
- 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.
- 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
- Consider an expression of the form
constant
(e.g., a numeric constant)
- Version one: Expressions return addresses
- Option a: Observation: Constants need locations, too
- Option b: General "locations" include constants
- Version two: Expressions take addresses as paraemters
- Code: Store the constant into result location
- 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.