CS计算机代考程序代写 js assembly OSU CSE 2421

OSU CSE 2421
CSE 2421
Control (Loops)
J.E.Jones

OSU CSE 2421
 Control: Condition codes (Review)  Conditional branches (Review)
 Loops
 Switch Statements
J. E. Jones

OSU CSE 2421
 jX Instructions
◦ Jump to different part of code depending on condition codes
jX Condition
Description
jmp 1
je ZF
jne ~ZF
js SF
jns ~SF
jg ~(SF^OF)&~ZF jge ~(SF^OF)
jl (SF^OF)
jle (SF^OF)|ZF
ja ~CF&~ZF
jb CF
Unconditional
Equal / Zero
Not Equal / Not Zero Negative
Nonnegative
Greater (Signed)
Greater or Equal (Signed) Less (Signed)
Less or Equal (Signed) Above (unsigned)
Below (unsigned)
◦ This is only a partial list. A more inclusive one at: http://unixwiz.net/techtips/x86-jumps.html
J. E. Jones

OSU CSE 2421
 cmovX Instructions
◦ Move a value (or not) depending on condition codes
cmovX Condition
Description
cmove ZF
cmovne ~ZF
cmovs SF
cmovns ~SF
cmovg ~(SF^OF)&~ZF cmovge ~(SF^OF) cmovl (SF^OF) cmovle (SF^OF)|ZF cmova ~CF&~ZF cmovb CF
Equal / Zero
Not Equal / Not Zero Negative
Nonnegative
Greater (Signed)
Greater or Equal (Signed) Less (Signed)
Less or Equal (Signed) Above (unsigned)
Below (unsigned)
◦ This is only a partial list. A move inclusive one at: https://www.felixcloutier.com/x86/cmovcc
J. E. Jones

OSU CSE 2421
◦ Create separate code regions for then & else expressions ◦ Execute appropriate one
C Code
goto Version
if (Test) then {
val= Then_Expr;
ntest = !Test;
if (ntest) goto Else;
} else {
val= Else_Expr;
val = Then_Expr;
}
goto Done; Else:
val = Else_Expr; Done:
.. .
J. E. Jones

OSU CSE 2421
 C allows goto statement
 Jump to position designated by label
Now ntest is 0 or 1
long absdiff (long x, long y) long absdiff_j(long x, long y) {{
}
Done:
return result;
long result; if (x > y){
long result;
int ntest = (x <= y); if (ntest) goto Else; result = x-y; goto Done; result = x-y; } else { result = y-x; } return result; Else: } result = y-x; J. E. Jones OSU CSE 2421  C code example with assembly long absdiff (long x, long y) { absdiff: cmpq %rsi, %rdi jle reverse movq %rdi, %rax subq %rsi, %rax jmp Done # x:y x-y } Done: ret long result; if (x > y)
result = x-y;
else
reverse: # x <= y result = y-x; movq %rsi, %rax return result; subq %rdi, %rax Register Use(s) %rdi %rsi %rax Argument x Argument y Return value J. E. Jones OSU CSE 2421  Conditional Move Instructions ◦ Instruction supports: C Code val = Test ? Then_Expr : Else_Expr;  But only when known to be safe if (Test) DestSrc ◦ GCC tries to use them  Why? ◦ Branches are very disruptive to goto Version instruction flow through pipelines result = Then_Expr; eval = Else_Expr; ◦ Conditional moves do not require control transfer nt = !Test; if (nt) result = eval; return result; J. E. Jones OSU CSE 2421 long absdiff(long x, long y) { absdiff: long result; if (x > y){
movq
%rdi, %rax
# x
}
result = x-y;
movq
%rsi, %rdx
} else {
subq
%rdi, %rdx
# eval = y-x
result = y-x;
%rsi, %rdi
return result; }
subq
%rsi, %rax
# result = x-y
cmpq
cmovle %rdx, %rax ret
# x:y
# if <=, result = eval Register Use(s) %rdi %rsi %rax Argument x Argument y Return value J. E. Jones OSU CSE 2421 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 (no short circuit evaluation)  May have undesirable effects Computations with side effects val = x > 0 ? x *= 7 : x += 3;
 Both values get computed  Must be side-effect free
J. E. Jones

