CS代考 PowerPoint Presentation - Introduction to Computer Systems 15-213/18-213

PowerPoint Presentation – Introduction to Computer Systems 15-213/18-213

Machine language II

Acknowledgement: These slides are based on the textbook
(Computer Systems: A Programmer’s Perspective) and its slides.

What happens in machine code and CPU?
During the execution of
Arithmetic/comparison operators
Conditional branches, loops, ……

C programs

Executable file
long absdiff
(long x, long y)
long result;
if (x > y)
result = x-y;
result = y-x;
return result;
long pcount
(unsigned long x)
long result = 0;
while (x) {
result += x & 0x1;
return result;

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Control: Condition codes

Conditional branches

Switch Statements

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Processor State (x86-64, Partial)
Information about currently executing program
Temporary data
( %rax, … )
Location of runtime stack
Location of current code control point
( %rip, … )
Status of recent tests
( CF, ZF, SF, OF )
Current stack top
Instruction pointer
Condition codes

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

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) by arithmetic operations
Example: addq Src,Dest ↔ t = a+b
CF set if carry out from most significant bit (unsigned overflow)
ZF set if t == 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)
Note: leaq is not considered as arithmetic instruction

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Condition Codes (Explicit Setting: Compare)
Explicit Setting by Compare Instruction
cmpq Src1, Src2
cmpq b,a like computing a-b without setting destination

CF set if carry out from most significant bit (used for unsigned comparisons)
ZF set if a == 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

Condition Codes (Explicit Setting: Test)
Explicit Setting by Test instruction
testq Src1, Src2
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 when a&b == 0
SF set when a&b < 0 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Reading Condition Codes SetX Instructions Set low-order byte of destination to 0 or 1 based on combinations of condition codes Does not alter remaining 7 bytes 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 x86-64 Integer Registers Integer registers (64-bit) %rax, %rbx, %rcx, %rdx, %rsi, %rdi, %rbp, %rsp %r8, %r9, %r10, %r11, %r12, %r13, %r14, %r15 The lower-order portion of a register can be accessed as byte, word (16-bit), double-word (32-bit) E.g., r8b (byte), r8w (16-bit), r8d (32-bit) Assembly-code suffix b: 1 byte, w: 2 bytes, l: 4 bytes, q: 8 bytes Example: movb, movw, movl, movq Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition cmpq %rsi, %rdi # Compare x:y setg %al # Set when >
movzbl %al, %eax # Zero rest of %rax

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
int gt (long x, long y)
return x > y;
Register Use(s)
%rdi Argument x
%rsi Argument y
%rax Return value

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Control: Condition codes

Conditional branches

Switch Statements

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

jX Instructions
Jump to different part of code depending on 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

Conditional Branch Example (Old Style)
long absdiff
(long x, long y)
long result;
if (x > y)
result = x-y;
result = y-x;
return result;
cmpq %rsi, %rdi # x:y
jle .L4
movq %rdi, %rax
subq %rsi, %rax
.L4: # x <= y movq %rsi, %rax subq %rdi, %rax Generation gcc –Og -S –fno-if-conversion control.c Register Use(s) %rdi Argument x %rsi Argument y %rax Return value Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Expressing with Goto Code long absdiff (long x, long y) long result; if (x > y)
result = x-y;
result = y-x;
return result;
C allows goto statement
Jump to position designated by label

long absdiff_j
(long x, long y)
long result;
int ntest = x <= y; if (ntest) goto Else; result = x-y; goto Done; result = y-x; return result; Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition val = Test ? Then_Expr : Else_Expr; Goto Version ntest = !Test; if (ntest) goto Else; val = Then_Expr; goto Done; val = Else_Expr; General Conditional Expression Translation (Using Branches) Create separate code regions for then & else expressions Execute appropriate one val = x>y ? x-y : y-x;

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

val = Test
? Then_Expr
: Else_Expr;
Goto Version
result = Then_Expr;
eval = Else_Expr;
nt = !Test;
if (nt) result = eval;
return result;
Using Conditional Moves
Conditional Move Instructions
Instruction supports:
if (Test) Dest  Src
GCC tries to use them
But, only when known to be safe
Branches are disruptive to instruction flow through pipelines
Conditional moves do not require control transfer

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Conditional Move Example

movq %rdi, %rax # x
subq %rsi, %rax # result = x-y
movq %rsi, %rdx
subq %rdi, %rdx # eval = y-x
cmpq %rsi, %rdi # x:y
cmovle %rdx, %rax # if <=, result = eval long absdiff (long x, long y) long result; if (x > y)
result = x-y;
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

Expensive Computations
Bad Cases for Conditional Move
Both values get computed
Only makes sense when computations are very simple
val = Test(x) ? Hard1(x) : Hard2(x);
Risky Computations
Both values get computed
May have undesirable effects
val = p ? *p : 0;
Computations with side effects
Both values get computed
Must be side-effect free
val = x > 0 ? x*=7 : x+=3;

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Control: Condition codes

Conditional branches

Switch Statements

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

