Equivalent to julia's `ifelse`

If you want a branchless if, it’s possible to play chicken with the llvm heuristics, which increasingly avoids instructions like cmov because it’s hard for the compiler to guess whether or not the branch will be predictable.

But this is fragile. To wit - the trick above doesn’t work for me in either x86 or wasm. In both cases that code now generates a stack allocated array and looks up the array index, exactly like you’d expect.

In julia they have an ifelse builtin which always generates llvm’s select instruction. I still don’t get a cmov, but I at least get what llvm thinks is better than a cmov if it can’t prove the branch is wildly unpredictable. (It is, in this case, unfortunately totally wrong).

It might be nice to have @ifelse in zig. It would emit llvms select instruction in the llvm backend, the wasm select instruction in the wasm backend, and cmov or similar in the x86 backend. I’d still fall afoul of the heuristics in the llvm backend, but at least I could have some control in the other backends.

Tangentially, [X86] cmov conversion hurts binary search performance · Issue #39374 · llvm/llvm-project · GitHub.

Ah, if I bump to zig master then

if (less_than(keys[mid], search_key)) {
    @branchHint(.unpredictable);
    offset = mid;
}

gets me

   0x0000000001001eda <+26>:	cmp    %rdx,(%rdi,%r8,8)
   0x0000000001001ede <+30>:	cmovb  %r8,%rcx

which is a nearly 2x speedup for some workloads.

Gets me a select on wasm too:

...
          (local.set 3
            (select
              (local.tee 5
                (i32.add
                  (local.get 3)
                  (local.tee 4
                    (i32.shr_u
                      (local.get 1)
                      (i32.const 1)))))
              (local.get 3)
              (i64.lt_u
                (i64.load
                  (i32.add
                    (local.get 0)
                    (i32.shl
                      (local.get 5)
                      (i32.const 3))))
                (local.get 2))))
...

@matklad this might be useful for you.

1 Like