When in doubt, express intent, and leave the rest to the compiler

I sometimes get asked what stylistic choices a C developer could make that would help their code work well with static analysis or formal verification. I usually do not have a good answer—the reader of this blog or of the previous one may have categorized me as a detail-oriented person; when thus solicited, my first instinct is to look for concrete examples, but stylistic choices in programming are full of trade-offs. I might provide an answer such as “Some verification tools may have difficulties with goto, so you could try to avoid goto as much as possible. Of course, the analyzer I work on has no difficulties with goto, it is only that other techniques exist with which goto is an inconvenience. But of course if you are implementing error-handling in a C function that allocates resources, then you should use goto, because there is not really a better way, unless…” This is about the time I notice that whoever asked has gone get themselves another cocktail and a better discussion group to mingle with.

The general, non-detailed answer that I should give, and I am writing it down here for future reference, is that when in doubt, the developer should choose to express clearly the intent of their program.

Imagine that, while reviewing foreign code, you arrive to the snippet below, except that instead of being isolated inside a function, it is three lines of code within another hundred that you are trying to make sense of.

void * f2(int c, void * p1, void * p2) {
  void * r = p1;
  uintptr_t mask = -c;
  r = (void*)(((uintptr_t)r & mask) | ((uintptr_t)p2 & ~mask));
  return r;
}

What does the above code do?

The answer is that it is nonsensical. It mixes some bits from a pointer p1 with bits from a pointer p2. Perhaps we can assume that p1 and p2 point to blocks that are aligned to the same large power of two in memory, and this code is simply copying the offset of p2 inside its own block to a similar offset within the block inside which p1 points? That would depend on the value of c. You look to the code above the snippet and painfully infer that c can contain only 0 or 1. At least that explains it: the code, for c containing 0 or 1, is intended to be equivalent to the one below:

void * f1(int c, void * p1, void * p2) {
  void * r = p1;
  if (!c) r = p2;
  return r;
}

The developer’s idea may be that the f2 version is faster, because it doesn’t contain any expensive conditional branch. Let us take a look:

$ clang -O3 -S -fomit-frame-pointer -fno-asynchronous-unwind-tables cmov.c
$ cat cmov.s
…
_f2:                                    ## @f2
## BB#0:
	negl	%edi
	movslq	%edi, %rax
	andq	%rax, %rsi
	notq	%rax
	andq	%rdx, %rax
	orq	%rsi, %rax
	retq

The compiled code for f2 is beautiful: a straight sequence of arithmetic instructions that modern processors can fetch and decode well in advance to sustain a rhythm of one instruction per cycle or more. But not much more in this case, as most instructions depend immediately on the result of the preceding instruction. At least the code doesn’t contain any conditional branches that might get mis-predicted and inflict a penalty of several tens of cycles.

What about f1?

_f1:                                    ## @f1
## BB#0:
	testl	%edi, %edi
	cmoveq	%rdx, %rsi
	movq	%rsi, %rax
	retq

Looking at the compiled code for f1, it does not contain any expensive conditional branch either! It uses the “conditional move” instruction. Just after a testl %edi, %edi instruction, the cmoveq %rdx, %rsi instruction has the same meaning as if (%edi == 0) %rsi = %rdx; would have in C, but the execution flow does not depend on %edi, allowing efficient fetching, decoding and execution at one instruction per cycle.

When producing IA-32 code, you might need a commandline option to tell the compiler to emit this instruction, as it does not exist in every IA-32 processor in history. The CMOV instruction was only introduced in the Pentium Pro processor, in 1995, and you might encounter a processor that does not support it if you are in some kind of computing museum. Say “hi!” to the Missile Command arcade game for me.

Here, my compiler is producing 64-bit code by default (x86-64), and every x86-64 processor has the CMOV instruction, so I do not even need to think about whether I want 20-year-old processors to execute f2 branchlessly. The dilemma is solved for me by such an x86-64 processor not exiting at all.

In the compilation of f2, the compiler needs to produce code that works for all values of c, because it has not been provided with the information that c contained only 0 or 1. If we do provide the compiler with that information, it can do a better job at compiling it to fast code:

void * f3(int c, void * p1, void * p2) {
  void * r = p1;
  c = !!c; // force c to be 0 or 1 only
  uintptr_t mask = -c;
  r = (void*)(((uintptr_t)r & mask) | ((uintptr_t)p2 & ~mask));
  return r;
}
$ clang -O3 -S -fomit-frame-pointer -fno-asynchronous-unwind-tables cmov.c
$ cat cmov.s
…
_f3:                                    ## @f3
## BB#0:
	testl	%edi, %edi
	cmoveq	%rdx, %rsi
	movq	%rsi, %rax
	retq

This is the same code as for f1! The pattern under discussion was actually common enough that the authors of Clang have had to invent an optimization to detect that the code implements a crude branchless conditional move and compile it to an efficient one. The optimization only works if the compiler can also infer that the variable c can only contain 0 or 1, though.