[11/n] PR85694: Apply pattern matching to pattern definition statements

[Richard Sandiford <richard dot sandiford at arm dot com>]

Although the first pattern match wins in the sense that no later
function can match the *old* gimple statement, it still seems worth
letting them match the *new* gimple statements, just like we would if
the original IR had included that sequence from the outset.

This is mostly true after the later patch for PR85694, where e.g. we
could recognise:

   signed char a;
   int ap = (int) a;
   int res = ap * 3;

as the pattern:

   short ap' = (short) a;
   short res = ap' * 3;     // S1: definition statement
   int res = (int) res;     // S2: pattern statement

and then apply the mult pattern to "ap' * 3".  The patch needs to
come first (without its own test cases) so that the main over-widening
patch doesn't regress anything.

Tested on aarch64-linux-gnu and x86_64-linux-gnu.  OK to install?

Richard


2018-06-20  Richard Sandiford  <richard.sandiford@arm.com>

gcc/
	* gimple-iterator.c (gsi_for_stmt): Add a new overload that takes
	the containing gimple_seq *.
	* gimple-iterator.h (gsi_for_stmt): Declare it.
	* tree-vect-patterns.c (vect_recog_dot_prod_pattern)
	(vect_recog_sad_pattern, vect_recog_widen_sum_pattern)
	(vect_recog_widen_shift_pattern, vect_recog_rotate_pattern)
	(vect_recog_vector_vector_shift_pattern, vect_recog_divmod_pattern)
	(vect_recog_mask_conversion_pattern): Remove STMT_VINFO_IN_PATTERN_P
	checks.
	(vect_init_pattern_stmt, vect_set_pattern_stmt): New functions,
	split out from...
	(vect_mark_pattern_stmts): ...here.  Handle cases in which the
	statement being replaced is part of an existing pattern
	definition sequence, inserting the new pattern statements before
	the original one.
	(vect_pattern_recog_1): Don't return a bool.  If the statement
	is already part of a pattern, instead apply pattern matching
	to the pattern definition statements.  Don't clear the
	STMT_VINFO_RELATED_STMT if is_pattern_stmt_p.
	(vect_pattern_recog): Don't break after the first match;
	continue processing the pattern definition statements instead.
	Don't bail out for STMT_VINFO_IN_PATTERN_P here.

Index: gcc/gimple-iterator.c
===================================================================
--- gcc/gimple-iterator.c	2018-05-02 08:38:09.833407589 +0100
+++ gcc/gimple-iterator.c	2018-06-20 11:26:07.913295807 +0100
@@ -619,6 +619,18 @@ gsi_for_stmt (gimple *stmt)
   return i;
 }
 
+/* Get an iterator for STMT, which is known to belong to SEQ.  This is
+   equivalent to starting at the beginning of SEQ and searching forward
+   until STMT is found.  */
+
+gimple_stmt_iterator
+gsi_for_stmt (gimple *stmt, gimple_seq *seq)
+{
+  gimple_stmt_iterator i = gsi_start_1 (seq);
+  i.ptr = stmt;
+  return i;
+}
+
 /* Finds iterator for PHI.  */
 
 gphi_iterator
Index: gcc/gimple-iterator.h
===================================================================
--- gcc/gimple-iterator.h	2018-05-02 08:38:10.117404903 +0100
+++ gcc/gimple-iterator.h	2018-06-20 11:26:07.913295807 +0100
@@ -79,6 +79,7 @@ extern void gsi_insert_after (gimple_stm
 			      enum gsi_iterator_update);
 extern bool gsi_remove (gimple_stmt_iterator *, bool);
 extern gimple_stmt_iterator gsi_for_stmt (gimple *);
+extern gimple_stmt_iterator gsi_for_stmt (gimple *, gimple_seq *);
 extern gphi_iterator gsi_for_phi (gphi *);
 extern void gsi_move_after (gimple_stmt_iterator *, gimple_stmt_iterator *);
 extern void gsi_move_before (gimple_stmt_iterator *, gimple_stmt_iterator *);
Index: gcc/tree-vect-patterns.c
===================================================================
--- gcc/tree-vect-patterns.c	2018-06-20 11:26:00.497361237 +0100
+++ gcc/tree-vect-patterns.c	2018-06-20 11:26:07.913295807 +0100
@@ -60,6 +60,42 @@ vect_pattern_detected (const char *name,
     }
 }
 
