Line data Source code
1 : /* RTL iterators
2 : Copyright (C) 2014-2026 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 5953408445 : inline generic_subrtx_iterator <T>::array_type::array_type () : heap (0) {}
113 :
114 : template <typename T>
115 5953408489 : inline generic_subrtx_iterator <T>::array_type::~array_type ()
116 : {
117 5953408489 : if (UNLIKELY (heap != 0))
118 300478 : free_array (*this);
119 1641837179 : }
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 5954661465 : inline generic_subrtx_iterator <T>::
128 : generic_subrtx_iterator (array_type &array, value_type x,
129 : const rtx_subrtx_bound_info *bounds)
130 5954661465 : : m_bounds (bounds),
131 5954661465 : m_array (array),
132 5954661465 : m_current (x),
133 5954661465 : m_base (m_array.stack),
134 5954661465 : m_end (0),
135 5954661465 : m_done (false),
136 5954661465 : m_skip (false),
137 5649923163 : m_substitute (false)
138 : {
139 5954661411 : }
140 :
141 : /* Return the current subrtx. */
142 :
143 : template <typename T>
144 : inline typename T::value_type
145 20954709300 : generic_subrtx_iterator <T>::operator * () const
146 : {
147 20954709202 : return m_current;
148 : }
149 :
150 : /* Return true if the iteration has finished. */
151 :
152 : template <typename T>
153 : inline bool
154 26598085757 : generic_subrtx_iterator <T>::at_end () const
155 : {
156 26598085649 : return m_done;
157 : }
158 :
159 : /* Move on to the next subrtx. */
160 :
161 : template <typename T>
162 : inline void
163 20643424292 : generic_subrtx_iterator <T>::next ()
164 : {
165 20643424292 : if (m_substitute)
166 : {
167 626067 : m_substitute = false;
168 626067 : m_skip = false;
169 626067 : return;
170 : }
171 20642798225 : if (!m_skip)
172 : {
173 : /* Add the subrtxes of M_CURRENT. */
174 20078938995 : rtx_type x = T::get_rtx (m_current);
175 20078938995 : if (LIKELY (x != 0))
176 : {
177 20036365201 : enum rtx_code code = GET_CODE (x);
178 20036365201 : ssize_t count = m_bounds[code].count;
179 20036365201 : 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 8722339298 : if (LIKELY (m_end + count <= LOCAL_ELEMS + 1))
184 : {
185 : /* Set M_CURRENT to the first subrtx and queue the rest. */
186 8396716067 : ssize_t start = m_bounds[code].start;
187 8396716067 : rtunion_type *src = &x->u.fld[start];
188 8396716067 : if (UNLIKELY (count > 2))
189 559035010 : m_base[m_end++] = T::get_value (src[2].rt_rtx);
190 8396716067 : if (count > 1)
191 5592180756 : m_base[m_end++] = T::get_value (src[1].rt_rtx);
192 8396716067 : m_current = T::get_value (src[0].rt_rtx);
193 8396716067 : return;
194 : }
195 : /* Handle cases which aren't simple "e" sequences or where
196 : the sequence might overrun M_BASE. */
197 325623231 : count = add_subrtxes_to_queue (m_array, m_base, m_end, x);
198 325623231 : if (count > 0)
199 : {
200 324724161 : m_end += count;
201 324724161 : if (m_end > LOCAL_ELEMS)
202 651735 : m_base = m_array.heap->address ();
203 324724161 : m_current = m_base[--m_end];
204 324724161 : return;
205 : }
206 : }
207 : }
208 : }
209 : else
210 563859230 : m_skip = false;
211 11921357997 : if (m_end == 0)
212 5643376457 : m_done = true;
213 : else
214 6277981540 : 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 563859230 : generic_subrtx_iterator <T>::skip_subrtxes ()
222 : {
223 394754598 : m_skip = true;
224 401903577 : }
225 :
226 : /* Ignore the subrtxes of the current rtx and look at X instead. */
227 :
228 : template <typename T>
229 : inline void
230 626067 : generic_subrtx_iterator <T>::substitute (value_type x)
231 : {
232 626067 : m_substitute = true;
233 626067 : m_current = x;
234 626067 : }
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 1016338544 : 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 ())
|
