[Bug other/55181] New: [4.7/4.8 Regression] Expensive shift loop where a bit-testing instruction could be used

[Bug other/55181] New: [4.7/4.8 Regression] Expensive shift loop where a bit-testing instruction could be used

[gjl at gcc dot gnu.org]

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

             Bug #: 55181
           Summary: [4.7/4.8 Regression] Expensive shift loop where a
                    bit-testing instruction could be used
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: other
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: gjl@gcc.gnu.org
            Target: avr


The following C code:

unsigned char lfsr (unsigned long number)
{
  unsigned char b = 0;
  if (number & (1L << 29)) b++;
  if (number & (1L << 13)) b++;

  return b;
}

compiles to a right shift 29 bits of number which is very expensive because AVR
has no barrel shifter.  Instead, a bit-testing instruction could be used which
takes just a few cycles and not more than 100 like with the right shift.

4.6.2 uses a bit testing instruction.

== Command line ==

[Bug other/55181] [4.7/4.8 Regression] Expensive shift loop where a bit-testing instruction could be used

[gjl at gcc dot gnu.org]

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

Georg-Johann Lay <gjl at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-11-02
     Ever Confirmed|0                           |1

--- Comment #1 from Georg-Johann Lay <gjl at gcc dot gnu.org> 2012-11-02 16:10:05 UTC ---
== Command Line ==

$ avr-gcc -S foo.c -Os -dp

with avr-gcc

GCC: (GNU) 4.8.0 20120915 (experimental)

Set component to "other", dunno if avr backend is the culprit or the middle-end
disregarding costs.

[Bug other/55181] [4.7/4.8 Regression] Expensive shift loop where a bit-testing instruction could be used

[gjl at gcc dot gnu.org]

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

--- Comment #2 from Georg-Johann Lay <gjl at gcc dot gnu.org> 2012-11-02 16:11:40 UTC ---
Created attachment 28597
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=28597
foo.c Test case

[Bug other/55181] [4.7/4.8 Regression] Expensive shift loop where a bit-testing instruction could be used

[gjl at gcc dot gnu.org]

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

--- Comment #3 from Georg-Johann Lay <gjl at gcc dot gnu.org> 2012-11-02 16:13:18 UTC ---
Created attachment 28598
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=28598
foo.s (from 4.8)

Assembler output that shows the expensive shift loop in insn 44.

[Bug other/55181] [4.7/4.8 Regression] Expensive shift loop where a bit-testing instruction could be used

[gjl at gcc dot gnu.org]

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

--- Comment #4 from Georg-Johann Lay <gjl at gcc dot gnu.org> 2012-11-02 16:15:16 UTC ---
Created attachment 28599
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=28599
foo.s (4.6.2, good)

Assembler output from 4.6.2 that generates a bit test instruction.

[Bug other/55181] [4.7/4.8 Regression] Expensive shift loop where a bit-testing instruction could be used

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.7.3

[Bug target/55181] [4.7/4.8 Regression] Expensive shift loop where a bit-testing instruction could be used

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
           Priority|P3                          |P4
          Component|other                       |target

[Bug target/55181] [4.7/4.8 Regression] Expensive shift loop where a bit-testing instruction could be used

[steven at gcc dot gnu.org]

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.

[Bug target/55181] [4.7/4.8 Regression] Expensive shift loop where a bit-testing instruction could be used

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> 2013-03-06 08:51:30 UTC ---
Note that a bit-test instruction can only be used if the and only feeds a
comparison against zero.  Not sure how canonical bit-test patterns should
look like, but combine should be able to work this out, no?  Unless we
mess things up earlier during generic expansion (which seems to be the
case)

[Bug target/55181] [4.7/4.8/4.9 Regression] Expensive shift loop where a bit-testing instruction could be used

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.7.3                       |4.7.4

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> 2013-04-11 07:59:32 UTC ---
GCC 4.7.3 is being released, adjusting target milestone.

[Bug target/55181] [4.7/4.8/4.9 Regression] Expensive shift loop where a bit-testing instruction could be used

