Assembly 3: Branching

Overview

We discuss branching and save/restore calling conventions in machine code.

Full lecture notes on assembly — Textbook readings

State in programming languages

• An unbounded number of variables of arbitrary type
• Dynamic allocation
• Good access control
  • Local variables in one function cannot be accessed from others
  • A local variable in a block isn’t accessible outside that block

State in CPUs

• A small number of named registers of limited type
  • Computation acts on registers
• A large primary memory accessed by numeric address
  • Stores data that doesn’t fit in registers, and data displaced by newer computations
  • Explicit save & restore often required
• Limited access control
  • Instructions have undifferentiated access to memory and registers

Function entry and exit sequence

• Call sequence: Steps required before calling a function
  • Set up arguments
• Entry sequence: Steps required to enter a function
  • Prepare environment for callee function
• Exit sequence: Steps required to exit a function
  • Set up return value
  • Restore environment for caller function
• Return sequence: Steps required after function returns
  • Clean up any argument space

Call and return instructions

• Action of call FUNCTION instruction

  subq $8, %rsp
  movq %NEXT_rip, (%rsp)
  movq FUNCTION, %rip
  # now runs FUNCTION’s entry sequence
  

• Action of ret instruction

  addq $8, %rsp
  movq -8(%rsp), %rip
  # now runs caller’s return sequence
  

Stacks and function-local storage

• Stacks grow down: callee storage (inner function) has lower addresses
• The return address, which is stored automatically by callq, marks the boundary between callee storage and caller storage
• Natural storage for local temporaries
  • Finite register set; often need to save intermediate values

Calling convention and save/restore

• A function must restore certain registers to their entry-time values before returning
  • Example: %rsp, %rip—but more too
• Caller-saved registers
  • If the caller (the “outer”, or calling, function) cares about the value, it must save that value and restore it after the callee returns
  • Most registers
• Callee-saved registers
  • If the callee (the “inner”, or called, function) uses the value, it must save that value first and restore it before returning
  • %rbx, %r12–%r15, %rbp

Saving data on the stack

• Save: subq $8, %rsp; movq REG, (%rsp)
  • pushq REG
• Restore: movq (%rsp), REG; addq $8, %rsp
  • popq REG

Typical (not universal) entry and exit sequence

• Entry sequence: Save entry %rbp, set %rbp to the initial stack pointer, sometimes save other callee-saved registers
  • Local variables are negative offsets from %rbp, 7th and subsequent arguments are positive offsets from %rbp
  • Allows compiler to modify %rsp within function without losing track of local variable locations
  • Allows debugger to trace backwards up the stack

  endbr64
  pushq %rbp
  movq %rsp, %rbp
  

• Exit sequence: After computing return value, restore callee-saved registers and entry %rsp, then return

  leaveq    # means `movq %rbp, %rsp; popq %rbp`
  ret
  

• Compiler optimizations can streamline these sequences

cc04.cc

cc05.cc

Local variables

• Local variables are stored in the stack
• Function entry sequence reserves enough space for locals
• Local variables may be stored in the unreserved red zone
  • 128 bytes below %rsp
  • Does not need explicit reservation
  • Generally seen in leaf functions (functions that do not call other functions)

Control flow in programming languages

• Sequential execution by default (statements run one after the next)
• Structured control flow: if, while, for
• Unstructured control flow: goto (but that’s “BAD”)
• Functions
  • Control flow (call, return) plus state (parameters, return value)
• Complex control flow (e.g. exceptions)

Control flow in CPUs

• Sequential execution by default
• Only unstructured control flow
  • Unconditional branch: go to a specific instruction
  • Conditional branch: go to a specific instruction if a condition holds
• Functions
  • CPU defines control flow (call, return)
  • Calling convention defines state (argument registers, return value register)
• Communication with operating systems (next unit)

Unconditional jumps in assembly

• j/jmp ADDR
  • j ADDR
  • j *%reg: Jump to address stored in %reg
  • j *ADDR: Jump to address stored in ADDR
  • In compiler-generated assembly: j LABEL

Conditional jumps in assembly

• je ADDR: Jump to ADDR if equal
  • Continue to next instruction if not equal
• If equal to what????

Condition flags

• Arithmetic operations not only produce results, they also change a special-purpose register called the flags register %rflags/%eflags
  • Comprising many boolean flags
• Conditional jumps read flags from this register
• Data movement instructions leave flags unchanged

Flag-only instructions

• Commonly find cmp and test instructions near conditional branches
• These instructions perform arithmetic, but ignore the result except they set flags
• cmp SRC1, SRC2: Set flags based on SRC2 - SRC1
• test SRC1, SRC2: Set flags based on SRC2 & SRC1

ZF

• ZF is the zero flag
  • Set iff result of computation is zero
• jz: Jump if ZF (ZF==1)
• jnz: Jump if !ZF (ZF==0)
• je: Jump if ZF
• jne: Jump if !ZF

ZF example

• Desired: Jump to .L2 if %rax == %rcx

cmp %rcx, %rax
jz .L2

Other flags

• SF: Set iff result is negative when considered as signed
• CF: Set iff computation overflowed when considered as unsigned
• OF: Set iff computation overflowed when considered as signed

Why two overflow flags (CF and OF)?

• Consider 0xFFFF'FFFF'FFFF'FFFF + 0x1
• The result is 0
• This overflows when considered as unsigned
  • (2^{64} - 1) + 1 = 2^{64} can’t be represented in a 64-bit unsigned number
• This does not overflow when considered as signed
  • (-1) + 1 = 0 can be represented in a 64-bit signed number

Comparison conditional jumps

• Usually associated with cmp
• ja (jnbe): Jump if greater, unsigned
  • !ZF && !CF
• jg (jnle): Jump if greater, signed
  • !ZF && (SF == OF)

How to read a comparison

• jCONDITION: Jump if previous computation CONDITION zero
  • je: Jump if previous computation equaled zero
  • ja: Jump if previous computation is greater than zero, unsigned
  • jg: Jump if previous computation is greater than zero, signed
• Arithmetic transformations help it make sense
  • cmp %edi, %esi; jg .L2
  • jg means “jump if previous computation > 0, signed”
  • ⟶ “jump if %esi - %edi > 0, signed”
  • ⟶ “jump if %esi > %edi, signed”

Yet more

• jae, jge, jb, jl, jbe, jle
• js, jns, jo, jno, jc, jnc

Conditional move instructions

• cmovCONDITION SRC, DST
  • Example: cmovz SRC, DST, cmovl SRC, DST
  • Perform move only if condition holds
  • Shorthand for jnCONDITION 1f; mov SRC, DST; 1:

f19.s–f31.s