[Bug tree-optimization/109539] New: [13/14 Regression] Compile-time hog in gimple-ssa-warn-access.cc since r13-6706-gadb70c2d1060b3

[Bug tree-optimization/109539] New: [13/14 Regression] Compile-time hog in gimple-ssa-warn-access.cc since r13-6706-gadb70c2d1060b3

[marxin at gcc dot gnu.org]

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

            Bug ID: 109539
           Summary: [13/14 Regression] Compile-time hog in
                    gimple-ssa-warn-access.cc since
                    r13-6706-gadb70c2d1060b3
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Keywords: needs-reduction
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: marxin at gcc dot gnu.org
                CC: rguenth at gcc dot gnu.org
  Target Milestone: ---

Created attachment 54876
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54876&action=edit
Unreduced test-case

Originally reported as openSUSE issue of psi+ package:
https://bugzilla.suse.com/show_bug.cgi?id=1210557

it's problem that started with r13-6706-gadb70c2d1060b3 and I'm reducing that
right now.

[Bug tree-optimization/109539] [13/14 Regression] Compile-time hog in gimple-ssa-warn-access.cc since r13-6706-gadb70c2d1060b3

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |13.0
     Ever confirmed|0                           |1
                 CC|                            |jirislaby at gmail dot com
   Last reconfirmed|                            |2023-04-18
             Status|UNCONFIRMED                 |NEW

[Bug tree-optimization/109539] [13/14 Regression] Compile-time hog in gimple-ssa-warn-access.cc since r13-6706-gadb70c2d1060b3

[marxin at gcc dot gnu.org]

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

--- Comment #1 from Martin Liška <marxin at gcc dot gnu.org> ---
Created attachment 54877
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54877&action=edit
Reduced test-case

Takes 1.77s after the mentioned revision and 0.15s before it.

[Bug tree-optimization/109539] [13/14 Regression] Compile-time hog in gimple-ssa-warn-access.cc since r13-6706-gadb70c2d1060b3

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
I will have a look.

[Bug tree-optimization/109539] [13/14 Regression] Compile-time hog in gimple-ssa-warn-access.cc since r13-6706-gadb70c2d1060b3

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
The issue is almost certainly the cost of pointers_related_p

Samples: 3M of event 'cycles', Event count (approx.): 3573086788171             
  Children      Self       Samples  Command  Shared Object     Symbol           
-   93.15%     0.80%         25898  cc1plus  cc1plus           [.] (anonymous
namespace)::pointers_related_p     #
   - 92.35% (anonymous namespace)::pointers_related_p                          
                                 #
      - 92.30% (anonymous namespace)::pointers_related_p                       
                                 #
         - 92.21% (anonymous namespace)::pointers_related_p                    
                                 #
            - 92.12% (anonymous namespace)::pointers_related_p                 
                                 #
               - 92.02% (anonymous namespace)::pointers_related_p              
                                 #
                  - 91.93% (anonymous namespace)::pointers_related_p           
                                 #
                     - 91.84% (anonymous namespace)::pointers_related_p        
                                 #
                        - 91.75% (anonymous namespace)::pointers_related_p     
                                 #
                           - 91.66% (anonymous namespace)::pointers_related_p  
                                 #
                              - 91.57% (anonymous
namespace)::pointers_related_p                                 #
                                 - 91.48% (anonymous
namespace)::pointers_related_p                              #
                                    - 91.39% (anonymous
namespace)::pointers_related_p                           #
                                       - 87.34% (anonymous
namespace)::pointers_related_p                        #
                                          - 62.30% (anonymous
namespace)::pointers_related_p                     #
                                             - 44.52% pointer_query::get_ref   
                                 #
                                                - 44.51% compute_objsize       
                                 #
                                                   + 15.03%
access_ref::size_remaining                           #
                                                   + 14.49% wide_int_to_tree   
                                 #
                                                   + 4.91%
generic_wide_int<fixed_wide_int_storage<128> >::operat#
                                                   + 4.57% operator<
<generic_wide_int<fixed_wide_int_storage<128#
                                                   + 2.41% poly_int<1u,
generic_wide_int<wide_int_ref_storage<fal#
                                                   + 1.15%
pointer_query::~pointer_query                         #
                                                     0.80%
