[Bug tree-optimization/107009] New: massive unnecessary code blowup in vectorizer

[Bug tree-optimization/107009] New: massive unnecessary code blowup in vectorizer

[drepper.fsp+rhbz at gmail dot com]

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

            Bug ID: 107009
           Summary: massive unnecessary code blowup in vectorizer
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: drepper.fsp+rhbz at gmail dot com
  Target Milestone: ---

Given an annotated saxpy function:

#include <cstdlib>

void saxpy(size_t n, float* __restrict res, float a, const float* __restrict x,
const float* __restrict y)
{
  if (n == 0 || n % 8 != 0)
    __builtin_unreachable();
  res = (float*)__builtin_assume_aligned(res, 32);
  x = (const float*) __builtin_assume_aligned(x, 32);
  y = (const float*) __builtin_assume_aligned(y, 32);
  for (size_t i = 0; i < n; ++i)
    res[i] = a * x[i] + y[i];
}


Compiling this with the gcc 12.2.1 version from Fedora 36 leads to the
expected, guided result (although the shrq isn't necessary…) with -O3:

_Z5saxpymPffPKfS1_:
        .cfi_startproc
        shrq    $3, %rdi
        vbroadcastss    %xmm0, %ymm0
        xorl    %eax, %eax
        salq    $5, %rdi
        .p2align 4
        .p2align 3
.L2:
        vmovaps (%rdx,%rax), %ymm1
        vfmadd213ps     (%rcx,%rax), %ymm0, %ymm1
        vmovaps %ymm1, (%rsi,%rax)
        addq    $32, %rax
        cmpq    %rdi, %rax
        jne     .L2
        vzeroupper
        ret

The the current trunk gcc the result is massively bigger and given the guidance
in the sources none of the extra code is necessary.

_Z5saxpymPffPKfS1_:
.LFB22:
        .cfi_startproc
        movq    %rdi, %r8
        movq    %rdx, %rdi
        movq    %rcx, %rdx
        leaq    -1(%r8), %rax
        cmpq    $6, %rax
        jbe     .L7
        movq    %r8, %rcx
        vbroadcastss    %xmm0, %ymm2
        xorl    %eax, %eax
        shrq    $3, %rcx
        salq    $5, %rcx
        .p2align 4
        .p2align 3
.L3:
        vmovaps (%rdi,%rax), %ymm1
        vfmadd213ps     (%rdx,%rax), %ymm2, %ymm1
        vmovaps %ymm1, (%rsi,%rax)
        addq    $32, %rax
        cmpq    %rcx, %rax
        jne     .L3
        movq    %r8, %rax
        andq    $-8, %rax
        testb   $7, %r8b
        je      .L18
        vzeroupper
.L2:
        movq    %r8, %rcx
        subq    %rax, %rcx
        leaq    -1(%rcx), %r9
        cmpq    $2, %r9
        jbe     .L5
        vmovaps (%rdx,%rax,4), %xmm3
        vshufps $0, %xmm0, %xmm0, %xmm1
        movq    %rcx, %r9
        vfmadd132ps     (%rdi,%rax,4), %xmm3, %xmm1
        andq    $-4, %r9
        vmovaps %xmm1, (%rsi,%rax,4)
        addq    %r9, %rax
        andl    $3, %ecx
        je      .L16
.L5:
        vmovss  (%rdi,%rax,4), %xmm1
        leaq    0(,%rax,4), %rcx
        leaq    1(%rax), %r9
        vfmadd213ss     (%rdx,%rax,4), %xmm0, %xmm1
        vmovss  %xmm1, (%rsi,%rcx)
        cmpq    %r8, %r9
        jnb     .L16
        vmovss  4(%rdi,%rcx), %xmm1
        addq    $2, %rax
        vfmadd213ss     4(%rdx,%rcx), %xmm0, %xmm1
        vmovss  %xmm1, 4(%rsi,%rcx)
        cmpq    %r8, %rax
        jnb     .L16
        vmovss  8(%rdx,%rcx), %xmm4
        vfmadd132ss     8(%rdi,%rcx), %xmm4, %xmm0
        vmovss  %xmm0, 8(%rsi,%rcx)
.L16:
        ret
        .p2align 4
        .p2align 3
.L18:
        vzeroupper
        ret
        .p2align 4
        .p2align 3
.L7:
        xorl    %eax, %eax
        jmp     .L2

[Bug tree-optimization/107009] [13 Regression] massive unnecessary code blowup in vectorizer

[mpolacek at gcc dot gnu.org]

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

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |13.0
     Ever confirmed|0                           |1
            Summary|massive unnecessary code    |[13 Regression] massive
                   |blowup in vectorizer        |unnecessary code blowup in
                   |                            |vectorizer
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |mpolacek at gcc dot gnu.org
   Last reconfirmed|                            |2022-09-22
             Status|UNCONFIRMED                 |NEW

--- Comment #1 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Looks like it was caused by r13-1268-g8c99e307b20c50:

commit 8c99e307b20c502e55c425897fb3884ba8f05882
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Sat Jun 25 18:58:02 2022 -0400

    Convert DOM to use Ranger rather than EVRP

[Bug tree-optimization/107009] [13 Regression] massive unnecessary code blowup in vectorizer

[aldyh at gcc dot gnu.org]

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

--- Comment #2 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
(In reply to Marek Polacek from comment #1)
> Looks like it was caused by r13-1268-g8c99e307b20c50:
> 
> commit 8c99e307b20c502e55c425897fb3884ba8f05882
> Author: Aldy Hernandez <aldyh@redhat.com>
> Date:   Sat Jun 25 18:58:02 2022 -0400
> 
>     Convert DOM to use Ranger rather than EVRP

Note that this patch is usually a red herring. It makes DOM smarter by
improving its copy propagation and threading capabilities. And when DOM is
done, it will export whatever global ranges it discovered to other passes. Any
number of these things could cause the vectorizer to make different decisions.

I'll take a look tomorrow though.

[Bug tree-optimization/107009] [13 Regression] massive unnecessary code blowup in vectorizer

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
           Priority|P3                          |P1
                 CC|                            |rguenth at gcc dot gnu.org

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
  # RANGE [irange] size_t [1, +INF]
  size_t n_12(D) = n;

the nonzero bits info on 'n' is gone.  DOM2 used to produce that and
CCP3 elides the __builtin_unreachable () but if DOM2 is disabled that
doesn't produce the nonzero bits.

DOM2 from trunk no longer sets nonzero bits.  CCP doesn't do any
conditional non-zero bits (or constant equivalence) propagation.

[Bug tree-optimization/107009] [13 Regression] massive unnecessary code blowup in vectorizer

[aldyh at gcc dot gnu.org]

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

--- Comment #4 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #3)
>   # RANGE [irange] size_t [1, +INF]
>   size_t n_12(D) = n;
> 
> the nonzero bits info on 'n' is gone.  DOM2 used to produce that and
> CCP3 elides the __builtin_unreachable () but if DOM2 is disabled that
> doesn't produce the nonzero bits.
> 
> DOM2 from trunk no longer sets nonzero bits.  CCP doesn't do any
> conditional non-zero bits (or constant equivalence) propagation.

Indeed, there is a missing nonzero mask on n_12(D).  Thanks for the analysis,
Richi.  It saved me a ton of work.

This is the problematic BB, where the 2->3 edge is unreachable:

    <bb 2> [local count: 118111600]:
    _1 = n_12(D) & 7;
    if (_1 != 0)
      goto <bb 3>; [0.00%]
    else
      goto <bb 4>; [100.00%]

_1 : [irange] long unsigned int [0, 0]
2->3  (T) _1 :  [irange] UNDEFINED
2->3  (T) n_12(D) :     [irange] UNDEFINED
2->4  (F) _1 :  [irange] long unsigned int [0, 0]
2->4  (F) n_12(D) :     [irange] size_t [1, 18446744073709551608] <-- BOO
HISS!!!!

Notice there is no nonzero mask on n_12(D) in the 2->4 edge which is
unreachable.

So this is actually our fault, not because of this patch, but because we didn't
track nonzero bits back then.  I keep saying, this patch is a red herring :-P.

However, we do track nonzero bits now, and the testcase still fails so...

The culprit is operator_bitwise_and::op1_range() which is not setting the
nonzero mask.  This should be quite easy to fix.  What we're trying to solve is
n_12 on the 2->4 edge:

    _1 = n_12(D) & 7;

which _1 = 0 because we're talking about the 2->4 edge:

     0 = n_12(D) & 7;

So the mask should be everything but the lower 3 bits, 0xffff...f8 if my math
is correct.

[Bug tree-optimization/107009] [13 Regression] massive unnecessary code blowup in vectorizer

[aldyh at gcc dot gnu.org]

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

--- Comment #5 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
There are two things needed to fix this regression.

First, we need an op1_range entry for bitwise-and, so that the 2->4 edge range
has the correct nonzero bits for n_12.

    <bb 2> [local count: 118111600]:
    _1 = n_12(D) & 7;
    if (_1 != 0)
      goto <bb 3>; [0.00%]
    else
      goto <bb 4>; [100.00%]

With the correct tweak to range-ops, we have:

2->4  (F) n_12(D) :     [irange] size_t [1, 18446744073709551608] NONZERO
0xfffffffffffffff8

Which is correct and what DOM would need from ranger to get the nonzero mask
correct.

However, set_global_ranges_from_unreachable_edges() in DOM is is only exporting
ranges for unreachable edges on the SSA names feeding the final conditional
above (_1).  It also needs to calculate these ranges for other exports from
this BB.  In this case, we'd need to do the same thing for n_12 as well as _1.

In my conversion of DOM+evrp to DOM+ranger, I missed that evrp was doing this
dance for all the ranges it knew about coming out of the BB, not just op1 of
the conditional.  This is legacy evrp:

          /* Push updated ranges only after finding all of them to avoid
             ordering issues that can lead to worse ranges.  */
          for (unsigned i = 0; i < vrs.length (); ++i)
...
...
              if (is_fallthru
                  && m_update_global_ranges
                  && all_uses_feed_or_dominated_by_stmt (vrs[i].first, stmt)
                  /* The condition must post-dominate the definition point.  */
                  && (SSA_NAME_IS_DEFAULT_DEF (vrs[i].first)
                      || (gimple_bb (SSA_NAME_DEF_STMT (vrs[i].first))
                          == pred_e->src)))
                {
                  set_ssa_range_info (vrs[i].first, vrs[i].second);
                  maybe_set_nonzero_bits (pred_e, vrs[i].first);
                }

All we'd need in theory is to loop over the exports to BB2, and export those if
the same logic applies.  

I have two patches in testing that fix the regression.

[Bug tree-optimization/107009] [13 Regression] massive unnecessary code blowup in vectorizer

[aldyh at gcc dot gnu.org]

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

--- Comment #6 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
Created attachment 53621
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53621&action=edit
bitwise and op1_range patch in testing

[Bug tree-optimization/107009] [13 Regression] massive unnecessary code blowup in vectorizer

[aldyh at gcc dot gnu.org]

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

--- Comment #7 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
Created attachment 53622
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53622&action=edit
DOM patch in testing to calculate ranges for all ranges involving unreachable
edges

[Bug tree-optimization/107009] [13 Regression] massive unnecessary code blowup in vectorizer

[cvs-commit at gcc dot gnu.org]

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

--- Comment #8 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Aldy Hernandez <aldyh@gcc.gnu.org>:

https://gcc.gnu.org/g:2460f7cdef7ef9c971de79271afc0db73687a272

commit r13-2876-g2460f7cdef7ef9c971de79271afc0db73687a272
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Fri Sep 23 19:47:33 2022 +0200

    Set ranges from unreachable edges for all known ranges.

    In the conversion of DOM+evrp to DOM+ranger, we missed that evrp was
    exporting ranges for unreachable edges for all SSA names for which we
    have ranges for.  Instead we have only been exporting ranges for the
    SSA name in the final conditional to the BB involving the unreachable
    edge.

    This patch adjusts adjusts DOM to iterate over the exports, similarly
    to what evrp was doing.

    Note that I also noticed that we don't calculate the nonzero bit mask
    for op1, when 0 = op1 & MASK.  This isn't needed for this PR,
    since maybe_set_nonzero_bits() is chasing the definition and
    parsing the bitwise and on its own.  However, I'll be adding the
    functionality for completeness sake, plus we could probably drop the
    maybe_set_nonzero_bits legacy call entirely.

            PR tree-optimization/107009

    gcc/ChangeLog:

            * tree-ssa-dom.cc
            (dom_opt_dom_walker::set_global_ranges_from_unreachable_edges):
            Iterate over exports.

    gcc/testsuite/ChangeLog:

            * gcc.dg/tree-ssa/pr107009.c: New test.

[Bug tree-optimization/107009] [13 Regression] massive unnecessary code blowup in vectorizer

[aldyh at gcc dot gnu.org]

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

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

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

--- Comment #9 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
fixed

[Bug tree-optimization/107009] [13 Regression] massive unnecessary code blowup in vectorizer

[cvs-commit at gcc dot gnu.org]

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

--- Comment #10 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Aldy Hernandez <aldyh@gcc.gnu.org>:

https://gcc.gnu.org/g:5e77d4082fa845f1182641a93cfbae71984244d2

commit r13-2880-g5e77d4082fa845f1182641a93cfbae71984244d2
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Fri Sep 23 19:47:19 2022 +0200

    Optimize [0 = x & MASK] in range-ops.

    For [0 = x & MASK], we can determine that x is ~MASK.  This is
    something we're picking up in DOM thanks to maybe_set_nonzero_bits,
    but is something we should handle natively.

    This is a good example of how much easier to maintain the range-ops
    entries are versus the ad-hoc pattern matching stuff we had to do
    before.  For the curious, compare the changes to range-op here,
    versus maybe_set_nonzero_bits.

    I'm leaving the call to maybe_set_nonzero_bits until I can properly
    audit it to make sure we're catching it all in range-ops.  It won't
    hurt, since both set_range_info() and set_nonzero_bits() are
    intersect operations, so we'll never lose information if we do both.

            PR tree-optimization/107009

    gcc/ChangeLog:

            * range-op.cc (operator_bitwise_and::op1_range): Optimize 0 = x &
MASK.
            (range_op_bitwise_and_tests): New test.