https://gcc.gnu.org/bugzilla/show_bug.cgi?id=72851
--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Ok, so with clever stmt / SSA use ordering you can get to quadratic propagation
as VRP allows ranges to arbitrarily grow:
Found new range for res_561: [0, 20368]
Found new range for res_561: [0, 20370]
Found new range for res_561: [0, 20372]
Found new range for res_561: [0, 20374]
Found new range for res_561: [0, 20376]
Found new range for res_561: [0, 20378]
Found new range for res_561: [0, 20380]
Found new range for res_561: [0, 20382]
Found new range for res_561: [0, 20384]
Found new range for res_561: [0, 20386]
Found new range for res_561: [0, 20388]
Found new range for res_561: [0, 20390]
Found new range for res_561: [0, 20392]
Found new range for res_561: [0, 20394]
Found new range for res_561: [0, 20396]
...
the SSA worklist in the SSA propagator is just a stack that is pushed/popped
to/from.
Ideally that worklist would be processed in stmt order but that requires
sorting the worklist vector or changing the worklist data structure to
sth "better" (a balanced tree?). Slightly "randomizing" the worklist
processing, say by
Index: gcc/tree-ssa-propagate.c
===================================================================
--- gcc/tree-ssa-propagate.c (revision 238469)
+++ gcc/tree-ssa-propagate.c (working copy)
@@ -422,7 +422,8 @@ process_ssa_edge_worklist (vec<gimple *>
basic_block bb;
/* Pull the statement to simulate off the worklist. */
- gimple *stmt = worklist->pop ();
+ gimple *stmt = (*worklist)[0];
+ worklist->unordered_remove (0);
/* If this statement was already visited by simulate_block, then
we don't need to visit it again here. */
fixes the testcase. Of course it's just a matter of pure luck that it
re-appears (with the current processing order it's just most likely given
its depth-first processing nature). Picking a truly random element from
the worklist would be better than the above (but truly random has to be
predictable to not break bootstrap).