+/* Associate pattern statement PATTERN_STMT with ORIG_STMT_INFO.
+   Set its vector type to VECTYPE if it doesn't have one already.  */
+
+static void
+vect_init_pattern_stmt (gimple *pattern_stmt, stmt_vec_info orig_stmt_info,
+			tree vectype)
+{
+  stmt_vec_info pattern_stmt_info = vinfo_for_stmt (pattern_stmt);
+  if (pattern_stmt_info == NULL)
+    {
+      pattern_stmt_info = new_stmt_vec_info (pattern_stmt,
+					     orig_stmt_info->vinfo);
+      set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info);
+    }
+  gimple_set_bb (pattern_stmt, gimple_bb (orig_stmt_info->stmt));
+
+  STMT_VINFO_RELATED_STMT (pattern_stmt_info) = orig_stmt_info->stmt;
+  STMT_VINFO_DEF_TYPE (pattern_stmt_info)
+    = STMT_VINFO_DEF_TYPE (orig_stmt_info);
+  if (!STMT_VINFO_VECTYPE (pattern_stmt_info))
+    STMT_VINFO_VECTYPE (pattern_stmt_info) = vectype;
+}
+
+/* Set the pattern statement of ORIG_STMT_INFO to PATTERN_STMT.
+   Also set the vector type of PATTERN_STMT to VECTYPE, if it doesn't
+   have one already.  */
+
+static void
+vect_set_pattern_stmt (gimple *pattern_stmt, stmt_vec_info orig_stmt_info,
+		       tree vectype)
+{
+  STMT_VINFO_IN_PATTERN_P (orig_stmt_info) = true;
+  STMT_VINFO_RELATED_STMT (orig_stmt_info) = pattern_stmt;
+  vect_init_pattern_stmt (pattern_stmt, orig_stmt_info, vectype);
+}
+
 static inline void
 append_pattern_def_seq (stmt_vec_info stmt_info, gimple *stmt)
 {
@@ -353,9 +389,6 @@ vect_recog_dot_prod_pattern (vec<gimple
   /* Starting from LAST_STMT, follow the defs of its uses in search
      of the above pattern.  */
 
-  if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
-    return NULL;
-
   if (!vect_reassociating_reduction_p (stmt_vinfo, PLUS_EXPR,
 				       &oprnd0, &oprnd1))
     return NULL;
@@ -513,9 +546,6 @@ vect_recog_sad_pattern (vec<gimple *> *s
   /* Starting from LAST_STMT, follow the defs of its uses in search
      of the above pattern.  */
 
-  if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
-    return NULL;
-
   tree plus_oprnd0, plus_oprnd1;
   if (!vect_reassociating_reduction_p (stmt_vinfo, PLUS_EXPR,
 				       &plus_oprnd0, &plus_oprnd1))
@@ -1128,9 +1158,6 @@ vect_recog_widen_sum_pattern (vec<gimple
   tree var;
   bool promotion;
 
-  if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
-    return NULL;
-
   /* Look for the following pattern
           DX = (TYPE) X;
           sum_1 = DX + sum_0;
@@ -1606,9 +1633,6 @@ vect_recog_widen_shift_pattern (vec<gimp
   if (!is_gimple_assign (last_stmt) || !vinfo_for_stmt (last_stmt))
     return NULL;
 
-  if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (last_stmt)))
-    return NULL;
-
   if (gimple_assign_rhs_code (last_stmt) != LSHIFT_EXPR)
     return NULL;
 
@@ -1743,9 +1767,6 @@ vect_recog_rotate_pattern (vec<gimple *>
       return NULL;
     }
 
-  if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
-    return NULL;
-
   lhs = gimple_assign_lhs (last_stmt);
   oprnd0 = gimple_assign_rhs1 (last_stmt);
   type = TREE_TYPE (oprnd0);
@@ -1991,9 +2012,6 @@ vect_recog_vector_vector_shift_pattern (
       return NULL;
     }
 
-  if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
-    return NULL;
-
   lhs = gimple_assign_lhs (last_stmt);
   oprnd0 = gimple_assign_rhs1 (last_stmt);
   oprnd1 = gimple_assign_rhs2 (last_stmt);
@@ -2492,9 +2510,6 @@ vect_recog_divmod_pattern (vec<gimple *>
       return NULL;
     }
 
-  if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
-    return NULL;
-
   oprnd0 = gimple_assign_rhs1 (last_stmt);
   oprnd1 = gimple_assign_rhs2 (last_stmt);
   itype = TREE_TYPE (oprnd0);
@@ -3829,11 +3844,6 @@ vect_recog_mask_conversion_pattern (vec<
   /* Check for cond expression requiring mask conversion.  */
   if (rhs_code == COND_EXPR)
     {
-      /* vect_recog_mixed_size_cond_pattern could apply.
-	 Do nothing then.  */
-      if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
-	return NULL;
-
       vectype1 = get_vectype_for_scalar_type (TREE_TYPE (lhs));
 
       if (TREE_CODE (rhs1) == SSA_NAME)
@@ -4222,42 +4232,59 @@ const unsigned int NUM_PATTERNS = ARRAY_
 vect_mark_pattern_stmts (gimple *orig_stmt, gimple *pattern_stmt,
                          tree pattern_vectype)
 {
-  stmt_vec_info pattern_stmt_info, def_stmt_info;
   stmt_vec_info orig_stmt_info = vinfo_for_stmt (orig_stmt);
-  vec_info *vinfo = orig_stmt_info->vinfo;
-  gimple *def_stmt;
+  gimple *def_seq = STMT_VINFO_PATTERN_DEF_SEQ (orig_stmt_info);
 
-  pattern_stmt_info = vinfo_for_stmt (pattern_stmt);
-  if (pattern_stmt_info == NULL)
+  bool old_pattern_p = is_pattern_stmt_p (orig_stmt_info);
+  if (old_pattern_p)
     {
-      pattern_stmt_info = new_stmt_vec_info (pattern_stmt, vinfo);
-      set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info);
+      /* We're replacing a statement in an existing pattern definition
+	 sequence.  */
+      if (dump_enabled_p ())
+	{
+	  dump_printf_loc (MSG_NOTE, vect_location,
+			   "replacing earlier pattern ");
+	  dump_gimple_stmt (MSG_NOTE, TDF_SLIM, orig_stmt, 0);
+	}
+
+      /* To keep the book-keeping simple, just swap the lhs of the
+	 old and new statements, so that the old one has a valid but
+	 unused lhs.  */
+      tree old_lhs = gimple_get_lhs (orig_stmt);
+      gimple_set_lhs (orig_stmt, gimple_get_lhs (pattern_stmt));
+      gimple_set_lhs (pattern_stmt, old_lhs);
+
+      if (dump_enabled_p ())
+	{
+	  dump_printf_loc (MSG_NOTE, vect_location, "with ");
+	  dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
+	}
+
+      /* Switch to the statement that ORIG replaces.  */
+      orig_stmt_info
+	= vinfo_for_stmt (STMT_VINFO_RELATED_STMT (orig_stmt_info));
+
+      /* We shouldn't be replacing the main pattern statement.  */
+      gcc_assert (STMT_VINFO_RELATED_STMT (orig_stmt_info) != orig_stmt);
     }
-  gimple_set_bb (pattern_stmt, gimple_bb (orig_stmt));
 
-  STMT_VINFO_RELATED_STMT (pattern_stmt_info) = orig_stmt;
-  STMT_VINFO_DEF_TYPE (pattern_stmt_info)
-    = STMT_VINFO_DEF_TYPE (orig_stmt_info);
-  STMT_VINFO_VECTYPE (pattern_stmt_info) = pattern_vectype;
-  STMT_VINFO_IN_PATTERN_P (orig_stmt_info) = true;
-  STMT_VINFO_RELATED_STMT (orig_stmt_info) = pattern_stmt;
-  if (gimple *def_seq = STMT_VINFO_PATTERN_DEF_SEQ (orig_stmt_info))
+  if (def_seq)
     for (gimple_stmt_iterator si = gsi_start (def_seq);
 	 !gsi_end_p (si); gsi_next (&si))
-      {
-	def_stmt = gsi_stmt (si);
-	def_stmt_info = vinfo_for_stmt (def_stmt);
-	if (def_stmt_info == NULL)
-	  {
-	    def_stmt_info = new_stmt_vec_info (def_stmt, vinfo);
-	    set_vinfo_for_stmt (def_stmt, def_stmt_info);
-	  }
-	gimple_set_bb (def_stmt, gimple_bb (orig_stmt));
-	STMT_VINFO_RELATED_STMT (def_stmt_info) = orig_stmt;
-	STMT_VINFO_DEF_TYPE (def_stmt_info) = vect_internal_def;
-	if (STMT_VINFO_VECTYPE (def_stmt_info) == NULL_TREE)
-	  STMT_VINFO_VECTYPE (def_stmt_info) = pattern_vectype;
-      }
+      vect_init_pattern_stmt (gsi_stmt (si), orig_stmt_info, pattern_vectype);
+
+  if (old_pattern_p)
+    {
+      vect_init_pattern_stmt (pattern_stmt, orig_stmt_info, pattern_vectype);
+
+      /* Insert all the new pattern statements before the original one.  */
+      gimple_seq *orig_def_seq = &STMT_VINFO_PATTERN_DEF_SEQ (orig_stmt_info);
+      gimple_stmt_iterator gsi = gsi_for_stmt (orig_stmt, orig_def_seq);
+      gsi_insert_seq_before_without_update (&gsi, def_seq, GSI_SAME_STMT);
+      gsi_insert_before_without_update (&gsi, pattern_stmt, GSI_SAME_STMT);
+    }
+  else
+    vect_set_pattern_stmt (pattern_stmt, orig_stmt_info, pattern_vectype);
 }
 
 /* Function vect_pattern_recog_1
@@ -4278,7 +4305,7 @@ vect_mark_pattern_stmts (gimple *orig_st
    This function also does some bookkeeping, as explained in the documentation
    for vect_recog_pattern.  */
 
-static bool
+static void
 vect_pattern_recog_1 (vect_recog_func *recog_func,
 		      gimple_stmt_iterator si,
 		      vec<gimple *> *stmts_to_replace)
@@ -4289,6 +4316,20 @@ vect_pattern_recog_1 (vect_recog_func *r
   tree pattern_vectype;
   int i;
 
+  /* If this statement has already been replaced with pattern statements,
+     leave the original statement alone, since the first match wins.
+     Instead try to match against the definition statements that feed
+     the main pattern statement.  */
+  stmt_info = vinfo_for_stmt (stmt);
+  if (STMT_VINFO_IN_PATTERN_P (stmt_info))
+    {
+      gimple_stmt_iterator gsi;
+      for (gsi = gsi_start (STMT_VINFO_PATTERN_DEF_SEQ (stmt_info));
+	   !gsi_end_p (gsi); gsi_next (&gsi))
+	vect_pattern_recog_1 (recog_func, gsi, stmts_to_replace);
+      return;
+    }
+
   stmts_to_replace->truncate (0);
   stmts_to_replace->quick_push (stmt);
   pattern_stmt = recog_func->fn (stmts_to_replace, &pattern_vectype);
@@ -4301,9 +4342,10 @@ vect_pattern_recog_1 (vect_recog_func *r
 	   i++)
 	{
 	  stmt_info = vinfo_for_stmt (stmt);
-	  STMT_VINFO_RELATED_STMT (stmt_info) = NULL;
+	  if (!is_pattern_stmt_p (stmt_info))
+	    STMT_VINFO_RELATED_STMT (stmt_info) = NULL;
 	}
-      return false;
+      return;
     }
 
   stmt = stmts_to_replace->last ();
@@ -4351,7 +4393,7 @@ vect_pattern_recog_1 (vect_recog_func *r
       vect_mark_pattern_stmts (stmt, pattern_stmt, NULL_TREE);
     }
 
-  return true;
+  return;
 }
 
 
@@ -4456,17 +4498,10 @@ vect_pattern_recog (vec_info *vinfo)
 	{
 	  basic_block bb = bbs[i];
 	  for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
-	    {
-	      gimple *stmt = gsi_stmt (si);
-	      stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
-	      if (stmt_info && STMT_VINFO_IN_PATTERN_P (stmt_info))
-		continue;
-	      /* Scan over all generic vect_recog_xxx_pattern functions.  */
-	      for (j = 0; j < NUM_PATTERNS; j++)
-		if (vect_pattern_recog_1 (&vect_vect_recog_func_ptrs[j], si,
-					  &stmts_to_replace))
-		  break;
-	    }
+	    /* Scan over all generic vect_recog_xxx_pattern functions.  */
+	    for (j = 0; j < NUM_PATTERNS; j++)
+	      vect_pattern_recog_1 (&vect_vect_recog_func_ptrs[j], si,
+				    &stmts_to_replace);
 	}
     }
   else
@@ -4477,16 +4512,13 @@ vect_pattern_recog (vec_info *vinfo)
 	{
 	  gimple *stmt = gsi_stmt (si);
 	  stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
-	  if (stmt_info
-	      && (!STMT_VINFO_VECTORIZABLE (stmt_info)
-		  || STMT_VINFO_IN_PATTERN_P (stmt_info)))
+	  if (stmt_info && !STMT_VINFO_VECTORIZABLE (stmt_info))
 	    continue;
 
 	  /* Scan over all generic vect_recog_xxx_pattern functions.  */
 	  for (j = 0; j < NUM_PATTERNS; j++)
-	    if (vect_pattern_recog_1 (&vect_vect_recog_func_ptrs[j], si,
-				      &stmts_to_replace))
-	      break;
+	    vect_pattern_recog_1 (&vect_vect_recog_func_ptrs[j], si,
+				  &stmts_to_replace);
 	}
     }
 }