re PR middle-end/90726 (exponential behavior on SCEV results everywhere)

2019-06-04  Richard Biener  <rguenther@suse.de>

	PR middle-end/90726
	* tree-chrec.c (chrec_contains_symbols): Add to visited.
	(tree_contains_chrecs): Likewise.
	(chrec_contains_symbols_defined_in_loop): Move here and avoid
	exponential behaivor from ...
	* tree-scalar-evolution.c (chrec_contains_symbols_defined_in_loop):
	... here.
	(expression_expensive_p): Avoid exponential behavior and compute
	expanded size, rejecting any expansion.
	* tree-ssa-loop-ivopts.c (abnormal_ssa_name_p): Remove.
	(idx_contains_abnormal_ssa_name_p): Likewise.
	(contains_abnormal_ssa_name_p_1): New helper for walk_tree.
	(contains_abnormal_ssa_name_p): Simplify and use
	walk_tree_without_duplicates.

	* gcc.dg/pr90726.c: New testcase.

From-SVN: r271903

1 files changed, 65 insertions, 0 deletions

diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c
index 813b87f..f50fd20 100644
--- a/gcc/tree-chrec.c
+++ b/gcc/tree-chrec.c
@@ -35,6 +35,8 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-ssa-loop-ivopts.h"
 #include "tree-ssa-loop-niter.h"
 #include "tree-chrec.h"
+#include "gimple.h"
+#include "tree-ssa-loop.h"
 #include "dumpfile.h"
 #include "params.h"
 #include "tree-scalar-evolution.h"
@@ -959,6 +961,9 @@ chrec_contains_symbols (const_tree chrec, hash_set<const_tree> &visited,
       && flow_loop_nested_p (get_chrec_loop (chrec), loop))
     return true;
 
+  if (visited.add (chrec))
+    return false;
+
   n = TREE_OPERAND_LENGTH (chrec);
   for (i = 0; i < n; i++)
     if (chrec_contains_symbols (TREE_OPERAND (chrec, i), visited, loop))
@@ -978,6 +983,63 @@ chrec_contains_symbols (const_tree chrec, struct loop* loop)
   return chrec_contains_symbols (chrec, visited, loop);
 }
 
+/* Return true when CHREC contains symbolic names defined in
+   LOOP_NB.  */
+
+static bool
+chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb,
+					hash_set<const_tree> &visited)
+{
+  int i, n;
+
+  if (chrec == NULL_TREE)
+    return false;
+
+  if (is_gimple_min_invariant (chrec))
+    return false;
+
+  if (TREE_CODE (chrec) == SSA_NAME)
+    {
+      gimple *def;
+      loop_p def_loop, loop;
+
+      if (SSA_NAME_IS_DEFAULT_DEF (chrec))
+	return false;
+
+      def = SSA_NAME_DEF_STMT (chrec);
+      def_loop = loop_containing_stmt (def);
+      loop = get_loop (cfun, loop_nb);
+
+      if (def_loop == NULL)
+	return false;
+
+      if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
+	return true;
+
+      return false;
+    }
+
+  if (visited.add (chrec))
+    return false;
+
+  n = TREE_OPERAND_LENGTH (chrec);
+  for (i = 0; i < n; i++)
+    if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
+						loop_nb, visited))
+      return true;
+  return false;
+}
+
+/* Return true when CHREC contains symbolic names defined in
+   LOOP_NB.  */
+
+bool
+chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
+{
+  hash_set<const_tree> visited;
+  return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited);
+}
+
 /* Determines whether the chrec contains undetermined coefficients.  */
 
 static bool
@@ -1026,6 +1088,9 @@ tree_contains_chrecs (const_tree expr, int *size, hash_set<const_tree> &visited)
   if (tree_is_chrec (expr))
     return true;
 
+  if (visited.add (expr))
+    return false;
+
   n = TREE_OPERAND_LENGTH (expr);
   for (i = 0; i < n; i++)
     if (tree_contains_chrecs (TREE_OPERAND (expr, i), size, visited))