long pcount_do
(unsigned long x) {
long result = 0;
result += x & 0x1;
} while (x);
return result;
Goto Version
long pcount_goto
(unsigned long x) {
long result = 0;
result += x & 0x1;
if(x) goto loop;
return result;
“Do-While” Loop Example
This function is used to count number of 1’s in argument x
Use conditional branch to either
continue looping or exit loop

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

Goto Version
“Do-While” Loop Compilation
movl $0, %eax # result = 0
.L2: # loop:
movq %rdi, %rdx
andl $1, %edx # t = x & 0x1
addq %rdx, %rax # result += t
shrq %rdi # x >>= 1
jne .L2 # if (x) goto loop
long pcount_goto
(unsigned long x) {
long result = 0;
result += x & 0x1;
if(x) goto loop;
return result;
Register Use(s)
%rdi Argument x
%rax result

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

while (Test);
Goto Version
General “Do-While” Translation
Statement1;
Statement2;
Statementn;

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

While version
while (Test)
General “While” Translation #1
“Jump-to-middle” translation
Used with – Version
goto test;
goto loop;

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

long pcount_while
(unsigned long x) {
long result = 0;
while (x) {
result += x & 0x1;
return result;
Jump to Middle Version
long pcount_goto_jtm
(unsigned long x) {
long result = 0;
goto test;
result += x & 0x1;
if(x) goto loop;
return result;
While Loop Example #1
Compare to do-while version of function
Initial goto starts loop at test

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

While version
while (Test)
Do-While Version
if (!Test)
goto done;
while(Test);
General “While” Translation #2
“Do-while” conversion
Used with –O1
Goto Version
if (!Test)
goto done;
goto loop;

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

long pcount_while
(unsigned long x) {
long result = 0;
while (x) {
result += x & 0x1;
return result;
Do-While Version
long pcount_goto_dw
(unsigned long x) {
long result = 0;
if (!x) goto done;
result += x & 0x1;
if(x) goto loop;
return result;
While Loop Example #2
Compare to do-while version of function
Initial conditional guards entrance to loop

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

“For” Loop Form
for (Init; Test; Update )
General Form

#define WSIZE 8*sizeof(int)
long pcount_for
(unsigned long x)
long result = 0;
for (i = 0; i < WSIZE; i++) unsigned bit = (x >> i) & 0x1;
result += bit;
return result;
unsigned bit =
(x >> i) & 0x1;
result += bit;

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

“For” Loop  While Loop
for (Init; Test; Update )
For Version

while (Test ) {
While Version

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

For-While Conversion
long pcount_for_while
(unsigned long x)
long result = 0;
while (i < WSIZE) unsigned bit = (x >> i) & 0x1;
result += bit;
return result;
unsigned bit =
(x >> i) & 0x1;
result += bit;

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition

“For” Loop Do-While Conversion
Initial test can be optimized away
long pcount_for
(unsigned long x)
long result = 0;
for (i = 0; i < WSIZE; i++) unsigned bit = (x >> i) & 0x1;
result += bit;
return result;
Goto Version
long pcount_for_goto_dw
(unsigned long x) {
long result = 0;
if (!(i < WSIZE)) goto done; unsigned bit = (x >> i) & 0x1;
result += bit;
if (i < WSIZE) goto loop; return result; Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Control: Condition codes Conditional branches Switch Statements Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Switch Statement Example Multiple case labels Here: 5 & 6 Fall through cases Missing cases long switch_eg (long x, long y, long z) long w = 1; switch(x) { /* Fall Through */ Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Jump Table Structure Code Block Code Block Code Block Code Block goto *JTab[x]; switch(x) { case val_0: case val_1: case val_n-1: Switch Form Translation (Extended C) Jump Table Jump Targets Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Switch Statement Example long switch_eg(long x, long y, long z) long w = 1; switch(x) { switch_eg: movq %rdx, %rcx cmpq $6, %rdi # x:6 ja .L8 jmp *.L4(,%rdi,8) What range of values takes default? Note that w not initialized here 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 Switch Statement Example long switch_eg(long x, long y, long z) long w = 1; switch(x) { Jump table .section .rodata .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 switch_eg: movq %rdx, %rcx cmpq $6, %rdi # x:6 ja .L8 # Use default jmp *.L4(,%rdi,8) # goto *JTab[x] Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Assembly Setup Explanation Table Structure Each target requires 8 bytes Base address at .L4 Direct: jmp .L8 Jump target is denoted by label .L8 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 Jump table .section .rodata .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 .section .rodata .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 Jump Table Jump table switch(x) { case 1: // .L3 case 2: // .L5 /* Fall Through */ case 3: // .L9 case 6: // .L7 default: // .L8 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Code Blocks (x == 1) movq %rsi, %rax # y imulq %rdx, %rax # y*z switch(x) { case 1: // .L3 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 Handling Fall-Through long w = 1; switch(x) { /* Fall Through */ goto merge; Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Code Blocks (x == 2, x == 3) .L5: # Case 2 movq %rsi, %rax idivq %rcx # y/z jmp .L6 # goto merge .L9: # Case 3 movl $1, %eax # w = 1 .L6: # merge: addq %rcx, %rax # w += z long w = 1; switch(x) { /* Fall Through */ 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 Code Blocks (x == 5, x == 6, default) .L7: # Case 5,6 movl $1, %eax # w = 1 subq %rdx, %rax # w -= z .L8: # Default: movl $2, %eax # 2 switch(x) { case 5: // .L7 case 6: // .L7 default: // .L8 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 Summarizing if-then-else while, for 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 Control: Condition codes Conditional branches & conditional moves Switch statements Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Online Quiz 1 Date/Time: 24 Feb (Thursday), 12:30-13:20 These questions can be answered within 30 minutes We give you 45 minutes so that you’ll have enough time to write your answers in a file and submit it online Scope: Lectures 2, 3, 4, 5 Format: 2 short questions (with parts) Open book  /docProps/thumbnail.jpeg 程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts