On Thu, Nov 30, 2017 at 2:18 PM, Richard Sandiford
<richard.sandif...@linaro.org> wrote:
> Richard Sandiford <richard.sandif...@linaro.org> writes:
>> Richard Biener <richard.guent...@gmail.com> writes:
>>> On Wed, Nov 29, 2017 at 12:57 PM, Richard Sandiford
>>> <richard.sandif...@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)?
>>
>> Right. The rtl and vec_perm_indices parts don't have this restriction,
>> since some ports do define non-power-of-2 vectors for internal use.
>> The problem is that, since VECTOR_CSTs are used by the FE, we need
>> to support all valid vector lengths without blowing the 16-bit field.
>> Using the same style of representation as TYPE_VECTOR_SUBPARTS seemed
>> like the safest way of doing that.
>>
>>> I wonder if there exists a vector where say a three-pattern
>>> interleaving would be smaller than a four-pattern one?
>>
>> Only in the non-power-of-2 case.
>>
>>> 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 :/
>>
>> I wondered about keeping it as an array of trees and tacking the
>> steps onto the end as an optional addition. But the idea is that
>> tree_vector_pattern becomes the preferred way of handling constant
>> vectors, if it can be used, so it seemed neater to use in the tree
>> node too.
>
> In the end it seemed better to encode the first NPATTERNS * N
> elements of the vector, where:
>
> - N==3 if at least one pattern needs a step; otherwise
> - N==2 if at least one pattern has different BASE0s and BASE1s; otherwise
> - N==1 (i.e. the vector is a repeated sequence of NPATTERNS elements)
>
> So effectively all we're doing for the constant-length case is
> reducing the number of elements that need to be stored and processed
> (once code is converted to use the new routines).
>
> The patch below does this. It also introduces a new class
> vector_builder<T> for building vectors of Ts, with a derived
> tree_vector_builder specifically for trees. This allows the
> compression code to be shared between representations and also
> avoids hard-coding the auto_vec<> count everywhere.
>
> I've also fixed the selftests to get the actual and expected values
> the right way round (thanks David for noticing that).
>
> What do you think? Does this look better?
Yes! This is ok for trunk.
Thanks,
Richard.
> Thanks,
> Richard
>
>
> 2017-11-30 Richard Sandiford <richard.sandif...@arm.com>
>
> gcc/
> * doc/generic.texi (VECTOR_CST): Describe new representation of
> vector constants.
> * vector-builder.h: New file.
> * tree-vector-builder.h: Likewise.
> * tree-vector-builder.c: Likewise.
> * Makefile.in (OBJS): Add tree-vector-builder.o.
> * 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): Change the number of elements to
> vector_cst_encoded_nelts.
> * 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_NELTS_PER_PATTERN, VECTOR_CST_DUPLICATE_P): Likewise.
> (VECTOR_CST_STRIDED_P, VECTOR_CST_ENCODED_ELTS): Likewise.
> (VECTOR_CST_ENCODED_ELT): Likewise.
> (vector_cst_encoded_nelts): New function.
> (make_vector): Take the values of VECTOR_CST_LOG2_NPATTERNS and
> VECTOR_CST_NELTS_PER_PATTERN as arguments.
> (vector_cst_int_elt, vector_cst_elt): Declare.
> * tree.c: Include tree-vector-builder.h.
> (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 and
> VECTOR_CST_NELTS_PER_PATTERN as arguments.
> (build_vector): Use tree_vector_builder.
> (vector_cst_int_elt, vector_cst_elt): New functions.
> (drop_tree_overflow): For VECTOR_CST, drop the TREE_OVERFLOW from the
> encoded elements and then create the vector in the canonical form.
> (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-30 13:07:23.752425675 +0000
> +++ gcc/doc/generic.texi 2017-11-30 13:07:24.028415186 +0000
> @@ -1084,10 +1084,64 @@ These nodes are used to represent comple
> 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}.
> +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 has the form:
> +
> +@smallexample
> +@{ @var{base0}, @var{base1}, @var{base1} + @var{step}, @var{base1} +
> @var{step} * 2, @dots{} @}
> +@end smallexample
> +
> +The first three elements in each pattern are enough to determine the
> +values of other elements. However, if all @var{step}s are zero,
> +only the first two elements are needed. If in addition each @var{base1}
> +is equal to the corresponding @var{base0}, only the first element in
> +each pattern is needed. The number of encoded elements per pattern
> +is given by @samp{VECTOR_CST_NELTS_PER_PATTERN (@var{v})}.
> +
> +For example, the constant:
> +
> +@smallexample
> +@{ 0, 1, 2, 6, 3, 8, 4, 10, 5, 12, 6, 14, 7, 16, 8, 18 @}
> +@end smallexample
> +
> +is encoded using the interleaved sequences:
> +
> +@smallexample
> +@{ 0, 2, 3, 4, 5, 6, 7, 8 @}
> +@{ 1, 6, 8, 10, 12, 14, 16, 18 @}
> +@end smallexample
> +
> +where the sequences are represented by the following patterns:
> +
> +@smallexample
> +@var{base0} == 0, @var{base1} == 2, @var{step} == 1
> +@var{base0} == 1, @var{base1} == 6, @var{step} == 2
> +@end smallexample
> +
> +In this case:
> +
> +@smallexample
> +VECTOR_CST_NPATTERNS (@var{v}) == 2
> +VECTOR_CST_NELTS_PER_PATTERN (@var{v}) == 3
> +@end smallexample
> +
> +The vector is therefore encoded using the first 6 elements, with the
> +remaining 10 elements being implicit extensions of them.
> +
> +@samp{VECTOR_CST_DUPLICATE_P (@var{v})} is true if @var{v} simply
> +contains repeated instances of @samp{VECTOR_CST_NPATTERNS (@var{v})}
> +values. This is a shorthand for testing
> +@samp{VECTOR_CST_NELTS_PER_PATTERN (@var{v}) == 1}.
> +
> +@samp{VECTOR_CST_STEPPED_P (@var{v})} is true if at least one
> +pattern in @var{v} has a nonzero step. This is a shorthand for
> +testing @samp{VECTOR_CST_NELTS_PER_PATTERN (@var{v}) == 3}.
> +
> +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/vector-builder.h
> ===================================================================
> --- /dev/null 2017-11-30 11:13:00.800636184 +0000
> +++ gcc/vector-builder.h 2017-11-30 13:07:24.033414996 +0000
> @@ -0,0 +1,372 @@
> +/* A class for building vector constant patterns.
> + Copyright (C) 2017 Free Software Foundation, Inc.
> +
> +This file is part of GCC.
> +
> +GCC is free software; you can redistribute it and/or modify it under
> +the terms of the GNU General Public License as published by the Free
> +Software Foundation; either version 3, or (at your option) any later
> +version.
> +
> +GCC is distributed in the hope that it will be useful, but WITHOUT ANY
> +WARRANTY; without even the implied warranty of MERCHANTABILITY or
> +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
> +for more details.
> +
> +You should have received a copy of the GNU General Public License
> +along with GCC; see the file COPYING3. If not see
> +<http://www.gnu.org/licenses/>. */
> +
> +#ifndef GCC_VECTOR_BUILDER_H
> +#define GCC_VECTOR_BUILDER_H
> +
> +/* This class is a wrapper around auto_vec<T> for building vectors of T.
> + It aims to encode each vector as npatterns interleaved patterns,
> + where each pattern represents a sequence:
> +
> + { BASE0, BASE1, BASE1 + STEP, BASE1 + STEP*2, BASE1 + STEP*3, ... }
> +
> + The first three elements in each pattern provide enough information
> + to derive the other elements. If all patterns have a STEP of zero,
> + we only need to encode the first two elements in each pattern.
> + If BASE1 is also equal to BASE0 for all patterns, we only need to
> + encode the first element in each pattern. The number of encoded
> + elements per pattern is given by nelts_per_pattern.
> +
> + The class can be used in two ways:
> +
> + 1. It can be used to build a full image of the vector, which is then
> + canonicalized. In this case npatterns is initially the number of
> + elements in the vector and nelts_per_pattern is initially 1.
> +
> + 2. It can be used to build a vector that already has a known encoding.
> + This is preferred since it is more efficient and copes with
> + variable-length vectors. The class then canonicalizes the encoding
> + to a simpler form if possible.
> +
> + Derived classes provide this functionality for specific Ts.
> + The "Derived *" arguments to some functions are pointers to the
> + derived class, which needs to provide the following interface:
> +
> + bool equal_p (unsigned int i1, unsigned int i2) const;
> +
> + Return true if elements I1 and I2 are equal.
> +
> + bool allow_steps_p () const;
> +
> + Return true if a stepped representation is OK. We don't allow
> + linear series for anything other than integers, to avoid problems
> + with rounding.
> +
> + bool integral_p (unsigned int i) const;
> +
> + Return true if element I can be interpreted as an integer.
> +
> + StepType step (unsigned int i1, unsigned int i2) const;
> +
> + Return the value of element I2 minus the value of element I1,
> + given integral_p (I1) && integral_p (I2). There is no fixed
> + choice of StepType.
> +
> + bool can_elide_p (unsigned int i) const;
> +
> + Return true if we can drop element I, even if the retained
> + elements are different. This is provided for TREE_OVERFLOW
> + handling.
> +
> + void note_representative (unsigned int i1, unsigned int i2);
> +
> + Record that I2 is being elided and that I1 is the last encoded
> + element for the containing pattern. This is again provided
> + for TREE_OVERFLOW handling. */
> +
> +template<typename T>
> +class vector_builder : public auto_vec<T, 32>
> +{
> +public:
> + vector_builder (unsigned int, unsigned int, unsigned int);
> + vector_builder (const vector_builder &);
> +
> + unsigned int full_nelts () const { return m_full_nelts; }
> + unsigned int npatterns () const { return m_npatterns; }
> + unsigned int nelts_per_pattern () const { return m_nelts_per_pattern; }
> + unsigned int encoded_nelts () const;
> + bool encoded_full_vector_p () const;
> +
> + void reshape (unsigned int, unsigned int);
> +
> +protected:
> + template<typename Derived>
> + void reshape (Derived *, unsigned int, unsigned int);
> + template<typename Derived>
> + bool repeating_sequence_p (Derived *, unsigned int, unsigned int,
> + unsigned int);
> + template<typename Derived>
> + bool stepped_sequence_p (Derived *, unsigned int, unsigned int,
> + unsigned int);
> + template<typename Derived>
> + bool try_npatterns (Derived *, unsigned int);
> + template<typename Derived>
> + void finalize (Derived *);
> +
> +private:
> + vector_builder &operator= (const vector_builder &);
> +
> + unsigned int m_full_nelts;
> + unsigned int m_npatterns;
> + unsigned int m_nelts_per_pattern;
> +};
> +
> +/* Initialize a vector_builder for a vector that has FULL_NELTS elements.
> + Initially encode it using NPATTERNS patterns with NELTS_PER_PATTERN
> + each. */
> +
> +template<typename T>
> +inline
> +vector_builder<T>::vector_builder (unsigned int full_nelts,
> + unsigned int npatterns,
> + unsigned int nelts_per_pattern)
> + : auto_vec<T, 32> (npatterns * nelts_per_pattern),
> + m_full_nelts (full_nelts),
> + m_npatterns (npatterns),
> + m_nelts_per_pattern (nelts_per_pattern)
> +{}
> +
> +/* Copy constructor. */
> +
> +template<typename T>
> +inline
> +vector_builder<T>::vector_builder (const vector_builder &other)
> + : auto_vec<T, 32> (other.length ()),
> + m_full_nelts (other.m_full_nelts),
> + m_npatterns (other.m_npatterns),
> + m_nelts_per_pattern (other.m_nelts_per_pattern)
> +{
> + this->splice (other);
> +}
> +
> +/* Return the number of elements that are explicitly encoded. The vec
> + starts with these explicitly-encoded elements and may contain additional
> + elided elements. */
> +
> +template<typename T>
> +inline unsigned int
> +vector_builder<T>::encoded_nelts () const
> +{
> + return m_npatterns * m_nelts_per_pattern;
> +}
> +
> +/* Return true if every element of the vector is explicitly encoded. */
> +
> +template<typename T>
> +inline bool
> +vector_builder<T>::encoded_full_vector_p () const
> +{
> + return m_npatterns * m_nelts_per_pattern == m_full_nelts;
> +}
> +
> +/* Change the encoding to NPATTERNS patterns of NELTS_PER_PATTERN each,
> + but without changing the underlying vector. We explicitly don't
> + truncate the vec here since callers might want to refer to the
> + elided elements. */
> +
> +template<typename T>
> +inline void
> +vector_builder<T>::reshape (unsigned int npatterns,
> + unsigned int nelts_per_pattern)
> +{
> + m_npatterns = npatterns;
> + m_nelts_per_pattern = nelts_per_pattern;
> +}
> +
> +/* Likewise, but invoke DERIVED->note_representative for each elided
> + element. */
> +
> +template<typename T>
> +template<typename Derived>
> +inline void
> +vector_builder<T>::reshape (Derived *derived, unsigned int npatterns,
> + unsigned int nelts_per_pattern)
> +{
> + unsigned int old_encoded_nelts = encoded_nelts ();
> + reshape (npatterns, nelts_per_pattern);
> + unsigned int new_encoded_nelts = encoded_nelts ();
> + unsigned int next = new_encoded_nelts - m_npatterns;
> + for (unsigned int i = new_encoded_nelts; i < old_encoded_nelts; ++i)
> + {
> + derived->note_representative (next, i);
> + next += 1;
> + if (next == new_encoded_nelts)
> + next -= m_npatterns;
> + }
> +}
> +
> +/* Return true if elements [START, END) contain a repeating sequence of
> + STEP elements. */
> +
> +template<typename T>
> +template<typename Derived>
> +bool
> +vector_builder<T>::repeating_sequence_p (Derived *derived, unsigned int
> start,
> + unsigned int end, unsigned int step)
> +{
> + for (unsigned int i = start; i < end - step; ++i)
> + if (!derived->equal_p (i, i + step))
> + return false;
> + return true;
> +}
> +
> +/* Return true if elements [START, END) contain STEP interleaved linear
> + series. */
> +
> +template<typename T>
> +template<typename Derived>
> +bool
> +vector_builder<T>::stepped_sequence_p (Derived *derived, unsigned int start,
> + unsigned int end, unsigned int step)
> +{
> + if (!derived->allow_steps_p ())
> + return false;
> +
> + for (unsigned int i3 = start + step * 2; i3 < end; ++i3)
> + {
> + unsigned int i2 = i3 - step;
> + unsigned int i1 = i2 - step;
> +
> + if (!derived->integral_p (i1)
> + || !derived->integral_p (i2)
> + || !derived->integral_p (i3))
> + return false;
> +
> + if (derived->step (i1, i2) != derived->step (i2, i3))
> + return false;
> +
> + if (!derived->can_elide_p (i3))
> + return false;
> + }
> + return true;
> +}
> +
> +/* Try to change the number of encoded patterns to NPATTERNS, returning
> + true on success. */
> +
> +template<typename T>
> +template<typename Derived>
> +bool
> +vector_builder<T>::try_npatterns (Derived *derived, unsigned int npatterns)
> +{
> + if (m_nelts_per_pattern == 1)
> + {
> + /* See whether NPATTERNS is valid with the current
> 1-element-per-pattern
> + encoding. */
> + if (repeating_sequence_p (derived, 0, encoded_nelts (), npatterns))
> + {
> + reshape (derived, npatterns, 1);
> + return true;
> + }
> +
> + /* We can only increase the number of elements per pattern if all
> + elements are still encoded explicitly. */
> + if (!encoded_full_vector_p ())
> + return false;
> + }
> +
> + if (m_nelts_per_pattern <= 2)
> + {
> + /* See whether NPATTERNS is valid with a 2-element-per-pattern
> + encoding. */
> + if (repeating_sequence_p (derived, npatterns, encoded_nelts (),
> + npatterns))
> + {
> + reshape (derived, npatterns, 2);
> + return true;
> + }
> +
> + /* We can only increase the number of elements per pattern if all
> + elements are still encoded explicitly. */
> + if (!encoded_full_vector_p ())
> + return false;
> + }
> +
> + if (m_nelts_per_pattern <= 3)
> + {
> + /* See whether we have NPATTERNS interleaved linear series,
> + giving a 3-element-per-pattern encoding. */
> + if (stepped_sequence_p (derived, npatterns, encoded_nelts (),
> npatterns))
> + {
> + reshape (derived, npatterns, 3);
> + return true;
> + }
> + return false;
> + }
> +
> + gcc_unreachable ();
> +}
> +
> +/* Canonicalize the encoding. */
> +
> +template<typename T>
> +template<typename Derived>
> +void
> +vector_builder<T>::finalize (Derived *derived)
> +{
> + /* Try to whittle down the number of elements per pattern. That is:
> +
> + 1. If we have stepped patterns whose steps are all 0, reduce the
> + number of elements per pattern from 3 to 2.
> +
> + 2. If we have background fill values that are the same as the
> + foreground values, reduce the number of elements per pattern
> + from 2 to 1. */
> + while (m_nelts_per_pattern > 1
> + && repeating_sequence_p (derived, encoded_nelts () - m_npatterns * 2,
> + encoded_nelts (), m_npatterns))
> + /* The last two sequences of M_NPATTERNS elements are equal,
> + so remove the last one. */
> + reshape (derived, m_npatterns, m_nelts_per_pattern - 1);
> +
> + /* Try to halve the number of patterns while doing so gives a valid
> pattern.
> +
> + Each halving step tries to keep the number of elements per pattern
> + the same. If that isn't possible, and if all elements are still
> + explicitly encoded, the halving step can instead increase the number
> + of elements per pattern.
> +
> + E.g. for:
> +
> + { 0, 2, 3, 4, 5, 6, 7, 8 } npatterns == 8 full_nelts == 8
> +
> + we first realize that the second half of the sequence is not equal
> + to the first, so we cannot maintain 1 element per pattern for
> + npatterns == 4. Instead we halve the number of patterns and double
> + the number of elements per pattern, treating this as a "foreground"
> + { 0, 2, 3, 4 } against a "background" of { 5, 6, 7, 8 | 5, 6, 7, 8 ...
> }:
> +
> + { 0, 2, 3, 4 | 5, 6, 7, 8 } npatterns == 4
> +
> + Next we realize that this is *not* a foreround of { 0, 2 } against
> + a background of { 3, 4 | 3, 4 ... }, so the only remaining option
> + for reducing the number of patterns is to use a foreground of { 0, 2 }
> + against a stepped background of { 1, 2 | 3, 4 | 5, 6 ... }. This is
> + valid because we still haven't elided any elements:
> +
> + { 0, 2 | 3, 4 | 5, 6 } npatterns == 2
> +
> + This in turn can be reduced to a foreground of { 0 } against a stepped
> + background of { 1 | 2 | 3 ... }:
> +
> + { 0 | 2 | 3 } npatterns == 1
> +
> + This last step would not have been possible for:
> +
> + { 0, 0 | 3, 4 | 5, 6 } npatterns == 2. */
> + while ((m_npatterns & 1) == 0
> + && try_npatterns (derived, m_npatterns / 2))
> + continue;
> +
> + /* At present this code doesn't (need to) cope with vector lengths
> + that are not a power of 2. */
> + gcc_assert (pow2p_hwi (m_npatterns));
> +}
> +
> +#endif
> Index: gcc/tree-vector-builder.h
> ===================================================================
> --- /dev/null 2017-11-30 11:13:00.800636184 +0000
> +++ gcc/tree-vector-builder.h 2017-11-30 13:07:24.029415148 +0000
> @@ -0,0 +1,48 @@
> +/* A class for building vector tree constants.
> + Copyright (C) 2017 Free Software Foundation, Inc.
> +
> +This file is part of GCC.
> +
> +GCC is free software; you can redistribute it and/or modify it under
> +the terms of the GNU General Public License as published by the Free
> +Software Foundation; either version 3, or (at your option) any later
> +version.
> +
> +GCC is distributed in the hope that it will be useful, but WITHOUT ANY
> +WARRANTY; without even the implied warranty of MERCHANTABILITY or
> +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
> +for more details.
> +
> +You should have received a copy of the GNU General Public License
> +along with GCC; see the file COPYING3. If not see
> +<http://www.gnu.org/licenses/>. */
> +
> +#ifndef GCC_TREE_VECTOR_BUILDER_H
> +#define GCC_TREE_VECTOR_BUILDER_H
> +
> +#include "vector-builder.h"
> +
> +/* This class is used to build VECTOR_CSTs from a sequence of elements.
> + See vector_builder for more details. */
> +class tree_vector_builder : public vector_builder<tree>
> +{
> + friend class vector_builder<tree>;
> +
> +public:
> + tree_vector_builder (tree, unsigned int, unsigned int);
> + tree build ();
> +
> + static tree_vector_builder unary (tree, bool);
> +
> +private:
> + bool equal_p (unsigned int, unsigned int) const;
> + bool allow_steps_p () const;
> + bool integral_p (unsigned int) const;
> + wide_int step (unsigned int, unsigned int) const;
> + bool can_elide_p (unsigned int) const;
> + void note_representative (unsigned int, unsigned int);
> +
> + tree m_type;
> +};
> +
> +#endif
> Index: gcc/tree-vector-builder.c
> ===================================================================
> --- /dev/null 2017-11-30 11:13:00.800636184 +0000
> +++ gcc/tree-vector-builder.c 2017-11-30 13:07:24.029415148 +0000
> @@ -0,0 +1,131 @@
> +/* A class for building vector tree constants.
> + Copyright (C) 2017 Free Software Foundation, Inc.
> +
> +This file is part of GCC.
> +
> +GCC is free software; you can redistribute it and/or modify it under
> +the terms of the GNU General Public License as published by the Free
> +Software Foundation; either version 3, or (at your option) any later
> +version.
> +
> +GCC is distributed in the hope that it will be useful, but WITHOUT ANY
> +WARRANTY; without even the implied warranty of MERCHANTABILITY or
> +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
> +for more details.
> +
> +You should have received a copy of the GNU General Public License
> +along with GCC; see the file COPYING3. If not see
> +<http://www.gnu.org/licenses/>. */
> +
> +#include "config.h"
> +#include "system.h"
> +#include "coretypes.h"
> +#include "tree-vector-builder.h"
> +#include "tree.h"
> +#include "fold-const.h"
> +
> +/* Create a new builder for a vector of type TYPE. Initially encode the
> + value as NPATTERNS interleaved patterns with NELTS_PER_PATTERN elements
> + each. */
> +
> +tree_vector_builder::tree_vector_builder (tree type, unsigned int npatterns,
> + unsigned int nelts_per_pattern)
> + : vector_builder<tree> (TYPE_VECTOR_SUBPARTS (type), npatterns,
> + nelts_per_pattern),
> + m_type (type)
> +{
> +}
> +
> +/* Create a new builder for a unary operation on VECTOR_CST T.
> + ALLOW_STEPPED_P is true if the operation can handle stepped encodings
> + directly, without having to expand the full sequence. */
> +
> +tree_vector_builder
> +tree_vector_builder::unary (tree t, bool allow_stepped_p)
> +{
> + tree type = TREE_TYPE (t);
> + unsigned int npatterns = VECTOR_CST_NPATTERNS (t);
> + unsigned int nelts_per_pattern = VECTOR_CST_NELTS_PER_PATTERN (t);
> + if (!allow_stepped_p && nelts_per_pattern > 2)
> + {
> + npatterns = TYPE_VECTOR_SUBPARTS (type);
> + nelts_per_pattern = 1;
> + }
> + return tree_vector_builder (type, npatterns, nelts_per_pattern);
> +}
> +
> +/* Return true if elements I1 and I2 are equal. */
> +
> +inline bool
> +tree_vector_builder::equal_p (unsigned int i1, unsigned int i2) const
> +{
> + return operand_equal_p ((*this)[i1], (*this)[i2], 0);
> +}
> +
> +/* Return true if a stepped representation is OK. We don't allow
> + linear series for anything other than integers, to avoid problems
> + with rounding. */
> +
> +inline bool
> +tree_vector_builder::allow_steps_p () const
> +{
> + return INTEGRAL_TYPE_P (TREE_TYPE (m_type));
> +}
> +
> +/* Return true if element I can be interpreted as an integer. */
> +
> +inline bool
> +tree_vector_builder::integral_p (unsigned int i) const
> +{
> + return TREE_CODE ((*this)[i]) == INTEGER_CST;
> +}
> +
> +/* Return the value of element I2 minus the value of element I1.
> + Both elements are known to be INTEGER_CSTs. */
> +
> +inline wide_int
> +tree_vector_builder::step (unsigned int i1, unsigned int i2) const
> +{
> + return wi::to_wide ((*this)[i2]) - wi::to_wide ((*this)[i1]);
> +}
> +
> +/* Return true if we can drop element I, even if the retained elements
> + are different. Return false if this would mean losing overflow
> + information. */
> +
> +inline bool
> +tree_vector_builder::can_elide_p (unsigned int i) const
> +{
> + tree elt = (*this)[i];
> + return !CONSTANT_CLASS_P (elt) || !TREE_OVERFLOW (elt);
> +}
> +
> +/* Record that I2 is being elided and that I1 is the last encoded element
> + for the containing pattern. */
> +
> +inline void
> +tree_vector_builder::note_representative (unsigned int i1, unsigned int i2)
> +{
> + tree elt2 = (*this)[i2];
> + if (CONSTANT_CLASS_P (elt2) && TREE_OVERFLOW (elt2))
> + {
> + tree elt1 = (*this)[i1];
> + gcc_assert (operand_equal_p (elt1, elt2, 0));
> + if (!TREE_OVERFLOW (elt2))
> + (*this)[i1] = elt2;
> + }
> +}
> +
> +/* Return a VECTOR_CST for the current constant. */
> +
> +tree
> +tree_vector_builder::build ()
> +{
> + finalize (this);
> + gcc_assert (pow2p_hwi (npatterns ()));
> + tree v = make_vector (exact_log2 (npatterns ()), nelts_per_pattern ());
> + TREE_TYPE (v) = m_type;
> + memcpy (VECTOR_CST_ENCODED_ELTS (v), address (),
> + encoded_nelts () * sizeof (tree));
> + return v;
> +}
> Index: gcc/Makefile.in
> ===================================================================
> --- gcc/Makefile.in 2017-11-29 11:06:34.324730917 +0000
> +++ gcc/Makefile.in 2017-11-30 13:07:24.027415224 +0000
> @@ -1568,6 +1568,7 @@ OBJS = \
> tree-vect-loop-manip.o \
> tree-vect-slp.o \
> tree-vectorizer.o \
> + tree-vector-builder.o \
> tree-vrp.o \
> tree.o \
> typed-splay-tree.o \
> Index: gcc/tree.def
> ===================================================================
> --- gcc/tree.def 2017-11-30 13:07:23.752425675 +0000
> +++ gcc/tree.def 2017-11-30 13:07:24.032415034 +0000
> @@ -301,7 +301,7 @@ DEFTREECODE (FIXED_CST, "fixed_cst", tcc
> whose contents are other constant nodes. */
> DEFTREECODE (COMPLEX_CST, "complex_cst", tcc_constant, 0)
>
> -/* Contents are in VECTOR_CST_ELTS field. */
> +/* 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-30 13:07:23.752425675 +0000
> +++ gcc/tree-core.h 2017-11-30 13:07:24.029415148 +0000
> @@ -976,8 +976,17 @@ struct GTY(()) tree_base {
> /* 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;
> + /* This field is only used with VECTOR_CST. */
> + struct {
> + /* The value of VECTOR_CST_LOG2_NPATTERNS. */
> + unsigned int log2_npatterns : 8;
> +
> + /* The value of VECTOR_CST_NELTS_PER_PATTERN. */
> + unsigned int nelts_per_pattern : 8;
> +
> + /* For future expansion. */
> + unsigned int unused : 16;
> + } vector_cst;
>
> /* SSA version number. This field is only used with SSA_NAME. */
> unsigned int version;
> @@ -1333,7 +1342,7 @@ struct GTY(()) tree_complex {
>
> struct GTY(()) tree_vector {
> struct tree_typed typed;
> - tree GTY ((length ("VECTOR_CST_NELTS ((tree) &%h)"))) elts[1];
> + tree GTY ((length ("vector_cst_encoded_nelts ((tree) &%h)"))) elts[1];
> };
>
> struct GTY(()) tree_identifier {
> Index: gcc/tree.h
> ===================================================================
> --- gcc/tree.h 2017-11-30 13:07:23.752425675 +0000
> +++ gcc/tree.h 2017-11-30 13:07:24.033414996 +0000
> @@ -1012,10 +1012,24 @@ #define TREE_STRING_POINTER(NODE) \
> #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])
> +/* 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_NELTS_PER_PATTERN(NODE) \
> + (VECTOR_CST_CHECK (NODE)->base.u.vector_cst.nelts_per_pattern)
> +#define VECTOR_CST_DUPLICATE_P(NODE) \
> + (VECTOR_CST_NELTS_PER_PATTERN (NODE) == 1)
> +#define VECTOR_CST_STEPPED_P(NODE) \
> + (VECTOR_CST_NELTS_PER_PATTERN (NODE) == 3)
> +#define VECTOR_CST_ENCODED_ELTS(NODE) \
> + (VECTOR_CST_CHECK (NODE)->vector.elts)
> +#define VECTOR_CST_ENCODED_ELT(NODE, ELT) \
> + (VECTOR_CST_CHECK (NODE)->vector.elts[ELT])
>
> /* Define fields and accessors for some special-purpose tree nodes. */
>
> @@ -3885,6 +3899,14 @@ #define error_operand_p(NODE)
> \
> ((NODE) == error_mark_node \
> || ((NODE) && TREE_TYPE ((NODE)) == error_mark_node))
>
> +/* Return the number of elements encoded directly in a VECTOR_CST. */
> +
> +inline unsigned int
> +vector_cst_encoded_nelts (const_tree t)
> +{
> + return VECTOR_CST_NPATTERNS (t) * VECTOR_CST_NELTS_PER_PATTERN (t);
> +}
> +
> extern tree decl_assembler_name (tree);
> extern void overwrite_decl_assembler_name (tree decl, tree name);
> extern tree decl_comdat_group (const_tree);
> @@ -4024,7 +4046,7 @@ extern tree force_fit_type (tree, const
> 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 make_vector (unsigned, 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);
> @@ -4271,6 +4293,9 @@ extern tree first_field (const_tree);
>
> 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-30 13:07:23.752425675 +0000
> +++ gcc/tree.c 2017-11-30 13:07:24.032415034 +0000
> @@ -66,6 +66,7 @@ Software Foundation; either version 3, o
> #include "attribs.h"
> #include "rtl.h"
> #include "regs.h"
> +#include "tree-vector-builder.h"
>
> /* Tree code classes. */
>
> @@ -839,7 +840,7 @@ tree_code_size (enum tree_code code)
> 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 VECTOR_CST: gcc_unreachable ();
> case STRING_CST: gcc_unreachable ();
> default:
> gcc_checking_assert (code >= NUM_TREE_CODES);
> @@ -899,7 +900,7 @@ tree_size (const_tree node)
>
> case VECTOR_CST:
> return (sizeof (struct tree_vector)
> - + (VECTOR_CST_NELTS (node) - 1) * sizeof (tree));
> + + (vector_cst_encoded_nelts (node) - 1) * sizeof (tree));
>
> case STRING_CST:
> return TREE_STRING_LENGTH (node) + offsetof (struct tree_string, str)
> + 1;
> @@ -1708,13 +1709,19 @@ cst_and_fits_in_hwi (const_tree x)
> && (tree_fits_shwi_p (x) || tree_fits_uhwi_p (x)));
> }
>
> -/* Build a newly constructed VECTOR_CST node of length LEN. */
> +/* Build a newly constructed VECTOR_CST with the given values of
> + (VECTOR_CST_)LOG2_NPATTERNS and (VECTOR_CST_)NELTS_PER_PATTERN. */
>
> tree
> -make_vector (unsigned len MEM_STAT_DECL)
> +make_vector (unsigned log2_npatterns,
> + unsigned int nelts_per_pattern MEM_STAT_DECL)
> {
> + gcc_assert (IN_RANGE (nelts_per_pattern, 1, 3));
> tree t;
> - unsigned length = (len - 1) * sizeof (tree) + sizeof (struct tree_vector);
> + unsigned npatterns = 1 << log2_npatterns;
> + unsigned encoded_nelts = npatterns * nelts_per_pattern;
> + unsigned length = (sizeof (struct tree_vector)
> + + (encoded_nelts - 1) * sizeof (tree));
>
> record_node_allocation_statistics (VECTOR_CST, length);
>
> @@ -1722,7 +1729,8 @@ make_vector (unsigned len MEM_STAT_DECL)
>
> TREE_SET_CODE (t, VECTOR_CST);
> TREE_CONSTANT (t) = 1;
> - VECTOR_CST_NELTS (t) = len;
> + VECTOR_CST_LOG2_NPATTERNS (t) = log2_npatterns;
> + VECTOR_CST_NELTS_PER_PATTERN (t) = nelts_per_pattern;
>
> return t;
> }
> @@ -1733,29 +1741,10 @@ make_vector (unsigned len MEM_STAT_DECL)
> 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;
> + gcc_assert (vals.length () == TYPE_VECTOR_SUBPARTS (type));
> + tree_vector_builder builder (type, vals.length (), 1);
> + builder.splice (vals);
> + return builder.build ();
> }
>
> /* Return a new VECTOR_CST node whose type is TYPE and whose values
> @@ -10353,6 +10342,57 @@ build_opaque_vector_type (tree innertype
> 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)
> +{
> + /* First handle elements that are directly encoded. */
> + unsigned int encoded_nelts = vector_cst_encoded_nelts (t);
> + if (i < encoded_nelts)
> + return wi::to_wide (VECTOR_CST_ENCODED_ELT (t, i));
> +
> + /* Identify the pattern that contains element I and work out the index of
> + the last encoded element for that pattern. */
> + unsigned int npatterns = VECTOR_CST_NPATTERNS (t);
> + unsigned int pattern = i & (npatterns - 1);
> + unsigned int final_i = encoded_nelts - npatterns + pattern;
> +
> + /* If there are no steps, the final encoded value is the right one. */
> + if (!VECTOR_CST_STEPPED_P (t))
> + return wi::to_wide (VECTOR_CST_ENCODED_ELT (t, final_i));
> +
> + /* Otherwise work out the value from the last two encoded elements. */
> + unsigned int factor = (i - final_i) >> VECTOR_CST_LOG2_NPATTERNS (t);
> + tree v1 = VECTOR_CST_ENCODED_ELT (t, final_i - npatterns);
> + tree v2 = VECTOR_CST_ENCODED_ELT (t, final_i);
> + return wi::to_wide (v2) + factor * (wi::to_wide (v2) - wi::to_wide (v1));
> +}
> +
> +/* Return the value of element I of VECTOR_CST T. */
> +
> +tree
> +vector_cst_elt (const_tree t, unsigned int i)
> +{
> + /* First handle elements that are directly encoded. */
> + unsigned int encoded_nelts = vector_cst_encoded_nelts (t);
> + if (i < encoded_nelts)
> + return VECTOR_CST_ENCODED_ELT (t, i);
> +
> + /* Identify the pattern that contains element I and work out the index of
> + the last encoded element for that pattern. */
> + unsigned int npatterns = VECTOR_CST_NPATTERNS (t);
> + unsigned int pattern = i & (npatterns - 1);
> + unsigned int final_i = encoded_nelts - npatterns + pattern;
> +
> + /* If there are no steps, the final encoded value is the right one. */
> + if (!VECTOR_CST_STEPPED_P (t))
> + return VECTOR_CST_ENCODED_ELT (t, final_i);
> +
> + /* Otherwise work out the value from the last two encoded elements. */
> + return wide_int_to_tree (TREE_TYPE (TREE_TYPE (t)),
> + vector_cst_int_elt (t, i));
> +}
>
> /* Given an initializer INIT, return TRUE if INIT is zero or some
> aggregate of zeros. Otherwise return FALSE. */
> @@ -12433,6 +12473,22 @@ drop_tree_overflow (tree t)
> if (TREE_CODE (t) == INTEGER_CST)
> return wide_int_to_tree (TREE_TYPE (t), wi::to_wide (t));
>
> + /* For VECTOR_CST, remove the overflow bits from the encoded elements
> + and canonicalize the result. */
> + if (TREE_CODE (t) == VECTOR_CST)
> + {
> + tree_vector_builder builder (tree_vector_builder::unary (t, true));
> + unsigned int count = builder.encoded_nelts ();
> + for (unsigned int i = 0; i < count; ++i)
> + {
> + tree elt = VECTOR_CST_ELT (t, i);
> + if (TREE_OVERFLOW (elt))
> + elt = drop_tree_overflow (elt);
> + builder.quick_push (elt);
> + }
> + return builder.build ();
> + }
> +
> /* Otherwise, as all tcc_constants are possibly shared, copy the node
> and drop the flag. */
> t = copy_node (t);
> @@ -12447,15 +12503,7 @@ drop_tree_overflow (tree t)
> 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;
> }
>
> @@ -13954,6 +14002,138 @@ test_labels ()
> ASSERT_FALSE (FORCED_LABEL (label_decl));
> }
>
> +/* Check that VECTOR_CST ACTUAL contains the elements in EXPECTED. */
> +
> +static void
> +check_vector_cst (vec<tree> expected, tree actual)
> +{
> + for (unsigned int i = 0; i < expected.length (); ++i)
> + ASSERT_EQ (wi::to_wide (expected[i]),
> + wi::to_wide (vector_cst_elt (actual, i)));
> +}
> +
> +/* Check that VECTOR_CST ACTUAL contains NPATTERNS duplicated elements,
> + and that its elements match EXPECTED. */
> +
> +static void
> +check_vector_cst_duplicate (vec<tree> expected, tree actual,
> + unsigned int npatterns)
> +{
> + ASSERT_EQ (npatterns, VECTOR_CST_NPATTERNS (actual));
> + ASSERT_EQ (1, VECTOR_CST_NELTS_PER_PATTERN (actual));
> + ASSERT_EQ (npatterns, vector_cst_encoded_nelts (actual));
> + ASSERT_TRUE (VECTOR_CST_DUPLICATE_P (actual));
> + ASSERT_FALSE (VECTOR_CST_STEPPED_P (actual));
> + check_vector_cst (expected, actual);
> +}
> +
> +/* Check that VECTOR_CST ACTUAL contains NPATTERNS foreground elements
> + and NPATTERNS background elements, and that its elements match
> + EXPECTED. */
> +
> +static void
> +check_vector_cst_fill (vec<tree> expected, tree actual,
> + unsigned int npatterns)
> +{
> + ASSERT_EQ (npatterns, VECTOR_CST_NPATTERNS (actual));
> + ASSERT_EQ (2, VECTOR_CST_NELTS_PER_PATTERN (actual));
> + ASSERT_EQ (2 * npatterns, vector_cst_encoded_nelts (actual));
> + ASSERT_FALSE (VECTOR_CST_DUPLICATE_P (actual));
> + ASSERT_FALSE (VECTOR_CST_STEPPED_P (actual));
> + check_vector_cst (expected, actual);
> +}
> +
> +/* Check that VECTOR_CST ACTUAL contains NPATTERNS stepped patterns,
> + and that its elements match EXPECTED. */
> +
> +static void
> +check_vector_cst_stepped (vec<tree> expected, tree actual,
> + unsigned int npatterns)
> +{
> + ASSERT_EQ (npatterns, VECTOR_CST_NPATTERNS (actual));
> + ASSERT_EQ (3, VECTOR_CST_NELTS_PER_PATTERN (actual));
> + ASSERT_EQ (3 * npatterns, vector_cst_encoded_nelts (actual));
> + ASSERT_FALSE (VECTOR_CST_DUPLICATE_P (actual));
> + ASSERT_TRUE (VECTOR_CST_STEPPED_P (actual));
> + check_vector_cst (expected, actual);
> +}
> +
> +/* 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);
> + check_vector_cst_stepped (elements, build_vector (vector_type, elements),
> 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);
> + check_vector_cst_stepped (elements, build_vector (vector_type, elements),
> 1);
> +
> + /* 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);
> + check_vector_cst_stepped (elements, build_vector (vector_type, elements),
> 1);
> +
> + /* 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);
> + check_vector_cst_stepped (elements, build_vector (vector_type, elements),
> 1);
> +
> + /* 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);
> + }
> + check_vector_cst_stepped (elements, build_vector (vector_type, elements),
> 2);
> +
> + /* Try a duplicated value:
> + { 100, 100, 100, 100, 100, 100, 100, 100 }. */
> + for (unsigned int i = 1; i < 8; ++i)
> + elements[i] = elements[0];
> + check_vector_cst_duplicate (elements,
> + build_vector (vector_type, elements), 1);
> +
> + /* 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];
> + check_vector_cst_duplicate (elements,
> + build_vector (vector_type, elements), 2);
> +
> + /* 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);
> + check_vector_cst_fill (elements, build_vector (vector_type, elements), 2);
> +
> + /* 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);
> + check_vector_cst_stepped (elements, build_vector (vector_type, elements),
> 2);
> +
> + /* Try a fully-general constant:
> + { 41, 97, 100, 21, 100, 9990, 100, 49 }. */
> + elements[5] = build_int_cst (element_type, 9990);
> + check_vector_cst_fill (elements, build_vector (vector_type, elements), 4);
> +}
> +
> /* Run all of the selftests within this file. */
>
> void
> @@ -13962,6 +14142,7 @@ tree_c_tests ()
> 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-30 13:07:23.752425675 +0000
> +++ gcc/lto-streamer-out.c 2017-11-30 13:07:24.029415148 +0000
> @@ -747,8 +747,9 @@ #define DFS_follow_tree_edge(DEST) \
>
> 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));
> + unsigned int count = vector_cst_encoded_nelts (expr);
> + for (unsigned int i = 0; i < count; ++i)
> + DFS_follow_tree_edge (VECTOR_CST_ENCODED_ELT (expr, i));
> }
>
> if (CODE_CONTAINS_STRUCT (code, TS_COMPLEX))
> @@ -1195,8 +1196,11 @@ #define visit(SIBLING) \
> }
>
> if (CODE_CONTAINS_STRUCT (code, TS_VECTOR))
> - for (unsigned i = 0; i < VECTOR_CST_NELTS (t); ++i)
> - visit (VECTOR_CST_ELT (t, i));
> + {
> + unsigned int count = vector_cst_encoded_nelts (t);
> + for (unsigned int i = 0; i < count; ++i)
> + visit (VECTOR_CST_ENCODED_ELT (t, i));
> + }
>
> if (CODE_CONTAINS_STRUCT (code, TS_COMPLEX))
> {
> Index: gcc/tree-streamer-out.c
> ===================================================================
> --- gcc/tree-streamer-out.c 2017-11-30 13:07:23.752425675 +0000
> +++ gcc/tree-streamer-out.c 2017-11-30 13:07:24.029415148 +0000
> @@ -533,11 +533,11 @@ write_ts_common_tree_pointers (struct ou
> 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);
> + unsigned int count = vector_cst_encoded_nelts (expr);
> + for (unsigned int i = 0; i < count; ++i)
> + stream_write_tree (ob, VECTOR_CST_ENCODED_ELT (expr, i), ref_p);
> }
>
>
> @@ -960,7 +960,12 @@ streamer_write_tree_header (struct outpu
> 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));
> + {
> + bitpack_d bp = bitpack_create (ob->main_stream);
> + bp_pack_value (&bp, VECTOR_CST_LOG2_NPATTERNS (expr), 8);
> + bp_pack_value (&bp, VECTOR_CST_NELTS_PER_PATTERN (expr), 8);
> + 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-30 13:07:23.752425675 +0000
> +++ gcc/tree-streamer-in.c 2017-11-30 13:07:24.029415148 +0000
> @@ -592,8 +592,10 @@ streamer_alloc_tree (struct lto_input_bl
> }
> else if (CODE_CONTAINS_STRUCT (code, TS_VECTOR))
> {
> - HOST_WIDE_INT len = streamer_read_hwi (ib);
> - result = make_vector (len);
> + bitpack_d bp = streamer_read_bitpack (ib);
> + unsigned int log2_npatterns = bp_unpack_value (&bp, 8);
> + unsigned int nelts_per_pattern = bp_unpack_value (&bp, 8);
> + result = make_vector (log2_npatterns, nelts_per_pattern);
> }
> else if (CODE_CONTAINS_STRUCT (code, TS_BINFO))
> {
> @@ -650,9 +652,9 @@ lto_input_ts_common_tree_pointers (struc
> 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);
> + unsigned int count = vector_cst_encoded_nelts (expr);
> + for (unsigned int i = 0; i < count; ++i)
> + VECTOR_CST_ENCODED_ELT (expr, i) = stream_read_tree (ib, data_in);
> }
>
>
> Index: gcc/fold-const.c
> ===================================================================
> --- gcc/fold-const.c 2017-11-30 13:07:23.752425675 +0000
> +++ gcc/fold-const.c 2017-11-30 13:07:24.029415148 +0000
> @@ -11610,9 +11610,8 @@ fold_ternary_loc (location_t loc, enum t
> 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;
> + 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-30 13:07:23.752425675 +0000
> +++ gcc/lto/lto.c 2017-11-30 13:07:24.029415148 +0000
> @@ -1065,6 +1065,12 @@ #define compare_values(X) \
> 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_NELTS_PER_PATTERN);
> + }
> +
> if (CODE_CONTAINS_STRUCT (code, TS_DECL_COMMON))
> {
> compare_values (DECL_MODE);
> @@ -1281,11 +1287,12 @@ #define compare_tree_edges(E1, E2) \
>
> 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));
> + unsigned int count = vector_cst_encoded_nelts (t1);
> + for (unsigned int i = 0; i < count; ++i)
> + compare_tree_edges (VECTOR_CST_ENCODED_ELT (t1, i),
> + VECTOR_CST_ENCODED_ELT (t2, i));
> }
>
> if (CODE_CONTAINS_STRUCT (code, TS_COMPLEX))
