gcc/rtl-iter.h

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