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

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

[Alexandre Oliva]

https://gcc.gnu.org/g:38cb5568ce3b8bfae001df066f5c5e9d1a7fe649

commit 38cb5568ce3b8bfae001df066f5c5e9d1a7fe649
Author: Alexandre Oliva <oliva@adacore.com>
Date:   Thu May 26 09:15:53 2022 -0300

    [PR105665] ivopts: check defs of names in base for undefs

Diff:
---
 gcc/testsuite/gcc.dg/torture/pr105665.c |  2 +-
 gcc/tree-ssa-loop-ivopts.cc             | 19 +++++++++++++++----
 2 files changed, 16 insertions(+), 5 deletions(-)

diff --git a/gcc/testsuite/gcc.dg/torture/pr105665.c b/gcc/testsuite/gcc.dg/torture/pr105665.c
index 12f0b78a4b4..34cfc658434 100644
--- a/gcc/testsuite/gcc.dg/torture/pr105665.c
+++ b/gcc/testsuite/gcc.dg/torture/pr105665.c
@@ -6,7 +6,7 @@ int main() {
   for (; b < 2; b++) {
     int g;
     if (f)
-      b = 40;
+      g++, b = 40;
     a = d[b * b];
     for (f = 0; f < 3; f++) {
       if (e)
diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 2e8cd486cc0..e68968efc5f 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3074,10 +3074,18 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
 /* Find the first undefined SSA name in *TP.  */
 
 static tree
-find_ssa_undef (tree *tp, int *walk_subtrees, void *)
+find_ssa_undef (tree *tp, int *walk_subtrees, void *pset_)
 {
+  auto pset = static_cast<hash_set<tree> *> (pset_);
+
   if (TREE_CODE (*tp) == SSA_NAME)
     {
+      /* 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;
+
       if (ssa_undefined_value_p (*tp, false))
 	return *tp;
 
@@ -3092,8 +3100,10 @@ find_ssa_undef (tree *tp, int *walk_subtrees, void *)
 	{
 	  tree use = USE_FROM_PTR (use_p);
 
-	  if (ssa_undefined_value_p (use, false))
-	    return use;
+	  int wsub = 1;
+	  tree result = find_ssa_undef (&use, &wsub, pset);
+	  if (result)
+	    return result;
 	}
     }
 
@@ -3132,7 +3142,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;

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

[Alexandre Oliva]

https://gcc.gnu.org/g:58da319e5e66673ffcb77eecfc8e8a0f2f78ed60

commit 58da319e5e66673ffcb77eecfc8e8a0f2f78ed60
Author: Alexandre Oliva <oliva@adacore.com>
Date:   Wed Jun 1 19:32:38 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.
    
    To avoid deep recursion, precompute maybe-undefined SSA_NAMEs: start
    from known-undefined nonvirtual default defs, and propagate them to
    any PHI nodes reached by a maybe-undefined arg, as long as there
    aren't intervening non-PHI uses, that would imply the maybe-undefined
    name must be defined at that point, otherwise it would invoke
    undefined behavior.  Also test for intervening non-PHI uses of DEFs in
    the base expr.
    
    The test for intervening uses implemented herein relies on dominance;
    this could be further extended, regarding conditional uses in every
    path leading to a point as an unconditional use dominating that point,
    but I haven't implemented that.
    
    
    for  gcc/ChangeLog
    
            PR tree-optimization/105665
            PR tree-optimization/100810
            * tree-ssa-loop-ivopts.cc
            (ssa_name_maybe_undef_p, ssa_name_set_maybe_undef): New.
            (ssa_name_any_use_dominates_bb_p, mark_ssa_maybe_undefs): New.
            (find_ssa_undef): Check precomputed flag and intervening uses.
            (tree_ssa_iv_optimize): Call mark_ssa_maybe_undefs.
    
    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             | 125 +++++++++++++++++++++++++++++++-
 2 files changed, 141 insertions(+), 4 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..549168aebd6 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3071,13 +3071,129 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
   return *slot;
 }
 
-/* Find the first undefined SSA name in *TP.  */
+/* Return TRUE iff VAR is marked as maybe-undefined.  See
+   mark_ssa_maybe_undefs.  */
+
+static inline bool
+ssa_name_maybe_undef_p (tree var)
+{
+  gcc_checking_assert (TREE_CODE (var) == SSA_NAME);
+  return TREE_VISITED (var);
+}
+
+/* Set (or clear, depending on VALUE) VAR's maybe-undefined mark.  */
+
+static inline void
+ssa_name_set_maybe_undef (tree var, bool value = true)
+{
+  gcc_checking_assert (TREE_CODE (var) == SSA_NAME);
+  TREE_VISITED (var) = value;
+}
+
+/* Return TRUE iff there are any non-PHI uses of VAR that dominate the
+   end of BB.  If we return TRUE and BB is a loop header, then VAR we
+   be assumed to be defined within the loop, even if it is marked as
+   maybe-undefined.  */
+
+static inline bool
+ssa_name_any_use_dominates_bb_p (tree var, basic_block bb)
+{
+  imm_use_iterator iter;
+  use_operand_p use_p;
+  FOR_EACH_IMM_USE_FAST (use_p, iter, var)
+    {
+      if (is_a <gphi *> (USE_STMT (use_p))
+	  || is_gimple_debug (USE_STMT (use_p)))
+	continue;
+      basic_block dombb = gimple_bb (USE_STMT (use_p));
+      if (dominated_by_p (CDI_DOMINATORS, bb, dombb))
+	return true;
+    }
+
+  return false;
+}
+
+/* Mark as maybe_undef any SSA_NAMEs that are unsuitable as ivopts
+   candidates for potentially involving undefined behavior.  */
+
+static void
+mark_ssa_maybe_undefs (void)
+{
+  auto_vec<tree> queue;
+
+  /* Scan all SSA_NAMEs, marking the definitely-undefined ones as
+     maybe-undefined and queuing them for propagation, while clearing
+     the mark on others.  */
+  unsigned int i;
+  tree var;
+  FOR_EACH_SSA_NAME (i, var, cfun)
+    {
+      if (SSA_NAME_IS_VIRTUAL_OPERAND (var)
+	  || !ssa_undefined_value_p (var, false))
+	ssa_name_set_maybe_undef (var, false);
+      else
+	{
+	  ssa_name_set_maybe_undef (var);
+	  queue.safe_push (var);
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "marking _%i as maybe-undef\n",
+		     SSA_NAME_VERSION (var));
+	}
+    }
+
+  /* Now propagate maybe-undefined from a DEF to any other PHI that
+     uses it, as long as there isn't any intervening use of DEF.  */
+  while (!queue.is_empty ())
+    {
+      var = queue.pop ();
+      imm_use_iterator iter;
+      use_operand_p use_p;
+      FOR_EACH_IMM_USE_FAST (use_p, iter, var)
+	{
+	  /* Any uses of VAR that aren't PHI args imply VAR must be
+	     defined, otherwise undefined behavior would have been
+	     definitely invoked.  Only PHI args may hold
+	     maybe-undefined values without invoking undefined
+	     behavior for that reason alone.  */
+	  if (!is_a <gphi *> (USE_STMT (use_p)))
+	    continue;
+	  gphi *phi = as_a <gphi *> (USE_STMT (use_p));
+
+	  tree def = gimple_phi_result (phi);
+	  if (ssa_name_maybe_undef_p (def))
+	    continue;
+
+	  /* Look for any uses of the maybe-unused SSA_NAME that
+	     dominates the block that reaches the incoming block
+	     corresponding to the PHI arg in which it is mentioned.
+	     That means we can assume the SSA_NAME is defined in that
+	     path, so we only mark a PHI result as maybe-undef if we
+	     find an unused reaching SSA_NAME.  */
+	  int idx = phi_arg_index_from_use (use_p);
+	  basic_block bb = gimple_phi_arg_edge (phi, idx)->src;
+	  if (ssa_name_any_use_dominates_bb_p (var, bb))
+	    continue;
+
+	  ssa_name_set_maybe_undef (def);
+	  queue.safe_push (def);
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "marking _%i as maybe-undef because of _%i\n",
+		     SSA_NAME_VERSION (def), SSA_NAME_VERSION (var));
+	}
+    }
+}
+
+/* Return *TP if it is an SSA_NAME marked with TREE_VISITED, i.e., as
+   unsuitable as ivopts candidates for potentially involving undefined
+   behavior.  */
 
 static tree
-find_ssa_undef (tree *tp, int *walk_subtrees, void *)
+find_ssa_undef (tree *tp, int *walk_subtrees, void *bb_)
 {
+  basic_block bb = (basic_block) bb_;
   if (TREE_CODE (*tp) == SSA_NAME
-      && ssa_undefined_value_p (*tp, false))
+      && ssa_name_maybe_undef_p (*tp)
+      && !ssa_name_any_use_dominates_bb_p (*tp, bb))
     return *tp;
   if (!EXPR_P (*tp))
     *walk_subtrees = 0;
@@ -3114,7 +3230,7 @@ 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))
+  if (walk_tree (&base, find_ssa_undef, data->current_loop->header, NULL))
     {
       if (pos != IP_ORIGINAL)
 	return NULL;
@@ -8192,6 +8308,7 @@ tree_ssa_iv_optimize (void)
   auto_bitmap toremove;
 
   tree_ssa_iv_optimize_init (&data);
+  mark_ssa_maybe_undefs ();
 
   /* Optimize the loops starting with the innermost ones.  */
   for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))

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

