Branching
Compiler Implementation
COP-3402
Table of Contents
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?
int x = read_int();
if (x > 10) {
x = 11;
}
x += 1;
print_int(x);
function main localVariables x result x := call read_int if x <= 10 goto falselabel x := 11 falselabel: x := x + 1 result := call print_int x return 0 end function
Why is the condition inverted?
Won't need compile to SimpleIR but should understand how conditionals are translated to branch instructions.
Assembly translation:
.file "stdin"
.section .note.GNU-stack,"",@progbits
.text
.globl main
.type main, @function
main:
# prologue, update stack pointer
pushq %rbp # save old base ponter
movq %rsp, %rbp # set new base pointer
push %rbx # %rbx is callee-saved
# allocate stack space for locals
sub $24, %rsp
call read_int
add $0, %rsp
mov %rax, -16(%rbp)
# ifgoto x 10 to falselabel
mov -16(%rbp), %rax
mov $10, %rbx
cmp %rbx, %rax
jle falselabel
# assign 11 to x
mov $11, %rax
mov %rax, -16(%rbp)
falselabel:
# operation x 1 to x
mov -16(%rbp), %rax
mov $1, %rbx
add %rbx, %rax
mov %rax, -16(%rbp)
mov -16(%rbp), %rdi
call print_int
add $0, %rsp
mov %rax, -24(%rbp)
# set return value
mov $0, %rax
# epilogue
add $24, %rsp
pop %rbx # restore %rbx
pop %rbp # restore old base pointer
ret
Accessing variables
How we do access x's data?
if x <= 10 goto falselabel x := 11 falselabel: x := x + 1
Symbol table
localVariables x
| Variable | Offset |
|---|---|
| x | -16 |
| result | -24 |
mov -16(%rbp), %rax
Load from the stack frame, e.g., -16(%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 template:
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
Assembly translation
if x <= 10 goto falselabel
# getoperands
mov -16(%rbp), %rax
mov $10, %rbx
cmp %rbx, %rax
jle falselabel
x := 11
mov $11, %rax mov %rax, -16(%rbp)
falselabel:
# label falselabel:
x := x + 1
# x := x + 1 mov -16(%rbp), %rax mov $1, %rbx add %rbx, %rax mov %rax, -16(%rbp)
(Optional) C to SimpleIR
We won't be automatically compiling from C to SimpleIR in this class, but these are examples of hand translating them.