PowerPoint PresentationIntroduction to Computer Systems 15-213/18-213
Machine language II
Copyright By Assignmentchef assignmentchef
Acknowledgement: These slides are based on the textbook
(Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers Perspective, Third Edition
Control: Condition codes
Conditional branches
Switch Statements
Bryant and OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 twos-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 OHallaron, Computer Systems: A Programmers 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 twos-complement (signed) overflow(a>0 && b<0 && (a-b)<0) || (a<0 && b>0 && (a-b)>0)
Bryant and OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers Perspective, Third Edition
Control: Condition codes
Conditional branches
Switch Statements
Bryant and OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers Perspective, Third Edition
Control: Condition codes
Conditional branches
Switch Statements
Bryant and OHallaron, Computer Systems: A Programmers 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 1s in argument x
Use conditional branch to either
continue looping or exit loop
Bryant and OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers Perspective, Third Edition
while (Test);
Goto Version
General Do-While Translation
Statement1;
Statement2;
Statementn;
Bryant and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
While version
while (Test)
General While Translation #1
Jump-to-middle translation
Used with Version
goto test;
goto loop;
Bryant and OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers Perspective, Third Edition
For Loop While Loop
for (Init; Test; Update )
For Version
while (Test ) {
While Version
Bryant and OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers Perspective, Third EditionControl: Condition codesConditional branchesSwitch StatementsBryant and OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers Perspective, Third Edition Handling Fall-Throughlong w = 1;switch(x) {/* Fall Through */ goto merge;Bryant and OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers 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 OHallaron, Computer Systems: A Programmers Perspective, Third Edition Control: Condition codesConditional branches & conditional movesSwitch statementsBryant and OHallaron, Computer Systems: A Programmers 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 youll 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]
Reviews
There are no reviews yet.