From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-bugs-return-416992-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Received: (qmail 18143 invoked by alias); 5 Mar 2013 23:46:15 -0000
Received: (qmail 16839 invoked by uid 48); 5 Mar 2013 23:45:41 -0000
From: "steven at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug target/55181] [4.7/4.8 Regression] Expensive shift loop where a bit-testing instruction could be used
Date: Tue, 05 Mar 2013 23:46:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: target
X-Bugzilla-Keywords: missed-optimization
X-Bugzilla-Severity: normal
X-Bugzilla-Who: steven at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Priority: P4
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 4.7.3
X-Bugzilla-Changed-Fields: Target CC
Message-ID: <bug-55181-4-pGiAElBfXu@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-55181-4@http.gcc.gnu.org/bugzilla/>
References: <bug-55181-4@http.gcc.gnu.org/bugzilla/>
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
Content-Type: text/plain; charset="UTF-8"
MIME-Version: 1.0
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
X-SW-Source: 2013-03/txt/msg00434.txt.bz2


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55181

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|avr                         |
                 CC|                            |steven at gcc dot gnu.org

--- Comment #5 from Steven Bosscher <steven at gcc dot gnu.org> 2013-03-05 23:45:38 UTC ---
At trunk r196410, the .164t.optimized dump looks like this:

lfsr (long unsigned int number)
{
  unsigned char b;
  long unsigned int _4;
  long unsigned int _5;
  _Bool _8;

  <bb 2>:
  _4 = number_3(D) & 536870912;
  _8 = _4 != 0;
  b_10 = (unsigned char) _8;
  _5 = number_3(D) & 8192;
  if (_5 != 0)
    goto <bb 3>;
  else
    goto <bb 4>;

  <bb 3>:
  b_6 = b_10 + 1;

  <bb 4>:
  # b_2 = PHI <b_10(2), b_6(3)>
  return b_2;

}

and exact_log2 could be used to identify the and-instruction as
a bit test instruction:
(gdb) p exact_log2(536870912)
$1 = 29
(gdb) 

AFAIK there are no named patterns for bit tests, perhaps there should be.
(http://gcc.gnu.org/onlinedocs/gccint/Standard-Names.html#Standard-Names)

So at least on x86_64 the test gets expanded as a shift:

    6: {r65:DI=r64:DI 0>>0x1d;clobber flags:CC;}
    7: {r59:QI=r65:DI#0&0x1;clobber flags:CC;}
    8: {r66:DI=r64:DI&0x2000;clobber flags:CC;}
    9: flags:CCZ=cmp(r66:DI,0)

i.e. also far from optimal.