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
} 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