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

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

[Alexandre Oliva]

https://gcc.gnu.org/g:3ea43cb1be1f7b7dfe32f12fbe0ae0aef3abe384

commit 3ea43cb1be1f7b7dfe32f12fbe0ae0aef3abe384
Author: Alexandre Oliva <oliva@gnu.org>
Date:   Fri May 27 22:41:54 2022 -0300

    ivopts: check defs of names in base for undefs

Diff:
---
 gcc/tree-ssa-loop-ivopts.cc | 83 +++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 80 insertions(+), 3 deletions(-)

diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 8902702cbbb..da70767b5f1 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3071,6 +3071,57 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
   return *slot;
 }
 
+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));
+	    }
+	}
+    }
+}
+
 /* Find the first undefined SSA name in *TP.  Use PSET_, a
    hash_set<tree>*, to avoid cycles and to skip other duplicates.  */
 
@@ -3081,7 +3132,11 @@ find_ssa_undef (tree *tp, int *walk_subtrees, void *pset_)
 
   if (TREE_CODE (*tp) == SSA_NAME)
     {
-      if (ssa_defined_default_def_p (*tp))
+      if (SSA_NAME_IS_VIRTUAL_OPERAND (*tp))
+	return NULL;
+
+      if (SSA_NAME_IS_DEFAULT_DEF (*tp)
+	  && ssa_defined_default_def_p (*tp))
 	return NULL;
 
       if (ssa_undefined_value_p (*tp, false))
@@ -3123,6 +3178,28 @@ find_ssa_undef (tree *tp, int *walk_subtrees, void *pset_)
   return NULL;
 }
 
+static tree
+is_ssa_undef_1 (tree *tp, int *walk_subtrees, void *)
+{
+  if (TREE_CODE (*tp) == SSA_NAME && TREE_VISITED (*tp))
+    return *tp;
+  if (!EXPR_P (*tp))
+    *walk_subtrees = 0;
+  return NULL;
+}
+
+static tree
+is_ssa_undef (tree *tp, int *walk_subtrees, void *data)
+{
+  tree ret = is_ssa_undef_1 (tp, walk_subtrees, data);
+#if CHECKING_P
+  int wst = 1;
+  hash_set<tree> pset;
+  gcc_checking_assert (!ret == !find_ssa_undef (tp, &wst, &pset));
+#endif
+  return ret;
+}
+
 /* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
    position to POS.  If USE is not NULL, the candidate is set as related to
    it.  If both BASE and STEP are NULL, we add a pseudocandidate for the
@@ -3153,8 +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;
-  hash_set<tree> pset;
-  if (walk_tree (&base, find_ssa_undef, &pset, NULL))
+  if (walk_tree (&base, is_ssa_undef, NULL, NULL))
     {
       if (pos != IP_ORIGINAL)
 	return NULL;
@@ -8232,6 +8308,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)] ivopts: check defs of names in base for undefs

[Alexandre Oliva]

https://gcc.gnu.org/g:13f856729353c4dae4a1657733fbca0275ce3945

commit 13f856729353c4dae4a1657733fbca0275ce3945
Author: Alexandre Oliva <oliva@gnu.org>
Date:   Fri May 27 22:41:54 2022 -0300

    ivopts: check defs of names in base for undefs

Diff:
---
 gcc/tree-ssa-loop-ivopts.cc | 78 +++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 76 insertions(+), 2 deletions(-)

diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 8902702cbbb..fcbc3879b53 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -3071,6 +3071,58 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
   return *slot;
 }
 
+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_defined_default_def_p (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));
+	    }
+	}
+    }
+}
+
 /* Find the first undefined SSA name in *TP.  Use PSET_, a
    hash_set<tree>*, to avoid cycles and to skip other duplicates.  */
 
@@ -3123,6 +3175,28 @@ find_ssa_undef (tree *tp, int *walk_subtrees, void *pset_)
   return NULL;
 }
 
+static tree
+is_ssa_undef_1 (tree *tp, int *walk_subtrees, void *)
+{
+  if (TREE_CODE (*tp) == SSA_NAME && TREE_VISITED (*tp))
+    return *tp;
+  if (!EXPR_P (*tp))
+    *walk_subtrees = 0;
+  return NULL;
+}
+
+static tree
+is_ssa_undef (tree *tp, int *walk_subtrees, void *data)
+{
+  tree ret = is_ssa_undef_1 (tp, walk_subtrees, data);
+#if CHECKING_P
+  int wst = 1;
+  hash_set<tree> pset;
+  gcc_checking_assert (!ret == !find_ssa_undef (tp, &wst, &pset));
+#endif
+  return ret;
+}
+
 /* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
    position to POS.  If USE is not NULL, the candidate is set as related to
    it.  If both BASE and STEP are NULL, we add a pseudocandidate for the
@@ -3153,8 +3227,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;
-  hash_set<tree> pset;
-  if (walk_tree (&base, find_ssa_undef, &pset, NULL))
+  if (walk_tree (&base, is_ssa_undef, NULL, NULL))
     {
       if (pos != IP_ORIGINAL)
 	return NULL;
@@ -8232,6 +8305,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))