public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
From: "tkoenig at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org> To: gcc-bugs@gcc.gnu.org Subject: [Bug tree-optimization/108710] New: Recognizing "rounding down to the nearest power of two" Date: Wed, 08 Feb 2023 06:59:39 +0000 [thread overview] Message-ID: <bug-108710-4@http.gcc.gnu.org/bugzilla/> (raw) https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108710 Bug ID: 108710 Summary: Recognizing "rounding down to the nearest power of two" Product: gcc Version: 13.0 Status: UNCONFIRMED Severity: enhancement Priority: P3 Component: tree-optimization Assignee: unassigned at gcc dot gnu.org Reporter: tkoenig at gcc dot gnu.org Target Milestone: --- In the code #include <stdint.h> #include <stdio.h> #include <stdlib.h> uint64_t foo (uint64_t x) { x = x | (x >> 1); x = x | (x >> 2); x = x | (x >> 4); x = x | (x >> 8); x = x | (x >> 16); x = x | (x >> 32); return x - (x >> 1); } uint64_t bar (uint64_t x) { if (x == 0) return 0; else return 1ul << (63 - __builtin_clzl(x)); } void tst (uint64_t a) { uint64_t r_foo, r_bar; r_foo = foo(a); r_bar = bar(a); printf ("%20lu %20lu %20lu\n", a, r_foo, r_bar); if (r_foo != r_bar) abort(); } int main() { tst(0ul); for (uint64_t i = 1; i<64; i++) { for (uint64_t j = 0; j<i; j++) { uint64_t a, b, c; b = 1ul << i; a = b - (1ul << j); c = b + (1ul << j); tst(a); tst(b); tst(c); } } return 0; } the nearest power of two, roundnihg down, is calculated, using the two methods from chapter 3-2 in Hacker's Delight. The method used in foo, using only standard C, is used, for example, in the embench benchmkark. Code for recent trunk is foo: .LFB39: .cfi_startproc endbr64 movq %rdi, %rax shrq %rax orq %rax, %rdi movq %rdi, %rax shrq $2, %rax orq %rdi, %rax movq %rax, %rdi shrq $4, %rdi orq %rdi, %rax movq %rax, %rdi shrq $8, %rdi orq %rax, %rdi movq %rdi, %rax shrq $16, %rax orq %rax, %rdi movq %rdi, %rax shrq $32, %rax orq %rdi, %rax movq %rax, %rdx shrq %rdx subq %rdx, %rax ret (same with -O3 and -Os) and for bar is bar: .LFB23: .cfi_startproc movq %rdi, %rax testq %rdi, %rdi je .L4 movabsq $-9223372036854775808, %rax bsrq %rdi, %rcx xorq $63, %rcx shrq %cl, %rax .L4: ret which is more compact and should have a well-predicted branch. It would be good for the idiom to be recognized (same as for the round up to the nearest power of two). Also, the number of register moves in the original version could be removed by using more registers, at least for -Os.
next reply other threads:[~2023-02-08 6:59 UTC|newest] Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top 2023-02-08 6:59 tkoenig at gcc dot gnu.org [this message] 2023-02-09 7:34 ` [Bug tree-optimization/108710] " tkoenig at gcc dot gnu.org
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=bug-108710-4@http.gcc.gnu.org/bugzilla/ \ --to=gcc-bugzilla@gcc.gnu.org \ --cc=gcc-bugs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).