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 localVariables x if x <= 10 goto falselabel x := 11 falselabel: x := x + 1 return x end function
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)