Carnegie Mellon
Machine-Level Programming II: Control
15-213/18-213/14-513/15-513: Introduction to Computer Systems 6th Lecture, May 28, 2020
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
1
Carnegie Mellon
Today
Control: Condition codes Conditional branches
Loops
Switch Statements
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
2
Carnegie Mellon
Recall: ISA = Assembly/Machine Code View
CPU
PC
Registers
Addresses
Data Instructions
Memory
Code Data Stack
Condition Codes
Programmer-Visible State
▪ PC: Program counter
▪ Address of next instruction
▪ Register file
▪ Heavily used program data
▪ Condition codes
▪ Store status information about most
recent arithmetic or logical operation ▪ Used for conditional branching
▪ Memory
▪ Byte addressable array
▪ Code and user data
▪ Stack to support procedures
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
3
Carnegie Mellon
Recall: Turning C into Object Code
▪ Code in files p1.c p2.c
▪ Compile with command: gcc –Og p1.c p2.c -o p
▪ Use basic optimizations (-Og) [New to recent versions of GCC] ▪ Put resulting binary in file p
text
text
binary
C program (p1.c p2.c)
Compiler (gcc –Og -S)
Asm program (p1.s p2.s)
Assembler (gcc or as)
Object program (p1.o p2.o)
Linker (gcc or ld)
Executable program (p) Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
binary
Static libraries (.a)
4
Carnegie Mellon
Recall: Move & Arithmetic Operations
Some Two Operand Instructions: Format Computation
movq Src,Dest leaq Src,Dest addq Src,Dest subq Src,Dest imulq Src,Dest salq Src,Dest sarq Src,Dest shrq Src,Dest xorq Src,Dest andq Src,Dest orq Src,Dest
Dest = Src (Src can be $const)
Dest = address computed by expression Src Dest = Dest + Src
Dest = Dest − Src
Dest = Dest * Src
Dest = Dest << Src
Dest = Dest >> Src
Dest = Dest >> Src
Dest = Dest ^ Src
Dest = Dest & Src
Dest = Dest | Src
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
5
Also called shlq Arithmetic Logical
Carnegie Mellon
Recall: Addressing Modes
Most General Form
▪ D: ▪ Rb: ▪ Ri: ▪S:
D(Rb,Ri,S) Mem[Reg[Rb]+S*Reg[Ri]+ D]
Constant “displacement” 1, 2, or 4 bytes Base register: Any of 16 integer registers Index register: Any, except for %rsp Scale: 1, 2, 4, or 8
Special Cases (Rb,Ri)
D(Rb,Ri) (Rb,Ri,S)
Mem[Reg[Rb]+Reg[Ri]] Mem[Reg[Rb]+Reg[Ri]+D] Mem[Reg[Rb]+S*Reg[Ri]]
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
6
Carnegie Mellon
Processor State (x86-64, Partial)
Information about currently executing program
▪ Temporary data ( %rax, … )
▪ Location of runtime stack (%rsp)
▪ Location of current code control point
( %rip, … )
▪ Status of recent tests ( CF, ZF, SF, OF )
Current stack top
Registers
%rax
%rbx
%rcx
%rdx
%rsi
%rdi
%rsp
%rbp
%r8
%r9
%r10
%r11
%r12
%r13
%r14
%r15
%rip Instruction pointer
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
7
CF ZF SF OF
Condition codes
Carnegie Mellon
Condition Codes (Implicit Setting)
Single bit registers
▪CF Carry Flag (for unsigned) SF Sign Flag (for signed)
▪ZF Zero Flag OF Overflow Flag (for signed)
Implicitly set (as side effect) of arithmetic operations Example: addq Src,Dest ↔ t = a+b
CF set if carry/borrow out from most significant bit (unsigned overflow) ZFset ift==0
SF set if t < 0 (as signed)
OF set if two’s-complement (signed) overflow
(a>0 && b>0 && t<0) || (a<0 && b<0 && t>=0)
Not set by leaq instruction Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
8
Carnegie Mellon
ZF set when
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
9
000000000000…00000000000
Carnegie Mellon
SF set when +
yxxxxxxxxxxxx…
yxxxxxxxxxxxx…
1xxxxxxxxxxxx…
For signed arithmetic, this reports when result is a negative number
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
10
Carnegie Mellon
CF set when +
1
1
–
For unsigned arithmetic, this reports overflow
Carry
1xxxxxxxxxxxx…
1xxxxxxxxxxxx…
xxxxxxxxxxxxx…
0xxxxxxxxxxxx…
1xxxxxxxxxxxx…
Borrow
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
11
1xxxxxxxxxxxx…
Carnegie Mellon
OF set when +
a b
t
yxxxxxxxxxxxx…
yxxxxxxxxxxxx…
zxxxxxxxxxxxx…
z = ~y
(a>0 && b>0 && t<0) || (a<0 && b<0 && t>=0)
For signed arithmetic, this reports overflow
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
12
Carnegie Mellon
Condition Codes (Explicit Setting: Compare)
Explicit Setting by Compare Instruction
▪ cmpq Src2, Src1
▪ cmpq b,a like computing a-b without setting destination
▪ CF set if carry/borrow out from most significant bit (used for unsigned comparisons)
▪ZFset ifa==b
▪ SF set if (a-b) < 0 (as signed)
▪ OF set if two’s-complement (signed) overflow
(a>0 && b<0 && (a-b)<0) || (a<0 && b>0 && (a-b)>0)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
13
Carnegie Mellon
Condition Codes (Explicit Setting: Test)
Explicit Setting by Test instruction ▪ testq Src2, Src1
▪ testq b,a like computing a&b without setting destination ▪Sets condition codes based on value of Src1 & Src2
▪Useful to have one of the operands be a mask ▪ZF set whena&b == 0
▪SF set whena&b < 0
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
14
Very often:
testq %rax,%rax
Carnegie Mellon
Condition Codes (Explicit Reading: Set) Explicit Reading by Set Instructions
▪ setX Dest: Set low-order byte of destination Dest to 0 or 1 based on combinations of condition codes
▪ Does not alter remaining 7 bytes of Dest
SetX
Condition
Description
sete
ZF
Equal / Zero
setne
~ZF
Not Equal / Not Zero
sets
SF
Negative
setns
~SF
Nonnegative
setg
~(SF^OF)&~ZF
Greater (signed)
setge
~(SF^OF)
Greater or Equal (signed)
setl
SF^OF
Less (signed)
setle
(SF^OF)|ZF
Less or Equal (signed)
seta
~CF&~ZF
Above (unsigned)
setb
CF
Below (unsigned)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
15
Carnegie Mellon
Example: setl (Signed <) Condition: SF^OF
SF
OF
SF ^ OF
Implication
0
0
0
No overflow, so SF implies not <
1
0
1
No overflow, so SF implies <
0
1
1
Overflow, so SF implies negative overflow, i.e. <
1
1
0
Overflow, so SF implies positive overflow, i.e. not <
negative overflow case
-
a b
t
1xxxxxxxxxxxx...
0xxxxxxxxxxxx...
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
16
0xxxxxxxxxxxx...
Carnegie Mellon
x86-64 Integer Registers
%rax
%al
%rbx
%bl
%rcx
%cl
%rdx
%dl
%rsi
%sil
%rdi
%dil
%rsp
%spl
%rbp
%bpl
%r8
%r8b
%r9
%r9b
%r10
%r10b
%r11
%r11b
%r12
%r12b
%r13
%r13b
%r14
%r14b
%r15
%r15b
▪ Can reference low-order byte
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
17
Carnegie Mellon
Explicit Reading Condition Codes (Cont.) SetX Instructions:
▪ Set single byte based on combination of condition codes
One of addressable byte registers ▪ Does not alter remaining bytes
▪ Typically use movzbl to finish job
▪ 32-bit instructions also set upper 32 bits to 0
Register
Use(s)
%rdi
Argument x
%rsi
Argument y
%rax
Return value
int gt (long x, long y)
{
return x > y; }
cmpq %rsi, %rdi
setg %al
movzbl %al, %eax
ret
# Compare x:y
# Set when >
# Zero rest of %rax
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
18
Carnegie Mellon
Explicit Reading Condition Codes (Cont.)
SetX Instructions:
Beware weirdness movzbl (and others)
▪ Set single byte based on combination of condition codes One of addressable byte registers
▪ Does not alter remaining bytes
movzbl %al, %eax
▪ Typically use movzbl to finish job
▪ 32-bit instructions also set upper 32 bits to 0
0x00000000 %al %rax
0x000000 0x000000 %eax %al
int gt (long x, long y)
{
Zapped to all 0’s
return x > y; }
Register
%rdi
%rsi
%rax
Use(s)
Argument x
Argument y
Return value
cmpq %rsi, %rdi
setg %al
movzbl %al, %eax
ret
# Compare x:y
# Set when >
# Zero rest of %rax
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
19
Carnegie Mellon
Today
Control: Condition codes Conditional branches
Loops
Switch Statements
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
20
Carnegie Mellon
Jumping
jX Instructions
▪ Jump to different part of code depending on condition codes ▪ Implicit reading of condition codes
jX
Condition
Description
jmp
1
Unconditional
je
ZF
Equal / Zero
jne
~ZF
Not Equal / Not Zero
js
SF
Negative
jns
~SF
Nonnegative
jg
~(SF^OF)&~ZF
Greater (signed)
jge
~(SF^OF)
Greater or Equal (signed)
jl
SF^OF
Less (signed)
jle
(SF^OF)|ZF
Less or Equal (signed)
ja
~CF&~ZF
Above (unsigned)
jb
CF
Below (unsigned)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
21
Conditional Branch Example (Old Style) Generation
shark> gcc –Og -S –fno-if-conversion control.c
absdiff:
cmpq %rsi, %rdi # x:y jle .L4
movq %rdi, %rax
subq %rsi, %rax
ret
.L4: # x <= y
movq %rsi, %rax
subq %rdi, %rax
ret
Carnegie Mellon
long absdiff
(long x, long y)
{
long result; if (x > y)
result = x-y;
else
result = y-x;
return result;
}
Register
Use(s)
%rdi
Argument x
%rsi
Argument y
%rax
Return value
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
22
Get to this shortly
Carnegie Mellon
Expressing with Goto Code C allows goto statement
Jump to position designated by label
long absdiff
(long x, long y)
{
long result;
if (x > y)
result = x-y;
else
result = y-x;
return result;
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
23
long absdiff_j
(long x, long y)
{
long result;
int ntest = x <= y; if (ntest) goto Else; result = x-y;
goto Done;
Else:
result = y-x;
Done:
return result;
}
Carnegie Mellon
General Conditional Expression Translation
(Using Branches) C Code
val = Test ? Then_Expr : Else_Expr; val = x>y ? x-y : y-x;
Goto Version
ntest = !Test;
if (ntest) goto Else; val = Then_Expr;
goto Done;
Else:
val = Else_Expr;
Done:
. ..
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
24
▪ Create separate code regions for then & else expressions
▪ Execute appropriate one
Carnegie Mellon
Using Conditional Moves
Conditional Move Instructions ▪ Instruction supports:
if (Test) DestSrc
▪ Supported in post-1995 x86 processors ▪ GCC tries to use them
▪ But, only when known to be safe Why?
▪ Branches are very disruptive to instruction flow through pipelines
▪ Conditional moves do not require control transfer
C Code
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
25
val = Test
? Then_Expr
: Else_Expr;
Goto Version
result = Then_Expr;
eval = Else_Expr;
nt = !Test;
if (nt) result = eval; return result;
Carnegie Mellon
Conditional Move Example
long absdiff
(long x, long y)
{
long result;
if (x > y)
result = x-y;
else
result = y-x;
return result; }
Register
Use(s)
%rdi
Argument x
%rsi
Argument y
%rax
Return value
When is this bad?
#eval=y-x
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
26
absdiff:
movq %rdi, %rax
subq %rsi, %rax
movq %rsi, %rdx
subq %rdi, %rdx
cmpq %rsi, %rdi # x:y
cmovle %rdx, %rax # if <=, result = eval ret
#x
# result = x-y
Carnegie Mellon
Bad Cases for Conditional Move Expensive Computations
val = Test(x) ? Hard1(x) : Hard2(x);
Both values get computed
Only makes sense when computations are very simple
Risky Computations
val = p ? *p : 0;
Both values get computed
May have undesirable effects
Computations with side effects
val = x > 0 ? x*=7 : x+=3;
Both values get computed
Must be side-effect free
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Unsafe
Bad Performance
Illegal
27
Carnegie Mellon
Today
Control: Condition codes Conditional branches
Loops
Switch Statements
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
28
Carnegie Mellon
“Do-While” Loop Example
C Code Goto Version
Count number of 1’s in argument x (“popcount”) Use conditional branch to either continue looping
or to exit loop
long pcount_do (unsigned long x) { long result = 0; do {
result += x & 0x1;
x >>= 1;
} while (x);
return result;
}
long pcount_goto
(unsigned long x) {
long result = 0;
loop:
result += x & 0x1;
x >>= 1;
if(x) goto loop;
return result;
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
29
x86 being CISC has a popcount instruction
Carnegie Mellon
“Do-While” Loop Compilation
long pcount_goto
(unsigned long x) {
long result = 0;
loop:
result += x & 0x1; x >>= 1;
if(x) goto loop; return result;
}
Register
Use(s)
%rdi
Argument x
%rax
result
movl $0, %eax
.L2:
movq %rdi, %rdx andl $1,%edx addq %rdx, %rax shrq %rdi
jne .L2
rep; ret
# result = 0
# loop:
# t=x&0x1
# result += t
# x>>=1
# if(x) goto loop
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
30
Carnegie Mellon
General “Do-While” Translation
C Code
Goto Version
do
Body
while (Test);
Body:
{ Statement1; Statement2;
… Statementn;
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
31
loop:
Body
if (Test)
goto loop
Carnegie Mellon
General “While” Translation #1 “Jump-to-middle” translation
Used with -Og While version
Goto Version
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
32
goto test;
loop:
Body
test:
if (Test)
goto loop;
done:
while (Test) Body
Carnegie Mellon
While Loop Example #1
C Code Jump to Middle
Compare to do-while version of function Initial goto starts loop at test
long pcount_while (unsigned long x) { long result = 0; while (x) {
result += x & 0x1;
x >>= 1; }
return result;
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
33
Version
long pcount_goto_jtm
(unsigned long x) { long result = 0; goto test;
loop:
result += x & 0x1;
x >>= 1;
test:
if(x) goto loop;
return result;
}
Carnegie Mellon
General “While” Translation #2
While version
“Do-while” conversion Used with –O1
Goto Version
while (Test) Body
Do-While Version
if (!Test) goto done;
loop:
Body
if (Test)
goto loop;
done:
if (!Test) goto done;
do
Body
while(Test); done:
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
34
Carnegie Mellon
While Loop Example #2
C Code Do-While Version
Initial conditional guards entrance to loop Compare to do-while version of function
▪ Removes jump to middle. When is this good or bad? Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
35
long pcount_while (unsigned long x) { long result = 0; while (x) {
result += x & 0x1;
x >>= 1; }
return result;
}
long pcount_goto_dw (unsigned long x) { long result = 0; if (!x) goto done;
loop:
result += x & 0x1;
x >>= 1;
if(x) goto loop;
done:
return result;
}
Carnegie Mellon
“For” Loop Form General Form
Init
i=0
Test
i < WSIZE
Update
i++
Body
for (Init; Test; Update ) Body
#define WSIZE 8*sizeof(int)
long pcount_for
(unsigned long x)
{
size_t i;
long result = 0;
for (i = 0; i < WSIZE; i++)
{
unsigned bit = (x >> i) & 0x1;
result += bit;
}
return result;
}
36
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
{
unsigned bit =
(x >> i) & 0x1; result += bit;
}
Carnegie Mellon
“For” Loop→While Loop For Version
for (Init; Test; Update ) Body
While Version
Init;
while (Test ) {
Body
Update; }
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
37
Carnegie Mellon
For-While Conversion Init
i=0
Test
i < WSIZE
Update
i++
Body
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
38
long pcount_for_while
(unsigned long x)
{
size_t i;
long result = 0;
i = 0;
while (i < WSIZE)
{
unsigned bit = (x >> i) & 0x1;
result += bit;
i++;
}
return result;
}
{
}
unsigned bit =
(x >> i) & 0x1;
result += bit;
Carnegie Mellon
“For” Loop Do-While Conversion
C Code
Goto Version
Initial test can be optimized away – why?
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
long pcount_for_goto_dw (unsigned long x) { size_t i;
long result = 0;
i = 0; Init if (!(i < WSIZE))
long pcount_for (unsigned long x)
{
size_t i;
long result = 0;
for (i = 0; i < WSIZE; i++) {
unsigned bit =
(x >> i) & 0x1;
result += bit;
}
return result;
}
goto done;
loop:
!Test
Body
{
unsigned bit =
(x >> i) & 0x1;
result += bit;
}
i++;
if (i < WSIZE)
goto loop;
done:
return result;
}
Update
Test
39
Carnegie Mellon
Today
Control: Condition codes Conditional branches
Loops
Switch Statements
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
40
Carnegie Mellon
long my_switch
(long x, long y, long z)
{
long w = 1;
switch(x) {
case 1:
w = y*z;
break;
case 2:
w = y/z;
/* Fall Through */
case 3:
w += z;
break;
case 5:
case 6:
w -= z;
break; default:
w = 2; }
return w; }
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
41
Switch Statement Example
Multiple case labels ▪ Here: 5 & 6
Fall through cases ▪ Here: 2
Missing cases ▪ Here: 4
Carnegie Mellon
Jump Table Structure
Switch Form
Jump Table
jtab:
Jump Targets
Targ0:
Targ1:
Targ2:
Targ0
Targ1
Targ2
• • •
Targn-1
switch(x) {
case val_0:
Block 0 case val_1:
Block 1
•••
case val_n-1:
Block n–1 }
Translation (Extended C)
goto *JTab[x];
• • •
Code Block 0
Code Block 1
Code Block 2
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
42
Targn-1:
Code Block n–1
Carnegie Mellon
Switch Statement Example
long my_switch(long x, long y, long z)
{
long w = 1;
switch(x) {
... }
return w; }
Setup
my_switch:
movq %rdx, %rcx
cmpq $6, %rdi # x:6 ja .L8
jmp *.L4(,%rdi,8)
What range of values
takes default?
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Note that w not initialized here
43
Register
Use(s)
%rdi
Argument x
%rsi
Argument y
%rdx
Argument z
%rax
Return value
Carnegie Mellon
Switch Statement Example
long my_switch(long x, long y, long z)
{
long w = 1;
switch(x) {
... }
return w; }
Jump table
Setup
my_switch:
movq %rdx, %rcx
cmpq $6, %rdi
ja .L8
jmp *.L4(,%rdi,8) # goto *Jtab[x]
Indirect jump
# x:6
# use default
.section .rodata .align 8
.L4:
.quad .L8 #x=0 .quad .L3 #x=1 .quad .L5 #x=2 .quad .L9 #x=3 .quad .L8 #x=4 .quad .L7 #x=5 .quad .L7 #x=6
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
44
Carnegie Mellon
Assembly Setup Explanation
Table Structure
▪ Each target requires 8 bytes ▪ Base address at .L4
Jumping
▪ Direct: jmp .L8
▪ Jump target is denoted by label .L8
Jump table
▪ Indirect: jmp *.L4(,%rdi,8)
▪ Start of jump table: .L4
▪ Must scale by factor of 8 (addresses are 8 bytes) ▪ Fetch target from effective Address .L4 + x*8
▪ Only for 0 ≤ x ≤ 6
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
45
.section .rodata .align 8
.L4:
.quad .L8 #x=0 .quad .L3 #x=1 .quad .L5 #x=2 .quad .L9 #x=3 .quad .L8 #x=4 .quad .L7 #x=5 .quad .L7 #x=6
Carnegie Mellon
Jump Table Jump table
.section .rodata .align 8
.L4:
.quad .L8 #x=0 .quad .L3 #x=1 .quad .L5 #x=2 .quad .L9 #x=3 .quad .L8 #x=4 .quad .L7 #x=5 .quad .L7 #x=6
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
46
switch(x) { case 1:
w = y*z;
break;
case 2:
// .L3
// .L5
/* Fall Through */
w = y/z;
case 3:
w += z;
break;
case 5:
case 6:
w -= z;
break;
default:
w = 2; }
// .L9
// .L7 // .L8
Carnegie Mellon
Code Blocks (x == 1)
switch(x) {
case 1: // .L3
w = y*z;
break; .. .
}
Register
Use(s)
%rdi
Argument x
%rsi
Argument y
%rdx
Argument z
%rax
Return value
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
47
.L3:
movq %rsi, %rax # y
imulq %rdx, %rax # y*z
ret
Carnegie Mellon
Handling Fall-Through
long w = 1; . ..
switch(x) { . ..
case 2:
w = y/z;
/* Fall Through */ case 3:
w += z;
break; . ..
}
case 2:
w = y/z;
goto merge;
case 3:
w = 1;
merge:
w += z;
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
48
Carnegie Mellon
Code Blocks (x == 2, x == 3)
long w = 1; . ..
switch(x) { . ..
case 2:
w = y/z;
/* Fall Through */ case 3:
w += z;
break; . ..
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
49
.L5: movq
cqto
idivq %rcx
jmp .L6 .L9:
movl $1, %eax .L6:
Register
%rdi
%rsi
%rcx
%rax
# Case 2
%rsi, %rax
addq %rcx, %rax # w += z ret
Use(s)
Argument x
Argument y
z
Return value
# sign extend
# rax to rdx:rax
# y/z
# goto merge # Case 3
# w = 1
# merge:
Carnegie Mellon
Code Blocks (x == 5, x == 6, default)
}
switch(x) { ...
case 5: // .L7
case 6: // .L7
w -= z;
break;
default: // .L8
w = 2;
Register
Use(s)
%rdi
Argument x
%rsi
Argument y
%rdx
Argument z
%rax
Return value
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
50
.L7: # Case 5,6 movl $1,%eax # w=1 subq %rdx, %rax # w -= z ret
.L8: # Default:
movl $2, %eax # 2
ret
Carnegie Mellon
Summarizing
C Control
▪ if-then-else
▪ do-while ▪ while, for ▪ switch
Assembler Control
▪ Conditional jump
▪ Conditional move
▪ Indirect jump (via jump tables)
▪ Compiler generates code sequence to implement more complex control
Standard Techniques
▪ Loops converted to do-while or jump-to-middle form
▪ Large switch statements use jump tables
▪ Sparse switch statements may use decision trees (if-elseif-elseif-else) Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
51
Carnegie Mellon
Summary
Today
▪ Control: Condition codes
▪ Conditional branches & conditional moves ▪ Loops
▪ Switch statements
Next Time ▪ Stack
▪ Call / return
▪ Procedure call discipline
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
52
Carnegie Mellon
Finding Jump Table in Binary
00000000004005e0
4005e0: 48 89 4005e3: 48 83 4005e7: 77 2b 4005e9: ff 24 4005f0: 48 89 4005f3: 48 0f
4005f7: c3
4005f8: 48 89
4005fb: 48 99 4005fd: 48 f7 400600: eb 05 400602: b8 01 400607: 48 01
40060a: c3
40060b: b8 01
400610: 48 29 d0
400613: c3
400614: b8
400619: c3
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
53
02
00 00 00
d1 ff
fd f0 af
f0
f9
00 c8
00 00
06 f0 c2
00 00 00
07 40 00
mov %rdx,%rcx
cmp $0x6,%rdi
ja 400614
mov %rsi,%rax
imul %rdx,%rax
retq
mov %rsi,%rax
cqto
idiv %rcx
jmp 400607
add %rcx,%rax
retq
mov $0x1,%eax
sub %rdx,%rax
retq
mov $0x2,%eax
retq
Carnegie Mellon
Finding Jump Table in Binary (cont.)
00000000004005e0
…
4005e9: ff 24 fd f0 07 40 00 jmpq *0x4007f0(,%rdi,8) …
% gdb switch
(gdb) x /8xg 0x4007f0
0x4007f0:
0x400800:
0x400810:
0x400820:
(gdb)
0x0000000000400614
0x00000000004005f8
0x0000000000400614
0x000000000040060b
0x00000000004005f0
0x0000000000400602
0x000000000040060b
0x2c646c25203d2078
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
54
Carnegie Mellon
Finding Jump Table in Binary (cont.)
% gdb switch
(gdb) x /8xg 0x4007f0
0x4007f0: 0x400800: 0x400810: 0x400820:
0x0000000000400614 0x00000000004005f8 0x0000000000400614 0x000000000040060b
0x00000000004005f0 0x0000000000400602 0x000000000040060b 0x2c646c25203d2078
…
4005f0: 48 89 4005f3: 48 0f
4005f7: c3
4005f8: 48 89
4005fb: 48 99
4005fd: 48 f7
400600: eb 05
400602: b8 01
400607: 48 01
40060a: c3
40060b: b8 01
400610: 48 29 d0
400613: c3
400614: b8
400619: c3
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
55
02
00 00
f0 af c2
mov %rsi,%rax imul %rdx,%rax retq
mov %rsi,%rax cqto
idiv %rcx
jmp 400607
add %rcx,%rax
retq
mov $0x1,%eax
sub %rdx,%rax
retq
mov $0x2,%eax
retq
f0 f9
00 c8
00 00
00 00
00 00