RFC: Variable-length VECTOR_CSTs

Richard Biener richard.guenther@gmail.com
Wed Nov 29 15:56:00 GMT 2017


On Wed, Nov 29, 2017 at 12:57 PM, Richard Sandiford
<richard.sandiford@linaro.org> wrote:
> It was clear from the SVE reviews that people were unhappy with how
> "special" the variable-length case was.  One particular concern was
> the use of VEC_DUPLICATE_CST and VEC_SERIES_CST, and the way that
> that would in turn lead to different representations of VEC_PERM_EXPRs
> with constant permute vectors, and difficulties in invoking
> vec_perm_const_ok.
>
> This is an RFC for a VECTOR_CST representation that treats each
> specific constant as one instance of an arbitrary-length sequence.
> The reprensentation then extends to variable-length vectors in a
> natural way.
>
> As discussed on IRC, if a vector contains X*N elements for some
> constant N and integer X>0, the main features we need are:
>
> 1) the ability to represent a sequence that duplicates N values
>
>    This is useful for SLP invariants.
>
> 2) the ability to represent a sequence that starts with N values and
>    is followed by zeros
>
>    This is useful for the initial value in a double or SLP reduction
>
> 3) the ability to represent N interleaved series
>
>    This is useful for SLP inductions and for VEC_PERM_EXPRs.
>
> For (2), zero isn't necessarily special, since vectors used in an AND
> reduction might need to fill with ones.  Also, we might need up to N
> different fill values with mixed SLP operations; it isn't necessarily
> safe to assume that a single fill value will always be enough.
>
> The same goes for (3): there's no reason in principle why the
> steps in an SLP induction should all be the same (although they
> do need to be at the moment).  E.g. once we support SLP on:
>
>   for (unsigned int i = 0; i < n; i += 2)
>     {
>       x[i] += 4 + i;
>       x[i + 1] += 11 + i * 3;
>     }
>
> we'll need {[4, 14], +, [2, 6]}.
>
> So the idea is to represent vectors as P interleaved patterns of the form:
>
>   [BASE0, BASE1, BASE1 + STEP, BASE1 + STEP*2, ...]
>
> where the STEP is always zero (actually null) for non-integer vectors.
> This is effectively projecting a "foreground" value of P elements
> onto an arbitrary-length "background" sequenece, where the background
> sequence contains P parallel linear series.
>
> E.g. to pick an extreme and unlikely example,
>
>   [42, 99, 2, 20, 3, 30, 4, 40, ...]
>
> has 2 patterns:
>
>   BASE0 = 42, BASE1 = 2, STEP = 1
>   BASE0 = 99, BASE1 = 20, STEP = 10
>
> The more useful cases are degenerate versions of this general case.
>
> As far as memory consumption goes: the number of patterns needed for a
> fixed-length vector with 2*N elements is always at most N; in the worst
> case, we simply interleave the first N elements with the second N elements.
> The worst-case increase in footprint is therefore N trees for the steps.
> In practice the footprint is usually smaller than it was before, since
> most constants do have a pattern.
>
> The patch below implements this for trees.  I have patches to use the
> same style of encoding for CONST_VECTOR and vec_perm_indices, but the
> tree one is probably easiest to read.
>
> The patch only adds the representation.  Follow-on patches make more
> use of it (and usually make things simpler; e.g. integer_zerop is no
> longer a looping operation).
>
> Does this look better?

Yes, the overall design looks good.  I wonder why you chose to have
the number of patterns being a power of two?  I suppose this is
to have the same number of elements from all patterns in the final
vector (which is power-of-two sized)?  I wonder if there exists
a vector where say a three-pattern interleaving would be smaller
than a four-pattern one?

Given you add flags for various purposes would it make sense to
overload 'step' with a regular element to avoid the storage increase
in case step is unnecessary?  This makes it have three elements
which is of course awkward :/

Few more comments below.

Otherwise looks good to go!

Thanks for doing this.

