gcc/vector-builder.h

   1 /* A class for building vector constant patterns.
   2    Copyright (C) 2017 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #ifndef GCC_VECTOR_BUILDER_H
  21 #define GCC_VECTOR_BUILDER_H
  22
  23 /* This class is a wrapper around auto_vec<T> for building vectors of T.
  24    It aims to encode each vector as npatterns interleaved patterns,
  25    where each pattern represents a sequence:
  26
  27      { BASE0, BASE1, BASE1 + STEP, BASE1 + STEP*2, BASE1 + STEP*3, ... }
  28
  29    The first three elements in each pattern provide enough information
  30    to derive the other elements.  If all patterns have a STEP of zero,
  31    we only need to encode the first two elements in each pattern.
  32    If BASE1 is also equal to BASE0 for all patterns, we only need to
  33    encode the first element in each pattern.  The number of encoded
  34    elements per pattern is given by nelts_per_pattern.
  35
  36    The class can be used in two ways:
  37
  38    1. It can be used to build a full image of the vector, which is then
  39       canonicalized by finalize ().  In this case npatterns is initially
  40       the number of elements in the vector and nelts_per_pattern is
  41       initially 1.
  42
  43    2. It can be used to build a vector that already has a known encoding.
  44       This is preferred since it is more efficient and copes with
  45       variable-length vectors.  finalize () then canonicalizes the encoding
  46       to a simpler form if possible.
  47
  48    The derived class Derived provides this functionality for specific Ts.
  49    Derived needs to provide the following interface:
  50
  51       bool equal_p (T elt1, T elt2) const;
  52
  53           Return true if elements ELT1 and ELT2 are equal.
  54
  55       bool allow_steps_p () const;
  56
  57           Return true if a stepped representation is OK.  We don't allow
  58           linear series for anything other than integers, to avoid problems
  59           with rounding.
  60
  61       bool integral_p (T elt) const;
  62
  63           Return true if element ELT can be interpreted as an integer.
  64
  65       StepType step (T elt1, T elt2) const;
  66
  67           Return the value of element ELT2 minus the value of element ELT1,
  68           given integral_p (ELT1) && integral_p (ELT2).  There is no fixed
  69           choice of StepType.
  70
  71       bool can_elide_p (T elt) const;
  72
  73           Return true if we can drop element ELT, even if the retained
  74           elements are different.  This is provided for TREE_OVERFLOW
  75           handling.
  76
  77       void note_representative (T *elt1_ptr, T elt2);
  78
  79           Record that ELT2 is being elided, given that ELT1_PTR points to
  80           the last encoded element for the containing pattern.  This is
  81           again provided for TREE_OVERFLOW handling.  */
  82
  83 template<typename T, typename Derived>
  84 class vector_builder : public auto_vec<T, 32>
  85 {
  86 public:
  87   vector_builder ();
  88
  89   unsigned int full_nelts () const { return m_full_nelts; }
  90   unsigned int npatterns () const { return m_npatterns; }
  91   unsigned int nelts_per_pattern () const { return m_nelts_per_pattern; }
  92   unsigned int encoded_nelts () const;
  93   bool encoded_full_vector_p () const;
  94
  95   void finalize ();
  96
  97 protected:
  98   void new_vector (unsigned int, unsigned int, unsigned int);
  99   void reshape (unsigned int, unsigned int);
 100   bool repeating_sequence_p (unsigned int, unsigned int, unsigned int);
 101   bool stepped_sequence_p (unsigned int, unsigned int, unsigned int);
 102   bool try_npatterns (unsigned int);
 103
 104 private:
 105   vector_builder (const vector_builder &);
 106   vector_builder &operator= (const vector_builder &);
 107   Derived *derived () { return static_cast<Derived *> (this); }
 108   const Derived *derived () const;
 109
 110   unsigned int m_full_nelts;
 111   unsigned int m_npatterns;
 112   unsigned int m_nelts_per_pattern;
 113 };
 114
 115 template<typename T, typename Derived>
 116 inline const Derived *
 117 vector_builder<T, Derived>::derived () const
 118 {
 119   return static_cast<const Derived *> (this);
 120 }
 121
 122 template<typename T, typename Derived>
 123 inline
 124 vector_builder<T, Derived>::vector_builder ()
 125   : m_full_nelts (0),
 126     m_npatterns (0),
 127     m_nelts_per_pattern (0)
 128 {}
 129
 130 /* Return the number of elements that are explicitly encoded.  The vec
 131    starts with these explicitly-encoded elements and may contain additional
 132    elided elements.  */
 133
 134 template<typename T, typename Derived>
 135 inline unsigned int
 136 vector_builder<T, Derived>::encoded_nelts () const
 137 {
 138   return m_npatterns * m_nelts_per_pattern;
 139 }
 140
 141 /* Return true if every element of the vector is explicitly encoded.  */
 142
 143 template<typename T, typename Derived>
 144 inline bool
 145 vector_builder<T, Derived>::encoded_full_vector_p () const
 146 {
 147   return m_npatterns * m_nelts_per_pattern == m_full_nelts;
 148 }
 149
 150 /* Start building a vector that has FULL_NELTS elements.  Initially
 151    encode it using NPATTERNS patterns with NELTS_PER_PATTERN each.  */
 152
 153 template<typename T, typename Derived>
 154 void
 155 vector_builder<T, Derived>::new_vector (unsigned int full_nelts,
 156                                         unsigned int npatterns,
 157                                         unsigned int nelts_per_pattern)
 158 {
 159   m_full_nelts = full_nelts;
 160   m_npatterns = npatterns;
 161   m_nelts_per_pattern = nelts_per_pattern;
 162   this->reserve (encoded_nelts ());
 163   this->truncate (0);
 164 }
 165
 166 /* Change the encoding to NPATTERNS patterns of NELTS_PER_PATTERN each,
 167    but without changing the underlying vector.  */
 168
 169 template<typename T, typename Derived>
 170 void
 171 vector_builder<T, Derived>::reshape (unsigned int npatterns,
 172                                      unsigned int nelts_per_pattern)
 173 {
 174   unsigned int old_encoded_nelts = encoded_nelts ();
 175   unsigned int new_encoded_nelts = npatterns * nelts_per_pattern;
 176   gcc_checking_assert (new_encoded_nelts <= old_encoded_nelts);
 177   unsigned int next = new_encoded_nelts - npatterns;
 178   for (unsigned int i = new_encoded_nelts; i < old_encoded_nelts; ++i)
 179     {
 180       derived ()->note_representative (&(*this)[next], (*this)[i]);
 181       next += 1;
 182       if (next == new_encoded_nelts)
 183         next -= npatterns;
 184     }
 185   m_npatterns = npatterns;
 186   m_nelts_per_pattern = nelts_per_pattern;
 187 }
 188
 189 /* Return true if elements [START, END) contain a repeating sequence of
 190    STEP elements.  */
 191
 192 template<typename T, typename Derived>
 193 bool
 194 vector_builder<T, Derived>::repeating_sequence_p (unsigned int start,
 195                                                   unsigned int end,
 196                                                   unsigned int step)
 197 {
 198   for (unsigned int i = start; i < end - step; ++i)
 199     if (!derived ()->equal_p ((*this)[i], (*this)[i + step]))
 200       return false;
 201   return true;
 202 }
 203
 204 /* Return true if elements [START, END) contain STEP interleaved linear
 205    series.  */
 206
 207 template<typename T, typename Derived>
 208 bool
 209 vector_builder<T, Derived>::stepped_sequence_p (unsigned int start,
 210                                                 unsigned int end,
 211                                                 unsigned int step)
 212 {
 213   if (!derived ()->allow_steps_p ())
 214     return false;
 215
 216   for (unsigned int i = start + step * 2; i < end; ++i)
 217     {
 218       T elt1 = (*this)[i - step * 2];
 219       T elt2 = (*this)[i - step];
 220       T elt3 = (*this)[i];
 221
 222       if (!derived ()->integral_p (elt1)
 223           || !derived ()->integral_p (elt2)
 224           || !derived ()->integral_p (elt3))
 225         return false;
 226
 227       if (derived ()->step (elt1, elt2) != derived ()->step (elt2, elt3))
 228         return false;
 229
 230       if (!derived ()->can_elide_p (elt3))
 231         return false;
 232     }
 233   return true;
 234 }
 235
 236 /* Try to change the number of encoded patterns to NPATTERNS, returning
 237    true on success.  */
 238
 239 template<typename T, typename Derived>
 240 bool
 241 vector_builder<T, Derived>::try_npatterns (unsigned int npatterns)
 242 {
 243   if (m_nelts_per_pattern == 1)
 244     {
 245       /* See whether NPATTERNS is valid with the current 1-element-per-pattern
 246          encoding.  */
 247       if (repeating_sequence_p (0, encoded_nelts (), npatterns))
 248         {
 249           reshape (npatterns, 1);
 250           return true;
 251         }
 252
 253       /* We can only increase the number of elements per pattern if all
 254          elements are still encoded explicitly.  */
 255       if (!encoded_full_vector_p ())
 256         return false;
 257     }
 258
 259   if (m_nelts_per_pattern <= 2)
 260     {
 261       /* See whether NPATTERNS is valid with a 2-element-per-pattern
 262          encoding.  */
 263       if (repeating_sequence_p (npatterns, encoded_nelts (), npatterns))
 264         {
 265           reshape (npatterns, 2);
 266           return true;
 267         }
 268
 269       /* We can only increase the number of elements per pattern if all
 270          elements are still encoded explicitly.  */
 271       if (!encoded_full_vector_p ())
 272         return false;
 273     }
 274
 275   if (m_nelts_per_pattern <= 3)
 276     {
 277       /* See whether we have NPATTERNS interleaved linear series,
 278          giving a 3-element-per-pattern encoding.  */
 279       if (stepped_sequence_p (npatterns, encoded_nelts (), npatterns))
 280         {
 281           reshape (npatterns, 3);
 282           return true;
 283         }
 284       return false;
 285     }
 286
 287   gcc_unreachable ();
 288 }
 289
 290 /* Replace the current encoding with the canonical form.  */
 291
 292 template<typename T, typename Derived>
 293 void
 294 vector_builder<T, Derived>::finalize ()
 295 {
 296   /* The encoding requires the same number of elements to come from each
 297      pattern.  */
 298   gcc_assert (m_full_nelts % m_npatterns == 0);
 299
 300   /* Allow the caller to build more elements than necessary.  For example,
 301      it's often convenient to build a stepped vector from the natural
 302      encoding of three elements even if the vector itself only has two.  */
 303   if (m_full_nelts <= encoded_nelts ())
 304     {
 305       m_npatterns = m_full_nelts;
 306       m_nelts_per_pattern = 1;
 307     }
 308
 309   /* Try to whittle down the number of elements per pattern.  That is:
 310
 311      1. If we have stepped patterns whose steps are all 0, reduce the
 312         number of elements per pattern from 3 to 2.
 313
 314      2. If we have background fill values that are the same as the
 315         foreground values, reduce the number of elements per pattern
 316         from 2 to 1.  */
 317   while (m_nelts_per_pattern > 1
 318          && repeating_sequence_p (encoded_nelts () - m_npatterns * 2,
 319                                   encoded_nelts (), m_npatterns))
 320     /* The last two sequences of M_NPATTERNS elements are equal,
 321        so remove the last one.  */
 322     reshape (m_npatterns, m_nelts_per_pattern - 1);
 323
 324   if (pow2p_hwi (m_npatterns))
 325     {
 326       /* Try to halve the number of patterns while doing so gives a
 327          valid pattern.  This approach is linear in the number of
 328          elements, whereas searcing from 1 up would be O(n*log(n)).
 329
 330          Each halving step tries to keep the number of elements per pattern
 331          the same.  If that isn't possible, and if all elements are still
 332          explicitly encoded, the halving step can instead increase the number
 333          of elements per pattern.
 334
 335          E.g. for:
 336
 337              { 0, 2, 3, 4, 5, 6, 7, 8 }  npatterns == 8  full_nelts == 8
 338
 339          we first realize that the second half of the sequence is not
 340          equal to the first, so we cannot maintain 1 element per pattern
 341          for npatterns == 4.  Instead we halve the number of patterns
 342          and double the number of elements per pattern, treating this
 343          as a "foreground" { 0, 2, 3, 4 } against a "background" of
 344          { 5, 6, 7, 8 | 5, 6, 7, 8 ... }:
 345
 346              { 0, 2, 3, 4 | 5, 6, 7, 8 }  npatterns == 4
 347
 348          Next we realize that this is *not* a foreround of { 0, 2 }
 349          against a background of { 3, 4 | 3, 4 ... }, so the only
 350          remaining option for reducing the number of patterns is
 351          to use a foreground of { 0, 2 } against a stepped background
 352          of { 1, 2 | 3, 4 | 5, 6 ... }.  This is valid because we still
 353          haven't elided any elements:
 354
 355              { 0, 2 | 3, 4 | 5, 6 }  npatterns == 2
 356
 357          This in turn can be reduced to a foreground of { 0 } against a
 358          stepped background of { 1 | 2 | 3 ... }:
 359
 360              { 0 | 2 | 3 }  npatterns == 1
 361
 362          This last step would not have been possible for:
 363
 364              { 0, 0 | 3, 4 | 5, 6 }  npatterns == 2.  */
 365       while ((m_npatterns & 1) == 0 && try_npatterns (m_npatterns / 2))
 366         continue;
 367
 368       /* Builders of arbitrary fixed-length vectors can use:
 369
 370              new_vector (x, x, 1)
 371
 372          so that every element is specified explicitly.  Handle cases
 373          that are actually wrapping series, like { 0, 1, 2, 3, 0, 1, 2, 3 }
 374          would be for 2-bit elements.  We'll have treated them as
 375          duplicates in the loop above.  */
 376       if (m_nelts_per_pattern == 1
 377           && this->length () >= m_full_nelts
 378           && (m_npatterns & 3) == 0
 379           && stepped_sequence_p (m_npatterns / 4, m_full_nelts,
 380                                  m_npatterns / 4))
 381         {
 382           reshape (m_npatterns / 4, 3);
 383           while ((m_npatterns & 1) == 0 && try_npatterns (m_npatterns / 2))
 384             continue;
 385         }
 386     }
 387   else
 388     /* For the non-power-of-2 case, do a simple search up from 1.  */
 389     for (unsigned int i = 1; i <= m_npatterns / 2; ++i)
 390       if (m_npatterns % i == 0 && try_npatterns (i))
 391         break;
 392 }
 393
 394 #endif