111
|
1 /* RTL iterators
|
131
|
2 Copyright (C) 2014-2018 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:
|
|
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 ())
|