> Thanks,
> Richard
>
>
> 2017-11-29  Richard Sandiford  <richard.sandiford@arm.com>
>
> gcc/
>         * doc/generic.texi (VECTOR_CST): Describe new representation of
>         vector constants.
>         * tree.def (VECTOR_CST): Update comment to refer to generic.texi.
>         * tree-core.h (tree_base): Add a vector_cst field to the u union.
>         (tree_vector_pattern): New struct.
>         (tree_vector): Replace elts array with a patterns array.
>         * tree.h (VECTOR_CST_NELTS): Redefine using TYPE_VECTOR_SUBPARTS.
>         (VECTOR_CST_ELTS): Delete.
>         (VECTOR_CST_ELT): Redefine using vector_cst_elt.
>         (VECTOR_CST_LOG2_NPATTERNS, VECTOR_CST_NPATTERNS): New macros.
>         (VECTOR_CST_DUPLICATE_P, VECTOR_CST_SERIES_P, VECTOR_CST_BASE)
>         (VECTOR_CST_STEP): Likewise.
>         (make_vector): Take the values of VECTOR_CST_LOG2_NPATTERNS,
>         VECTOR_CST_DUPLICATE_P and VECTOR_CST_SERIES_P as arguments.
>         (build_vector): Declare an overload that takes a vector of
>         tree_vector_patterns.
>         (vector_cst_int_elt, vector_cst_elt): Declare.
>         * tree.c (tree_code_size): Abort if passed VECTOR_CST.
>         (tree_size): Update for new VECTOR_CST layout.
>         (make_vector): Take the values of VECTOR_CST_LOG2_NPATTERNS,
>         VECTOR_CST_DUPLICATE_P and VECTOR_CST_SERIES_P as arguments.
>         (combine_patterns, compress_vector_patterns, vector_overflow_p)
>         (vector_duplicate_p, vector_series_p): New functions.
>         (build_vector): Add an overload that takes a vector of
>         tree_vector_patterns.  Use it for the overload that takes
>         a vector of elements.
>         (vector_cst_int_elt, vector_cst_elt): New functions.
>         (drop_tree_overflow): For VECTOR_CST, drop the overflow flags
>         from the VECTOR_CST_BASEs.
>         (check_vector_cst, test_vector_cst_patterns): New functions.
>         (tree_c_tests): Call it.
>         * lto-streamer-out.c (DFS::DFS_write_tree_body): Handle the new
>         VECTOR_CST fields.
>         (hash_tree): Likewise.
>         * tree-streamer-out.c (write_ts_vector_tree_pointers): Likewise.
>         (streamer_write_tree_header): Likewise.
>         * tree-streamer-in.c (lto_input_ts_vector_tree_pointers): Likewise.
>         (streamer_alloc_tree): Likewise.  Update call to make_vector.
>         * fold-const.c (fold_ternary_loc): Avoid using VECTOR_CST_ELTS.
>
> gcc/lto/
>         * lto.c (compare_tree_sccs_1): Compare the new VECTOR_CST flags.
>
> Index: gcc/doc/generic.texi
> ===================================================================
> *** gcc/doc/generic.texi        2017-11-29 11:07:59.961993930 +0000
> --- gcc/doc/generic.texi        2017-11-29 11:08:00.183993912 +0000
> *************** These nodes are used to represent comple
> *** 1084,1093 ****
>   imaginary parts respectively.
>
>   @item VECTOR_CST
> ! These nodes are used to represent vector constants, whose parts are
> ! constant nodes.  Each individual constant node is either an integer or a
> ! double constant node.  The first operand is a @code{TREE_LIST} of the
> ! constant nodes and is accessed through @code{TREE_VECTOR_CST_ELTS}.
>
>   @item STRING_CST
>   These nodes represent string-constants.  The @code{TREE_STRING_LENGTH}
> --- 1084,1147 ----
>   imaginary parts respectively.
>
>   @item VECTOR_CST
> ! These nodes are used to represent vector constants.  Each vector
> ! constant @var{v} is treated as a specific instance of an arbitrary-length
> ! sequence that itself contains @samp{VECTOR_CST_NPATTERNS (@var{v})}
> ! interleaved patterns.  Each pattern @var{i} has three parts:
> !
> ! @itemize @samp
> ! @item VECTOR_CST_BASE (@var{v}, @var{i}, 0)
> ! The vector element value for the first instance of the pattern.
> !
> ! @item VECTOR_CST_BASE (@var{v}, @var{i}, 1)
> ! The vector element value for the second instance of the pattern.
> !
> ! @item VECTOR_CST_STEP (@var{v}, @var{i})
> ! If the first and second instances of the pattern are @code{INTEGER_CST}s,
> ! this is the difference between each subsequent instance of the pattern
> ! and the previous instance.  In other cases it is null, which indicates
> ! that subsequent instances of the pattern have the same value as the
> ! second instance.
> !
> ! If @var{v} only needs two instances of a pattern, and if both instances
> ! are @code{INTEGER_CST}s, the step is the difference between them.
> !
> ! The addition of the step to get third and subsequent elements is always
> ! a wrapping operation: there is no undefined behavior or overflow.
> ! @end itemize
> !
> ! For example, the constant:
> ! @smallexample
> ! @{ 1, 5, 2, 6, 3, 7, 4, 8 @}
> ! @end smallexample
> ! is encoded using the interleaved patterns:
> ! @smallexample
> ! @{ 1, 2, 3, @dots{} @}
> ! @{ 5, 6, 7, @dots{} @}
> ! @end smallexample
> ! where:
> ! @smallexample
> ! wi::to_wide (VECTOR_CST_BASE (@var{v}, 0, 0)) == 1
> ! wi::to_wide (VECTOR_CST_BASE (@var{v}, 0, 1)) == 2
> ! wi::to_wide (VECTOR_CST_STEP (@var{v}, 0)) == 1
> ! wi::to_wide (VECTOR_CST_BASE (@var{v}, 1, 0)) == 5
> ! wi::to_wide (VECTOR_CST_BASE (@var{v}, 1, 1)) == 6
> ! wi::to_wide (VECTOR_CST_STEP (@var{v}, 1)) == 1
> ! @end smallexample
> !
> ! @samp{VECTOR_CST_DUPLICATE_P (@var{v})} is true if @var{v} simply
> ! contains repeated instances of @samp{VECTOR_CST_NPATTERNS (@var{v})}
> ! values.  In this case the two bases in each pattern are equal and
> ! the steps for integer vectors are zero.
> !
> ! @samp{VECTOR_CST_SERIES_P (@var{v})} is true if each pattern can
> ! be seen as a linear series, with @samp{VECTOR_CST_BASE (@var{v}, @var{i}, 0)}
> ! giving the start value and @samp{VECTOR_CST_STEP (@var{v}, @var{i}))}
> ! giving the step.
> !
> ! The utility function @code{vector_cst_elt} gives the value of an
> ! arbitrary index as a @code{tree}.  @code{vector_cst_int_elt} gives
> ! the same value as a @code{wide_int}.
>
>   @item STRING_CST
>   These nodes represent string-constants.  The @code{TREE_STRING_LENGTH}
> Index: gcc/tree.def
> ===================================================================
> *** gcc/tree.def        2017-11-29 11:07:59.961993930 +0000
> --- gcc/tree.def        2017-11-29 11:08:00.187993912 +0000
> *************** DEFTREECODE (FIXED_CST, "fixed_cst", tcc
> *** 301,307 ****
>      whose contents are other constant nodes.  */
>   DEFTREECODE (COMPLEX_CST, "complex_cst", tcc_constant, 0)
>
> ! /* Contents are in VECTOR_CST_ELTS field.  */
>   DEFTREECODE (VECTOR_CST, "vector_cst", tcc_constant, 0)
>
>   /* Contents are TREE_STRING_LENGTH and the actual contents of the string.  */
> --- 301,307 ----
>      whose contents are other constant nodes.  */
>   DEFTREECODE (COMPLEX_CST, "complex_cst", tcc_constant, 0)
>
> ! /* See generic.texi for details.  */
>   DEFTREECODE (VECTOR_CST, "vector_cst", tcc_constant, 0)
>
>   /* Contents are TREE_STRING_LENGTH and the actual contents of the string.  */
> Index: gcc/tree-core.h
> ===================================================================
> *** gcc/tree-core.h     2017-11-29 11:07:59.961993930 +0000
> --- gcc/tree-core.h     2017-11-29 11:08:00.185993912 +0000
> *************** struct GTY(()) tree_base {
> *** 976,983 ****
>       /* VEC length.  This field is only used with TREE_VEC.  */
>       int length;
>
> !     /* Number of elements.  This field is only used with VECTOR_CST.  */
> !     unsigned int nelts;
>
>       /* SSA version number.  This field is only used with SSA_NAME.  */
>       unsigned int version;
> --- 976,995 ----
>       /* VEC length.  This field is only used with TREE_VEC.  */
>       int length;
>
> !     /* This field is only used with VECTOR_CST.  */
> !     struct {
> !       /* The value of VECTOR_CST_LOG2_NPATTERNS.  */
> !       unsigned int log2_npatterns : 16;
> !
> !       /* The value of VECTOR_CST_DUPLICATE_P.  */
> !       unsigned int duplicate_p : 1;
> !
> !       /* The value of VECTOR_CST_SERIES_P.  */
> !       unsigned int series_p : 1;
> !
> !       /* For future expansion.  */
> !       unsigned int unused : 14;
> !     } vector_cst;
>
>       /* SSA version number.  This field is only used with SSA_NAME.  */
>       unsigned int version;
> *************** struct GTY(()) tree_complex {
> *** 1331,1339 ****
>     tree imag;
>   };
>
>   struct GTY(()) tree_vector {
>     struct tree_typed typed;
> !   tree GTY ((length ("VECTOR_CST_NELTS ((tree) &%h)"))) elts[1];
>   };
>
>   struct GTY(()) tree_identifier {
> --- 1343,1363 ----
>     tree imag;
>   };
>
> + /* One pattern in a VECTOR_CST.  Instance I of the pattern has the value:
> +
> +       I == 0 ? BASE[0] : BASE[1] + (I - 1) * STEP
> +
> +    The STEP is nonnull iff BASE[0] and BASE[1] are INTEGER_CSTs;
> +    in other cases the step is implicitly 0.  */
> + struct GTY(()) tree_vector_pattern {
> +   tree base[2];
> +   tree step;
> + };
> +
>   struct GTY(()) tree_vector {
>     struct tree_typed typed;
> !   tree_vector_pattern
> !     GTY ((length ("VECTOR_CST_NPATTERNS ((tree) &%h)"))) patterns[1];
>   };
>
>   struct GTY(()) tree_identifier {
> Index: gcc/tree.h
> ===================================================================
> *** gcc/tree.h  2017-11-29 11:07:59.961993930 +0000
> --- gcc/tree.h  2017-11-29 11:08:00.188993912 +0000
> *************** #define TREE_STRING_POINTER(NODE) \
> *** 1012,1021 ****
>   #define TREE_REALPART(NODE) (COMPLEX_CST_CHECK (NODE)->complex.real)
>   #define TREE_IMAGPART(NODE) (COMPLEX_CST_CHECK (NODE)->complex.imag)
>
> ! /* In a VECTOR_CST node.  */
> ! #define VECTOR_CST_NELTS(NODE) (VECTOR_CST_CHECK (NODE)->base.u.nelts)
> ! #define VECTOR_CST_ELTS(NODE) (VECTOR_CST_CHECK (NODE)->vector.elts)
> ! #define VECTOR_CST_ELT(NODE,IDX) (VECTOR_CST_CHECK (NODE)->vector.elts[IDX])
>
>   /* Define fields and accessors for some special-purpose tree nodes.  */
>
> --- 1012,1033 ----
>   #define TREE_REALPART(NODE) (COMPLEX_CST_CHECK (NODE)->complex.real)
>   #define TREE_IMAGPART(NODE) (COMPLEX_CST_CHECK (NODE)->complex.imag)
>
> ! /* In a VECTOR_CST node.  See generic.texi for details.  */
> ! #define VECTOR_CST_NELTS(NODE) (TYPE_VECTOR_SUBPARTS (TREE_TYPE (NODE)))
> ! #define VECTOR_CST_ELT(NODE,IDX) vector_cst_elt (NODE, IDX)
> !
> ! #define VECTOR_CST_LOG2_NPATTERNS(NODE) \
> !   (VECTOR_CST_CHECK (NODE)->base.u.vector_cst.log2_npatterns)
> ! #define VECTOR_CST_NPATTERNS(NODE) \
> !   (1U << VECTOR_CST_LOG2_NPATTERNS (NODE))
> ! #define VECTOR_CST_DUPLICATE_P(NODE) \
> !   (VECTOR_CST_CHECK (NODE)->base.u.vector_cst.duplicate_p)
> ! #define VECTOR_CST_SERIES_P(NODE) \
> !   (VECTOR_CST_CHECK (NODE)->base.u.vector_cst.series_p)
> ! #define VECTOR_CST_BASE(NODE, ELT, SUBELT) \
> !   (VECTOR_CST_CHECK (NODE)->vector.patterns[ELT].base[SUBELT])
> ! #define VECTOR_CST_STEP(NODE, ELT) \
> !   (VECTOR_CST_CHECK (NODE)->vector.patterns[ELT].step)
>
>   /* Define fields and accessors for some special-purpose tree nodes.  */
>
> *************** extern tree force_fit_type (tree, const
> *** 4024,4030 ****
>   extern tree build_int_cst (tree, HOST_WIDE_INT);
>   extern tree build_int_cstu (tree type, unsigned HOST_WIDE_INT cst);
>   extern tree build_int_cst_type (tree, HOST_WIDE_INT);
> ! extern tree make_vector (unsigned CXX_MEM_STAT_INFO);
>   extern tree build_vector (tree, vec<tree> CXX_MEM_STAT_INFO);
>   extern tree build_vector_from_ctor (tree, vec<constructor_elt, va_gc> *);
>   extern tree build_vector_from_val (tree, tree);
> --- 4036,4043 ----
>   extern tree build_int_cst (tree, HOST_WIDE_INT);
>   extern tree build_int_cstu (tree type, unsigned HOST_WIDE_INT cst);
>   extern tree build_int_cst_type (tree, HOST_WIDE_INT);
> ! extern tree make_vector (unsigned, bool, bool CXX_MEM_STAT_INFO);
> ! extern tree build_vector (tree, vec<tree_vector_pattern> CXX_MEM_STAT_INFO);
>   extern tree build_vector (tree, vec<tree> CXX_MEM_STAT_INFO);
>   extern tree build_vector_from_ctor (tree, vec<constructor_elt, va_gc> *);
>   extern tree build_vector_from_val (tree, tree);
> *************** extern tree first_field (const_tree);
> *** 4271,4276 ****
> --- 4284,4292 ----
>
>   extern bool initializer_zerop (const_tree);
>
> + extern wide_int vector_cst_int_elt (const_tree, unsigned int);
> + extern tree vector_cst_elt (const_tree, unsigned int);
> +
>   /* Given a vector VEC, return its first element if all elements are
>      the same.  Otherwise return NULL_TREE.  */
>
> Index: gcc/tree.c
> ===================================================================
> *** gcc/tree.c  2017-11-29 11:07:59.961993930 +0000
> --- gcc/tree.c  2017-11-29 11:08:00.187993912 +0000
> *************** tree_code_size (enum tree_code code)
> *** 839,845 ****
>         case REAL_CST:          return sizeof (tree_real_cst);
>         case FIXED_CST:         return sizeof (tree_fixed_cst);
>         case COMPLEX_CST:       return sizeof (tree_complex);
> !       case VECTOR_CST:        return sizeof (tree_vector);
>         case STRING_CST:        gcc_unreachable ();
>         default:
>           gcc_checking_assert (code >= NUM_TREE_CODES);
> --- 839,845 ----
>         case REAL_CST:          return sizeof (tree_real_cst);
>         case FIXED_CST:         return sizeof (tree_fixed_cst);
>         case COMPLEX_CST:       return sizeof (tree_complex);
> !       case VECTOR_CST:        gcc_unreachable ();
>         case STRING_CST:        gcc_unreachable ();
>         default:
>           gcc_checking_assert (code >= NUM_TREE_CODES);
> *************** tree_size (const_tree node)
> *** 899,905 ****
>
>       case VECTOR_CST:
>         return (sizeof (struct tree_vector)
> !             + (VECTOR_CST_NELTS (node) - 1) * sizeof (tree));
>
>       case STRING_CST:
>         return TREE_STRING_LENGTH (node) + offsetof (struct tree_string, str) + 1;
> --- 899,906 ----
>
>       case VECTOR_CST:
>         return (sizeof (struct tree_vector)
> !             + ((VECTOR_CST_NPATTERNS (node) - 1)
> !                * sizeof (tree_vector_pattern)));
>
>       case STRING_CST:
>         return TREE_STRING_LENGTH (node) + offsetof (struct tree_string, str) + 1;
> *************** cst_and_fits_in_hwi (const_tree x)
> *** 1708,1720 ****
>           && (tree_fits_shwi_p (x) || tree_fits_uhwi_p (x)));
>   }
>
> ! /* Build a newly constructed VECTOR_CST node of length LEN.  */
>
>   tree
> ! make_vector (unsigned len MEM_STAT_DECL)
>   {
>     tree t;
> !   unsigned length = (len - 1) * sizeof (tree) + sizeof (struct tree_vector);
>
>     record_node_allocation_statistics (VECTOR_CST, length);
>
> --- 1709,1726 ----
>           && (tree_fits_shwi_p (x) || tree_fits_uhwi_p (x)));
>   }
>
> ! /* Build a newly constructed VECTOR_CST with the given values of
> !    (VECTOR_CST_)LOG2_NPATTERNS, (VECTOR_CST_)DUPLICATE_P amd
> !    (VECTOR_CST_)SERIES_P.  */
>
>   tree
> ! make_vector (unsigned log2_npatterns, bool duplicate_p,
> !            bool series_p MEM_STAT_DECL)
>   {
>     tree t;
> !   unsigned npatterns = 1 << log2_npatterns;
> !   unsigned length = (sizeof (struct tree_vector)
> !                    + (npatterns - 1) * sizeof (tree_vector_pattern));
>
>     record_node_allocation_statistics (VECTOR_CST, length);
>
> *************** make_vector (unsigned len MEM_STAT_DECL)
> *** 1722,1764 ****
>
>     TREE_SET_CODE (t, VECTOR_CST);
>     TREE_CONSTANT (t) = 1;
> !   VECTOR_CST_NELTS (t) = len;
>
>     return t;
>   }
>
> ! /* Return a new VECTOR_CST node whose type is TYPE and whose values
> !    are given by VALS.  */
>
> ! tree
> ! build_vector (tree type, vec<tree> vals MEM_STAT_DECL)
>   {
> !   unsigned int nelts = vals.length ();
> !   gcc_assert (nelts == TYPE_VECTOR_SUBPARTS (type));
> !   int over = 0;
> !   unsigned cnt = 0;
> !   tree v = make_vector (nelts);
> !   TREE_TYPE (v) = type;
>
> !   /* Iterate through elements and check for overflow.  */
> !   for (cnt = 0; cnt < nelts; ++cnt)
>       {
> !       tree value = vals[cnt];
>
> !       VECTOR_CST_ELT (v, cnt) = value;
>
> !       /* Don't crash if we get an address constant.  */
> !       if (!CONSTANT_CLASS_P (value))
> !       continue;
>
> !       over |= TREE_OVERFLOW (value);
>       }
>
> !   TREE_OVERFLOW (v) = over;
>     return v;
>   }
>
>   /* Return a new VECTOR_CST node whose type is TYPE and whose values
>      are extracted from V, a vector of CONSTRUCTOR_ELT.  */
>
>   tree
> --- 1728,1949 ----
>
>     TREE_SET_CODE (t, VECTOR_CST);
>     TREE_CONSTANT (t) = 1;
> !   VECTOR_CST_LOG2_NPATTERNS (t) = log2_npatterns;
> !   VECTOR_CST_DUPLICATE_P (t) = duplicate_p;
> !   VECTOR_CST_SERIES_P (t) = series_p;
>
>     return t;
>   }
>
> ! /* Try to represent the interleaving of SRC1 and SRC2 as a single
> !    pattern.  Return true on success, adding the pattern to DEST.
> !    FIRST_P is true if all elements are represented by the bases,
> !    with no values determined by the steps.  */
>
> ! static bool
> ! combine_patterns (vec<tree_vector_pattern> *dest,
> !                 const tree_vector_pattern *src1,
> !                 const tree_vector_pattern *src2,
> !                 bool first_p)
>   {
> !   /* Any new pattern would represent:
> !
> !      { src1->base[0], vals[0], vals[1], vals[2], ... }
> !
> !      where ... exists only if !FIRST_P.  */
> !   tree vals[3] = { src2->base[0], src1->base[1], src2->base[1] };
> !
> !   /* See whether any values overflowed.  */
> !   tree overflowed = NULL_TREE;
> !   for (unsigned int i = 0; i < 3; ++i)
> !     if (CONSTANT_CLASS_P (vals[i]) && TREE_OVERFLOW (vals[i]))
> !       {
> !       overflowed = vals[i];
> !       break;
> !       }
> !
> !   bool zero_step1_p = (!src1->step || wi::to_wide (src1->step) == 0);
> !   bool zero_step2_p = (!src2->step || wi::to_wide (src1->step) == 0);
>
> !   /* Option 1: use VALS[0] as the second base without a step.  */
> !   if ((first_p || (zero_step1_p && zero_step2_p))
> !       && operand_equal_p (vals[0], vals[1], 0)
> !       && operand_equal_p (vals[1], vals[2], 0))
> !     {
> !       tree_vector_pattern pattern (*src1);
> !       /* Set TREE_OVERFLOW on the result if it was set for any of
> !        the values being merged.  */
> !       if (overflowed)
> !       pattern.base[1] = overflowed;
> !       if (!zero_step1_p)
> !       pattern.step = build_zero_cst (TREE_TYPE (pattern.step));
> !       dest->quick_push (pattern);
> !       return true;
> !     }
> !
> !   /* Option 2: use VALS[0] as the second base and handle the rest
> !      via a step.  In this case we must have nonnull steps (which
> !      indicates that using a step is valid).  */
> !   if (!src1->step || !src2->step)
> !     return false;
> !
> !   /* Check that VALS has a consistent step.  */
> !   wide_int step = wi::to_wide (vals[1]) - wi::to_wide (vals[0]);
> !   if (step != wi::to_wide (vals[2]) - wi::to_wide (vals[1]))
> !     return false;
> !
> !   /* Check that that step is in turn consistent with any existing one.  */
> !   if (!first_p)
>       {
> !       wide_int double_step = wi::lshift (step, 1);
> !       if (double_step != wi::to_wide (src1->step)
> !         || double_step != wi::to_wide (src2->step))
> !       return false;
> !     }
>
> !   /* The combination is valid.  */
> !   tree_vector_pattern pattern (*src1);
> !   /* Set TREE_OVERFLOW on the result if it was set for any of
> !      the values being merged.  */
> !   if (!overflowed || overflowed == vals[0])
> !     pattern.base[1] = vals[0];
> !   else
> !     pattern.base[1] = force_fit_type (TREE_TYPE (vals[0]),
> !                                     wi::to_wide (vals[0]), 0, true);
> !   pattern.step = wide_int_to_tree (TREE_TYPE (vals[0]), step);
> !   dest->quick_push (pattern);
> !   return true;
> ! }
>
> ! /* PATTERNS represents a constant of type TYPE.  Compress it into the
> !    canonical form, returning the new vector of patterns.  Use CUR and NEXT
> !    as temporary workspace.  */
> !
> ! static vec<tree_vector_pattern>
> ! compress_vector_patterns (vec<tree_vector_pattern> *cur,
> !                         vec<tree_vector_pattern> *next,
> !                         tree type, vec<tree_vector_pattern> patterns)
> ! {
> !   while (patterns.length () > 1)
> !     {
> !       unsigned int npatterns = patterns.length ();
> !       gcc_assert ((npatterns & 1) == 0);
> !       unsigned int step = npatterns / 2;
> !       cur->truncate (0);
> !       cur->reserve (step);
> !       bool first_p = npatterns * 2 == TYPE_VECTOR_SUBPARTS (type);
> !       for (unsigned int i = 0; i < step; ++i)
> !       if (!combine_patterns (cur, &patterns[i], &patterns[i + step],
> !                              first_p))
> !         return patterns;
> !       patterns = *cur;
> !       std::swap (cur, next);
> !     }
> !   return patterns;
> ! }

