Implementing Conditional Branches with Conditional Control
The General Form of If-Else Statement
In C
if (test-expr)
then-statment
else
else-statement
The assembly sometimes adheres to the following form.
t = test-expr
if (!t)
goto false;
then-statment
goto done
false:
else-statement
done:
Example
long lt_cnt = 0;
long ge_cnt = 0;
long absdiff_se(long x, long y) { //absdiff() with side effect
long result;
if (x < y) {
lt_cnt++;
result = y - x;
}
else {
ge_cnt++;
result = x - y;
}
return result;
}
Assembly XXX
long absdiff_se(long x, long y)
Note: x in %rdi, y in %rsi
absdiff_se:
cmpq %rsi, %rdi // compare x and y
jge .L2 // If y >= x goto L2
addq $1, lt_cnt(%rip) // lt_cnt++ - %rip is PC
// (p 705) lt_cnt is replaced by offset
// from global var to cur instr in %rip
movq %rsi, %rax // copy y into rax
subq %rdi, %rax // store y - x in rax
ret // return with result in rax
.L2:
addq $1,ge_cnt(%rip) // ge_cnt++
movq %rdi, %rax // copy x into rax
subq %rsi, %rax // store x - y in rax
ret // return with result in rax
Implementing Conditional Branches with Conditional Moves
The conventional way to handle conditonal operations is to transfer control under certain conditions. An alternative is through a conditional transfer of data.
This strategy computes both outcomes of a conditional operation and then selects the one based on whether or not a condition holds. This approach is only used in certain situations.
C code
long absdiff(long x, long y){
long result;
if (x < y)
result = y - x;
else
result = x - y;
return result;
}
C code that mimics the assembly code generated from absdiff()
long cmovediff(long x, long y){
long rval = y - x;
long eval = x - y;
long ntest = x >= y;
/* The if-block below require a single instruction */
if (ntest)
rval = eval;
return rval;
}
Assembly code generated by GCC for absdiff(long x, long y)
Note: x in %rdi, y on %rsi
absdiff:
movq %rsi, %rax
subq %rdi, %rax // rval = y -x
movq %rdi, %rdx
subq %rsi, %rdx // eval = x - y
cmpq %rsi, %rdi // compare y:x
cmovge %rdx, %rax // if x >= y, rval = eval
ret // return rval
Why do compiler use conditional move?
CPUs achieve high performance through pipelining where an instruction is processed through a series of stages
- fetch the instruction from memory
- update program counter
- determine the instruction type
- read data from memory
- perform arithmetic operation
- write to memory
High performance is achieved by overlapping the execution of multiple instructions. This can only be done if the CPU can predict the next few instructions.
When the machine encounters a conditional jump it cannot determine with certainty which way the execution will go until it has evaluated the branch condition.
X86_64 Conditional Move Instructions
| Instruction | Synonmy | Move Condition | Description | |
| cmove | S, R | cmovz | ZF | Equal/zero |
| cmovne | S,R | cmovnz | ~ZF | Not equal/not zero |
| cmovs | S,R | SF | Negative | |
| cmovns | S,R | ~SF | Nonnegative |
- Similar to SET and JUMP instructions
- Instructions assume some previous instruction set the condition code flags.
- S must be a memory address or a register
- R must be a register
- S and R may be 16, 32 or 64 bits long.
- Single byte conditional moves are not supported
Not all conditional expressions can be compiled using conditional moves. Take the absdiff_se() method. If we evaluate both branches, both global variables will be incremented. This would be an unintended side effect.
General form
v = test-expr ? then-expr : else-expr;
The standard way to evaluate
if (!test-expr)
goto false;
v = then-expr
goto done;
false:
v = else-expr;
done:
Evaluate with conditional moves
v = then-expr;
ve = else-expr;
t = test-expr
if (!t)
v = ve;
Switch Statements
A switch statement provides a multi-way branching capability based on the value of an integer index.
They are sometimes implemented using an array, referred to as a jumptable, where entry i is the address of code segment that should be executed when the switch index equals i. The code performs an array reference into the jump table to determine the address to jump to.
Switch implementations are faster than a string of if-else blocks.
GCC determines whether or not to use a jumptable based on
- the number of cases
- the sparcity of the case values
In particular GCC will use a jumptable if there are 4 or more cases and a small range in values.
C Example
void switch_eg(long x, long n, long *dest){
long val = x;
switch (n) {
case 100: // index = (n - 100) = (100 - 100) = 0
val *= 13;
break;
case 102: // index = (n - 100) = (102 - 100) = 2
val += 10;
case 103: // index = (n - 100) = (103 - 100) = 3
val += 11;
break;
case 104: // index = (n - 100) = (104 - 100) = 4
case 106: // index = (n - 100) = (106 - 100) = 6
val *= val;
break;
default: // index ??
val = 0;
}
*dest = val;
}
Assembly Code
Note: x in %rdi, n in %rsi, dest in %rdx
switch_eg:
subq $100, %rsi // compute index = (n - 100)
cmpq $6, %rsi // compare 6:index
ja .L8 // if index above 6 (unsigned >)
jmp *.L4(,%rsi,8) // * signifies indirect jump
// jump to *jg[index]
.L3:
leaq (%rdi,%rdi,2), %rax // load effective address
// store in %rax = x + 2x = 3x
leaq (%rdi,%rax,4), %rdi // val = x + (4*3x) = x + 12x = 13x
jmp .L2
.L5:
addq $10, %rdi // val = 10 + x
.L6:
addq $11, %rdi // val = val + 11
jmp .L2
.L7:
imulq %rdi, %rdi // val = x * x
jmp .L2
.L8: // undefined case
movl $0, %edi // val = 0;
.L2:
movq %rdi, (%rdx) // *dest = val
ret
The jumptable is indicated in the assembly code by the following declarations
.section .rodata .align 8 .L4: .quad .L3 // index 0 case 100: .quad .L8 // index 1 case 101: - undefined case .quad .L5 // index 2 case 102: .quad .L6 // index 3 case 103: .quad .L7 // index 4 case 104: .quad .L8 // index 5 case 105: - undefined case .quad .L7 // index 6 case 106
© 2017 – 2018, Eric. All rights reserved.