--- a/gcc/tree-vect-patterns.c	Thu Oct 25 08:08:40 2018 +0900
+++ b/gcc/tree-vect-patterns.c	Thu Oct 25 10:21:07 2018 +0900
@@ -1,5 +1,5 @@
 /* Analysis Utilities for Loop Vectorization.
-   Copyright (C) 2006-2017 Free Software Foundation, Inc.
+   Copyright (C) 2006-2018 Free Software Foundation, Inc.
    Contributed by Dorit Nuzman <dorit@il.ibm.com>
 
 This file is part of GCC.
@@ -41,127 +41,216 @@
 #include "builtins.h"
 #include "internal-fn.h"
 #include "case-cfn-macros.h"
-
-/* Pattern recognition functions  */
-static gimple *vect_recog_widen_sum_pattern (vec<gimple *> *, tree *,
-					    tree *);
-static gimple *vect_recog_widen_mult_pattern (vec<gimple *> *, tree *,
-					     tree *);
-static gimple *vect_recog_dot_prod_pattern (vec<gimple *> *, tree *,
-					   tree *);
-static gimple *vect_recog_sad_pattern (vec<gimple *> *, tree *,
-				      tree *);
-static gimple *vect_recog_pow_pattern (vec<gimple *> *, tree *, tree *);
-static gimple *vect_recog_over_widening_pattern (vec<gimple *> *, tree *,
-                                                 tree *);
-static gimple *vect_recog_widen_shift_pattern (vec<gimple *> *,
-	                                tree *, tree *);
-static gimple *vect_recog_rotate_pattern (vec<gimple *> *, tree *, tree *);
-static gimple *vect_recog_vector_vector_shift_pattern (vec<gimple *> *,
-						      tree *, tree *);
-static gimple *vect_recog_divmod_pattern (vec<gimple *> *,
-					 tree *, tree *);
-
-static gimple *vect_recog_mult_pattern (vec<gimple *> *,
-				       tree *, tree *);
-
-static gimple *vect_recog_mixed_size_cond_pattern (vec<gimple *> *,
-						  tree *, tree *);
-static gimple *vect_recog_bool_pattern (vec<gimple *> *, tree *, tree *);
-static gimple *vect_recog_mask_conversion_pattern (vec<gimple *> *, tree *, tree *);
-
-struct vect_recog_func
+#include "fold-const-call.h"
+#include "attribs.h"
+#include "cgraph.h"
+#include "omp-simd-clone.h"
+#include "predict.h"
+
+/* Return true if we have a useful VR_RANGE range for VAR, storing it
+   in *MIN_VALUE and *MAX_VALUE if so.  Note the range in the dump files.  */
+
+static bool
+vect_get_range_info (tree var, wide_int *min_value, wide_int *max_value)
 {
-  vect_recog_func_ptr fn;
-  const char *name;
-};
-
-/* Note that ordering matters - the first pattern matching on a stmt
-   is taken which means usually the more complex one needs to preceed
-   the less comples onex (widen_sum only after dot_prod or sad for example).  */
-static vect_recog_func vect_vect_recog_func_ptrs[NUM_PATTERNS] = {
-      { vect_recog_widen_mult_pattern, "widen_mult" },
-      { vect_recog_dot_prod_pattern, "dot_prod" },
-      { vect_recog_sad_pattern, "sad" },
-      { vect_recog_widen_sum_pattern, "widen_sum" },
-      { vect_recog_pow_pattern, "pow" },
-      { vect_recog_widen_shift_pattern, "widen_shift" },
-      { vect_recog_over_widening_pattern, "over_widening" },
-      { vect_recog_rotate_pattern, "rotate" },
-      { vect_recog_vector_vector_shift_pattern, "vector_vector_shift" },
-      {	vect_recog_divmod_pattern, "divmod" },
-      {	vect_recog_mult_pattern, "mult" },
-      {	vect_recog_mixed_size_cond_pattern, "mixed_size_cond" },
-      {	vect_recog_bool_pattern, "bool" },
-      {	vect_recog_mask_conversion_pattern, "mask_conversion" }
-};
+  value_range_kind vr_type = get_range_info (var, min_value, max_value);
+  wide_int nonzero = get_nonzero_bits (var);
+  signop sgn = TYPE_SIGN (TREE_TYPE (var));
+  if (intersect_range_with_nonzero_bits (vr_type, min_value, max_value,
+					 nonzero, sgn) == VR_RANGE)
+    {
+      if (dump_enabled_p ())
+	{
+	  dump_generic_expr_loc (MSG_NOTE, vect_location, TDF_SLIM, var);
+	  dump_printf (MSG_NOTE, " has range [");
+	  dump_hex (MSG_NOTE, *min_value);
+	  dump_printf (MSG_NOTE, ", ");
+	  dump_hex (MSG_NOTE, *max_value);
+	  dump_printf (MSG_NOTE, "]\n");
+	}
+      return true;
+    }
+  else
+    {
+      if (dump_enabled_p ())
+	{
+	  dump_generic_expr_loc (MSG_NOTE, vect_location, TDF_SLIM, var);
+	  dump_printf (MSG_NOTE, " has no range info\n");
+	}
+      return false;
+    }
+}
+
+/* Report that we've found an instance of pattern PATTERN in
+   statement STMT.  */
+
+static void
+vect_pattern_detected (const char *name, gimple *stmt)
+{
+  if (dump_enabled_p ())
+    dump_printf_loc (MSG_NOTE, vect_location, "%s: detected: %G", name, stmt);
+}
+
+/* Associate pattern statement PATTERN_STMT with ORIG_STMT_INFO and
+   return the pattern statement's stmt_vec_info.  Set its vector type to
+   VECTYPE if it doesn't have one already.  */
+
+static stmt_vec_info
+vect_init_pattern_stmt (gimple *pattern_stmt, stmt_vec_info orig_stmt_info,
+			tree vectype)
+{
+  vec_info *vinfo = orig_stmt_info->vinfo;
+  stmt_vec_info pattern_stmt_info = vinfo->lookup_stmt (pattern_stmt);
+  if (pattern_stmt_info == NULL)
+    pattern_stmt_info = orig_stmt_info->vinfo->add_stmt (pattern_stmt);
+  gimple_set_bb (pattern_stmt, gimple_bb (orig_stmt_info->stmt));
+
+  pattern_stmt_info->pattern_stmt_p = true;
+  STMT_VINFO_RELATED_STMT (pattern_stmt_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;
+  return pattern_stmt_info;
+}
+
+/* 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)
+    = vect_init_pattern_stmt (pattern_stmt, orig_stmt_info, vectype);
+}
+
+/* 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.  */
 
 static inline void
-append_pattern_def_seq (stmt_vec_info stmt_info, gimple *stmt)
+append_pattern_def_seq (stmt_vec_info stmt_info, gimple *new_stmt,
+			tree vectype = NULL_TREE)
 {
+  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;
+    }
   gimple_seq_add_stmt_without_update (&STMT_VINFO_PATTERN_DEF_SEQ (stmt_info),
-				      stmt);
+				      new_stmt);
 }
 
-static inline void
-new_pattern_def_seq (stmt_vec_info stmt_info, gimple *stmt)
+/* The caller wants to perform new operations on vect_external variable
+   VAR, so that the result of the operations would also be vect_external.
+   Return the edge on which the operations can be performed, if one exists.
+   Return null if the operations should instead be treated as part of
+   the pattern that needs them.  */
+
+static edge
+vect_get_external_def_edge (vec_info *vinfo, tree var)
 {
-  STMT_VINFO_PATTERN_DEF_SEQ (stmt_info) = NULL;
-  append_pattern_def_seq (stmt_info, stmt);
+  edge e = NULL;
+  if (loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo))
+    {
+      e = loop_preheader_edge (loop_vinfo->loop);
+      if (!SSA_NAME_IS_DEFAULT_DEF (var))
+	{
+	  basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (var));
+	  if (bb == NULL
+	      || !dominated_by_p (CDI_DOMINATORS, e->dest, bb))
+	    e = NULL;
+	}
+    }
+  return e;
 }
 
-/* Check whether STMT2 is in the same loop or basic block as STMT1.
-   Which of the two applies depends on whether we're currently doing
-   loop-based or basic-block-based vectorization, as determined by
-   the vinfo_for_stmt for STMT1 (which must be defined).
-
-   If this returns true, vinfo_for_stmt for STMT2 is guaranteed
-   to be defined as well.  */
+/* Return true if the target supports a vector version of CODE,
+   where CODE is known to map to a direct optab.  ITYPE specifies
+   the type of (some of) the scalar inputs and OTYPE specifies the
+   type of the scalar result.
+
+   If CODE allows the inputs and outputs to have different type
+   (such as for WIDEN_SUM_EXPR), it is the input mode rather
+   than the output mode that determines the appropriate target pattern.
+   Operand 0 of the target pattern then specifies the mode that the output
+   must have.
+
+   When returning true, set *VECOTYPE_OUT to the vector version of OTYPE.
+   Also set *VECITYPE_OUT to the vector version of ITYPE if VECITYPE_OUT
+   is nonnull.  */
 
 static bool
-vect_same_loop_or_bb_p (gimple *stmt1, gimple *stmt2)
-{
-  stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt1);
-  return vect_stmt_in_region_p (stmt_vinfo->vinfo, stmt2);
-}
-
-/* If the LHS of DEF_STMT has a single use, and that statement is
-   in the same loop or basic block, return it.  */
-
-static gimple *
-vect_single_imm_use (gimple *def_stmt)
+vect_supportable_direct_optab_p (tree otype, tree_code code,
+				 tree itype, tree *vecotype_out,
+				 tree *vecitype_out = NULL)
 {
-  tree lhs = gimple_assign_lhs (def_stmt);
-  use_operand_p use_p;
-  gimple *use_stmt;
-
-  if (!single_imm_use (lhs, &use_p, &use_stmt))
-    return NULL;
-
-  if (!vect_same_loop_or_bb_p (def_stmt, use_stmt))
-    return NULL;
-
-  return use_stmt;
+  tree vecitype = get_vectype_for_scalar_type (itype);
+  if (!vecitype)
+    return false;
+
+  tree vecotype = get_vectype_for_scalar_type (otype);
+  if (!vecotype)
+    return false;
+
+  optab optab = optab_for_tree_code (code, vecitype, optab_default);
+  if (!optab)
+    return false;
+
+  insn_code icode = optab_handler (optab, TYPE_MODE (vecitype));
+  if (icode == CODE_FOR_nothing
+      || insn_data[icode].operand[0].mode != TYPE_MODE (vecotype))
+    return false;
+
+  *vecotype_out = vecotype;
+  if (vecitype_out)
+    *vecitype_out = vecitype;
+  return true;
 }
 
-/* Check whether NAME, an ssa-name used in USE_STMT,
+/* Round bit precision PRECISION up to a full element.  */
+
+static unsigned int
+vect_element_precision (unsigned int precision)
+{
+  precision = 1 << ceil_log2 (precision);
+  return MAX (precision, BITS_PER_UNIT);
+}
+
+/* If OP is defined by a statement that's being considered for vectorization,
+   return information about that statement, otherwise return NULL.  */
+
+static stmt_vec_info
+vect_get_internal_def (vec_info *vinfo, tree op)
+{
+  stmt_vec_info def_stmt_info = vinfo->lookup_def (op);
+  if (def_stmt_info
+      && STMT_VINFO_DEF_TYPE (def_stmt_info) == vect_internal_def)
+    return def_stmt_info;
+  return NULL;
+}
+
+/* Check whether NAME, an ssa-name used in STMT_VINFO,
    is a result of a type promotion, such that:
      DEF_STMT: NAME = NOP (name0)
    If CHECK_SIGN is TRUE, check that either both types are signed or both are
    unsigned.  */
 
 static bool
