[Bug middle-end/38474] compile time explosion in dataflow_set_preserve_mem_locs at -O3

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

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=38474

--- Comment #74 from Richard Biener <rguenth at gcc dot gnu.org> 2013-03-07 14:55:27 UTC ---
(In reply to comment #73)
> On trunk with the reduced testcase I now see PTA taking 90% of compile-time ...
> 
> Argh.

I can speed it up by

@@ -1631,7 +1619,20 @@ do_sd_constraint (constraint_graph_t gra
            flag |= bitmap_set_bit (sol, escaped_id);
          else if (v->may_have_pointers
                   && add_graph_edge (graph, lhs, t))
-           flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
+           {
+             /* For transitive closures, x = *(x + UNKNOWN), delay
+                propagation of the solution across the added edges
+                by marking sources as changed.  */
+             if (lhs == c->rhs.var)
+               {
+                 bitmap_set_bit (changed, t);
+                 flag |= true;
+               }
+             /* Else speedup solving by doing that here to save
+                iterations.  */
+             else
+               flag |= bitmap_ior_into (sol, get_varinfo (t)->solution);
+           }

          /* If the variable is not exactly at the requested offset
             we have to include the next one.  */

as repeatedly walking all of 'sol' for 'sol = *(sol + UNKNOWN)' when
adding the solution of one of delta(sol)'s member is slow.  Using
a temporary bitmap to collect all changes doesn't speed it up though,
so the only effect of the above is that the forwarding is delayed until
the next solver iteration (where eventually we discover and eliminate
more indirect cycles).