1 /* RTL iterators 2 Copyright (C) 2014-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 /* 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 ()) 292