How to check if any word is zero

Author: Wojciech Muła
Added on:2021-03-11

Problem

We want to check if at least one integer value is zero. In other words, we are evaluating following expression (for reasonably small N):

if (x0 == 0 or x1 == 0 or ... or xN == 0)
    ...

For a three-argument expression GCC 10.2 produces (with -O3 switch) the following x86 code:

testl   %esi, %esi  ; esi == 0?
sete    %al         ; al = 1 if the above condition is true, 0 otherwise
testl   %edx, %edx
sete    %dl
orl     %edx, %eax  ; plain `or`
testl   %edi, %edi
sete    %dl
orl     %edx, %eax

Clang 11.0 generates almost identical code:

testl   %edi, %edi
sete    %al
testl   %esi, %esi
sete    %cl
orb     %al, %cl
testl   %edx, %edx
sete    %al
orb     %cl, %al

ICC and MSVC added some jumps, but generally also use basic building block: test followed by a conditional set sete.

Can we do better?

It's possible with help of function min. Our initial condition can be rewritten as min(x0, x1, ldots, xN) = 0.

The minimum of two numbers can be calculated on x86 with a branch-free code:

cmpl    %ebx, %eax  ; copare ebx with eax
cmovg   %ebx, %eax  ; eax := ebx if ebx < eax

When min gets more arguments, we simply repeat this code, accumulating the minimum value in a selected register. Finally, we have to compare it with zero. Hand-written code for the three arguments expression:

; esi, edi and edx are inputs

cmpl    %esi, %edx
cmovg   %esi, %edx  ; edx = min(esi, edx)
cmpl    %edi, %edx
cmovg   %edi, %edx  ; edx = min(edi, edx)

test    %edx, %edx
setz    %al

But how compilers would compile this? GCC 10.2:

cmpl    %edx, %esi
cmovg   %edx, %esi
cmpl    %edi, %esi
cmovg   %edi, %esi
testl   %esi, %esi
sete    %al

Clang 11.0:

cmpl    %esi, %edi
cmovlel %edi, %esi
cmpl    %edx, %esi
cmovgl  %edx, %esi
testl   %esi, %esi
sete    %al