[olegendo at gcc dot gnu.org]

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

Oleg Endo <olegendo at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |olegendo at gcc dot gnu.org

--- Comment #8 from Oleg Endo <olegendo at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #6)
> Note that a bit-test instruction can only be used if the and only feeds a
> comparison against zero.  Not sure how canonical bit-test patterns should
> look like, but combine should be able to work this out, no?  Unless we
> mess things up earlier during generic expansion (which seems to be the
> case)

A single bit test pattern such as (taken from SH)

(define_insn "tstsi_t"
  [(set (reg:SI T_REG)
    (eq:SI (and:SI (match_operand:SI 0 "logical_operand" "%z,r")
               (match_operand:SI 1 "logical_operand" "K08,r"))
           (const_int 0)))]

is not enough.  If the second operand is a constant combine will try out
various variations (canonicalized bit extractions) such as zero_extend or

  [(set (reg:SI T_REG)
     (and:SI (not:SI (match_operand:SI 0 "logical_operand" "z"))
         (const_int 1)))]

[Bug target/55181] [4.7/4.8/4.9 Regression] Expensive shift loop where a bit-testing instruction could be used

[olegendo at gcc dot gnu.org]

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

--- Comment #9 from Oleg Endo <olegendo at gcc dot gnu.org> ---
The first "if (...) b++;" is transformed to a bit extraction (right shift +
and), because the result is either b = 0 or b = 1.
The second "if (...) b++" uses an and + zero-compare + branch around add.
The and + zero-compare are then combined to a bit test insn.

The first bit extraction could be turned into a bit test followed by a test
result store by implementing the according zero_extract combine pattern:

(set (reg:SI 169)
    (zero_extract:SI (reg/v:SI 165 [ number ])
        (const_int 1 [0x1])
        (const_int 29 [0x1d])))

Although doing so resulted in problems when matching bit test insns, if I
remember correctly.

The second bit test + branch + add is a bit more difficult, as it is always
expanded as a branch + add.

On SH there are multiple minimal sequences, depending on the context /
surrounding code.  The following branchless variant could used if the tested
reg dies after the tests and the whole thing is not inside a (inner) loop:

        mov     r4,r0                // r0 = number
        shlr8   r0                   // r0 = r0 >> 8 (logical shift)
        tst     #(1 << (13-8)),r0    // T = (r0 & (1 << (13-8))) == 0
        shlr8   r0                   // r0 = r0 >> 8 (logical shift)
        movrt   r1                   // r1 = !T
        tst     #(1 << (29-16)),r0   // T = (r0 & (1 << (26-16))) == 0
        movrt   r0                   // r0 = !T
        rts
        add     r1,r0                // r0 = r0 + r1

If the code is in a loop, it's more efficient to load constants (which might
require a constant pool on SH):

        mov.l   (1 << 13),r1
        mov.l   (1 << 29),r2
        mov     #0,r0
        ...
loop:
        ...
        // r4 = number from somewhere
        tst     r1,r4               // T = (r4 & (1 << 13)) == 0
        movrt   r3                  // r3 = !T
        tst     r2,r4               // T = (r4 & (1 << 29)) == 0
        add     r3,r0               // r0 = r0 + r3
        movrt   r3                  // r3 = !T
        add     r3,r0
        ...
        <cbranch loop>


Using shift + and is usually worse on SH for these kind of sequences.

I've tried adding the standard name pattern extzv<mode> but it doesn't seem to
be used neither for the first if (...) nor for the second during RTL expansion.

Maybe if-convert could be taught to transform the second if (...) to a
zero_extract as well.  But probably it's better to catch this earlier.

[Bug target/55181] [4.7/4.8/4.9 Regression] Expensive shift loop where a bit-testing instruction could be used

[olegendo at gcc dot gnu.org]

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

