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

Carnegie Mellon
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
1
14
–
513
18
–
613

Carnegie Mellon
Machine-Level Programming II: Control
15-213/18-213/14-513/15-513/18-613: Introduction to Computer Systems 6th Lecture, September 16, 2020
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
2

Carnegie Mellon
Announcements  Lab 1 (datalab)
▪ Due Thurs, Sept. 17, 11:59pm ET
 Written Assignment 1 peer grading
▪ Due Wed, Sept. 23, 11:59pm ET
 Written Assignment 2 available on Canvas
▪ Due Wed, Sept. 23, 11:59pm ET
 Lab 2 (bomblab) will be available at midnight via Autolab
▪ Due Tues, Sept. 29, 11:59 pm ET
 Recitation on bomblab this Monday
▪ In person: you have been contacted with your recitation info ▪ Online: use the zoom links provided on the Canvas homepage
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
3

Carnegie Mellon
Catching Up
 Reviewing LEAQ (based on after-class questions)  Reviewing Arithmetic Expressions in ASM
 C -> Assembly -> Machine Code
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
4

Carnegie Mellon
LEA: Evaluate Memory Address Expression Without Accessing Memory
 leaq Src, Dst
▪ Src is address computation expression
▪ Set Dst to address denoted by expression
D(Rb,Ri,S): Reg[Rb]+S*Reg[Ri]+ D
 Uses
▪ Computing address/pointer WITHOUT ACCESSING MEMORY
▪ E.g., translation of p = &x[i];
▪ Compute arbitrary expressions of form: b+(s*i)+d, where s = 1, 2, 4, or 8
▪ [also w/o accessing memory]
 Example
