Code Generation Rules

University of Toronto

CSC467F Compilers and Interpreters

Fall 2005

Code Generation Rules

The following is a list of code generation actions you will need to perform for the project. They are referenced R0-R49. No other code generation actions should be necessary.

Data Structures used by Code Generation Rules

Forward Branch Stacks (FBS)
- Stacks used to record the location of forward branches that need to be fixed up; since we are using the ELSEIF construct it may be more convenient to use more than one (i.e. one for condition FALSE goto next ELSEIF and one for condition TRUE statements executed exit entire IF statement). Used by: R8, R13, R14, R23, R24.
Backward Branch Stack (BBS)
- A stack used to record locations for future use in backward branches. Used by: R11, R15.
Loop Exit Stack (LES)
- Used to record the locations of exit branches (break statements) in a loop. Used by: R11, R12, R15.
Other control structures
- Depending on how the code generation for e.g. function/procedure bodies is implemented, other stack structures may be needed.

Code Generation Rules

Programs and Scopes

R0:	Start of the program	Set `pc` and `mt` to values for starting execution. Initialize display registers.
R1:	Start of scope (global, procedure/function)	Check that lexical level less than `displaySize`. Emit instructions to enter statement scope.
R3:	End of declarations	Emit instructions to allocate variables (if required) and prepare scope for execution.
R4:	Before returning from a function	Emit instructions to obtain address for result.
R5:	End of scope	Emit instructions to free variables and prepare to exit statement scope.
R7:	Last statement in program	Emit Halt.

If and Loop Constructs

R8:	Conditional in IF and WHILE	Emit forward branch to next ELSEIF, ELSE, or outside of block on false. Record address of instruction in FBS.
R11:	Before body of WHILE loop	Push current location onto BBS. Push LES.
R12:	BREAK statement	Emit forward branch for exit. Record instruction address in LES.
R13:	After entire IF statement, body of WHILE loop	Fix-up address of forward branches identified by top entry of appropriate FBS to current location. Pop FBS.
R14:	After THEN, before ELSEIF/ELSE part of IF statement	Emit forward unconditional branch `B`. Fix-up address of forward branch identified by top entry of appropriate FBS to location immediately after `B` and pop current FBS. Record address of `B` in FBS.
R15:	After body of WHILE loop	Emit unconditional branch to address on top of BBS. Pop BBS. Fixup branches described by top entry in LES to current location. Pop LES.

Scalars and Arrays

R16:	Need address of variable, e.g., during assignment	Emit instructions to obtain address of variable. Note that even variables in current scope need to be accessed via data frames.
R17:	Need value of variable, e.g., during call-by-value	Emit instructions to obtain value of variable.
R18:	Storage (e.g., assignment)	Emit STORE.
R19:	Scalar variable/constant declaration	Emit instructions to allocate storage for a scalar variable. If necessary, emit instructions for initialization of variable.
R20:	Array variable declaration	Emit instructions to allocate storage for an array variable.
R21:	Beginning of subscript computation	Emit instructions to obtain address of an array variable.
R22:	End of subscript computation	Emit instructions to create address of array element. Note that the first element in the array is element 1 (not 0).

Functions, procedures and arguments.

R23:	Before body of functions and procedures	Emit forward unconditional branch. Record address of instruction in FBS.
R24:	End of function/procedure body	Emit instructions to return from a function or procedure. Fix-up address of forward branch identified by top entry of FBS to current location. Pop FBS.
R25:	Function/procedure call	Emit instructions to call a subroutine. This includes building data frame to hold parameters and return address prior to call, unconditional branch to address of subroutine, and deallocation with possible assignment of return value after the call.
R26:	Start of list of actual parameters to a function/procedure	Emit instructions to generate block mark for procedure call. Note that this requires prior calculation of size of data frame.
R27:	Actual parameter to function/procedure	Emit instructions to save argument for call. Note that expressions are passed by value by assignment to the data frame, while var and array parameters are addresses.

Expressions, Input & Output

R28:	Integer constant	Emit PUSH integer value.
R29:	Boolean value `false`	Emit PUSH 0.
R30:	Boolean value `true`	Emit PUSH 1.
R31:	UNARY MINUS operator	Emit instructions appropriate to operator.
R49:	NOT operator	" " "
R32:	PLUS operator	" " "
R33:	MINUS operator	" " "
R34:	MULTIPLY operator	" " "
R35:	DIVIDE operator	" " "
R36:	EXPONENT operator	" " "
R37:	AND operator	" " "
R38:	OR operator	" " "
R39:	EQUAL operator	" " "
R40:	NOT EQUAL operator	" " "
R41:	LESS THAN operator	" " "
R42:	LESS THAN OR EQUAL TO operator	" " "
R43:	GREATER THAN operator	" " "
R44:	GREATER THAN OR EQUAL TO operator	" " "
R45:	GET integer	Emit instructions to read and store integer.
R46:	PUT integer	Emit instructions to print integer.
R47:	PUT string constant	Emit instructions to print text.
R48:	NEWLINE statement	Emit instructions to output a newline.

Note: Depending on the implementation decisions that you make, some of these code generation actions may be no-ops.

Frank Van Bussel

Last modified November, 2005