[Bug tree-optimization/103462] New: vectorizer failed to reduce bit_clear in loop.

[Bug tree-optimization/103462] New: vectorizer failed to reduce bit_clear in loop.

[crazylht at gmail dot com]

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

            Bug ID: 103462
           Summary: vectorizer failed to reduce bit_clear in loop.
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: crazylht at gmail dot com
  Target Milestone: ---
              Host: x86_64-pc-linux-gnu

the testcase is from pr47769

unsigned long cfunc_one(unsigned long tmp) {
    for (unsigned long bit = 0; bit < 64; bit += 3) {
        tmp &= ~(1UL << bit);
    }
    return tmp;
}

with -O3 -march=skylake -funroll-loops
gcc generates:
cfunc_one:
        mov     rax, rdi
        xor     edx, edx
.L2:
        lea     rcx, [rdx+3]
        btr     rax, rdx
        lea     rsi, [rdx+6]
        btr     rax, rcx
        lea     rdi, [rdx+9]
        btr     rax, rsi
        btr     rax, rdi
        lea     r8, [rdx+12]
        lea     r9, [rdx+15]
        btr     rax, r8
        lea     r10, [rdx+18]
        btr     rax, r9
        lea     r11, [rdx+21]
        btr     rax, r10
        lea     rcx, [rdx+24]
        btr     rax, r11
        lea     rsi, [rdx+27]
        btr     rax, rcx
        lea     rdi, [rdx+30]
        btr     rax, rsi
        add     rdx, 33
        btr     rax, rdi
        cmp     rdx, 66
        jne     .L2
        ret

while clang generates:

cfunc_one(unsigned long):                          # @cfunc_one(unsigned long)
        movabs  rax, 7905747460161236406
        and     rax, rdi
        ret

7905747460161236406 is bit clear for bit {0, 3, 6, 9, ..., 63}.

[Bug tree-optimization/103462] GCC failed to reduce bit clear in loop.

[crazylht at gmail dot com]

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

--- Comment #1 from Hongtao.liu <crazylht at gmail dot com> ---
Should it be done in vectorizer or ldist(just like memory op), or somewhere
else?

[Bug tree-optimization/103462] GCC failed to reduce bit clear in loop.

[crazylht at gmail dot com]

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

--- Comment #2 from Hongtao.liu <crazylht at gmail dot com> ---
bit clear and induction variable could be simplified to `& CONSTANT`

[Bug tree-optimization/103462] GCC failed to reduce bit clear in loop.

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
           Severity|normal                      |enhancement

[Bug tree-optimization/103462] GCC failed to reduce bit clear in loop.

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=101991

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Related to PR 101991 but not really the same. In this case the value that
matters is an induction variable while in the other case it was an invariant.

[Bug tree-optimization/103462] GCC failed to reduce bit clear in loop.

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2021-11-29

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
final value replacement could handle this I guess.

[Bug tree-optimization/103462] GCC failed to reduce bit clear in loop.

[crazylht at gmail dot com]

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

--- Comment #5 from Hongtao.liu <crazylht at gmail dot com> ---
Created attachment 52004
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52004&action=edit
Testes patch, wait for gcc13.

[Bug tree-optimization/103462] GCC failed to reduce bit clear in loop.

[crazylht at gmail dot com]

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

--- Comment #6 from Hongtao.liu <crazylht at gmail dot com> ---
(In reply to Hongtao.liu from comment #5)
> Created attachment 52004 [details]
> Testes patch, wait for gcc13.

Add error in the patch to see if there's any change in gcc which can be
optimized, it turns out there're several places.

gcc/final.c:4363:24: error: Got bitwise induction optimization
 4363 |   virtual unsigned int execute (function *) { return
rest_of_handle_final (); }

gcc/ira-lives.c:1221:1: error: Got bitwise induction optimization
 1221 | process_bb_node_lives (ira_loop_tree_node_t loop_tree_node)


gcc/lra-lives.c:653:1: error: Got bitwise induction optimization
  653 | process_bb_lives (basic_block bb, int &curr_point, bool dead_insn_p)


gcc/lra-assigns.c:478:1: error: Got bitwise induction optimization
  478 | find_hard_regno_for_1 (int regno, int *cost, int try_only_hard_regno,

gcc/ira.c:1703:1: error: Got bitwise induction optimization
 1703 | ira_init (void)

[Bug tree-optimization/103462] GCC failed to reduce bit clear in loop.

[cvs-commit at gcc dot gnu.org]

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

--- Comment #7 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by hongtao Liu <liuhongt@gcc.gnu.org>:

https://gcc.gnu.org/g:9d1336d977cf0cab75679d4b4170e7c9a86cd1f4

commit r13-583-g9d1336d977cf0cab75679d4b4170e7c9a86cd1f4
Author: liuhongt <hongtao.liu@intel.com>
Date:   Tue Dec 7 15:41:52 2021 +0800

    Enhance final_value_replacement_loop to handle bitwise induction.

    This patch will enable below optimization:

     {
    -  int bit;
    -  long long unsigned int _1;
    -  long long unsigned int _2;
    -
       <bb 2> [local count: 46707768]:
    -
    -  <bb 3> [local count: 1027034057]:
    -  # tmp_11 = PHI <tmp_8(3), tmp_6(D)(2)>
    -  # bit_13 = PHI <bit_9(3), 63(2)>
    -  _1 = 1 << bit_13;
    -  _2 = ~_1;
    -  tmp_8 = _2 & tmp_11;
    -  bit_9 = bit_13 + -3;
    -  if (bit_9 != -3(OVF))
    -    goto <bb 3>; [95.65%]
    -  else
    -    goto <bb 4>; [4.35%]
    -
    -  <bb 4> [local count: 46707768]:
    -  return tmp_8;
    +  tmp_12 = tmp_6(D) & 7905747460161236406;
    +  return tmp_12;

     }

    gcc/ChangeLog:

            PR middle-end/103462
            * match.pd (bitwise_induction_p): New match.
            * tree-scalar-evolution.cc (gimple_bitwise_induction_p):
            Declare.
            (analyze_and_compute_bitwise_induction_effect): New function.
            (enum bit_op_kind): New enum.
            (final_value_replacement_loop): Enhanced to handle bitwise
            induction.

    gcc/testsuite/ChangeLog:

            * gcc.target/i386/pr103462-1.c: New test.
            * gcc.target/i386/pr103462-2.c: New test.
            * gcc.target/i386/pr103462-3.c: New test.
            * gcc.target/i386/pr103462-4.c: New test.
            * gcc.target/i386/pr103462-5.c: New test.
            * gcc.target/i386/pr103462-6.c: New test.

[Bug tree-optimization/103462] GCC failed to reduce bit clear in loop.

[crazylht at gmail dot com]

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

Hongtao.liu <crazylht at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

--- Comment #8 from Hongtao.liu <crazylht at gmail dot com> ---
Fixed in GCC13.