-type_conversion_p (tree name, gimple *use_stmt, bool check_sign,
+type_conversion_p (tree name, stmt_vec_info stmt_vinfo, bool check_sign,
 		   tree *orig_type, gimple **def_stmt, bool *promotion)
 {
-  gimple *dummy_gimple;
-  stmt_vec_info stmt_vinfo;
   tree type = TREE_TYPE (name);
   tree oprnd0;
   enum vect_def_type dt;
 
-  stmt_vinfo = vinfo_for_stmt (use_stmt);
-  if (!vect_is_simple_use (name, stmt_vinfo->vinfo, def_stmt, &dt))
+  stmt_vec_info def_stmt_info;
+  if (!vect_is_simple_use (name, stmt_vinfo->vinfo, &dt, &def_stmt_info,
+			   def_stmt))
     return false;
 
   if (dt != vect_internal_def
@@ -171,13 +260,6 @@
   if (!*def_stmt)
     return false;
 
-  if (dt == vect_internal_def)
-    {
-      stmt_vec_info def_vinfo = vinfo_for_stmt (*def_stmt);
-      if (STMT_VINFO_IN_PATTERN_P (def_vinfo))
-	return false;
-    }
-
   if (!is_gimple_assign (*def_stmt))
     return false;
 
@@ -196,12 +278,338 @@
   else
     *promotion = false;
 
-  if (!vect_is_simple_use (oprnd0, stmt_vinfo->vinfo, &dummy_gimple, &dt))
+  if (!vect_is_simple_use (oprnd0, stmt_vinfo->vinfo, &dt))
     return false;
 
   return true;
 }
 
+/* Holds information about an input operand after some sign changes
+   and type promotions have been peeled away.  */
+struct vect_unpromoted_value {
+  vect_unpromoted_value ();
+
+  void set_op (tree, vect_def_type, stmt_vec_info = NULL);
+
+  /* The value obtained after peeling away zero or more casts.  */
+  tree op;
+
+  /* The type of OP.  */
+  tree type;
+
+  /* The definition type of OP.  */
+  vect_def_type dt;
+
+  /* If OP is the result of peeling at least one cast, and if the cast
+     of OP itself is a vectorizable statement, CASTER identifies that
+     statement, otherwise it is null.  */
+  stmt_vec_info caster;
+};
+
+inline vect_unpromoted_value::vect_unpromoted_value ()
+  : op (NULL_TREE),
+    type (NULL_TREE),
+    dt (vect_uninitialized_def),
+    caster (NULL)
+{
+}
+
+/* Set the operand to OP_IN, its definition type to DT_IN, and the
+   statement that casts it to CASTER_IN.  */
+
+inline void
+vect_unpromoted_value::set_op (tree op_in, vect_def_type dt_in,
+			       stmt_vec_info caster_in)
+{
+  op = op_in;
+  type = TREE_TYPE (op);
+  dt = dt_in;
+  caster = caster_in;
+}
+
+/* If OP is a vectorizable SSA name, strip a sequence of integer conversions
+   to reach some vectorizable inner operand OP', continuing as long as it
+   is possible to convert OP' back to OP using a possible sign change
+   followed by a possible promotion P.  Return this OP', or null if OP is
+   not a vectorizable SSA name.  If there is a promotion P, describe its
+   input in UNPROM, otherwise describe OP' in UNPROM.  If SINGLE_USE_P
+   is nonnull, set *SINGLE_USE_P to false if any of the SSA names involved
+   have more than one user.
+
+   A successful return means that it is possible to go from OP' to OP
+   via UNPROM.  The cast from OP' to UNPROM is at most a sign change,
+   whereas the cast from UNPROM to OP might be a promotion, a sign
+   change, or a nop.
+
+   E.g. say we have:
+
+       signed short *ptr = ...;
+       signed short C = *ptr;
+       unsigned short B = (unsigned short) C;    // sign change
+       signed int A = (signed int) B;            // unsigned promotion
+       ...possible other uses of A...
+       unsigned int OP = (unsigned int) A;       // sign change
+
+   In this case it's possible to go directly from C to OP using:
+
+       OP = (unsigned int) (unsigned short) C;
+	    +------------+ +--------------+
+	       promotion      sign change
+
+   so OP' would be C.  The input to the promotion is B, so UNPROM
+   would describe B.  */
+
+static tree
+vect_look_through_possible_promotion (vec_info *vinfo, tree op,
+				      vect_unpromoted_value *unprom,
+				      bool *single_use_p = NULL)
+{
+  tree res = NULL_TREE;
+  tree op_type = TREE_TYPE (op);
+  unsigned int orig_precision = TYPE_PRECISION (op_type);
+  stmt_vec_info caster = NULL;
+  while (TREE_CODE (op) == SSA_NAME && INTEGRAL_TYPE_P (op_type))
+    {
+      /* See whether OP is simple enough to vectorize.  */
+      stmt_vec_info def_stmt_info;
+      gimple *def_stmt;
+      vect_def_type dt;
+      if (!vect_is_simple_use (op, vinfo, &dt, &def_stmt_info, &def_stmt))
+	break;
+
+      /* If OP is the input of a demotion, skip over it to see whether
+	 OP is itself the result of a promotion.  If so, the combined
+	 effect of the promotion and the demotion might fit the required
+	 pattern, otherwise neither operation fits.
+
+	 This copes with cases such as the result of an arithmetic
+	 operation being truncated before being stored, and where that
+	 arithmetic operation has been recognized as an over-widened one.  */
+      if (TYPE_PRECISION (op_type) <= orig_precision)
+	{
+	  /* Use OP as the UNPROM described above if we haven't yet
+	     found a promotion, or if using the new input preserves the
+	     sign of the previous promotion.  */
+	  if (!res
+	      || TYPE_PRECISION (unprom->type) == orig_precision
+	      || TYPE_SIGN (unprom->type) == TYPE_SIGN (op_type))
+	    unprom->set_op (op, dt, caster);
+	  /* Stop if we've already seen a promotion and if this
+	     conversion does more than change the sign.  */
+	  else if (TYPE_PRECISION (op_type)
+		   != TYPE_PRECISION (unprom->type))
+	    break;
+
+	  /* The sequence now extends to OP.  */
+	  res = op;
+	}
+
+      /* See whether OP is defined by a cast.  Record it as CASTER if
+	 the cast is potentially vectorizable.  */
+      if (!def_stmt)
+	break;
+      caster = def_stmt_info;
+
+      /* Ignore pattern statements, since we don't link uses for them.  */
+      if (caster
+	  && single_use_p
+	  && !STMT_VINFO_RELATED_STMT (caster)
+	  && !has_single_use (res))
+	*single_use_p = false;
+
+      gassign *assign = dyn_cast <gassign *> (def_stmt);
+      if (!assign || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
+	break;
+
+      /* Continue with the input to the cast.  */
+      op = gimple_assign_rhs1 (def_stmt);
+      op_type = TREE_TYPE (op);
+    }
+  return res;
+}
+
+/* OP is an integer operand to an operation that returns TYPE, and we
+   want to treat the operation as a widening one.  So far we can treat
+   it as widening from *COMMON_TYPE.
+
+   Return true if OP is suitable for such a widening operation,
+   either widening from *COMMON_TYPE or from some supertype of it.
+   Update *COMMON_TYPE to the supertype in the latter case.
+
+   SHIFT_P is true if OP is a shift amount.  */
+
+static bool
+vect_joust_widened_integer (tree type, bool shift_p, tree op,
+			    tree *common_type)
+{
+  /* Calculate the minimum precision required by OP, without changing
+     the sign of either operand.  */
+  unsigned int precision;
+  if (shift_p)
+    {
+      if (!wi::leu_p (wi::to_widest (op), TYPE_PRECISION (type) / 2))
+	return false;
+      precision = TREE_INT_CST_LOW (op);
+    }
+  else
+    {
+      precision = wi::min_precision (wi::to_widest (op),
+				     TYPE_SIGN (*common_type));
+      if (precision * 2 > TYPE_PRECISION (type))
+	return false;
+    }
+
+  /* If OP requires a wider type, switch to that type.  The checks
+     above ensure that this is still narrower than the result.  */
+  precision = vect_element_precision (precision);
+  if (TYPE_PRECISION (*common_type) < precision)
+    *common_type = build_nonstandard_integer_type
+      (precision, TYPE_UNSIGNED (*common_type));
+  return true;
+}
+
+/* Return true if the common supertype of NEW_TYPE and *COMMON_TYPE
+   is narrower than type, storing the supertype in *COMMON_TYPE if so.  */
+
+static bool
+vect_joust_widened_type (tree type, tree new_type, tree *common_type)
+{
+  if (types_compatible_p (*common_type, new_type))
+    return true;
+
+  /* See if *COMMON_TYPE can hold all values of NEW_TYPE.  */
+  if ((TYPE_PRECISION (new_type) < TYPE_PRECISION (*common_type))
+      && (TYPE_UNSIGNED (new_type) || !TYPE_UNSIGNED (*common_type)))
+    return true;
+
+  /* See if NEW_TYPE can hold all values of *COMMON_TYPE.  */
+  if (TYPE_PRECISION (*common_type) < TYPE_PRECISION (new_type)
+      && (TYPE_UNSIGNED (*common_type) || !TYPE_UNSIGNED (new_type)))
+    {
+      *common_type = new_type;
+      return true;
+    }
+
+  /* We have mismatched signs, with the signed type being
+     no wider than the unsigned type.  In this case we need
+     a wider signed type.  */
+  unsigned int precision = MAX (TYPE_PRECISION (*common_type),
+				TYPE_PRECISION (new_type));
+  precision *= 2;
+  if (precision * 2 > TYPE_PRECISION (type))
+    return false;
+
+  *common_type = build_nonstandard_integer_type (precision, false);
+  return true;
+}
+
+/* Check whether STMT_INFO can be viewed as a tree of integer operations
+   in which each node either performs CODE or WIDENED_CODE, and where
+   each leaf operand is narrower than the result of STMT_INFO.  MAX_NOPS
+   specifies the maximum number of leaf operands.  SHIFT_P says whether
+   CODE and WIDENED_CODE are some sort of shift.
+
+   If STMT_INFO is such a tree, return the number of leaf operands
+   and describe them in UNPROM[0] onwards.  Also set *COMMON_TYPE
+   to a type that (a) is narrower than the result of STMT_INFO and
+   (b) can hold all leaf operand values.
+
+   Return 0 if STMT_INFO isn't such a tree, or if no such COMMON_TYPE
+   exists.  */
+
+static unsigned int
+vect_widened_op_tree (stmt_vec_info stmt_info, tree_code code,
+		      tree_code widened_code, bool shift_p,
+		      unsigned int max_nops,
+		      vect_unpromoted_value *unprom, tree *common_type)
+{
+  /* Check for an integer operation with the right code.  */
+  vec_info *vinfo = stmt_info->vinfo;
+  gassign *assign = dyn_cast <gassign *> (stmt_info->stmt);
+  if (!assign)
+    return 0;
+
+  tree_code rhs_code = gimple_assign_rhs_code (assign);
+  if (rhs_code != code && rhs_code != widened_code)
+    return 0;
+
+  tree type = gimple_expr_type (assign);
+  if (!INTEGRAL_TYPE_P (type))
+    return 0;
+
+  /* Assume that both operands will be leaf operands.  */
+  max_nops -= 2;
+
+  /* Check the operands.  */
+  unsigned int next_op = 0;
+  for (unsigned int i = 0; i < 2; ++i)
+    {
+      vect_unpromoted_value *this_unprom = &unprom[next_op];
+      unsigned int nops = 1;
+      tree op = gimple_op (assign, i + 1);
+      if (i == 1 && TREE_CODE (op) == INTEGER_CST)
+	{
+	  /* We already have a common type from earlier operands.
+	     Update it to account for OP.  */
+	  this_unprom->set_op (op, vect_constant_def);
+	  if (!vect_joust_widened_integer (type, shift_p, op, common_type))
+	    return 0;
+	}
+      else
+	{
+	  /* Only allow shifts by constants.  */
+	  if (shift_p && i == 1)
+	    return 0;
+
+	  if (!vect_look_through_possible_promotion (stmt_info->vinfo, op,
+						     this_unprom))
+	    return 0;
+
+	  if (TYPE_PRECISION (this_unprom->type) == TYPE_PRECISION (type))
+	    {
+	      /* The operand isn't widened.  If STMT_INFO has the code
+		 for an unwidened operation, recursively check whether
+		 this operand is a node of the tree.  */
+	      if (rhs_code != code
+		  || max_nops == 0
+		  || this_unprom->dt != vect_internal_def)
+		return 0;
+
+	      /* Give back the leaf slot allocated above now that we're
+		 not treating this as a leaf operand.  */
+	      max_nops += 1;
+
+	      /* Recursively process the definition of the operand.  */
+	      stmt_vec_info def_stmt_info
+		= vinfo->lookup_def (this_unprom->op);
+	      nops = vect_widened_op_tree (def_stmt_info, code, widened_code,
+					   shift_p, max_nops, this_unprom,
+					   common_type);
+	      if (nops == 0)
+		return 0;
+
+	      max_nops -= nops;
+	    }
+	  else
+	    {
+	      /* Make sure that the operand is narrower than the result.  */
+	      if (TYPE_PRECISION (this_unprom->type) * 2
+		  > TYPE_PRECISION (type))
+		return 0;
+
+	      /* Update COMMON_TYPE for the new operand.  */
+	      if (i == 0)
+		*common_type = this_unprom->type;
+	      else if (!vect_joust_widened_type (type, this_unprom->type,
+						 common_type))
+		return 0;
+	    }
+	}
+      next_op += nops;
+    }
+  return next_op;
+}
+
 /* Helper to return a new temporary for pattern of TYPE for STMT.  If STMT
    is NULL, the caller must set SSA_NAME_DEF_STMT for the returned SSA var. */
 
@@ -211,6 +619,227 @@
   return make_temp_ssa_name (type, stmt, "patt");
 }
 
+/* STMT2_INFO describes a type conversion that could be split into STMT1
+   followed by a version of STMT2_INFO that takes NEW_RHS as its first
+   input.  Try to do this using pattern statements, returning true on
+   success.  */
+
+static bool
+vect_split_statement (stmt_vec_info stmt2_info, tree new_rhs,
+		      gimple *stmt1, tree vectype)
+{
+  if (is_pattern_stmt_p (stmt2_info))
+    {
+      /* STMT2_INFO is part of a pattern.  Get the statement to which
+	 the pattern is attached.  */
+      stmt_vec_info orig_stmt2_info = STMT_VINFO_RELATED_STMT (stmt2_info);
+      vect_init_pattern_stmt (stmt1, orig_stmt2_info, vectype);
+
+      if (dump_enabled_p ())
+	dump_printf_loc (MSG_NOTE, vect_location,
+			 "Splitting pattern statement: %G", stmt2_info->stmt);
+
+      /* Since STMT2_INFO is a pattern statement, we can change it
+	 in-situ without worrying about changing the code for the
+	 containing block.  */
+      gimple_assign_set_rhs1 (stmt2_info->stmt, new_rhs);
+
+      if (dump_enabled_p ())
+	{
+	  dump_printf_loc (MSG_NOTE, vect_location, "into: %G", stmt1);
+	  dump_printf_loc (MSG_NOTE, vect_location, "and: %G",
+			   stmt2_info->stmt);
+	}
+
+      gimple_seq *def_seq = &STMT_VINFO_PATTERN_DEF_SEQ (orig_stmt2_info);
+      if (STMT_VINFO_RELATED_STMT (orig_stmt2_info) == stmt2_info)
+	/* STMT2_INFO is the actual pattern statement.  Add STMT1
+	   to the end of the definition sequence.  */
+	gimple_seq_add_stmt_without_update (def_seq, stmt1);
+      else
+	{
+	  /* STMT2_INFO belongs to the definition sequence.  Insert STMT1
+	     before it.  */
+	  gimple_stmt_iterator gsi = gsi_for_stmt (stmt2_info->stmt, def_seq);
+	  gsi_insert_before_without_update (&gsi, stmt1, GSI_SAME_STMT);
+	}
+      return true;
+    }
+  else
+    {
+      /* STMT2_INFO doesn't yet have a pattern.  Try to create a
+	 two-statement pattern now.  */
+      gcc_assert (!STMT_VINFO_RELATED_STMT (stmt2_info));
+      tree lhs_type = TREE_TYPE (gimple_get_lhs (stmt2_info->stmt));
+      tree lhs_vectype = get_vectype_for_scalar_type (lhs_type);
+      if (!lhs_vectype)
+	return false;
+
+      if (dump_enabled_p ())
+	dump_printf_loc (MSG_NOTE, vect_location,
+			 "Splitting statement: %G", stmt2_info->stmt);
+
+      /* Add STMT1 as a singleton pattern definition sequence.  */
+      gimple_seq *def_seq = &STMT_VINFO_PATTERN_DEF_SEQ (stmt2_info);
+      vect_init_pattern_stmt (stmt1, stmt2_info, vectype);
+      gimple_seq_add_stmt_without_update (def_seq, stmt1);
+
+      /* Build the second of the two pattern statements.  */
+      tree new_lhs = vect_recog_temp_ssa_var (lhs_type, NULL);
+      gassign *new_stmt2 = gimple_build_assign (new_lhs, NOP_EXPR, new_rhs);
+      vect_set_pattern_stmt (new_stmt2, stmt2_info, lhs_vectype);
+
+      if (dump_enabled_p ())
+	{
+	  dump_printf_loc (MSG_NOTE, vect_location,
+			   "into pattern statements: %G", stmt1);
+	  dump_printf_loc (MSG_NOTE, vect_location, "and: %G", new_stmt2);
+	}
+
+      return true;
+    }
+}
+
+/* Convert UNPROM to TYPE and return the result, adding new statements
+   to STMT_INFO's pattern definition statements if no better way is
+   available.  VECTYPE is the vector form of TYPE.  */
+
+static tree
+vect_convert_input (stmt_vec_info stmt_info, tree type,
+		    vect_unpromoted_value *unprom, tree vectype)
+{
+  /* Check for a no-op conversion.  */
+  if (types_compatible_p (type, TREE_TYPE (unprom->op)))
+    return unprom->op;
+
+  /* Allow the caller to create constant vect_unpromoted_values.  */
+  if (TREE_CODE (unprom->op) == INTEGER_CST)
+    return wide_int_to_tree (type, wi::to_widest (unprom->op));
+
+  /* See if we can reuse an existing result.  */
+  if (unprom->caster)
+    {
+      tree lhs = gimple_get_lhs (unprom->caster->stmt);
+      if (types_compatible_p (TREE_TYPE (lhs), type))
+	return lhs;
+    }
+
+  /* We need a new conversion statement.  */
+  tree new_op = vect_recog_temp_ssa_var (type, NULL);
+  gassign *new_stmt = gimple_build_assign (new_op, NOP_EXPR, unprom->op);
+
+  /* If the operation is the input to a vectorizable cast, try splitting
+     that cast into two, taking the required result as a mid-way point.  */
+  if (unprom->caster)
+    {
+      tree lhs = gimple_get_lhs (unprom->caster->stmt);
+      if (TYPE_PRECISION (TREE_TYPE (lhs)) > TYPE_PRECISION (type)
+	  && TYPE_PRECISION (type) > TYPE_PRECISION (unprom->type)
+	  && (TYPE_UNSIGNED (unprom->type) || !TYPE_UNSIGNED (type))
+	  && vect_split_statement (unprom->caster, new_op, new_stmt, vectype))
+	return new_op;
+    }
+
+  /* If OP is an external value, see if we can insert the new statement
+     on an incoming edge.  */
+  if (unprom->dt == vect_external_def)
+    if (edge e = vect_get_external_def_edge (stmt_info->vinfo, unprom->op))
+      {
+	basic_block new_bb = gsi_insert_on_edge_immediate (e, new_stmt);
+	gcc_assert (!new_bb);
+	return new_op;
+      }
+
+  /* As a (common) last resort, add the statement to the pattern itself.  */
+  append_pattern_def_seq (stmt_info, new_stmt, vectype);
+  return new_op;
+}
+
+/* Invoke vect_convert_input for N elements of UNPROM and store the
+   result in the corresponding elements of RESULT.  */
+
+static void
+vect_convert_inputs (stmt_vec_info stmt_info, unsigned int n,
+		     tree *result, tree type, vect_unpromoted_value *unprom,
+		     tree vectype)
+{
+  for (unsigned int i = 0; i < n; ++i)
+    {
+      unsigned int j;
+      for (j = 0; j < i; ++j)
+	if (unprom[j].op == unprom[i].op)
+	  break;
+      if (j < i)
+	result[i] = result[j];
+      else
+	result[i] = vect_convert_input (stmt_info, type, &unprom[i], vectype);
+    }
+}
+
+/* The caller has created a (possibly empty) sequence of pattern definition
+   statements followed by a single statement PATTERN_STMT.  Cast the result
+   of this final statement to TYPE.  If a new statement is needed, add
+   PATTERN_STMT to the end of STMT_INFO's pattern definition statements
+   and return the new statement, otherwise return PATTERN_STMT as-is.
+   VECITYPE is the vector form of PATTERN_STMT's result type.  */
+
+static gimple *
+vect_convert_output (stmt_vec_info stmt_info, tree type, gimple *pattern_stmt,
+		     tree vecitype)
+{
+  tree lhs = gimple_get_lhs (pattern_stmt);
+  if (!types_compatible_p (type, TREE_TYPE (lhs)))
+    {
+      append_pattern_def_seq (stmt_info, pattern_stmt, vecitype);
+      tree cast_var = vect_recog_temp_ssa_var (type, NULL);
+      pattern_stmt = gimple_build_assign (cast_var, NOP_EXPR, lhs);
+    }
+  return pattern_stmt;
+}
+
+/* Return true if STMT_VINFO describes a reduction for which reassociation
+   is allowed.  If STMT_INFO is part of a group, assume that it's part of
+   a reduction chain and optimistically assume that all statements
+   except the last allow reassociation.  */
+
+static bool
+vect_reassociating_reduction_p (stmt_vec_info stmt_vinfo)
+{
+  return (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def
+	  ? STMT_VINFO_REDUC_TYPE (stmt_vinfo) != FOLD_LEFT_REDUCTION
+	  : REDUC_GROUP_FIRST_ELEMENT (stmt_vinfo) != NULL);
+}
+
+/* As above, but also require it to have code CODE and to be a reduction
+   in the outermost loop.  When returning true, store the operands in
+   *OP0_OUT and *OP1_OUT.  */
+
+static bool
+vect_reassociating_reduction_p (stmt_vec_info stmt_info, tree_code code,
+				tree *op0_out, tree *op1_out)
+{
+  loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_info);
+  if (!loop_info)
+    return false;
+
+  gassign *assign = dyn_cast <gassign *> (stmt_info->stmt);
+  if (!assign || gimple_assign_rhs_code (assign) != code)
+    return false;
+
+  /* We don't allow changing the order of the computation in the inner-loop
+     when doing outer-loop vectorization.  */
+  struct loop *loop = LOOP_VINFO_LOOP (loop_info);
+  if (loop && nested_in_vect_loop_p (loop, stmt_info))
+    return false;
+
+  if (!vect_reassociating_reduction_p (stmt_info))
+    return false;
+
+  *op0_out = gimple_assign_rhs1 (assign);
+  *op1_out = gimple_assign_rhs2 (assign);
+  return true;
+}
+
 /* Function vect_recog_dot_prod_pattern
 
    Try to find the following pattern:
@@ -234,14 +863,12 @@
 
    Input:
 
-   * STMTS: Contains a stmt from which the pattern search begins.  In the
+   * STMT_VINFO: The stmt from which the pattern search begins.  In the
    example, when this function is called with S7, the pattern {S3,S4,S5,S6,S7}
    will be detected.
 
    Output:
 
-   * TYPE_IN: The type of the input arguments to the pattern.
-
    * TYPE_OUT: The type of the output  of this pattern.
 
    * Return value: A new stmt that will be used to replace the sequence of
@@ -257,35 +884,14 @@
          inner-loop nested in an outer-loop that us being vectorized).  */
 
 static gimple *
-vect_recog_dot_prod_pattern (vec<gimple *> *stmts, tree *type_in,
-			     tree *type_out)
+vect_recog_dot_prod_pattern (stmt_vec_info stmt_vinfo, tree *type_out)
 {
-  gimple *stmt, *last_stmt = (*stmts)[0];
   tree oprnd0, oprnd1;
-  tree oprnd00, oprnd01;
-  stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
+  gimple *last_stmt = stmt_vinfo->stmt;
+  vec_info *vinfo = stmt_vinfo->vinfo;
   tree type, half_type;
   gimple *pattern_stmt;
-  tree prod_type;
-  loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
-  struct loop *loop;
   tree var;
-  bool promotion;
-
-  if (!loop_info)
-    return NULL;
-
-  loop = LOOP_VINFO_LOOP (loop_info);
-
-  /* We don't allow changing the order of the computation in the inner-loop
-     when doing outer-loop vectorization.  */
-  if (loop && nested_in_vect_loop_p (loop, last_stmt))
-    return NULL;
-
-  if (!is_gimple_assign (last_stmt))
-    return NULL;
-
-  type = gimple_expr_type (last_stmt);
 
   /* Look for the following pattern
           DX = (TYPE1) X;
@@ -311,127 +917,54 @@
   /* Starting from LAST_STMT, follow the defs of its uses in search
      of the above pattern.  */
 
-  if (gimple_assign_rhs_code (last_stmt) != PLUS_EXPR)
+  if (!vect_reassociating_reduction_p (stmt_vinfo, PLUS_EXPR,
+				       &oprnd0, &oprnd1))
     return NULL;
 
-  if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
-    {
-      /* Has been detected as widening-summation?  */
-
-      stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
-      type = gimple_expr_type (stmt);
-      if (gimple_assign_rhs_code (stmt) != WIDEN_SUM_EXPR)
-        return NULL;
-      oprnd0 = gimple_assign_rhs1 (stmt);
-      oprnd1 = gimple_assign_rhs2 (stmt);
-      half_type = TREE_TYPE (oprnd0);
-    }
-  else
-    {
-      gimple *def_stmt;
-
-      if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def
-	  && ! STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_vinfo))
-	return NULL;
-      oprnd0 = gimple_assign_rhs1 (last_stmt);
-      oprnd1 = gimple_assign_rhs2 (last_stmt);
-      if (!types_compatible_p (TREE_TYPE (oprnd0), type)
-	  || !types_compatible_p (TREE_TYPE (oprnd1), type))
-        return NULL;
-      stmt = last_stmt;
-
-      if (type_conversion_p (oprnd0, stmt, true, &half_type, &def_stmt,
-			     &promotion)
-	  && promotion)
-        {
-          stmt = def_stmt;
-          oprnd0 = gimple_assign_rhs1 (stmt);
-        }
-      else
-        half_type = type;
-    }
+  type = gimple_expr_type (last_stmt);
+
+  vect_unpromoted_value unprom_mult;
+  oprnd0 = vect_look_through_possible_promotion (vinfo, oprnd0, &unprom_mult);
 
   /* So far so good.  Since last_stmt was detected as a (summation) reduction,
      we know that oprnd1 is the reduction variable (defined by a loop-header
      phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.
      Left to check that oprnd0 is defined by a (widen_)mult_expr  */
-  if (TREE_CODE (oprnd0) != SSA_NAME)
+  if (!oprnd0)
     return NULL;
 
-  prod_type = half_type;
-  stmt = SSA_NAME_DEF_STMT (oprnd0);
-
-  /* It could not be the dot_prod pattern if the stmt is outside the loop.  */
-  if (!gimple_bb (stmt) || !flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
+  stmt_vec_info mult_vinfo = vect_get_internal_def (vinfo, oprnd0);
+  if (!mult_vinfo)
     return NULL;
 
   /* FORNOW.  Can continue analyzing the def-use chain when this stmt in a phi
      inside the loop (in case we are analyzing an outer-loop).  */
-  if (!is_gimple_assign (stmt))
+  vect_unpromoted_value unprom0[2];
+  if (!vect_widened_op_tree (mult_vinfo, MULT_EXPR, WIDEN_MULT_EXPR,
+			     false, 2, unprom0, &half_type))
     return NULL;
-  stmt_vinfo = vinfo_for_stmt (stmt);
-  gcc_assert (stmt_vinfo);
-  if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_internal_def)
-    return NULL;
-  if (gimple_assign_rhs_code (stmt) != MULT_EXPR)
+
+  /* If there are two widening operations, make sure they agree on
+     the sign of the extension.  */
+  if (TYPE_PRECISION (unprom_mult.type) != TYPE_PRECISION (type)
+      && TYPE_SIGN (unprom_mult.type) != TYPE_SIGN (half_type))
     return NULL;
-  if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
-    {
-      /* Has been detected as a widening multiplication?  */
-
-      stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
-      if (gimple_assign_rhs_code (stmt) != WIDEN_MULT_EXPR)
-        return NULL;
-      stmt_vinfo = vinfo_for_stmt (stmt);
-      gcc_assert (stmt_vinfo);
-      gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_internal_def);
-      oprnd00 = gimple_assign_rhs1 (stmt);
-      oprnd01 = gimple_assign_rhs2 (stmt);
-      STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (last_stmt))
-	  = STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo);
-    }
-  else
-    {
-      tree half_type0, half_type1;
-      gimple *def_stmt;
-      tree oprnd0, oprnd1;
-
-      oprnd0 = gimple_assign_rhs1 (stmt);
-      oprnd1 = gimple_assign_rhs2 (stmt);
-      if (!types_compatible_p (TREE_TYPE (oprnd0), prod_type)
-          || !types_compatible_p (TREE_TYPE (oprnd1), prod_type))
-        return NULL;
-      if (!type_conversion_p (oprnd0, stmt, true, &half_type0, &def_stmt,
-			      &promotion)
-	  || !promotion)
-        return NULL;
-      oprnd00 = gimple_assign_rhs1 (def_stmt);
-      if (!type_conversion_p (oprnd1, stmt, true, &half_type1, &def_stmt,
-			      &promotion)
-	  || !promotion)
-        return NULL;
-      oprnd01 = gimple_assign_rhs1 (def_stmt);
-      if (!types_compatible_p (half_type0, half_type1))
-        return NULL;
-      if (TYPE_PRECISION (prod_type) != TYPE_PRECISION (half_type0) * 2)
-	return NULL;
-    }
-
-  half_type = TREE_TYPE (oprnd00);
-  *type_in = half_type;
-  *type_out = type;
-
-  /* Pattern detected. Create a stmt to be used to replace the pattern: */
+
+  vect_pattern_detected ("vect_recog_dot_prod_pattern", last_stmt);
+
+  tree half_vectype;
+  if (!vect_supportable_direct_optab_p (type, DOT_PROD_EXPR, half_type,
+					type_out, &half_vectype))
+    return NULL;
+
+  /* Get the inputs in the appropriate types.  */
+  tree mult_oprnd[2];
+  vect_convert_inputs (stmt_vinfo, 2, mult_oprnd, half_type,
+		       unprom0, half_vectype);
+
   var = vect_recog_temp_ssa_var (type, NULL);
   pattern_stmt = gimple_build_assign (var, DOT_PROD_EXPR,
-				      oprnd00, oprnd01, oprnd1);
-
-  if (dump_enabled_p ())
-    {
-      dump_printf_loc (MSG_NOTE, vect_location,
-                       "vect_recog_dot_prod_pattern: detected: ");
-      dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
-    }
+				      mult_oprnd[0], mult_oprnd[1], oprnd1);
 
   return pattern_stmt;
 }
@@ -461,14 +994,12 @@
 
    Input:
 
-   * STMTS: Contains a stmt from which the pattern search begins.  In the
+   * STMT_VINFO: The stmt from which the pattern search begins.  In the
    example, when this function is called with S8, the pattern
    {S3,S4,S5,S6,S7,S8} will be detected.
 
    Output:
 
-   * TYPE_IN: The type of the input arguments to the pattern.
-
    * TYPE_OUT: The type of the output of this pattern.
 
    * Return value: A new stmt that will be used to replace the sequence of
@@ -477,31 +1008,11 @@
   */
 
 static gimple *
-vect_recog_sad_pattern (vec<gimple *> *stmts, tree *type_in,
-			     tree *type_out)
+vect_recog_sad_pattern (stmt_vec_info stmt_vinfo, tree *type_out)
 {
-  gimple *last_stmt = (*stmts)[0];
-  tree sad_oprnd0, sad_oprnd1;
-  stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
+  gimple *last_stmt = stmt_vinfo->stmt;
+  vec_info *vinfo = stmt_vinfo->vinfo;
   tree half_type;
-  loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
-  struct loop *loop;
-  bool promotion;
-
-  if (!loop_info)
-    return NULL;
-
-  loop = LOOP_VINFO_LOOP (loop_info);
-
-  /* We don't allow changing the order of the computation in the inner-loop
-     when doing outer-loop vectorization.  */
-  if (loop && nested_in_vect_loop_p (loop, last_stmt))
-    return NULL;
-
-  if (!is_gimple_assign (last_stmt))
-    return NULL;
-
-  tree sum_type = gimple_expr_type (last_stmt);
 
   /* Look for the following pattern
           DX = (TYPE1) X;
@@ -530,477 +1041,178 @@
   /* Starting from LAST_STMT, follow the defs of its uses in search
      of the above pattern.  */
 
-  if (gimple_assign_rhs_code (last_stmt) != PLUS_EXPR)
+  tree plus_oprnd0, plus_oprnd1;
+  if (!vect_reassociating_reduction_p (stmt_vinfo, PLUS_EXPR,
+				       &plus_oprnd0, &plus_oprnd1))
     return NULL;
 
-  tree plus_oprnd0, plus_oprnd1;
-
-  if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
-    {
-      /* Has been detected as widening-summation?  */
-
-      gimple *stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
-      sum_type = gimple_expr_type (stmt);
-      if (gimple_assign_rhs_code (stmt) != WIDEN_SUM_EXPR)
-        return NULL;
-      plus_oprnd0 = gimple_assign_rhs1 (stmt);
-      plus_oprnd1 = gimple_assign_rhs2 (stmt);
-      half_type = TREE_TYPE (plus_oprnd0);
-    }
-  else
-    {
-      gimple *def_stmt;
-
-      if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def
-	  && ! STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_vinfo))
-	return NULL;
-      plus_oprnd0 = gimple_assign_rhs1 (last_stmt);
-      plus_oprnd1 = gimple_assign_rhs2 (last_stmt);
-      if (!types_compatible_p (TREE_TYPE (plus_oprnd0), sum_type)
-	  || !types_compatible_p (TREE_TYPE (plus_oprnd1), sum_type))
-        return NULL;
-
-      /* The type conversion could be promotion, demotion,
-         or just signed -> unsigned.  */
-      if (type_conversion_p (plus_oprnd0, last_stmt, false,
-                             &half_type, &def_stmt, &promotion))
-        plus_oprnd0 = gimple_assign_rhs1 (def_stmt);
-      else
-        half_type = sum_type;
-    }
+  tree sum_type = gimple_expr_type (last_stmt);
+
+  /* Any non-truncating sequence of conversions is OK here, since
+     with a successful match, the result of the ABS(U) is known to fit
+     within the nonnegative range of the result type.  (It cannot be the
+     negative of the minimum signed value due to the range of the widening
+     MINUS_EXPR.)  */
+  vect_unpromoted_value unprom_abs;
+  plus_oprnd0 = vect_look_through_possible_promotion (vinfo, plus_oprnd0,
+						      &unprom_abs);
 
   /* So far so good.  Since last_stmt was detected as a (summation) reduction,
      we know that plus_oprnd1 is the reduction variable (defined by a loop-header
      phi), and plus_oprnd0 is an ssa-name defined by a stmt in the loop body.
      Then check that plus_oprnd0 is defined by an abs_expr.  */
 
-  if (TREE_CODE (plus_oprnd0) != SSA_NAME)
+  if (!plus_oprnd0)
     return NULL;
 
-  tree abs_type = half_type;
-  gimple *abs_stmt = SSA_NAME_DEF_STMT (plus_oprnd0);
-
-  /* It could not be the sad pattern if the abs_stmt is outside the loop.  */
-  if (!gimple_bb (abs_stmt) || !flow_bb_inside_loop_p (loop, gimple_bb (abs_stmt)))
+  stmt_vec_info abs_stmt_vinfo = vect_get_internal_def (vinfo, plus_oprnd0);
+  if (!abs_stmt_vinfo)
     return NULL;
 
   /* FORNOW.  Can continue analyzing the def-use chain when this stmt in a phi
      inside the loop (in case we are analyzing an outer-loop).  */
-  if (!is_gimple_assign (abs_stmt))
-    return NULL;
-
-  stmt_vec_info abs_stmt_vinfo = vinfo_for_stmt (abs_stmt);
-  gcc_assert (abs_stmt_vinfo);
-  if (STMT_VINFO_DEF_TYPE (abs_stmt_vinfo) != vect_internal_def)
-    return NULL;
-  if (gimple_assign_rhs_code (abs_stmt) != ABS_EXPR)
+  gassign *abs_stmt = dyn_cast <gassign *> (abs_stmt_vinfo->stmt);
+  if (!abs_stmt
+      || (gimple_assign_rhs_code (abs_stmt) != ABS_EXPR
+	  && gimple_assign_rhs_code (abs_stmt) != ABSU_EXPR))
     return NULL;
 
   tree abs_oprnd = gimple_assign_rhs1 (abs_stmt);
-  if (!types_compatible_p (TREE_TYPE (abs_oprnd), abs_type))
+  tree abs_type = TREE_TYPE (abs_oprnd);
+  if (TYPE_UNSIGNED (abs_type))
     return NULL;
