PowerPoint Presentation – Introduction to Computer Systems 15-213/18-213
Machine language II
Copyright By PowCoder代写 加微信 powcoder
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