diff options
Diffstat (limited to 'support/cpp/gcc/vector-builder.h')
| -rw-r--r-- | support/cpp/gcc/vector-builder.h | 612 |
1 files changed, 612 insertions, 0 deletions
diff --git a/support/cpp/gcc/vector-builder.h b/support/cpp/gcc/vector-builder.h new file mode 100644 index 000000000..6e917063d --- /dev/null +++ b/support/cpp/gcc/vector-builder.h @@ -0,0 +1,612 @@ +/* A class for building vector constant patterns. + Copyright (C) 2017-2022 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/>. */ + +#if 0 // sdcpp ndef 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 by finalize (). 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. finalize () then canonicalizes the encoding + to a simpler form if possible. + + Shape is the type that specifies the number of elements in the vector + and (where relevant) the type of each element. + + The derived class Derived provides the functionality of this class + for specific Ts. Derived needs to provide the following interface: + + bool equal_p (T elt1, T elt2) const; + + Return true if elements ELT1 and ELT2 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 (T elt) const; + + Return true if element ELT can be interpreted as an integer. + + StepType step (T elt1, T elt2) const; + + Return the value of element ELT2 minus the value of element ELT1, + given integral_p (ELT1) && integral_p (ELT2). There is no fixed + choice of StepType. + + T apply_step (T base, unsigned int factor, StepType step) const; + + Return a vector element with the value BASE + FACTOR * STEP. + + bool can_elide_p (T elt) const; + + Return true if we can drop element ELT, even if the retained + elements are different. This is provided for TREE_OVERFLOW + handling. + + void note_representative (T *elt1_ptr, T elt2); + + Record that ELT2 is being elided, given that ELT1_PTR points to + the last encoded element for the containing pattern. This is + again provided for TREE_OVERFLOW handling. + + static poly_uint64 shape_nelts (Shape shape); + + Return the number of elements in SHAPE. + + The class provides additional functionality for the case in which + T can describe a vector constant as well as an individual element. + This functionality requires: + + static poly_uint64 nelts_of (T x); + + Return the number of elements in vector constant X. + + static unsigned int npatterns_of (T x); + + Return the number of patterns used to encode vector constant X. + + static unsigned int nelts_per_pattern_of (T x); + + Return the number of elements used to encode each pattern + in vector constant X. */ + +template<typename T, typename Shape, typename Derived> +class vector_builder : public auto_vec<T, 32> +{ +public: + vector_builder (); + + // sdcpp poly_uint64 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; + T elt (unsigned int) const; + unsigned int count_dups (int, int, int) const; + + bool operator == (const Derived &) const; + bool operator != (const Derived &x) const { return !operator == (x); } + + bool new_unary_operation (Shape, T, bool); + bool new_binary_operation (Shape, T, T, bool); + + void finalize (); + + static unsigned int binary_encoded_nelts (T, T); + +protected: + // sdcpp void new_vector (poly_uint64, unsigned int, unsigned int); + void reshape (unsigned int, unsigned int); + bool repeating_sequence_p (unsigned int, unsigned int, unsigned int); + bool stepped_sequence_p (unsigned int, unsigned int, unsigned int); + bool try_npatterns (unsigned int); + +private: + vector_builder (const vector_builder &); + vector_builder &operator= (const vector_builder &); + Derived *derived () { return static_cast<Derived *> (this); } + const Derived *derived () const; + + // sdcpp poly_uint64 m_full_nelts; + unsigned int m_npatterns; + unsigned int m_nelts_per_pattern; +}; + +template<typename T, typename Shape, typename Derived> +inline const Derived * +vector_builder<T, Shape, Derived>::derived () const +{ + return static_cast<const Derived *> (this); +} + +template<typename T, typename Shape, typename Derived> +inline +vector_builder<T, Shape, Derived>::vector_builder () + : // sdcpp m_full_nelts (0), + m_npatterns (0), + m_nelts_per_pattern (0) +{} + +/* 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, typename Shape, typename Derived> +inline unsigned int +vector_builder<T, Shape, Derived>::encoded_nelts () const +{ + return m_npatterns * m_nelts_per_pattern; +} + +/* Return true if every element of the vector is explicitly encoded. */ + +template<typename T, typename Shape, typename Derived> +inline bool +vector_builder<T, Shape, Derived>::encoded_full_vector_p () const +{ + return known_eq (m_npatterns * m_nelts_per_pattern, m_full_nelts); +} + +/* Start building a vector that has FULL_NELTS elements. Initially + encode it using NPATTERNS patterns with NELTS_PER_PATTERN each. */ + +template<typename T, typename Shape, typename Derived> +void +vector_builder<T, Shape, Derived>::new_vector (poly_uint64 full_nelts, + unsigned int npatterns, + unsigned int nelts_per_pattern) +{ + m_full_nelts = full_nelts; + m_npatterns = npatterns; + m_nelts_per_pattern = nelts_per_pattern; + this->reserve (encoded_nelts ()); + this->truncate (0); +} + +/* Return true if this vector and OTHER have the same elements and + are encoded in the same way. */ + +template<typename T, typename Shape, typename Derived> +bool +vector_builder<T, Shape, Derived>::operator == (const Derived &other) const +{ + if (maybe_ne (m_full_nelts, other.m_full_nelts) + || m_npatterns != other.m_npatterns + || m_nelts_per_pattern != other.m_nelts_per_pattern) + return false; + + unsigned int nelts = encoded_nelts (); + for (unsigned int i = 0; i < nelts; ++i) + if (!derived ()->equal_p ((*this)[i], other[i])) + return false; + + return true; +} + +/* Return the value of vector element I, which might or might not be + encoded explicitly. */ + +template<typename T, typename Shape, typename Derived> +T +vector_builder<T, Shape, Derived>::elt (unsigned int i) const +{ + /* First handle elements that are already present in the underlying + vector, regardless of whether they're part of the encoding or not. */ + if (i < this->length ()) + return (*this)[i]; + + /* Extrapolation is only possible if the encoding has been fully + populated. */ + gcc_checking_assert (encoded_nelts () <= this->length ()); + + /* Identify the pattern that contains element I and work out the index of + the last encoded element for that pattern. */ + unsigned int pattern = i % m_npatterns; + unsigned int count = i / m_npatterns; + unsigned int final_i = encoded_nelts () - m_npatterns + pattern; + T final = (*this)[final_i]; + + /* If there are no steps, the final encoded value is the right one. */ + if (m_nelts_per_pattern <= 2) + return final; + + /* Otherwise work out the value from the last two encoded elements. */ + T prev = (*this)[final_i - m_npatterns]; + return derived ()->apply_step (final, count - 2, + derived ()->step (prev, final)); +} + +/* Try to start building a new vector of shape SHAPE that holds the result of + a unary operation on vector constant VEC. ALLOW_STEPPED_P is true if the + operation can handle stepped encodings directly, without having to expand + the full sequence. + + Return true if the operation is possible, which it always is when + ALLOW_STEPPED_P is true. Leave the builder unchanged otherwise. */ + +template<typename T, typename Shape, typename Derived> +bool +vector_builder<T, Shape, Derived>::new_unary_operation (Shape shape, T vec, + bool allow_stepped_p) +{ + poly_uint64 full_nelts = Derived::shape_nelts (shape); + gcc_assert (known_eq (full_nelts, Derived::nelts_of (vec))); + unsigned int npatterns = Derived::npatterns_of (vec); + unsigned int nelts_per_pattern = Derived::nelts_per_pattern_of (vec); + if (!allow_stepped_p && nelts_per_pattern > 2) + { + if (!full_nelts.is_constant ()) + return false; + npatterns = full_nelts.to_constant (); + nelts_per_pattern = 1; + } + derived ()->new_vector (shape, npatterns, nelts_per_pattern); + return true; +} + +/* Try to start building a new vector of shape SHAPE that holds the result of + a binary operation on vector constants VEC1 and VEC2. ALLOW_STEPPED_P is + true if the operation can handle stepped encodings directly, without + having to expand the full sequence. + + Return true if the operation is possible. Leave the builder unchanged + otherwise. */ + +template<typename T, typename Shape, typename Derived> +bool +vector_builder<T, Shape, Derived>::new_binary_operation (Shape shape, + T vec1, T vec2, + bool allow_stepped_p) +{ + poly_uint64 full_nelts = Derived::shape_nelts (shape); + gcc_assert (known_eq (full_nelts, Derived::nelts_of (vec1)) + && known_eq (full_nelts, Derived::nelts_of (vec2))); + /* Conceptually we split the patterns in VEC1 and VEC2 until we have + an equal number for both. Each split pattern requires the same + number of elements per pattern as the original. E.g. splitting: + + { 1, 2, 3, ... } + + into two gives: + + { 1, 3, 5, ... } + { 2, 4, 6, ... } + + while splitting: + + { 1, 0, ... } + + into two gives: + + { 1, 0, ... } + { 0, 0, ... }. */ + unsigned int npatterns + = least_common_multiple (Derived::npatterns_of (vec1), + Derived::npatterns_of (vec2)); + unsigned int nelts_per_pattern + = MAX (Derived::nelts_per_pattern_of (vec1), + Derived::nelts_per_pattern_of (vec2)); + if (!allow_stepped_p && nelts_per_pattern > 2) + { + if (!full_nelts.is_constant ()) + return false; + npatterns = full_nelts.to_constant (); + nelts_per_pattern = 1; + } + derived ()->new_vector (shape, npatterns, nelts_per_pattern); + return true; +} + +/* Return the number of elements that the caller needs to operate on in + order to handle a binary operation on vector constants VEC1 and VEC2. + This static function is used instead of new_binary_operation if the + result of the operation is not a constant vector. */ + +template<typename T, typename Shape, typename Derived> +unsigned int +vector_builder<T, Shape, Derived>::binary_encoded_nelts (T vec1, T vec2) +{ + poly_uint64 nelts = Derived::nelts_of (vec1); + gcc_assert (known_eq (nelts, Derived::nelts_of (vec2))); + /* See new_binary_operation for details. */ + unsigned int npatterns + = least_common_multiple (Derived::npatterns_of (vec1), + Derived::npatterns_of (vec2)); + unsigned int nelts_per_pattern + = MAX (Derived::nelts_per_pattern_of (vec1), + Derived::nelts_per_pattern_of (vec2)); + unsigned HOST_WIDE_INT const_nelts; + if (nelts.is_constant (&const_nelts)) + return MIN (npatterns * nelts_per_pattern, const_nelts); + return npatterns * nelts_per_pattern; +} + +/* Return the number of leading duplicate elements in the range + [START:END:STEP]. The value is always at least 1. */ + +template<typename T, typename Shape, typename Derived> +unsigned int +vector_builder<T, Shape, Derived>::count_dups (int start, int end, + int step) const +{ + gcc_assert ((end - start) % step == 0); + + unsigned int ndups = 1; + for (int i = start + step; + i != end && derived ()->equal_p (elt (i), elt (start)); + i += step) + ndups++; + return ndups; +} + +/* Change the encoding to NPATTERNS patterns of NELTS_PER_PATTERN each, + but without changing the underlying vector. */ + +template<typename T, typename Shape, typename Derived> +void +vector_builder<T, Shape, Derived>::reshape (unsigned int npatterns, + unsigned int nelts_per_pattern) +{ + unsigned int old_encoded_nelts = encoded_nelts (); + unsigned int new_encoded_nelts = npatterns * nelts_per_pattern; + gcc_checking_assert (new_encoded_nelts <= old_encoded_nelts); + unsigned int next = new_encoded_nelts - npatterns; + for (unsigned int i = new_encoded_nelts; i < old_encoded_nelts; ++i) + { + derived ()->note_representative (&(*this)[next], (*this)[i]); + next += 1; + if (next == new_encoded_nelts) + next -= npatterns; + } + m_npatterns = npatterns; + m_nelts_per_pattern = nelts_per_pattern; +} + +/* Return true if elements [START, END) contain a repeating sequence of + STEP elements. */ + +template<typename T, typename Shape, typename Derived> +bool +vector_builder<T, Shape, Derived>::repeating_sequence_p (unsigned int start, + unsigned int end, + unsigned int step) +{ + for (unsigned int i = start; i < end - step; ++i) + if (!derived ()->equal_p ((*this)[i], (*this)[i + step])) + return false; + return true; +} + +/* Return true if elements [START, END) contain STEP interleaved linear + series. */ + +template<typename T, typename Shape, typename Derived> +bool +vector_builder<T, Shape, Derived>::stepped_sequence_p (unsigned int start, + unsigned int end, + unsigned int step) +{ + if (!derived ()->allow_steps_p ()) + return false; + + for (unsigned int i = start + step * 2; i < end; ++i) + { + T elt1 = (*this)[i - step * 2]; + T elt2 = (*this)[i - step]; + T elt3 = (*this)[i]; + + if (!derived ()->integral_p (elt1) + || !derived ()->integral_p (elt2) + || !derived ()->integral_p (elt3)) + return false; + + if (maybe_ne (derived ()->step (elt1, elt2), + derived ()->step (elt2, elt3))) + return false; + + if (!derived ()->can_elide_p (elt3)) + return false; + } + return true; +} + +/* Try to change the number of encoded patterns to NPATTERNS, returning + true on success. */ + +template<typename T, typename Shape, typename Derived> +bool +vector_builder<T, Shape, Derived>::try_npatterns (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 (0, encoded_nelts (), npatterns)) + { + reshape (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 (npatterns, encoded_nelts (), npatterns)) + { + reshape (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 (npatterns, encoded_nelts (), npatterns)) + { + reshape (npatterns, 3); + return true; + } + return false; + } + + gcc_unreachable (); +} + +/* Replace the current encoding with the canonical form. */ + +template<typename T, typename Shape, typename Derived> +void +vector_builder<T, Shape, Derived>::finalize () +{ + /* The encoding requires the same number of elements to come from each + pattern. */ + gcc_assert (multiple_p (m_full_nelts, m_npatterns)); + + /* Allow the caller to build more elements than necessary. For example, + it's often convenient to build a stepped vector from the natural + encoding of three elements even if the vector itself only has two. */ + unsigned HOST_WIDE_INT const_full_nelts; + if (m_full_nelts.is_constant (&const_full_nelts) + && const_full_nelts <= encoded_nelts ()) + { + m_npatterns = const_full_nelts; + m_nelts_per_pattern = 1; + } + + /* 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 (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 (m_npatterns, m_nelts_per_pattern - 1); + + if (pow2p_hwi (m_npatterns)) + { + /* Try to halve the number of patterns while doing so gives a + valid pattern. This approach is linear in the number of + elements, whereas searcing from 1 up would be O(n*log(n)). + + 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 (m_npatterns / 2)) + continue; + + /* Builders of arbitrary fixed-length vectors can use: + + new_vector (x, x, 1) + + so that every element is specified explicitly. Handle cases + that are actually wrapping series, like { 0, 1, 2, 3, 0, 1, 2, 3 } + would be for 2-bit elements. We'll have treated them as + duplicates in the loop above. */ + if (m_nelts_per_pattern == 1 + && m_full_nelts.is_constant (&const_full_nelts) + && this->length () >= const_full_nelts + && (m_npatterns & 3) == 0 + && stepped_sequence_p (m_npatterns / 4, const_full_nelts, + m_npatterns / 4)) + { + reshape (m_npatterns / 4, 3); + while ((m_npatterns & 1) == 0 && try_npatterns (m_npatterns / 2)) + continue; + } + } + else + /* For the non-power-of-2 case, do a simple search up from 1. */ + for (unsigned int i = 1; i <= m_npatterns / 2; ++i) + if (m_npatterns % i == 0 && try_npatterns (i)) + break; +} + +#endif |