2025-02-Compiler/notes/7.md

Code Generation 2

Stack Machine

Consider two instructions

• push i
• add i

It is not efficient because all stack is considered as memory (which is slower than register).

Utilizing Register Files

Keep the top of the stack in a register, so add requires only a single memory access.

• acc <- i
• push acc
• pop
• add

Code Generation From Stack Machine

Assume that stack grows towards lower addresses.

MIPS

32 regs

$sp, $a0, $t1

• lw
• add
• sw
• addi
• li
• mv

Converting Stack to MIPS ISA

• acc <- i
  • li $a0 i

Optimizing

no

Branch

beq $1 $2 lbl b lbl

Function

At Caller Side:

1. saves the $fp to the stack
2. saves the actual params in reverse order
3. saves the return address to $ra

At Callee Side:

1. set $fp to $sp
2. the callee saves the return address
3. ...

Temp Var

Many various intermediate vars should be stored in the AR. But compiler can statically know how many temporary variables there are.

Let NT(e) is defined recursively by:

NT(e1 + e2) = \max (NT(e1), NT(e2) + 1)

for example:

CG using NT

add new args to the cgen(e, nt)

reduce number of decrease $sp (addi $sp $sp -4)

Intermediate Representation (IR)

Before: Each Languages need respective, different Optimizer.

Now: Common IR optimizer.

IR is language-independent and machine-independent optimization.

High-Level Assembly

It uses unlimited number of registers. It uses assembly-like control structures (jmp and lbl). opcodes but some are higher level

igen(e, t)