[Alexandre Oliva]

https://gcc.gnu.org/g:2f1dfd38f0d9a7acb9c14dfbb32145822294bb53

commit 2f1dfd38f0d9a7acb9c14dfbb32145822294bb53
Author: Alexandre Oliva <oliva@adacore.com>
Date:   Wed Jun 1 19:32:38 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.
    
    To avoid deep recursion, precompute maybe-undefined SSA_NAMEs: start
    from known-undefined nonvirtual default defs, and propagate them to
    any PHI nodes reached by a maybe-undefined arg, as long as there
    aren't intervening non-PHI uses, that would imply the maybe-undefined
    name must be defined at that point, otherwise it would invoke
    undefined behavior.  Also test for intervening non-PHI uses of DEFs in
    the base expr.
    
    The test for intervening uses implemented herein relies on dominance;
    this could be further extended, regarding conditional uses in every
    path leading to a point as an unconditional use dominating that point,
    but I haven't implemented that.
    
    
    for  gcc/ChangeLog
    
            PR tree-optimization/105665
            PR tree-optimization/100810
            * tree-ssa-loop-ivopts.cc
            (ssa_name_maybe_undef_p, ssa_name_set_maybe_undef): New.
            (ssa_name_any_use_dominates_bb_p, mark_ssa_maybe_undefs): New.
            (find_ssa_undef): Check precomputed flag and intervening uses.
            (tree_ssa_iv_optimize): Call mark_ssa_maybe_undefs.
    
    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             | 124 ++++++++++++++++++++++++++++++--
 2 files changed, 140 insertions(+), 4 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..f20a985d7ca 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3071,13 +3071,128 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
   return *slot;
 }
 
