How are booleans "notted" in assembly?

Question

I understand that in C-like languages I can perform a boolean not with the not operator: (C)

int myBool = TRUE;
myBool = !myBool;

But my question is: How is this implemented behind the scenes? My guess is by using jumps, but those could be inefficient if used excessively: (Intel x86 syntax)

; assume eax holds boolean
  test eax, eax
  jnz short boolTrue
  inc eax ; eax was 0, now 1
  jmp short after
boolTrue: ; eax non-zero
  xor eax, eax ; eax now 0
after:

As shown, it requires 5 instructions with at least one jump and one bit-wise and (test). There has to be an easier way to do this because I've seen code bases that do "double-nots" (if (!!fileHandle)) for some weird reason.

So (as said above): How do compilers do boolean !s on x86?

Answer 1

You can do it with SETZ (set (if) zero (flag is set)) which require no branches.

Answer 2

There's a possibility of using carry and branchless sequences:

sub %eax, 1        ;; this produces carry only when %eax EQ zero
sbb %eax, %eax     ;; 0 when not carry, -1 when carry
and %eax, 1        ;; just get the least significant bit (also neg %eax will do)

for eax=!eax and

sub %eax, 1        ;; 
sbb %eax, %eax     
add %eax, 1        ;; [-1, 0] + 1 == [0, 1]

for eax = !!eax.

I couldn't figure out if there are 3 instruction (or less) sequences using common arithmetic operations that wouldn't waste the original variable (or register eax).

Answer 3

In a good compiler, the method for implementing an operator such as NOT will generally not be limited to just one code generation pattern. The compiler will take into account many factors of surrounding context, such as compile time optimizations, source and/or generated code immediately preceding the NOT operator, whether the NOT operator is used in a conditional context (e.g. used in an if-statement) or a value context (used in an assignment).

When used in an if-statement, a NOT operator is more likely to be implemented using a branch, since an if-statement most likely need to branch anyway. When used in a value context, a NOT operator is more likely to be implemented with an compare and capture of the result (without a branch).

When a NOT operator is used in a larger expression, often a nested operator can be reversed, so to one way of looking at it, the NOT operator generates no code at all; this may happen in expressions like a = ! (b > 0) or if ( ! ( a && b ) ). Even with if ( !a ), you'll probably find a isn't actually being NOT'ed, but simply being tested as in if ( a ), though with branch condition reversed.

In the specific example you give, I'd expect a good compiler's best effort (generating code for production and not for debugging), that it would determine at compile time that the constant 0 instead of myBool should be passed to printf.

In short, a decent compiler has many techniques available and many criteria for determining which to use.

Answer 4

If you have a proper boolean, you can use XOR to toggle between the two representations. Note that C doesn't have a bool, it just interprets zero as false and anything else as true. C++ and C# both have proper booleans, as such they don't need to mess with the non-zero check and indeed at least g++ does use the XOR method.