-  if (TYPE_UNSIGNED (abs_type))
+
+  /* Peel off conversions from the ABS input.  This can involve sign
+     changes (e.g. from an unsigned subtraction to a signed ABS input)
+     or signed promotion, but it can't include unsigned promotion.
+     (Note that ABS of an unsigned promotion should have been folded
+     away before now anyway.)  */
+  vect_unpromoted_value unprom_diff;
+  abs_oprnd = vect_look_through_possible_promotion (vinfo, abs_oprnd,
+						    &unprom_diff);
+  if (!abs_oprnd)
+    return NULL;
+  if (TYPE_PRECISION (unprom_diff.type) != TYPE_PRECISION (abs_type)
+      && TYPE_UNSIGNED (unprom_diff.type))
     return NULL;
 
   /* We then detect if the operand of abs_expr is defined by a minus_expr.  */
-
-  if (TREE_CODE (abs_oprnd) != SSA_NAME)
-    return NULL;
-
-  gimple *diff_stmt = SSA_NAME_DEF_STMT (abs_oprnd);
-
-  /* It could not be the sad pattern if the diff_stmt is outside the loop.  */
-  if (!gimple_bb (diff_stmt)
-      || !flow_bb_inside_loop_p (loop, gimple_bb (diff_stmt)))
+  stmt_vec_info diff_stmt_vinfo = vect_get_internal_def (vinfo, abs_oprnd);
+  if (!diff_stmt_vinfo)
     return NULL;
 
   /* FORNOW.  Can continue analyzing the def-use chain when this stmt in a phi
      inside the loop (in case we are analyzing an outer-loop).  */
-  if (!is_gimple_assign (diff_stmt))
-    return NULL;
-
-  stmt_vec_info diff_stmt_vinfo = vinfo_for_stmt (diff_stmt);
-  gcc_assert (diff_stmt_vinfo);
-  if (STMT_VINFO_DEF_TYPE (diff_stmt_vinfo) != vect_internal_def)
-    return NULL;
-  if (gimple_assign_rhs_code (diff_stmt) != MINUS_EXPR)
-    return NULL;
-
-  tree half_type0, half_type1;
-  gimple *def_stmt;
-
-  tree minus_oprnd0 = gimple_assign_rhs1 (diff_stmt);
-  tree minus_oprnd1 = gimple_assign_rhs2 (diff_stmt);
-
-  if (!types_compatible_p (TREE_TYPE (minus_oprnd0), abs_type)
-      || !types_compatible_p (TREE_TYPE (minus_oprnd1), abs_type))
-    return NULL;
-  if (!type_conversion_p (minus_oprnd0, diff_stmt, false,
-                          &half_type0, &def_stmt, &promotion)
-      || !promotion)
+  vect_unpromoted_value unprom[2];
+  if (!vect_widened_op_tree (diff_stmt_vinfo, MINUS_EXPR, MINUS_EXPR,
+			     false, 2, unprom, &half_type))
     return NULL;
-  sad_oprnd0 = gimple_assign_rhs1 (def_stmt);
-
-  if (!type_conversion_p (minus_oprnd1, diff_stmt, false,
-                          &half_type1, &def_stmt, &promotion)
-      || !promotion)
-    return NULL;
-  sad_oprnd1 = gimple_assign_rhs1 (def_stmt);
-
-  if (!types_compatible_p (half_type0, half_type1))
-    return NULL;
-  if (TYPE_PRECISION (abs_type) < TYPE_PRECISION (half_type0) * 2
-      || TYPE_PRECISION (sum_type) < TYPE_PRECISION (half_type0) * 2)
+
+  vect_pattern_detected ("vect_recog_sad_pattern", last_stmt);
+
+  tree half_vectype;
+  if (!vect_supportable_direct_optab_p (sum_type, SAD_EXPR, half_type,
+					type_out, &half_vectype))
     return NULL;
 
-  *type_in = TREE_TYPE (sad_oprnd0);
-  *type_out = sum_type;
-
-  /* Pattern detected. Create a stmt to be used to replace the pattern: */
+  /* Get the inputs to the SAD_EXPR in the appropriate types.  */
+  tree sad_oprnd[2];
+  vect_convert_inputs (stmt_vinfo, 2, sad_oprnd, half_type,
+		       unprom, half_vectype);
+
   tree var = vect_recog_temp_ssa_var (sum_type, NULL);
-  gimple *pattern_stmt = gimple_build_assign (var, SAD_EXPR, sad_oprnd0,
-					      sad_oprnd1, plus_oprnd1);
-
-  if (dump_enabled_p ())
-    {
-      dump_printf_loc (MSG_NOTE, vect_location,
-                       "vect_recog_sad_pattern: detected: ");
-      dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
-    }
+  gimple *pattern_stmt = gimple_build_assign (var, SAD_EXPR, sad_oprnd[0],
+					      sad_oprnd[1], plus_oprnd1);
 
   return pattern_stmt;
 }
 
-
-/* Handle widening operation by a constant.  At the moment we support MULT_EXPR
-   and LSHIFT_EXPR.
-
-   For MULT_EXPR we check that CONST_OPRND fits HALF_TYPE, and for LSHIFT_EXPR
-   we check that CONST_OPRND is less or equal to the size of HALF_TYPE.
-
-   Otherwise, if the type of the result (TYPE) is at least 4 times bigger than
-   HALF_TYPE, and there is an intermediate type (2 times smaller than TYPE)
-   that satisfies the above restrictions,  we can perform a widening opeartion
-   from the intermediate type to TYPE and replace a_T = (TYPE) a_t;
-   with a_it = (interm_type) a_t;  Store such operation in *WSTMT.  */
-
-static bool
-vect_handle_widen_op_by_const (gimple *stmt, enum tree_code code,
-		               tree const_oprnd, tree *oprnd,
-			       gimple **wstmt, tree type,
-			       tree *half_type, gimple *def_stmt)
-{
-  tree new_type, new_oprnd;
-
-  if (code != MULT_EXPR && code != LSHIFT_EXPR)
-    return false;
-
-  if (((code == MULT_EXPR && int_fits_type_p (const_oprnd, *half_type))
-        || (code == LSHIFT_EXPR
-            && compare_tree_int (const_oprnd, TYPE_PRECISION (*half_type))
-	    	!= 1))
-      && TYPE_PRECISION (type) == (TYPE_PRECISION (*half_type) * 2))
-    {
-      /* CONST_OPRND is a constant of HALF_TYPE.  */
-      *oprnd = gimple_assign_rhs1 (def_stmt);
-      return true;
-    }
-
-  if (TYPE_PRECISION (type) < (TYPE_PRECISION (*half_type) * 4))
-    return false;
-
-  if (!vect_same_loop_or_bb_p (stmt, def_stmt))
-    return false;
-
-  /* TYPE is 4 times bigger than HALF_TYPE, try widening operation for
-     a type 2 times bigger than HALF_TYPE.  */
-  new_type = build_nonstandard_integer_type (TYPE_PRECISION (type) / 2,
-                                             TYPE_UNSIGNED (type));
-  if ((code == MULT_EXPR && !int_fits_type_p (const_oprnd, new_type))
-      || (code == LSHIFT_EXPR
-          && compare_tree_int (const_oprnd, TYPE_PRECISION (new_type)) == 1))
-    return false;
-
-  /* Use NEW_TYPE for widening operation and create a_T = (NEW_TYPE) a_t;  */
-  *oprnd = gimple_assign_rhs1 (def_stmt);
-  new_oprnd = make_ssa_name (new_type);
-  *wstmt = gimple_build_assign (new_oprnd, NOP_EXPR, *oprnd);
-  *oprnd = new_oprnd;
-
-  *half_type = new_type;
-  return true;
-}
-
-
-/* Function vect_recog_widen_mult_pattern
-
-   Try to find the following pattern:
-
-     type1 a_t;
-     type2 b_t;
-     TYPE a_T, b_T, prod_T;
-
-     S1  a_t = ;
-     S2  b_t = ;
-     S3  a_T = (TYPE) a_t;
-     S4  b_T = (TYPE) b_t;
-     S5  prod_T = a_T * b_T;
-
-   where type 'TYPE' is at least double the size of type 'type1' and 'type2'.
-
-   Also detect unsigned cases:
-
-     unsigned type1 a_t;
-     unsigned type2 b_t;
-     unsigned TYPE u_prod_T;
-     TYPE a_T, b_T, prod_T;
-
-     S1  a_t = ;
-     S2  b_t = ;
-     S3  a_T = (TYPE) a_t;
-     S4  b_T = (TYPE) b_t;
-     S5  prod_T = a_T * b_T;
-     S6  u_prod_T = (unsigned TYPE) prod_T;
-
-   and multiplication by constants:
-
-     type a_t;
-     TYPE a_T, prod_T;
-
-     S1  a_t = ;
-     S3  a_T = (TYPE) a_t;
-     S5  prod_T = a_T * CONST;
-
-   A special case of multiplication by constants is when 'TYPE' is 4 times
-   bigger than 'type', but CONST fits an intermediate type 2 times smaller
-   than 'TYPE'.  In that case we create an additional pattern stmt for S3
-   to create a variable of the intermediate type, and perform widen-mult
-   on the intermediate type as well:
-
-     type a_t;
-     interm_type a_it;
-     TYPE a_T, prod_T,  prod_T';
-
-     S1  a_t = ;
-     S3  a_T = (TYPE) a_t;
-           '--> a_it = (interm_type) a_t;
-     S5  prod_T = a_T * CONST;
-           '--> prod_T' = a_it w* CONST;
-
-   Input/Output:
-
-   * STMTS: Contains a stmt from which the pattern search begins.  In the
-   example, when this function is called with S5, the pattern {S3,S4,S5,(S6)}
-   is detected.  In case of unsigned widen-mult, the original stmt (S5) is
-   replaced with S6 in STMTS.  In case of multiplication by a constant
-   of an intermediate type (the last case above), STMTS also contains S3
-   (inserted before S5).
-
-   Output:
-
-   * TYPE_IN: The type of the input arguments to the pattern.
-
-   * TYPE_OUT: The type of the output of this pattern.
-
-   * Return value: A new stmt that will be used to replace the sequence of
-   stmts that constitute the pattern.  In this case it will be:
-        WIDEN_MULT <a_t, b_t>
-   If the result of WIDEN_MULT needs to be converted to a larger type, the
-   returned stmt will be this type conversion stmt.
-*/
+/* Recognize an operation that performs ORIG_CODE on widened inputs,
+   so that it can be treated as though it had the form:
+
+      A_TYPE a;
+      B_TYPE b;
+      HALF_TYPE a_cast = (HALF_TYPE) a;  // possible no-op
+      HALF_TYPE b_cast = (HALF_TYPE) b;  // possible no-op
+    | RES_TYPE a_extend = (RES_TYPE) a_cast;  // promotion from HALF_TYPE
+    | RES_TYPE b_extend = (RES_TYPE) b_cast;  // promotion from HALF_TYPE
+    | RES_TYPE res = a_extend ORIG_CODE b_extend;
+
+   Try to replace the pattern with:
+
+      A_TYPE a;
+      B_TYPE b;
+      HALF_TYPE a_cast = (HALF_TYPE) a;  // possible no-op
+      HALF_TYPE b_cast = (HALF_TYPE) b;  // possible no-op
+    | EXT_TYPE ext = a_cast WIDE_CODE b_cast;
+    | RES_TYPE res = (EXT_TYPE) ext;  // possible no-op
+
+   where EXT_TYPE is wider than HALF_TYPE but has the same signedness.
+
+   SHIFT_P is true if ORIG_CODE and WIDE_CODE are shifts.  NAME is the
+   name of the pattern being matched, for dump purposes.  */
 
 static gimple *
-vect_recog_widen_mult_pattern (vec<gimple *> *stmts,
-                               tree *type_in, tree *type_out)
+vect_recog_widen_op_pattern (stmt_vec_info last_stmt_info, tree *type_out,
+			     tree_code orig_code, tree_code wide_code,
+			     bool shift_p, const char *name)
 {
-  gimple *last_stmt = stmts->pop ();
-  gimple *def_stmt0, *def_stmt1;
-  tree oprnd0, oprnd1;
-  tree type, half_type0, half_type1;
-  gimple *new_stmt = NULL, *pattern_stmt = NULL;
-  tree vectype, vecitype;
-  tree var;
+  gimple *last_stmt = last_stmt_info->stmt;
+
+  vect_unpromoted_value unprom[2];
+  tree half_type;
+  if (!vect_widened_op_tree (last_stmt_info, orig_code, orig_code,
+			     shift_p, 2, unprom, &half_type))
+    return NULL;
+
+  /* Pattern detected.  */
+  vect_pattern_detected (name, last_stmt);
+
+  tree type = gimple_expr_type (last_stmt);
+  tree itype = type;
+  if (TYPE_PRECISION (type) != TYPE_PRECISION (half_type) * 2
+      || TYPE_UNSIGNED (type) != TYPE_UNSIGNED (half_type))
+    itype = build_nonstandard_integer_type (TYPE_PRECISION (half_type) * 2,
+					    TYPE_UNSIGNED (half_type));
+
+  /* Check target support  */
+  tree vectype = get_vectype_for_scalar_type (half_type);
+  tree vecitype = get_vectype_for_scalar_type (itype);
   enum tree_code dummy_code;
   int dummy_int;
-  vec<tree> dummy_vec;
-  bool op1_ok;
-  bool promotion;
-
-  if (!is_gimple_assign (last_stmt))
-    return NULL;
-
-  type = gimple_expr_type (last_stmt);
-
-  /* Starting from LAST_STMT, follow the defs of its uses in search
-     of the above pattern.  */
-
-  if (gimple_assign_rhs_code (last_stmt) != MULT_EXPR)
-    return NULL;
-
-  oprnd0 = gimple_assign_rhs1 (last_stmt);
-  oprnd1 = gimple_assign_rhs2 (last_stmt);
-  if (!types_compatible_p (TREE_TYPE (oprnd0), type)
-      || !types_compatible_p (TREE_TYPE (oprnd1), type))
-    return NULL;
-
-  /* Check argument 0.  */
-  if (!type_conversion_p (oprnd0, last_stmt, false, &half_type0, &def_stmt0,
-                         &promotion)
-      || !promotion)
-     return NULL;
-  /* Check argument 1.  */
-  op1_ok = type_conversion_p (oprnd1, last_stmt, false, &half_type1,
-                              &def_stmt1, &promotion);
-
-  if (op1_ok && promotion)
-    {
-      oprnd0 = gimple_assign_rhs1 (def_stmt0);
-      oprnd1 = gimple_assign_rhs1 (def_stmt1);
-    }	       
-  else
-    {
-      if (TREE_CODE (oprnd1) == INTEGER_CST
-          && TREE_CODE (half_type0) == INTEGER_TYPE
-          && vect_handle_widen_op_by_const (last_stmt, MULT_EXPR, oprnd1,
-		                            &oprnd0, &new_stmt, type,
-					    &half_type0, def_stmt0))
-	{
-	  half_type1 = half_type0;
-	  oprnd1 = fold_convert (half_type1, oprnd1);
-	}
-      else
-        return NULL;
-    }
-
-  /* If the two arguments have different sizes, convert the one with
-     the smaller type into the larger type.  */
-  if (TYPE_PRECISION (half_type0) != TYPE_PRECISION (half_type1))
-    {
-      /* If we already used up the single-stmt slot give up.  */
-      if (new_stmt)
-	return NULL;
-
-      tree* oprnd = NULL;
-      gimple *def_stmt = NULL;
-
-      if (TYPE_PRECISION (half_type0) < TYPE_PRECISION (half_type1))
-	{
-	  def_stmt = def_stmt0;
-	  half_type0 = half_type1;
-	  oprnd = &oprnd0;
-	}
-      else
-	{
-	  def_stmt = def_stmt1;
-	  half_type1 = half_type0;
-	  oprnd = &oprnd1;
-	}
-
-      tree old_oprnd = gimple_assign_rhs1 (def_stmt);
-      tree new_oprnd = make_ssa_name (half_type0);
-      new_stmt = gimple_build_assign (new_oprnd, NOP_EXPR, old_oprnd);
-      *oprnd = new_oprnd;
-    }
-
-  /* Handle unsigned case.  Look for
-     S6  u_prod_T = (unsigned TYPE) prod_T;
-     Use unsigned TYPE as the type for WIDEN_MULT_EXPR.  */
-  if (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (half_type0))
-    {
-      gimple *use_stmt;
-      tree use_lhs;
-      tree use_type;
-
-      if (TYPE_UNSIGNED (type) == TYPE_UNSIGNED (half_type1))
-        return NULL;
-
-      use_stmt = vect_single_imm_use (last_stmt);
-      if (!use_stmt || !is_gimple_assign (use_stmt)
-	  || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt)))
-        return NULL;
-
-      use_lhs = gimple_assign_lhs (use_stmt);
-      use_type = TREE_TYPE (use_lhs);
-      if (!INTEGRAL_TYPE_P (use_type)
-          || (TYPE_UNSIGNED (type) == TYPE_UNSIGNED (use_type))
-          || (TYPE_PRECISION (type) != TYPE_PRECISION (use_type)))
-        return NULL;
-
-      type = use_type;
-      last_stmt = use_stmt;
-    }
-
-  if (!types_compatible_p (half_type0, half_type1))
-    return NULL;
-
-  /* If TYPE is more than twice larger than HALF_TYPE, we use WIDEN_MULT
-     to get an intermediate result of type ITYPE.  In this case we need
-     to build a statement to convert this intermediate result to type TYPE.  */
-  tree itype = type;
-  if (TYPE_PRECISION (type) > TYPE_PRECISION (half_type0) * 2)
-    itype = build_nonstandard_integer_type
-	      (GET_MODE_BITSIZE (SCALAR_TYPE_MODE (half_type0)) * 2,
-	       TYPE_UNSIGNED (type));
-
-  /* Pattern detected.  */
-  if (dump_enabled_p ())
-    dump_printf_loc (MSG_NOTE, vect_location,
-                     "vect_recog_widen_mult_pattern: detected:\n");
-
-  /* Check target support  */
-  vectype = get_vectype_for_scalar_type (half_type0);
-  vecitype = get_vectype_for_scalar_type (itype);
+  auto_vec<tree> dummy_vec;
   if (!vectype
       || !vecitype
-      || !supportable_widening_operation (WIDEN_MULT_EXPR, last_stmt,
+      || !supportable_widening_operation (wide_code, last_stmt_info,
 					  vecitype, vectype,
 					  &dummy_code, &dummy_code,
 					  &dummy_int, &dummy_vec))
     return NULL;
 
-  *type_in = vectype;
   *type_out = get_vectype_for_scalar_type (type);
-
-  /* Pattern supported. Create a stmt to be used to replace the pattern: */
-  var = vect_recog_temp_ssa_var (itype, NULL);
-  pattern_stmt = gimple_build_assign (var, WIDEN_MULT_EXPR, oprnd0, oprnd1);
-
-  stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
-  STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo) = NULL;
-
-  /* If the original two operands have different sizes, we may need to convert
-     the smaller one into the larget type.  If this is the case, at this point
-     the new stmt is already built.  */
-  if (new_stmt)
-    {
-      append_pattern_def_seq (stmt_vinfo, new_stmt);
-      stmt_vec_info new_stmt_info
-        = new_stmt_vec_info (new_stmt, stmt_vinfo->vinfo);
-      set_vinfo_for_stmt (new_stmt, new_stmt_info);
-      STMT_VINFO_VECTYPE (new_stmt_info) = vectype;
-    }
-
-  /* If ITYPE is not TYPE, we need to build a type convertion stmt to convert
-     the result of the widen-mult operation into type TYPE.  */
-  if (itype != type)
-    {
-      append_pattern_def_seq (stmt_vinfo, pattern_stmt);
-      stmt_vec_info pattern_stmt_info
-        = new_stmt_vec_info (pattern_stmt, stmt_vinfo->vinfo);
-      set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info);
-      STMT_VINFO_VECTYPE (pattern_stmt_info) = vecitype;
-      pattern_stmt = gimple_build_assign (vect_recog_temp_ssa_var (type, NULL),
-					  NOP_EXPR,
-					  gimple_assign_lhs (pattern_stmt));
-    }
-
-  if (dump_enabled_p ())
-    dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt, 0);
-
-  stmts->safe_push (last_stmt);
-  return pattern_stmt;
+  if (!*type_out)
+    return NULL;
+
+  tree oprnd[2];
+  vect_convert_inputs (last_stmt_info, 2, oprnd, half_type, unprom, vectype);
+
+  tree var = vect_recog_temp_ssa_var (itype, NULL);
+  gimple *pattern_stmt = gimple_build_assign (var, wide_code,
+					      oprnd[0], oprnd[1]);
+
+  return vect_convert_output (last_stmt_info, type, pattern_stmt, vecitype);
 }
 
+/* Try to detect multiplication on widened inputs, converting MULT_EXPR
+   to WIDEN_MULT_EXPR.  See vect_recog_widen_op_pattern for details.  */
+
+static gimple *
+vect_recog_widen_mult_pattern (stmt_vec_info last_stmt_info, tree *type_out)
+{
+  return vect_recog_widen_op_pattern (last_stmt_info, type_out, MULT_EXPR,
+				      WIDEN_MULT_EXPR, false,
+				      "vect_recog_widen_mult_pattern");
+}
 
 /* Function vect_recog_pow_pattern
 
@@ -1013,12 +1225,10 @@
 
    Input:
 
-   * LAST_STMT: A stmt from which the pattern search begins.
+   * STMT_VINFO: The stmt from which the pattern search begins.
 
    Output:
 
-   * TYPE_IN: The type of the input arguments to the pattern.
-
    * TYPE_OUT: The type of the output of this pattern.
 
    * Return value: A new stmt that will be used to replace the sequence of
@@ -1029,11 +1239,10 @@
 */
 
 static gimple *
