Record the vector mask precision in stmt_vec_info

search_type_for_mask uses a worklist to search a chain of boolean
operations for a natural vector mask type.  This patch instead does
that in vect_determine_stmt_precisions, where we also look for
overpromoted integer operations.  We then only need to compute
the precision once and can cache it in the stmt_vec_info.

The new function vect_determine_mask_precision is supposed
to handle exactly the same cases as search_type_for_mask_1,
and in the same way.  There's a lot we could improve here,
but that's not stage 3 material.

I wondered about sharing mask_precision with other fields like
operation_precision, but in the end that seemed too dangerous.
We have patterns to convert between boolean and non-boolean
operations and it would be very easy to get mixed up about
which case the fields are describing.

2019-11-29  Richard Sandiford  <richard.sandiford@arm.com>

gcc/
	* tree-vectorizer.h (stmt_vec_info::mask_precision): New field.
	(vect_use_mask_type_p): New function.
	* tree-vect-patterns.c (vect_init_pattern_stmt): Copy the
	mask precision to the pattern statement.
	(append_pattern_def_seq): Add a scalar_type_for_mask parameter
	and use it to initialize the new stmt's mask precision.
	(search_type_for_mask_1): Delete.
	(search_type_for_mask): Replace with...
	(integer_type_for_mask): ...this new function.  Use the information
	cached in the stmt_vec_info.
	(vect_recog_bool_pattern): Update accordingly.
	(build_mask_conversion): Pass the scalar type associated with the
	mask type to append_pattern_def_seq.
	(vect_recog_mask_conversion_pattern): Likewise.  Call
	integer_type_for_mask instead of search_type_for_mask.
	(vect_convert_mask_for_vectype): Call integer_type_for_mask instead
	of search_type_for_mask.
	(possible_vector_mask_operation_p): New function.
	(vect_determine_mask_precision): Likewise.
	(vect_determine_stmt_precisions): Call it.


git-svn-id: https://gcc.gnu.org/svn/gcc/trunk@278850 138bc75d-0d04-0410-961f-82ee72b054a4

3 files changed, 226 insertions, 106 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index d5a4f620be7..e1bd340e4bc 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,28 @@
 2019-11-29  Richard Sandiford  <richard.sandiford@arm.com>
 
+	* tree-vectorizer.h (stmt_vec_info::mask_precision): New field.
+	(vect_use_mask_type_p): New function.
+	* tree-vect-patterns.c (vect_init_pattern_stmt): Copy the
+	mask precision to the pattern statement.
+	(append_pattern_def_seq): Add a scalar_type_for_mask parameter
+	and use it to initialize the new stmt's mask precision.
+	(search_type_for_mask_1): Delete.
+	(search_type_for_mask): Replace with...
+	(integer_type_for_mask): ...this new function.  Use the information
+	cached in the stmt_vec_info.
+	(vect_recog_bool_pattern): Update accordingly.
+	(build_mask_conversion): Pass the scalar type associated with the
+	mask type to append_pattern_def_seq.
+	(vect_recog_mask_conversion_pattern): Likewise.  Call
+	integer_type_for_mask instead of search_type_for_mask.
+	(vect_convert_mask_for_vectype): Call integer_type_for_mask instead
+	of search_type_for_mask.
+	(possible_vector_mask_operation_p): New function.
+	(vect_determine_mask_precision): Likewise.
+	(vect_determine_stmt_precisions): Call it.
+
+2019-11-29  Richard Sandiford  <richard.sandiford@arm.com>
+
 	* tree-vectorizer.h (get_mask_type_for_scalar_type): Replace
 	the slp_tree parameter with a group size parameter.
 	(vect_get_mask_type_for_stmt): Likewise.
diff --git a/gcc/tree-vect-patterns.c b/gcc/tree-vect-patterns.c
index 6985214d435..2e021287b4e 100644
--- a/gcc/tree-vect-patterns.c
+++ b/gcc/tree-vect-patterns.c
@@ -112,7 +112,12 @@ vect_init_pattern_stmt (gimple *pattern_stmt, stmt_vec_info orig_stmt_info,
   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;
+    {
+      gcc_assert (VECTOR_BOOLEAN_TYPE_P (vectype)
+		  == vect_use_mask_type_p (orig_stmt_info));
+      STMT_VINFO_VECTYPE (pattern_stmt_info) = vectype;
+      pattern_stmt_info->mask_precision = orig_stmt_info->mask_precision;
+    }
   return pattern_stmt_info;
 }
 
