4

if( !A && !B ) seems like it should compile to

mov    eax, dword ptr[esp + A_offset]
test   eax, dword ptr[esp + B_offset]
jne    ~~~~~~~~~~

The compiler actually generates

mov    eax, dword ptr[esp + A_offset]
test   eax, eax
jne    ~~~~~~~~~~
mov    eax, dword ptr[esp + B_offset]
test   eax, eax
jne    ~~~~~~~~~~

See dump here

8B 45 F8             mov         eax,dword ptr [b]  
83 7D FC 00          cmp         dword ptr [a],0  
75 04                jne         main+32h (0A71072h)  
85 C0                test        eax,eax  
75 00                jne         main+32h (0A71072h)

Why doesn't it use a single TEST instruction to save branches and instructions?

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
Jun Ryung Ju
  • 61
  • 4
  • 2
    What if A=1 and B=2? Then test would give the wrong answer. – Marc Glisse Sep 01 '16 at 08:35
  • 1
    @Yuval This is not a duplicate (at least not of that particular question). The issue here is about `(a!=0)&(b!=0` vs `(a&b)!=0`, not lazy evaluation. – Marc Glisse Sep 01 '16 at 08:56
  • @MarcGlisse The question says `&&`, not `&`. – molbdnilo Sep 01 '16 at 08:58
  • @molbdnilo yes, but that's a secondary concern only. – Marc Glisse Sep 01 '16 at 08:58
  • 3
    `if( !A && !B )` is true only when `A` and `B` are both zero (= `if (!(A || B))`). So if you are "code golfing", this can be done as `mov eax,[A]` `or eax,[B]` `jnz not_true`. Compiler is using more instructions, but decouples direct dependency between A and B, the particular non-zero test can be done in any order, whichever value arrives from memory first (if the "B" branch is run speculatively out-of-order as a prediction - I have no idea if CPUs are that advanced in reordering). In case both A and B are local variables in the same scope, I would bet $0.01 my version is optimal. ;) – Ped7g Sep 01 '16 at 09:23
  • It seems like it would be useful for CPUs to implement logical-AND and logical-OR two-input instructions, that set ZF according to `A && B` or `A || B` (and also produce a bool in the dst operand so you can chain this or use the bool directly). It would be easy to implement in hardware; simpler than an adder. x86's opcode space is very crowded, but I'm surprised that no other ISAs implement something like this (to my knowledge. Do you know of any, @Marc?) It's probably often easier to predict one branch on the combined condition than two separate branches on multiple conditions. – Peter Cordes Sep 01 '16 at 09:31
  • 1
    @PeterCordes for example i8051 and clones have bit data type and bit-oriented instructions. However, the number of bit variables is hardware limited to 256. From my experience they would better implement some useful math instead. May be the lack of usefulness is a reason of dropping bit-oriented instructions in bigger CPUs – Serge Sep 01 '16 at 10:04
  • 2
    gcc already turns `!a&&!b` into `!(a|b)` when it knows that b is safe to read. Peter, the closest I can think of are 1) reduction operation on simd vectors and 2) predicated operations (set it so the operation b!=0 is only executed if a!=0 returned true). But I don't know that many instruction sets... – Marc Glisse Sep 01 '16 at 10:07
  • @MarcGlisse: Oh right, hardware `A||B` isn't really needed: `OR r32, r/m32` already does that and sets ZF accordingly. Having a separate instruction just to produce a 0-or-1 output is a minor waste when `setz r/m8` exists. Logical-AND is the only hard one. Good point about predicated instructions, like ARM can do. – Peter Cordes Sep 01 '16 at 10:13

2 Answers2

2

No. The test instruction performs bitwise AND of the operands and set flags according to the result, see https://en.wikipedia.org/wiki/TEST_(x86_instruction).

So the code generated by compiler is correct.

Serge
  • 6,088
  • 17
  • 27
2

Because of the short-circuit evaluation.

if(!A && !B)

Let's pay attention to code above.

If A is truthy(not 0), !A && !B becomes 0(FALSE). Right, you don't have to check the value of the B. It should skip(jump) the code-block for the if statement.

mov eax, dword ptr[esp + A_offset]
test eax, eax   ; If `A & A`
jne ~~~~~~~~~~  ; is not 0(If A is not 0), skip this if-codeblock.
mov eax, dword ptr[esp + B_offset] ; Otherwise,
test eax, eax   ; If `B & B`
jne ~~~~~~~~~~  ; is not 0(If B is not 0), skip this if-codeblock.
......          ; Both A and B are 0, and `!A && !B` is `1(TRUE)`! Run the if-codeblock.

Plus:

It seems your code is wrong..?

mov eax, dword ptr[esp + A_offset]
mov ebx, dword ptr[esp + B_offset]
test eax, ebx  ; `A & B`
jne ~~~~~~~~~~ ; If `A & B != 0`, skip this code-block for the if statement.
...... ; In other words, this code-block will be run when `A & B == 0`,
       ; which will be `TRUE` when A is 1(0b00000001) and B is 2(0b00000010).
Константин Ван
  • 12,550
  • 7
  • 61
  • 73
  • If there was an efficient way to test both at once, the compiler would do so. Note that the OP's code already loaded `b` into a register before testing `a`, so the compiler's decision-making is nothing to do with work-avoiding or short-circuit evaluation, and everything to do with the fact that `bool(A&B)` != `A&&B` when A and B are non-zero with non-intersecting bit patterns. Also note the comment from gcc developer Marc Glisse that gcc turns `!a&&!b` into `!(a|b)` when it knows that `b` is safe to read. – Peter Cordes Sep 01 '16 at 14:04
  • @PeterCordes Well, to fair, the reason why GCC doesn't do that optimization when `b` isn't safe to read is because short-circuit evaluation means that it's never accessed if `a` is true. – Ross Ridge Sep 01 '16 at 15:16
  • @RossRidge: right, obviously that's a pre-requisite to maintain the C source's semantics. But my point was the *real* compiler output in the question (the last code block) does both loads before the first test, proving that they are both safe to access and that it's not trying to avoid it, so this answer's first hypothesis is wrong. – Peter Cordes Sep 01 '16 at 15:21