From 4efd8968f8bf48265f18022b4eda5e7a99c24445 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Wed, 17 Jul 2019 11:21:49 +0000 Subject: re PR tree-optimization/91178 (Infinite recursion in split_constant_offset in slp after r260289) 2019-07-17 Richard Biener PR tree-optimization/91178 * tree-ssa.c (release_defs_bitset): Iterate from higher to lower SSA names to avoid quadratic behavior in the common case. * tree-data-ref.c (split_constant_offset): Add limit argument and pass it down. Initialize it from PARAM_SSA_NAME_DEF_CHAIN_LIMIT. (split_constant_offset_1): Add limit argument and use it to limit SSA def walking. Optimize the common plus/minus case. From-SVN: r273550 --- gcc/tree-ssa.c | 36 +++++++++++++++++++++--------------- 1 file changed, 21 insertions(+), 15 deletions(-) (limited to 'gcc/tree-ssa.c') diff --git a/gcc/tree-ssa.c b/gcc/tree-ssa.c index 16eaa8e..b4b5c90 100644 --- a/gcc/tree-ssa.c +++ b/gcc/tree-ssa.c @@ -559,20 +559,25 @@ release_defs_bitset (bitmap toremove) /* Performing a topological sort is probably overkill, this will most likely run in slightly superlinear time, rather than the - pathological quadratic worst case. */ + pathological quadratic worst case. + But iterate from max SSA name version to min one because + that mimics allocation order during code generation behavior best. + Use an array for this which we compact on-the-fly with a NULL + marker moving towards the end of the vector. */ + auto_vec names; + names.reserve (bitmap_count_bits (toremove) + 1); + names.quick_push (NULL_TREE); + EXECUTE_IF_SET_IN_BITMAP (toremove, 0, j, bi) + names.quick_push (ssa_name (j)); + + bitmap_tree_view (toremove); while (!bitmap_empty_p (toremove)) { - unsigned to_remove_bit = -1U; - EXECUTE_IF_SET_IN_BITMAP (toremove, 0, j, bi) + j = names.length () - 1; + for (unsigned i = names.length () - 1; names[i];) { - if (to_remove_bit != -1U) - { - bitmap_clear_bit (toremove, to_remove_bit); - to_remove_bit = -1U; - } - bool remove_now = true; - tree var = ssa_name (j); + tree var = names[i]; gimple *stmt; imm_use_iterator uit; @@ -617,14 +622,15 @@ release_defs_bitset (bitmap toremove) gsi_remove (&gsi, true); release_defs (def); } - - to_remove_bit = j; + bitmap_clear_bit (toremove, SSA_NAME_VERSION (var)); } + else + --i; + if (--j != i) + names[i] = names[j]; } - if (to_remove_bit != -1U) - bitmap_clear_bit (toremove, to_remove_bit); } - + bitmap_list_view (toremove); } /* Disable warnings about missing quoting in GCC diagnostics for -- cgit v1.1