OSU CSE 2421
long find_min(long *x, long c) {
find_min:
decq %rsi
movq (%rdi,%rsi,8), %rax
# c-1
# x[c-1]
long min;
int i;
min = *x; for(i=1, i>= 1;
} while (x>0); return result;
#define WSIZE 8*sizeof(long) long pcount_for(unsigned long x) {
long pcount_while(unsigned long x) { long result = 0;
while (x>0) {
int i;
unsigned result = 0;
for (i = 0; i < WSIZE; i++) { result += x & 0x1; result += x & 0x1; x >>= 1; }
x >>= 1; }
return result; }
return result; }
J. E. Jones

OSU CSE 2421
 Count number of 1’s in argument x (“popcount”)
 Use conditional branch to either continue looping or to
}
exit loop
C Code
C Code goto Version
long pcount_do(unsigned long x) { long result = 0;
do {
long pcount_goto (unsigned long x) { long result = 0;
loop:
result += x & 0x1;
result += x & 0x1; x >>= 1;
if(x>0) goto loop; return result;
x >>= 1;
} while (x>0); return result;
}
J. E. Jones

OSU CSE 2421
}
C Code goto Version
long pcount_goto(unsigned long x) { long result = 0;
Register
Use(s)
loop:
%rdi %rdx %rax
Argument x temp value result
result += x & 0x1; x >>= 1;
if(x>0) goto loop; return result;
movq loop:
$0, %rax
# result = 0
# loop:
# t1 = x
# t1 = t1 & 0x1 # result += t1
movq
%rdi, %rdx
andq addq shrq jne ret
$1, %rdx %rdx, %rax $1, %rdi
# x >>= 1
loop
# if (x) goto loop # ret
J. E. Jones

OSU CSE 2421
 Body: C Code
goto Version loop:
do
Body
if (Test) goto loop
Body while (Test);
{ Statement1; Statement2;
}
… Statementn;
J. E. Jones

OSU CSE 2421
 “Jump-to-middle” translation
goto C Version
While version
loop:
while (Test) Body
Body
 Note that this is same as do_while goto version with blue lines added change it to a while loop.
goto test;
test:
if (Test) goto loop; done:
J. E. Jones

OSU CSE 2421
 Compare to do-while version of function  Initial goto starts loop at test
C Code
Jump to Middle Version
long pcount_while (unsigned long x) { long result = 0; while (x>0) {
long pcount_goto_jtm(unsigned long x) { long result = 0;
result += x & 0x1;
goto test; loop:
x >>= 1; }
result += x & 0x1;
return result; }
test:
x >>= 1;
if(x>0) goto loop;
return result; }
J. E. Jones

OSU CSE 2421
 “Do-while” conversion While version
while (Test) Body
Do-While Version
goto Version
if (!Test) goto done;
if (!Test) goto done;
#if Test initially false
do
loop:
Body
Body
if (Test)
while(Test); done:
goto loop; done:
J. E. Jones

OSU CSE 2421
 Compare to do-while version of function  Initial conditional guards entrance to loop
C Code
Do-While Version
long pcount_while(unsigned long x) { long result = 0;
while (x) {
long pcount_goto_dw(unsigned long x) { long result = 0;
if (!x) goto done;
}
done:
result += x & 0x1;
loop:
x >>= 1; }
result += x & 0x1; x >>= 1;
if(x>0) goto loop;
return result;
return result; }
J. E. Jones

OSU CSE 2421
General Form
for (Init; Test; Update ) Body
Init
#define WSIZE 8*sizeof(long) long pcount_for(unsigned long x) {
i < WSIZE int i; unsigned result = 0; for (i = 0; i < WSIZE; i++) { Update result += x & 0x1; { result += x & 0x1; x >>= 1; }
x >>= 1; }
return result; }
i=0
Test
i++
Body
J. E. Jones

OSU CSE 2421
For Version
for (Init; Test; Update ) Body
While Version
Init;
while (Test ) {
Body
Update; }
J. E. Jones

OSU CSE 2421
{
return result; }
}
Init
i=0
long pcount_for_while(unsigned long x) {
Test
size_t i;
long result = 0;
i = 0;
while (i < WSIZE) { i < WSIZE Update i++ result += x & 0x1; x >>= 1;
i++;
Body
}
result += x & 0x1;
x >>= 1;
J. E. Jones

OSU CSE 2421
}
goto loop; done:
 Initial test can be optimized away
