Code Generation

Topics

• Interpretation: syntax-directed and based on abstract syntax tree.
• Code generation: syntax-directed and based on abstract syntax tree.

The Postfix Machine

SL0 - single stack, large stack, 0 operand machine.

Three special purpose registers: IP (instruction pointer), for jumps and function calls; FP (frame pointer), the basis of the frame pointer for each function; SP (stack pointer), keeps track of the top of the stack.

The stack grows in the direction of lower addresses.

Almost all operations use the stack as input and output (exceptions are PUSH and POP, for returning values from functions in accordance with CDecl), and instructions that use either immediate arguments or arguments in global memory (i.e., with explicit named addressing).

Basic Structures (code)

The mnemonics are those of the Postfix language. Comments indicate missing parts.

Cycles

Basic structure of a "while" cycle:

<asm> LABEL "condition"

evaluate condition expression

JZ "endwhile"

evaluate block

JMP "condition" LABEL "endwhile" </asm>

Basic structure of a C-style "for" cycle:

<asm>

evaluate initializer

LABEL "condition"

evaluate condition expression

JZ "endfor"

evaluate block

LABEL "increment"

evaluate increment expression

JMP "condition" LABEL "endfor" </asm>

"Break" and "Continue" Instructions

The C-style "break" and "continue" instructions must jump, respectively, to the end of the cycle or to its condition (for deciding on whether to execute the next iteration). In the case of "for" cycles, the jump to the condition is not direct, but rather via a jump to the increment label.

If there are multiple nested cycles, the code generator must keep track of the innermost one, so that it can generate the appropriate jumps. This may be achieved through the use of address stacks (one for the condition labels and another for increment labels).

If-Then and If-Then-Else Instructions

Basic structure of an "if-then" instruction:

<text> (evaluate condition expression) JZ "endif" (evaluate then block) LABEL "endif" </text>

Basic structure of an "if-then-else" instruction:

<text> (evaluate condition expression) JZ "else" (evaluate then block) JMP "endif" LABEL "else" (evaluate else block) LABEL "endif" </text>

Basic Structures (data)

Global (permanent) variables

We include in this category C-like "static" function variables (the only difference is that they are not accessed with their explicit names, but rather with a automatic symbol table-based name).