-vect_recog_pow_pattern (vec<gimple *> *stmts, tree *type_in,
-			tree *type_out)
+vect_recog_pow_pattern (stmt_vec_info stmt_vinfo, tree *type_out)
 {
-  gimple *last_stmt = (*stmts)[0];
-  tree base, exp = NULL;
+  gimple *last_stmt = stmt_vinfo->stmt;
+  tree base, exp;
   gimple *stmt;
   tree var;
 
@@ -1044,29 +1253,90 @@
     {
     CASE_CFN_POW:
     CASE_CFN_POWI:
-      base = gimple_call_arg (last_stmt, 0);
-      exp = gimple_call_arg (last_stmt, 1);
-      if (TREE_CODE (exp) != REAL_CST
-	  && TREE_CODE (exp) != INTEGER_CST)
-        return NULL;
       break;
 
     default:
       return NULL;
     }
 
+  base = gimple_call_arg (last_stmt, 0);
+  exp = gimple_call_arg (last_stmt, 1);
+  if (TREE_CODE (exp) != REAL_CST
+      && TREE_CODE (exp) != INTEGER_CST)
+    {
+      if (flag_unsafe_math_optimizations
+	  && TREE_CODE (base) == REAL_CST
+	  && !gimple_call_internal_p (last_stmt))
+	{
+	  combined_fn log_cfn;
+	  built_in_function exp_bfn;
+	  switch (DECL_FUNCTION_CODE (gimple_call_fndecl (last_stmt)))
+	    {
+	    case BUILT_IN_POW:
+	      log_cfn = CFN_BUILT_IN_LOG;
+	      exp_bfn = BUILT_IN_EXP;
+	      break;
+	    case BUILT_IN_POWF:
+	      log_cfn = CFN_BUILT_IN_LOGF;
+	      exp_bfn = BUILT_IN_EXPF;
+	      break;
+	    case BUILT_IN_POWL:
+	      log_cfn = CFN_BUILT_IN_LOGL;
+	      exp_bfn = BUILT_IN_EXPL;
+	      break;
+	    default:
+	      return NULL;
+	    }
+	  tree logc = fold_const_call (log_cfn, TREE_TYPE (base), base);
+	  tree exp_decl = builtin_decl_implicit (exp_bfn);
+	  /* Optimize pow (C, x) as exp (log (C) * x).  Normally match.pd
+	     does that, but if C is a power of 2, we want to use
+	     exp2 (log2 (C) * x) in the non-vectorized version, but for
+	     vectorization we don't have vectorized exp2.  */
+	  if (logc
+	      && TREE_CODE (logc) == REAL_CST
+	      && exp_decl
+	      && lookup_attribute ("omp declare simd",
+				   DECL_ATTRIBUTES (exp_decl)))
+	    {
+	      cgraph_node *node = cgraph_node::get_create (exp_decl);
+	      if (node->simd_clones == NULL)
+		{
+		  if (targetm.simd_clone.compute_vecsize_and_simdlen == NULL
+		      || node->definition)
+		    return NULL;
+		  expand_simd_clones (node);
+		  if (node->simd_clones == NULL)
+		    return NULL;
+		}
+	      *type_out = get_vectype_for_scalar_type (TREE_TYPE (base));
+	      if (!*type_out)
+		return NULL;
+	      tree def = vect_recog_temp_ssa_var (TREE_TYPE (base), NULL);
+	      gimple *g = gimple_build_assign (def, MULT_EXPR, exp, logc);
+	      append_pattern_def_seq (stmt_vinfo, g);
+	      tree res = vect_recog_temp_ssa_var (TREE_TYPE (base), NULL);
+	      g = gimple_build_call (exp_decl, 1, def);
+	      gimple_call_set_lhs (g, res);
+	      return g;
+	    }
+	}
+
+      return NULL;
+    }
+
   /* We now have a pow or powi builtin function call with a constant
      exponent.  */
 
-  *type_out = NULL_TREE;
-
   /* Catch squaring.  */
   if ((tree_fits_shwi_p (exp)
        && tree_to_shwi (exp) == 2)
       || (TREE_CODE (exp) == REAL_CST
           && real_equal (&TREE_REAL_CST (exp), &dconst2)))
     {
-      *type_in = TREE_TYPE (base);
+      if (!vect_supportable_direct_optab_p (TREE_TYPE (base), MULT_EXPR,
+					    TREE_TYPE (base), type_out))
+	return NULL;
 
       var = vect_recog_temp_ssa_var (TREE_TYPE (base), NULL);
       stmt = gimple_build_assign (var, MULT_EXPR, base, base);
@@ -1077,9 +1347,9 @@
   if (TREE_CODE (exp) == REAL_CST
       && real_equal (&TREE_REAL_CST (exp), &dconsthalf))
     {
-      *type_in = get_vectype_for_scalar_type (TREE_TYPE (base));
-      if (*type_in
-	  && direct_internal_fn_supported_p (IFN_SQRT, *type_in,
+      *type_out = get_vectype_for_scalar_type (TREE_TYPE (base));
+      if (*type_out
+	  && direct_internal_fn_supported_p (IFN_SQRT, *type_out,
 					     OPTIMIZE_FOR_SPEED))
 	{
 	  gcall *stmt = gimple_build_call_internal (IFN_SQRT, 1, base);
@@ -1112,13 +1382,11 @@
 
    Input:
 
-   * LAST_STMT: A stmt from which the pattern search begins. In the example,
+   * STMT_VINFO: The stmt from which the pattern search begins. In the example,
    when this function is called with S3, the pattern {S2,S3} will be detected.
 
    Output:
 
-   * TYPE_IN: The type of the input arguments to the pattern.
-
    * TYPE_OUT: The type of the output of this pattern.
 
    * Return value: A new stmt that will be used to replace the sequence of
@@ -1134,33 +1402,14 @@
 	 inner-loop nested in an outer-loop that us being vectorized).  */
 
 static gimple *
-vect_recog_widen_sum_pattern (vec<gimple *> *stmts, tree *type_in,
-			      tree *type_out)
+vect_recog_widen_sum_pattern (stmt_vec_info stmt_vinfo, tree *type_out)
 {
-  gimple *stmt, *last_stmt = (*stmts)[0];
+  gimple *last_stmt = stmt_vinfo->stmt;
   tree oprnd0, oprnd1;
-  stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
-  tree type, half_type;
+  vec_info *vinfo = stmt_vinfo->vinfo;
+  tree type;
   gimple *pattern_stmt;
-  loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
-  struct loop *loop;
   tree var;
-  bool promotion;
-
-  if (!loop_info)
-    return NULL;
-
-  loop = LOOP_VINFO_LOOP (loop_info);
-
-  /* We don't allow changing the order of the computation in the inner-loop
-     when doing outer-loop vectorization.  */
-  if (loop && nested_in_vect_loop_p (loop, last_stmt))
-    return NULL;
-
-  if (!is_gimple_assign (last_stmt))
-    return NULL;
-
-  type = gimple_expr_type (last_stmt);
 
   /* Look for the following pattern
           DX = (TYPE) X;
@@ -1172,18 +1421,11 @@
   /* Starting from LAST_STMT, follow the defs of its uses in search
      of the above pattern.  */
 
-  if (gimple_assign_rhs_code (last_stmt) != PLUS_EXPR)
-    return NULL;
-
-  if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def
-      && ! STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_vinfo))
+  if (!vect_reassociating_reduction_p (stmt_vinfo, PLUS_EXPR,
+				       &oprnd0, &oprnd1))
     return NULL;
 
-  oprnd0 = gimple_assign_rhs1 (last_stmt);
-  oprnd1 = gimple_assign_rhs2 (last_stmt);
-  if (!types_compatible_p (TREE_TYPE (oprnd0), type)
-      || !types_compatible_p (TREE_TYPE (oprnd1), type))
-    return NULL;
+  type = gimple_expr_type (last_stmt);
 
   /* So far so good.  Since last_stmt was detected as a (summation) reduction,
      we know that oprnd1 is the reduction variable (defined by a loop-header
@@ -1191,562 +1433,477 @@
      Left to check that oprnd0 is defined by a cast from type 'type' to type
      'TYPE'.  */
 
-  if (!type_conversion_p (oprnd0, last_stmt, true, &half_type, &stmt,
-                          &promotion)
-      || !promotion)
-     return NULL;
-
-  oprnd0 = gimple_assign_rhs1 (stmt);
-  *type_in = half_type;
-  *type_out = type;
-
-  /* Pattern detected. Create a stmt to be used to replace the pattern: */
+  vect_unpromoted_value unprom0;
+  if (!vect_look_through_possible_promotion (vinfo, oprnd0, &unprom0)
+      || TYPE_PRECISION (unprom0.type) * 2 > TYPE_PRECISION (type))
+    return NULL;
+
+  vect_pattern_detected ("vect_recog_widen_sum_pattern", last_stmt);
+
+  if (!vect_supportable_direct_optab_p (type, WIDEN_SUM_EXPR, unprom0.type,
+					type_out))
+    return NULL;
+
   var = vect_recog_temp_ssa_var (type, NULL);
-  pattern_stmt = gimple_build_assign (var, WIDEN_SUM_EXPR, oprnd0, oprnd1);
-
-  if (dump_enabled_p ())
-    {
-      dump_printf_loc (MSG_NOTE, vect_location,
-                       "vect_recog_widen_sum_pattern: detected: ");
-      dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
-    }
+  pattern_stmt = gimple_build_assign (var, WIDEN_SUM_EXPR, unprom0.op, oprnd1);
 
   return pattern_stmt;
 }
 
-
-/* Return TRUE if the operation in STMT can be performed on a smaller type.
-
-   Input:
-   STMT - a statement to check.
-   DEF - we support operations with two operands, one of which is constant.
-         The other operand can be defined by a demotion operation, or by a
-         previous statement in a sequence of over-promoted operations.  In the
-         later case DEF is used to replace that operand.  (It is defined by a
-         pattern statement we created for the previous statement in the
-         sequence).
-
-   Input/output:
-   NEW_TYPE - Output: a smaller type that we are trying to use.  Input: if not
-         NULL, it's the type of DEF.
-   STMTS - additional pattern statements.  If a pattern statement (type
-         conversion) is created in this function, its original statement is
-         added to STMTS.
-
-   Output:
-   OP0, OP1 - if the operation fits a smaller type, OP0 and OP1 are the new
-         operands to use in the new pattern statement for STMT (will be created
-         in vect_recog_over_widening_pattern ()).
-   NEW_DEF_STMT - in case DEF has to be promoted, we create two pattern
-         statements for STMT: the first one is a type promotion and the second
-         one is the operation itself.  We return the type promotion statement
-	 in NEW_DEF_STMT and further store it in STMT_VINFO_PATTERN_DEF_SEQ of
-         the second pattern statement.  */
-
-static bool
-vect_operation_fits_smaller_type (gimple *stmt, tree def, tree *new_type,
-				  tree *op0, tree *op1, gimple **new_def_stmt,
-				  vec<gimple *> *stmts)
-{
-  enum tree_code code;
-  tree const_oprnd, oprnd;
-  tree interm_type = NULL_TREE, half_type, new_oprnd, type;
-  gimple *def_stmt, *new_stmt;
-  bool first = false;
-  bool promotion;
-
-  *op0 = NULL_TREE;
-  *op1 = NULL_TREE;
-  *new_def_stmt = NULL;
-
-  if (!is_gimple_assign (stmt))
-    return false;
-
-  code = gimple_assign_rhs_code (stmt);
-  if (code != LSHIFT_EXPR && code != RSHIFT_EXPR
-      && code != BIT_IOR_EXPR && code != BIT_XOR_EXPR && code != BIT_AND_EXPR)
-    return false;
-
-  oprnd = gimple_assign_rhs1 (stmt);
-  const_oprnd = gimple_assign_rhs2 (stmt);
-  type = gimple_expr_type (stmt);
-
-  if (TREE_CODE (oprnd) != SSA_NAME
-      || TREE_CODE (const_oprnd) != INTEGER_CST)
-    return false;
-
-  /* If oprnd has other uses besides that in stmt we cannot mark it
-     as being part of a pattern only.  */
-  if (!has_single_use (oprnd))
-    return false;
-
-  /* If we are in the middle of a sequence, we use DEF from a previous
-     statement.  Otherwise, OPRND has to be a result of type promotion.  */
-  if (*new_type)
-    {
-      half_type = *new_type;
-      oprnd = def;
-    }
-  else
-    {
-      first = true;
-      if (!type_conversion_p (oprnd, stmt, false, &half_type, &def_stmt,
-			      &promotion)
-	  || !promotion
-	  || !vect_same_loop_or_bb_p (stmt, def_stmt))
-        return false;
-    }
-
-  /* Can we perform the operation on a smaller type?  */
-  switch (code)
-    {
-      case BIT_IOR_EXPR:
-      case BIT_XOR_EXPR:
-      case BIT_AND_EXPR:
-        if (!int_fits_type_p (const_oprnd, half_type))
-          {
-            /* HALF_TYPE is not enough.  Try a bigger type if possible.  */
-            if (TYPE_PRECISION (type) < (TYPE_PRECISION (half_type) * 4))
-              return false;
-
-            interm_type = build_nonstandard_integer_type (
-                        TYPE_PRECISION (half_type) * 2, TYPE_UNSIGNED (type));
-            if (!int_fits_type_p (const_oprnd, interm_type))
-              return false;
-          }
-
-        break;
-
-      case LSHIFT_EXPR:
-        /* Try intermediate type - HALF_TYPE is not enough for sure.  */
-        if (TYPE_PRECISION (type) < (TYPE_PRECISION (half_type) * 4))
-          return false;
-
-        /* Check that HALF_TYPE size + shift amount <= INTERM_TYPE size.
-          (e.g., if the original value was char, the shift amount is at most 8
-           if we want to use short).  */
-        if (compare_tree_int (const_oprnd, TYPE_PRECISION (half_type)) == 1)
-          return false;
-
-        interm_type = build_nonstandard_integer_type (
-                        TYPE_PRECISION (half_type) * 2, TYPE_UNSIGNED (type));
-
-        if (!vect_supportable_shift (code, interm_type))
-          return false;
-
-        break;
-
-      case RSHIFT_EXPR:
-        if (vect_supportable_shift (code, half_type))
-          break;
-
-        /* Try intermediate type - HALF_TYPE is not supported.  */
-        if (TYPE_PRECISION (type) < (TYPE_PRECISION (half_type) * 4))
-          return false;
-
-        interm_type = build_nonstandard_integer_type (
-                        TYPE_PRECISION (half_type) * 2, TYPE_UNSIGNED (type));
-
-        if (!vect_supportable_shift (code, interm_type))
-          return false;
-
-        break;
-
-      default:
-        gcc_unreachable ();
-    }
-
-  /* There are four possible cases:
-     1. OPRND is defined by a type promotion (in that case FIRST is TRUE, it's
-        the first statement in the sequence)
-        a. The original, HALF_TYPE, is not enough - we replace the promotion
-           from HALF_TYPE to TYPE with a promotion to INTERM_TYPE.
-        b. HALF_TYPE is sufficient, OPRND is set as the RHS of the original
-           promotion.
-     2. OPRND is defined by a pattern statement we created.
-        a. Its type is not sufficient for the operation, we create a new stmt:
-           a type conversion for OPRND from HALF_TYPE to INTERM_TYPE.  We store
-           this statement in NEW_DEF_STMT, and it is later put in
-	   STMT_VINFO_PATTERN_DEF_SEQ of the pattern statement for STMT.
-        b. OPRND is good to use in the new statement.  */
-  if (first)
-    {
-      if (interm_type)
-        {
-          /* Replace the original type conversion HALF_TYPE->TYPE with
-             HALF_TYPE->INTERM_TYPE.  */
-          if (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt)))
-            {
-              new_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt));
-              /* Check if the already created pattern stmt is what we need.  */
-              if (!is_gimple_assign (new_stmt)
-                  || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (new_stmt))
-                  || TREE_TYPE (gimple_assign_lhs (new_stmt)) != interm_type)
-                return false;
-
-	      stmts->safe_push (def_stmt);
-              oprnd = gimple_assign_lhs (new_stmt);
-            }
-          else
-            {
-              /* Create NEW_OPRND = (INTERM_TYPE) OPRND.  */
-              oprnd = gimple_assign_rhs1 (def_stmt);
-	      new_oprnd = make_ssa_name (interm_type);
-	      new_stmt = gimple_build_assign (new_oprnd, NOP_EXPR, oprnd);
-              STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt)) = new_stmt;
-              stmts->safe_push (def_stmt);
-              oprnd = new_oprnd;
-            }
-        }
-      else
-        {
-          /* Retrieve the operand before the type promotion.  */
-          oprnd = gimple_assign_rhs1 (def_stmt);
-        }
-    }
-  else
-    {
-      if (interm_type)
-        {
-          /* Create a type conversion HALF_TYPE->INTERM_TYPE.  */
-	  new_oprnd = make_ssa_name (interm_type);
-	  new_stmt = gimple_build_assign (new_oprnd, NOP_EXPR, oprnd);
-          oprnd = new_oprnd;
-          *new_def_stmt = new_stmt;
-        }
-
-      /* Otherwise, OPRND is already set.  */
-    }
-
-  if (interm_type)
-    *new_type = interm_type;
-  else
-    *new_type = half_type;
-
-  *op0 = oprnd;
-  *op1 = fold_convert (*new_type, const_oprnd);
-
-  return true;
-}
-
-
-/* Try to find a statement or a sequence of statements that can be performed
-   on a smaller type:
-
-     type x_t;
-     TYPE x_T, res0_T, res1_T;
-   loop:
-     S1  x_t = *p;
-     S2  x_T = (TYPE) x_t;
-     S3  res0_T = op (x_T, C0);
-     S4  res1_T = op (res0_T, C1);
-     S5  ... = () res1_T;  - type demotion
-
-   where type 'TYPE' is at least double the size of type 'type', C0 and C1 are
-   constants.
-   Check if S3 and S4 can be done on a smaller type than 'TYPE', it can either
-   be 'type' or some intermediate type.  For now, we expect S5 to be a type
-   demotion operation.  We also check that S3 and S4 have only one use.  */
+/* Recognize cases in which an operation is performed in one type WTYPE
+   but could be done more efficiently in a narrower type NTYPE.  For example,
+   if we have:
+
+     ATYPE a;  // narrower than NTYPE
+     BTYPE b;  // narrower than NTYPE
+     WTYPE aw = (WTYPE) a;
+     WTYPE bw = (WTYPE) b;
+     WTYPE res = aw + bw;  // only uses of aw and bw
+
+   then it would be more efficient to do:
+
+     NTYPE an = (NTYPE) a;
+     NTYPE bn = (NTYPE) b;
+     NTYPE resn = an + bn;
+     WTYPE res = (WTYPE) resn;
+
+   Other situations include things like:
+
+     ATYPE a;  // NTYPE or narrower
+     WTYPE aw = (WTYPE) a;
+     WTYPE res = aw + b;
+
+   when only "(NTYPE) res" is significant.  In that case it's more efficient
+   to truncate "b" and do the operation on NTYPE instead:
+
+     NTYPE an = (NTYPE) a;
+     NTYPE bn = (NTYPE) b;  // truncation
+     NTYPE resn = an + bn;
+     WTYPE res = (WTYPE) resn;
+
+   All users of "res" should then use "resn" instead, making the final
+   statement dead (not marked as relevant).  The final statement is still
+   needed to maintain the type correctness of the IR.
+
+   vect_determine_precisions has already determined the minimum
+   precison of the operation and the minimum precision required
+   by users of the result.  */
 
 static gimple *
-vect_recog_over_widening_pattern (vec<gimple *> *stmts,
-                                  tree *type_in, tree *type_out)
+vect_recog_over_widening_pattern (stmt_vec_info last_stmt_info, tree *type_out)
 {
-  gimple *stmt = stmts->pop ();
-  gimple *pattern_stmt = NULL, *new_def_stmt, *prev_stmt = NULL,
-	 *use_stmt = NULL;
-  tree op0, op1, vectype = NULL_TREE, use_lhs, use_type;
-  tree var = NULL_TREE, new_type = NULL_TREE, new_oprnd;
-  bool first;
-  tree type = NULL;
-
-  first = true;
-  while (1)
+  gassign *last_stmt = dyn_cast <gassign *> (last_stmt_info->stmt);
+  if (!last_stmt)
+    return NULL;
+
+  /* See whether we have found that this operation can be done on a
+     narrower type without changing its semantics.  */
+  unsigned int new_precision = last_stmt_info->operation_precision;
+  if (!new_precision)
+    return NULL;
+
+  vec_info *vinfo = last_stmt_info->vinfo;
+  tree lhs = gimple_assign_lhs (last_stmt);
+  tree type = TREE_TYPE (lhs);
+  tree_code code = gimple_assign_rhs_code (last_stmt);
+
+  /* Keep the first operand of a COND_EXPR as-is: only the other two
+     operands are interesting.  */
+  unsigned int first_op = (code == COND_EXPR ? 2 : 1);
+
+  /* Check the operands.  */
+  unsigned int nops = gimple_num_ops (last_stmt) - first_op;
+  auto_vec <vect_unpromoted_value, 3> unprom (nops);
+  unprom.quick_grow (nops);
+  unsigned int min_precision = 0;
+  bool single_use_p = false;
+  for (unsigned int i = 0; i < nops; ++i)
     {
-      if (!vinfo_for_stmt (stmt)
-          || STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (stmt)))
-        return NULL;
-
-      new_def_stmt = NULL;
-      if (!vect_operation_fits_smaller_type (stmt, var, &new_type,
-                                             &op0, &op1, &new_def_stmt,
-                                             stmts))
-        {
-          if (first)
-            return NULL;
-          else
-            break;
-        }
-
-      /* STMT can be performed on a smaller type.  Check its uses.  */
-      use_stmt = vect_single_imm_use (stmt);
-      if (!use_stmt || !is_gimple_assign (use_stmt))
-        return NULL;
-
-      /* Create pattern statement for STMT.  */
-      vectype = get_vectype_for_scalar_type (new_type);
-      if (!vectype)
-        return NULL;
-
-      /* We want to collect all the statements for which we create pattern
-         statetments, except for the case when the last statement in the
-         sequence doesn't have a corresponding pattern statement.  In such
-         case we associate the last pattern statement with the last statement
-         in the sequence.  Therefore, we only add the original statement to
-         the list if we know that it is not the last.  */
-      if (prev_stmt)
-        stmts->safe_push (prev_stmt);
-
-      var = vect_recog_temp_ssa_var (new_type, NULL);
-      pattern_stmt
-	= gimple_build_assign (var, gimple_assign_rhs_code (stmt), op0, op1);
-      STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt)) = pattern_stmt;
-      new_pattern_def_seq (vinfo_for_stmt (stmt), new_def_stmt);
-
-      if (dump_enabled_p ())
-        {
-          dump_printf_loc (MSG_NOTE, vect_location,
-                           "created pattern stmt: ");
-          dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
-        }
-
-      type = gimple_expr_type (stmt);
-      prev_stmt = stmt;
-      stmt = use_stmt;
-
-      first = false;
+      tree op = gimple_op (last_stmt, first_op + i);
+      if (TREE_CODE (op) == INTEGER_CST)
+	unprom[i].set_op (op, vect_constant_def);
+      else if (TREE_CODE (op) == SSA_NAME)
+	{
+	  bool op_single_use_p = true;
+	  if (!vect_look_through_possible_promotion (vinfo, op, &unprom[i],
+						     &op_single_use_p))
+	    return NULL;
+	  /* If:
+
+	     (1) N bits of the result are needed;
+	     (2) all inputs are widened from M<N bits; and
+	     (3) one operand OP is a single-use SSA name
+
+	     we can shift the M->N widening from OP to the output
+	     without changing the number or type of extensions involved.
+	     This then reduces the number of copies of STMT_INFO.
+
+	     If instead of (3) more than one operand is a single-use SSA name,
+	     shifting the extension to the output is even more of a win.
+
+	     If instead:
+
+	     (1) N bits of the result are needed;
+	     (2) one operand OP2 is widened from M2<N bits;
+	     (3) another operand OP1 is widened from M1<M2 bits; and
+	     (4) both OP1 and OP2 are single-use
+
+	     the choice is between:
+
+	     (a) truncating OP2 to M1, doing the operation on M1,
+		 and then widening the result to N
+
+	     (b) widening OP1 to M2, doing the operation on M2, and then
+		 widening the result to N
+
+	     Both shift the M2->N widening of the inputs to the output.
+	     (a) additionally shifts the M1->M2 widening to the output;
+	     it requires fewer copies of STMT_INFO but requires an extra
+	     M2->M1 truncation.
+
+	     Which is better will depend on the complexity and cost of
+	     STMT_INFO, which is hard to predict at this stage.  However,
+	     a clear tie-breaker in favor of (b) is the fact that the
+	     truncation in (a) increases the length of the operation chain.
+
+	     If instead of (4) only one of OP1 or OP2 is single-use,
+	     (b) is still a win over doing the operation in N bits:
+	     it still shifts the M2->N widening on the single-use operand
+	     to the output and reduces the number of STMT_INFO copies.
+
+	     If neither operand is single-use then operating on fewer than
+	     N bits might lead to more extensions overall.  Whether it does
+	     or not depends on global information about the vectorization
+	     region, and whether that's a good trade-off would again
+	     depend on the complexity and cost of the statements involved,
+	     as well as things like register pressure that are not normally
+	     modelled at this stage.  We therefore ignore these cases
+	     and just optimize the clear single-use wins above.
+
+	     Thus we take the maximum precision of the unpromoted operands
+	     and record whether any operand is single-use.  */
+	  if (unprom[i].dt == vect_internal_def)
+	    {
+	      min_precision = MAX (min_precision,
+				   TYPE_PRECISION (unprom[i].type));
+	      single_use_p |= op_single_use_p;
+	    }
+	}
     }
 
-  /* We got a sequence.  We expect it to end with a type demotion operation.
-     Otherwise, we quit (for now).  There are three possible cases: the
-     conversion is to NEW_TYPE (we don't do anything), the conversion is to
-     a type bigger than NEW_TYPE and/or the signedness of USE_TYPE and
-     NEW_TYPE differs (we create a new conversion statement).  */
-  if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt)))
-    {
-      use_lhs = gimple_assign_lhs (use_stmt);
-      use_type = TREE_TYPE (use_lhs);
-      /* Support only type demotion or signedess change.  */
-      if (!INTEGRAL_TYPE_P (use_type)
-	  || TYPE_PRECISION (type) <= TYPE_PRECISION (use_type))
-        return NULL;
-
-      /* Check that NEW_TYPE is not bigger than the conversion result.  */
-      if (TYPE_PRECISION (new_type) > TYPE_PRECISION (use_type))
-	return NULL;
-
-      if (TYPE_UNSIGNED (new_type) != TYPE_UNSIGNED (use_type)
-          || TYPE_PRECISION (new_type) != TYPE_PRECISION (use_type))
-        {
-          /* Create NEW_TYPE->USE_TYPE conversion.  */
-	  new_oprnd = make_ssa_name (use_type);
-	  pattern_stmt = gimple_build_assign (new_oprnd, NOP_EXPR, var);
-          STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use_stmt)) = pattern_stmt;
-
-          *type_in = get_vectype_for_scalar_type (new_type);
-          *type_out = get_vectype_for_scalar_type (use_type);
-
-          /* We created a pattern statement for the last statement in the
-             sequence, so we don't need to associate it with the pattern
-             statement created for PREV_STMT.  Therefore, we add PREV_STMT
-             to the list in order to mark it later in vect_pattern_recog_1.  */
-          if (prev_stmt)
-            stmts->safe_push (prev_stmt);
-        }
-      else
-        {
-          if (prev_stmt)
-	    STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (use_stmt))
-	       = STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (prev_stmt));
-
-          *type_in = vectype;
-          *type_out = NULL_TREE;
-        }
-
-      stmts->safe_push (use_stmt);
-    }
+  /* Although the operation could be done in operation_precision, we have
+     to balance that against introducing extra truncations or extensions.
+     Calculate the minimum precision that can be handled efficiently.
+
+     The loop above determined that the operation could be handled
+     efficiently in MIN_PRECISION if SINGLE_USE_P; this would shift an
+     extension from the inputs to the output without introducing more
+     instructions, and would reduce the number of instructions required
+     for STMT_INFO itself.
+
+     vect_determine_precisions has also determined that the result only
+     needs min_output_precision bits.  Truncating by a factor of N times
+     requires a tree of N - 1 instructions, so if TYPE is N times wider
+     than min_output_precision, doing the operation in TYPE and truncating
+     the result requires N + (N - 1) = 2N - 1 instructions per output vector.
+     In contrast:
+
+     - truncating the input to a unary operation and doing the operation
+       in the new type requires at most N - 1 + 1 = N instructions per
+       output vector
+
+     - doing the same for a binary operation requires at most
+       (N - 1) * 2 + 1 = 2N - 1 instructions per output vector
+
+     Both unary and binary operations require fewer instructions than
+     this if the operands were extended from a suitable truncated form.
+     Thus there is usually nothing to lose by doing operations in
+     min_output_precision bits, but there can be something to gain.  */
+  if (!single_use_p)
+    min_precision = last_stmt_info->min_output_precision;
   else
