[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: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))