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

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).

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