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) DestSrc
◦ 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
} 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