111
|
1 /* RTL iterators
|
145
|
2 Copyright (C) 2014-2020 Free Software Foundation, Inc.
|
111
|
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:
|
145
|
59 class array_type
|
111
|
60 {
|
145
|
61 public:
|
111
|
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 (__builtin_expect (heap != 0, false))
|
|
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 (__builtin_expect (x != 0, true))
|
|
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 (__builtin_expect (m_end + count <= LOCAL_ELEMS + 1, true))
|
|
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 (__builtin_expect (count > 2, false))
|
|
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 ())
|