Branching
Compiler Implementation
COP-3402
Branching
Goal
Map SimpleIR branching operations
loop: goto loop
to assembly, e.g.,
loop: jmp loop
Labels
Named locations in the code.
labelname: mov $1, %rax
Where is code stored?
How are locations represented in the machine?
What address does the label correspond to at runtime?
Unconditional branching/jump
jmp loop
Addresses are relative to the instruction pointer
Absolute address can be specified with a value in a register
For our compiler, we'll only need to use labels
Assembler will compute relative offset for us
Conditional branching
How can we represent conditional statements in machine-like code?
if (x > 10) {
x = 11;
}
x += 1;
function main localvars x if x <= 10 goto falselabel x := 11 falselabel: x := x + 1 return x
Why is the condition inverted?
Won't need compile to SimpleIR but should understand how conditionals are translated to branch instructions.
Accessing variables
How we do access x's data?
if x <= 10 goto falselabel x := 11 falselabel: x := x + 1
Load from the stack frame, e.g., -16(%rbp)
# ifgoto x 10 to falselabel mov -8(%rbp), %rax mov $10, %rbx cmp %rbx, %rax jle falselabel # assign 11 to x mov $11, %rax mov %rax, -8(%rbp) falselabel: # operation x 1 to x mov -8(%rbp), %rax mov $1, %rbx add %rbx, %rax mov %rax, -8(%rbp)
Comparing operands
cmp %rbx, %rax
https://www.felixcloutier.com/x86/cmp
Where does the result go?
Sets the EFLAGS internal register https://en.wikibooks.org/wiki/X86_Assembly/X86_Architecture
x86's conditional jumps
ifgoto translation
SimpleIR
if x <= 10 goto falselabel
assembly (assuming %rbx and %rax already set)
cmp %rbx, %rax # %rbx is 10, %rax is x jle falselabel
Note: assembly operand order!
Just like subtraction, left operand is the second operand.
Other condition codes
| ASM Op | SimpleIR Op | Jump if… |
|---|---|---|
| je | = | Equal |
| jne | != | Not equal |
| jl | < | Less than |
| jle | <= | Less than or equal |
| jg | > | Greater than |
| jge | >= | Greater than or equal |
Pattern of conditional jumps
SimpleIR pattern
if OPERAND1 OPERATOR OPERAND2 goto LABEL
Convert operator to ASM jCC. Assembly code pattern
mov OPERAND1, %rax
mov OPERAND2, %rbx
cmp %rbx, %rax # %rbx is 10, %rax is x
jOP LABEL
Complete example
if x <= 10 goto falselabel x := 11 falselabel: x := x + 1
Complete example
if x <= 10 goto falselabel
# getoperands
mov -8(%rbp), %rax
mov $10, %rbx
cmp %rbx, %rax
jle falselabel
x := 11
mov $11, %rax mov %rax, -8(%rbp)
falselabel:
# label falselabel:
x := x + 1
# x := x + 1 mov -8(%rbp), %rax mov $1, %rbx add %rbx, %rax mov %rax, -8(%rbp)