tree-optimization/101242 - fix reverse graph entry detection

This avoids detecting random unrelated nodes as possible entries
to not backwards reachable regions of the SLP graph.  Instead
explicitely add the problematic nodes.

This temporary XFAILs gcc.dg/vect/pr67790.c until I get the
permute propagation adjusted to when it needs more than one
optimistic iteration.

2021-06-29  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/101242
	* tree-vect-slp.c (vect_slp_build_vertices): Force-add
	PHIs with not represented initial values as leafs.

	* gcc.dg/vect/bb-slp-pr101242.c: New testcase.
	* gcc.dg/vect/pr67790.c: XFAIL scan for zero VEC_PERM_EXPR.

3 files changed, 50 insertions, 14 deletions

diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr101242.c b/gcc/testsuite/gcc.dg/vect/bb-slp-pr101242.c
new file mode 100644
index 0000000..d885446
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr101242.c
@@ -0,0 +1,38 @@
+/* { dg-do compile } */
+/* { dg-additional-options "-Ofast" } */
+
+typedef struct {
+  double real;
+  double imag;
+} complex;
+typedef struct {
+  complex e[3][3];
+} su3_matrix;
+su3_matrix check_su3_c;
+double check_su3_ar, check_su3_ari, check_su3_max;
+int arireturn();
+int check_su3() {
+  check_su3_ar = check_su3_c.e[0][0].real * check_su3_c.e[1][0].real +
+                 check_su3_c.e[0][0].imag * check_su3_c.e[1][0].imag +
+                 check_su3_c.e[0][1].real * check_su3_c.e[1][1].real +
+                 check_su3_c.e[0][1].imag * check_su3_c.e[1][1].imag +
+                 check_su3_c.e[0][2].real * check_su3_c.e[1][2].real +
+                 check_su3_c.e[0][2].imag * check_su3_c.e[1][2].imag;
+  check_su3_max = check_su3_c.e[0][0].real * check_su3_c.e[2][0].real +
+                  check_su3_c.e[0][0].imag * check_su3_c.e[2][0].imag +
+                  check_su3_c.e[0][1].real * check_su3_c.e[2][1].real +
+                  check_su3_c.e[0][1].imag * check_su3_c.e[2][1].imag +
+                  check_su3_c.e[0][2].real * check_su3_c.e[2][2].real +
+                  check_su3_c.e[0][2].imag * check_su3_c.e[2][2].imag;
+  check_su3_ari = check_su3_ar;
+  if (check_su3_ari)
+    check_su3_max = check_su3_c.e[1][0].real * check_su3_c.e[2][0].real +
+                    check_su3_c.e[1][0].imag * check_su3_c.e[2][0].imag +
+                    check_su3_c.e[1][1].real * check_su3_c.e[2][1].real +
+                    check_su3_c.e[1][1].imag * check_su3_c.e[2][1].imag +
+                    check_su3_c.e[1][2].real * check_su3_c.e[2][2].real +
+                    check_su3_c.e[1][2].imag * check_su3_c.e[2][2].imag;
+  if (check_su3_max)
+    arireturn();
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/vect/pr67790.c b/gcc/testsuite/gcc.dg/vect/pr67790.c
index 32eacd9..0555d41 100644
--- a/gcc/testsuite/gcc.dg/vect/pr67790.c
+++ b/gcc/testsuite/gcc.dg/vect/pr67790.c
@@ -38,4 +38,4 @@ int main()
 }
 
 /* { dg-final { scan-tree-dump "vectorizing stmts using SLP" "vect" } } */
-/* { dg-final { scan-tree-dump-times "VEC_PERM_EXPR" 0 "vect" } } */
+/* { dg-final { scan-tree-dump-times "VEC_PERM_EXPR" 0 "vect" { xfail *-*-* } } } */
diff --git a/gcc/tree-vect-slp.c b/gcc/tree-vect-slp.c
index 5401dbe..63b6e6a 100644
--- a/gcc/tree-vect-slp.c
+++ b/gcc/tree-vect-slp.c
@@ -3499,13 +3499,21 @@ vect_slp_build_vertices (hash_set<slp_tree> &visited, slp_tree node,
   vertices.safe_push (slpg_vertex (node));
 
   bool leaf = true;
+  bool force_leaf = false;
   FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
     if (child)
       {
 	leaf = false;
 	vect_slp_build_vertices (visited, child, vertices, leafs);
       }
-  if (leaf)
+    else
+      force_leaf = true;
+  /* Since SLP discovery works along use-def edges all cycles have an
+     entry - but there's the exception of cycles where we do not handle
+     the entry explicitely (but with a NULL SLP node), like some reductions
+     and inductions.  Force those SLP PHIs to act as leafs to make them
+     backwards reachable.  */
+  if (leaf || force_leaf)
     leafs.safe_push (node->vertex);
 }
 
@@ -3519,18 +3527,8 @@ vect_slp_build_vertices (vec_info *info, vec<slpg_vertex> &vertices,
   unsigned i;
   slp_instance instance;
   FOR_EACH_VEC_ELT (info->slp_instances, i, instance)
-    {
-      unsigned n_v = vertices.length ();
-      unsigned n_l = leafs.length ();
-      vect_slp_build_vertices (visited, SLP_INSTANCE_TREE (instance), vertices,
-			       leafs);
-      /* If we added vertices but no entries to the reverse graph we've
-	 added a cycle that is not backwards-reachable.   Push the entry
-	 to mimic as leaf then.  */
-      if (vertices.length () > n_v
-	  && leafs.length () == n_l)
-	leafs.safe_push (SLP_INSTANCE_TREE (instance)->vertex);
-    }
+    vect_slp_build_vertices (visited, SLP_INSTANCE_TREE (instance), vertices,
+			     leafs);
 }
 
 /* Apply (reverse) bijectite PERM to VEC.  */