goto Version
C Code
long pcount_for_goto_dw(unsigned long x) { size_t i;
long result = 0; Init
i = 0;
long pcount_for(unsigned long x) {
if (!(i < WSIZE)) goto done; !Test { { Body size_t i; long result = 0; for (i = 0; i < WSIZE; i++) loop: result += x & 0x1; result += x & 0x1; x >>= 1;
x >>= 1; }
}i++;
if (i < WSIZE) Test return result; Update return result; } J. E. Jones OSU CSE 2421  Multiple case labels ◦ Here:5&6 { long w = 1; switch(x) { case 1:  Fall through cases ◦ Here: 2 w = y*z;  Missing cases ◦ Here: 4 w = y/z; long switch_eg (long x, long y, long z) } J. E. Jones break; case 2: /* Fall Through */ case 3: w += z; break; case 5: case 6: w -= z; break; default: w = 2; } return w; OSU CSE 2421 Switch Form Jump Table Jump Targets switch(x) { case val_0: Targ0: 0 Block 0 case val_1: Targ1: Targ2: Code Block 1 Block 1 ••• • case val_n-1: • Block n–1 Targn-1 Sw_End: Code Block 2 } Translation (Extended C) goto *JTab[x]; • • • JTab: Targ0 Targ1 Targ2 • Code Block Targn-1: n–1 Code Block J. E. Jones OSU CSE 2421 long switch_eg(long x, long y, long z) { long w = 1; switch(x) { .. . } return w; } Setup: switch_eg: movq %rdx, %rcx cmpq $6, %rdi # x:6 ja Sw_D jmp *JTab(,%rdi,8) Register Use(s) What range of values takes default? Note that w not initialized here J. E. Jones %rdi Argument x %rsi Argument y %rdx Argument z %rax Return value OSU CSE 2421 long switch_eg(long x, long y, long z) { long w = 1; switch(x) { Jump table .. . } .section .align 8 .rodata return w; } JTab: .quad SW_D #x=0 C1 #x=1 C2 #x=2 C3 #x=3 SW_D #x=4 C5_6 #x=5 C5_6 #x=6 Setup: .quad .quad switch_eg: .quad movq %rdx, %rcx cmpq $6, %rdi # x:6 ja SW_D # Use default Indirect jmp *JTab(,%rdi,8) # goto *JTab[x] jump .quad .quad .quad J. E. Jones OSU CSE 2421  Table Structure ◦ Each target requires 8 bytes ◦ Base address at JTab Jump table  Jumping ◦ Direct: jmp SW_D ◦ Jump target is denoted by label SW_D JTab: .quad SW_D #x=0 C1 #x=1 C2 #x=2 C3 #x=3 SW_D #x=4 C5_6 #x=5 C5_6 #x=6 ◦ Indirect: jmp *JTab(,%rdi,8) ◦ Start of jump table: JTab ◦ Must scale by factor of 8 (addresses are 8 bytes) ◦ Fetch target from effective Address JTab + x*8 Onlyfor 0≤x≤6 .section .align 8 .rodata .quad .quad .quad .quad .quad .quad J. E. Jones OSU CSE 2421 Jump table switch(x) { case 1: .section .align 8 .rodata /* Label C1 */ .JTab: .quad SW_D #x=0 C1 #x=1 C2 #x=2 C3 #x=3 SW_D #x=4 C5_6 #x=5 C5_6 #x=6 break; case 2: .quad .quad .quad .quad .quad .quad /* Label C2 */ /* Fall Through */ w = y*z; w = y/z; case 3: w += z; /* Label C3*/ break; case 5: case 6: w -= z; /* Label C5_6 */ /* Label SW_D */ break; default: w = 2; } J. E. Jones OSU CSE 2421 } switch(x) { case 1: /* Label C1*/ C1: movq w = y*z; %rsi, %rax # y %rdx, %rax # y*z break; .. . imulq ret Register Use(s) %rdi Argument x %rsi Argument y %rdx Argument z %rax Return value J. E. Jones OSU CSE 2421 long w = 1; .. . switch(x) { . .. case 2: w = y/z; case 2: w = y/z; goto merge; /* Fall Through */ case 3: w += z; break; case 3: w = 1; .. . } merge: w += z; J. E. Jones