-/* Find the first undefined SSA name in *TP.  */
+/* Return TRUE iff VAR is marked as maybe-undefined.  See
+   mark_ssa_maybe_undefs.  */
+
+static inline bool
+ssa_name_maybe_undef_p (tree var)
+{
+  gcc_checking_assert (TREE_CODE (var) == SSA_NAME);
+  return TREE_VISITED (var);
+}
+
+/* Set (or clear, depending on VALUE) VAR's maybe-undefined mark.  */
+
+static inline void
+ssa_name_set_maybe_undef (tree var, bool value = true)
+{
+  gcc_checking_assert (TREE_CODE (var) == SSA_NAME);
+  TREE_VISITED (var) = value;
+}
+
+/* Return TRUE iff there are any non-PHI uses of VAR that dominate the
+   end of BB.  If we return TRUE and BB is a loop header, then VAR we
+   be assumed to be defined within the loop, even if it is marked as
+   maybe-undefined.  */
+
+static inline bool
+ssa_name_any_use_dominates_bb_p (tree var, basic_block bb)
+{
+  imm_use_iterator iter;
+  use_operand_p use_p;
+  FOR_EACH_IMM_USE_FAST (use_p, iter, var)
+    {
+      if (is_a <gphi *> (USE_STMT (use_p)))
+	continue;
+      basic_block dombb = gimple_bb (USE_STMT (use_p));
+      if (dominated_by_p (CDI_DOMINATORS, bb, dombb))
+	return true;
+    }
+
+  return false;
+}
+
+/* Mark as maybe_undef any SSA_NAMEs that are unsuitable as ivopts
+   candidates for potentially involving undefined behavior.  */
+
+static void
+mark_ssa_maybe_undefs (void)
+{
+  auto_vec<tree> queue;
+
+  /* Scan all SSA_NAMEs, marking the definitely-undefined ones as
+     maybe-undefined and queuing them for propagation, while clearing
+     the mark on others.  */
+  unsigned int i;
+  tree var;
+  FOR_EACH_SSA_NAME (i, var, cfun)
+    {
+      if (SSA_NAME_IS_VIRTUAL_OPERAND (var)
+	  || !ssa_undefined_value_p (var, false))
+	ssa_name_set_maybe_undef (var, false);
+      else
+	{
+	  ssa_name_set_maybe_undef (var);
+	  queue.safe_push (var);
+	  if (dump_file)
+	    fprintf (dump_file, "marking _%i as maybe-undef\n",
+		     SSA_NAME_VERSION (var));
+	}
+    }
+
+  /* Now propagate maybe-undefined from a DEF to any other PHI that
+     uses it, as long as there isn't any intervening use of DEF.  */
+  while (!queue.is_empty ())
+    {
+      var = queue.pop ();
+      imm_use_iterator iter;
+      use_operand_p use_p;
+      FOR_EACH_IMM_USE_FAST (use_p, iter, var)
+	{
+	  /* Any uses of VAR that aren't PHI args imply VAR must be
+	     defined, otherwise undefined behavior would have been
+	     definitely invoked.  Only PHI args may hold
+	     maybe-undefined values without invoking undefined
+	     behavior for that reason alone.  */
+	  if (!is_a <gphi *> (USE_STMT (use_p)))
+	    continue;
+	  gphi *phi = as_a <gphi *> (USE_STMT (use_p));
+
+	  tree def = gimple_phi_result (phi);
+	  if (ssa_name_maybe_undef_p (def))
+	    continue;
+
+	  /* Look for any uses of the maybe-unused SSA_NAME that
+	     dominates the block that reaches the incoming block
+	     corresponding to the PHI arg in which it is mentioned.
+	     That means we can assume the SSA_NAME is defined in that
+	     path, so we only mark a PHI result as maybe-undef if we
+	     find an unused reaching SSA_NAME.  */
+	  int idx = phi_arg_index_from_use (use_p);
+	  basic_block bb = gimple_phi_arg_edge (phi, idx)->src;
+	  if (ssa_name_any_use_dominates_bb_p (var, bb))
+	    continue;
+
+	  ssa_name_set_maybe_undef (def);
+	  queue.safe_push (def);
+	  if (dump_file)
+	    fprintf (dump_file, "marking _%i as maybe-undef because of _%i\n",
+		     SSA_NAME_VERSION (def), SSA_NAME_VERSION (var));
+	}
+    }
+}
+
+/* Return *TP if it is an SSA_NAME marked with TREE_VISITED, i.e., as
+   unsuitable as ivopts candidates for potentially involving undefined
+   behavior.  */
 
 static tree
