https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61515
--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> --- (In reply to rguent...@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; }