程序代写代做代考 assembler js compiler x86 assembly decision tree C Carnegie Mellon

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) DestSrc
▪ 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 jmpq *0x4007f0(,%rdi,8)
mov %rsi,%rax
imul %rdx,%rax
retq
mov %rsi,%rax
cqto
idiv %rcx
jmp 400607 mov $0x1,%eax
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 mov $0x1,%eax
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