-    /* TODO: support general case, create a conversion to the correct type.  */
+    min_precision = MIN (min_precision, last_stmt_info->min_output_precision);
+
+  /* Apply the minimum efficient precision we just calculated.  */
+  if (new_precision < min_precision)
+    new_precision = min_precision;
+  if (new_precision >= TYPE_PRECISION (type))
+    return NULL;
+
+  vect_pattern_detected ("vect_recog_over_widening_pattern", last_stmt);
+
+  *type_out = get_vectype_for_scalar_type (type);
+  if (!*type_out)
     return NULL;
 
-  /* Pattern detected.  */
+  /* We've found a viable pattern.  Get the new type of the operation.  */
+  bool unsigned_p = (last_stmt_info->operation_sign == UNSIGNED);
+  tree new_type = build_nonstandard_integer_type (new_precision, unsigned_p);
+
+  /* We specifically don't check here whether the target supports the
+     new operation, since it might be something that a later pattern
+     wants to rewrite anyway.  If targets have a minimum element size
+     for some optabs, we should pattern-match smaller ops to larger ops
+     where beneficial.  */
+  tree new_vectype = get_vectype_for_scalar_type (new_type);
+  if (!new_vectype)
+    return NULL;
+
   if (dump_enabled_p ())
-    {
-      dump_printf_loc (MSG_NOTE, vect_location,
-                       "vect_recog_over_widening_pattern: detected: ");
-      dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
-    }
+    dump_printf_loc (MSG_NOTE, vect_location, "demoting %T to %T\n",
+		     type, new_type);
+
+  /* Calculate the rhs operands for an operation on NEW_TYPE.  */
+  tree ops[3] = {};
+  for (unsigned int i = 1; i < first_op; ++i)
+    ops[i - 1] = gimple_op (last_stmt, i);
+  vect_convert_inputs (last_stmt_info, nops, &ops[first_op - 1],
+		       new_type, &unprom[0], new_vectype);
+
+  /* Use the operation to produce a result of type NEW_TYPE.  */
+  tree new_var = vect_recog_temp_ssa_var (new_type, NULL);
+  gimple *pattern_stmt = gimple_build_assign (new_var, code,
+					      ops[0], ops[1], ops[2]);
+  gimple_set_location (pattern_stmt, gimple_location (last_stmt));
+
+  if (dump_enabled_p ())
+    dump_printf_loc (MSG_NOTE, vect_location,
+		     "created pattern stmt: %G", pattern_stmt);
+
+  pattern_stmt = vect_convert_output (last_stmt_info, type,
+				      pattern_stmt, new_vectype);
 
   return pattern_stmt;
 }
 
-/* Detect widening shift pattern:
-
-   type a_t;
-   TYPE a_T, res_T;
-
-   S1 a_t = ;
-   S2 a_T = (TYPE) a_t;
-   S3 res_T = a_T << CONST;
-
-  where type 'TYPE' is at least double the size of type 'type'.
-
-  Also detect cases where the shift result is immediately converted
-  to another type 'result_type' that is no larger in size than 'TYPE'.
-  In those cases we perform a widen-shift that directly results in
-  'result_type', to avoid a possible over-widening situation:
-
-  type a_t;
-  TYPE a_T, res_T;
-  result_type res_result;
-
-  S1 a_t = ;
-  S2 a_T = (TYPE) a_t;
-  S3 res_T = a_T << CONST;
-  S4 res_result = (result_type) res_T;
-      '--> res_result' = a_t w<< CONST;
-
-  And a case when 'TYPE' is 4 times bigger than 'type'.  In that case we
-  create an additional pattern stmt for S2 to create a variable of an
-  intermediate type, and perform widen-shift on the intermediate type:
-
-  type a_t;
-  interm_type a_it;
-  TYPE a_T, res_T, res_T';
-
-  S1 a_t = ;
-  S2 a_T = (TYPE) a_t;
-      '--> a_it = (interm_type) a_t;
-  S3 res_T = a_T << CONST;
-      '--> res_T' = a_it <<* CONST;
-
-  Input/Output:
-
-  * STMTS: Contains a stmt from which the pattern search begins.
-    In case of unsigned widen-shift, the original stmt (S3) is replaced with S4
-    in STMTS.  When an intermediate type is used and a pattern statement is
-    created for S2, we also put S2 here (before S3).
-
-  Output:
-
-  * TYPE_IN: The type of the input arguments to the pattern.
-
-  * TYPE_OUT: The type of the output of this pattern.
-
-  * Return value: A new stmt that will be used to replace the sequence of
-    stmts that constitute the pattern.  In this case it will be:
-    WIDEN_LSHIFT_EXPR <a_t, CONST>.  */
+/* Recognize the patterns:
+
+	    ATYPE a;  // narrower than TYPE
+	    BTYPE b;  // narrower than TYPE
+	(1) TYPE avg = ((TYPE) a + (TYPE) b) >> 1;
+     or (2) TYPE avg = ((TYPE) a + (TYPE) b + 1) >> 1;
+
+   where only the bottom half of avg is used.  Try to transform them into:
+
+	(1) NTYPE avg' = .AVG_FLOOR ((NTYPE) a, (NTYPE) b);
+     or (2) NTYPE avg' = .AVG_CEIL ((NTYPE) a, (NTYPE) b);
+
+  followed by:
+
+	    TYPE avg = (TYPE) avg';
+
+  where NTYPE is no wider than half of TYPE.  Since only the bottom half
+  of avg is used, all or part of the cast of avg' should become redundant.  */
 
 static gimple *
-vect_recog_widen_shift_pattern (vec<gimple *> *stmts,
-				tree *type_in, tree *type_out)
+vect_recog_average_pattern (stmt_vec_info last_stmt_info, tree *type_out)
 {
-  gimple *last_stmt = stmts->pop ();
-  gimple *def_stmt0;
-  tree oprnd0, oprnd1;
-  tree type, half_type0;
-  gimple *pattern_stmt;
-  tree vectype, vectype_out = NULL_TREE;
-  tree var;
-  enum tree_code dummy_code;
-  int dummy_int;
-  vec<tree>  dummy_vec;
-  gimple *use_stmt;
-  bool promotion;
-
-  if (!is_gimple_assign (last_stmt) || !vinfo_for_stmt (last_stmt))
+  /* Check for a shift right by one bit.  */
+  gassign *last_stmt = dyn_cast <gassign *> (last_stmt_info->stmt);
+  vec_info *vinfo = last_stmt_info->vinfo;
+  if (!last_stmt
+      || gimple_assign_rhs_code (last_stmt) != RSHIFT_EXPR
+      || !integer_onep (gimple_assign_rhs2 (last_stmt)))
+    return NULL;
+
+  /* Check that the shift result is wider than the users of the
+     result need (i.e. that narrowing would be a natural choice).  */
+  tree lhs = gimple_assign_lhs (last_stmt);
+  tree type = TREE_TYPE (lhs);
+  unsigned int target_precision
+    = vect_element_precision (last_stmt_info->min_output_precision);
+  if (!INTEGRAL_TYPE_P (type) || target_precision >= TYPE_PRECISION (type))
     return NULL;
 
-  if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (last_stmt)))
-    return NULL;
-
-  if (gimple_assign_rhs_code (last_stmt) != LSHIFT_EXPR)
+  /* Get the definition of the shift input.  */
+  tree rshift_rhs = gimple_assign_rhs1 (last_stmt);
+  stmt_vec_info plus_stmt_info = vect_get_internal_def (vinfo, rshift_rhs);
+  if (!plus_stmt_info)
     return NULL;
 
-  oprnd0 = gimple_assign_rhs1 (last_stmt);
-  oprnd1 = gimple_assign_rhs2 (last_stmt);
-  if (TREE_CODE (oprnd0) != SSA_NAME || TREE_CODE (oprnd1) != INTEGER_CST)
+  /* Check whether the shift input can be seen as a tree of additions on
+     2 or 3 widened inputs.
+
+     Note that the pattern should be a win even if the result of one or
+     more additions is reused elsewhere: if the pattern matches, we'd be
+     replacing 2N RSHIFT_EXPRs and N VEC_PACK_*s with N IFN_AVG_*s.  */
+  internal_fn ifn = IFN_AVG_FLOOR;
+  vect_unpromoted_value unprom[3];
+  tree new_type;
+  unsigned int nops = vect_widened_op_tree (plus_stmt_info, PLUS_EXPR,
+					    PLUS_EXPR, false, 3,
+					    unprom, &new_type);
+  if (nops == 0)
     return NULL;
-
-  /* Check operand 0: it has to be defined by a type promotion.  */
-  if (!type_conversion_p (oprnd0, last_stmt, false, &half_type0, &def_stmt0,
-			  &promotion)
-      || !promotion)
-     return NULL;
-
-  /* Check operand 1: has to be positive.  We check that it fits the type
-     in vect_handle_widen_op_by_const ().  */
-  if (tree_int_cst_compare (oprnd1, size_zero_node) <= 0)
+  if (nops == 3)
+    {
+      /* Check that one operand is 1.  */
+      unsigned int i;
+      for (i = 0; i < 3; ++i)
+	if (integer_onep (unprom[i].op))
+	  break;
+      if (i == 3)
+	return NULL;
+      /* Throw away the 1 operand and keep the other two.  */
+      if (i < 2)
+	unprom[i] = unprom[2];
+      ifn = IFN_AVG_CEIL;
+    }
+
+  vect_pattern_detected ("vect_recog_average_pattern", last_stmt);
+
+  /* We know that:
+
+     (a) the operation can be viewed as:
+
+	   TYPE widened0 = (TYPE) UNPROM[0];
+	   TYPE widened1 = (TYPE) UNPROM[1];
+	   TYPE tmp1 = widened0 + widened1 {+ 1};
+	   TYPE tmp2 = tmp1 >> 1;   // LAST_STMT_INFO
+
+     (b) the first two statements are equivalent to:
+
+	   TYPE widened0 = (TYPE) (NEW_TYPE) UNPROM[0];
+	   TYPE widened1 = (TYPE) (NEW_TYPE) UNPROM[1];
+
+     (c) vect_recog_over_widening_pattern has already tried to narrow TYPE
+	 where sensible;
+
+     (d) all the operations can be performed correctly at twice the width of
+	 NEW_TYPE, due to the nature of the average operation; and
+
+     (e) users of the result of the right shift need only TARGET_PRECISION
+	 bits, where TARGET_PRECISION is no more than half of TYPE's
+	 precision.
+
+     Under these circumstances, the only situation in which NEW_TYPE
+     could be narrower than TARGET_PRECISION is if widened0, widened1
+     and an addition result are all used more than once.  Thus we can
+     treat any widening of UNPROM[0] and UNPROM[1] to TARGET_PRECISION
+     as "free", whereas widening the result of the average instruction
+     from NEW_TYPE to TARGET_PRECISION would be a new operation.  It's
+     therefore better not to go narrower than TARGET_PRECISION.  */
+  if (TYPE_PRECISION (new_type) < target_precision)
+    new_type = build_nonstandard_integer_type (target_precision,
+					       TYPE_UNSIGNED (new_type));
+
+  /* Check for target support.  */
+  tree new_vectype = get_vectype_for_scalar_type (new_type);
+  if (!new_vectype
+      || !direct_internal_fn_supported_p (ifn, new_vectype,
+					  OPTIMIZE_FOR_SPEED))
     return NULL;
 
-  oprnd0 = gimple_assign_rhs1 (def_stmt0);
-  type = gimple_expr_type (last_stmt);
-
-  /* Check for subsequent conversion to another type.  */
-  use_stmt = vect_single_imm_use (last_stmt);
-  if (use_stmt && is_gimple_assign (use_stmt)
-      && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt))
-      && !STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (use_stmt)))
-    {
-      tree use_lhs = gimple_assign_lhs (use_stmt);
-      tree use_type = TREE_TYPE (use_lhs);
-
-      if (INTEGRAL_TYPE_P (use_type)
-	  && TYPE_PRECISION (use_type) <= TYPE_PRECISION (type))
-	{
-	  last_stmt = use_stmt;
-	  type = use_type;
-	}
-    }
-
-  /* Check if this a widening operation.  */
-  gimple *wstmt = NULL;
-  if (!vect_handle_widen_op_by_const (last_stmt, LSHIFT_EXPR, oprnd1,
-       				      &oprnd0, &wstmt,
-	                              type, &half_type0, def_stmt0))
+  /* The IR requires a valid vector type for the cast result, even though
+     it's likely to be discarded.  */
+  *type_out = get_vectype_for_scalar_type (type);
+  if (!*type_out)
     return NULL;
 
-  /* Pattern detected.  */
+  /* Generate the IFN_AVG* call.  */
+  tree new_var = vect_recog_temp_ssa_var (new_type, NULL);
+  tree new_ops[2];
+  vect_convert_inputs (last_stmt_info, 2, new_ops, new_type,
+		       unprom, new_vectype);
+  gcall *average_stmt = gimple_build_call_internal (ifn, 2, new_ops[0],
+						    new_ops[1]);
+  gimple_call_set_lhs (average_stmt, new_var);
+  gimple_set_location (average_stmt, gimple_location (last_stmt));
+
   if (dump_enabled_p ())
     dump_printf_loc (MSG_NOTE, vect_location,
-                     "vect_recog_widen_shift_pattern: detected:\n");
-
-  /* Check target support.  */
-  vectype = get_vectype_for_scalar_type (half_type0);
-  vectype_out = get_vectype_for_scalar_type (type);
-
-  if (!vectype
-      || !vectype_out
-      || !supportable_widening_operation (WIDEN_LSHIFT_EXPR, last_stmt,
-					  vectype_out, vectype,
-					  &dummy_code, &dummy_code,
-					  &dummy_int, &dummy_vec))
+		     "created pattern stmt: %G", average_stmt);
+
+  return vect_convert_output (last_stmt_info, type, average_stmt, new_vectype);
+}
+
+/* Recognize cases in which the input to a cast is wider than its
+   output, and the input is fed by a widening operation.  Fold this
+   by removing the unnecessary intermediate widening.  E.g.:
+
+     unsigned char a;
+     unsigned int b = (unsigned int) a;
+     unsigned short c = (unsigned short) b;
+
+   -->
+
+     unsigned short c = (unsigned short) a;
+
+   Although this is rare in input IR, it is an expected side-effect
+   of the over-widening pattern above.
+
+   This is beneficial also for integer-to-float conversions, if the
+   widened integer has more bits than the float, and if the unwidened
+   input doesn't.  */
+
+static gimple *
+vect_recog_cast_forwprop_pattern (stmt_vec_info last_stmt_info, tree *type_out)
+{
+  /* Check for a cast, including an integer-to-float conversion.  */
+  gassign *last_stmt = dyn_cast <gassign *> (last_stmt_info->stmt);
+  if (!last_stmt)
+    return NULL;
+  tree_code code = gimple_assign_rhs_code (last_stmt);
+  if (!CONVERT_EXPR_CODE_P (code) && code != FLOAT_EXPR)
+    return NULL;
+
+  /* Make sure that the rhs is a scalar with a natural bitsize.  */
+  tree lhs = gimple_assign_lhs (last_stmt);
+  if (!lhs)
+    return NULL;
+  tree lhs_type = TREE_TYPE (lhs);
+  scalar_mode lhs_mode;
+  if (VECT_SCALAR_BOOLEAN_TYPE_P (lhs_type)
+      || !is_a <scalar_mode> (TYPE_MODE (lhs_type), &lhs_mode))
     return NULL;
 
-  *type_in = vectype;
-  *type_out = vectype_out;
-
-  /* Pattern supported.  Create a stmt to be used to replace the pattern.  */
-  var = vect_recog_temp_ssa_var (type, NULL);
-  pattern_stmt =
-    gimple_build_assign (var, WIDEN_LSHIFT_EXPR, oprnd0, oprnd1);
-  if (wstmt)
-    {
-      stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
-      new_pattern_def_seq (stmt_vinfo, wstmt);
-      stmt_vec_info new_stmt_info
-	= new_stmt_vec_info (wstmt, stmt_vinfo->vinfo);
-      set_vinfo_for_stmt (wstmt, new_stmt_info);
-      STMT_VINFO_VECTYPE (new_stmt_info) = vectype;
-    }
-
-  if (dump_enabled_p ())
-    dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt, 0);
-
-  stmts->safe_push (last_stmt);
+  /* Check for a narrowing operation (from a vector point of view).  */
+  tree rhs = gimple_assign_rhs1 (last_stmt);
+  tree rhs_type = TREE_TYPE (rhs);
+  if (!INTEGRAL_TYPE_P (rhs_type)
+      || VECT_SCALAR_BOOLEAN_TYPE_P (rhs_type)
+      || TYPE_PRECISION (rhs_type) <= GET_MODE_BITSIZE (lhs_mode))
+    return NULL;
+
+  /* Try to find an unpromoted input.  */
+  vec_info *vinfo = last_stmt_info->vinfo;
+  vect_unpromoted_value unprom;
+  if (!vect_look_through_possible_promotion (vinfo, rhs, &unprom)
+      || TYPE_PRECISION (unprom.type) >= TYPE_PRECISION (rhs_type))
+    return NULL;
+
+  /* If the bits above RHS_TYPE matter, make sure that they're the
+     same when extending from UNPROM as they are when extending from RHS.  */
+  if (!INTEGRAL_TYPE_P (lhs_type)
+      && TYPE_SIGN (rhs_type) != TYPE_SIGN (unprom.type))
+    return NULL;
+
+  /* We can get the same result by casting UNPROM directly, to avoid
+     the unnecessary widening and narrowing.  */
+  vect_pattern_detected ("vect_recog_cast_forwprop_pattern", last_stmt);
+
+  *type_out = get_vectype_for_scalar_type (lhs_type);
+  if (!*type_out)
+    return NULL;
+
+  tree new_var = vect_recog_temp_ssa_var (lhs_type, NULL);
+  gimple *pattern_stmt = gimple_build_assign (new_var, code, unprom.op);
+  gimple_set_location (pattern_stmt, gimple_location (last_stmt));
+
   return pattern_stmt;
 }
 
+/* Try to detect a shift left of a widened input, converting LSHIFT_EXPR
+   to WIDEN_LSHIFT_EXPR.  See vect_recog_widen_op_pattern for details.  */
+
+static gimple *
+vect_recog_widen_shift_pattern (stmt_vec_info last_stmt_info, tree *type_out)
+{
+  return vect_recog_widen_op_pattern (last_stmt_info, type_out, LSHIFT_EXPR,
+				      WIDEN_LSHIFT_EXPR, true,
+				      "vect_recog_widen_shift_pattern");
+}
+
 /* Detect a rotate pattern wouldn't be otherwise vectorized:
 
    type a_t, b_t, c_t;
@@ -1755,7 +1912,7 @@
 
   Input/Output:
 
-  * STMTS: Contains a stmt from which the pattern search begins,
+  * STMT_VINFO: The stmt from which the pattern search begins,
     i.e. the shift/rotate stmt.  The original stmt (S0) is replaced
     with a sequence:
 
@@ -1769,21 +1926,18 @@
 
   Output:
 
-  * TYPE_IN: The type of the input arguments to the pattern.
-
   * TYPE_OUT: The type of the output of this pattern.
 
   * Return value: A new stmt that will be used to replace the rotate
     S0 stmt.  */
 
 static gimple *
-vect_recog_rotate_pattern (vec<gimple *> *stmts, tree *type_in, tree *type_out)
+vect_recog_rotate_pattern (stmt_vec_info stmt_vinfo, tree *type_out)
 {
-  gimple *last_stmt = stmts->pop ();
+  gimple *last_stmt = stmt_vinfo->stmt;
   tree oprnd0, oprnd1, lhs, var, var1, var2, vectype, type, stype, def, def2;
   gimple *pattern_stmt, *def_stmt;
   enum tree_code rhs_code;
-  stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
   vec_info *vinfo = stmt_vinfo->vinfo;
   enum vect_def_type dt;
   optab optab1, optab2;
@@ -1802,9 +1956,6 @@
       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);
@@ -1815,7 +1966,8 @@
       || !TYPE_UNSIGNED (type))
     return NULL;
 
-  if (!vect_is_simple_use (oprnd1, vinfo, &def_stmt, &dt))
+  stmt_vec_info def_stmt_info;
+  if (!vect_is_simple_use (oprnd1, vinfo, &dt, &def_stmt_info, &def_stmt))
     return NULL;
 
   if (dt != vect_internal_def
@@ -1862,25 +2014,11 @@
 	return NULL;
     }
 
-  *type_in = vectype;
   *type_out = vectype;
-  if (*type_in == NULL_TREE)
-    return NULL;
 
   if (dt == vect_external_def
-      && TREE_CODE (oprnd1) == SSA_NAME
-      && is_a <loop_vec_info> (vinfo))
-    {
-      struct loop *loop = as_a <loop_vec_info> (vinfo)->loop;
-      ext_def = loop_preheader_edge (loop);
-      if (!SSA_NAME_IS_DEFAULT_DEF (oprnd1))
-	{
-	  basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (oprnd1));
-	  if (bb == NULL
-	      || !dominated_by_p (CDI_DOMINATORS, ext_def->dest, bb))
-	    ext_def = NULL;
-	}
-    }
+      && TREE_CODE (oprnd1) == SSA_NAME)
+    ext_def = vect_get_external_def_edge (vinfo, oprnd1);
 
   def = NULL_TREE;
   scalar_int_mode mode = SCALAR_INT_TYPE_MODE (type);
@@ -1896,7 +2034,6 @@
 	def = rhs1;
     }
 
-  STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo) = NULL;
   if (def == NULL_TREE)
     {
       def = vect_recog_temp_ssa_var (type, NULL);
@@ -1925,7 +2062,6 @@
   else
     {
       tree vecstype = get_vectype_for_scalar_type (stype);
-      stmt_vec_info def_stmt_vinfo;
 
       if (vecstype == NULL_TREE)
 	return NULL;
@@ -1938,12 +2074,7 @@
 	  gcc_assert (!new_bb);
 	}
       else
-	{
-	  def_stmt_vinfo = new_stmt_vec_info (def_stmt, vinfo);
-	  set_vinfo_for_stmt (def_stmt, def_stmt_vinfo);
-	  STMT_VINFO_VECTYPE (def_stmt_vinfo) = vecstype;
-	  append_pattern_def_seq (stmt_vinfo, def_stmt);
-	}
+	append_pattern_def_seq (stmt_vinfo, def_stmt, vecstype);
 
       def2 = vect_recog_temp_ssa_var (stype, NULL);
       tree mask = build_int_cst (stype, GET_MODE_PRECISION (smode) - 1);
@@ -1956,12 +2087,7 @@
 	  gcc_assert (!new_bb);
 	}
       else
-	{
-	  def_stmt_vinfo = new_stmt_vec_info (def_stmt, vinfo);
-	  set_vinfo_for_stmt (def_stmt, def_stmt_vinfo);
-	  STMT_VINFO_VECTYPE (def_stmt_vinfo) = vecstype;
-	  append_pattern_def_seq (stmt_vinfo, def_stmt);
-	}
+	append_pattern_def_seq (stmt_vinfo, def_stmt, vecstype);
     }
 
   var1 = vect_recog_temp_ssa_var (type, NULL);
@@ -1977,18 +2103,12 @@
   append_pattern_def_seq (stmt_vinfo, def_stmt);
 
   /* Pattern detected.  */
-  if (dump_enabled_p ())
-    dump_printf_loc (MSG_NOTE, vect_location,
-		     "vect_recog_rotate_pattern: detected:\n");
+  vect_pattern_detected ("vect_recog_rotate_pattern", last_stmt);
 
   /* Pattern supported.  Create a stmt to be used to replace the pattern.  */
   var = vect_recog_temp_ssa_var (type, NULL);
   pattern_stmt = gimple_build_assign (var, BIT_IOR_EXPR, var1, var2);
 