-find_ssa_undef (tree *tp, int *walk_subtrees, void *)
+find_ssa_undef (tree *tp, int *walk_subtrees, void *bb_)
 {
+  basic_block bb = (basic_block) bb_;
   if (TREE_CODE (*tp) == SSA_NAME
-      && ssa_undefined_value_p (*tp, false))
+      && ssa_name_maybe_undef_p (*tp)
+      && !ssa_name_any_use_dominates_bb_p (*tp, bb))
     return *tp;
   if (!EXPR_P (*tp))
     *walk_subtrees = 0;
@@ -3114,7 +3229,7 @@ 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))
+  if (walk_tree (&base, find_ssa_undef, data->current_loop->header, NULL))
     {
       if (pos != IP_ORIGINAL)
 	return NULL;
@@ -8192,6 +8307,7 @@ tree_ssa_iv_optimize (void)
   auto_bitmap toremove;
 
   tree_ssa_iv_optimize_init (&data);
+  mark_ssa_maybe_undefs ();
 
   /* Optimize the loops starting with the innermost ones.  */
   for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))

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

[Alexandre Oliva]

https://gcc.gnu.org/g:0f6179f2b85698b94e5a494920f0b282f414ea46

commit 0f6179f2b85698b94e5a494920f0b282f414ea46
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.
    
    To avoid deep recursion, precompute SSA_NAMEs deemed unsuitable
    candidates, so that we can skip them with a flag test.
    
    
    for  gcc/ChangeLog
    
            PR tree-optimization/105665
            PR tree-optimization/100810
            * tree-ssa-loop-ivopts.cc (mark_ssa_undefs): Precompute
            unsuitability of SSA_NAMEs in TREE_VISITED.
            (find_ssa_undef): Check the precomputed flag.
            (tree_ssa_iv_optimize): Call mark_ssa_undefs.
    
    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             | 61 +++++++++++++++++++++++++++++++--
 2 files changed, 79 insertions(+), 2 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..af508818522 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3071,13 +3071,69 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
   return *slot;
 }
 
