程序代写代做代考 js assembly Introduction to Computer Systems 15-213/18-243, spring 2009

Introduction to Computer Systems 15-213/18-243, spring 2009

CSE 2421
X86-64 Assembly Language Part 3: Control (Loops)

Today
Control: Condition codes (Review)
Conditional branches (Review)
Loops
Example program with loop

Jumping
jX Instructions
Jump to different part of code depending on condition codes

This is only a partial list
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)

Conditional Moves
cmovX Instructions
Move a value (or not) depending on condition codes
cmovX Condition Description
cmove ZF Equal / Zero
cmovne ~ZF Not Equal / Not Zero
cmovs SF Negative
cmovns ~SF Nonnegative
cmovg ~(SF^OF)&~ZF Greater (Signed)
cmovge ~(SF^OF) Greater or Equal (Signed)
cmovl (SF^OF) Less (Signed)
cmovle (SF^OF)|ZF Less or Equal (Signed)
cmova ~CF&~ZF Above (unsigned)
cmovb CF Below (unsigned)

C Code
if (Test) then {
val= Then_Expr;
} else {
val= Else_Expr;
}
goto Version
ntest = !Test;
if (ntest) goto Else;
val = Then_Expr;
goto Done;
Else:
val = Else_Expr;
Done:
. . .
General Conditional Expression Translation (Using Branches)
Create separate code regions for then & else expressions
Execute appropriate one

Using C language w/goto
C allows goto statement
Jump to position designated by label

long absdiff (long x, long y)
{
long result;
if (x > y){
result = x-y;
} else {
result = y-x;
}
return result;
}
long absdiff_j(long x, long y)
{
long result;
int ntest = (x <= y); if (ntest) goto Else; result = x-y; goto Done; Else: result = y-x; Done: return result; } Now ntest is 0 or 1 Conditional Branch Example C code example with assembly (stack instructions omitted) long absdiff (long x, long y) { long result; if (x > y)
result = x-y;
else
result = y-x;
return result;
}
absdiff:
cmpq %rsi, %rdi # x:y x-y
jle reverse
movq %rdi, %rax
subq %rsi, %rax
jmp Done
reverse: # x <= y movq %rsi, %rax subq %rdi, %rax Done: ret Register Use(s) %rdi Argument x %rsi Argument y %rax Return value C Code 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 Why? Branches are very disruptive to instruction flow through pipelines Conditional moves do not require control transfer Conditional Move Example absdiff: 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 ret long absdiff(long x, long y) { long result; if (x > y){
result = x-y;
} else {
result = y-x;
}
return result;
}
Register Use(s)
%rdi Argument x
%rsi Argument y
%rax Return value

Conditional Move Example #2
find_min:
decq %rsi # c-1
movq (%rdi,%rsi,8), %rax # x[c-1]
minloop:
decq %rsi #c-1
jl return_min
movq (%rdi,%rsi,8), %rcx
cmpq %rax, %rcx #newmin-currmin
cmovl %rcx, %rax # if negative replace
jmp minloop
return_min:
ret
long find_min(long *x, long c)
{
long min;
int i;
min = *x;
for(i=1, i>= 1;
} while (x>0);
return result;
}
long pcount_while(unsigned long x) {
long result = 0;
while (x>0) {
result += x & 0x1;
x >>= 1;
}
return result;
}
#define WSIZE 8*sizeof(long)
long pcount_for(unsigned long x)
{
int i;
unsigned result = 0;
for (i = 0; i < WSIZE; i++) { result += x & 0x1; x >>= 1;
}
return result;
}
We can write the same loop using do_while, while or for loop constructs.

C Code
C Code goto Version
long pcount_goto (unsigned long x) {
long result = 0;
loop:
result += x & 0x1;
x >>= 1;
if(x>0) goto loop;
return result;
}
“Do-While” Loop Example
Count number of 1’s in argument x (“popcount”)
Use conditional branch to either continue looping or to exit loop
long pcount_do(unsigned long x) {
long result = 0;
do {
result += x & 0x1;
x >>= 1;
} while (x>0);
return result;
}

C Code goto Version
“Do-While” Loop Compilation
movq $0, %rax # result = 0
loop: # loop:
movq %rdi, %rdx # t1 = x
andq $1, %rdx # t1 = t1 & 0x1
addq %rdx, %rax # result += t1
shrq $1, %rdi # x >>= 1
jne loop # if (x) goto loop
ret # ret
long pcount_goto(unsigned long x) {
long result = 0;
loop:
result += x & 0x1;
x >>= 1;
if(x>0) goto loop;
return result;
}
Register Use(s)
%rdi Argument x
%rax result

C Code
do
Body
while (Test);
goto Version
loop:
Body
if (Test) goto loop
General “Do-While” Translation
Body:

{
Statement1;
Statement2;

Statementn;
}

While version
while (Test)
Body
General “While” Translation #1
“Jump-to-middle” translation

Note that this is same as do_while goto version with blue lines added change it to a while loop.

goto C Version
goto test;
loop:
Body
test:
if (Test) goto loop;
done:

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

While version
while (Test)
Body
Do-While Version
if (!Test)
goto done;
do
Body
while(Test);
done:
General “While” Translation #2
“Do-while” conversion

goto Version
if (!Test) #if Test initially false
goto done;
loop:
Body
if (Test)
goto loop;
done:

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

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

i = 0
i < WSIZE i++ { result += x & 0x1; x >>= 1;
}
Init

Test

Update

Body

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

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

Init;
while (Test ) {
Body
Update;
}
While Version

For-While Conversion
long pcount_for_while(unsigned long x)
{
size_t i;
long result = 0;
i = 0;
while (i < WSIZE) { result += x & 0x1; x >>= 1;
i++;
}
return result;
}
i = 0
i < WSIZE i++ { result += x & 0x1; x >>= 1;
}
Init

Test

Update
Body

C Code
“For” Loop “Do-While” Conversion
Initial test can be optimized away
long pcount_for(unsigned long x)
{
size_t i;
long result = 0;
for (i = 0; i < WSIZE; i++) { result += x & 0x1; x >>= 1;
}
return result;
}
goto Version
long pcount_for_goto_dw(unsigned long x) {
size_t i;
long result = 0;
i = 0;
if (!(i < WSIZE)) goto done; loop: { result += x & 0x1; x >>= 1;
}
i++;
if (i < WSIZE) goto loop; done: return result; } Init !Test Body Update Test Example program See calc-sum.pdf on Carmen in Class slides PartB Program with main, function to calculate and print sum of elements of int (Intel long) array