The label generation approach to control structure compilation discussed in the previous section required two-passes. The macro version of this solution rested on a two pass assembler, while the suggested incorporation of this method into a "load and go" compiler for our calculator's language requires that all branches be indirect, through a table of labels.
Many one-pass compilers and assemblers use a different approach to generating code. The following macros illustrate this, in a simple form:
MACRO LOOP
LOOPTOP = .
FIXUP = 0
ENDMAC
MACRO ENDLOOP
JUMP LOOPTOP
IF \(FIXUP = 0)
SAVELC = .
. = FIXUP
JUMP SAVELC
. = SAVELC
ENDIF
ENDMAC
MACRO EQUALS
ADDSI R2,-8
LOAD R4,R2,4
LOADS R3,R2
CMP R3,R4
BNE .+6
FIXUP = .
. = . + 4
ENDMAC
Here, we assume that loops are never nested, and that each loop contains
exactly one exit. Backward branches are easy because the destination
address is known at the time the location containing the branch is reached
during the assembly process.
Forward branches are far more challenging. In the above code, the solution is to simply avoid the problem! During assembly of the EQUALS macro, the code simply remembers where to put the branch to the end of loop, using the label FIXUP, and reserves space for the branch (using .=.+4). Later, when the ENDLOOP macro is assembled, the current location counter is set aside, using SAVELC, and the branch to the end of loop is assembled at the location where FIXUP pointed.
Note the use of the IF and ENDIF assembly directives! These control what lines are assembled. If the operand of the IF statement is false -- in this case, if FIXUP is still equal to zero, the assembler ignores everything up until the ENDIF (or until the ELSE, if an ELSE is present). The conditional was needed here to prevent attempts to fix the loop exit if there was no loop exit to fix.
Ignoring the problem of loop exit, this method can be extended to nested loops, using the PUSH and POP macros defined in the previous section:
MACRO LOOP PUSH . ENDMAC MACRO ENDLOOP POP LOOPTOP JUMP LOOPTOP ENDMACExpanding on this so that exits from loops work in the presence of nesting is more challenging. The fundamental problem is to make sure that the exit from each loop branches to the end of the correct loop, which is not necessarily the end of the nearest loop, as illustrated below:
{ = { > } }
| |__| |
|_____________|
The solution is to push not only the starting address, when a loop is entered,
but also the information needed to patch up the exit from any outer loop.
This is illustrated here:
MACRO LOOP
PUSH FIXUP
FIXUP = 0
PUSH .
ENDMAC
MACRO ENDLOOP
POP LOOPTOP
JUMP LOOPTOP
IF \(FIXUP = 0)
SAVELC = .
. = FIXUP
JUMP SAVELC
. = SAVELC
ENDIF
POP FIXUP
ENDMAC
MACRO EQUALS
ADDSI R2,-8
LOAD R4,R2,4
LOADS R3,R2
CMP R3,R4
BNE .+6
FIXUP = .
. = . + 4
ENDMAC
What about multiple exits from a loop? In this case, instead of a single
label, FIXUP, we need an open ended list of labels, one for each exit from
each loop. In effect, we need a linked list. We can build this using the
same mechanism we used for building the assembly time stack!
In one-pass compilers, assemblers and linkers, there is a common optimization: Instead of keeping the linked list of unresolved forward references in the heap, we can keep it in the code being assembled, compiled or linked:
Expensive and Obvious Better
Approach Approach
| | | |
_______ |_______| |_______|
|_X_|___|--->|_______| -->|___X___|
^ | | | | |
| | | | | |
_|_____ |_______| | |_______|
|___|___|--->|_______| ---|_______|<--
^ | | | | |
_|_____ |_______| |_______| |
|___|___|--->|_______| -->|_______|---
^ | | | | |
___|___ ___|___
|_fixup_| |_fixup_|