Microsoft PowerPoint – 26_X86-64_Assembly_Language_Part_6
O
SU
C
SE
2
42
1
J.E.Jones
CSE 2421
Control (Loops)
O
SU
C
SE
2
42
1
J. E. Jones
Control: Condition codes (Review)
Conditional branches (Review)
Loops
Switch Statements
O
SU
C
SE
2
42
1
J. E. Jones
jX Instructions
◦ Jump to different part of code depending on condition codes
◦ This is only a partial list. A more inclusive one at:
http://unixwiz.net/techtips/x86-jumps.html
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)
O
SU
C
SE
2
42
1
J. E. Jones
cmovX Instructions
◦ Move a value (or not) depending on condition codes
◦ This is only a partial list. A move inclusive one at:
https://www.felixcloutier.com/x86/cmovcc
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)
O
SU
C
SE
2
42
1
J. E. Jones
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:
. . .
◦ Create separate code regions for then & else expressions
◦ Execute appropriate one
O
SU
C
SE
2
42
1
J. E. Jones
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
O
SU
C
SE
2
42
1
J. E. Jones
C code example with assembly
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 O SU C SE 2 42 1 J. E. Jones C Code val = Test ? Then_Expr : Else_Expr; goto Version result = Then_Expr; eval = Else_Expr; nt = !Test; if (nt) result = eval; return result; 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 O SU C SE 2 42 1 J. E. Jones 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
O
SU
C
SE
2
42
1
J. E. Jones
Expensive Computations
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 (no short circuit evaluation)
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;
O
SU
C
SE
2
42
1
J. E. Jones
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.
We can write the same loop
using do_while, while or for
loop constructs.
O
SU
C
SE
2
42
1
J. E. Jones
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;
}
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;
}
O
SU
C
SE
2
42
1
J. E. Jones
C Code goto Version
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
%rdx temp value
%rax result
O
SU
C
SE
2
42
1
J. E. Jones
C Code
do
Body
while (Test);
goto Version
loop:
Body
if (Test) goto loop
Body:
{
Statement1;
Statement2;
…
Statementn;
}
O
SU
C
SE
2
42
1
J. E. Jones
While version
while (Test)
Body
“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:
O
SU
C
SE
2
42
1
J. E. Jones
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;
}
Compare to do-while version of function
Initial goto starts loop at test
O
SU
C
SE
2
42
1
J. E. Jones
While version
while (Test)
Body
Do-While Version
if (!Test)
goto done;
do
Body
while(Test);
done:
“Do-while” conversion
goto Version
if (!Test) #if Test initially false
goto done;
loop:
Body
if (Test)
goto loop;
done:
O
SU
C
SE
2
42
1
J. E. Jones
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;
}
Compare to do-while version of function
Initial conditional guards entrance to loop
O
SU
C
SE
2
42
1
J. E. Jones
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;
}
O
SU
C
SE
2
42
1
J. E. Jones
for (Init; Test; Update )
Body
For Version
Init;
while (Test ) {
Body
Update;
}
While Version
O
SU
C
SE
2
42
1
J. E. Jones
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
O
SU
C
SE
2
42
1
J. E. Jones
C Code
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
O
SU
C
SE
2
42
1
J. E. Jones
Multiple case labels
◦ Here: 5 & 6
Fall through cases
◦ Here: 2
Missing cases
◦ Here: 4
long switch_eg
(long x, long y, long z)
{
long w = 1;
switch(x) {
case 1:
w = y*z;
break;
case 2:
w = y/z;
/* Fall Through */
case 3:
w += z;
break;
case 5:
case 6:
w -= z;
break;
default:
w = 2;
}
return w;
}
O
SU
C
SE
2
42
1
J. E. Jones
Code Block
0
Targ0:
Code Block
1
Targ1:
Code Block
2
Targ2:
Code Block
n–1
Targn-1:
•
•
•
Targ0
Targ1
Targ2
Targn-1
•
•
•
JTab:
goto *JTab[x];
switch(x) {
case val_0:
Block 0
case val_1:
Block 1
• • •
case val_n-1:
Block n–1
}
Sw_End:
Switch Form
Translation (Extended C)
Jump Table Jump Targets
O
SU
C
SE
2
42
1
J. E. Jones
Setup:
long switch_eg(long x, long y, long z)
{
long w = 1;
switch(x) {
. . .
}
return w;
}
switch_eg:
movq %rdx, %rcx
cmpq $6, %rdi # x:6
ja Sw_D
jmp *JTab(,%rdi,8)
What range of values
takes default?
Note that w not
initialized here
Register Use(s)
%rdi Argument x
%rsi Argument y
%rdx Argument z
%rax Return value
O
SU
C
SE
2
42
1
J. E. Jones
long switch_eg(long x, long y, long z)
{
long w = 1;
switch(x) {
. . .
}
return w;
}
Indirect
jump
Jump table
.section .rodata
.align 8
JTab:
.quad SW_D # x = 0
.quad C1 # x = 1
.quad C2 # x = 2
.quad C3 # x = 3
.quad SW_D # x = 4
.quad C5_6 # x = 5
.quad C5_6 # x = 6
Setup:
switch_eg:
movq %rdx, %rcx
cmpq $6, %rdi # x:6
ja SW_D # Use default
jmp *JTab(,%rdi,8) # goto *JTab[x]
O
SU
C
SE
2
42
1
J. E. Jones
Table Structure
◦ Each target requires 8 bytes
◦ Base address at JTab
Jumping
◦ Direct: jmp SW_D
◦ Jump target is denoted by label SW_D
◦ 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
Only for 0 ≤ x ≤ 6
Jump table
.section .rodata
.align 8
JTab:
.quad SW_D # x = 0
.quad C1 # x = 1
.quad C2 # x = 2
.quad C3 # x = 3
.quad SW_D # x = 4
.quad C5_6 # x = 5
.quad C5_6 # x = 6
O
SU
C
SE
2
42
1
J. E. Jones
.section .rodata
.align 8
.JTab:
.quad SW_D # x = 0
.quad C1 # x = 1
.quad C2 # x = 2
.quad C3 # x = 3
.quad SW_D # x = 4
.quad C5_6 # x = 5
.quad C5_6 # x = 6
Jump table
switch(x) {
case 1: /* Label C1 */
w = y*z;
break;
case 2: /* Label C2 */
w = y/z;
/* Fall Through */
case 3: /* Label C3*/
w += z;
break;
case 5:
case 6: /* Label C5_6 */
w -= z;
break;
default: /* Label SW_D */
w = 2;
}
O
SU
C
SE
2
42
1
J. E. Jones
C1:
movq %rsi, %rax # y
imulq %rdx, %rax # y*z
ret
switch(x) {
case 1: /* Label C1*/
w = y*z;
break;
. . .
}
Register Use(s)
%rdi Argument x
%rsi Argument y
%rdx Argument z
%rax Return value
O
SU
C
SE
2
42
1
J. E. Jones
long w = 1;
. . .
switch(x) {
. . .
case 2:
w = y/z;
/* Fall Through */
case 3:
w += z;
break;
. . .
}
case 3:
w = 1;
case 2:
w = y/z;
goto merge;
merge:
w += z;