vector-builder.h

/* A class for building vector constant patterns.
   Copyright (C) 2017-2018 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.

   The derived class Derived provides this functionality 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.  */

template<typename T, 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;

  bool operator == (const Derived &) const;
  bool operator != (const Derived &x) const { return !operator == (x); }

  void finalize ();

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 Derived>
inline const Derived *
vector_builder<T, Derived>::derived () const
{
  return static_cast<const Derived *> (this);
}

template<typename T, typename Derived>
inline
vector_builder<T, 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 Derived>
inline unsigned int
vector_builder<T, 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 Derived>
inline bool
vector_builder<T, 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 Derived>
void
vector_builder<T, 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 Derived>
bool
vector_builder<T, 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 Derived>
T
vector_builder<T, Derived>::elt (unsigned int i) const
{
  /* This only makes sense if the encoding has been fully populated.  */
  gcc_checking_assert (encoded_nelts () <= this->length ());

  /* 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];

  /* 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));
}

/* Change the encoding to NPATTERNS patterns of NELTS_PER_PATTERN each,
   but without changing the underlying vector.  */

template<typename T, typename Derived>
void
vector_builder<T, 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 Derived>
bool
vector_builder<T, 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 Derived>
bool
vector_builder<T, 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 Derived>
bool
vector_builder<T, 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 Derived>
void
vector_builder<T, 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