1 | /* RTL iterators |
2 | Copyright (C) 2014-2023 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 | 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 (UNLIKELY (heap != 0)) |
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 (LIKELY (x != 0)) |
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 (LIKELY (m_end + count <= LOCAL_ELEMS + 1)) |
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 (UNLIKELY (count > 2)) |
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 ()) |
293 | |