-  if (dump_enabled_p ())
-    dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt, 0);
-
-  stmts->safe_push (last_stmt);
   return pattern_stmt;
 }
 
@@ -2017,7 +2137,7 @@
 
   Input/Output:
 
-  * STMTS: Contains a stmt from which the pattern search begins,
+  * STMT_VINFO: The stmt from which the pattern search begins,
     i.e. the shift/rotate stmt.  The original stmt (S3) is replaced
     with a shift/rotate which has same type on both operands, in the
     second case just b_T op c_T, in the first case with added cast
@@ -2025,24 +2145,20 @@
 
   Output:
 
-  * TYPE_IN: The type of the input arguments to the pattern.
-
   * TYPE_OUT: The type of the output of this pattern.
 
   * Return value: A new stmt that will be used to replace the shift/rotate
     S3 stmt.  */
 
 static gimple *
-vect_recog_vector_vector_shift_pattern (vec<gimple *> *stmts,
-					tree *type_in, tree *type_out)
+vect_recog_vector_vector_shift_pattern (stmt_vec_info stmt_vinfo,
+					tree *type_out)
 {
-  gimple *last_stmt = stmts->pop ();
+  gimple *last_stmt = stmt_vinfo->stmt;
   tree oprnd0, oprnd1, lhs, var;
-  gimple *pattern_stmt, *def_stmt;
+  gimple *pattern_stmt;
   enum tree_code rhs_code;
-  stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
   vec_info *vinfo = stmt_vinfo->vinfo;
-  enum vect_def_type dt;
 
   if (!is_gimple_assign (last_stmt))
     return NULL;
@@ -2059,9 +2175,6 @@
       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);
@@ -2073,20 +2186,17 @@
 	 != TYPE_PRECISION (TREE_TYPE (oprnd0)))
     return NULL;
 
-  if (!vect_is_simple_use (oprnd1, vinfo, &def_stmt, &dt))
-    return NULL;
-
-  if (dt != vect_internal_def)
+  stmt_vec_info def_vinfo = vect_get_internal_def (vinfo, oprnd1);
+  if (!def_vinfo)
     return NULL;
 
-  *type_in = get_vectype_for_scalar_type (TREE_TYPE (oprnd0));
-  *type_out = *type_in;
-  if (*type_in == NULL_TREE)
+  *type_out = get_vectype_for_scalar_type (TREE_TYPE (oprnd0));
+  if (*type_out == NULL_TREE)
     return NULL;
 
   tree def = NULL_TREE;
-  stmt_vec_info def_vinfo = vinfo_for_stmt (def_stmt);
-  if (!STMT_VINFO_IN_PATTERN_P (def_vinfo) && gimple_assign_cast_p (def_stmt))
+  gassign *def_stmt = dyn_cast <gassign *> (def_vinfo->stmt);
+  if (def_stmt && gimple_assign_cast_p (def_stmt))
     {
       tree rhs1 = gimple_assign_rhs1 (def_stmt);
       if (TYPE_MODE (TREE_TYPE (rhs1)) == TYPE_MODE (TREE_TYPE (oprnd0))
@@ -2103,7 +2213,8 @@
 				       TYPE_PRECISION (TREE_TYPE (oprnd1)));
 	      def = vect_recog_temp_ssa_var (TREE_TYPE (rhs1), NULL);
 	      def_stmt = gimple_build_assign (def, BIT_AND_EXPR, rhs1, mask);
-	      new_pattern_def_seq (stmt_vinfo, def_stmt);
+	      tree vecstype = get_vectype_for_scalar_type (TREE_TYPE (rhs1));
+	      append_pattern_def_seq (stmt_vinfo, def_stmt, vecstype);
 	    }
 	}
     }
@@ -2112,22 +2223,16 @@
     {
       def = vect_recog_temp_ssa_var (TREE_TYPE (oprnd0), NULL);
       def_stmt = gimple_build_assign (def, NOP_EXPR, oprnd1);
-      new_pattern_def_seq (stmt_vinfo, def_stmt);
+      append_pattern_def_seq (stmt_vinfo, def_stmt);
     }
 
   /* Pattern detected.  */
-  if (dump_enabled_p ())
-    dump_printf_loc (MSG_NOTE, vect_location,
-                     "vect_recog_vector_vector_shift_pattern: detected:\n");
+  vect_pattern_detected ("vect_recog_vector_vector_shift_pattern", last_stmt);
 
   /* Pattern supported.  Create a stmt to be used to replace the pattern.  */
   var = vect_recog_temp_ssa_var (TREE_TYPE (oprnd0), NULL);
   pattern_stmt = gimple_build_assign (var, rhs_code, oprnd0, def);
 
-  if (dump_enabled_p ())
-    dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt, 0);
-
-  stmts->safe_push (last_stmt);
   return pattern_stmt;
 }
 
@@ -2312,7 +2417,6 @@
   tree accumulator;
 
   /* Clear out the sequence of statements so we can populate it below.  */
-  STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo) = NULL;
   gimple *stmt = NULL;
 
   if (cast_to_unsigned_p)
@@ -2436,26 +2540,22 @@
 
    Input/Output:
 
-   STMTS: Contains a stmt from which the pattern search begins,
+   STMT_VINFO: The stmt from which the pattern search begins,
    i.e. the mult stmt.
 
  Output:
 
-  * TYPE_IN: The type of the input arguments to the pattern.
-
   * TYPE_OUT: The type of the output of this pattern.
 
   * Return value: A new stmt that will be used to replace
     the multiplication.  */
 
 static gimple *
-vect_recog_mult_pattern (vec<gimple *> *stmts,
-			 tree *type_in, tree *type_out)
+vect_recog_mult_pattern (stmt_vec_info stmt_vinfo, tree *type_out)
 {
-  gimple *last_stmt = stmts->pop ();
+  gimple *last_stmt = stmt_vinfo->stmt;
   tree oprnd0, oprnd1, vectype, itype;
   gimple *pattern_stmt;
-  stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
 
   if (!is_gimple_assign (last_stmt))
     return NULL;
@@ -2493,16 +2593,8 @@
     return NULL;
 
   /* Pattern detected.  */
-  if (dump_enabled_p ())
-    dump_printf_loc (MSG_NOTE, vect_location,
-		     "vect_recog_mult_pattern: detected:\n");
-
-  if (dump_enabled_p ())
-    dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM,
-			  pattern_stmt,0);
-
-  stmts->safe_push (last_stmt);
-  *type_in = vectype;
+  vect_pattern_detected ("vect_recog_mult_pattern", last_stmt);
+
   *type_out = vectype;
 
   return pattern_stmt;
@@ -2523,7 +2615,7 @@
 
   Input/Output:
 
-  * STMTS: Contains a stmt from which the pattern search begins,
+  * STMT_VINFO: The stmt from which the pattern search begins,
     i.e. the division stmt.  S1 is replaced by if N is a power
     of two constant and type is signed:
   S3  y_t = b_t < 0 ? N - 1 : 0;
@@ -2541,27 +2633,21 @@
 
   Output:
 
-  * TYPE_IN: The type of the input arguments to the pattern.
-
   * TYPE_OUT: The type of the output of this pattern.
 
   * Return value: A new stmt that will be used to replace the division
     S1 or modulo S4 stmt.  */
 
 static gimple *
-vect_recog_divmod_pattern (vec<gimple *> *stmts,
-			   tree *type_in, tree *type_out)
+vect_recog_divmod_pattern (stmt_vec_info stmt_vinfo, tree *type_out)
 {
-  gimple *last_stmt = stmts->pop ();
+  gimple *last_stmt = stmt_vinfo->stmt;
   tree oprnd0, oprnd1, vectype, itype, cond;
   gimple *pattern_stmt, *def_stmt;
   enum tree_code rhs_code;
-  stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
-  vec_info *vinfo = stmt_vinfo->vinfo;
   optab optab;
   tree q;
   int dummy_int, prec;
-  stmt_vec_info def_stmt_vinfo;
 
   if (!is_gimple_assign (last_stmt))
     return NULL;
@@ -2570,15 +2656,13 @@
   switch (rhs_code)
     {
     case TRUNC_DIV_EXPR:
+    case EXACT_DIV_EXPR:
     case TRUNC_MOD_EXPR:
       break;
     default:
       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);
@@ -2593,15 +2677,19 @@
   if (vectype == NULL_TREE)
     return NULL;
 
-  /* If the target can handle vectorized division or modulo natively,
-     don't attempt to optimize this.  */
-  optab = optab_for_tree_code (rhs_code, vectype, optab_default);
-  if (optab != unknown_optab)
+  if (optimize_bb_for_size_p (gimple_bb (last_stmt)))
     {
-      machine_mode vec_mode = TYPE_MODE (vectype);
-      int icode = (int) optab_handler (optab, vec_mode);
-      if (icode != CODE_FOR_nothing)
-	return NULL;
+      /* If the target can handle vectorized division or modulo natively,
+	 don't attempt to optimize this, since native division is likely
+	 to give smaller code.  */
+      optab = optab_for_tree_code (rhs_code, vectype, optab_default);
+      if (optab != unknown_optab)
+	{
+	  machine_mode vec_mode = TYPE_MODE (vectype);
+	  int icode = (int) optab_handler (optab, vec_mode);
+	  if (icode != CODE_FOR_nothing)
+	    return NULL;
+	}
     }
 
   prec = TYPE_PRECISION (itype);
@@ -2611,13 +2699,12 @@
 	return NULL;
 
       /* Pattern detected.  */
-      if (dump_enabled_p ())
-        dump_printf_loc (MSG_NOTE, vect_location,
-                         "vect_recog_divmod_pattern: detected:\n");
+      vect_pattern_detected ("vect_recog_divmod_pattern", last_stmt);
 
       cond = build2 (LT_EXPR, boolean_type_node, oprnd0,
 		     build_int_cst (itype, 0));
-      if (rhs_code == TRUNC_DIV_EXPR)
+      if (rhs_code == TRUNC_DIV_EXPR
+	  || rhs_code == EXACT_DIV_EXPR)
 	{
 	  tree var = vect_recog_temp_ssa_var (itype, NULL);
 	  tree shift;
@@ -2626,7 +2713,7 @@
 				   fold_build2 (MINUS_EXPR, itype, oprnd1,
 						build_int_cst (itype, 1)),
 				   build_int_cst (itype, 0));
-	  new_pattern_def_seq (stmt_vinfo, def_stmt);
+	  append_pattern_def_seq (stmt_vinfo, def_stmt);
 	  var = vect_recog_temp_ssa_var (itype, NULL);
 	  def_stmt
 	    = gimple_build_assign (var, PLUS_EXPR, oprnd0,
@@ -2641,7 +2728,6 @@
       else
 	{
 	  tree signmask;
-	  STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo) = NULL;
 	  if (compare_tree_int (oprnd1, 2) == 0)
 	    {
 	      signmask = vect_recog_temp_ssa_var (itype, NULL);
@@ -2663,18 +2749,12 @@
 	      def_stmt = gimple_build_assign (var, COND_EXPR, cond,
 					      build_int_cst (utype, -1),
 					      build_int_cst (utype, 0));
-	      def_stmt_vinfo = new_stmt_vec_info (def_stmt, vinfo);
-	      set_vinfo_for_stmt (def_stmt, def_stmt_vinfo);
-	      STMT_VINFO_VECTYPE (def_stmt_vinfo) = vecutype;
-	      append_pattern_def_seq (stmt_vinfo, def_stmt);
+	      append_pattern_def_seq (stmt_vinfo, def_stmt, vecutype);
 	      var = vect_recog_temp_ssa_var (utype, NULL);
 	      def_stmt = gimple_build_assign (var, RSHIFT_EXPR,
 					      gimple_assign_lhs (def_stmt),
 					      shift);
-	      def_stmt_vinfo = new_stmt_vec_info (def_stmt, vinfo);
-	      set_vinfo_for_stmt (def_stmt, def_stmt_vinfo);
-	      STMT_VINFO_VECTYPE (def_stmt_vinfo) = vecutype;
-	      append_pattern_def_seq (stmt_vinfo, def_stmt);
+	      append_pattern_def_seq (stmt_vinfo, def_stmt, vecutype);
 	      signmask = vect_recog_temp_ssa_var (itype, NULL);
 	      def_stmt
 		= gimple_build_assign (signmask, NOP_EXPR, var);
@@ -2697,13 +2777,6 @@
 				   signmask);
 	}
 
-      if (dump_enabled_p ())
-	dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt,
-                              0);
-
-      stmts->safe_push (last_stmt);
-
-      *type_in = vectype;
       *type_out = vectype;
       return pattern_stmt;
     }
@@ -2715,8 +2788,6 @@
   if (!can_mult_highpart_p (TYPE_MODE (vectype), TYPE_UNSIGNED (itype)))
     return NULL;
 
-  STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo) = NULL;
-
   if (TYPE_UNSIGNED (itype))
     {
       unsigned HOST_WIDE_INT mh, ml;
@@ -2951,16 +3022,8 @@
     }
 
   /* Pattern detected.  */
-  if (dump_enabled_p ())
-    {
-      dump_printf_loc (MSG_NOTE, vect_location,
-                       "vect_recog_divmod_pattern: detected: ");
-      dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
-    }
-
-  stmts->safe_push (last_stmt);
-
-  *type_in = vectype;
+  vect_pattern_detected ("vect_recog_divmod_pattern", last_stmt);
+
   *type_out = vectype;
   return pattern_stmt;
 }
@@ -2981,12 +3044,10 @@
 
    Input:
 
-   * LAST_STMT: A stmt from which the pattern search begins.
+   * STMT_VINFO: The stmt from which the pattern search begins.
 
    Output:
 
-   * TYPE_IN: The type of the input arguments to the pattern.
-
    * TYPE_OUT: The type of the output of this pattern.
 
    * Return value: A new stmt that will be used to replace the pattern.
@@ -2996,15 +3057,12 @@
 	a_T = (TYPE) a_it;  */
 
 static gimple *
-vect_recog_mixed_size_cond_pattern (vec<gimple *> *stmts, tree *type_in,
-				    tree *type_out)
+vect_recog_mixed_size_cond_pattern (stmt_vec_info stmt_vinfo, tree *type_out)
 {
-  gimple *last_stmt = (*stmts)[0];
+  gimple *last_stmt = stmt_vinfo->stmt;
   tree cond_expr, then_clause, else_clause;
-  stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt), def_stmt_info;
   tree type, vectype, comp_vectype, itype = NULL_TREE, vecitype;
   gimple *pattern_stmt, *def_stmt;
-  vec_info *vinfo = stmt_vinfo->vinfo;
   tree orig_type0 = NULL_TREE, orig_type1 = NULL_TREE;
   gimple *def_stmt0 = NULL, *def_stmt1 = NULL;
   bool promotion;
@@ -3036,11 +3094,11 @@
     return NULL;
 
   if ((TREE_CODE (then_clause) != INTEGER_CST
-       && !type_conversion_p (then_clause, last_stmt, false, &orig_type0,
-                              &def_stmt0, &promotion))
+       && !type_conversion_p (then_clause, stmt_vinfo, false, &orig_type0,
+			      &def_stmt0, &promotion))
       || (TREE_CODE (else_clause) != INTEGER_CST
-          && !type_conversion_p (else_clause, last_stmt, false, &orig_type1,
-                                 &def_stmt1, &promotion)))
+	  && !type_conversion_p (else_clause, stmt_vinfo, false, &orig_type1,
+				 &def_stmt1, &promotion)))
     return NULL;
 
   if (orig_type0 && orig_type1
@@ -3109,16 +3167,10 @@
   pattern_stmt = gimple_build_assign (vect_recog_temp_ssa_var (type, NULL),
 				      NOP_EXPR, gimple_assign_lhs (def_stmt));
 
-  new_pattern_def_seq (stmt_vinfo, def_stmt);
-  def_stmt_info = new_stmt_vec_info (def_stmt, vinfo);
-  set_vinfo_for_stmt (def_stmt, def_stmt_info);
-  STMT_VINFO_VECTYPE (def_stmt_info) = vecitype;
-  *type_in = vecitype;
+  append_pattern_def_seq (stmt_vinfo, def_stmt, vecitype);
   *type_out = vectype;
 
-  if (dump_enabled_p ())
-    dump_printf_loc (MSG_NOTE, vect_location,
-                     "vect_recog_mixed_size_cond_pattern: detected:\n");
+  vect_pattern_detected ("vect_recog_mixed_size_cond_pattern", last_stmt);
 
   return pattern_stmt;
 }
@@ -3133,18 +3185,15 @@
 static bool
 check_bool_pattern (tree var, vec_info *vinfo, hash_set<gimple *> &stmts)
 {
-  gimple *def_stmt;
-  enum vect_def_type dt;
   tree rhs1;
   enum tree_code rhs_code;
 
-  if (!vect_is_simple_use (var, vinfo, &def_stmt, &dt))
+  stmt_vec_info def_stmt_info = vect_get_internal_def (vinfo, var);
+  if (!def_stmt_info)
     return false;
 
-  if (dt != vect_internal_def)
-    return false;
-
-  if (!is_gimple_assign (def_stmt))
+  gassign *def_stmt = dyn_cast <gassign *> (def_stmt_info->stmt);
+  if (!def_stmt)
     return false;
 
   if (stmts.contains (def_stmt))
@@ -3186,7 +3235,7 @@
 
 	  /* If the comparison can throw, then is_gimple_condexpr will be
 	     false and we can't make a COND_EXPR/VEC_COND_EXPR out of it.  */
-	  if (stmt_could_throw_p (def_stmt))
+	  if (stmt_could_throw_p (cfun, def_stmt))
 	    return false;
 
 	  comp_vectype = get_vectype_for_scalar_type (TREE_TYPE (rhs1));
@@ -3234,10 +3283,8 @@
 {
   gimple *cast_stmt = gimple_build_assign (vect_recog_temp_ssa_var (type, NULL),
 					   NOP_EXPR, var);
-  stmt_vec_info patt_vinfo = new_stmt_vec_info (cast_stmt, stmt_info->vinfo);
-  set_vinfo_for_stmt (cast_stmt, patt_vinfo);
-  STMT_VINFO_VECTYPE (patt_vinfo) = get_vectype_for_scalar_type (type);
-  append_pattern_def_seq (stmt_info, cast_stmt);
+  append_pattern_def_seq (stmt_info, cast_stmt,
+			  get_vectype_for_scalar_type (type));
   return gimple_assign_lhs (cast_stmt);
 }
 
@@ -3388,8 +3435,8 @@
       gcc_assert (TREE_CODE_CLASS (rhs_code) == tcc_comparison);
       if (TREE_CODE (TREE_TYPE (rhs1)) != INTEGER_TYPE
 	  || !TYPE_UNSIGNED (TREE_TYPE (rhs1))
-	  || (TYPE_PRECISION (TREE_TYPE (rhs1))
-	      != GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs1)))))
+	  || maybe_ne (TYPE_PRECISION (TREE_TYPE (rhs1)),
+		       GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs1)))))
 	{
 	  scalar_mode mode = SCALAR_TYPE_MODE (TREE_TYPE (rhs1));
 	  itype
@@ -3411,13 +3458,8 @@
     }
 
   gimple_set_location (pattern_stmt, loc);
-  /* ???  Why does vect_mark_pattern_stmts set the vector type on all
-     pattern def seq stmts instead of just letting auto-detection do
-     its work?  */
-  stmt_vec_info patt_vinfo = new_stmt_vec_info (pattern_stmt, stmt_info->vinfo);
-  set_vinfo_for_stmt (pattern_stmt, patt_vinfo);
-  STMT_VINFO_VECTYPE (patt_vinfo) = get_vectype_for_scalar_type (itype);
-  append_pattern_def_seq (stmt_info, pattern_stmt);
+  append_pattern_def_seq (stmt_info, pattern_stmt,
+			  get_vectype_for_scalar_type (itype));
   defs.put (var, gimple_assign_lhs (pattern_stmt));
 }
 
@@ -3432,12 +3474,12 @@
 }
 
 /* Create pattern stmts for all stmts participating in the bool pattern
-   specified by BOOL_STMT_SET and its root STMT with the desired type
+   specified by BOOL_STMT_SET and its root STMT_INFO with the desired type
    OUT_TYPE.  Return the def of the pattern root.  */
 
 static tree
 adjust_bool_stmts (hash_set <gimple *> &bool_stmt_set,
-		   tree out_type, gimple *stmt)
+		   tree out_type, stmt_vec_info stmt_info)
 {
   /* Gather original stmts in the bool pattern in their order of appearance
      in the IL.  */
@@ -3451,11 +3493,11 @@
   hash_map <tree, tree> defs;
   for (unsigned i = 0; i < bool_stmts.length (); ++i)
     adjust_bool_pattern (gimple_assign_lhs (bool_stmts[i]),
-			 out_type, vinfo_for_stmt (stmt), defs);
+			 out_type, stmt_info, defs);
 
   /* Pop the last pattern seq stmt and install it as pattern root for STMT.  */
   gimple *pattern_stmt
-    = gimple_seq_last_stmt (STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (stmt)));
+    = gimple_seq_last_stmt (STMT_VINFO_PATTERN_DEF_SEQ (stmt_info));
   return gimple_assign_lhs (pattern_stmt);
 }
 
@@ -3465,25 +3507,19 @@
 search_type_for_mask_1 (tree var, vec_info *vinfo,
 			hash_map<gimple *, tree> &cache)
 {
-  gimple *def_stmt;
-  enum vect_def_type dt;
   tree rhs1;
   enum tree_code rhs_code;
   tree res = NULL_TREE, res2;
 
-  if (TREE_CODE (var) != SSA_NAME)
-    return NULL_TREE;
-
   if (!VECT_SCALAR_BOOLEAN_TYPE_P (TREE_TYPE (var)))
     return NULL_TREE;
 
-  if (!vect_is_simple_use (var, vinfo, &def_stmt, &dt))
+  stmt_vec_info def_stmt_info = vect_get_internal_def (vinfo, var);
+  if (!def_stmt_info)
     return NULL_TREE;
 
-  if (dt != vect_internal_def)
-    return NULL_TREE;
-
-  if (!is_gimple_assign (def_stmt))
+  gassign *def_stmt = dyn_cast <gassign *> (def_stmt_info->stmt);
+  if (!def_stmt)
     return NULL_TREE;
 
   tree *c = cache.get (def_stmt);
@@ -3591,14 +3627,12 @@
 
    Input:
 
-   * LAST_STMT: A stmt at the end from which the pattern
-		search begins, i.e. cast of a bool to
-		an integer type.
+   * STMT_VINFO: The stmt at the end from which the pattern
+		 search begins, i.e. cast of a bool to
+		 an integer type.
 
    Output:
 
-   * TYPE_IN: The type of the input arguments to the pattern.
-
    * TYPE_OUT: The type of the output of this pattern.
 
    * Return value: A new stmt that will be used to replace the pattern.
@@ -3618,14 +3652,11 @@
 	but the above is more efficient.  */
 
 static gimple *
-vect_recog_bool_pattern (vec<gimple *> *stmts, tree *type_in,
-			 tree *type_out)
+vect_recog_bool_pattern (stmt_vec_info stmt_vinfo, tree *type_out)
 {
-  gimple *last_stmt = stmts->pop ();
+  gimple *last_stmt = stmt_vinfo->stmt;
   enum tree_code rhs_code;
   tree var, lhs, rhs, vectype;
-  stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
-  stmt_vec_info new_stmt_info;
   vec_info *vinfo = stmt_vinfo->vinfo;
   gimple *pattern_stmt;
 
@@ -3652,7 +3683,7 @@
 
       if (check_bool_pattern (var, vinfo, bool_stmts))
 	{
-	  rhs = adjust_bool_stmts (bool_stmts, TREE_TYPE (lhs), last_stmt);
+	  rhs = adjust_bool_stmts (bool_stmts, TREE_TYPE (lhs), stmt_vinfo);
 	  lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL);
 	  if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
 	    pattern_stmt = gimple_build_assign (lhs, SSA_NAME, rhs);
@@ -3684,10 +3715,7 @@
 	  if (!useless_type_conversion_p (type, TREE_TYPE (lhs)))
 	    {
 	      tree new_vectype = get_vectype_for_scalar_type (type);
-	      new_stmt_info = new_stmt_vec_info (pattern_stmt, vinfo);
-	      set_vinfo_for_stmt (pattern_stmt, new_stmt_info);
-	      STMT_VINFO_VECTYPE (new_stmt_info) = new_vectype;
-	      new_pattern_def_seq (stmt_vinfo, pattern_stmt);
+	      append_pattern_def_seq (stmt_vinfo, pattern_stmt, new_vectype);
 
 	      lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL);
 	      pattern_stmt = gimple_build_assign (lhs, CONVERT_EXPR, tmp);
@@ -3695,11 +3723,7 @@
 	}
 
       *type_out = vectype;
-      *type_in = vectype;
-      stmts->safe_push (last_stmt);
-      if (dump_enabled_p ())
-	dump_printf_loc (MSG_NOTE, vect_location,
-                         "vect_recog_bool_pattern: detected:\n");
+      vect_pattern_detected ("vect_recog_bool_pattern", last_stmt);
 
       return pattern_stmt;
     }