-/* Find the first undefined SSA name in *TP.  */
+/* Mark as TREE_VISITED any SSA_NAMEs that are unsuitable as ivopts
+   candidates for potentially involving undefined behavior.  */
+
+static void
+mark_ssa_undefs (void)
+{
+  auto_vec<tree> queue;
+
+  unsigned int i;
+  tree var;
+  FOR_EACH_SSA_NAME (i, var, cfun)
+    {
+      if (SSA_NAME_IS_VIRTUAL_OPERAND (var)
+	  || !ssa_undefined_value_p (var, false))
+	TREE_VISITED (var) = false;
+      else
+	{
+	  TREE_VISITED (var) = true;
+	  queue.safe_push (var);
+	  if (dump_file)
+	    fprintf (dump_file, "marking _%i as undef\n",
+		     SSA_NAME_VERSION (var));
+	}
+    }
+
+  while (!queue.is_empty ())
+    {
+      var = queue.pop ();
+      gimple *stmt;
+      imm_use_iterator iter;
+      FOR_EACH_IMM_USE_STMT (stmt, iter, var)
+	{
+	  if (is_gimple_call (stmt) || is_a <gasm *> (stmt))
+	    continue;
+
+	  def_operand_p defvar;
+	  ssa_op_iter diter;
+	  FOR_EACH_PHI_OR_STMT_DEF (defvar, stmt, diter, SSA_OP_DEF)
+	    {
+	      gcc_checking_assert (is_gimple_assign (stmt)
+				   || is_a <gphi *> (stmt));
+	      tree def = DEF_FROM_PTR (defvar);
+	      if (TREE_VISITED (def))
+		continue;
+	      TREE_VISITED (def) = true;
+	      queue.safe_push (def);
+	      if (dump_file)
+		fprintf (dump_file, "Marking _%i as undef because of _%i\n",
+			 SSA_NAME_VERSION (def), SSA_NAME_VERSION (var));
+	    }
+	}
+    }
+}
+
+/* Return *TP if it is an SSA_NAME marked with TREE_VISITED, i.e., as
+   unsuitable as ivopts candidates for potentially involving undefined
+   behavior.  */
 
 static tree
 find_ssa_undef (tree *tp, int *walk_subtrees, void *)
 {
   if (TREE_CODE (*tp) == SSA_NAME
-      && ssa_undefined_value_p (*tp, false))
+      && TREE_VISITED (*tp))
     return *tp;
   if (!EXPR_P (*tp))
     *walk_subtrees = 0;
@@ -8192,6 +8248,7 @@ tree_ssa_iv_optimize (void)
   auto_bitmap toremove;
 
   tree_ssa_iv_optimize_init (&data);
+  mark_ssa_undefs ();
 
   /* Optimize the loops starting with the innermost ones.  */
   for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))

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

[Alexandre Oliva]

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;

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

[Alexandre Oliva]

https://gcc.gnu.org/g:781277269a6c76123d8ca5b38dbe9ab63a0fd699

commit 781277269a6c76123d8ca5b38dbe9ab63a0fd699
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             | 51 +++++++++++++++++++++++++++++----
 2 files changed, 65 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..adf9010ad67 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3071,14 +3071,52 @@ 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;
