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?
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))
