• Abstract machine language
• Separates front-end and back-end considerations
• Enhances modularity and portability
• Convenient for front-end to generate
• Convenient to translate to real machine code
• Simple, straightforward, fairly low-level

• Abstract code for a stack machine:
• Store operands on stack (LDC, LOAD, ...)
• Take operands form stack, process,
• Store result on stack (ADD, SUB, ...)
• Move to memory (Store, ...)

Trivial:

• ...
• void translate() {
• left.translate(); right.translate();
• switch(op) {
• case PLUS:
• emit0(Add); break;
• case MINUS:
• ...

(MULT, 2, a)

(SUB, b, 3)

• Need to add more IR operations:
• Function call/ret
• Conditional branch
• Unconditional branch
• May introduce others, e.g. switch statement
• Define code templates for high-level control structures

• CONST(i) 
• TEMP(t)
• MEM(a)
• BINOP(op, e1, e2)
• CALL(f, l) - call function f with arg list l
• ESEQ(s,e) - evaluate s (for side efects only), evaluate e and return as result

• MOVE(dst, src)
• JUMP(l)
• JUMP(e,label) - evaluate e, jump to label
• SEQ(s1, s2) - sequencing s1 followed by s2
• LABEL(n) - define label n at current position
• NAME(n) - label n
• CJUMP(op, e1, e2, t, f) - evaluate (e1 op e2), jump to correspoding label t or f

• Target architecture uses finite set of registers to hold operands
• Register-only operations much faster
• IR uses TEMPs:
• Assume infinitely many available
• Register allocation phase will map to actual registers
• Register spilling(i.e. move to memory) when not enough registers)
• Goal: store local variables and temporary values in registers where possible
• CAVEAT: some variables must be allocated in memory(excaping)

• Escaping: variables must be stored in memory if...
• They are passed by reference
• Their address is taken
• Using &operator in C
• Accessed by address arithmetic (e.g. arrays
• They are accessed from a nested function
• Spilling: Variables must be moved to memory if...
• Their register is required for a specific purpose
• Parameter passing
• Special operations (e.g. floating point arithmetics)
• There are not enough registers

• The variable needs to be stored in stack frame
• Needs to be addresed via frame pointer

• Static links are handled as normal variable in frame
• To be accessed you need to add k_sl(offset of static link in frame) to the frame pointer.

• Evaluate index: a[j]=a[ j + 1 ];
• Multiply by element size: a array of int
• Add base address: a[j]

• Complex control expressions are compiled into SEQuences of CJUMPs:

[image]

• Some aspects of translated tree complicate later stages of code generation process, e.g.
• ESEQ within expressions: order of evaluation of subtrees matters
• CJUMP has two destination labels, real machines' equivalent has only one
• ...so transform tree to eliminate awkward cases:
• remove ESEQs, move SEQs to top level
• Rearrange code so CJUMP always followed immediately by its false label

• Single-entry, single-exit, straight-line sequences:
• Always entered at begining and exited at end
• First statement is LABEL
• last statement is JUMP or CJUMP
• No other LABELs, JUMPs, or CJUMPs
• To partition program into basic blocks, scan sequentially:
• if LABEL found, start new block
• add JUMP at end of previous block if necessary
• if JUMP or CJUMP found, end block
• add LABEL at start of new block if necessary

• Basic blocks can be reordered without affecting results of execution
• All control flow is made explicit by jumps
• Group blocks into traces to maximize sequential execution sequences
• If block bi ends with JUMP to block bj, and bj not yet used, follow bi by bj
• If block bi ends with CJUMP to block bj or bk, follow with bk if possible, otherwise bj
• Followed by tidying-up phase to remove useless JUMP and CJUMP instructions