@@ -3714,8 +3738,9 @@
          vectorized matches the vector type of the result in
 	 size and number of elements.  */
       unsigned prec
-	= wi::udiv_trunc (wi::to_wide (TYPE_SIZE (vectype)),
-			  TYPE_VECTOR_SUBPARTS (vectype)).to_uhwi ();
+	= vector_element_size (tree_to_poly_uint64 (TYPE_SIZE (vectype)),
+			       TYPE_VECTOR_SUBPARTS (vectype));
+
       tree type
 	= build_nonstandard_integer_type (prec,
 					  TYPE_UNSIGNED (TREE_TYPE (var)));
@@ -3725,7 +3750,7 @@
       if (!check_bool_pattern (var, vinfo, bool_stmts))
 	return NULL;
 
-      rhs = adjust_bool_stmts (bool_stmts, type, last_stmt);
+      rhs = adjust_bool_stmts (bool_stmts, type, stmt_vinfo);
 
       lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL);
       pattern_stmt 
@@ -3735,11 +3760,7 @@
 				 gimple_assign_rhs2 (last_stmt),
 				 gimple_assign_rhs3 (last_stmt));
       *type_out = vectype;
-      *type_in = vectype;
-      stmts->safe_push (last_stmt);
-      if (dump_enabled_p ())
-	dump_printf_loc (MSG_NOTE, vect_location,
-                         "vect_recog_bool_pattern: detected:\n");
+      vect_pattern_detected ("vect_recog_bool_pattern", last_stmt);
 
       return pattern_stmt;
     }
@@ -3753,7 +3774,7 @@
 	return NULL;
 
       if (check_bool_pattern (var, vinfo, bool_stmts))
-	rhs = adjust_bool_stmts (bool_stmts, TREE_TYPE (vectype), last_stmt);
+	rhs = adjust_bool_stmts (bool_stmts, TREE_TYPE (vectype), stmt_vinfo);
       else
 	{
 	  tree type = search_type_for_mask (var, vinfo);
@@ -3771,11 +3792,7 @@
 
 	  rhs = vect_recog_temp_ssa_var (type, NULL);
 	  pattern_stmt = gimple_build_assign (rhs, COND_EXPR, var, cst1, cst0);
-
-	  pattern_stmt_info = new_stmt_vec_info (pattern_stmt, vinfo);
-	  set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info);
-	  STMT_VINFO_VECTYPE (pattern_stmt_info) = new_vectype;
-	  append_pattern_def_seq (stmt_vinfo, pattern_stmt);
+	  append_pattern_def_seq (stmt_vinfo, pattern_stmt, new_vectype);
 	}
 
       lhs = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (vectype), lhs);
@@ -3787,19 +3804,11 @@
 	  rhs = rhs2;
 	}
       pattern_stmt = gimple_build_assign (lhs, SSA_NAME, rhs);
-      pattern_stmt_info = new_stmt_vec_info (pattern_stmt, vinfo);
-      set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info);
-      STMT_VINFO_DATA_REF (pattern_stmt_info)
-	= STMT_VINFO_DATA_REF (stmt_vinfo);
-      STMT_VINFO_DR_WRT_VEC_LOOP (pattern_stmt_info)
-	= STMT_VINFO_DR_WRT_VEC_LOOP (stmt_vinfo);
-      DR_STMT (STMT_VINFO_DATA_REF (stmt_vinfo)) = pattern_stmt;
+      pattern_stmt_info = vinfo->add_stmt (pattern_stmt);
+      vinfo->move_dr (pattern_stmt_info, stmt_vinfo);
       *type_out = vectype;
-      *type_in = vectype;
-      stmts->safe_push (last_stmt);
-      if (dump_enabled_p ())
-	dump_printf_loc (MSG_NOTE, vect_location,
-                         "vect_recog_bool_pattern: detected:\n");
+      vect_pattern_detected ("vect_recog_bool_pattern", last_stmt);
+
       return pattern_stmt;
     }
   else
@@ -3815,20 +3824,15 @@
    Return converted mask.  */
 
 static tree
-build_mask_conversion (tree mask, tree vectype, stmt_vec_info stmt_vinfo,
-		       vec_info *vinfo)
+build_mask_conversion (tree mask, tree vectype, stmt_vec_info stmt_vinfo)
 {
   gimple *stmt;
   tree masktype, tmp;
-  stmt_vec_info new_stmt_info;
 
   masktype = build_same_sized_truth_vector_type (vectype);
   tmp = vect_recog_temp_ssa_var (TREE_TYPE (masktype), NULL);
   stmt = gimple_build_assign (tmp, CONVERT_EXPR, mask);
-  new_stmt_info = new_stmt_vec_info (stmt, vinfo);
-  set_vinfo_for_stmt (stmt, new_stmt_info);
-  STMT_VINFO_VECTYPE (new_stmt_info) = masktype;
-  append_pattern_def_seq (stmt_vinfo, stmt);
+  append_pattern_def_seq (stmt_vinfo, stmt, masktype);
 
   return tmp;
 }
@@ -3860,83 +3864,74 @@
    S4'  c_1' = m_3'' ? c_2 : c_3;  */
 
 static gimple *
-vect_recog_mask_conversion_pattern (vec<gimple *> *stmts, tree *type_in,
-				    tree *type_out)
+vect_recog_mask_conversion_pattern (stmt_vec_info stmt_vinfo, tree *type_out)
 {
-  gimple *last_stmt = stmts->pop ();
+  gimple *last_stmt = stmt_vinfo->stmt;
   enum tree_code rhs_code;
   tree lhs = NULL_TREE, rhs1, rhs2, tmp, rhs1_type, rhs2_type;
   tree vectype1, vectype2;
-  stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
   stmt_vec_info pattern_stmt_info;
   vec_info *vinfo = stmt_vinfo->vinfo;
 
   /* Check for MASK_LOAD ans MASK_STORE calls requiring mask conversion.  */
   if (is_gimple_call (last_stmt)
-      && gimple_call_internal_p (last_stmt)
-      && (gimple_call_internal_fn (last_stmt) == IFN_MASK_STORE
-	  || gimple_call_internal_fn (last_stmt) == IFN_MASK_LOAD))
+      && gimple_call_internal_p (last_stmt))
     {
       gcall *pattern_stmt;
-      bool load = (gimple_call_internal_fn (last_stmt) == IFN_MASK_LOAD);
-
-      if (load)
+
+      internal_fn ifn = gimple_call_internal_fn (last_stmt);
+      int mask_argno = internal_fn_mask_index (ifn);
+      if (mask_argno < 0)
+	return NULL;
+
+      bool store_p = internal_store_fn_p (ifn);
+      if (store_p)
+	{
+	  int rhs_index = internal_fn_stored_value_index (ifn);
+	  tree rhs = gimple_call_arg (last_stmt, rhs_index);
+	  vectype1 = get_vectype_for_scalar_type (TREE_TYPE (rhs));
+	}
+      else
 	{
 	  lhs = gimple_call_lhs (last_stmt);
 	  vectype1 = get_vectype_for_scalar_type (TREE_TYPE (lhs));
 	}
-      else
-	{
-	  rhs2 = gimple_call_arg (last_stmt, 3);
-	  vectype1 = get_vectype_for_scalar_type (TREE_TYPE (rhs2));
-	}
-
-      rhs1 = gimple_call_arg (last_stmt, 2);
-      rhs1_type = search_type_for_mask (rhs1, vinfo);
-      if (!rhs1_type)
+
+      tree mask_arg = gimple_call_arg (last_stmt, mask_argno);
+      tree mask_arg_type = search_type_for_mask (mask_arg, vinfo);
+      if (!mask_arg_type)
 	return NULL;
-      vectype2 = get_mask_type_for_scalar_type (rhs1_type);
+      vectype2 = get_mask_type_for_scalar_type (mask_arg_type);
 
       if (!vectype1 || !vectype2
-	  || TYPE_VECTOR_SUBPARTS (vectype1) == TYPE_VECTOR_SUBPARTS (vectype2))
+	  || known_eq (TYPE_VECTOR_SUBPARTS (vectype1),
+		       TYPE_VECTOR_SUBPARTS (vectype2)))
 	return NULL;
 
-      tmp = build_mask_conversion (rhs1, vectype1, stmt_vinfo, vinfo);
-
-      if (load)
+      tmp = build_mask_conversion (mask_arg, vectype1, stmt_vinfo);
+
+      auto_vec<tree, 8> args;
+      unsigned int nargs = gimple_call_num_args (last_stmt);
+      args.safe_grow (nargs);
+      for (unsigned int i = 0; i < nargs; ++i)
+	args[i] = ((int) i == mask_argno
+		   ? tmp
+		   : gimple_call_arg (last_stmt, i));
+      pattern_stmt = gimple_build_call_internal_vec (ifn, args);
+
+      if (!store_p)
 	{
 	  lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL);
-	  pattern_stmt
-	    = gimple_build_call_internal (IFN_MASK_LOAD, 3,
-					  gimple_call_arg (last_stmt, 0),
-					  gimple_call_arg (last_stmt, 1),
-					  tmp);
 	  gimple_call_set_lhs (pattern_stmt, lhs);
 	}
-      else
-	  pattern_stmt
-	    = gimple_build_call_internal (IFN_MASK_STORE, 4,
-					  gimple_call_arg (last_stmt, 0),
-					  gimple_call_arg (last_stmt, 1),
-					  tmp,
-					  gimple_call_arg (last_stmt, 3));
-
       gimple_call_set_nothrow (pattern_stmt, true);
 
-      pattern_stmt_info = new_stmt_vec_info (pattern_stmt, vinfo);
-      set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info);
-      STMT_VINFO_DATA_REF (pattern_stmt_info)
-	= STMT_VINFO_DATA_REF (stmt_vinfo);
-      STMT_VINFO_DR_WRT_VEC_LOOP (pattern_stmt_info)
-	= STMT_VINFO_DR_WRT_VEC_LOOP (stmt_vinfo);
-      DR_STMT (STMT_VINFO_DATA_REF (stmt_vinfo)) = pattern_stmt;
+      pattern_stmt_info = vinfo->add_stmt (pattern_stmt);
+      if (STMT_VINFO_DATA_REF (stmt_vinfo))
+	vinfo->move_dr (pattern_stmt_info, stmt_vinfo);
 
       *type_out = vectype1;
-      *type_in = vectype1;
-      stmts->safe_push (last_stmt);
-      if (dump_enabled_p ())
-	dump_printf_loc (MSG_NOTE, vect_location,
-                         "vect_recog_mask_conversion_pattern: detected:\n");
+      vect_pattern_detected ("vect_recog_mask_conversion_pattern", last_stmt);
 
       return pattern_stmt;
     }
@@ -3952,11 +3947,6 @@
   /* 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)
@@ -3966,16 +3956,69 @@
 	    return NULL;
 	}
       else if (COMPARISON_CLASS_P (rhs1))
-	rhs1_type = TREE_TYPE (TREE_OPERAND (rhs1, 0));
+	{
+	  /* Check whether we're comparing scalar booleans and (if so)
+	     whether a better mask type exists than the mask associated
+	     with boolean-sized elements.  This avoids unnecessary packs
+	     and unpacks if the booleans are set from comparisons of
+	     wider types.  E.g. in:
+
+	       int x1, x2, x3, x4, y1, y1;
+	       ...
+	       bool b1 = (x1 == x2);
+	       bool b2 = (x3 == x4);
+	       ... = b1 == b2 ? y1 : y2;
+
+	     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);
+	  if (!rhs1_type)
+	    rhs1_type = TREE_TYPE (TREE_OPERAND (rhs1, 0));
+	}
       else
 	return NULL;
 
       vectype2 = get_mask_type_for_scalar_type (rhs1_type);
 
-      if (!vectype1 || !vectype2
-	  || TYPE_VECTOR_SUBPARTS (vectype1) == TYPE_VECTOR_SUBPARTS (vectype2))
+      if (!vectype1 || !vectype2)
+	return NULL;
+
+      /* Continue if a conversion is needed.  Also continue if we have
+	 a comparison whose vector type would normally be different from
+	 VECTYPE2 when considered in isolation.  In that case we'll
+	 replace the comparison with an SSA name (so that we can record
+	 its vector type) and behave as though the comparison was an SSA
+	 name from the outset.  */
+      if (known_eq (TYPE_VECTOR_SUBPARTS (vectype1),
+		    TYPE_VECTOR_SUBPARTS (vectype2))
+	  && (TREE_CODE (rhs1) == SSA_NAME
+	      || rhs1_type == TREE_TYPE (TREE_OPERAND (rhs1, 0))))
 	return NULL;
 
+      /* If rhs1 is invariant and we can promote it leave the COND_EXPR
+         in place, we can handle it in vectorizable_condition.  This avoids
+	 unnecessary promotion stmts and increased vectorization factor.  */
+      if (COMPARISON_CLASS_P (rhs1)
+	  && INTEGRAL_TYPE_P (rhs1_type)
+	  && known_le (TYPE_VECTOR_SUBPARTS (vectype1),
+		       TYPE_VECTOR_SUBPARTS (vectype2)))
+	{
+	  enum vect_def_type dt;
+	  if (vect_is_simple_use (TREE_OPERAND (rhs1, 0), vinfo, &dt)
+	      && dt == vect_external_def
+	      && vect_is_simple_use (TREE_OPERAND (rhs1, 1), vinfo, &dt)
+	      && (dt == vect_external_def
+		  || dt == vect_constant_def))
+	    {
+	      tree wide_scalar_type = build_nonstandard_integer_type
+		(tree_to_uhwi (TYPE_SIZE (TREE_TYPE (vectype1))),
+		 TYPE_UNSIGNED (rhs1_type));
+	      tree vectype3 = get_vectype_for_scalar_type (wide_scalar_type);
+	      if (expand_vec_cond_expr_p (vectype1, vectype3, TREE_CODE (rhs1)))
+		return NULL;
+	    }
+	}
+
       /* If rhs1 is a comparison we need to move it into a
 	 separate statement.  */
       if (TREE_CODE (rhs1) != SSA_NAME)
@@ -3983,14 +4026,14 @@
 	  tmp = vect_recog_temp_ssa_var (TREE_TYPE (rhs1), NULL);
 	  pattern_stmt = gimple_build_assign (tmp, rhs1);
 	  rhs1 = tmp;
-
-	  pattern_stmt_info = new_stmt_vec_info (pattern_stmt, vinfo);
-	  set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info);
-	  STMT_VINFO_VECTYPE (pattern_stmt_info) = vectype2;
-	  append_pattern_def_seq (stmt_vinfo, pattern_stmt);
+	  append_pattern_def_seq (stmt_vinfo, pattern_stmt, vectype2);
 	}
 
-      tmp = build_mask_conversion (rhs1, vectype1, stmt_vinfo, vinfo);
+      if (maybe_ne (TYPE_VECTOR_SUBPARTS (vectype1),
+		    TYPE_VECTOR_SUBPARTS (vectype2)))
+	tmp = build_mask_conversion (rhs1, vectype1, stmt_vinfo);
+      else
+	tmp = rhs1;
 
       lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL);
       pattern_stmt = gimple_build_assign (lhs, COND_EXPR, tmp,
@@ -3998,11 +4041,7 @@
 					  gimple_assign_rhs3 (last_stmt));
 
       *type_out = vectype1;
-      *type_in = vectype1;
-      stmts->safe_push (last_stmt);
-      if (dump_enabled_p ())
-	dump_printf_loc (MSG_NOTE, vect_location,
-                         "vect_recog_mask_conversion_pattern: detected:\n");
+      vect_pattern_detected ("vect_recog_mask_conversion_pattern", last_stmt);
 
       return pattern_stmt;
     }
@@ -4032,77 +4071,672 @@
       vectype1 = get_mask_type_for_scalar_type (rhs1_type);
       if (!vectype1)
 	return NULL;
-      rhs2 = build_mask_conversion (rhs2, vectype1, stmt_vinfo, vinfo);
+      rhs2 = build_mask_conversion (rhs2, vectype1, stmt_vinfo);
     }
   else
     {
       vectype1 = get_mask_type_for_scalar_type (rhs2_type);
       if (!vectype1)
 	return NULL;
-      rhs1 = build_mask_conversion (rhs1, vectype1, stmt_vinfo, vinfo);
+      rhs1 = build_mask_conversion (rhs1, vectype1, stmt_vinfo);
     }
 
   lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL);
   pattern_stmt = gimple_build_assign (lhs, rhs_code, rhs1, rhs2);
 
   *type_out = vectype1;
-  *type_in = vectype1;
-  stmts->safe_push (last_stmt);
-  if (dump_enabled_p ())
-    dump_printf_loc (MSG_NOTE, vect_location,
-		     "vect_recog_mask_conversion_pattern: detected:\n");
+  vect_pattern_detected ("vect_recog_mask_conversion_pattern", last_stmt);
+
+  return pattern_stmt;
+}
+
+/* STMT_INFO is a load or store.  If the load or store is conditional, return
+   the boolean condition under which it occurs, otherwise return null.  */
+
+static tree
+vect_get_load_store_mask (stmt_vec_info stmt_info)
+{
+  if (gassign *def_assign = dyn_cast <gassign *> (stmt_info->stmt))
+    {
+      gcc_assert (gimple_assign_single_p (def_assign));
+      return NULL_TREE;
+    }
+
+  if (gcall *def_call = dyn_cast <gcall *> (stmt_info->stmt))
+    {
+      internal_fn ifn = gimple_call_internal_fn (def_call);
+      int mask_index = internal_fn_mask_index (ifn);
+      return gimple_call_arg (def_call, mask_index);
+    }
+
+  gcc_unreachable ();
+}
+
+/* Return the scalar offset type that an internal gather/scatter function
+   should use.  GS_INFO describes the gather/scatter operation.  */
+
+static tree
+vect_get_gather_scatter_offset_type (gather_scatter_info *gs_info)
+{
+  tree offset_type = TREE_TYPE (gs_info->offset);
+  unsigned int element_bits = tree_to_uhwi (TYPE_SIZE (gs_info->element_type));
+
+  /* Enforced by vect_check_gather_scatter.  */
+  unsigned int offset_bits = TYPE_PRECISION (offset_type);
+  gcc_assert (element_bits >= offset_bits);
+
+  /* If the offset is narrower than the elements, extend it according
+     to its sign.  */
+  if (element_bits > offset_bits)
+    return build_nonstandard_integer_type (element_bits,
+					   TYPE_UNSIGNED (offset_type));
+
+  return offset_type;
+}
+
+/* Return MASK if MASK is suitable for masking an operation on vectors
+   of type VECTYPE, otherwise convert it into such a form and return
+   the result.  Associate any conversion statements with STMT_INFO's
+   pattern.  */
+
+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);
+  if (mask_type)
+    {
+      tree mask_vectype = get_mask_type_for_scalar_type (mask_type);
+      if (mask_vectype
+	  && maybe_ne (TYPE_VECTOR_SUBPARTS (vectype),
+		       TYPE_VECTOR_SUBPARTS (mask_vectype)))
+	mask = build_mask_conversion (mask, vectype, stmt_info);
+    }
+  return mask;
+}
+
+/* Return the equivalent of:
+
+     fold_convert (TYPE, VALUE)
+
+   with the expectation that the operation will be vectorized.
+   If new statements are needed, add them as pattern statements
+   to STMT_INFO.  */
+
+static tree
+vect_add_conversion_to_pattern (tree type, tree value, stmt_vec_info stmt_info)
+{
+  if (useless_type_conversion_p (type, TREE_TYPE (value)))
+    return value;
+
+  tree new_value = vect_recog_temp_ssa_var (type, NULL);
+  gassign *conversion = gimple_build_assign (new_value, CONVERT_EXPR, value);
+  append_pattern_def_seq (stmt_info, conversion,
+			  get_vectype_for_scalar_type (type));
+  return new_value;
+}
+
+/* Try to convert STMT_INFO into a call to a gather load or scatter store
+   internal function.  Return the final statement on success and set
+   *TYPE_OUT to the vector type being loaded or stored.
+
+   This function only handles gathers and scatters that were recognized
+   as such from the outset (indicated by STMT_VINFO_GATHER_SCATTER_P).  */
+
+static gimple *
+vect_recog_gather_scatter_pattern (stmt_vec_info stmt_info, tree *type_out)
+{
+  /* Currently we only support this for loop vectorization.  */
+  loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (stmt_info->vinfo);
+  if (!loop_vinfo)
+    return NULL;
+
+  /* Make sure that we're looking at a gather load or scatter store.  */
+  data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
+  if (!dr || !STMT_VINFO_GATHER_SCATTER_P (stmt_info))
+    return NULL;
+
+  /* Get the boolean that controls whether the load or store happens.
+     This is null if the operation is unconditional.  */
+  tree mask = vect_get_load_store_mask (stmt_info);
+
+  /* Make sure that the target supports an appropriate internal
+     function for the gather/scatter operation.  */
+  gather_scatter_info gs_info;
+  if (!vect_check_gather_scatter (stmt_info, loop_vinfo, &gs_info)
+      || gs_info.decl)
+    return NULL;
+
+  /* Convert the mask to the right form.  */
+  tree gs_vectype = get_vectype_for_scalar_type (gs_info.element_type);
+  if (mask)
+    mask = vect_convert_mask_for_vectype (mask, gs_vectype, stmt_info,
+					  loop_vinfo);
+
+  /* Get the invariant base and non-invariant offset, converting the
+     latter to the same width as the vector elements.  */
+  tree base = gs_info.base;
+  tree offset_type = vect_get_gather_scatter_offset_type (&gs_info);
+  tree offset = vect_add_conversion_to_pattern (offset_type, gs_info.offset,
+						stmt_info);
+
+  /* Build the new pattern statement.  */
+  tree scale = size_int (gs_info.scale);
+  gcall *pattern_stmt;
+  if (DR_IS_READ (dr))
+    {
+      if (mask != NULL)
+	pattern_stmt = gimple_build_call_internal (gs_info.ifn, 4, base,
+						   offset, scale, mask);
+      else
+	pattern_stmt = gimple_build_call_internal (gs_info.ifn, 3, base,
+						   offset, scale);
+      tree load_lhs = vect_recog_temp_ssa_var (gs_info.element_type, NULL);
+      gimple_call_set_lhs (pattern_stmt, load_lhs);
+    }
+  else
+    {
+      tree rhs = vect_get_store_rhs (stmt_info);
+      if (mask != NULL)
+	pattern_stmt = gimple_build_call_internal (IFN_MASK_SCATTER_STORE, 5,
+						   base, offset, scale, rhs,
+						   mask);
+      else
+	pattern_stmt = gimple_build_call_internal (IFN_SCATTER_STORE, 4,
+						   base, offset, scale, rhs);
+    }
+  gimple_call_set_nothrow (pattern_stmt, true);
+
+  /* Copy across relevant vectorization info and associate DR with the
+     new pattern statement instead of the original statement.  */
+  stmt_vec_info pattern_stmt_info = loop_vinfo->add_stmt (pattern_stmt);
+  loop_vinfo->move_dr (pattern_stmt_info, stmt_info);
+
+  tree vectype = STMT_VINFO_VECTYPE (stmt_info);
+  *type_out = vectype;
+  vect_pattern_detected ("gather/scatter pattern", stmt_info->stmt);
 
   return pattern_stmt;
 }
 