Wow, that looks complicated ;)  Which means it needs some more comments.

I wonder if avoiding all this for the special cases we like to handle by
providing vector_cst constructors for one and two pattern cases would
be best.  Or even more specialized, not exposing "patterns".

> ! /* Return true if PATTERNS has an overflow bit set.  */
> !
> ! static bool
> ! vector_overflow_p (vec<tree_vector_pattern> patterns)
> ! {
> !   unsigned int i;
> !   tree_vector_pattern *pattern;
> !   FOR_EACH_VEC_ELT (patterns, i, pattern)
> !     for (unsigned int j = 0; j < 2; ++j)
> !       if (CONSTANT_CLASS_P (pattern->base[j])
> !         && TREE_OVERFLOW (pattern->base[j]))
> !       return true;
> !   return false;
> ! }
> !
> ! /* Return true if PATTERNS represents a duplicate operation.  */
>
> ! static bool
> ! vector_duplicate_p (vec<tree_vector_pattern> patterns)
> ! {
> !   unsigned int i;
> !   tree_vector_pattern *pattern;
> !   FOR_EACH_VEC_ELT (patterns, i, pattern)
> !     {
> !       if (pattern->step && wi::to_wide (pattern->step) != 0)

I wonder if step == 0 should be canonicalized to NULL_TREE?

> !       return false;
> !       if (!operand_equal_p (pattern->base[0], pattern->base[1], 0))
> !       return false;
>       }
> +   return true;
> + }
> +
> + /* Return true if PATTERNS represents a vector series.  */
> +
> + static bool
> + vector_series_p (vec<tree_vector_pattern> patterns)
> + {
> +   unsigned int i;
> +   tree_vector_pattern *pattern;
> +   FOR_EACH_VEC_ELT (patterns, i, pattern)
> +     if (!pattern->step
> +       || (wi::to_wide (pattern->base[1]) - wi::to_wide (pattern->base[0])
> +           != wi::to_wide (pattern->step)))
> +       return false;
> +   return true;
> + }
> +
> + /* Build a VECTOR_CST of type TYPE using the patterns in PATTERNS,
> +    canonicalizing it first if necessary.  */
> +
> + tree
> + build_vector (tree type, vec<tree_vector_pattern> patterns MEM_STAT_DECL)
> + {
> +   auto_vec<tree_vector_pattern, 16> tmp1, tmp2;
> +   patterns = compress_vector_patterns (&tmp1, &tmp2, type, patterns);
> +   unsigned int npatterns = patterns.length ();
> +
> +   gcc_assert (pow2p_hwi (npatterns));
> +   bool overflow_p = vector_overflow_p (patterns);
> +   bool duplicate_p = vector_duplicate_p (patterns);
> +   bool series_p = vector_series_p (patterns);
> +   tree v = make_vector (exact_log2 (npatterns), duplicate_p, series_p);
> +   TREE_TYPE (v) = type;
> +   TREE_OVERFLOW (v) = overflow_p;
>
> !   memcpy (v->vector.patterns, patterns.address (),
> !         npatterns * sizeof (tree_vector_pattern));
>     return v;
>   }
>
>   /* Return a new VECTOR_CST node whose type is TYPE and whose values
> +    are given by ELTS.  */
> +
> + tree
> + build_vector (tree type, vec<tree> elts MEM_STAT_DECL)
> + {
> +   unsigned int nelts = elts.length ();
> +   gcc_assert (nelts == TYPE_VECTOR_SUBPARTS (type));
> +
> +   gcc_assert (pow2p_hwi (nelts));
> +   bool single_p = nelts == 1;
> +   unsigned int npatterns = single_p ? 1 : nelts / 2;
> +   auto_vec<tree_vector_pattern, 16> patterns (npatterns);
> +   for (unsigned int i = 0; i < npatterns; ++i)
> +     {
> +       tree_vector_pattern pattern;
> +       pattern.base[0] = elts[i];
> +       pattern.base[1] = elts[single_p ? i : i + npatterns];
> +       if (INTEGRAL_TYPE_P (TREE_TYPE (type))
> +         && TREE_CODE (pattern.base[0]) == INTEGER_CST
> +         && TREE_CODE (pattern.base[1]) == INTEGER_CST)
> +       pattern.step = wide_int_to_tree (TREE_TYPE (type),
> +                                        wi::to_wide (pattern.base[1])
> +                                        - wi::to_wide (pattern.base[0]));
> +       else
> +       pattern.step = NULL_TREE;

I wonder why given the simple representation with n/2 patterns
you don't use step == NULL_TREE unconditionally here.

Is there a target macro specifying the maximum target supported
vector length?  It might be nice to use that in the auto_vec <> size.

OTOH sometimes I really like

  tree_vector_pattern *p = XALLOCAVEC (npatterns);

more... (ok, __attribute__((vector_size(1048576))) might blow the stack...)

> +       patterns.quick_push (pattern);
> +     }
> +   return build_vector (type, patterns);
> + }
> +
> + /* Return a new VECTOR_CST node whose type is TYPE and whose values
>      are extracted from V, a vector of CONSTRUCTOR_ELT.  */
>
>   tree
> *************** build_opaque_vector_type (tree innertype
> *** 10353,10358 ****
> --- 10538,10581 ----
>     return cand;
>   }
>
> + /* Return the value of element I of VECTOR_CST T as a wide_int.  */
> +
> + wide_int
> + vector_cst_int_elt (const_tree t, unsigned int i)
> + {
> +   unsigned int npatterns = VECTOR_CST_NPATTERNS (t);
> +   if (i < npatterns)
> +     return wi::to_wide (VECTOR_CST_BASE (t, i, 0));
> +
> +   unsigned int pattern = i & (npatterns - 1);
> +   tree base = VECTOR_CST_BASE (t, pattern, 1);
> +   tree step = VECTOR_CST_STEP (t, pattern);
> +   if (i < npatterns * 2 || !step || wi::to_wide (step) == 0)
> +     return wi::to_wide (base);
> +
> +   unsigned int factor = (i >> VECTOR_CST_LOG2_NPATTERNS (t)) - 1;
> +   return wi::to_wide (base) + factor * wi::to_wide (step);
> + }
> +
> + /* Return the value of element I of VECTOR_CST T.  */
> +
> + tree
> + vector_cst_elt (const_tree t, unsigned int i)
> + {
> +   unsigned int npatterns = VECTOR_CST_NPATTERNS (t);
> +   if (i < npatterns)
> +     return VECTOR_CST_BASE (t, i, 0);
> +
> +   unsigned int pattern = i & (npatterns - 1);
> +   tree base = VECTOR_CST_BASE (t, pattern, 1);
> +   tree step = VECTOR_CST_STEP (t, pattern);
> +   if (i < npatterns * 2 || !step || wi::to_wide (step) == 0)
> +     return base;
> +
> +   unsigned int factor = (i >> VECTOR_CST_LOG2_NPATTERNS (t)) - 1;
> +   return wide_int_to_tree (TREE_TYPE (TREE_TYPE (t)),
> +                          wi::to_wide (base) + factor * wi::to_wide (step));
> + }
>
>   /* Given an initializer INIT, return TRUE if INIT is zero or some
>      aggregate of zeros.  Otherwise return FALSE.  */
> *************** drop_tree_overflow (tree t)
> *** 12447,12461 ****
>         if (TREE_OVERFLOW (TREE_IMAGPART (t)))
>         TREE_IMAGPART (t) = drop_tree_overflow (TREE_IMAGPART (t));
>       }
>     if (TREE_CODE (t) == VECTOR_CST)
> !     {
> !       for (unsigned i = 0; i < VECTOR_CST_NELTS (t); ++i)
> !       {
> !         tree& elt = VECTOR_CST_ELT (t, i);
> !         if (TREE_OVERFLOW (elt))
> !           elt = drop_tree_overflow (elt);
>         }
> !     }
>     return t;
>   }
>
> --- 12670,12686 ----
>         if (TREE_OVERFLOW (TREE_IMAGPART (t)))
>         TREE_IMAGPART (t) = drop_tree_overflow (TREE_IMAGPART (t));
>       }
> +
>     if (TREE_CODE (t) == VECTOR_CST)
> !     /* Only the base values can have an overflow bit set.  */
> !     for (unsigned i = 0; i < VECTOR_CST_NPATTERNS (t); ++i)
> !       for (unsigned int j = 0; j < 2; ++j)
> !       {
> !         tree *elt = &VECTOR_CST_BASE (t, i, j);
> !         if (TREE_OVERFLOW (*elt))
> !           *elt = drop_tree_overflow (*elt);
>         }
> !
>     return t;
>   }
>
> *************** test_labels ()
> *** 13954,13959 ****
> --- 14179,14350 ----
>     ASSERT_FALSE (FORCED_LABEL (label_decl));
>   }
>
> + /* Check that VECTOR_CST Y contains the elements in X.  */
> +
> + static void
> + check_vector_cst (vec<tree> x, tree y)
> + {
> +   for (unsigned int i = 0; i < x.length (); ++i)
> +     ASSERT_EQ (wi::to_wide (x[i]), wi::to_wide (vector_cst_elt (y, i)));
> + }
> +
> + /* Test the creation of VECTOR_CSTs.  */
> +
> + static void
> + test_vector_cst_patterns ()
> + {
> +   auto_vec<tree, 8> elements (8);
> +   elements.quick_grow (8);
> +   tree element_type = build_nonstandard_integer_type (16, true);
> +   tree vector_type = build_vector_type (element_type, 8);
> +
> +   /* Test a simple linear series with a base of 0 and a step of 1:
> +      { 0, 1, 2, 3, 4, 5, 6, 7 }.  */
> +   for (unsigned int i = 0; i < 8; ++i)
> +     elements[i] = build_int_cst (element_type, i);
> +   tree series_0_1 = build_vector (vector_type, elements);
> +   ASSERT_EQ (VECTOR_CST_NPATTERNS (series_0_1), 1);
> +   ASSERT_TRUE (integer_zerop (VECTOR_CST_BASE (series_0_1, 0, 0)));
> +   ASSERT_TRUE (integer_onep (VECTOR_CST_BASE (series_0_1, 0, 1)));
> +   ASSERT_TRUE (integer_onep (VECTOR_CST_STEP (series_0_1, 0)));
> +   ASSERT_FALSE (VECTOR_CST_DUPLICATE_P (series_0_1));
> +   ASSERT_TRUE (VECTOR_CST_SERIES_P (series_0_1));
> +   check_vector_cst (elements, series_0_1);
> +
> +   /* Try the same with the first element replaced by 100:
> +      { 100, 1, 2, 3, 4, 5, 6, 7 }.  */
> +   elements[0] = build_int_cst (element_type, 100);
> +   tree jump_series = build_vector (vector_type, elements);
> +   ASSERT_EQ (VECTOR_CST_NPATTERNS (jump_series), 1);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (jump_series, 0, 0)), 100);
> +   ASSERT_TRUE (integer_onep (VECTOR_CST_BASE (jump_series, 0, 1)));
> +   ASSERT_TRUE (integer_onep (VECTOR_CST_STEP (jump_series, 0)));
> +   ASSERT_FALSE (VECTOR_CST_DUPLICATE_P (jump_series));
> +   ASSERT_FALSE (VECTOR_CST_SERIES_P (jump_series));
> +   check_vector_cst (elements, jump_series);
> +
> +   /* Try a series that wraps around.
> +      { 100, 65531, 65532, 65533, 65534, 65535, 0, 1 }.  */
> +   for (unsigned int i = 1; i < 8; ++i)
> +     elements[i] = build_int_cst (element_type, (65530 + i) & 0xffff);
> +   tree wrap_series = build_vector (vector_type, elements);
> +   ASSERT_EQ (VECTOR_CST_NPATTERNS (wrap_series), 1);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (wrap_series, 0, 0)), 100);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (wrap_series, 0, 1)), 65531);
> +   ASSERT_TRUE (integer_onep (VECTOR_CST_STEP (wrap_series, 0)));
> +   ASSERT_FALSE (VECTOR_CST_DUPLICATE_P (wrap_series));
> +   ASSERT_FALSE (VECTOR_CST_SERIES_P (wrap_series));
> +   check_vector_cst (elements, wrap_series);
> +
> +   /* Try a downward series:
> +      { 100, 79, 78, 77, 76, 75, 75, 73 }.  */
> +   for (unsigned int i = 1; i < 8; ++i)
> +     elements[i] = build_int_cst (element_type, 80 - i);
> +   tree down_series = build_vector (vector_type, elements);
> +   ASSERT_EQ (VECTOR_CST_NPATTERNS (down_series), 1);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (down_series, 0, 0)), 100);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (down_series, 0, 1)), 79);
> +   ASSERT_TRUE (integer_minus_onep (VECTOR_CST_STEP (down_series, 0)));
> +   ASSERT_FALSE (VECTOR_CST_DUPLICATE_P (down_series));
> +   ASSERT_FALSE (VECTOR_CST_SERIES_P (down_series));
> +   check_vector_cst (elements, down_series);
> +
> +   /* Try two interleaved series with different bases and steps:
> +      { 100, 53, 66, 206, 62, 212, 58, 218 }.  */
> +   elements[1] = build_int_cst (element_type, 53);
> +   for (unsigned int i = 2; i < 8; i += 2)
> +     {
> +       elements[i] = build_int_cst (element_type, 70 - i * 2);
> +       elements[i + 1] = build_int_cst (element_type, 200 + i * 3);
> +     }
> +   tree mixed_series = build_vector (vector_type, elements);
> +   ASSERT_EQ (VECTOR_CST_NPATTERNS (mixed_series), 2);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (mixed_series, 0, 0)), 100);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (mixed_series, 0, 1)), 66);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_STEP (mixed_series, 0)), -4);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (mixed_series, 1, 0)), 53);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (mixed_series, 1, 1)), 206);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_STEP (mixed_series, 1)), 6);
> +   ASSERT_FALSE (VECTOR_CST_DUPLICATE_P (mixed_series));
> +   ASSERT_FALSE (VECTOR_CST_SERIES_P (mixed_series));
> +   check_vector_cst (elements, mixed_series);
> +
> +   /* Try a duplicated value:
> +      { 100, 100, 100, 100, 100, 100, 100, 100 }.  */
> +   for (unsigned int i = 1; i < 8; ++i)
> +     elements[i] = elements[0];
> +   tree dup1 = build_vector (vector_type, elements);
> +   ASSERT_EQ (VECTOR_CST_NPATTERNS (dup1), 1);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (dup1, 0, 0)), 100);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (dup1, 0, 1)), 100);
> +   ASSERT_TRUE (integer_zerop (VECTOR_CST_STEP (dup1, 0)));
> +   ASSERT_TRUE (VECTOR_CST_DUPLICATE_P (dup1));
> +   ASSERT_TRUE (VECTOR_CST_SERIES_P (dup1));
> +   check_vector_cst (elements, dup1);
> +
> +   /* Try an interleaved duplicated value:
> +      { 100, 55, 100, 55, 100, 55, 100, 55 }.  */
> +   elements[1] = build_int_cst (element_type, 55);
> +   for (unsigned int i = 2; i < 8; ++i)
> +     elements[i] = elements[i - 2];
> +   tree dup2 = build_vector (vector_type, elements);
> +   ASSERT_EQ (VECTOR_CST_NPATTERNS (dup2), 2);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (dup2, 0, 0)), 100);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (dup2, 0, 1)), 100);
> +   ASSERT_TRUE (integer_zerop (VECTOR_CST_STEP (dup2, 0)));
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (dup2, 1, 0)), 55);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (dup2, 1, 1)), 55);
> +   ASSERT_TRUE (integer_zerop (VECTOR_CST_STEP (dup2, 1)));
> +   ASSERT_TRUE (VECTOR_CST_DUPLICATE_P (dup2));
> +   ASSERT_TRUE (VECTOR_CST_SERIES_P (dup2));
> +   check_vector_cst (elements, dup2);
> +
> +   /* Try a duplicated value with 2 exceptions
> +      { 41, 97, 100, 55, 100, 55, 100, 55 }.  */
> +   elements[0] = build_int_cst (element_type, 41);
> +   elements[1] = build_int_cst (element_type, 97);
> +   tree jump_dup2 = build_vector (vector_type, elements);
> +   ASSERT_EQ (VECTOR_CST_NPATTERNS (jump_dup2), 2);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (jump_dup2, 0, 0)), 41);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (jump_dup2, 0, 1)), 100);
> +   ASSERT_TRUE (integer_zerop (VECTOR_CST_STEP (jump_dup2, 0)));
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (jump_dup2, 1, 0)), 97);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (jump_dup2, 1, 1)), 55);
> +   ASSERT_TRUE (integer_zerop (VECTOR_CST_STEP (jump_dup2, 1)));
> +   ASSERT_FALSE (VECTOR_CST_DUPLICATE_P (jump_dup2));
> +   ASSERT_FALSE (VECTOR_CST_SERIES_P (jump_dup2));
> +   check_vector_cst (elements, jump_dup2);
> +
> +   /* Try with and without a step
> +      { 41, 97, 100, 21, 100, 35, 100, 49 }.  */
> +   for (unsigned int i = 3; i < 8; i += 2)
> +     elements[i] = build_int_cst (element_type, i * 7);
> +   tree mixed2 = build_vector (vector_type, elements);
> +   ASSERT_EQ (VECTOR_CST_NPATTERNS (mixed2), 2);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (mixed2, 0, 0)), 41);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (mixed2, 0, 1)), 100);
> +   ASSERT_TRUE (integer_zerop (VECTOR_CST_STEP (mixed2, 0)));
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (mixed2, 1, 0)), 97);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_BASE (mixed2, 1, 1)), 21);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_STEP (mixed2, 1)), 14);
> +   ASSERT_FALSE (VECTOR_CST_DUPLICATE_P (mixed2));
> +   ASSERT_FALSE (VECTOR_CST_SERIES_P (mixed2));
> +   check_vector_cst (elements, mixed2);
> +
> +   /* Try a fully-general constant:
> +      { 41, 97, 100, 21, 100, 9990, 100, 49 }.  */
> +   elements[5] = build_int_cst (element_type, 9990);
> +   tree general = build_vector (vector_type, elements);
> +   ASSERT_EQ (VECTOR_CST_NPATTERNS (general), 4);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_STEP (general, 0)), 59);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_STEP (general, 1)), 9893);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_STEP (general, 2)), 0);
> +   ASSERT_EQ (wi::to_wide (VECTOR_CST_STEP (general, 3)), 28);
> +   ASSERT_FALSE (VECTOR_CST_DUPLICATE_P (general));
> +   ASSERT_TRUE (VECTOR_CST_SERIES_P (general));
> +   check_vector_cst (elements, general);
> + }
> +
>   /* Run all of the selftests within this file.  */
>
>   void
> *************** tree_c_tests ()
> *** 13962,13967 ****
> --- 14353,14359 ----
>     test_integer_constants ();
>     test_identifiers ();
>     test_labels ();
> +   test_vector_cst_patterns ();
>   }
>
>   } // namespace selftest
> Index: gcc/lto-streamer-out.c
> ===================================================================
> *** gcc/lto-streamer-out.c      2017-11-29 11:07:59.961993930 +0000
> --- gcc/lto-streamer-out.c      2017-11-29 11:08:00.185993912 +0000
> *************** #define DFS_follow_tree_edge(DEST) \
> *** 747,754 ****
>
>     if (CODE_CONTAINS_STRUCT (code, TS_VECTOR))
>       {
> !       for (unsigned i = 0; i < VECTOR_CST_NELTS (expr); ++i)
> !       DFS_follow_tree_edge (VECTOR_CST_ELT (expr, i));
>       }
>
>     if (CODE_CONTAINS_STRUCT (code, TS_COMPLEX))
> --- 747,758 ----
>
>     if (CODE_CONTAINS_STRUCT (code, TS_VECTOR))
>       {
> !       for (unsigned i = 0; i < VECTOR_CST_NPATTERNS (expr); ++i)
> !       {
> !         for (unsigned int j = 0; j < 2; ++j)
> !           DFS_follow_tree_edge (VECTOR_CST_BASE (expr, i, j));
> !         DFS_follow_tree_edge (VECTOR_CST_STEP (expr, i));
> !       }
>       }
>
>     if (CODE_CONTAINS_STRUCT (code, TS_COMPLEX))
> *************** #define visit(SIBLING) \
> *** 1195,1202 ****
>       }
>
>     if (CODE_CONTAINS_STRUCT (code, TS_VECTOR))
> !     for (unsigned i = 0; i < VECTOR_CST_NELTS (t); ++i)
> !       visit (VECTOR_CST_ELT (t, i));
>
>     if (CODE_CONTAINS_STRUCT (code, TS_COMPLEX))
>       {
> --- 1199,1210 ----
>       }
>
>     if (CODE_CONTAINS_STRUCT (code, TS_VECTOR))
> !     for (unsigned i = 0; i < VECTOR_CST_NPATTERNS (t); ++i)
> !       {
> !       for (unsigned int j = 0; j < 2; ++j)
> !         visit (VECTOR_CST_BASE (t, i, j));
> !       visit (VECTOR_CST_STEP (t, i));
> !       }
>
>     if (CODE_CONTAINS_STRUCT (code, TS_COMPLEX))
>       {
> Index: gcc/tree-streamer-out.c
> ===================================================================
> *** gcc/tree-streamer-out.c     2017-11-29 11:07:59.961993930 +0000
> --- gcc/tree-streamer-out.c     2017-11-29 11:08:00.186993912 +0000
> *************** write_ts_common_tree_pointers (struct ou
> *** 533,543 ****
>   static void
>   write_ts_vector_tree_pointers (struct output_block *ob, tree expr, bool ref_p)
>   {
> -   unsigned i;
>     /* Note that the number of elements for EXPR has already been emitted
>        in EXPR's header (see streamer_write_tree_header).  */
> !   for (i = 0; i < VECTOR_CST_NELTS (expr); ++i)
> !     stream_write_tree (ob, VECTOR_CST_ELT (expr, i), ref_p);
>   }
>
>
> --- 533,546 ----
>   static void
>   write_ts_vector_tree_pointers (struct output_block *ob, tree expr, bool ref_p)
>   {
>     /* Note that the number of elements for EXPR has already been emitted
>        in EXPR's header (see streamer_write_tree_header).  */
> !   for (unsigned int i = 0; i < VECTOR_CST_NPATTERNS (expr); ++i)
> !     {
> !       for (unsigned int j = 0; j < 2; ++j)
> !       stream_write_tree (ob, VECTOR_CST_BASE (expr, i, j), ref_p);
> !       stream_write_tree (ob, VECTOR_CST_STEP (expr, i), ref_p);
> !     }
>   }
>
>
> *************** streamer_write_tree_header (struct outpu
> *** 960,966 ****
>     else if (CODE_CONTAINS_STRUCT (code, TS_IDENTIFIER))
>       write_identifier (ob, ob->main_stream, expr);
>     else if (CODE_CONTAINS_STRUCT (code, TS_VECTOR))
> !     streamer_write_hwi (ob, VECTOR_CST_NELTS (expr));
>     else if (CODE_CONTAINS_STRUCT (code, TS_VEC))
>       streamer_write_hwi (ob, TREE_VEC_LENGTH (expr));
>     else if (CODE_CONTAINS_STRUCT (code, TS_BINFO))
> --- 963,975 ----
>     else if (CODE_CONTAINS_STRUCT (code, TS_IDENTIFIER))
>       write_identifier (ob, ob->main_stream, expr);
>     else if (CODE_CONTAINS_STRUCT (code, TS_VECTOR))
> !     {
> !       bitpack_d bp = bitpack_create (ob->main_stream);
> !       bp_pack_value (&bp, VECTOR_CST_LOG2_NPATTERNS (expr), 16);
> !       bp_pack_value (&bp, VECTOR_CST_DUPLICATE_P (expr), 1);
> !       bp_pack_value (&bp, VECTOR_CST_SERIES_P (expr), 1);
> !       streamer_write_bitpack (&bp);
> !     }
>     else if (CODE_CONTAINS_STRUCT (code, TS_VEC))
>       streamer_write_hwi (ob, TREE_VEC_LENGTH (expr));
>     else if (CODE_CONTAINS_STRUCT (code, TS_BINFO))
> Index: gcc/tree-streamer-in.c
> ===================================================================
> *** gcc/tree-streamer-in.c      2017-11-29 11:07:59.961993930 +0000
> --- gcc/tree-streamer-in.c      2017-11-29 11:08:00.186993912 +0000
> *************** streamer_alloc_tree (struct lto_input_bl
> *** 592,599 ****
>       }
>     else if (CODE_CONTAINS_STRUCT (code, TS_VECTOR))
>       {
> !       HOST_WIDE_INT len = streamer_read_hwi (ib);
> !       result = make_vector (len);
>       }
>     else if (CODE_CONTAINS_STRUCT (code, TS_BINFO))
>       {
> --- 592,602 ----
>       }
>     else if (CODE_CONTAINS_STRUCT (code, TS_VECTOR))
>       {
> !       bitpack_d bp = streamer_read_bitpack (ib);
> !       unsigned int log2_npatterns = bp_unpack_value (&bp, 16);
> !       unsigned int duplicate_p = bp_unpack_value (&bp, 1);
> !       unsigned int series_p = bp_unpack_value (&bp, 1);
> !       result = make_vector (log2_npatterns, duplicate_p, series_p);
>       }
>     else if (CODE_CONTAINS_STRUCT (code, TS_BINFO))
>       {
> *************** lto_input_ts_common_tree_pointers (struc
> *** 650,658 ****
>   lto_input_ts_vector_tree_pointers (struct lto_input_block *ib,
>                                    struct data_in *data_in, tree expr)
>   {
> !   unsigned i;
> !   for (i = 0; i < VECTOR_CST_NELTS (expr); ++i)
> !     VECTOR_CST_ELT (expr, i) = stream_read_tree (ib, data_in);
>   }
>
>
> --- 653,664 ----
>   lto_input_ts_vector_tree_pointers (struct lto_input_block *ib,
>                                    struct data_in *data_in, tree expr)
>   {
> !   for (unsigned int i = 0; i < VECTOR_CST_NPATTERNS (expr); ++i)
> !     {
> !       for (unsigned int j = 0; j < 2; ++j)
> !       VECTOR_CST_BASE (expr, i, j) = stream_read_tree (ib, data_in);
> !       VECTOR_CST_STEP (expr, i) = stream_read_tree (ib, data_in);
> !     }
>   }
>
>
> Index: gcc/fold-const.c
> ===================================================================
> *** gcc/fold-const.c    2017-11-29 11:07:59.961993930 +0000
> --- gcc/fold-const.c    2017-11-29 11:08:00.184993912 +0000
> *************** fold_ternary_loc (location_t loc, enum t
> *** 11610,11618 ****
>                   unsigned int nelts = VECTOR_CST_NELTS (arg0);
>                   auto_vec<tree, 32> elts (nelts);
>                   elts.quick_grow (nelts);
> !                 memcpy (&elts[0], VECTOR_CST_ELTS (arg0),
> !                         sizeof (tree) * nelts);
> !                 elts[k] = arg1;
>                   return build_vector (type, elts);
>                 }
>             }
> --- 11610,11617 ----
>                   unsigned int nelts = VECTOR_CST_NELTS (arg0);
>                   auto_vec<tree, 32> elts (nelts);
>                   elts.quick_grow (nelts);
> !                 for (unsigned int i = 0; i < VECTOR_CST_NELTS (arg0); ++i)
> !                   elts[i] = (i == k ? arg1 : VECTOR_CST_ELT (arg0, i));
>                   return build_vector (type, elts);
>                 }
>             }
> Index: gcc/lto/lto.c
> ===================================================================
> *** gcc/lto/lto.c       2017-11-29 11:07:59.961993930 +0000
> --- gcc/lto/lto.c       2017-11-29 11:08:00.185993912 +0000
> *************** #define compare_values(X) \
> *** 1065,1070 ****
> --- 1065,1077 ----
>                         TREE_FIXED_CST_PTR (t1), TREE_FIXED_CST_PTR (t2)))
>         return false;
>
> +   if (CODE_CONTAINS_STRUCT (code, TS_VECTOR))
> +     {
> +       compare_values (VECTOR_CST_LOG2_NPATTERNS);
> +       compare_values (VECTOR_CST_DUPLICATE_P);
> +       compare_values (VECTOR_CST_SERIES_P);
> +     }
> +
>     if (CODE_CONTAINS_STRUCT (code, TS_DECL_COMMON))
>       {
>         compare_values (DECL_MODE);
> *************** #define compare_tree_edges(E1, E2) \
> *** 1281,1291 ****
>
>     if (CODE_CONTAINS_STRUCT (code, TS_VECTOR))
>       {
> -       unsigned i;
>         /* Note that the number of elements for EXPR has already been emitted
>          in EXPR's header (see streamer_write_tree_header).  */
> !       for (i = 0; i < VECTOR_CST_NELTS (t1); ++i)
> !       compare_tree_edges (VECTOR_CST_ELT (t1, i), VECTOR_CST_ELT (t2, i));
>       }
>
>     if (CODE_CONTAINS_STRUCT (code, TS_COMPLEX))
> --- 1288,1303 ----
>
>     if (CODE_CONTAINS_STRUCT (code, TS_VECTOR))
>       {
>         /* Note that the number of elements for EXPR has already been emitted
>          in EXPR's header (see streamer_write_tree_header).  */
> !       for (unsigned int i = 0; i < VECTOR_CST_NPATTERNS (t1); ++i)
> !       {
> !         for (unsigned int j = 0; j < 2; ++j)
> !           compare_tree_edges (VECTOR_CST_BASE (t1, i, j),
> !                               VECTOR_CST_BASE (t2, i, j));
> !         compare_tree_edges (VECTOR_CST_STEP (t1, i),
> !                             VECTOR_CST_STEP (t2, i));
> !       }
>       }
>
>     if (CODE_CONTAINS_STRUCT (code, TS_COMPLEX))



More information about the Gcc-patches mailing list