Is there a way to convert a conditional assignment to branch free code?

Question

Is there a way to convert the following C code to something without any conditional statements? I have profiled some of my code and noticed that it is getting many branch misses on an if statement that is very similar to this one.

int cond = /*...*/;
int a = /*...*/;
int b = /*...*/;

int x;
if (cond) {
   x = a;
} else {
   x = b;
}

Chumash

Do you use a and b after this fragment? I assume you do use x after this too. – Queasy

@JonathanLeffler: no, I don't use a and b after this fragment. – Chumash

If you don't use a or b after this fragment, then you don't need to calculate both unless there are side-effects in their calculation. – Queasy

@Cornstalks: Hmm, maybe I should try massaging my code a bit to see if the compiler can optimize it by itself then. I was thinking that perhaps there was some bit-fiddling trick I could use that wouldn't require me dropping down to assembly language. – Chumash

Presumably the compiler thinks that it is better to avoid the computation of whichever of a and b is unneeded, even at the cost of a branch misprediction. And who knows? Maybe it's right. – Haletta

The above presumed that you told the compiler which architecture to compile for, that the architecture has conditional move opcodes, and that you have requested optimisation. If all of those are true, the compiler should emit conditional move instructions unless it has a good reason not to. – Haletta

Answer 1

It depends on the instruction set you're targeting. For x86, there's cmov. For arm64, there's csel. For armv7, there's mov with an optional conditional op-code.

Any decent compiler should be able to optimize that code you have into the most optimal set of instructions. GCC and clang do that (try it out yourself at https://gcc.godbolt.org/).

To answer your question more directly: there is no way to force this in straight C, since it's possible the CPU instruction set doesn't have a branch-free instruction that can be used as a substitute. So you either have to rely on your compiler (which is probably a good idea), or hand-write your own assembly.

To give you a little example, consider the following C code:

int min(int a, int b) {
  int result;
  if (a < b) {
    result = a;
  } else {
    result = b;
  }
  return result;
}

gcc 5.4.1 for armv7 generates:

min(int, int):
        cmp     r0, r1
        movge   r0, r1
        bx      lr

gcc 5.4 for arm64 generates:

min(int, int):
        cmp     w0, w1
        csel    w0, w0, w1, le
        ret

clang 4.0 for x86 generates:

min(int, int):                               # @min(int, int)
        cmp     edi, esi
        cmovle  esi, edi
        mov     eax, esi
        ret

gcc 5 for x86 generates:

min(int, int):
        cmp     edi, esi
        mov     eax, esi
        cmovle  eax, edi
        ret

icc 17 for x86 generates:

min(int, int):
        cmp       edi, esi                                      #8.10
        cmovl     esi, edi                                      #8.10
        mov       eax, esi                                      #8.10
        ret                                                     #8.10

As you can see, they're all branch-free (when compiled at -O1 or above).

Tamikotamil

Thanks. The problem must be with something extra about my original code that is confusing the compiler... I guess I'll have to take a more careful look at it. – Chumash

Answer 2

A more complete example would be more helpful as the way the variables x, a, b and cond are accessed can play a role. If they are global variables declared outside the function that performs the conditional assignment then they will be accessed using loads and stores, which the compiler may deem to be too expensive to execute conditionally. Look at the examples at https://godbolt.org/g/GEZbuf where the same conditional assignment is performed on globals and in foo and on local arguments in foo2

Deadman

Answer 3

x = (!cond * b) | (!!cond * a);

Cernuous