]>
Commit | Line | Data |
---|---|---|
69924e56 | 1 | /* RTL iterators |
fbd26352 | 2 | Copyright (C) 2014-2019 Free Software Foundation, Inc. |
69924e56 | 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 ()) |