Over the last couple of sessions, we have learned about translating abstract syntax into three-address code. Now let's try it out on one of the control statements in BigRig.
Generate three-address code for this BigRig snippet:
assign i := 2.
loop
assign i := i * 2.
exit when i >= max.
assign i := i + 1.
!
Here is a three-address code version:
i := 2
LABEL L1
t1 := i
t2 := 2
t3 := t1 * t2
i := t3
t4 := i
t5 := max
t6 := t4 ≥ t5
IF t6 GOTO L2
t7 := i
t8 := 1
t9 := t7 * t8
i := t9
GOTO L1
LABEL L2
Yes, that is a lot of temporaries. We could try to generate more frugal three-address code, or we could optimize the 3AC code after generating it. Because the value of i over time, we'll need load it into a temp var on each use, but the literal values could be used in place. We could also re-use the same temp var for i each time. Optimizing is sometimes easier after the fact than at generation time.
Now let's take the next step, to target code. We will use Louden's TM assembly language as our target to explore some of the issues that arise at the machine level.
Here is a simple BigRig statement:
if a < b then, a.
From our discussion of translating selection statements to three-address code in Session 24, we might arrive at this three-address code result:
t1 := a
t2 := b
t3 := a < b
IF_NOT t3 GOTO L1
RETURN a
LABEL L1
How can our compiler convert this into TM assembly code? Let's assume that:
An equivalent assembly language program is:
| 3AC STATEMENT | CODE GENERATED |
|---|---|
| t1 := a | LD 1, 4(6) |
| t2 := b | LD 2, 8(6) |
| t3 := t1 < t2 | ??? how ??? |
| IF_NOT t3 GOTO L1 | J?? 1, ?(7) |
| RETURN a | STO 1, return |
Issue #1: TM assembly has no < operation. All of its comparisons use zero as the base. How can we compare a to b then? Let's use a simple transformation:
t1 < t2 → t1 - t2 < 0
So:
| 3AC STATEMENT | CODE GENERATED |
|---|---|
| t3 := t1 < t2 | SUB 3, 1, 2 |
| IF_NOT t3 GOTO L1 | JGE 3, ?(7) |
Issue #2: How can the code generator know how many instructions to skip? TM assembly language does not have labels, so we cannot generate a "jump to location labeled L1" instruction. This is a situation we encountered briefly in Session 24: When the compiler generates code for a boolean expression or a conditional statement, it may not yet know where the target of a jump is. We can take advantage of a feature of TM assembly to "backpatch" the label:
Statements in a TM program are labeled by their integer position in the program! As a consequence, the simulator does not require that a program's statements appear in order. So the code generator can wait to write the JGE instruction until it has generated all of the statements in the then clause, counting the space that those statements take as it goes. Then, when it generates the jump statement, it knows the number of instructions to skip.
So, in our example, the generator will generate the one assembly statement for the body of the clause, and then generate the jump statement to skip over it:
| 3AC STATEMENT | CODE GENERATED |
|---|---|
| IF_NOT t3 GOTO L1 | JGE 3, 1(7) |
What the code generator will produce will actually look something like this on standard output:
0: LD 1, 4(6)
1: LD 2, 8(6)
2: SUB 3, 1, 2
4: STO 1, return
3: JGE 3, 1(7)
Simple, but nice. This approach works for boolean computations and for control structures alike. In particular, you can use it to handle more complex boolean conditions, such as a or b. The complexity, of course, lies in the fact that BigRig conditions use short-circuit evaluation, which means that if a evaluates to true, then the code for the boolean expression must skip the evaluation of b and the subsequent disjunction.
Quick Exercise: What changes if we decide not to "waste" a register on t3 and instead generate:
2: SUB 1, 1, 2
? Hint: Our backpatching has more to count now...
Issue #3: How does return work?
This is a big one, in particular because one of the assumptions I made above that may not work in practice.
I assumed that the code generator could simply store the return value in some location that it already knows about on the stack. That part of my assumption is not unreasonable, and is in fact one way you might implement your own code generator. This is akin to assigning the return value as the value of the function being computed. Some languages make this idea explicit -- in Pascal, for instance, the way one says that the function remainder returns a as its value is to write the statement remainder := a .
The place where I may have oversimplified is that, even if we treat return statements as stores into the return slot on the stack, this operation is actually a part of a return sequence. Unless I do something special to generate the rest of the return sequence at the end of the body of the function, I need to generate it here.
If BigRig were functional, without sequences of statements, generating the rest of the return sequence at the end of the body of the function would be a viable option. In fact, this is an efficient approach, because otherwise the code generator will produce the return sequence twice for every if statement!
We will talk more about generating target code for procedure calls later in this session.
At its heart, generating target code comes down to producing one or more target instructions for each node in the AST or each statement in the intermediate representation. The basic algorithm for code generation will be the same for most operations. Control flow operators are bit different.
(One detail about TM affects our implementation: all arithmetic uses register-only instructions.)
For each three-address code instruction "x := y op z":
- Decide where to store the value of 'y op z'. If x is already in a register, then use that register, else if y is already in a register, then use that register. Otherwise invoke the function getRegister() to get a free register, and move y there.
- Look to see where z is currently stored. If it is not already in a register, then invoke getRegister() to get a free register, and move z there.
- Do the operation on the two registers.
- Copy the value from that register to memory location for x.
Be sure to update your list of registers when you "assign" a value to a register.
One way to optimize this code is to save Step 4 until later, when we are done with the code block or when we need the register.
But how does getRegister() work?
At first, all registers are free, so the code generator can simply grab an empty register when it needs one. Eventually, though, the generator may have used all of the registers, each of which will hold a value from the program. How do registers become available again?
If the code generator always stores its results to memory, into the slots allocated to the temporary and user-defined objects, then the program will never have many registers in use for very long. Then getRegister() won't have to do much. But the compiler will generate inefficient code! Each time its needs a value, it will have to load the value into a register. But many values will be used again soon or even immediately in instructions that follow.
Here are two options for getRegister() that generate more efficient code, at the cost of a more complex code generator:
This technique requires the code generator to maintain a map of (register, object) pairs. Keep in mind that a register may hold two objects at one time -- for example, after an x := y instruction.
If the object won't be used again, there is no need to waste a register holding it. But how can the code generator know this? Before generating code, the compiler can make a backward scan of the three-address code program to see where each value is used next after each instruction and which objects are "live" at the end of the code block.
Just from these two options, you can see that what the 'red' Dragon book says is true:
A great deal of effort can be expended in implementing [getRegister()] to produce a perspicacious choice....
Here is an algorithm to retrieve a register for x in the instruction "x := y op z" that takes advantage of "next use" information:
For target machines that allow operations on memory locations, this algorithm can have a Step 4 that doesn't return a register:
Consider this example:
k := (i + j) - (i + h) - (i + h)
Let's assume that h, i, j, and k are in memory locations 0, 4, 8, and 12, respectively.
| STATEMENT | CODE GENERATED | REGISTER MAP |
|---|---|---|
| . | . | . |
| t1 := i + j | LD 0, 4(6) LD 1, 8(6) ADD 0, 0, 1 |
(R0, t1) |
| t2 := i + h | LD 1, 4(6) LD 2, 0(6) ADD 1, 1, 2 |
(R0, t1), (R1, t2) |
| t3 := t1 - t2 | SUB 0, 0, 1 | (R0, t3), (R1, t2) |
| k := t3 - t2 | SUB 0, 0, 1 ST 0, 12(6) |
(R0, k) |
Note that in the third step the code generator can take advantage of the fact that t1 is in R0 but has no next use in the code block.
Because k is live at the end of this block, the code generator stores its value into memory. To be as efficient as possible, the code generator might maintain a "memory map" that shows the current location of each object's value. Sometimes the location in memory will be out of date!
There are many other strategies for improving efficiency that a code generator can use when allocating registers. For example, it might identify an object that is used frequently in the block and make a global assignment of a register to that object. On machines with plenty of registers, this approach can work quite nicely.
"Plenty" is relative to the kind of source code being translated. For example, functions in a pure functional programming language tend to be small, because those languages don't allow sequences of statements. As a result, the number of objects used by any given function tends to be small. So a target machine with even a small number of registers may make global assignment feasible.
Getting Things Done Your goal now is to produce a working code generator that writes legal, compilable Java code. You do not need a 100% correct type checker or a cross-reference tool to generate code. Focus on the code generator for now.
It is better to have a working code generator that does not handle all of BigRig than to have an "almost working" code generator that handles all of BigRig. If your compiler only "almost works", then it doesn't really "handle all of BigRig"! So, if you are short on time, be willing to assume that the BigRig language consists only of a subset of its features, and implement that.
For example, you might assume that there are no booleans, no selections, and no procedure calls. Generate code for integer expressions. Then generate code for boolean expressions, without short-cut evaluation. Then generate code for the if expression. Then generate code for a procedure call. Save short-cut boolean evaluation for last.
Or, after generating code for integer expressions, you might do procedure calls next. (That's a more impressive step!) Then generate code for boolean expressions, if expressions, and short-cut evaluation, in that order.
Or whatever order makes sense to you. The key is to make choices that let you grow a working code generator rather than produce a lot of code that doesn't quite work yet. As software guru Ward Cunningham likes to say: It's all talk until the tests run. And talk ain't a compiler!
Consider how we might translate this BigRig function:
function ge :=
function with number a, number b and returns boolean :
returns not a < b.
!.
... into three-address code:
ENTRY ge t01 := a t02 := b t03 := t01 < t02 t04 := not t3 return t04 END ge
The ENTRY and END instructions mark code boundaries, so that we can find the size of the target code and the appropriate addresses to branch to and from. The code generator can also use these boundaries to determine whether a variable (and register) has another use.
Now consider how we might translate the corresponding BigRig code to call the ge procedure:
if call ge(count, 0) then,
assign result := call repeat(count-1).
else
assign result := 0.
!
... into three-address code:
BEGIN_CALL PARAM count PARAM 0 CALL ge
The code template for CALL must implement the caller's side of calling sequence. The code template for ENTRY must implement the callee's side of this sequence.
The code template for END must implement the callee's side of return sequence. Who or what is responsible for the caller's side of the return sequence? The code template for CALL must be!
When the code generator encounters a procedure definition, it must generate code for the body and store it in the appropriate location. This is most likely in the static section of the target code, but it could be in a temporary object on the stack. Then it must record that location with the procedure's name in the symbol table.
Consider what the calling sequence part of "CALL update" might do:
return_address := getLabel()
allocate an activation record for ge
; ... evaluate args and store in activation record
LD r1, count
ST r1, first argument slot in activation record
LDC r1, 0
ST r1, second argument slot in activation record
; ... store return address
LD r1, return address
ST r1, return address slot in activation record
What do the other three templates for the calling and return sequences look like?