loadI 3 => r1
CS 432
loadI 4 => r2
mult r1, r2 => r3
loadI 2 => r4
add r3, r4 => r5
Fall 2018 print r5
Mike Lam, Professor
Code Generation
Compilers
"Back end"
Source code Tokens Syntax tree Machine code
char data[20];
7f 45 4c 46 01
int main() { 01 01 00 00 00
float x 00 00 00 00 00
= 42.0; ...
return 7;
}
Lexing Parsing Code Generation
& Optimization
Current
"Front end" focus
Our Project
●
Current status: type-checked AST
●
Next step: convert to ILOC
– This step is called code generation
– Convert from a tree-based IR to a linear IR
●
Or directly to machine code (uncommon)
●
Use a tree traversal to “linearize” the program
7f 45 4c 46 01
01 01 00 00 00
00 00 00 00 00
...
Goals
●
Linear codes
– Stack code (push a, push b, multiply, pop c)
– Three-address code (c = a + b)
– Machine code (movq )
a, %eax; addq b, %eax; movq %eax, c
●
Code generator requirements
– Must preserve semantics
– Should produce efficient code
– Should run efficiently
Obstacles
●
Generating the most optimal code is undecidable
– Unlike front-end transformations
●
(e.g., lexing & parsing)
– Must use heuristics and approximation algorithms
– This is why most compilers research since 1960s has
been on the back end
ILOC
●
Linear IR based on research compiler from Rice
●
See Appendix A (and ILOCInstruction / ILOCInterpreter)
●
I have made some modifications to simplify P5
– Removed most immediate instructions (i.e., subI)
– Removed binary shift instructions
– Removed character-based instructions
– Removed jump tables
– Removed comparison-based conditional jumps
– Added labels and function call mechanisms (call, param, return)
– Added binary not and arithmetic neg
– Added print and nop instructions
ILOC
●
Simple von Neumann architecture
– Not an actual hardware architecture, but useful for teaching
– 32-bit words w/ 64K address space
– Read-only code region indexed by instruction
– Unlimited 32-bit integer virtual registers (r1, r2, …)
– Four special-purpose registers:
●
IP: instruction pointer 0xFFFF
Stack
●
SP: stack pointer
●
BP: base pointer
●
RET: return value
Data
0x0
Code
ILOC
ILOC
Syntax-Directed Translation
●
Similar to attribute grammars (Figure 4.15)
●
Create code-gen routine for each production
– Each routine generates code based on a template
– Save intermediate results in temporary registers
●
In our project, we will use a visitor
– Still syntax-based (actually AST-based)
– Not dependent on original grammar
– Generate code as a synthesized attribute (“code”)
– Save temporary registers as another attribute (“reg”)
ILOC
●
Sample code: Decaf equivalent:
print_int(2+3*4);
loadI 3 => r1 // ASTLiteral (3)
loadI 4 => r2 // ASTLiteral (4)
mult r1, r2 => r3 // ASTBinOp (*)
loadI 2 => r4 // ASTLiteral (2)
add r3, r4 => r5 // ASTBinOp (+)
print r5 // ASTVoidFuncCall (print_str)
ILOC
●
Sample code: Decaf equivalent:
print_int(2+3*4);
loadI 3 => r1 // ASTLiteral (3)
loadI 4 => r2 // ASTLiteral (4)
mult r1, r2 => r3 // ASTBinOp (*)
loadI 2 => r4 // ASTLiteral (2)
add r3, r4 => r5 // ASTBinOp (+)
print r5 // ASTVoidFuncCall (print_str)
ILOC
●
Sample code:
Decaf equivalent:
loadI 5 => r1
loadI 8 => r2
add r1, r2 => r3
loadI 10 => r4 if (5 + 8 < 10) {
cmp_LT r3, r4 => r5 print_str(“yes”);
cbr r5 => l1, l2 } else {
print_str(“no”);
l1: }
print “yes”
jmp l3
l2:
print “no”
l3:
Boolean Encoding
●
Integers: 0 for false, 1 for true
●
Difference from book
– No comparison-based conditional branches
– Conditional branching uses boolean values instead
– This enables simpler code generation
●
Short-circuiting
– Not in Decaf!
String Handling
●
Arrays of chars vs. encapsulated type
– Former is faster, latter is easier/safer
– C uses the former, Java uses the latter
●
Mutable vs. immutable
– Former is more intuitive, latter is (sometimes) faster
– C uses the former, Java uses the latter
●
Decaf: immutable string constants only
– No string variables
Array Accesses
●
1-dimensional case: base + width * i
●
Generalization for multiple dimensions:
– base + (i_1 * w_1) + (i_2 * w_2) + ... + (i_k * w_k)
●
Alternate definition:
– 1d: base + width * (i_1)
– 2d: base + width * (i_1 * n_2 + i_2)
– nd: base + width * (( ... ((i_1 * n_2 + i_2) * n_3 + i_3) ... ) * n_k + i_k) * width
●
Row-major vs. column-major
●
In Decaf: row-major one-dimensional global arrays
Struct and Record Types
●
How to access member values?
– Static offsets from base of struct/record
●
OO adds another level of complexity
– Now classes have methods
– Class instance records and virtual method tables
●
In Decaf: no structs or classes
Control Flow
●
Introduce labels
– Named locations in the program
– Generated sequentially using static newlabel() call
●
Generate jumps/branches using templates
– In ILOC: “cbr” instruction (no fallthrough!)
– Templates are composable
Control Flow
if statement: if (E) B1
rE = << E code >>
cbr rE → b1, skip
b1:
<< B1 code >>
skip:
Control Flow
if statement: if (E) B1 else B2
rE = << E code >>
cbr rE → b1, b2
b1:
<< B1 code >>
jmp done
b2:
<< B2 code >>
done:
Control Flow
while loop: while (E) B
Control Flow
while loop: while (E) B
cond:
rE = << E code >>
cbr rE → body, done
body:
<< B code >>
jmp cond
done:
Control Flow
while loop: while (E) B
cond: ; CONTINUE target
rE = << E code >>
cbr rE → body, done
body:
<< B code >>
jmp cond
done: ; BREAK target
Control Flow
for loop: for V in E1, E2 B
NOT CURRENTLY
rX = << E1 code >> IN DECAF
rY = << E2 code >>
rV = rX
cond:
cmp_GE rV, rY → rC
cbr rC → done, body
body:
<< B code >>
rV = rV + 1 ; CONTINUE target
jmp cond
done: ; BREAK target
SSA Form
●
Static single-assignment
– Unique name for each newly-calculated value
– Values are collapsed at control flow points using Φ-functions
●
(not actual executed!)
– Useful for various types of analysis
– We’ll generate ILOC in SSA for P5
cmp_LT r1, r2 → r3
cbr r3 → l1, l2
if (a < b) {
c = 4; l1: l2:
} else { loadI 4 → r4 loadI 8 → r5
c = 8; jmp l3 jmp l3
}
l3:
r6 = Φ(r4, r5)
Procedure Calls
●
These are harder
– We'll talk about them next week