Course Homepage

Branching

Branching

Goal

Map Slang 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);
begin main()
locals x, result
x = read_int()
if x <= 10 goto falselabel
x = 11
falselabel:
x = x + 1
result = print_int(x)
return 0
end function

Why is the condition inverted?

Won’t need compile to Slang 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

locals x, result
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.html/wiki/X86_Assembly/X86_Architecture

x86’s conditional jumps

jle jump if result of comparison is less than or equal to

jle falselabel

https://www.felixcloutier.com/x86/jcc

ifgoto translation

Slang

if x <= 10 goto falselabel

Assembly (assuming %rbx and %rax already set)

cmp %rbx, %rax  # %rbx is 10, %rax is x
jle falselabel      # jump if rax <= rbx

Note assembly operand order!

Just like subtraction, left operand is the second operand.

Other condition codes

ASM Op Slang 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

Slang 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

# Get operands
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 Slang

We won’t be automatically compiling from C to Slang in this class, but these are examples of hand translating them.

If-then-else

While loops

Control-flow graphs