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

[rguenth at gcc dot gnu.org]

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

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
All time is spent in invalidate_equivalencies.

/* 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);
}

this is obviously quadratic ... nearly all calls are from

static gimple
record_temporary_equivalences_from_stmts_at_dest (edge e,
                                                  vec<tree> *stack,
                                                  tree (*simplify) (gimple,
                                                                    gimple),
                                                  bool backedge_seen)
{
...
      else if (backedge_seen)
        invalidate_equivalences (gimple_get_lhs (stmt), stack);
    }
  return stmt;
}

I think you should record a bitmap of SSA names you need to invalidate
equivalences to and only at the end of this do a single scan over all SSA
names.