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       T apply_step (T base, unsigned int factor, StepType step) const;
  72
  73           Return a vector element with the value BASE + FACTOR * STEP.
  74
  75       bool can_elide_p (T elt) const;
  76
  77           Return true if we can drop element ELT, even if the retained
  78           elements are different.  This is provided for TREE_OVERFLOW
  79           handling.
  80
  81       void note_representative (T *elt1_ptr, T elt2);
  82
  83           Record that ELT2 is being elided, given that ELT1_PTR points to
  84           the last encoded element for the containing pattern.  This is
  85           again provided for TREE_OVERFLOW handling.  */
  86
  87 template<typename T, typename Derived>
  88 class vector_builder : public auto_vec<T, 32>
  89 {
  90 public:
  91   vector_builder ();
  92
  93   unsigned int full_nelts () const { return m_full_nelts; }
  94   unsigned int npatterns () const { return m_npatterns; }
  95   unsigned int nelts_per_pattern () const { return m_nelts_per_pattern; }
  96   unsigned int encoded_nelts () const;
  97   bool encoded_full_vector_p () const;
  98   T elt (unsigned int) const;
  99
 100   void finalize ();
 101
 102 protected:
 103   void new_vector (unsigned int, unsigned int, unsigned int);
 104   void reshape (unsigned int, unsigned int);
 105   bool repeating_sequence_p (unsigned int, unsigned int, unsigned int);
 106   bool stepped_sequence_p (unsigned int, unsigned int, unsigned int);
 107   bool try_npatterns (unsigned int);
 108
 109 private:
 110   vector_builder (const vector_builder &);
 111   vector_builder &operator= (const vector_builder &);
 112   Derived *derived () { return static_cast<Derived *> (this); }
 113   const Derived *derived () const;
 114
 115   unsigned int m_full_nelts;
 116   unsigned int m_npatterns;
 117   unsigned int m_nelts_per_pattern;
 118 };
 119
 120 template<typename T, typename Derived>
 121 inline const Derived *
 122 vector_builder<T, Derived>::derived () const
 123 {
 124   return static_cast<const Derived *> (this);
 125 }
 126
 127 template<typename T, typename Derived>
 128 inline
 129 vector_builder<T, Derived>::vector_builder ()
 130   : m_full_nelts (0),
 131     m_npatterns (0),
 132     m_nelts_per_pattern (0)
 133 {}
 134
 135 /* Return the number of elements that are explicitly encoded.  The vec
 136    starts with these explicitly-encoded elements and may contain additional
 137    elided elements.  */
 138
 139 template<typename T, typename Derived>
 140 inline unsigned int
 141 vector_builder<T, Derived>::encoded_nelts () const
 142 {
 143   return m_npatterns * m_nelts_per_pattern;
 144 }
 145
 146 /* Return true if every element of the vector is explicitly encoded.  */
 147
 148 template<typename T, typename Derived>
 149 inline bool
 150 vector_builder<T, Derived>::encoded_full_vector_p () const
 151 {
 152   return m_npatterns * m_nelts_per_pattern == m_full_nelts;
 153 }
 154
 155 /* Start building a vector that has FULL_NELTS elements.  Initially
 156    encode it using NPATTERNS patterns with NELTS_PER_PATTERN each.  */
 157
 158 template<typename T, typename Derived>
 159 void
 160 vector_builder<T, Derived>::new_vector (unsigned int full_nelts,
 161                                         unsigned int npatterns,
 162                                         unsigned int nelts_per_pattern)
 163 {
 164   m_full_nelts = full_nelts;
 165   m_npatterns = npatterns;
 166   m_nelts_per_pattern = nelts_per_pattern;
 167   this->reserve (encoded_nelts ());
 168   this->truncate (0);
 169 }
 170
 171 /* Return the value of vector element I, which might or might not be
 172    encoded explicitly.  */
 173
 174 template<typename T, typename Derived>
 175 T
 176 vector_builder<T, Derived>::elt (unsigned int i) const
 177 {
 178   /* This only makes sense if the encoding has been fully populated.  */
 179   gcc_checking_assert (encoded_nelts () <= this->length ());
 180
 181   /* First handle elements that are already present in the underlying
 182      vector, regardless of whether they're part of the encoding or not.  */
 183   if (i < this->length ())
 184     return (*this)[i];
 185
 186   /* Identify the pattern that contains element I and work out the index of
 187      the last encoded element for that pattern.  */
 188   unsigned int pattern = i % m_npatterns;
 189   unsigned int count = i / m_npatterns;
 190   unsigned int final_i = encoded_nelts () - m_npatterns + pattern;
 191   T final = (*this)[final_i];
 192
 193   /* If there are no steps, the final encoded value is the right one.  */
 194   if (m_nelts_per_pattern <= 2)
 195     return final;
 196
 197   /* Otherwise work out the value from the last two encoded elements.  */
 198   T prev = (*this)[final_i - m_npatterns];
 199   return derived ()->apply_step (final, count - 2,
 200                                  derived ()->step (prev, final));
 201 }
 202
 203 /* Change the encoding to NPATTERNS patterns of NELTS_PER_PATTERN each,
 204    but without changing the underlying vector.  */
 205
 206 template<typename T, typename Derived>
 207 void
 208 vector_builder<T, Derived>::reshape (unsigned int npatterns,
 209                                      unsigned int nelts_per_pattern)
 210 {
 211   unsigned int old_encoded_nelts = encoded_nelts ();
 212   unsigned int new_encoded_nelts = npatterns * nelts_per_pattern;
 213   gcc_checking_assert (new_encoded_nelts <= old_encoded_nelts);
 214   unsigned int next = new_encoded_nelts - npatterns;
 215   for (unsigned int i = new_encoded_nelts; i < old_encoded_nelts; ++i)
 216     {
 217       derived ()->note_representative (&(*this)[next], (*this)[i]);
 218       next += 1;
 219       if (next == new_encoded_nelts)
 220         next -= npatterns;
 221     }
 222   m_npatterns = npatterns;
 223   m_nelts_per_pattern = nelts_per_pattern;
 224 }
 225
 226 /* Return true if elements [START, END) contain a repeating sequence of
 227    STEP elements.  */
 228
 229 template<typename T, typename Derived>
 230 bool
 231 vector_builder<T, Derived>::repeating_sequence_p (unsigned int start,
 232                                                   unsigned int end,
 233                                                   unsigned int step)
 234 {
 235   for (unsigned int i = start; i < end - step; ++i)
 236     if (!derived ()->equal_p ((*this)[i], (*this)[i + step]))
 237       return false;
 238   return true;
 239 }
 240
 241 /* Return true if elements [START, END) contain STEP interleaved linear
 242    series.  */
 243
 244 template<typename T, typename Derived>
 245 bool
 246 vector_builder<T, Derived>::stepped_sequence_p (unsigned int start,
 247                                                 unsigned int end,
 248                                                 unsigned int step)
 249 {
 250   if (!derived ()->allow_steps_p ())
 251     return false;
 252
 253   for (unsigned int i = start + step * 2; i < end; ++i)
 254     {
 255       T elt1 = (*this)[i - step * 2];
 256       T elt2 = (*this)[i - step];
 257       T elt3 = (*this)[i];
 258
 259       if (!derived ()->integral_p (elt1)
 260           || !derived ()->integral_p (elt2)
 261           || !derived ()->integral_p (elt3))
 262         return false;
 263
 264       if (derived ()->step (elt1, elt2) != derived ()->step (elt2, elt3))
 265         return false;
 266
 267       if (!derived ()->can_elide_p (elt3))
 268         return false;
 269     }
 270   return true;
 271 }
 272
 273 /* Try to change the number of encoded patterns to NPATTERNS, returning
 274    true on success.  */
 275
 276 template<typename T, typename Derived>
 277 bool
 278 vector_builder<T, Derived>::try_npatterns (unsigned int npatterns)
 279 {
 280   if (m_nelts_per_pattern == 1)
 281     {
 282       /* See whether NPATTERNS is valid with the current 1-element-per-pattern
 283          encoding.  */
 284       if (repeating_sequence_p (0, encoded_nelts (), npatterns))
 285         {
 286           reshape (npatterns, 1);
 287           return true;
 288         }
 289
 290       /* We can only increase the number of elements per pattern if all
 291          elements are still encoded explicitly.  */
 292       if (!encoded_full_vector_p ())
 293         return false;
 294     }
 295
 296   if (m_nelts_per_pattern <= 2)
 297     {
 298       /* See whether NPATTERNS is valid with a 2-element-per-pattern
 299          encoding.  */
 300       if (repeating_sequence_p (npatterns, encoded_nelts (), npatterns))
 301         {
 302           reshape (npatterns, 2);
 303           return true;
 304         }
 305
 306       /* We can only increase the number of elements per pattern if all
 307          elements are still encoded explicitly.  */
 308       if (!encoded_full_vector_p ())
 309         return false;
 310     }
 311
 312   if (m_nelts_per_pattern <= 3)
 313     {
 314       /* See whether we have NPATTERNS interleaved linear series,
 315          giving a 3-element-per-pattern encoding.  */
 316       if (stepped_sequence_p (npatterns, encoded_nelts (), npatterns))
 317         {
 318           reshape (npatterns, 3);
 319           return true;
 320         }
 321       return false;
 322     }
 323
 324   gcc_unreachable ();
 325 }
 326
 327 /* Replace the current encoding with the canonical form.  */
 328
 329 template<typename T, typename Derived>
 330 void
 331 vector_builder<T, Derived>::finalize ()
 332 {
 333   /* The encoding requires the same number of elements to come from each
 334      pattern.  */
 335   gcc_assert (m_full_nelts % m_npatterns == 0);
 336
 337   /* Allow the caller to build more elements than necessary.  For example,
 338      it's often convenient to build a stepped vector from the natural
 339      encoding of three elements even if the vector itself only has two.  */
 340   if (m_full_nelts <= encoded_nelts ())
 341     {
 342       m_npatterns = m_full_nelts;
 343       m_nelts_per_pattern = 1;
 344     }
 345
 346   /* Try to whittle down the number of elements per pattern.  That is:
 347
 348      1. If we have stepped patterns whose steps are all 0, reduce the
 349         number of elements per pattern from 3 to 2.
 350
 351      2. If we have background fill values that are the same as the
 352         foreground values, reduce the number of elements per pattern
 353         from 2 to 1.  */
 354   while (m_nelts_per_pattern > 1
 355          && repeating_sequence_p (encoded_nelts () - m_npatterns * 2,
 356                                   encoded_nelts (), m_npatterns))
 357     /* The last two sequences of M_NPATTERNS elements are equal,
 358        so remove the last one.  */
 359     reshape (m_npatterns, m_nelts_per_pattern - 1);
 360
 361   if (pow2p_hwi (m_npatterns))
 362     {
 363       /* Try to halve the number of patterns while doing so gives a
 364          valid pattern.  This approach is linear in the number of
 365          elements, whereas searcing from 1 up would be O(n*log(n)).
 366
 367          Each halving step tries to keep the number of elements per pattern
 368          the same.  If that isn't possible, and if all elements are still
 369          explicitly encoded, the halving step can instead increase the number
 370          of elements per pattern.
 371
 372          E.g. for:
 373
 374              { 0, 2, 3, 4, 5, 6, 7, 8 }  npatterns == 8  full_nelts == 8
 375
 376          we first realize that the second half of the sequence is not
 377          equal to the first, so we cannot maintain 1 element per pattern
 378          for npatterns == 4.  Instead we halve the number of patterns
 379          and double the number of elements per pattern, treating this
 380          as a "foreground" { 0, 2, 3, 4 } against a "background" of
 381          { 5, 6, 7, 8 | 5, 6, 7, 8 ... }:
 382
 383              { 0, 2, 3, 4 | 5, 6, 7, 8 }  npatterns == 4
 384
 385          Next we realize that this is *not* a foreround of { 0, 2 }
 386          against a background of { 3, 4 | 3, 4 ... }, so the only
 387          remaining option for reducing the number of patterns is
 388          to use a foreground of { 0, 2 } against a stepped background
 389          of { 1, 2 | 3, 4 | 5, 6 ... }.  This is valid because we still
 390          haven't elided any elements:
 391
 392              { 0, 2 | 3, 4 | 5, 6 }  npatterns == 2
 393
 394          This in turn can be reduced to a foreground of { 0 } against a
 395          stepped background of { 1 | 2 | 3 ... }:
 396
 397              { 0 | 2 | 3 }  npatterns == 1
 398
 399          This last step would not have been possible for:
 400
 401              { 0, 0 | 3, 4 | 5, 6 }  npatterns == 2.  */
 402       while ((m_npatterns & 1) == 0 && try_npatterns (m_npatterns / 2))
 403         continue;
 404
 405       /* Builders of arbitrary fixed-length vectors can use:
 406
 407              new_vector (x, x, 1)
 408
 409          so that every element is specified explicitly.  Handle cases
 410          that are actually wrapping series, like { 0, 1, 2, 3, 0, 1, 2, 3 }
 411          would be for 2-bit elements.  We'll have treated them as
 412          duplicates in the loop above.  */
 413       if (m_nelts_per_pattern == 1
 414           && this->length () >= m_full_nelts
 415           && (m_npatterns & 3) == 0
 416           && stepped_sequence_p (m_npatterns / 4, m_full_nelts,
 417                                  m_npatterns / 4))
 418         {
 419           reshape (m_npatterns / 4, 3);
 420           while ((m_npatterns & 1) == 0 && try_npatterns (m_npatterns / 2))
 421             continue;
 422         }
 423     }
 424   else
 425     /* For the non-power-of-2 case, do a simple search up from 1.  */
 426     for (unsigned int i = 1; i <= m_npatterns / 2; ++i)
 427       if (m_npatterns % i == 0 && try_npatterns (i))
 428         break;
 429 }
 430
 431 #endif