[gcc r11-6982] tree-optimization/98866 - Compile time hog in VRP

[gcc r11-6982] tree-optimization/98866 - Compile time hog in VRP

[Andrew Macleod]

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].

Diff:
---
 gcc/gimple-range-gori.cc | 27 ++++++++++++++++++++++-----
 gcc/gimple-range-gori.h  |  1 +
 gcc/gimple-range.cc      |  6 ++++++
 3 files changed, 29 insertions(+), 5 deletions(-)

diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
index 65faa2d24d4..7f7f3dc0d69 100644
--- a/gcc/gimple-range-gori.cc
+++ b/gcc/gimple-range-gori.cc
@@ -232,13 +232,14 @@ public:
   bool is_export_p (tree name, basic_block bb = NULL);
   bool def_chain_in_export_p (tree name, basic_block bb);
   bitmap exports (basic_block bb);
+  void set_range_invariant (tree name);
 
   void dump (FILE *f);
   void dump (FILE *f, basic_block bb);
 private:
   bitmap_obstack m_bitmaps;
   vec<bitmap> m_outgoing;	// BB: Outgoing ranges calculatable on edges
-  bitmap all_outgoing;		// All outgoing ranges combined. 
+  bitmap m_maybe_variant;	// Names which might have outgoing ranges.
   void maybe_add_gori (tree name, basic_block bb);
   void calculate_gori (basic_block bb);
 };
@@ -251,7 +252,7 @@ gori_map::gori_map ()
   m_outgoing.create (0);
   m_outgoing.safe_grow_cleared (last_basic_block_for_fn (cfun));
   bitmap_obstack_initialize (&m_bitmaps);
-  all_outgoing = BITMAP_ALLOC (&m_bitmaps);
+  m_maybe_variant = BITMAP_ALLOC (&m_bitmaps);
 }
 
 // Free any memory the GORI map allocated.
@@ -280,10 +281,18 @@ gori_map::is_export_p (tree name, basic_block bb)
 {
   // If no BB is specified, test if it is exported anywhere in the IL.
   if (!bb)
-    return bitmap_bit_p (all_outgoing, SSA_NAME_VERSION (name));
+    return bitmap_bit_p (m_maybe_variant, SSA_NAME_VERSION (name));
   return bitmap_bit_p (exports (bb), SSA_NAME_VERSION (name));
 }
 
+// Clear the m_maybe_variant bit so ranges will not be tracked for NAME.
+
+void
+gori_map::set_range_invariant (tree name)
+{
+  bitmap_clear_bit (m_maybe_variant, SSA_NAME_VERSION (name));
+}
+
 // Return true if any element in the def chain of NAME is in the
 // export list for BB.
 
@@ -348,7 +357,7 @@ gori_map::calculate_gori (basic_block bb)
       maybe_add_gori (name, gimple_bb (stmt));
     }
   // Add this bitmap to the aggregate list of all outgoing names.
-  bitmap_ior_into (all_outgoing, m_outgoing[bb->index]);
+  bitmap_ior_into (m_maybe_variant, m_outgoing[bb->index]);
 }
 
 // Dump the table information for BB to file F.
@@ -447,7 +456,7 @@ gori_compute::gori_compute ()
   m_gori_map = new gori_map;
   unsigned x, lim = last_basic_block_for_fn (cfun);
   // Calculate outgoing range info upfront.  This will fully populate the
-  // all_outgoing bitmap which will help eliminate processing of names
+  // m_maybe_variant bitmap which will help eliminate processing of names
   // which never have their ranges adjusted.
   for (x = 0; x < lim ; x++)
     {
@@ -996,6 +1005,14 @@ gori_compute::has_edge_range_p (tree name, edge e)
 	  || m_gori_map->def_chain_in_export_p (name, e->src));
 }
 
+// Clear the m_maybe_variant bit so ranges will not be tracked for NAME.
+
+void
+gori_compute::set_range_invariant (tree name)
+{
+  m_gori_map->set_range_invariant (name);
+}
+
 // Dump what is known to GORI computes to listing file F.
 
 void
diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h
index 3b9db0d406b..48c746d1f37 100644
--- a/gcc/gimple-range-gori.h
+++ b/gcc/gimple-range-gori.h
@@ -72,6 +72,7 @@ public:
   ~gori_compute ();
   bool outgoing_edge_range_p (irange &r, edge e, tree name);
   bool has_edge_range_p (tree name, edge e = NULL);
+  void set_range_invariant (tree name);
   void dump (FILE *f);
 protected:
   virtual void ssa_range_in_bb (irange &r, tree name, basic_block bb);
diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index 029aaa58640..6158a754dd6 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -1072,6 +1072,12 @@ gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name)
   // can sometimes get different results.  See PR 97741.
   r.intersect (tmp);
   m_cache.set_global_range (name, r);
+
+  // Pointers which resolve to non-zero at the defintion point do not need
+  // tracking in the cache as they will never change.  See PR 98866.
+  if (POINTER_TYPE_P (TREE_TYPE (name)) && r.nonzero_p ())
+    m_cache.set_range_invariant (name);
+
   return true;
 }