[SOLVED] CS代考 PowerPoint Presentation – Introduction to Computer Systems 15-213/18-213

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

Machine language II

Copyright By PowCoder代写加微信 assignmentchef

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)SFSign Flag (for signed)
ZF Zero FlagOFOverflow 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 < 0Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Reading Condition CodesSetX InstructionsSet low-order byte of destination to 0 or 1 based on combinations of condition codesDoes not alter remaining 7 bytesSetXConditionDescriptionseteZFEqual / Zerosetne~ZFNot Equal / Not ZerosetsSFNegativesetns~SFNonnegativesetg~(SF^OF)&~ZFGreater (Signed)setge~(SF^OF)Greater or Equal (Signed)setl(SF^OF)Less (Signed)setle(SF^OF)|ZFLess or Equal (Signed)seta~CF&~ZFAbove (unsigned)setbCFBelow (unsigned)Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Editionx86-64 Integer RegistersInteger registers(64-bit)%rax, %rbx, %rcx, %rdx, %rsi, %rdi, %rbp, %rsp%r8, %r9, %r10, %r11, %r12, %r13, %r14, %r15The 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 suffixb: 1 byte,w: 2 bytes, l: 4 bytes, q: 8 bytesExample: movb, movw, movl, movqBryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition cmpq %rsi, %rdi # Compare x:ysetg %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;
RegisterUse(s)
%rdiArgument x
%rsiArgument y
%raxReturn 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
jXConditionDescription
jmp1Unconditional
jeZFEqual / Zero
jne~ZFNot Equal / Not Zero
jsSFNegative
jns~SFNonnegative
jg~(SF^OF)&~ZFGreater (Signed)
jge~(SF^OF)Greater or Equal (Signed)
jl(SF^OF)Less (Signed)
jle(SF^OF)|ZFLess or Equal (Signed)
ja~CF&~ZFAbove (unsigned)
jbCFBelow (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, %raxGenerationgcc –Og -S –fno-if-conversion control.cRegisterUse(s)%rdiArgument x%rsiArgument y%raxReturn valueBryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Expressing with Goto Codelong 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 Versionntest = !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 expressionsExecute appropriate oneval = 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 = evallong absdiff(long x, long y)long result;if (x > y)
result = x-y;
result = y-x;
return result;
RegisterUse(s)
%rdiArgument x
%rsiArgument y
%raxReturn 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;
RegisterUse(s)
%rdiArgument x
%raxresult

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 EditionControl: Condition codesConditional branchesSwitch StatementsBryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Switch Statement ExampleMultiple case labelsHere: 5 & 6Fall through casesMissing caseslong 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 StructureCode BlockCode BlockCode BlockCode Blockgoto *JTab[x];switch(x) {case val_0:case val_1:case val_n-1:Switch FormTranslation (Extended C)Jump TableJump TargetsBryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Switch Statement Examplelong switch_eg(long x, long y, long z)long w = 1;switch(x) {switch_eg:movq%rdx, %rcxcmpq$6, %rdi # x:6ja.L8jmp *.L4(,%rdi,8)What range of values takes default?Note that w not initialized hereRegisterUse(s)%rdiArgument x%rsiArgument y%rdxArgument z%raxReturn valueBryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Switch Statement Examplelong 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 = 6switch_eg:movq%rdx, %rcxcmpq$6, %rdi# x:6ja.L8 # Use defaultjmp *.L4(,%rdi,8) # goto *JTab[x]Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Assembly Setup ExplanationTable StructureEach target requires 8 bytesBase address at .L4Direct: jmp .L8Jump target is denoted by label .L8Indirect: jmp *.L4(,%rdi,8)Start of jump table: .L4Must scale by factor of 8 (addresses are 8 bytes)Fetch target from effective Address .L4 + x*8Only for0 ≤ x ≤ 6Jump 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 = 6Bryant 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 TableJump tableswitch(x) {case 1:// .L3case 2:// .L5/* Fall Through */case 3:// .L9case 6:// .L7default: // .L8Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Code Blocks (x == 1) movq%rsi, %rax# y imulq %rdx, %rax# y*zswitch(x) {case 1:// .L3RegisterUse(s)%rdiArgument x%rsiArgument y%rdxArgument z%raxReturn valueBryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Handling Fall-Throughlong 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 += zlong w = 1;switch(x) {/* Fall Through */RegisterUse(s)%rdiArgument x%rsiArgument y%rdxArgument z%raxReturn valueBryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Code Blocks (x == 5, x == 6, default).L7: # Case 5,6movl$1, %eax #w = 1subq%rdx, %rax #w -= z.L8: # Default:movl$2, %eax #2switch(x) {case 5:// .L7case 6:// .L7default: // .L8RegisterUse(s)%rdiArgument x%rsiArgument y%rdxArgument z%raxReturn valueBryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Summarizingif-then-elsewhile, forAssembler ControlConditional jumpConditional moveIndirect jump (via jump tables)Compiler generates code sequence to implement more complex controlStandard TechniquesLoops converted to do-while or jump-to-middle formLarge switch statements use jump tablesSparse switch statements may use decision trees (if-elseif-elseif-else)Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Control: Condition codesConditional branches & conditional movesSwitch statementsBryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third EditionOnline Quiz 1Date/Time: 24 Feb (Thursday), 12:30-13:20These questions can be answered within 30 minutesWe give you 45 minutes so that you’ll have enough time to write your answers in a file and submit it onlineScope:Lectures 2, 3, 4, 5Format: 2 short questions (with parts)Open book /docProps/thumbnail.jpeg程序代写 CS代考加微信: assignmentchef QQ: 1823890830 Email: [email protected]