--- Comment #10 from Oleg Endo <olegendo at gcc dot gnu.org> ---
(In reply to Oleg Endo from comment #9)
> 
> Maybe if-convert could be taught to transform the second if (...) to a
> zero_extract as well.  But probably it's better to catch this earlier.

... which would make the original example

unsigned char lfsr (unsigned long number)
{
  unsigned char b = 0;
  if (number & (1L << 29)) b++;
  if (number & (1L << 13)) b++;

  return b;
}

produce the same code as

unsigned char lfsr (unsigned long number)
{
  return ((number & (1L << 29)) != 0) + ((number & (1L << 13)) != 0);
}

[Bug target/55181] [4.7/4.8/4.9/4.10 Regression] Expensive shift loop where a bit-testing instruction could be used

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.7.4                       |4.8.4

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
The 4.7 branch is being closed, moving target milestone to 4.8.4.

[Bug target/55181] [4.8/4.9/5 Regression] Expensive shift loop where a bit-testing instruction could be used

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.8.4                       |4.8.5

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.8.4 has been released.

[Bug target/55181] [4.8/4.9/5/6 Regression] Expensive shift loop where a bit-testing instruction could be used

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.8.5                       |4.9.3

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
The gcc-4_8-branch is being closed, re-targeting regressions to 4.9.3.

[Bug target/55181] [4.9/5/6 Regression] Expensive shift loop where a bit-testing instruction could be used

[jakub at gcc dot gnu.org]

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

--- Comment #14 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.3 has been released.

[Bug target/55181] [4.9/5/6 Regression] Expensive shift loop where a bit-testing instruction could be used

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.3                       |4.9.4

[Bug target/55181] [9/10/11/12 Regression] Expensive shift loop where a bit-testing instruction could be used

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|8.5                         |9.4

--- Comment #22 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 8 branch is being closed.

[Bug target/55181] [9/10/11/12 Regression] Expensive shift loop where a bit-testing instruction could be used

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|9.4                         |9.5

--- Comment #23 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 9.4 is being released, retargeting bugs to GCC 9.5.

[Bug target/55181] [10/11/12/13 Regression] Expensive shift loop where a bit-testing instruction could be used

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|9.5                         |10.4

--- Comment #24 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 9 branch is being closed

[Bug target/55181] [10/11/12/13 Regression] Expensive shift loop where a bit-testing instruction could be used

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|10.4                        |10.5

--- Comment #25 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 10.4 is being released, retargeting bugs to GCC 10.5.

[Bug target/55181] [10/11/12/13/14 Regression] Expensive shift loop where a bit-testing instruction could be used

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org
             Status|NEW                         |ASSIGNED

--- Comment #26 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So I guess this is mine too.

With my patches I created to improve PR 109907 (attached there), the initial
RTL now looks like:
;; _9 = (unsigned char) _8;

(insn 6 5 0 (set (reg/v:QI 46 [ <retval> ])
        (zero_extract:QI (subreg:QI (reg/v:SI 47 [ number ]) 3)
            (const_int 1 [0x1])
            (const_int 5 [0x5]))) "t2.c":4:6 -1
     (nil))

Where it was before:
;; _9 = (unsigned char) _8;

(insn 6 5 7 (set (reg:SI 48)
        (lshiftrt:SI (reg/v:SI 47 [ number ])
            (const_int 29 [0x1d]))) "t2.c":4:6 -1
     (nil))

(insn 7 6 0 (set (reg/v:QI 46 [ <retval> ])
        (and:QI (subreg:QI (reg:SI 48) 0)
            (const_int 1 [0x1]))) "t2.c":4:6 -1
     (nil))

[Bug target/55181] [10/11/12/13/14 Regression] Expensive shift loop where a bit-testing instruction could be used

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|                            |avr
   Target Milestone|10.5                        |14.0
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #27 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
This is now fixed on the trunk for GCC 14. I have no plans on backporting the
patches.

[Bug target/55181] [10/11/12/13/14 Regression] Expensive shift loop where a bit-testing instruction could be used

[pinskia at gcc dot gnu.org]

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

--- Comment #28 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I forgot to mention this was fixed by r14-1014-gc5df248509b48 .