+
+      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 +3152,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;

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

[Alexandre Oliva]

https://gcc.gnu.org/g:8b85376e8c4279e620d7c9793776b42b9575b9ff

commit 8b85376e8c4279e620d7c9793776b42b9575b9ff
Author: Alexandre Oliva <oliva@adacore.com>
Date:   Thu May 26 09:15:53 2022 -0300

    [PR105665] ivopts: check defs of names in base for undefs

Diff:
---
 gcc/testsuite/gcc.dg/torture/pr105665.c |  2 +-
 gcc/tree-ssa-loop-ivopts.cc             | 22 ++++++++++++++++++----
 2 files changed, 19 insertions(+), 5 deletions(-)

diff --git a/gcc/testsuite/gcc.dg/torture/pr105665.c b/gcc/testsuite/gcc.dg/torture/pr105665.c
index 12f0b78a4b4..34cfc658434 100644
--- a/gcc/testsuite/gcc.dg/torture/pr105665.c
+++ b/gcc/testsuite/gcc.dg/torture/pr105665.c
@@ -6,7 +6,7 @@ int main() {
   for (; b < 2; b++) {
     int g;
     if (f)
-      b = 40;
+      g++, b = 40;
     a = d[b * b];
     for (f = 0; f < 3; f++) {
       if (e)
diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 5b1c7340f77..654a0432ef4 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3074,13 +3074,24 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
 /* Find the first undefined SSA name in *TP.  */
 
 static tree
-find_ssa_undef (tree *tp, int *walk_subtrees, void *)
+find_ssa_undef (tree *tp, int *walk_subtrees, void *pset_)
 {
+  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));
@@ -3092,8 +3103,10 @@ find_ssa_undef (tree *tp, int *walk_subtrees, void *)
 	{
 	  tree use = USE_FROM_PTR (use_p);
 
-	  if (ssa_undefined_value_p (use, false))
-	    return use;
+	  int wsub = 1;
+	  tree result = find_ssa_undef (&use, &wsub, pset);
+	  if (result)
+	    return result;
 	}
     }
 
@@ -3132,7 +3145,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;

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

[Alexandre Oliva]

https://gcc.gnu.org/g:e90f0f0296d12932b2ec3660b296328c11f73cb3

commit e90f0f0296d12932b2ec3660b296328c11f73cb3
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

Diff:
---
 gcc/testsuite/gcc.dg/torture/pr105665.c | 20 ++++++++++++++++++++
 gcc/tree-ssa-loop-ivopts.cc             | 24 +++++++++++++++++++++---
 2 files changed, 41 insertions(+), 3 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..12f0b78a4b4
--- /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)
+      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..5b1c7340f77 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3076,9 +3076,27 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
 static tree
 find_ssa_undef (tree *tp, int *walk_subtrees, void *)
 {
-  if (TREE_CODE (*tp) == SSA_NAME
-      && ssa_undefined_value_p (*tp, false))
-    return *tp;
+  if (TREE_CODE (*tp) == SSA_NAME)
+    {
+      if (ssa_undefined_value_p (*tp, false))
+	return *tp;
+
+      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));
+
+      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);
+
+	  if (ssa_undefined_value_p (use, false))
+	    return use;
+	}
+    }
+
   if (!EXPR_P (*tp))
     *walk_subtrees = 0;
   return NULL;

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

[Alexandre Oliva]

https://gcc.gnu.org/g:956d7d6e6f657359550824e6363f75575fee6817

commit 956d7d6e6f657359550824e6363f75575fee6817
Author: Alexandre Oliva <oliva@adacore.com>
Date:   Thu May 26 09:15:53 2022 -0300

    [PR105665] ivopts: check defs of names in base for undefs

Diff:
---
 gcc/testsuite/gcc.dg/torture/pr105665.c |  2 +-
 gcc/tree-ssa-loop-ivopts.cc             | 22 ++++++++++++++++++----
 2 files changed, 19 insertions(+), 5 deletions(-)

