/* A class for building vector constant patterns. | |

Copyright (C) 2017-2020 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 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 (); | |

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: | |

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; | |

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

: 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 |