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