---

How control flow is mathematically mapped to hardware?

---

1. The Human Desire vs. The Physical Axiom

• The Desire: Conditional branching.

  • $\text{If condition } P \text{ is true, execute block } A\text{; otherwise, execute block } B.$

• The Physical Axiom (Axiom 4 — Monotonic Execution):

  • The Program Counter (%rip) naturally increments monotonically from one instruction to the next:

  $\%rip \leftarrow \%rip + \text{sizeof}(\text{current\_instruction})$

The CPU cannot "choose" a block of code directly.
It can only do one of two things:
1) Continue to the next sequential address.
2) Overwrite %rip with a target address (a Jump).

---

2. The Bridge: Condition Codes ($\mathcal{C}$)

To decide whether to jump, the CPU maintains a special 1-bit register collection called Condition Codes (or the EFLAGS register):

$\mathcal{C} = \langle \text{CF}, \text{ZF}, \text{SF}, \text{OF} \rangle$

Whenever the ALU executes an operation (like sub, add, cmp),
these 1-bit flags are updated automatically as side effects:

Flag	Name	Mathematical Definition	Hardware Meaning
ZF	Zero Flag	$\text{Result} == 0$	The operation produced a zero (e.g., $a - b = 0$, so $a == b$).
SF	Sign Flag	$\text{Result} < 0$	The most significant bit (MSB) of the result is 1 (negative).
OF	Overflow Flag	$(a > 0, b > 0, \text{Res} < 0) \lor (a < 0, b < 0, \text{Res} > 0)$	Two's-complement signed overflow occurred.
CF	Carry Flag	$\text{Unsigned Overflow}$	An unsigned addition carried out of the MSB, or a borrow occurred.

Crucial Rule: leaq does not alter condition codes. Pure arithmetic (addq, subq, cmpq, testq) does.

---

3. The 3-Step Machine Recipe for Any if or Loop

Every conditional construct in C is compiled into this exact 3-step sequence:

[Step 1: Set Flags]   ───>   cmpq %rsi, %rdi      (Compute %rdi - %rsi, discard result, set flags)
[Step 2: Read Flags]  ───>   jg   .L_greater      (Jump if ZF=0 and SF=OF)
[Step 3: Fallthrough] ───>   ...                  (Code executed if false)

---

test3_6.c

long max(long a, long b) {
    if (a > b) return a;
    else return b;
}

compiled -O0

cat test3_6.s

        .file   "test3_6.c"
        .text
        .globl  max
        .type   max, @function
max:
.LFB0:
        .cfi_startproc
        endbr64
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        movq    %rdi, -8(%rbp)
        movq    %rsi, -16(%rbp)
        movq    -8(%rbp), %rax
        cmpq    -16(%rbp), %rax
        jle     .L2
        movq    -8(%rbp), %rax
        jmp     .L3
.L2:
        movq    -16(%rbp), %rax
.L3:
        popq    %rbp
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE0:
        .size   max, .-max
        .ident  "GCC: (Ubuntu 13.3.0-ubuntu2~24.04.1) 13.3.0"
        .section        .note.GNU-tack,"",@progbits
        .section        .note.gnu.property,"a"
        .align 8
        .long   1f - 0f
        .long   4f - 1f
        .long   5
0:
        .string "GNU"
1:
        .align 8
        .long   0xc0000002
        .long   3f - 2f
2:
        .long   0x3
3:
        .align 8
