https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114855
--- Comment #43 from Richard Biener <rguenth at gcc dot gnu.org> ---
Thanks for the work sofar. It seems the back_jt_path_registry::update_cfg
has a "dead" guard against un-adjust_paths_after_duplication paths with
its tracking visited_starting_edges, so for the purpose of limiting
complexity we can do sth like
diff --git a/gcc/tree-ssa-threadupdate.cc b/gcc/tree-ssa-threadupdate.cc
index c88cc1d6aac..88e7290db61 100644
--- a/gcc/tree-ssa-threadupdate.cc
+++ b/gcc/tree-ssa-threadupdate.cc
@@ -2292,8 +2292,11 @@ back_jt_path_registry::adjust_paths_after_duplication
(unsigned curr_path_num)
{
vec<jump_thread_edge *> *curr_path = m_paths[curr_path_num];
- /* Iterate through all the other paths and adjust them. */
- for (unsigned cand_path_num = 0; cand_path_num < m_paths.length (); )
+ /* Iterate through all the other paths and adjust them.
+ ??? Limit the linear search so we do not run into quadratic
+ behavior (see PR114855). */
+ for (unsigned cand_path_num = 0;
+ cand_path_num < std::min (m_paths.length (), 1024u);)
{
if (cand_path_num == curr_path_num)
{
I measured no difference from disabling the merging (didn't try even
larger limits).
As for addressing the problem with "sorting", I think we should see to
order the jump threads in optimal order which should generally be RPO
of the entry edges and in case of multiple paths with the same entry
(the case adjust_paths_after_duplication is concerned with), we should
order those longest-to-shortes.
I believe all other order issues should be non-existent but we can end
up cancelling paths when we do the order wrong for same-entry paths.
Eventually adjusting the path_commpare sort function in your patch to
further order paths after e->dest->index and .length () would fix the
observed regressions.
Oddly your patch-set increases DOM time two-fold?