@@ -131,17 +136,25 @@ vect_set_pattern_stmt (gimple *pattern_stmt, stmt_vec_info orig_stmt_info,
 
 /* Add NEW_STMT to STMT_INFO's pattern definition statements.  If VECTYPE
    is nonnull, record that NEW_STMT's vector type is VECTYPE, which might
-   be different from the vector type of the final pattern statement.  */
+   be different from the vector type of the final pattern statement.
+   If VECTYPE is a mask type, SCALAR_TYPE_FOR_MASK is the scalar type
+   from which it was derived.  */
 
 static inline void
 append_pattern_def_seq (stmt_vec_info stmt_info, gimple *new_stmt,
-			tree vectype = NULL_TREE)
+			tree vectype = NULL_TREE,
+			tree scalar_type_for_mask = NULL_TREE)
 {
+  gcc_assert (!scalar_type_for_mask
+	      == (!vectype || !VECTOR_BOOLEAN_TYPE_P (vectype)));
   vec_info *vinfo = stmt_info->vinfo;
   if (vectype)
     {
       stmt_vec_info new_stmt_info = vinfo->add_stmt (new_stmt);
       STMT_VINFO_VECTYPE (new_stmt_info) = vectype;
+      if (scalar_type_for_mask)
+	new_stmt_info->mask_precision
+	  = GET_MODE_BITSIZE (SCALAR_TYPE_MODE (scalar_type_for_mask));
     }
   gimple_seq_add_stmt_without_update (&STMT_VINFO_PATTERN_DEF_SEQ (stmt_info),
 				      new_stmt);
@@ -3886,108 +3899,22 @@ adjust_bool_stmts (hash_set <gimple *> &bool_stmt_set,
   return gimple_assign_lhs (pattern_stmt);
 }
 
-/* Helper for search_type_for_mask.  */
+/* Return the proper type for converting bool VAR into
+   an integer value or NULL_TREE if no such type exists.
+   The type is chosen so that the converted value has the
+   same number of elements as VAR's vector type.  */
 
 static tree
-search_type_for_mask_1 (tree var, vec_info *vinfo,
-			hash_map<gimple *, tree> &cache)
+integer_type_for_mask (tree var, vec_info *vinfo)
 {
-  tree rhs1;
-  enum tree_code rhs_code;
-  tree res = NULL_TREE, res2;
-
   if (!VECT_SCALAR_BOOLEAN_TYPE_P (TREE_TYPE (var)))
     return NULL_TREE;
 
   stmt_vec_info def_stmt_info = vect_get_internal_def (vinfo, var);
-  if (!def_stmt_info)
+  if (!def_stmt_info || !vect_use_mask_type_p (def_stmt_info))
     return NULL_TREE;
 
-  gassign *def_stmt = dyn_cast <gassign *> (def_stmt_info->stmt);
-  if (!def_stmt)
-    return NULL_TREE;
-
-  tree *c = cache.get (def_stmt);
-  if (c)
-    return *c;
-
-  rhs_code = gimple_assign_rhs_code (def_stmt);
-  rhs1 = gimple_assign_rhs1 (def_stmt);
-
-  switch (rhs_code)
-    {
-    case SSA_NAME:
-    case BIT_NOT_EXPR:
-    CASE_CONVERT:
-      res = search_type_for_mask_1 (rhs1, vinfo, cache);
-      break;
-
-    case BIT_AND_EXPR:
-    case BIT_IOR_EXPR:
-    case BIT_XOR_EXPR:
-      res = search_type_for_mask_1 (rhs1, vinfo, cache);
-      res2 = search_type_for_mask_1 (gimple_assign_rhs2 (def_stmt), vinfo,
-				     cache);
-      if (!res || (res2 && TYPE_PRECISION (res) > TYPE_PRECISION (res2)))
-	res = res2;
-      break;
-
-    default:
-      if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
-	{
-	  tree comp_vectype, mask_type;
-
-	  if (VECT_SCALAR_BOOLEAN_TYPE_P (TREE_TYPE (rhs1)))
-	    {
-	      res = search_type_for_mask_1 (rhs1, vinfo, cache);
-	      res2 = search_type_for_mask_1 (gimple_assign_rhs2 (def_stmt),
-					     vinfo, cache);
-	      if (!res || (res2 && TYPE_PRECISION (res) > TYPE_PRECISION (res2)))
-		res = res2;
-	      if (res)
-		break;
-	    }
-
-	  comp_vectype = get_vectype_for_scalar_type (vinfo, TREE_TYPE (rhs1));
-	  if (comp_vectype == NULL_TREE)
-	    {
-	      res = NULL_TREE;
-	      break;
-	    }
-
-	  mask_type = get_mask_type_for_scalar_type (vinfo, TREE_TYPE (rhs1));
-	  if (!mask_type
-	      || !expand_vec_cmp_expr_p (comp_vectype, mask_type, rhs_code))
-	    {
-	      res = NULL_TREE;
-	      break;
-	    }
-
-	  if (TREE_CODE (TREE_TYPE (rhs1)) != INTEGER_TYPE
-	      || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
-	    {
-	      scalar_mode mode = SCALAR_TYPE_MODE (TREE_TYPE (rhs1));
-	      res = build_nonstandard_integer_type (GET_MODE_BITSIZE (mode), 1);
-	    }
-	  else
-	    res = TREE_TYPE (rhs1);
-	}
-    }
-
-  cache.put (def_stmt, res);
-  return res;
-}
-
-/* Return the proper type for converting bool VAR into
-   an integer value or NULL_TREE if no such type exists.
-   The type is chosen so that converted value has the
-   same number of elements as VAR's vector type.  */
-
-static tree
-search_type_for_mask (tree var, vec_info *vinfo)
-{
-  hash_map<gimple *, tree> cache;
-  return search_type_for_mask_1 (var, vinfo, cache);
+  return build_nonstandard_integer_type (def_stmt_info->mask_precision, 1);
 }
 
 /* Function vect_recog_bool_pattern
@@ -4079,7 +4006,7 @@ vect_recog_bool_pattern (stmt_vec_info stmt_vinfo, tree *type_out)
 	}
       else
 	{
-	  tree type = search_type_for_mask (var, vinfo);
+	  tree type = integer_type_for_mask (var, vinfo);
 	  tree cst0, cst1, tmp;
 
 	  if (!type)
@@ -4164,7 +4091,7 @@ vect_recog_bool_pattern (stmt_vec_info stmt_vinfo, tree *type_out)
 	rhs = adjust_bool_stmts (bool_stmts, TREE_TYPE (vectype), stmt_vinfo);
       else
 	{
-	  tree type = search_type_for_mask (var, vinfo);
+	  tree type = integer_type_for_mask (var, vinfo);
 	  tree cst0, cst1, new_vectype;
 
 	  if (!type)
@@ -4219,7 +4146,7 @@ build_mask_conversion (tree mask, tree vectype, stmt_vec_info stmt_vinfo)
   masktype = truth_type_for (vectype);
   tmp = vect_recog_temp_ssa_var (TREE_TYPE (masktype), NULL);
   stmt = gimple_build_assign (tmp, CONVERT_EXPR, mask);
-  append_pattern_def_seq (stmt_vinfo, stmt, masktype);
+  append_pattern_def_seq (stmt_vinfo, stmt, masktype, TREE_TYPE (vectype));
 
   return tmp;
 }
@@ -4285,7 +4212,7 @@ vect_recog_mask_conversion_pattern (stmt_vec_info stmt_vinfo, tree *type_out)
 	}
 
       tree mask_arg = gimple_call_arg (last_stmt, mask_argno);
-      tree mask_arg_type = search_type_for_mask (mask_arg, vinfo);
+      tree mask_arg_type = integer_type_for_mask (mask_arg, vinfo);
       if (!mask_arg_type)
 	return NULL;
       vectype2 = get_mask_type_for_scalar_type (vinfo, mask_arg_type);
@@ -4338,7 +4265,7 @@ vect_recog_mask_conversion_pattern (stmt_vec_info stmt_vinfo, tree *type_out)
 
       if (TREE_CODE (rhs1) == SSA_NAME)
 	{
-	  rhs1_type = search_type_for_mask (rhs1, vinfo);
+	  rhs1_type = integer_type_for_mask (rhs1, vinfo);
 	  if (!rhs1_type)
 	    return NULL;
 	}
@@ -4358,7 +4285,7 @@ vect_recog_mask_conversion_pattern (stmt_vec_info stmt_vinfo, tree *type_out)
 
 	     it is better for b1 and b2 to use the mask type associated
 	     with int elements rather bool (byte) elements.  */
-	  rhs1_type = search_type_for_mask (TREE_OPERAND (rhs1, 0), vinfo);
+	  rhs1_type = integer_type_for_mask (TREE_OPERAND (rhs1, 0), vinfo);
 	  if (!rhs1_type)
 	    rhs1_type = TREE_TYPE (TREE_OPERAND (rhs1, 0));
 	}
@@ -4414,7 +4341,8 @@ vect_recog_mask_conversion_pattern (stmt_vec_info stmt_vinfo, tree *type_out)
 	  tmp = vect_recog_temp_ssa_var (TREE_TYPE (rhs1), NULL);
 	  pattern_stmt = gimple_build_assign (tmp, rhs1);
 	  rhs1 = tmp;
-	  append_pattern_def_seq (stmt_vinfo, pattern_stmt, vectype2);
+	  append_pattern_def_seq (stmt_vinfo, pattern_stmt, vectype2,
+				  rhs1_type);
 	}
 
       if (maybe_ne (TYPE_VECTOR_SUBPARTS (vectype1),
@@ -4447,8 +4375,8 @@ vect_recog_mask_conversion_pattern (stmt_vec_info stmt_vinfo, tree *type_out)
 
   rhs2 = gimple_assign_rhs2 (last_stmt);
 
-  rhs1_type = search_type_for_mask (rhs1, vinfo);
-  rhs2_type = search_type_for_mask (rhs2, vinfo);
+  rhs1_type = integer_type_for_mask (rhs1, vinfo);
+  rhs2_type = integer_type_for_mask (rhs2, vinfo);
 
   if (!rhs1_type || !rhs2_type
       || TYPE_PRECISION (rhs1_type) == TYPE_PRECISION (rhs2_type))
@@ -4509,7 +4437,7 @@ static tree
 vect_convert_mask_for_vectype (tree mask, tree vectype,
 			       stmt_vec_info stmt_info, vec_info *vinfo)
 {
-  tree mask_type = search_type_for_mask (mask, vinfo);
+  tree mask_type = integer_type_for_mask (mask, vinfo);
   if (mask_type)
     {
       tree mask_vectype = get_mask_type_for_scalar_type (vinfo, mask_type);
@@ -4949,6 +4877,148 @@ vect_determine_precisions_from_users (stmt_vec_info stmt_info, gassign *stmt)
   vect_set_min_input_precision (stmt_info, type, min_input_precision);
 }
 
+/* Return true if the statement described by STMT_INFO sets a boolean
+   SSA_NAME and if we know how to vectorize this kind of statement using
+   vector mask types.  */
+
+static bool
+possible_vector_mask_operation_p (stmt_vec_info stmt_info)
+{
+  tree lhs = gimple_get_lhs (stmt_info->stmt);
+  if (!lhs
+      || TREE_CODE (lhs) != SSA_NAME
+      || !VECT_SCALAR_BOOLEAN_TYPE_P (TREE_TYPE (lhs)))
+    return false;
+
+  if (gassign *assign = dyn_cast <gassign *> (stmt_info->stmt))
+    {
+      tree_code rhs_code = gimple_assign_rhs_code (assign);
+      switch (rhs_code)
+	{
+	CASE_CONVERT:
+	case SSA_NAME:
+	case BIT_NOT_EXPR:
+	case BIT_IOR_EXPR:
+	case BIT_XOR_EXPR:
+	case BIT_AND_EXPR:
+	  return true;
+
+	default:
+	  return TREE_CODE_CLASS (rhs_code) == tcc_comparison;
+	}
+    }
+  return false;
+}
+
+/* If STMT_INFO sets a boolean SSA_NAME, see whether we should use
+   a vector mask type instead of a normal vector type.  Record the
+   result in STMT_INFO->mask_precision.  */
+
+static void
+vect_determine_mask_precision (stmt_vec_info stmt_info)
+{
+  vec_info *vinfo = stmt_info->vinfo;
+
+  if (!possible_vector_mask_operation_p (stmt_info)
+      || stmt_info->mask_precision)
+    return;
+
+  auto_vec<stmt_vec_info, 32> worklist;
+  worklist.quick_push (stmt_info);
+  while (!worklist.is_empty ())
+    {
+      stmt_info = worklist.last ();
+      unsigned int orig_length = worklist.length ();
+
+      /* If at least one boolean input uses a vector mask type,
+	 pick the mask type with the narrowest elements.
+
+	 ??? This is the traditional behavior.  It should always produce
+	 the smallest number of operations, but isn't necessarily the
+	 optimal choice.  For example, if we have:
+
+	   a = b & c
+
+	 where:
+
+	 - the user of a wants it to have a mask type for 16-bit elements (M16)
+	 - b also uses M16
+	 - c uses a mask type for 8-bit elements (M8)
+
+	 then picking M8 gives:
+
+	 - 1 M16->M8 pack for b
+	 - 1 M8 AND for a
+	 - 2 M8->M16 unpacks for the user of a
+
+	 whereas picking M16 would have given:
+
+	 - 2 M8->M16 unpacks for c
+	 - 2 M16 ANDs for a
+
+	 The number of operations are equal, but M16 would have given
+	 a shorter dependency chain and allowed more ILP.  */
+      unsigned int precision = ~0U;
+      gassign *assign = as_a <gassign *> (stmt_info->stmt);
+      unsigned int nops = gimple_num_ops (assign);
+      for (unsigned int i = 1; i < nops; ++i)
+	{
+	  tree rhs = gimple_op (assign, i);
+	  if (!VECT_SCALAR_BOOLEAN_TYPE_P (TREE_TYPE (rhs)))
+	    continue;
+
+	  stmt_vec_info def_stmt_info = vinfo->lookup_def (rhs);
+	  if (!def_stmt_info)
+	    /* Don't let external or constant operands influence the choice.
+	       We can convert them to whichever vector type we pick.  */
+	    continue;
+
+	  if (def_stmt_info->mask_precision)
+	    {
+	      if (precision > def_stmt_info->mask_precision)
+		precision = def_stmt_info->mask_precision;
+	    }
+	  else if (possible_vector_mask_operation_p (def_stmt_info))
+	    worklist.safe_push (def_stmt_info);
+	}
+
+      /* Defer the choice if we need to visit operands first.  */
+      if (orig_length != worklist.length ())
+	continue;
+
+      /* If the statement compares two values that shouldn't use vector masks,
+	 try comparing the values as normal scalars instead.  */
+      tree_code rhs_code = gimple_assign_rhs_code (assign);
+      if (precision == ~0U
+	  && TREE_CODE_CLASS (rhs_code) == tcc_comparison)
+	{
+	  tree rhs1_type = TREE_TYPE (gimple_assign_rhs1 (assign));
+	  scalar_mode mode;
+	  tree vectype, mask_type;
+	  if (is_a <scalar_mode> (TYPE_MODE (rhs1_type), &mode)
+	      && (vectype = get_vectype_for_scalar_type (vinfo, rhs1_type))
+	      && (mask_type = get_mask_type_for_scalar_type (vinfo, rhs1_type))
+	      && expand_vec_cmp_expr_p (vectype, mask_type, rhs_code))
+	    precision = GET_MODE_BITSIZE (mode);
+	}
+
+      if (dump_enabled_p ())
+	{
+	  if (precision == ~0U)
+	    dump_printf_loc (MSG_NOTE, vect_location,
+			     "using normal nonmask vectors for %G",
+			     stmt_info->stmt);
+	  else
+	    dump_printf_loc (MSG_NOTE, vect_location,
+			     "using boolean precision %d for %G",
+			     precision, stmt_info->stmt);
+	}
+
+      stmt_info->mask_precision = precision;
+      worklist.pop ();
+    }
+}
+
 /* Handle vect_determine_precisions for STMT_INFO, given that we
    have already done so for the users of its result.  */
 
@@ -4961,6 +5031,7 @@ vect_determine_stmt_precisions (stmt_vec_info stmt_info)
       vect_determine_precisions_from_range (stmt_info, stmt);
       vect_determine_precisions_from_users (stmt_info, stmt);
     }
+  vect_determine_mask_precision (stmt_info);
 }
 
 /* Walk backwards through the vectorizable region to determine the
diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index ad73519afaa..51a13f1d207 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -1089,6 +1089,23 @@ public:
   unsigned int operation_precision;
   signop operation_sign;
 
+  /* If the statement produces a boolean result, this value describes
+     how we should choose the associated vector type.  The possible
+     values are:
+
+     - an integer precision N if we should use the vector mask type
+       associated with N-bit integers.  This is only used if all relevant
+       input booleans also want the vector mask type for N-bit integers,
+       or if we can convert them into that form by pattern-matching.
+
+     - ~0U if we considered choosing a vector mask type but decided
+       to treat the boolean as a normal integer type instead.
+
+     - 0 otherwise.  This means either that the operation isn't one that
+       could have a vector mask type (and so should have a normal vector
+       type instead) or that we simply haven't made a choice either way.  */
+  unsigned int mask_precision;
+
   /* True if this is only suitable for SLP vectorization.  */
   bool slp_vect_only_p;
 };
@@ -1245,6 +1262,15 @@ nested_in_vect_loop_p (class loop *loop, stmt_vec_info stmt_info)
 	  && (loop->inner == (gimple_bb (stmt_info->stmt))->loop_father));
 }
 
+/* Return true if STMT_INFO should produce a vector mask type rather than
+   a normal nonmask type.  */
+
+static inline bool
+vect_use_mask_type_p (stmt_vec_info stmt_info)
+{
+  return stmt_info->mask_precision && stmt_info->mask_precision != ~0U;
+}
+
 /* Return TRUE if a statement represented by STMT_INFO is a part of a
    pattern.  */