Converted to ASM by compiler:
long m12(long x) {
return x*12;
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
5
leaq (%rdi,%rdi,2), %rax # t = x+2*x salq $2, %rax # return t<<2 Carnegie Mellon LEA vs. other instructions (e.g., MOV)  leaq D(Rb,Ri,S), dst ▪ dst Reg[Rb]+S*Reg[Ri]+ D ▪ NO MEMORY ACCESS HAPPENS!  movq D(Rb,Ri,S), dst ▪ dst Mem[Reg[Rb]+S*Reg[Ri]+ D] ▪ MEMORY ACCESS HAPPENS! Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 6 Carnegie Mellon Arithmetic Expression Example arith: leaq (%rdi,%rsi), %rax addq %rdx, %rax leaq (%rsi,%rsi,2), %rdx salq $4, %rdx leaq 4(%rdi,%rdx), %rcx imulq %rcx, %rax ret Interesting Instructions ▪ leaq: address computation ▪ salq: shift ▪ imulq: multiplication ▪ Curious: only used once... long arith (long x, long y, long z) { long t1 = x+y; long t2 = z+t1; long t3 = x+4; long t4 = y * 48; long t5 = t3 + t4; long rval = t2 * t5; return rval; } Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 8 Carnegie Mellon Understanding Arithmetic Expression Example arith: leaq (%rdi,%rsi), %rax addq %rdx, %rax leaq (%rsi,%rsi,2), %rdx salq $4, %rdx leaq 4(%rdi,%rdx), %rcx # t5 imulq %rcx, %rax # rval ret # t1 # t2 long arith (long x, long y, long z) { long t1 = x+y; long t2 = z+t1; long t3 = x+4; long t4 = y * 48; long t5 = t3 + t4; long rval = t2 * t5; return rval; } # t4 Register Use(s) %rdi Argument x %rsi Argument y %rdx Argument z, t4 %rax t1, t2, rval %rcx t5 D(Rb,Ri,S): Mem[Reg[Rb]+S*Reg[Ri]+ D] Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 9 Carnegie Mellon Today: Machine Programming I: Basics  History of Intel processors and architectures  Assembly Basics: Registers, operands, move  Arithmetic & logical operations  C, assembly, machine code Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 10 Carnegie Mellon 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) 11 Carnegie Mellon Compiling Into Assembly C Code (sum.c) Generated x86-64 Assembly long plus(long x, long y); void sumstore(long x, long y, long *dest) { long t = plus(x, y); *dest = t; } Obtain (on shark machine) with command gcc –Og –S sum.c Produces file sum.s Warning: Will get very different results on non-Shark machines (Andrew Linux, Mac OS-X, ...) due to different versions of gcc and different compiler settings. Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 12 sumstore: pushq %rbx movq %rdx, %rbx call plus movq %rax, (%rbx) popq %rbx ret Carnegie Mellon What it really looks like .globl sumstore .type sumstore, @function sumstore: .LFB35: .cfi_startproc pushq %rbx .cfi_def_cfa_offset 16 .cfi_offset 3, -16 movq %rdx, %rbx call plus movq %rax, (%rbx) popq %rbx .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE35: .size sumstore, .-sumstore Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 13 Carnegie Mellon What it really looks like .globl sumstore .type sumstore, @function sumstore: .LFB35: .cfi_startproc pushq %rbx .cfi_def_cfa_offset 16 .cfi_offset 3, -16 movq %rdx, %rbx call plus movq %rax, (%rbx) popq %rbx .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE35: .size sumstore, .-sumstore Things that look weird and are preceded by a ‘.’ are generally directives. Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 14 sumstore: pushq %rbx movq %rdx, %rbx call plus movq %rax, (%rbx) popq %rbx ret Carnegie Mellon Object Code Code for sumstore  Assembler ▪ Translates .s into .o ▪ Binary encoding of each instruction ▪ Nearly-complete image of executable code ▪ Missing linkages between code in different files  Linker ▪ Resolves references between files ▪ Combines with static run-time libraries ▪ E.g., code for malloc, printf ▪ Some libraries are dynamically linked ▪ Linking occurs when program begins execution 0x0400595: 0x53 0x48 0x89 0xd3 0xe8 0xf2 0xff 0xff 0xff 0x48 0x89 0x03 0x5b 0xc3 • • • Total of 14 bytes Each instruction 1, 3, or 5 bytes Starts at address 0x0400595 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 17 Carnegie Mellon Machine Instruction Example *dest = t; movq %rax, (%rbx)  C Code ▪ Store value t where designated by dest  Assembly ▪ Move 8-byte value to memory ▪ Quad words in x86-64 parlance ▪ Operands: t: Register %rax dest: Register %rbx *dest: MemoryM[%rbx]  Object Code ▪ 3-byte instruction ▪ Stored at address 0x40059e 0x40059e: 48 89 03 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 18 Carnegie Mellon Disassembling Object Code Disassembled 0000000000400595 :
400595: 53
400596: 48 89 d3 400599: e8 f2 ff ff ff 40059e: 48 89 03 4005a1: 5b
4005a2: c3
push %rbx
mov %rdx,%rbx callq 400590 mov %rax,(%rbx) pop %rbx
retq
 Disassembler
objdump –d sum
▪ Useful tool for examining object code
▪ Analyzes bit pattern of series of instructions
▪ Produces approximate rendition of assembly code
▪ Can be run on either a.out (complete executable) or .o file
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
19

Carnegie Mellon
Alternate Disassembly Disassembled
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
20
 Within gdb Debugger
▪ Disassemble procedure gdb sum
disassemble sumstore
Dump of assembler code for function sumstore:
0x0000000000400595 <+0>: push 0x0000000000400596 <+1>: mov 0x0000000000400599 <+4>: callq 0x000000000040059e <+9>: mov 0x00000000004005a1 <+12>:pop 0x00000000004005a2 <+13>:retq
%rbx
%rdx,%rbx 0x400590 %rax,(%rbx) %rbx

Carnegie Mellon
Alternate Disassembly
Object Code
Disassembled
0x0400595: 0x53 0x48 0x89 0xd3 0xe8 0xf2 0xff 0xff 0xff 0x48 0x89 0x03 0x5b 0xc3
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
21
 Within gdb Debugger
▪ Disassemble procedure
gdb sum
disassemble sumstore
▪ Examine the 14 bytes starting at sumstore x/14xb sumstore
Dump of assembler code for function sumstore:
0x0000000000400595 <+0>: push 0x0000000000400596 <+1>: mov 0x0000000000400599 <+4>: callq 0x000000000040059e <+9>: mov 0x00000000004005a1 <+12>:pop 0x00000000004005a2 <+13>:retq
%rbx
%rdx,%rbx 0x400590 %rax,(%rbx) %rbx

Carnegie Mellon
What Can be Disassembled?
% objdump -d WINWORD.EXE WINWORD.EXE: file format pei-i386
No symbols in “WINWORD.EXE”.
Disassembly of section .text:
30001000 <.text>: 30001000: 30001001: 30001003: 30001005: 3000100a:
55 push %ebp
8b ec mov %esp,%ebp
Reverse engineering forbidden by
6a ff push $0xffffffff
Microsoft End User License Agreement
68 90 10 00 30 push $0x30001090 68 91 dc 4c 30 push $0x304cdc91
 Anything that can be interpreted as executable code
 Disassembler examines bytes and reconstructs assembly source
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
22

Carnegie Mellon
Machine Programming I: Summary  History of Intel processors and architectures
▪ Evolutionary design leads to many quirks and artifacts
 C, assembly, machine code
▪ New forms of visible state: program counter, registers, …
▪ Compiler must transform statements, expressions, procedures into low-level instruction sequences
 Assembly Basics: Registers, operands, move
▪ The x86-64 move instructions cover wide range of data movement
forms
 Arithmetic
▪ C compiler will figure out different instruction combinations to
carry out computation
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
23

Carnegie Mellon
Today
 Control: Condition codes  Conditional branches
 Loops
 Switch Statements
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
24

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
29
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
30

Carnegie Mellon
ZF set when
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
31
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
32

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
33
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
34

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
35

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 36 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 37 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 38 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 39 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
40

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
41

Carnegie Mellon
Today
 Control: Condition codes  Conditional branches
 Loops
 Switch Statements
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
42

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
43

Carnegie Mellon
Conditional Branch Example (Old Style)
 Generation
shark> gcc –Og -S –fno-if-conversion control.c
absdiff:
cmpq %rsi, %rdi # x:y, x-y jle .L4
movq %rdi, %rax
subq %rsi, %rax
ret
.L4: # x <= y movq %rsi, %rax subq %rdi, %rax ret Get to this shortly 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
44

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
45
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
46
▪ 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
47
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
48
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
49

Carnegie Mellon
Exercise
cmpq b,a like computing a-b w/o setting 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)
 CF set
