gcc/vec-perm-indices.c

   1 /* A representation of vector permutation indices.
   2    Copyright (C) 2017-2018 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 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "vec-perm-indices.h"
  24 #include "tree.h"
  25 #include "fold-const.h"
  26 #include "tree-vector-builder.h"
  27 #include "backend.h"
  28 #include "rtl.h"
  29 #include "memmodel.h"
  30 #include "emit-rtl.h"
  31 #include "selftest.h"
  32 #include "rtx-vector-builder.h"
  33
  34 /* Switch to a new permutation vector that selects between NINPUTS vector
  35    inputs that have NELTS_PER_INPUT elements each.  Take the elements of the
  36    new permutation vector from ELEMENTS, clamping each one to be in range.  */
  37
  38 void
  39 vec_perm_indices::new_vector (const vec_perm_builder &elements,
  40                               unsigned int ninputs,
  41                               poly_uint64 nelts_per_input)
  42 {
  43   m_ninputs = ninputs;
  44   m_nelts_per_input = nelts_per_input;
  45   /* If the vector has a constant number of elements, expand the
  46      encoding and clamp each element.  E.g. { 0, 2, 4, ... } might
  47      wrap halfway if there is only one vector input, and we want
  48      the wrapped form to be the canonical one.
  49
  50      If the vector has a variable number of elements, just copy
  51      the encoding.  In that case the unwrapped form is canonical
  52      and there is no way of representing the wrapped form.  */
  53   poly_uint64 full_nelts = elements.full_nelts ();
  54   unsigned HOST_WIDE_INT copy_nelts;
  55   if (full_nelts.is_constant (&copy_nelts))
  56     m_encoding.new_vector (full_nelts, copy_nelts, 1);
  57   else
  58     {
  59       copy_nelts = elements.encoded_nelts ();
  60       m_encoding.new_vector (full_nelts, elements.npatterns (),
  61                              elements.nelts_per_pattern ());
  62     }
  63   unsigned int npatterns = m_encoding.npatterns ();
  64   for (unsigned int i = 0; i < npatterns; ++i)
  65     m_encoding.quick_push (clamp (elements.elt (i)));
  66   /* Use the fact that:
  67
  68         (a + b) % c == ((a % c) + (b % c)) % c
  69
  70      to simplify the clamping of variable-length vectors.  */
  71   for (unsigned int i = npatterns; i < copy_nelts; ++i)
  72     {
  73       element_type step = clamp (elements.elt (i)
  74                                  - elements.elt (i - npatterns));
  75       m_encoding.quick_push (clamp (m_encoding[i - npatterns] + step));
  76     }
  77   m_encoding.finalize ();
  78 }
  79
  80 /* Switch to a new permutation vector that selects the same input elements
  81    as ORIG, but with each element split into FACTOR pieces.  For example,
  82    if ORIG is { 1, 2, 0, 3 } and FACTOR is 2, the new permutation is
  83    { 2, 3, 4, 5, 0, 1, 6, 7 }.  */
  84
  85 void
  86 vec_perm_indices::new_expanded_vector (const vec_perm_indices &orig,
  87                                        unsigned int factor)
  88 {
  89   m_ninputs = orig.m_ninputs;
  90   m_nelts_per_input = orig.m_nelts_per_input * factor;
  91   m_encoding.new_vector (orig.m_encoding.full_nelts () * factor,
  92                          orig.m_encoding.npatterns () * factor,
  93                          orig.m_encoding.nelts_per_pattern ());
  94   unsigned int encoded_nelts = orig.m_encoding.encoded_nelts ();
  95   for (unsigned int i = 0; i < encoded_nelts; ++i)
  96     {
  97       element_type base = orig.m_encoding[i] * factor;
  98       for (unsigned int j = 0; j < factor; ++j)
  99         m_encoding.quick_push (base + j);
 100     }
 101   m_encoding.finalize ();
 102 }
 103
 104 /* Rotate the inputs of the permutation right by DELTA inputs.  This changes
 105    the values of the permutation vector but it doesn't change the way that
 106    the elements are encoded.  */
 107
 108 void
 109 vec_perm_indices::rotate_inputs (int delta)
 110 {
 111   element_type element_delta = delta * m_nelts_per_input;
 112   for (unsigned int i = 0; i < m_encoding.length (); ++i)
 113     m_encoding[i] = clamp (m_encoding[i] + element_delta);
 114 }
 115
 116 /* Return true if index OUT_BASE + I * OUT_STEP selects input
 117    element IN_BASE + I * IN_STEP.  */
 118
 119 bool
 120 vec_perm_indices::series_p (unsigned int out_base, unsigned int out_step,
 121                             element_type in_base, element_type in_step) const
 122 {
 123   /* Check the base value.  */
 124   if (maybe_ne (clamp (m_encoding.elt (out_base)), clamp (in_base)))
 125     return false;
 126
 127   element_type full_nelts = m_encoding.full_nelts ();
 128   unsigned int npatterns = m_encoding.npatterns ();
 129
 130   /* Calculate which multiple of OUT_STEP elements we need to get
 131      back to the same pattern.  */
 132   unsigned int cycle_length = least_common_multiple (out_step, npatterns);
 133
 134   /* Check the steps.  */
 135   in_step = clamp (in_step);
 136   out_base += out_step;
 137   unsigned int limit = 0;
 138   for (;;)
 139     {
 140       /* Succeed if we've checked all the elements in the vector.  */
 141       if (known_ge (out_base, full_nelts))
 142         return true;
 143
 144       if (out_base >= npatterns)
 145         {
 146           /* We've got to the end of the "foreground" values.  Check
 147              2 elements from each pattern in the "background" values.  */
 148           if (limit == 0)
 149             limit = out_base + cycle_length * 2;
 150           else if (out_base >= limit)
 151             return true;
 152         }
 153
 154       element_type v0 = m_encoding.elt (out_base - out_step);
 155       element_type v1 = m_encoding.elt (out_base);
 156       if (maybe_ne (clamp (v1 - v0), in_step))
 157         return false;
 158
 159       out_base += out_step;
 160     }
 161   return true;
 162 }
 163
 164 /* Return true if all elements of the permutation vector are in the range
 165    [START, START + SIZE).  */
 166
 167 bool
 168 vec_perm_indices::all_in_range_p (element_type start, element_type size) const
 169 {
 170   /* Check the first two elements of each pattern.  */
 171   unsigned int npatterns = m_encoding.npatterns ();
 172   unsigned int nelts_per_pattern = m_encoding.nelts_per_pattern ();
 173   unsigned int base_nelts = npatterns * MIN (nelts_per_pattern, 2);
 174   for (unsigned int i = 0; i < base_nelts; ++i)
 175     if (!known_in_range_p (m_encoding[i], start, size))
 176       return false;
 177
 178   /* For stepped encodings, check the full range of the series.  */
 179   if (nelts_per_pattern == 3)
 180     {
 181       element_type limit = input_nelts ();
 182
 183       /* The number of elements in each pattern beyond the first two
 184          that we checked above.  */
 185       poly_int64 step_nelts = exact_div (m_encoding.full_nelts (),
 186                                          npatterns) - 2;
 187       for (unsigned int i = 0; i < npatterns; ++i)
 188         {
 189           /* BASE1 has been checked but BASE2 hasn't.   */
 190           element_type base1 = m_encoding[i + npatterns];
 191           element_type base2 = m_encoding[i + base_nelts];
 192
 193           /* The step to add to get from BASE1 to each subsequent value.  */
 194           element_type step = clamp (base2 - base1);
 195
 196           /* STEP has no inherent sign, so a value near LIMIT can
 197              act as a negative step.  The series is in range if it
 198              is in range according to one of the two interpretations.
 199
 200              Since we're dealing with clamped values, ELEMENT_TYPE is
 201              wide enough for overflow not to be a problem.  */
 202           element_type headroom_down = base1 - start;
 203           element_type headroom_up = size - headroom_down - 1;
 204           HOST_WIDE_INT diff;
 205           if ((!step.is_constant (&diff)
 206                || maybe_lt (headroom_up, diff * step_nelts))
 207               && (!(limit - step).is_constant (&diff)
 208                   || maybe_lt (headroom_down, diff * step_nelts)))
 209             return false;
 210         }
 211     }
 212   return true;
 213 }
 214
 215 /* Try to read the contents of VECTOR_CST CST as a constant permutation
 216    vector.  Return true and add the elements to BUILDER on success,
 217    otherwise return false without modifying BUILDER.  */
 218
 219 bool
 220 tree_to_vec_perm_builder (vec_perm_builder *builder, tree cst)
 221 {
 222   unsigned int encoded_nelts = vector_cst_encoded_nelts (cst);
 223   for (unsigned int i = 0; i < encoded_nelts; ++i)
 224     if (!tree_fits_poly_int64_p (VECTOR_CST_ENCODED_ELT (cst, i)))
 225       return false;
 226
 227   builder->new_vector (TYPE_VECTOR_SUBPARTS (TREE_TYPE (cst)),
 228                        VECTOR_CST_NPATTERNS (cst),
 229                        VECTOR_CST_NELTS_PER_PATTERN (cst));
 230   for (unsigned int i = 0; i < encoded_nelts; ++i)
 231     builder->quick_push (tree_to_poly_int64 (VECTOR_CST_ENCODED_ELT (cst, i)));
 232   return true;
 233 }
 234
 235 /* Return a VECTOR_CST of type TYPE for the permutation vector in INDICES.  */
 236
 237 tree
 238 vec_perm_indices_to_tree (tree type, const vec_perm_indices &indices)
 239 {
 240   gcc_assert (known_eq (TYPE_VECTOR_SUBPARTS (type), indices.length ()));
 241   tree_vector_builder sel (type, indices.encoding ().npatterns (),
 242                            indices.encoding ().nelts_per_pattern ());
 243   unsigned int encoded_nelts = sel.encoded_nelts ();
 244   for (unsigned int i = 0; i < encoded_nelts; i++)
 245     sel.quick_push (build_int_cst (TREE_TYPE (type), indices[i]));
 246   return sel.build ();
 247 }
 248
 249 /* Return a CONST_VECTOR of mode MODE that contains the elements of
 250    INDICES.  */
 251
 252 rtx
 253 vec_perm_indices_to_rtx (machine_mode mode, const vec_perm_indices &indices)
 254 {
 255   gcc_assert (GET_MODE_CLASS (mode) == MODE_VECTOR_INT
 256               && known_eq (GET_MODE_NUNITS (mode), indices.length ()));
 257   rtx_vector_builder sel (mode, indices.encoding ().npatterns (),
 258                           indices.encoding ().nelts_per_pattern ());
 259   unsigned int encoded_nelts = sel.encoded_nelts ();
 260   for (unsigned int i = 0; i < encoded_nelts; i++)
 261     sel.quick_push (gen_int_mode (indices[i], GET_MODE_INNER (mode)));
 262   return sel.build ();
 263 }
 264
 265 #if CHECKING_P
 266
 267 namespace selftest {
 268
 269 /* Test a 12-element vector.  */
 270
 271 static void
 272 test_vec_perm_12 (void)
 273 {
 274   vec_perm_builder builder (12, 12, 1);
 275   for (unsigned int i = 0; i < 4; ++i)
 276     {
 277       builder.quick_push (i * 5);
 278       builder.quick_push (3 + i);
 279       builder.quick_push (2 + 3 * i);
 280     }
 281   vec_perm_indices indices (builder, 1, 12);
 282   ASSERT_TRUE (indices.series_p (0, 3, 0, 5));
 283   ASSERT_FALSE (indices.series_p (0, 3, 3, 5));
 284   ASSERT_FALSE (indices.series_p (0, 3, 0, 8));
 285   ASSERT_TRUE (indices.series_p (1, 3, 3, 1));
 286   ASSERT_TRUE (indices.series_p (2, 3, 2, 3));
 287
 288   ASSERT_TRUE (indices.series_p (0, 4, 0, 4));
 289   ASSERT_FALSE (indices.series_p (1, 4, 3, 4));
 290
 291   ASSERT_TRUE (indices.series_p (0, 6, 0, 10));
 292   ASSERT_FALSE (indices.series_p (0, 6, 0, 100));
 293
 294   ASSERT_FALSE (indices.series_p (1, 10, 3, 7));
 295   ASSERT_TRUE (indices.series_p (1, 10, 3, 8));
 296
 297   ASSERT_TRUE (indices.series_p (0, 12, 0, 10));
 298   ASSERT_TRUE (indices.series_p (0, 12, 0, 11));
 299   ASSERT_TRUE (indices.series_p (0, 12, 0, 100));
 300 }
 301
 302 /* Run selftests for this file.  */
 303
 304 void
 305 vec_perm_indices_c_tests ()
 306 {
 307   test_vec_perm_12 ();
 308 }
 309
 310 } // namespace selftest
 311
 312 #endif