+/* Return true if TYPE is a non-boolean integer type.  These are the types
+   that we want to consider for narrowing.  */
+
+static bool
+vect_narrowable_type_p (tree type)
+{
+  return INTEGRAL_TYPE_P (type) && !VECT_SCALAR_BOOLEAN_TYPE_P (type);
+}
+
+/* Return true if the operation given by CODE can be truncated to N bits
+   when only N bits of the output are needed.  This is only true if bit N+1
+   of the inputs has no effect on the low N bits of the result.  */
+
+static bool
+vect_truncatable_operation_p (tree_code code)
+{
+  switch (code)
+    {
+    case PLUS_EXPR:
+    case MINUS_EXPR:
+    case MULT_EXPR:
+    case BIT_AND_EXPR:
+    case BIT_IOR_EXPR:
+    case BIT_XOR_EXPR:
+    case COND_EXPR:
+      return true;
+
+    default:
+      return false;
+    }
+}
+
+/* Record that STMT_INFO could be changed from operating on TYPE to
+   operating on a type with the precision and sign given by PRECISION
+   and SIGN respectively.  PRECISION is an arbitrary bit precision;
+   it might not be a whole number of bytes.  */
+
+static void
+vect_set_operation_type (stmt_vec_info stmt_info, tree type,
+			 unsigned int precision, signop sign)
+{
+  /* Round the precision up to a whole number of bytes.  */
+  precision = vect_element_precision (precision);
+  if (precision < TYPE_PRECISION (type)
+      && (!stmt_info->operation_precision
+	  || stmt_info->operation_precision > precision))
+    {
+      stmt_info->operation_precision = precision;
+      stmt_info->operation_sign = sign;
+    }
+}
+
+/* Record that STMT_INFO only requires MIN_INPUT_PRECISION from its
+   non-boolean inputs, all of which have type TYPE.  MIN_INPUT_PRECISION
+   is an arbitrary bit precision; it might not be a whole number of bytes.  */
+
+static void
+vect_set_min_input_precision (stmt_vec_info stmt_info, tree type,
+			      unsigned int min_input_precision)
+{
+  /* This operation in isolation only requires the inputs to have
+     MIN_INPUT_PRECISION of precision,  However, that doesn't mean
+     that MIN_INPUT_PRECISION is a natural precision for the chain
+     as a whole.  E.g. consider something like:
+
+	 unsigned short *x, *y;
+	 *y = ((*x & 0xf0) >> 4) | (*y << 4);
+
+     The right shift can be done on unsigned chars, and only requires the
+     result of "*x & 0xf0" to be done on unsigned chars.  But taking that
+     approach would mean turning a natural chain of single-vector unsigned
+     short operations into one that truncates "*x" and then extends
+     "(*x & 0xf0) >> 4", with two vectors for each unsigned short
+     operation and one vector for each unsigned char operation.
+     This would be a significant pessimization.
+
+     Instead only propagate the maximum of this precision and the precision
+     required by the users of the result.  This means that we don't pessimize
+     the case above but continue to optimize things like:
+
+	 unsigned char *y;
+	 unsigned short *x;
+	 *y = ((*x & 0xf0) >> 4) | (*y << 4);
+
+     Here we would truncate two vectors of *x to a single vector of
+     unsigned chars and use single-vector unsigned char operations for
+     everything else, rather than doing two unsigned short copies of
+     "(*x & 0xf0) >> 4" and then truncating the result.  */
+  min_input_precision = MAX (min_input_precision,
+			     stmt_info->min_output_precision);
+
+  if (min_input_precision < TYPE_PRECISION (type)
+      && (!stmt_info->min_input_precision
+	  || stmt_info->min_input_precision > min_input_precision))
+    stmt_info->min_input_precision = min_input_precision;
+}
+
+/* Subroutine of vect_determine_min_output_precision.  Return true if
+   we can calculate a reduced number of output bits for STMT_INFO,
+   whose result is LHS.  */
+
+static bool
+vect_determine_min_output_precision_1 (stmt_vec_info stmt_info, tree lhs)
+{
+  /* Take the maximum precision required by users of the result.  */
+  vec_info *vinfo = stmt_info->vinfo;
+  unsigned int precision = 0;
+  imm_use_iterator iter;
+  use_operand_p use;
+  FOR_EACH_IMM_USE_FAST (use, iter, lhs)
+    {
+      gimple *use_stmt = USE_STMT (use);
+      if (is_gimple_debug (use_stmt))
+	continue;
+      stmt_vec_info use_stmt_info = vinfo->lookup_stmt (use_stmt);
+      if (!use_stmt_info || !use_stmt_info->min_input_precision)
+	return false;
+      /* The input precision recorded for COND_EXPRs applies only to the
+	 "then" and "else" values.  */
+      gassign *assign = dyn_cast <gassign *> (stmt_info->stmt);
+      if (assign
+	  && gimple_assign_rhs_code (assign) == COND_EXPR
+	  && use->use != gimple_assign_rhs2_ptr (assign)
+	  && use->use != gimple_assign_rhs3_ptr (assign))
+	return false;
+      precision = MAX (precision, use_stmt_info->min_input_precision);
+    }
+
+  if (dump_enabled_p ())
+    dump_printf_loc (MSG_NOTE, vect_location,
+		     "only the low %d bits of %T are significant\n",
+		     precision, lhs);
+  stmt_info->min_output_precision = precision;
+  return true;
+}
+
+/* Calculate min_output_precision for STMT_INFO.  */
+
+static void
+vect_determine_min_output_precision (stmt_vec_info stmt_info)
+{
+  /* We're only interested in statements with a narrowable result.  */
+  tree lhs = gimple_get_lhs (stmt_info->stmt);
+  if (!lhs
+      || TREE_CODE (lhs) != SSA_NAME
+      || !vect_narrowable_type_p (TREE_TYPE (lhs)))
+    return;
+
+  if (!vect_determine_min_output_precision_1 (stmt_info, lhs))
+    stmt_info->min_output_precision = TYPE_PRECISION (TREE_TYPE (lhs));
+}
+
+/* Use range information to decide whether STMT (described by STMT_INFO)
+   could be done in a narrower type.  This is effectively a forward
+   propagation, since it uses context-independent information that applies
+   to all users of an SSA name.  */
+
+static void
+vect_determine_precisions_from_range (stmt_vec_info stmt_info, gassign *stmt)
+{
+  tree lhs = gimple_assign_lhs (stmt);
+  if (!lhs || TREE_CODE (lhs) != SSA_NAME)
+    return;
+
+  tree type = TREE_TYPE (lhs);
+  if (!vect_narrowable_type_p (type))
+    return;
+
+  /* First see whether we have any useful range information for the result.  */
+  unsigned int precision = TYPE_PRECISION (type);
+  signop sign = TYPE_SIGN (type);
+  wide_int min_value, max_value;
+  if (!vect_get_range_info (lhs, &min_value, &max_value))
+    return;
+
+  tree_code code = gimple_assign_rhs_code (stmt);
+  unsigned int nops = gimple_num_ops (stmt);
+
+  if (!vect_truncatable_operation_p (code))
+    /* Check that all relevant input operands are compatible, and update
+       [MIN_VALUE, MAX_VALUE] to include their ranges.  */
+    for (unsigned int i = 1; i < nops; ++i)
+      {
+	tree op = gimple_op (stmt, i);
+	if (TREE_CODE (op) == INTEGER_CST)
+	  {
+	    /* Don't require the integer to have RHS_TYPE (which it might
+	       not for things like shift amounts, etc.), but do require it
+	       to fit the type.  */
+	    if (!int_fits_type_p (op, type))
+	      return;
+
+	    min_value = wi::min (min_value, wi::to_wide (op, precision), sign);
+	    max_value = wi::max (max_value, wi::to_wide (op, precision), sign);
+	  }
+	else if (TREE_CODE (op) == SSA_NAME)
+	  {
+	    /* Ignore codes that don't take uniform arguments.  */
+	    if (!types_compatible_p (TREE_TYPE (op), type))
+	      return;
+
+	    wide_int op_min_value, op_max_value;
+	    if (!vect_get_range_info (op, &op_min_value, &op_max_value))
+	      return;
+
+	    min_value = wi::min (min_value, op_min_value, sign);
+	    max_value = wi::max (max_value, op_max_value, sign);
+	  }
+	else
+	  return;
+      }
+
+  /* Try to switch signed types for unsigned types if we can.
+     This is better for two reasons.  First, unsigned ops tend
+     to be cheaper than signed ops.  Second, it means that we can
+     handle things like:
+
+	signed char c;
+	int res = (int) c & 0xff00; // range [0x0000, 0xff00]
+
+     as:
+
+	signed char c;
+	unsigned short res_1 = (unsigned short) c & 0xff00;
+	int res = (int) res_1;
+
+     where the intermediate result res_1 has unsigned rather than
+     signed type.  */
+  if (sign == SIGNED && !wi::neg_p (min_value))
+    sign = UNSIGNED;
+
+  /* See what precision is required for MIN_VALUE and MAX_VALUE.  */
+  unsigned int precision1 = wi::min_precision (min_value, sign);
+  unsigned int precision2 = wi::min_precision (max_value, sign);
+  unsigned int value_precision = MAX (precision1, precision2);
+  if (value_precision >= precision)
+    return;
+
+  if (dump_enabled_p ())
+    dump_printf_loc (MSG_NOTE, vect_location, "can narrow to %s:%d"
+		     " without loss of precision: %G",
+		     sign == SIGNED ? "signed" : "unsigned",
+		     value_precision, stmt);
+
+  vect_set_operation_type (stmt_info, type, value_precision, sign);
+  vect_set_min_input_precision (stmt_info, type, value_precision);
+}
+
+/* Use information about the users of STMT's result to decide whether
+   STMT (described by STMT_INFO) could be done in a narrower type.
+   This is effectively a backward propagation.  */
+
+static void
+vect_determine_precisions_from_users (stmt_vec_info stmt_info, gassign *stmt)
+{
+  tree_code code = gimple_assign_rhs_code (stmt);
+  unsigned int opno = (code == COND_EXPR ? 2 : 1);
+  tree type = TREE_TYPE (gimple_op (stmt, opno));
+  if (!vect_narrowable_type_p (type))
+    return;
+
+  unsigned int precision = TYPE_PRECISION (type);
+  unsigned int operation_precision, min_input_precision;
+  switch (code)
+    {
+    CASE_CONVERT:
+      /* Only the bits that contribute to the output matter.  Don't change
+	 the precision of the operation itself.  */
+      operation_precision = precision;
+      min_input_precision = stmt_info->min_output_precision;
+      break;
+
+    case LSHIFT_EXPR:
+    case RSHIFT_EXPR:
+      {
+	tree shift = gimple_assign_rhs2 (stmt);
+	if (TREE_CODE (shift) != INTEGER_CST
+	    || !wi::ltu_p (wi::to_widest (shift), precision))
+	  return;
+	unsigned int const_shift = TREE_INT_CST_LOW (shift);
+	if (code == LSHIFT_EXPR)
+	  {
+	    /* We need CONST_SHIFT fewer bits of the input.  */
+	    operation_precision = stmt_info->min_output_precision;
+	    min_input_precision = (MAX (operation_precision, const_shift)
+				    - const_shift);
+	  }
+	else
+	  {
+	    /* We need CONST_SHIFT extra bits to do the operation.  */
+	    operation_precision = (stmt_info->min_output_precision
+				   + const_shift);
+	    min_input_precision = operation_precision;
+	  }
+	break;
+      }
+
+    default:
+      if (vect_truncatable_operation_p (code))
+	{
+	  /* Input bit N has no effect on output bits N-1 and lower.  */
+	  operation_precision = stmt_info->min_output_precision;
+	  min_input_precision = operation_precision;
+	  break;
+	}
+      return;
+    }
+
+  if (operation_precision < precision)
+    {
+      if (dump_enabled_p ())
+	dump_printf_loc (MSG_NOTE, vect_location, "can narrow to %s:%d"
+			 " without affecting users: %G",
+			 TYPE_UNSIGNED (type) ? "unsigned" : "signed",
+			 operation_precision, stmt);
+      vect_set_operation_type (stmt_info, type, operation_precision,
+			       TYPE_SIGN (type));
+    }
+  vect_set_min_input_precision (stmt_info, type, min_input_precision);
+}
+
+/* Handle vect_determine_precisions for STMT_INFO, given that we
+   have already done so for the users of its result.  */
+
+void
+vect_determine_stmt_precisions (stmt_vec_info stmt_info)
+{
+  vect_determine_min_output_precision (stmt_info);
+  if (gassign *stmt = dyn_cast <gassign *> (stmt_info->stmt))
+    {
+      vect_determine_precisions_from_range (stmt_info, stmt);
+      vect_determine_precisions_from_users (stmt_info, stmt);
+    }
+}
+
+/* Walk backwards through the vectorizable region to determine the
+   values of these fields:
+
+   - min_output_precision
+   - min_input_precision
+   - operation_precision
+   - operation_sign.  */
+
+void
+vect_determine_precisions (vec_info *vinfo)
+{
+  DUMP_VECT_SCOPE ("vect_determine_precisions");
+
+  if (loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo))
+    {
+      struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
+      basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
+      unsigned int nbbs = loop->num_nodes;
+
+      for (unsigned int i = 0; i < nbbs; i++)
+	{
+	  basic_block bb = bbs[nbbs - i - 1];
+	  for (gimple_stmt_iterator si = gsi_last_bb (bb);
+	       !gsi_end_p (si); gsi_prev (&si))
+	    vect_determine_stmt_precisions
+	      (vinfo->lookup_stmt (gsi_stmt (si)));
+	}
+    }
+  else
+    {
+      bb_vec_info bb_vinfo = as_a <bb_vec_info> (vinfo);
+      gimple_stmt_iterator si = bb_vinfo->region_end;
+      gimple *stmt;
+      do
+	{
+	  if (!gsi_stmt (si))
+	    si = gsi_last_bb (bb_vinfo->bb);
+	  else
+	    gsi_prev (&si);
+	  stmt = gsi_stmt (si);
+	  stmt_vec_info stmt_info = vinfo->lookup_stmt (stmt);
+	  if (stmt_info && STMT_VINFO_VECTORIZABLE (stmt_info))
+	    vect_determine_stmt_precisions (stmt_info);
+	}
+      while (stmt != gsi_stmt (bb_vinfo->region_begin));
+    }
+}
+
+typedef gimple *(*vect_recog_func_ptr) (stmt_vec_info, tree *);
+
+struct vect_recog_func
+{
+  vect_recog_func_ptr fn;
+  const char *name;
+};
+
+/* Note that ordering matters - the first pattern matching on a stmt is
+   taken which means usually the more complex one needs to preceed the
+   less comples onex (widen_sum only after dot_prod or sad for example).  */
+static vect_recog_func vect_vect_recog_func_ptrs[] = {
+  { vect_recog_over_widening_pattern, "over_widening" },
+  /* Must come after over_widening, which narrows the shift as much as
+     possible beforehand.  */
+  { vect_recog_average_pattern, "average" },
+  { vect_recog_cast_forwprop_pattern, "cast_forwprop" },
+  { vect_recog_widen_mult_pattern, "widen_mult" },
+  { vect_recog_dot_prod_pattern, "dot_prod" },
+  { vect_recog_sad_pattern, "sad" },
+  { vect_recog_widen_sum_pattern, "widen_sum" },
+  { vect_recog_pow_pattern, "pow" },
+  { vect_recog_widen_shift_pattern, "widen_shift" },
+  { vect_recog_rotate_pattern, "rotate" },
+  { vect_recog_vector_vector_shift_pattern, "vector_vector_shift" },
+  { vect_recog_divmod_pattern, "divmod" },
+  { vect_recog_mult_pattern, "mult" },
+  { vect_recog_mixed_size_cond_pattern, "mixed_size_cond" },
+  { vect_recog_bool_pattern, "bool" },
+  /* This must come before mask conversion, and includes the parts
+     of mask conversion that are needed for gather and scatter
+     internal functions.  */
+  { vect_recog_gather_scatter_pattern, "gather_scatter" },
+  { vect_recog_mask_conversion_pattern, "mask_conversion" }
+};
+
+const unsigned int NUM_PATTERNS = ARRAY_SIZE (vect_vect_recog_func_ptrs);
 
 /* Mark statements that are involved in a pattern.  */
 
 static inline void
-vect_mark_pattern_stmts (gimple *orig_stmt, gimple *pattern_stmt,
+vect_mark_pattern_stmts (stmt_vec_info orig_stmt_info, 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;
-
-  pattern_stmt_info = vinfo_for_stmt (pattern_stmt);
-  if (pattern_stmt_info == NULL)
+  gimple *def_seq = STMT_VINFO_PATTERN_DEF_SEQ (orig_stmt_info);
+
+  gimple *orig_pattern_stmt = NULL;
+  if (is_pattern_stmt_p (orig_stmt_info))
     {
-      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.  */
+      orig_pattern_stmt = orig_stmt_info->stmt;
+      if (dump_enabled_p ())
+	dump_printf_loc (MSG_NOTE, vect_location,
+			 "replacing earlier pattern %G", orig_pattern_stmt);
+
+      /* 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_pattern_stmt);
+      gimple_set_lhs (orig_pattern_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 %G", pattern_stmt);
+
+      /* Switch to the statement that ORIG replaces.  */
+      orig_stmt_info = 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)->stmt
+		  != orig_pattern_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;
-  STMT_VINFO_PATTERN_DEF_SEQ (pattern_stmt_info)
-    = STMT_VINFO_PATTERN_DEF_SEQ (orig_stmt_info);
-  if (STMT_VINFO_PATTERN_DEF_SEQ (pattern_stmt_info))
+
+  if (def_seq)
+    for (gimple_stmt_iterator si = gsi_start (def_seq);
+	 !gsi_end_p (si); gsi_next (&si))
+      vect_init_pattern_stmt (gsi_stmt (si), orig_stmt_info, pattern_vectype);
+
+  if (orig_pattern_stmt)
     {
-      gimple_stmt_iterator si;
-      for (si = gsi_start (STMT_VINFO_PATTERN_DEF_SEQ (pattern_stmt_info));
-	   !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 (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_pattern_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);
+
+      /* Remove the pattern statement that this new pattern replaces.  */
+      gsi_remove (&gsi, false);
     }
+  else
+    vect_set_pattern_stmt (pattern_stmt, orig_stmt_info, pattern_vectype);
 }
 
 /* Function vect_pattern_recog_1
@@ -4110,126 +4744,70 @@
    Input:
    PATTERN_RECOG_FUNC: A pointer to a function that detects a certain
         computation pattern.
-   STMT: A stmt from which the pattern search should start.
-
-   If PATTERN_RECOG_FUNC successfully detected the pattern, it creates an
-   expression that computes the same functionality and can be used to
-   replace the sequence of stmts that are involved in the pattern.
-
-   Output:
-   This function checks if the expression returned by PATTERN_RECOG_FUNC is
-   supported in vector form by the target.  We use 'TYPE_IN' to obtain the
-   relevant vector type. If 'TYPE_IN' is already a vector type, then this
-   indicates that target support had already been checked by PATTERN_RECOG_FUNC.
-   If 'TYPE_OUT' is also returned by PATTERN_RECOG_FUNC, we check that it fits
-   to the available target pattern.
+   STMT_INFO: A stmt from which the pattern search should start.
+
+   If PATTERN_RECOG_FUNC successfully detected the pattern, it creates
+   a sequence of statements that has the same functionality and can be
+   used to replace STMT_INFO.  It returns the last statement in the sequence
+   and adds any earlier statements to STMT_INFO's STMT_VINFO_PATTERN_DEF_SEQ.
+   PATTERN_RECOG_FUNC also sets *TYPE_OUT to the vector type of the final
+   statement, having first checked that the target supports the new operation
+   in that type.
 
    This function also does some bookkeeping, as explained in the documentation
    for vect_recog_pattern.  */
 
-static bool
-vect_pattern_recog_1 (vect_recog_func *recog_func,
-		      gimple_stmt_iterator si,
-		      vec<gimple *> *stmts_to_replace)
+static void
+vect_pattern_recog_1 (vect_recog_func *recog_func, stmt_vec_info stmt_info)
 {
-  gimple *stmt = gsi_stmt (si), *pattern_stmt;
-  stmt_vec_info stmt_info;
+  vec_info *vinfo = stmt_info->vinfo;
+  gimple *pattern_stmt;
   loop_vec_info loop_vinfo;
   tree pattern_vectype;
-  tree type_in, type_out;
-  enum tree_code code;
-  int i;
-  gimple *next;
-
-  stmts_to_replace->truncate (0);
-  stmts_to_replace->quick_push (stmt);
-  pattern_stmt = recog_func->fn (stmts_to_replace, &type_in, &type_out);
-  if (!pattern_stmt)
-    return false;
-
-  stmt = stmts_to_replace->last ();
-  stmt_info = vinfo_for_stmt (stmt);
-  loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
- 
-  if (VECTOR_BOOLEAN_TYPE_P (type_in)
-      || VECTOR_TYPE_P (type_in))
-    {
-      /* No need to check target support (already checked by the pattern
-         recognition function).  */
-      pattern_vectype = type_out ? type_out : type_in;
-    }
-  else
+
+  /* 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.  */
+  if (STMT_VINFO_IN_PATTERN_P (stmt_info))
     {
-      machine_mode vec_mode;
-      enum insn_code icode;
-      optab optab;
-
-      /* Check target support  */
-      type_in = get_vectype_for_scalar_type (type_in);
-      if (!type_in)
-	return false;
-      if (type_out)
-	type_out = get_vectype_for_scalar_type (type_out);
-      else
-	type_out = type_in;
-      if (!type_out)
-	return false;
-      pattern_vectype = type_out;
-
-      if (is_gimple_assign (pattern_stmt))
-	code = gimple_assign_rhs_code (pattern_stmt);
-      else
-        {
-	  gcc_assert (is_gimple_call (pattern_stmt));
-	  code = CALL_EXPR;
-	}
-
-      optab = optab_for_tree_code (code, type_in, optab_default);
-      vec_mode = TYPE_MODE (type_in);
-      if (!optab
-          || (icode = optab_handler (optab, vec_mode)) == CODE_FOR_nothing
-          || (insn_data[icode].operand[0].mode != TYPE_MODE (type_out)))
-	return false;
+      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, vinfo->lookup_stmt (gsi_stmt (gsi)));
+      return;
     }
 
+  gcc_assert (!STMT_VINFO_PATTERN_DEF_SEQ (stmt_info));
+  pattern_stmt = recog_func->fn (stmt_info, &pattern_vectype);
+  if (!pattern_stmt)
+    {
+      /* Clear any half-formed pattern definition sequence.  */
+      STMT_VINFO_PATTERN_DEF_SEQ (stmt_info) = NULL;
+      return;
+    }
+
+  loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
+  gcc_assert (pattern_vectype);
+ 
   /* Found a vectorizable pattern.  */
   if (dump_enabled_p ())
-    {
-      dump_printf_loc (MSG_NOTE, vect_location,
-                       "%s pattern recognized: ", recog_func->name);
-      dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
-    }
+    dump_printf_loc (MSG_NOTE, vect_location,
+		     "%s pattern recognized: %G",
+		     recog_func->name, pattern_stmt);
 
   /* Mark the stmts that are involved in the pattern. */
-  vect_mark_pattern_stmts (stmt, pattern_stmt, pattern_vectype);
+  vect_mark_pattern_stmts (stmt_info, pattern_stmt, pattern_vectype);
 
   /* Patterns cannot be vectorized using SLP, because they change the order of
      computation.  */
   if (loop_vinfo)
-    FOR_EACH_VEC_ELT (LOOP_VINFO_REDUCTIONS (loop_vinfo), i, next)
-      if (next == stmt)
-        LOOP_VINFO_REDUCTIONS (loop_vinfo).ordered_remove (i);
-
-  /* It is possible that additional pattern stmts are created and inserted in
-     STMTS_TO_REPLACE.  We create a stmt_info for each of them, and mark the
-     relevant statements.  */
-  for (i = 0; stmts_to_replace->iterate (i, &stmt)
-	      && (unsigned) i < (stmts_to_replace->length () - 1);
-       i++)
     {
-      stmt_info = vinfo_for_stmt (stmt);
-      pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
-      if (dump_enabled_p ())
-        {
-          dump_printf_loc (MSG_NOTE, vect_location,
-                           "additional pattern stmt: ");
-          dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
-        }
-
-      vect_mark_pattern_stmts (stmt, pattern_stmt, NULL_TREE);
+      unsigned ix, ix2;
+      stmt_vec_info *elem_ptr;
+      VEC_ORDERED_REMOVE_IF (LOOP_VINFO_REDUCTIONS (loop_vinfo), ix, ix2,
+			     elem_ptr, *elem_ptr == stmt_info);
     }
-
-  return true;
 }
 
 
@@ -4318,12 +4896,10 @@
   unsigned int nbbs;
   gimple_stmt_iterator si;
   unsigned int i, j;
-  auto_vec<gimple *, 1> stmts_to_replace;
-  gimple *stmt;
-
-  if (dump_enabled_p ())
-    dump_printf_loc (MSG_NOTE, vect_location,
-                     "=== vect_pattern_recog ===\n");
+
+  vect_determine_precisions (vinfo);
+
+  DUMP_VECT_SCOPE ("vect_pattern_recog");
 
   if (loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo))
     {
@@ -4338,11 +4914,11 @@
 	  basic_block bb = bbs[i];
 	  for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
 	    {
+	      stmt_vec_info stmt_info = vinfo->lookup_stmt (gsi_stmt (si));
 	      /* 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],
+				      stmt_info);
 	    }
 	}
     }
@@ -4352,16 +4928,14 @@
       for (si = bb_vinfo->region_begin;
 	   gsi_stmt (si) != gsi_stmt (bb_vinfo->region_end); gsi_next (&si))
 	{
-	  if ((stmt = gsi_stmt (si))
-	      && vinfo_for_stmt (stmt)
-	      && !STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt)))
+	  gimple *stmt = gsi_stmt (si);
+	  stmt_vec_info stmt_info = bb_vinfo->lookup_stmt (stmt);
+	  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], stmt_info);
 	}
     }
 }