[Bug tree-optimization/61515] [4.9/5 Regression] Extremely long compile time for generated code

["rguenth at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>]

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

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to rguenther@suse.de from comment #13)
> On Tue, 17 Jun 2014, law at redhat dot com wrote:
> 
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61515
> > 
> > Jeffrey A. Law <law at redhat dot com> changed:
> > 
> >            What    |Removed                     |Added
> > ----------------------------------------------------------------------------
> >                  CC|                            |law at redhat dot com
> >            Assignee|unassigned at gcc dot gnu.org      |law at redhat dot com
> > 
> > --- Comment #12 from Jeffrey A. Law <law at redhat dot com> ---
> > Fundamentally we don't have a way to know what equivalences we need to
> > invalidate.
> > Invalidation is, umm, painful.  The question in my mind is why are we getting
> > so many invalidations to start with.  That's the first thing to look at.
> 
> Well, it's easy to avoid the quadraticness - you can always create 
> testcases that need a lot of invalidates.  But the current algorithm
> really does not scale.
> 
> > Honestly though, I really wonder if handling backedges is worth the effort,
> > even though it's important for one benchmark.
> 
> Not sure about that, but trivial improvements to the scalability are
> possible here.  Walking all SSA names is O(number of stmts) - if you
> do that O(number of stmts) time (as you do) that's clearly the bug.

Sth like (untested)

Index: tree-ssa-threadedge.c
===================================================================
        --- tree-ssa-threadedge.c       (revision 216464)
+++ tree-ssa-threadedge.c       (working copy)
@@ -287,20 +287,6 @@ fold_assignment_stmt (gimple stmt)
     }
 }

-/* A new value has been assigned to LHS.  If necessary, invalidate any
-   equivalences that are no longer valid.  */
-static void
-invalidate_equivalences (tree lhs, vec<tree> *stack)
-{
-
-  for (unsigned int i = 1; i < num_ssa_names; i++)
-    if (ssa_name (i) && SSA_NAME_VALUE (ssa_name (i)) == lhs)
-      record_temporary_equivalence (ssa_name (i), NULL_TREE, stack);
-
-  if (SSA_NAME_VALUE (lhs))
-    record_temporary_equivalence (lhs, NULL_TREE, stack);
-}
-
 /* Try to simplify each statement in E->dest, ultimately leading to
    a simplification of the COND_EXPR at the end of E->dest.

@@ -335,6 +321,8 @@ record_temporary_equivalences_from_stmts
      we discover.  Note any equivalences we discover are context
      sensitive (ie, are dependent on traversing E) and must be unwound
      when we're finished processing E.  */
+  sbitmap to_invalidate = sbitmap_alloc (num_ssa_names);
+  bitmap_clear (to_invalidate);
   for (gsi = gsi_start_bb (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
     {
       tree cached_lhs = NULL;
@@ -379,7 +367,7 @@ record_temporary_equivalences_from_stmts

          if (backedge_seen)
            FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
-             invalidate_equivalences (op, stack);
+             bitmap_set_bit (to_invalidate, SSA_NAME_VERSION (op));

          continue;
        }
@@ -419,7 +407,7 @@ record_temporary_equivalences_from_stmts
              if (backedge_seen)
                {
                  tree lhs = gimple_get_lhs (stmt);
-                 invalidate_equivalences (lhs, stack);
+                 bitmap_set_bit (to_invalidate, SSA_NAME_VERSION (lhs));
                }
              continue;
            }
@@ -497,8 +485,24 @@ record_temporary_equivalences_from_stmts
              || is_gimple_min_invariant (cached_lhs)))
        record_temporary_equivalence (gimple_get_lhs (stmt), cached_lhs,
stack);
       else if (backedge_seen)
-       invalidate_equivalences (gimple_get_lhs (stmt), stack);
+       bitmap_set_bit (to_invalidate,
+                       SSA_NAME_VERSION (gimple_get_lhs (stmt)));
     }
+
+  /* Now invalidate all equivalencies we have to invalidate.  */
+  unsigned i;
+  sbitmap_iterator bi;
+  EXECUTE_IF_SET_IN_BITMAP (to_invalidate, 0, i, bi)
+    {
+      tree name = ssa_name (i);
+      record_temporary_equivalence (name, NULL_TREE, stack);
+
+      if (name)
+       record_temporary_equivalence (name, NULL_TREE, stack);
+    }
+
+  sbitmap_free (to_invalidate);
+
   return stmt;
 }