[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.

(cherry picked from commit be2861fe8c527a5952257462ceca899bb43b1452)

1 files changed, 20 insertions, 0 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;
+}