4: 

				  +-----------------------------------+
                  |           Function Entry          |
                  |  pushq   %rbp                     |
                  |  movq    %rsp, %rbp               |
                  |  movq    %rdi, -8(%rbp)   (save a)|
                  |  movq    %rsi, -16(%rbp)  (save b)|
                  +-----------------------------------+
                                    |
                                    v
                  +-----------------------------------+
                  |             Condition             |
                  |  movq    -8(%rbp), %rax   (%rax=a)|
                  |  cmpq    -16(%rbp), %rax  (a - b) |
                  +-----------------------------------+
                                    |
                            jle .L2 (a <= b)
                           /                 \
                 [ True ] /                   \ [ False ]
                         /                     \
                        v                       v
      +----------------------------+  +----------------------------+
      |      .L2 (Else Block)      |  |      Then-Fallthrough      |
      |  movq  -16(%rbp), %rax     |  |  movq  -8(%rbp), %rax      |
      |        (%rax = b)          |  |        (%rax = a)          |
      +----------------------------+  |  jmp   .L3                 |
                    |                 +----------------------------+
                    \                               /
                     \                             /
                      ----->        .L3       <----
                                     |
                                     v
                  +-----------------------------------+
                  |             Function Exit         |
                  |  popq    %rbp                     |
                  |  ret                              |
                  +-----------------------------------+

Step-by-Step Flow

                  [Input Registers] ──────────> [%rdi = a]   [%rsi = b]
                                   │            │
                                   ▼            ▼
[Stack Memory Frame] ───────> [-8(%rbp)]   [-16(%rbp)]
                                   │            │
                                   ▼            ▼
[ALU Operation] ────────────> cmpq calculates: (%rax - %rsi) = (a - b)
                                   │
                                   ▼
[Flags Register EFLAGS] ────> Updates ZF, SF, OF, CF
                                   │
                                   ▼
[Decision Point] ───────────> Does a <= b hold? ((SF ^ OF) | ZF == 1)
                              ├── YES ──> Jump to .L2 ──> Load b into %rax
                              └── NO  ──> Fallthrough ──> Load a into %rax ──> Jump to .L3

---

compiled -O2

cat test3_6_opt.s 
        .file   "test3_6.c"
        .text
        .p2align 4
        .globl  max
        .type   max, @function
max:
.LFB0:
        .cfi_startproc
        endbr64
        cmpq    %rsi, %rdi
        movq    %rsi, %rax
        cmovge  %rdi, %rax
        ret
        .cfi_endproc
.LFE0:
        .size   max, .-max
        .ident  "GCC: (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0"
        .section        .note.GNU-stack,"",@progbits
        .section        .note.gnu.property,"a"
        .align 8
        .long   1f - 0f
        .long   4f - 1f
        .long   5
0:
        .string "GNU"
1:
        .align 8
        .long   0xc0000002
        .long   3f - 2f
2:
        .long   0x3
3:
        .align 8
4:

			   +----------------------------------------+
               |              Function Entry            |
               |  (No stack setup, no memory writes)    |
               |  Arguments already in registers:       |
               |      %rdi = a,  %rsi = b               |
               +----------------------------------------+
                                   |
                                   v  [Monotonic Flow: %rip advances]
               +----------------------------------------+
               |             1. Comparison              |
               |  cmpq   %rsi, %rdi                     |
               |  Computes: (%rdi - %rsi) = (a - b)     |
               |  Sets flags: SF, OF, ZF in %rflags     |
               +----------------------------------------+
                                   |
                                   v  [Monotonic Flow: %rip advances]
               +----------------------------------------+
               |        2. Default Assignment           |
               |  movq   %rsi, %rax                     |
               |  State: %rax = b                       |
               +----------------------------------------+
                                   |
                                   v  [Monotonic Flow: %rip advances]
               +----------------------------------------+
               |         3. Conditional Move            |
               |  cmovge %rdi, %rax                     |
               |  Condition: (SF ^ OF) == 0 (i.e. a>=b) |
               |                                        |
               |  [ a >= b ]: %rax <-- %rdi (value a)   |
               |  [ a <  b ]: %rax unchanged (value b)  |
               +----------------------------------------+
                                   |
                                   v  [Monotonic Flow: %rip advances]
               +----------------------------------------+
               |             Function Exit              |
               |  ret (Returns value in %rax)           |
               +----------------------------------------+

-O2 Shape (Strictly Linear / Monotonic Pipeline):

[Compare] ──> [Speculative Load] ──> [Conditional Select] ──> [Return]

The instruction stream never branches. The CPU pipeline executes in a straight line without stalling.

---