1 /* RTL iterators
2 Copyright (C) 2014-2021 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
leaf_code_p(enum rtx_code code)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>
array_type()112 inline generic_subrtx_iterator <T>::array_type::array_type () : heap (0) {}
113
114 template <typename T>
~array_type()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>::
generic_subrtx_iterator(array_type & array,value_type x,const rtx_subrtx_bound_info * bounds)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
at_end()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
next()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
skip_subrtxes()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
substitute(value_type x)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;
get_rtxconst_rtx_accessor242 static rtx_type get_rtx (value_type x) { return x; }
get_valueconst_rtx_accessor243 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;
get_rtxrtx_var_accessor253 static rtx_type get_rtx (value_type x) { return x; }
get_valuertx_var_accessor254 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;
get_rtxrtx_ptr_accessor264 static rtx_type get_rtx (value_type ptr) { return *ptr; }
get_valuertx_ptr_accessor265 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 ())
293