[gcc(refs/users/aoliva/heads/testme)] [PR105665] ivopts: check defs of names in base for undefs

[Alexandre Oliva <aoliva@gcc.gnu.org>]

https://gcc.gnu.org/g:7ed250b1b302b05171cd5d670cb326f27d89bef0

commit 7ed250b1b302b05171cd5d670cb326f27d89bef0
Author: Alexandre Oliva <oliva@adacore.com>
Date:   Thu May 26 09:38:31 2022 -0300

    [PR105665] ivopts: check defs of names in base for undefs
    
    The patch for PR 100810 tested for undefined SSA_NAMEs appearing
    directly in the base expression of the potential IV candidate, but
    that's not enough.  The testcase for PR105665 shows an undefined
    SSA_NAME has the same ill effect if it's referenced as an PHI_NODE arg
    in the referenced SSA_NAME.  The variant of that test shows it can be
    further removed from the referenced SSA_NAME.
    
    Turning the test for undefined SSA_NAMES into a recursive search,
    skipping cycles and other duplicates, avoids the problem.
    
    
    for  gcc/ChangeLog
    
            PR tree-optimization/105665
            PR tree-optimization/100810
            * tree-ssa-loop-ivopts.cc (find_ssa_undef): Take pointer set
            as argument, use it to avoid duplicates.  Recurse on SSA_NAMEs
            mentioned in each def.
            (add_candidate_1): Start the search with an empty pointer set.
    
    for  gcc/testsuite/ChangeLog
    
            PR tree-optimization/105665
            PR tree-optimization/100810
            * gcc.dg/torture/pr105665.c: New.

Diff:
---
 gcc/testsuite/gcc.dg/torture/pr105665.c | 20 +++++++++++++
 gcc/tree-ssa-loop-ivopts.cc             | 52 +++++++++++++++++++++++++++++----
 2 files changed, 66 insertions(+), 6 deletions(-)

diff --git a/gcc/testsuite/gcc.dg/torture/pr105665.c b/gcc/testsuite/gcc.dg/torture/pr105665.c
new file mode 100644
index 00000000000..34cfc658434
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr105665.c
@@ -0,0 +1,20 @@
+/* { dg-do run } */
+
+int a, b, c[1], d[2], *e = c;
+int main() {
+  int f = 0;
+  for (; b < 2; b++) {
+    int g;
+    if (f)
+      g++, b = 40;
+    a = d[b * b];
+    for (f = 0; f < 3; f++) {
+      if (e)
+        break;
+      g--;
+      if (a)
+        a = g;
+    }
+  }
+  return 0;
+}
diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 81b536f9304..8902702cbbb 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3071,14 +3071,53 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
   return *slot;
 }
 
-/* Find the first undefined SSA name in *TP.  */
+/* Find the first undefined SSA name in *TP.  Use PSET_, a
+   hash_set<tree>*, to avoid cycles and to skip other duplicates.  */
 
 static tree
-find_ssa_undef (tree *tp, int *walk_subtrees, void *)
+find_ssa_undef (tree *tp, int *walk_subtrees, void *pset_)
 {
-  if (TREE_CODE (*tp) == SSA_NAME
-      && ssa_undefined_value_p (*tp, false))
-    return *tp;
+  auto pset = static_cast<hash_set<tree> *> (pset_);
+
+  if (TREE_CODE (*tp) == SSA_NAME)
+    {
+      if (ssa_defined_default_def_p (*tp))
+	return NULL;
+
+      if (ssa_undefined_value_p (*tp, false))
+	return *tp;
+
+      /* If we've already visited this SSA_NAME and got to it again,
+	 we know we didn't find it to be undefined, otherwise we'd
+	 have stopped the walk then.  */
+      if (pset && pset->add (*tp))
+	return NULL;
+
+      gimple *def_stmt = SSA_NAME_DEF_STMT (*tp);
+      /* ssa_undefined_value_p must have caught nop defs above.  */
+      gcc_checking_assert (!gimple_nop_p (def_stmt));
+
+      /* No need to follow these: uses' undefinedness does not
+	 propagate to defs.  ??? Even inlined calls?  */
+      if (is_gimple_call (def_stmt) || is_a <gasm *> (def_stmt))
+	return NULL;
+      gcc_checking_assert (is_gimple_assign (def_stmt)
+			   || is_a <gphi *> (def_stmt));
+
+      ssa_op_iter iter;
+      use_operand_p use_p;
+
+      FOR_EACH_PHI_OR_STMT_USE (use_p, def_stmt, iter, SSA_OP_USE)
+	{
+	  tree use = USE_FROM_PTR (use_p);
+
+	  int wsub = 1;
+	  tree result = find_ssa_undef (&use, &wsub, pset);
+	  if (result)
+	    return result;
+	}
+    }
+
   if (!EXPR_P (*tp))
     *walk_subtrees = 0;
   return NULL;
@@ -3114,7 +3153,8 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
   /* If BASE contains undefined SSA names make sure we only record
      the original IV.  */
   bool involves_undefs = false;
-  if (walk_tree (&base, find_ssa_undef, NULL, NULL))
+  hash_set<tree> pset;
+  if (walk_tree (&base, find_ssa_undef, &pset, NULL))
     {
       if (pos != IP_ORIGINAL)
 	return NULL;