From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-bugzilla@gcc.gnu.org>
Received: by sourceware.org (Postfix, from userid 48)
	id 86C413858C2D; Wed,  8 Feb 2023 06:59:40 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 86C413858C2D
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org;
	s=default; t=1675839580;
	bh=eU+bm0RZtGldFCHdBhZ2Vk4cA6ssM5y10R2gWuBWz18=;
	h=From:To:Subject:Date:From;
	b=TdyuN6KOnjMACUqi+vekYS37IcWWwPBxyZe63ARZwlsufpLd0k08h+owKyYmvApJ8
	 X1a+pLAx2I8M+eDEAyt2Zau+tFlKoNfwal5Z6mgyXkJFGo8L98Lf8NjJo+7uzj628V
	 gIK1eqbQoJmwuFySleNOoKUnfUtjt1rA3rJ+7oSU=
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
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: tree-optimization
X-Bugzilla-Version: 13.0
X-Bugzilla-Keywords: 
X-Bugzilla-Severity: enhancement
X-Bugzilla-Who: tkoenig at gcc dot gnu.org
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Resolution: 
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags: 
X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status
 bug_severity priority component assigned_to reporter target_milestone
Message-ID: <bug-108710-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
List-Id: <gcc-bugs.sourceware.org>

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

            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 =3D x | (x >> 1);
  x =3D x | (x >> 2);
  x =3D x | (x >> 4);
  x =3D x | (x >> 8);
  x =3D x | (x >> 16);
  x =3D x | (x >> 32);
  return x - (x >> 1);
}

uint64_t bar (uint64_t x)
{
  if (x =3D=3D 0)
    return 0;
  else
    return 1ul << (63 - __builtin_clzl(x));
}

void tst (uint64_t a)
{
  uint64_t r_foo, r_bar;
  r_foo =3D foo(a);
  r_bar =3D bar(a);
  printf ("%20lu %20lu %20lu\n", a, r_foo, r_bar);
  if (r_foo !=3D r_bar)
    abort();
}

int main()
{
  tst(0ul);
  for (uint64_t i =3D 1; i<64; i++) {
    for (uint64_t j =3D 0; j<i; j++) {
      uint64_t a, b, c;
      b =3D 1ul << i;
      a =3D b - (1ul << j);
      c =3D 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=20

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.=