Branch data Line data Source code
1 : : /* RTL iterators
2 : : Copyright (C) 2014-2024 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 : 4404451282 : inline generic_subrtx_iterator <T>::array_type::array_type () : heap (0) {}
113 : :
114 : : template <typename T>
115 : 4404451314 : inline generic_subrtx_iterator <T>::array_type::~array_type ()
116 : : {
117 : 4404451314 : if (UNLIKELY (heap != 0))
118 : 245010 : free_array (*this);
119 : 1477325531 : }
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 : 4405394958 : inline generic_subrtx_iterator <T>::
128 : : generic_subrtx_iterator (array_type &array, value_type x,
129 : : const rtx_subrtx_bound_info *bounds)
130 : 4405394958 : : m_bounds (bounds),
131 : 4405394958 : m_array (array),
132 : 4405394958 : m_current (x),
133 : 4405394958 : m_base (m_array.stack),
134 : 4405394958 : m_end (0),
135 : 4405394958 : m_done (false),
136 : 4405394958 : m_skip (false),
137 : 4153501176 : m_substitute (false)
138 : : {
139 : 4405394916 : }
140 : :
141 : : /* Return the current subrtx. */
142 : :
143 : : template <typename T>
144 : : inline typename T::value_type
145 : 16183446924 : generic_subrtx_iterator <T>::operator * () const
146 : : {
147 : 16183446850 : return m_current;
148 : : }
149 : :
150 : : /* Return true if the iteration has finished. */
151 : :
152 : : template <typename T>
153 : : inline bool
154 : 20288765854 : generic_subrtx_iterator <T>::at_end () const
155 : : {
156 : 20288765770 : return m_done;
157 : : }
158 : :
159 : : /* Move on to the next subrtx. */
160 : :
161 : : template <typename T>
162 : : inline void
163 : 15883370896 : generic_subrtx_iterator <T>::next ()
164 : : {
165 : 15883370896 : if (m_substitute)
166 : : {
167 : 442048 : m_substitute = false;
168 : 442048 : m_skip = false;
169 : 442048 : return;
170 : : }
171 : 15882928848 : if (!m_skip)
172 : : {
173 : : /* Add the subrtxes of M_CURRENT. */
174 : 15633298812 : rtx_type x = T::get_rtx (m_current);
175 : 15633298812 : if (LIKELY (x != 0))
176 : : {
177 : 15612051512 : enum rtx_code code = GET_CODE (x);
178 : 15612051512 : ssize_t count = m_bounds[code].count;
179 : 15612051512 : 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 : 6802027265 : if (LIKELY (m_end + count <= LOCAL_ELEMS + 1))
184 : : {
185 : : /* Set M_CURRENT to the first subrtx and queue the rest. */
186 : 6553439967 : ssize_t start = m_bounds[code].start;
187 : 6553439967 : rtunion_type *src = &x->u.fld[start];
188 : 6553439967 : if (UNLIKELY (count > 2))
189 : 430957813 : m_base[m_end++] = T::get_value (src[2].rt_rtx);
190 : 6553439967 : if (count > 1)
191 : 4503469147 : m_base[m_end++] = T::get_value (src[1].rt_rtx);
192 : 6553439967 : m_current = T::get_value (src[0].rt_rtx);
193 : 6553439967 : return;
194 : : }
195 : : /* Handle cases which aren't simple "e" sequences or where
196 : : the sequence might overrun M_BASE. */
197 : 248587298 : count = add_subrtxes_to_queue (m_array, m_base, m_end, x);
198 : 248587298 : if (count > 0)
199 : : {
200 : 247786625 : m_end += count;
201 : 247786625 : if (m_end > LOCAL_ELEMS)
202 : 661324 : m_base = m_array.heap->address ();
203 : 247786625 : m_current = m_base[--m_end];
204 : 247786625 : return;
205 : : }
206 : : }
207 : : }
208 : : }
209 : : else
210 : 249630036 : m_skip = false;
211 : 9081702256 : if (m_end == 0)
212 : 4105318930 : m_done = true;
213 : : else
214 : 4976383326 : 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 : 249630036 : generic_subrtx_iterator <T>::skip_subrtxes ()
222 : : {
223 : 151463950 : m_skip = true;
224 : 232503828 : }
225 : :
226 : : /* Ignore the subrtxes of the current rtx and look at X instead. */
227 : :
228 : : template <typename T>
229 : : inline void
230 : 442048 : generic_subrtx_iterator <T>::substitute (value_type x)
231 : : {
232 : 442048 : m_substitute = true;
233 : 442048 : m_current = x;
234 : 442048 : }
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 : 896325146 : 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 ())
|
