gcc/vec-perm-indices.c

   1 /* A representation of vector permutation indices.
   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 #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
  32 /* Switch to a new permutation vector that selects between NINPUTS vector
  33    inputs that have NELTS_PER_INPUT elements each.  Take the elements of the
  34    new permutation vector from ELEMENTS, clamping each one to be in range.  */
  35
  36 void
  37 vec_perm_indices::new_vector (const vec_perm_builder &elements,
  38                               unsigned int ninputs,
  39                               unsigned int nelts_per_input)
  40 {
  41   m_ninputs = ninputs;
  42   m_nelts_per_input = nelts_per_input;
  43   /* Expand the encoding and clamp each element.  E.g. { 0, 2, 4, ... }
  44      might wrap halfway if there is only one vector input.  */
  45   unsigned int full_nelts = elements.full_nelts ();
  46   m_encoding.new_vector (full_nelts, full_nelts, 1);
  47   for (unsigned int i = 0; i < full_nelts; ++i)
  48     m_encoding.quick_push (clamp (elements.elt (i)));
  49   m_encoding.finalize ();
  50 }
  51
  52 /* Switch to a new permutation vector that selects the same input elements
  53    as ORIG, but with each element split into FACTOR pieces.  For example,
  54    if ORIG is { 1, 2, 0, 3 } and FACTOR is 2, the new permutation is
  55    { 2, 3, 4, 5, 0, 1, 6, 7 }.  */
  56
  57 void
  58 vec_perm_indices::new_expanded_vector (const vec_perm_indices &orig,
  59                                        unsigned int factor)
  60 {
  61   m_ninputs = orig.m_ninputs;
  62   m_nelts_per_input = orig.m_nelts_per_input * factor;
  63   m_encoding.new_vector (orig.m_encoding.full_nelts () * factor,
  64                          orig.m_encoding.npatterns () * factor,
  65                          orig.m_encoding.nelts_per_pattern ());
  66   unsigned int encoded_nelts = orig.m_encoding.encoded_nelts ();
  67   for (unsigned int i = 0; i < encoded_nelts; ++i)
  68     {
  69       element_type base = orig.m_encoding[i] * factor;
  70       for (unsigned int j = 0; j < factor; ++j)
  71         m_encoding.quick_push (base + j);
  72     }
  73   m_encoding.finalize ();
  74 }
  75
  76 /* Rotate the inputs of the permutation right by DELTA inputs.  This changes
  77    the values of the permutation vector but it doesn't change the way that
  78    the elements are encoded.  */
  79
  80 void
  81 vec_perm_indices::rotate_inputs (int delta)
  82 {
  83   element_type element_delta = delta * m_nelts_per_input;
  84   for (unsigned int i = 0; i < m_encoding.length (); ++i)
  85     m_encoding[i] = clamp (m_encoding[i] + element_delta);
  86 }
  87
  88 /* Return true if all elements of the permutation vector are in the range
  89    [START, START + SIZE).  */
  90
  91 bool
  92 vec_perm_indices::all_in_range_p (element_type start, element_type size) const
  93 {
  94   /* Check the first two elements of each pattern.  */
  95   unsigned int npatterns = m_encoding.npatterns ();
  96   unsigned int nelts_per_pattern = m_encoding.nelts_per_pattern ();
  97   unsigned int base_nelts = npatterns * MIN (nelts_per_pattern, 2);
  98   for (unsigned int i = 0; i < base_nelts; ++i)
  99     if (m_encoding[i] < start || (m_encoding[i] - start) >= size)
 100       return false;
 101
 102   /* For stepped encodings, check the full range of the series.  */
 103   if (nelts_per_pattern == 3)
 104     {
 105       element_type limit = input_nelts ();
 106
 107       /* The number of elements in each pattern beyond the first two
 108          that we checked above.  */
 109       unsigned int step_nelts = (m_encoding.full_nelts () / npatterns) - 2;
 110       for (unsigned int i = 0; i < npatterns; ++i)
 111         {
 112           /* BASE1 has been checked but BASE2 hasn't.   */
 113           element_type base1 = m_encoding[i + npatterns];
 114           element_type base2 = m_encoding[i + base_nelts];
 115
 116           /* The step to add to get from BASE1 to each subsequent value.  */
 117           element_type step = clamp (base2 - base1);
 118
 119           /* STEP has no inherent sign, so a value near LIMIT can
 120              act as a negative step.  The series is in range if it
 121              is in range according to one of the two interpretations.
 122
 123              Since we're dealing with clamped values, ELEMENT_TYPE is
 124              wide enough for overflow not to be a problem.  */
 125           element_type headroom_down = base1 - start;
 126           element_type headroom_up = size - headroom_down - 1;
 127           if (headroom_up < step * step_nelts
 128               && headroom_down < (limit - step) * step_nelts)
 129             return false;
 130         }
 131     }
 132   return true;
 133 }
 134
 135 /* Try to read the contents of VECTOR_CST CST as a constant permutation
 136    vector.  Return true and add the elements to BUILDER on success,
 137    otherwise return false without modifying BUILDER.  */
 138
 139 bool
 140 tree_to_vec_perm_builder (vec_perm_builder *builder, tree cst)
 141 {
 142   unsigned int encoded_nelts = vector_cst_encoded_nelts (cst);
 143   for (unsigned int i = 0; i < encoded_nelts; ++i)
 144     if (!tree_fits_shwi_p (VECTOR_CST_ENCODED_ELT (cst, i)))
 145       return false;
 146
 147   builder->new_vector (TYPE_VECTOR_SUBPARTS (TREE_TYPE (cst)),
 148                        VECTOR_CST_NPATTERNS (cst),
 149                        VECTOR_CST_NELTS_PER_PATTERN (cst));
 150   for (unsigned int i = 0; i < encoded_nelts; ++i)
 151     builder->quick_push (tree_to_shwi (VECTOR_CST_ENCODED_ELT (cst, i)));
 152   return true;
 153 }
 154
 155 /* Return a VECTOR_CST of type TYPE for the permutation vector in INDICES.  */
 156
 157 tree
 158 vec_perm_indices_to_tree (tree type, const vec_perm_indices &indices)
 159 {
 160   gcc_assert (TYPE_VECTOR_SUBPARTS (type) == indices.length ());
 161   tree_vector_builder sel (type, indices.encoding ().npatterns (),
 162                            indices.encoding ().nelts_per_pattern ());
 163   unsigned int encoded_nelts = sel.encoded_nelts ();
 164   for (unsigned int i = 0; i < encoded_nelts; i++)
 165     sel.quick_push (build_int_cst (TREE_TYPE (type), indices[i]));
 166   return sel.build ();
 167 }
 168
 169 /* Return a CONST_VECTOR of mode MODE that contains the elements of
 170    INDICES.  */
 171
 172 rtx
 173 vec_perm_indices_to_rtx (machine_mode mode, const vec_perm_indices &indices)
 174 {
 175   gcc_assert (GET_MODE_CLASS (mode) == MODE_VECTOR_INT
 176               && GET_MODE_NUNITS (mode) == indices.length ());
 177   unsigned int nelts = indices.length ();
 178   rtvec v = rtvec_alloc (nelts);
 179   for (unsigned int i = 0; i < nelts; ++i)
 180     RTVEC_ELT (v, i) = gen_int_mode (indices[i], GET_MODE_INNER (mode));
 181   return gen_rtx_CONST_VECTOR (mode, v);
 182 }