CS 208 s20 — x86-64 Control Flow: Conditionals

Table of Contents

1 Review

What effect do these instructions 

:
    leaq (%rdx,%rcx,4), %rax
    movq (%rdx,%rcx,4), %rbx
    leaq (%rdx), %rdi
    movq (%rdx), %rsi

have on register values give the initial state below?1

topic-10-review-initial.png

2 Video Lecture

Watch the video lecture for the material outlined below: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=4d3e29a2-ea32-48a8-a852-abaa00fe7865.

3 Condition Codes

  • 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)

3.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

3.2 Exercises

3.2.1 Which condition codes indicate \(a > b\)?

  • not less than and not equal
  • ~(SF ^ OF) and ~ZF
  • ~(SF ^ OF) & ~ZF

3.2.2 Translate this 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
  setg   %al
  movzbl %al, %eax
  ret

3.2.3 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

4 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

4.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:
    <else-statement>
done:

4.1.1 Exercises

Register Use
%rdi 1st argument (x)
%rsi 2nd argument (y)
%rax return value

Exercise 1: 

long absdiff(long x, long y) {
    long result;
    if (x > y)
        result = x-y;
    else
        result = y-x;
    return result;
}

Which pair of instructions should go on the two blank lines? 

absdiff:
        __________________
        __________________
                          # x > y:
        movq %rdi, %rax
        subq %rsi, %rax
        ret
    .L4:                  # x <= y:
        movq %rsi, %rax
        subq %rdi, %rax
        ret

cmpq %rsi, %rdi
jle .L4

Exercise 2: compile this code to assembly 

long wacky(long x, long y) {
    long result;
    if (x + y > 7) {
        result = x;
    } else {
        result = y + 2;
    }
    return result;
}

wacky:
  movq %rdi, %rax
  leaq (%rdi,%rsi), %rdx
  cmpq $7, %rdx
  jg .L2
  leaq 2(%rsi), %rax
.L2:
  rep ret

4.2 Jump Instruction Encodings

  • jump target encoded compactly with PC relative representation
    • specify offset to the address of the immediately following instruction
  • compile to binary and disassemble previous exercise (11010 checkbox on godbolt) for an example

4.3 (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

5 Homework

  1. CSPP practice problems 3.16 (p. 212) and 3.18 (p. 213)
  2. Both the Week 3 quiz and lab 1 are due 9pm Wednesday (April 29)

Footnotes:

1

topic-10-review-answers.png