[gcc r12-8241] tree-optimization/100810 - avoid undefs in IVOPT rewrites

[gcc r12-8241] tree-optimization/100810 - avoid undefs in IVOPT rewrites

[Richard Biener]

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

commit r12-8241-gab91c10792cd3a1ba1495aa30a34ca17b043bafb
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Apr 1 11:30:00 2022 +0200

    tree-optimization/100810 - avoid undefs in IVOPT rewrites
    
    The following attempts to avoid IVOPTs rewriting uses using
    IV candidates that involve undefined behavior by using uninitialized
    SSA names.  First we restrict the set of candidates we produce
    for such IVs to the original ones and mark them as not important.
    Second we try to only allow expressing uses with such IV if they
    originally use them.  That is to avoid rewriting all such uses
    in terms of other IVs.  Since cand->iv and use->iv seem to never
    exactly match up we resort to comparing the IV bases.
    
    The approach ends up similar to the one posted by Roger at
    https://gcc.gnu.org/pipermail/gcc-patches/2021-August/578441.html
    but it marks IV candidates rather than use groups and the cases
    we allow in determine_group_iv_cost_generic are slightly different.
    
    2022-01-04  Richard Biener  <rguenther@suse.de>
    
            PR tree-optimization/100810
            * tree-ssa-loop-ivopts.cc (struct iv_cand): Add involves_undefs flag.
            (find_ssa_undef): New function.
            (add_candidate_1): Avoid adding derived candidates with
            undefined SSA names and mark the original ones.
            (determine_group_iv_cost_generic): Reject rewriting
            uses with a different IV when that involves undefined SSA names.
    
            * gcc.dg/torture/pr100810.c: New testcase.
            * gcc.dg/torture/pr105337.c: Likewise.

Diff:
---
 gcc/testsuite/gcc.dg/torture/pr100810.c | 34 +++++++++++++++++++++++++++++++++
 gcc/testsuite/gcc.dg/torture/pr105337.c | 31 ++++++++++++++++++++++++++++++
 gcc/tree-ssa-loop-ivopts.cc             | 31 ++++++++++++++++++++++++++++++
 3 files changed, 96 insertions(+)

diff --git a/gcc/testsuite/gcc.dg/torture/pr100810.c b/gcc/testsuite/gcc.dg/torture/pr100810.c
new file mode 100644
index 00000000000..63566f530f7
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr100810.c
@@ -0,0 +1,34 @@
+/* { dg-do run } */
+
+int a, b = 1, c = 1, e, f = 1, g, h, j;
+volatile int d;
+static void k()
+{
+  int i;
+  h = b;
+  if (c && a >= 0) {
+      while (a) {
+	  i++;
+	  h--;
+      }
+      if (g)
+	for (h = 0; h < 2; h++)
+	  ;
+      if (!b)
+	i &&d;
+  }
+}
+static void l()
+{
+  for (; j < 1; j++)
+    if (!e && c && f)
+      k();
+}
+int main()
+{
+  if (f)
+    l();
+  if (h != 1)
+    __builtin_abort();
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/torture/pr105337.c b/gcc/testsuite/gcc.dg/torture/pr105337.c
new file mode 100644
index 00000000000..4a0bdf0363c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr105337.c
@@ -0,0 +1,31 @@
+/* { dg-do run } */
+
+__attribute__((noipa)) void
+bar (int x)
+{
+  (void) x;
+}
+
+int a;
+
+int
+foo (void)
+{
+  int b, c;
+  for (b = 0; b < 3; b++)
+    {
+      if (!a)
+	break;
+      c--;
+      bar (c);
+    }
+  return b;
+}
+
+int
+main ()
+{
+  if (foo ())
+    __builtin_abort ();
+  return 0;
+}
diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 581f92b059b..81b536f9304 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -452,6 +452,7 @@ struct iv_cand
   unsigned id;		/* The number of the candidate.  */
   bool important;	/* Whether this is an "important" candidate, i.e. such
 			   that it should be considered by all uses.  */
+  bool involves_undefs; /* Whether the IV involves undefined values.  */
   ENUM_BITFIELD(iv_position) pos : 8;	/* Where it is computed.  */
   gimple *incremented_at;/* For original biv, the statement where it is
 			   incremented.  */
@@ -3070,6 +3071,19 @@ get_loop_invariant_expr (struct ivopts_data *data, tree inv_expr)
   return *slot;
 }
 
+/* Find the first undefined SSA name in *TP.  */
+
+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 (!EXPR_P (*tp))
+    *walk_subtrees = 0;
+  return NULL;
+}
+
 /* 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
@@ -3097,6 +3111,17 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
   if (flag_keep_gc_roots_live && POINTER_TYPE_P (TREE_TYPE (base)))
     return NULL;
 
+  /* 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 (pos != IP_ORIGINAL)
+	return NULL;
+      important = false;
+      involves_undefs = true;
+    }
+
   /* For non-original variables, make sure their values are computed in a type
      that does not invoke undefined behavior on overflows (since in general,
      we cannot prove that these induction variables are non-wrapping).  */
@@ -3145,6 +3170,7 @@ add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important,
 	  cand->var_after = cand->var_before;
 	}
       cand->important = important;
+      cand->involves_undefs = involves_undefs;
       cand->incremented_at = incremented_at;
       cand->doloop_p = doloop;
       data->vcands.safe_push (cand);
@@ -4958,6 +4984,11 @@ determine_group_iv_cost_generic (struct ivopts_data *data,
      the candidate.  */
   if (cand->pos == IP_ORIGINAL && cand->incremented_at == use->stmt)
     cost = no_cost;
+  /* If the IV candidate involves undefined SSA values and is not the
+     same IV as on the USE avoid using that candidate here.  */
+  else if (cand->involves_undefs
+	   && (!use->iv || !operand_equal_p (cand->iv->base, use->iv->base, 0)))
+    return false;
   else
     cost = get_computation_cost (data, use, cand, false,
 				 &inv_vars, NULL, &inv_expr);