[Bug target/97734] New: GCC using branches when a conditional move would be better

[rafael at espindo dot la]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97734

            Bug ID: 97734
           Summary: GCC using branches when a conditional move would be
                    better
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: target
          Assignee: unassigned at gcc dot gnu.org
          Reporter: rafael at espindo dot la
  Target Milestone: ---

Created attachment 49511
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49511&action=edit
graph

Playing with the code in https://github.com/patmorin/arraylayout I noticed that
I could not reproduce the results for the eytzinger layout. It turns out the
issue was with current gcc selecting moves instead of conditional moves for
that particular code.

A reduced testcase is

#include <stdint.h>
uint64_t branchfree_search(uint64_t x, uint64_t n, uint32_t *a) {
    uint64_t i = 0;
    while (i < n) {
        i = (x <= a[i]) ? (2*i + 1) : (2*i + 2);
    }
    uint64_t j = (i+1) >> __builtin_ffsl(~(i+1));
    return (j == 0) ? n : j-1;
}

I have placed it in

https://gcc.godbolt.org/z/Krqrz7

Results
* ICC: conditional move
* Clang: branches
* GCC 6.4: conditional move
* Newer GCCs with -O2:  branches
* GCC with -Os: conditional move

The attached graph shows how the conditional move is better for "small" array
sizes.