CODEWITHSUNDEEP
cbooleancompiler-optimizationboolean-logic
ndbroadbent
ndbroadbent

Reputation: 13803

Why doesn't the C99 compiler optimize "!a && b" as "a < b" for booleans?

I saw this really interesting tweet:

resisting my code golf instinct to turn if(!bool1 && bool2) into if(bool1<bool2)

I had never seen that before, so I wanted to see if compilers would also use this optimization. I started a repo with a README and a test C program: https://github.com/ndbroadbent/gcc_experiments

Here is the test program:

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

int main(int argc, const char* argv[]) {
  if(argc != 3) {
    printf("Usage: %s <a> <b>\n", argv[0]);
    exit(1);
  }
  bool a = strtol(argv[1], NULL, 10) != 0;
  bool b = strtol(argv[2], NULL, 10) != 0;

  if (!a && b) {
    printf("!a && b == true (a: %d, b: %d)\n", a, b);
  } else {
    printf("!a && b == false (a: %d, b: %d)\n", a, b);
  }
}

I tried compiling this program with both the gnu90 and C99 standards. I know C99 has a bool type, but is that still treated like an integer, so the compiler can't make any optimizations based on boolean logic?

I might be reading the assembly wrong, but it looks like C99 with -O3 is also including jne and je instructions, instead of just using one "less than" operation and a single jump instruction. It looks like C++ doesn't make this optimization either.

Upvotes: 3

Views: 154

Answers (1)

n. m. could be an AI
n. m. could be an AI

Reputation: 119877

Compilers are well aware of the eqivalence and are able to optimise based on it. Their idea of what should be optimised to what might be opposite from yours though.

For sake of completeness, here's the clang-produced assembly output of a function that does !a && b and also of a function that does “a < b”. It's the same assembly output in both cases.

    mov     eax, edi
    not     al
    and     al, sil
    ret

Upvotes: 7

Related Questions