gcc/rtl-iter.h

   1 /* RTL iterators
   2    Copyright (C) 2014-2020 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 /* This structure describes the subrtxes of an rtx as follows:
  21
  22    - if the rtx has no subrtxes, START and COUNT are both 0.
  23
  24    - if all the subrtxes of an rtx are stored in a contiguous block
  25      of XEXPs ("e"s), START is the index of the first XEXP and COUNT
  26      is the number of them.
  27
  28    - otherwise START is arbitrary and COUNT is UCHAR_MAX.
  29
  30    rtx_all_subrtx_bounds applies to all codes.  rtx_nonconst_subrtx_bounds
  31    is like rtx_all_subrtx_bounds except that all constant rtxes are treated
  32    as having no subrtxes.  */
  33 struct rtx_subrtx_bound_info {
  34   unsigned char start;
  35   unsigned char count;
  36 };
  37 extern rtx_subrtx_bound_info rtx_all_subrtx_bounds[];
  38 extern rtx_subrtx_bound_info rtx_nonconst_subrtx_bounds[];
  39
  40 /* Return true if CODE has no subrtxes.  */
  41
  42 static inline bool
  43 leaf_code_p (enum rtx_code code)
  44 {
  45   return rtx_all_subrtx_bounds[code].count == 0;
  46 }
  47
  48 /* Used to iterate over subrtxes of an rtx.  T abstracts the type of
  49    access.  */
  50 template <typename T>
  51 class generic_subrtx_iterator
  52 {
  53   static const size_t LOCAL_ELEMS = 16;
  54   typedef typename T::value_type value_type;
  55   typedef typename T::rtx_type rtx_type;
  56   typedef typename T::rtunion_type rtunion_type;
  57
  58 public:
  59   class array_type
  60   {
  61   public:
  62     array_type ();
  63     ~array_type ();
  64     value_type stack[LOCAL_ELEMS];
  65     vec <value_type, va_heap, vl_embed> *heap;
  66   };
  67   generic_subrtx_iterator (array_type &, value_type,
  68                            const rtx_subrtx_bound_info *);
  69
  70   value_type operator * () const;
  71   bool at_end () const;
  72   void next ();
  73   void skip_subrtxes ();
  74   void substitute (value_type);
  75
  76 private:
  77   /* The bounds to use for iterating over subrtxes.  */
  78   const rtx_subrtx_bound_info *m_bounds;
  79
  80   /* The storage used for the worklist.  */
  81   array_type &m_array;
  82
  83   /* The current rtx.  */
  84   value_type m_current;
  85
  86   /* The base of the current worklist.  */
  87   value_type *m_base;
  88
  89   /* The number of subrtxes in M_BASE.  */
  90   size_t m_end;
  91
  92   /* The following booleans shouldn't end up in registers or memory
  93      but just direct control flow.  */
  94
  95   /* True if the iteration is over.  */
  96   bool m_done;
  97
  98   /* True if we should skip the subrtxes of M_CURRENT.  */
  99   bool m_skip;
 100
 101   /* True if M_CURRENT has been replaced with a different rtx.  */
 102   bool m_substitute;
 103
 104   static void free_array (array_type &);
 105   static size_t add_subrtxes_to_queue (array_type &, value_type *, size_t,
 106                                        rtx_type);
 107   static value_type *add_single_to_queue (array_type &, value_type *, size_t,
 108                                           value_type);
 109 };
 110
 111 template <typename T>
 112 inline generic_subrtx_iterator <T>::array_type::array_type () : heap (0) {}
 113
 114 template <typename T>
 115 inline generic_subrtx_iterator <T>::array_type::~array_type ()
 116 {
 117   if (__builtin_expect (heap != 0, false))
 118     free_array (*this);
 119 }
 120
 121 /* Iterate over X and its subrtxes, in arbitrary order.  Use ARRAY to
 122    store the worklist.  We use an external array in order to avoid
 123    capturing the fields of this structure when taking the address of
 124    the array.  Use BOUNDS to find the bounds of simple "e"-string codes.  */
 125
 126 template <typename T>
 127 inline generic_subrtx_iterator <T>::
 128 generic_subrtx_iterator (array_type &array, value_type x,
 129                          const rtx_subrtx_bound_info *bounds)
 130   : m_bounds (bounds),
 131     m_array (array),
 132     m_current (x),
 133     m_base (m_array.stack),
 134     m_end (0),
 135     m_done (false),
 136     m_skip (false),
 137     m_substitute (false)
 138 {
 139 }
 140
 141 /* Return the current subrtx.  */
 142
 143 template <typename T>
 144 inline typename T::value_type
 145 generic_subrtx_iterator <T>::operator * () const
 146 {
 147   return m_current;
 148 }
 149
 150 /* Return true if the iteration has finished.  */
 151
 152 template <typename T>
 153 inline bool
 154 generic_subrtx_iterator <T>::at_end () const
 155 {
 156   return m_done;
 157 }
 158
 159 /* Move on to the next subrtx.  */
 160
 161 template <typename T>
 162 inline void
 163 generic_subrtx_iterator <T>::next ()
 164 {
 165   if (m_substitute)
 166     {
 167       m_substitute = false;
 168       m_skip = false;
 169       return;
 170     }
 171   if (!m_skip)
 172     {
 173       /* Add the subrtxes of M_CURRENT.  */
 174       rtx_type x = T::get_rtx (m_current);
 175       if (__builtin_expect (x != 0, true))
 176         {
 177           enum rtx_code code = GET_CODE (x);
 178           ssize_t count = m_bounds[code].count;
 179           if (count > 0)
 180             {
 181               /* Handle the simple case of a single "e" block that is known
 182                  to fit into the current array.  */
 183               if (__builtin_expect (m_end + count <= LOCAL_ELEMS + 1, true))
 184                 {
 185                   /* Set M_CURRENT to the first subrtx and queue the rest.  */
 186                   ssize_t start = m_bounds[code].start;
 187                   rtunion_type *src = &x->u.fld[start];
 188                   if (__builtin_expect (count > 2, false))
 189                     m_base[m_end++] = T::get_value (src[2].rt_rtx);
 190                   if (count > 1)
 191                     m_base[m_end++] = T::get_value (src[1].rt_rtx);
 192                   m_current = T::get_value (src[0].rt_rtx);
 193                   return;
 194                 }
 195               /* Handle cases which aren't simple "e" sequences or where
 196                  the sequence might overrun M_BASE.  */
 197               count = add_subrtxes_to_queue (m_array, m_base, m_end, x);
 198               if (count > 0)
 199                 {
 200                   m_end += count;
 201                   if (m_end > LOCAL_ELEMS)
 202                     m_base = m_array.heap->address ();
 203                   m_current = m_base[--m_end];
 204                   return;
 205                 }
 206             }
 207         }
 208     }
 209   else
 210     m_skip = false;
 211   if (m_end == 0)
 212     m_done = true;
 213   else
 214     m_current = m_base[--m_end];
 215 }
 216
 217 /* Skip the subrtxes of the current rtx.  */
 218
 219 template <typename T>
 220 inline void
 221 generic_subrtx_iterator <T>::skip_subrtxes ()
 222 {
 223   m_skip = true;
 224 }
 225
 226 /* Ignore the subrtxes of the current rtx and look at X instead.  */
 227
 228 template <typename T>
 229 inline void
 230 generic_subrtx_iterator <T>::substitute (value_type x)
 231 {
 232   m_substitute = true;
 233   m_current = x;
 234 }
 235
 236 /* Iterators for const_rtx.  */
 237 struct const_rtx_accessor
 238 {
 239   typedef const_rtx value_type;
 240   typedef const_rtx rtx_type;
 241   typedef const rtunion rtunion_type;
 242   static rtx_type get_rtx (value_type x) { return x; }
 243   static value_type get_value (rtx_type x) { return x; }
 244 };
 245 typedef generic_subrtx_iterator <const_rtx_accessor> subrtx_iterator;
 246
 247 /* Iterators for non-constant rtx.  */
 248 struct rtx_var_accessor
 249 {
 250   typedef rtx value_type;
 251   typedef rtx rtx_type;
 252   typedef rtunion rtunion_type;
 253   static rtx_type get_rtx (value_type x) { return x; }
 254   static value_type get_value (rtx_type x) { return x; }
 255 };
 256 typedef generic_subrtx_iterator <rtx_var_accessor> subrtx_var_iterator;
 257
 258 /* Iterators for rtx *.  */
 259 struct rtx_ptr_accessor
 260 {
 261   typedef rtx *value_type;
 262   typedef rtx rtx_type;
 263   typedef rtunion rtunion_type;
 264   static rtx_type get_rtx (value_type ptr) { return *ptr; }
 265   static value_type get_value (rtx_type &x) { return &x; }
 266 };
 267 typedef generic_subrtx_iterator <rtx_ptr_accessor> subrtx_ptr_iterator;
 268
 269 #define ALL_BOUNDS rtx_all_subrtx_bounds
 270 #define NONCONST_BOUNDS rtx_nonconst_subrtx_bounds
 271
 272 /* Use ITER to iterate over const_rtx X and its recursive subrtxes,
 273    using subrtx_iterator::array ARRAY as the storage for the worklist.
 274    ARRAY can be reused for multiple consecutive iterations but shouldn't
 275    be shared by two concurrent iterations.  TYPE is ALL if all subrtxes
 276    are of interest or NONCONST if it is safe to ignore subrtxes of
 277    constants.  */
 278 #define FOR_EACH_SUBRTX(ITER, ARRAY, X, TYPE) \
 279   for (subrtx_iterator ITER (ARRAY, X, TYPE##_BOUNDS); !ITER.at_end (); \
 280        ITER.next ())
 281
 282 /* Like FOR_EACH_SUBRTX, but iterate over subrtxes of an rtx X.  */
 283 #define FOR_EACH_SUBRTX_VAR(ITER, ARRAY, X, TYPE) \
 284   for (subrtx_var_iterator ITER (ARRAY, X, TYPE##_BOUNDS); !ITER.at_end (); \
 285        ITER.next ())
 286
 287 /* Like FOR_EACH_SUBRTX, but iterate over subrtx pointers of rtx pointer X.
 288    For example, if X is &PATTERN (insn) and the pattern is a SET, iterate
 289    over &PATTERN (insn), &SET_DEST (PATTERN (insn)), etc.  */
 290 #define FOR_EACH_SUBRTX_PTR(ITER, ARRAY, X, TYPE) \
 291   for (subrtx_ptr_iterator ITER (ARRAY, X, TYPE##_BOUNDS); !ITER.at_end (); \
 292        ITER.next ())