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.