diff --git a/gcc/testsuite/gcc.dg/torture/pr105665.c b/gcc/testsuite/gcc.dg/torture/pr105665.c
index 12f0b78a4b4..34cfc658434 100644
--- a/gcc/testsuite/gcc.dg/torture/pr105665.c
+++ b/gcc/testsuite/gcc.dg/torture/pr105665.c
@@ -6,7 +6,7 @@ int main() {
   for (; b < 2; b++) {
     int g;
     if (f)
-      b = 40;
+      g++, b = 40;
     a = d[b * b];
     for (f = 0; f < 3; f++) {
       if (e)
diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 2e8cd486cc0..a834714181d 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3074,13 +3074,24 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
 /* Find the first undefined SSA name in *TP.  */
 
 static tree
-find_ssa_undef (tree *tp, int *walk_subtrees, void *)
+find_ssa_undef (tree *tp, int *walk_subtrees, void *pset_)
 {
+  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));
@@ -3092,8 +3103,10 @@ find_ssa_undef (tree *tp, int *walk_subtrees, void *)
 	{
 	  tree use = USE_FROM_PTR (use_p);
 
-	  if (ssa_undefined_value_p (use, false))
-	    return use;
+	  int wsub = 1;
+	  tree result = find_ssa_undef (&use, &wsub, pset);
+	  if (result)
+	    return result;
 	}
     }
 
@@ -3132,7 +3145,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;

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

[Alexandre Oliva]

https://gcc.gnu.org/g:ab0624ba523cb6118ef65962603bc150de66f6e3

commit ab0624ba523cb6118ef65962603bc150de66f6e3
Author: Alexandre Oliva <oliva@adacore.com>
Date:   Thu May 26 09:15:53 2022 -0300

    [PR105665] ivopts: check defs of names in base for undefs

Diff:
---
 gcc/tree-ssa-loop-ivopts.cc | 19 +++++++++++++++----
 1 file changed, 15 insertions(+), 4 deletions(-)

diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 2e8cd486cc0..e68968efc5f 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3074,10 +3074,18 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
 /* Find the first undefined SSA name in *TP.  */
 
 static tree
-find_ssa_undef (tree *tp, int *walk_subtrees, void *)
+find_ssa_undef (tree *tp, int *walk_subtrees, void *pset_)
 {
+  auto pset = static_cast<hash_set<tree> *> (pset_);
+
   if (TREE_CODE (*tp) == SSA_NAME)
     {
+      /* 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;
+
       if (ssa_undefined_value_p (*tp, false))
 	return *tp;
 
@@ -3092,8 +3100,10 @@ find_ssa_undef (tree *tp, int *walk_subtrees, void *)
 	{
 	  tree use = USE_FROM_PTR (use_p);
 
-	  if (ssa_undefined_value_p (use, false))
-	    return use;
+	  int wsub = 1;
+	  tree result = find_ssa_undef (&use, &wsub, pset);
+	  if (result)
+	    return result;
 	}
     }
 
@@ -3132,7 +3142,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;

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

[Alexandre Oliva]

https://gcc.gnu.org/g:e8e1a5d53833bab3774ca287381b84c5df1226ee

commit e8e1a5d53833bab3774ca287381b84c5df1226ee
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

Diff:
---
 gcc/testsuite/gcc.dg/torture/pr105665.c | 20 ++++++++++++++++++++
 gcc/tree-ssa-loop-ivopts.cc             | 24 +++++++++++++++++++++---
 2 files changed, 41 insertions(+), 3 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..12f0b78a4b4
--- /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)
+      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..2e8cd486cc0 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3076,9 +3076,27 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
 static tree
 find_ssa_undef (tree *tp, int *walk_subtrees, void *)
 {
-  if (TREE_CODE (*tp) == SSA_NAME
-      && ssa_undefined_value_p (*tp, false))
-    return *tp;
+  if (TREE_CODE (*tp) == SSA_NAME)
+    {
+      if (ssa_undefined_value_p (*tp, false))
+	return *tp;
+
+      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));
+
+      ssa_op_iter iter;
+      use_operand_p use_p;
+
+      FOR_EACH_PHI_OR_STMT_USE (use_p, def_stmt, iter, SSA_OP_ALL_USES)
+	{
+	  tree use = USE_FROM_PTR (use_p);
+
+	  if (ssa_undefined_value_p (use, false))
+	    return use;
+	}
+    }
+
   if (!EXPR_P (*tp))
     *walk_subtrees = 0;
   return NULL;