if carry/borrow out from most significant bit (used for unsigned comparisons)
ifa == b
if (a-b) < 0 (as signed) ZF set  SF set  OF set if two’s-complement (signed) overflow %rax SF CF OF ZF 0x0000 0000 0000 0000 0 0 0 1 0xFFFF FFFF FFFF FFFF 1 1 0 0 0xFFFF FFFF FFFF FFFF 1 0 0 0 0xFFFF FFFF FFFF FF01 1 0 0 0 0x0000 0000 0000 0001 1 0 0 0 xorq %rax, %rax subq $1, %rax cmpq $2, %rax setl %al movzblq %al, %eax Note: setl and movzblq do not modify condition codes Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 50 Carnegie Mellon Exercise cmpq b,a like computing a-b w/o setting 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)  CF set if carry/borrow out from most significant bit (used for unsigned comparisons) ifa == b if (a-b) < 0 (as signed) ZF set  SF set  OF set if two’s-complement (signed) overflow %rax SF CF OF ZF 0x0000 0000 0000 0000 0 0 0 1 0xFFFF FFFF FFFF FFFF 1 1 0 0 0xFFFF FFFF FFFF FFFF 1 0 0 0 0xFFFF FFFF FFFF FF01 1 0 0 0 0x0000 0000 0000 0001 1 0 0 0 xorq %rax, %rax subq $1, %rax cmpq $2, %rax setl %al movzblq %al, %eax Note: setl and movzblq do not modify condition codes Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 51 Carnegie Mellon Today  Control: Condition codes  Conditional branches  Loops  Switch Statements Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 52 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;
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
53
long pcount_goto
(unsigned long x) {
long result = 0;
loop:
result += x & 0x1;
x >>= 1;
if(x) goto loop;
return result;
}

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
54

Carnegie Mellon
Quiz Time!
Check out:
https://canvas.cmu.edu/courses/17808
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
55

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
56
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
57
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
58
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
59

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
60
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;
}
61
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
62

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 63 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 64 Carnegie Mellon Today  Control: Condition codes  Conditional branches  Loops  Switch Statements Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 65 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 66 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 67 Targn-1: Code Block n–1 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; } .L3: .L5: .L9: .L7: .L8: Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 68 Switch Statement Example my_switch: cmpq $6, %rdi # x:6 ja .L8 # if x > 6 jump
# to default
jmp *.L4(,%rdi,8)
.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
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
71
.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
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
73
.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
74

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
75
.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
76
.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
77

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
78

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
79
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
80

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
81
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