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