CS 208 s21 — x86-64 Control Flow: Conditionals

Table of Contents

1 Video

Link to the Panopto viewer: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=6b4e515f-00fd-41aa-8dad-ac4701309e8b

2 Condition Codes

  • condition codes are the basis for control flow within a program (i.e., determining which instruction gets executed next)
    • special %rip register stores instruction pointer
  • most useful codes:
    • CF: carry flag. Set when an operation generated a carry out of the most significant bit. Used to detect unsigned overflow
    • ZF: zero flag. Set when an operation yields 0
    • SF: sign flag. Set when an operation yields a negative value
    • OF: overflow flag. Set when an operation causes a two's complement overflow, negative or positive
  • all the standard arithmetic instructions set these flags except for leaq
  • cmp and test instructions set condition codes
    • cmp subtracts first operand from second
    • test ands operands (usually the same quantity is both operands, check if its zero, positive, negative)

2.1 Accessing the Condition Codes

  • class of set instructions to set a single byte to 1 or 0 based on one or more condition codes (figure 3.14, p. 203)
    • in the case where cmp b, a was executed
    • when \(a=b\), then \(a-b=0\), so ZF will be set
    • when \(a < b\), then \(a - b < 0\) (SF set) or \(a - b\) overflows so the result is positive and OF is set
      • but both SF and OF set would indicate \(a\) is positive and \(b\) is negative such that \(a-b\) would overflow to a negative value
      • hence, less than is detected when SF ^ OF
    • for unsigned \(a < b\), \(a - b\) would cause a carry out of the most significant bit, setting CF

2.2 Example

2.2.1 Translate conditional C code to assembly

int gt(long x, long y) {
    return x > y;
}
Register Use
%rdi 1st argument (x)
%rsi 2nd argument (y)
%rax return value 
gt:
  cmpq   %rsi, %rdi  // perform x - y, set condition codes
  setg   %al         // if the condition codes indicate x > y, write 1 to %al
  movzbl %al, %eax   // copy %al to %eax, using 0s to extend the 1 byte %al to the 4 bytes of %eax
  ret

2.2.2 movz and movs

  • when moving data from a smaller source to a larger destination, can specify zero extension or sign extension
    • destination must be a register
  • movzSD / movsSD
    • S is the size of the source (b or w)
    • D is the size of the destination (w, l, or q)

movz-example.png

3 Jump Instructions

  • class of jump instructions move program execution to specified instruction (figure 3.15, p. 206)
  • direct jumps encode the jump target in the instruction
  • indirect jumps read the jump target from register or memory
    • written with a * preceding the operand
  • conditional jumps (can only be direct) jump or continue the subsequent instruction based on some combination of condition codes
Instruction     (op) s, d test a, b cmp a, b
jmp   Unconditional      
je sete "Equal" d (op) s == 0 b & a == 0 b == a
jne setne "Not equal" d (op) s != 0 b & a != 0 b != a
js sets "Sign" (negative) d (op) s < 0 b & a < 0 b - a < 0
jns setns (non-negative) d (op) s >= 0 b & a >= 0 b - a >= 0
jg setg "Greater" d (op) s > 0 b & a > 0 b > a
jge setge "Greater or equal" d (op) s >= 0 b & a >= 0 b >= a
jl setl "Less" d (op) s < 0 b & a < 0 b < a
jle setle "Less or equal" d (op) s <= 0 b & a <= 0 b <= a
ja seta "Above" (unsigned >) d (op) s > 0U b & a > 0U b - a > 0U
jb setb "Below" (unsigned <) d (op) s < 0U b & a < 0U b - a < 0U

jumps.png

3.1 Implementing Conditional Branches with Conditional Control

if (<text-expr>)
    <then-statement>
else
    <else-statement>

becomes 

    t = <test-expr>;
    if (!t)
        goto false;
    <then-statement>
    goto done;
false:o
    <else-statement>
done:

3.1.1 Example

long absdiff(long x, long y) {
    long result;
    if (x > y)
        result = x - y;
    else
        result = y - x;
    return result;
}
Register Use
%rdi 1st argument (x)
%rsi 2nd argument (y)
%rax return value 
absdiff:
        cmpq %rsi, %rdi   // perform x - y
        jle .L4           // if condition codes indicate x <= y, jump to L4
                          // x > y:
        movq %rdi, %rax
        subq %rsi, %rax
        ret
    .L4:                  // x <= y:
        movq %rsi, %rax
        subq %rdi, %rax
        ret

3.2 (OPTIONAL) Implementing Conditional Branches with Conditional Moves

  • Reading: CSPP section 3.6.6
  • class of cmov instructions copy source operand to destination register when the condition holds
    • same conditions as set and jump instructions
  • can be more efficient than conditional jumps because the sequence of intructions is predictable
    • memory may or may not be moved, but the subsequent instruction is executed regardless
    • processors pipeline instructions, meaning they process them in a series of stages (fetching instruction from memory, determining instruction type, reading from memory, performing arithmetic operation, writing to memory, updating program counter)
    • significant performance benefits from overlapping different stages of sequential instructions
    • pipelining in the presence of conditional jumps requires sophisticated branch prediction (modern processors aim for 90% accuracy)
  • turn on optimization for previous exercise (-O1 compiler flag) to see an example