pointer_query::pointer_query                          #
                                                     0.78% compute_objsize_r   
                                 #
                                             - 14.08% (anonymous
namespace)::pointers_related_p                  #
                                                + 6.14% access_ref::access_ref 
                                 #
                                                + 4.53% pointer_query::get_ref 
                                 #
                                                + 2.07% ptr_derefs_may_alias_p 
                                 #
                                             + 3.70% access_ref::access_ref    
                                 #
                                          + 25.03% pointer_query::get_ref      
                                 #
                                       + 4.04% pointer_query::get_ref

[Bug tree-optimization/109539] [13/14 Regression] Compile-time hog in gimple-ssa-warn-access.cc since r13-6706-gadb70c2d1060b3

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
So what we try to do is, when check_pointer_uses follows the use chain
of 'ptr' through say

 ptr2 = ptr + 4;

then it wants to visit ptr2 uses as well.  For PHIs we get to

 ptr2 = PHI <..., ptr, ...>;

and we want to consider uses of ptr2 only if all other PHI arguments
are "related" to 'ptr'.  To prove that we perform complicated gymnastics,
in particular the only real check done is

  if (!ptr_derefs_may_alias_p (p, q))
    return false;

and that's of course incredibly weak.  To disprove relatedness
the pointers_related_p recurses, but only when either of both
pointers are defined by a PHI.  It uses pointer-query to skip
chains of pointer adjustments up to such definition.

So we basically do forward relatedness in check_pointer_uses and
then backward relatedness in pointers_related_p.

I think we should eschew that completely and only try to handle "forward"
PHIs by the iteration in check_pointer_uses itself.

[Bug tree-optimization/109539] [13/14 Regression] Compile-time hog in gimple-ssa-warn-access.cc since r13-6706-gadb70c2d1060b3

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Richard Biener <rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:fdbaab2dc886f78a1e75512eeee0faa17e77c862

commit r14-30-gfdbaab2dc886f78a1e75512eeee0faa17e77c862
Author: Richard Biener <rguenther@suse.de>
Date:   Tue Apr 18 11:49:48 2023 +0200

    tree-optimization/109539 - restrict PHI handling in access diagnostics

    Access diagnostics visits the SSA def-use chains to diagnose things like
    dangling pointer uses.  When that runs into PHIs it tries to prove
    all incoming pointers of which one is the currently visited use are
    related to decide whether to keep looking for the PHI def uses.
    That turns out to be overly optimistic and thus costly.  The following
    scraps the existing handling for simply requiring that we eventually
    visit all incoming pointers of the PHI during the def-use chain
    analysis and only then process uses of the PHI def.

    Note this handles backedges of natural loops optimistically, diagnosing
    the first iteration.  There's gcc.dg/Wuse-after-free-2.c containing
    a testcase requiring this.

            PR tree-optimization/109539
            * gimple-ssa-warn-access.cc (pass_waccess::check_pointer_uses):
            Re-implement pointer relatedness for PHIs.

[Bug tree-optimization/109539] [13/14 Regression] Compile-time hog in gimple-ssa-warn-access.cc since r13-6706-gadb70c2d1060b3

[cvs-commit at gcc dot gnu.org]

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

--- Comment #6 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-13 branch has been updated by Richard Biener
<rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:68aea7801848f978f8b5461807dfd3b7a504da1e

commit r13-7215-g68aea7801848f978f8b5461807dfd3b7a504da1e
Author: Richard Biener <rguenther@suse.de>
Date:   Tue Apr 18 11:49:48 2023 +0200

    tree-optimization/109539 - restrict PHI handling in access diagnostics

    Access diagnostics visits the SSA def-use chains to diagnose things like
    dangling pointer uses.  When that runs into PHIs it tries to prove
    all incoming pointers of which one is the currently visited use are
    related to decide whether to keep looking for the PHI def uses.
    That turns out to be overly optimistic and thus costly.  The following
    scraps the existing handling for simply requiring that we eventually
    visit all incoming pointers of the PHI during the def-use chain
    analysis and only then process uses of the PHI def.

    Note this handles backedges of natural loops optimistically, diagnosing
    the first iteration.  There's gcc.dg/Wuse-after-free-2.c containing
    a testcase requiring this.

            PR tree-optimization/109539
            * gimple-ssa-warn-access.cc (pass_waccess::check_pointer_uses):
            Re-implement pointer relatedness for PHIs.

    (cherry picked from commit fdbaab2dc886f78a1e75512eeee0faa17e77c862)

[Bug tree-optimization/109539] [13/14 Regression] Compile-time hog in gimple-ssa-warn-access.cc since r13-6706-gadb70c2d1060b3

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.