[Bug tree-optimization/98866] New: [11 Regresion] Compile time hog in VRP since r11-3685-gfcae5121154d1c33

[Bug tree-optimization/98866] New: [11 Regresion] Compile time hog in VRP since r11-3685-gfcae5121154d1c33

[marxin at gcc dot gnu.org]

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

            Bug ID: 98866
           Summary: [11 Regresion] Compile time hog in VRP since
                    r11-3685-gfcae5121154d1c33
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Keywords: compile-time-hog
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: marxin at gcc dot gnu.org
                CC: aldyh at gcc dot gnu.org, amacleod at redhat dot com
  Target Milestone: ---

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

Since the revision, 

g++ -Ofast -fno-checking pr12392.cpp -c

is slower by about 50%. Note that the source file comes from a different
compile time hog PR.

[Bug tree-optimization/98866] [11 Regresion] Compile time hog in VRP since r11-3685-gfcae5121154d1c33

[amacleod at redhat dot com]

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

--- Comment #1 from Andrew Macleod <amacleod at redhat dot com> ---
Very large function (16000+ basic blocks) with a lot of exception regions, and
a pattern whereby about 300 pointers are live to all the regions. We spend a
lot of time propagating an unchanging non-zero property around. 

My observation is that if a pointer evaluates to [1, +INF] at its definition
(ie, the address of something), there will never be a meaningful range to
track.

a comparison to NULL will be folded as appropriate, and there is no need to
track [UNDEFINED] on the un-taken edge as the branch will be folded and the
edge removed.  The range will remain [1, +INF] on the other edge.

a comparison to some other pointer will likewise not result in a  change of the
range [1, +INF].  Relational/symbolic tracking could decide to fold the
comparison away or propagate the ssa_name, but again, it will not change the
range from [1, +INF]

I think I can extend the invariant tweak to the cache to also include pointers
which evaluate to [1, +INF] at their definition to be "invariant" as well and
thus not be included in the on-entry cache.

This appears to resolve the time issue.  testing is underway

[Bug tree-optimization/98866] [11 Regresion] Compile time hog in VRP since r11-3685-gfcae5121154d1c33

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.0

[Bug tree-optimization/98866] [11 Regresion] Compile time hog in VRP since r11-3685-gfcae5121154d1c33

[cvs-commit at gcc dot gnu.org]

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

--- Comment #2 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Andrew Macleod <amacleod@gcc.gnu.org>:

https://gcc.gnu.org/g:2dd1f944547eb6560c3e15a4b705ae1ac236df75

commit r11-6982-g2dd1f944547eb6560c3e15a4b705ae1ac236df75
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Fri Jan 29 09:23:48 2021 -0500

    tree-optimization/98866 - Compile time hog in VRP

    Don't track [1, +INF] for pointer types, treat them as invariant for
caching
    purposes as they cannot be further refined without evaluating to UNDEFINED.

            PR tree-optimization/98866
            * gimple-range-gori.h (gori_compute:set_range_invariant): New.
            * gimple-range-gori.cc (gori_map::set_range_invariant): New.
            (gori_map::m_maybe_invariant): Rename from all_outgoing.
            (gori_map::gori_map): Rename all_outgoing to m_maybe_invariant.
            (gori_map::is_export_p): Ditto.
            (gori_map::calculate_gori): Ditto.
            (gori_compute::set_range_invariant): New.
            * gimple-range.cc (gimple_ranger::range_of_stmt): Set range
            invariant for pointers evaluating to [1, +INF].

[Bug tree-optimization/98866] [11 Regresion] Compile time hog in VRP since r11-3685-gfcae5121154d1c33

[amacleod at redhat dot com]

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

Andrew Macleod <amacleod at redhat dot com> changed:

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

--- Comment #3 from Andrew Macleod <amacleod at redhat dot com> ---
This should resolve the issue.

[Bug tree-optimization/98866] [11 Regresion] Compile time hog in VRP since r11-3685-gfcae5121154d1c33

[marxin at gcc dot gnu.org]

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

--- Comment #4 from Martin Liška <marxin at gcc dot gnu.org> ---
Thanks for the fix.