1*38fd1498Szrj /* RTL iterators
2*38fd1498Szrj Copyright (C) 2014-2018 Free Software Foundation, Inc.
3*38fd1498Szrj
4*38fd1498Szrj This file is part of GCC.
5*38fd1498Szrj
6*38fd1498Szrj GCC is free software; you can redistribute it and/or modify it under
7*38fd1498Szrj the terms of the GNU General Public License as published by the Free
8*38fd1498Szrj Software Foundation; either version 3, or (at your option) any later
9*38fd1498Szrj version.
10*38fd1498Szrj
11*38fd1498Szrj GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12*38fd1498Szrj WARRANTY; without even the implied warranty of MERCHANTABILITY or
13*38fd1498Szrj FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14*38fd1498Szrj for more details.
15*38fd1498Szrj
16*38fd1498Szrj You should have received a copy of the GNU General Public License
17*38fd1498Szrj along with GCC; see the file COPYING3. If not see
18*38fd1498Szrj <http://www.gnu.org/licenses/>. */
19*38fd1498Szrj
20*38fd1498Szrj /* This structure describes the subrtxes of an rtx as follows:
21*38fd1498Szrj
22*38fd1498Szrj - if the rtx has no subrtxes, START and COUNT are both 0.
23*38fd1498Szrj
24*38fd1498Szrj - if all the subrtxes of an rtx are stored in a contiguous block
25*38fd1498Szrj of XEXPs ("e"s), START is the index of the first XEXP and COUNT
26*38fd1498Szrj is the number of them.
27*38fd1498Szrj
28*38fd1498Szrj - otherwise START is arbitrary and COUNT is UCHAR_MAX.
29*38fd1498Szrj
30*38fd1498Szrj rtx_all_subrtx_bounds applies to all codes. rtx_nonconst_subrtx_bounds
31*38fd1498Szrj is like rtx_all_subrtx_bounds except that all constant rtxes are treated
32*38fd1498Szrj as having no subrtxes. */
33*38fd1498Szrj struct rtx_subrtx_bound_info {
34*38fd1498Szrj unsigned char start;
35*38fd1498Szrj unsigned char count;
36*38fd1498Szrj };
37*38fd1498Szrj extern rtx_subrtx_bound_info rtx_all_subrtx_bounds[];
38*38fd1498Szrj extern rtx_subrtx_bound_info rtx_nonconst_subrtx_bounds[];
39*38fd1498Szrj
40*38fd1498Szrj /* Return true if CODE has no subrtxes. */
41*38fd1498Szrj
42*38fd1498Szrj static inline bool
leaf_code_p(enum rtx_code code)43*38fd1498Szrj leaf_code_p (enum rtx_code code)
44*38fd1498Szrj {
45*38fd1498Szrj return rtx_all_subrtx_bounds[code].count == 0;
46*38fd1498Szrj }
47*38fd1498Szrj
48*38fd1498Szrj /* Used to iterate over subrtxes of an rtx. T abstracts the type of
49*38fd1498Szrj access. */
50*38fd1498Szrj template <typename T>
51*38fd1498Szrj class generic_subrtx_iterator
52*38fd1498Szrj {
53*38fd1498Szrj static const size_t LOCAL_ELEMS = 16;
54*38fd1498Szrj typedef typename T::value_type value_type;
55*38fd1498Szrj typedef typename T::rtx_type rtx_type;
56*38fd1498Szrj typedef typename T::rtunion_type rtunion_type;
57*38fd1498Szrj
58*38fd1498Szrj public:
59*38fd1498Szrj struct array_type
60*38fd1498Szrj {
61*38fd1498Szrj array_type ();
62*38fd1498Szrj ~array_type ();
63*38fd1498Szrj value_type stack[LOCAL_ELEMS];
64*38fd1498Szrj vec <value_type, va_heap, vl_embed> *heap;
65*38fd1498Szrj };
66*38fd1498Szrj generic_subrtx_iterator (array_type &, value_type,
67*38fd1498Szrj const rtx_subrtx_bound_info *);
68*38fd1498Szrj
69*38fd1498Szrj value_type operator * () const;
70*38fd1498Szrj bool at_end () const;
71*38fd1498Szrj void next ();
72*38fd1498Szrj void skip_subrtxes ();
73*38fd1498Szrj void substitute (value_type);
74*38fd1498Szrj
75*38fd1498Szrj private:
76*38fd1498Szrj /* The bounds to use for iterating over subrtxes. */
77*38fd1498Szrj const rtx_subrtx_bound_info *m_bounds;
78*38fd1498Szrj
79*38fd1498Szrj /* The storage used for the worklist. */
80*38fd1498Szrj array_type &m_array;
81*38fd1498Szrj
82*38fd1498Szrj /* The current rtx. */
83*38fd1498Szrj value_type m_current;
84*38fd1498Szrj
85*38fd1498Szrj /* The base of the current worklist. */
86*38fd1498Szrj value_type *m_base;
87*38fd1498Szrj
88*38fd1498Szrj /* The number of subrtxes in M_BASE. */
89*38fd1498Szrj size_t m_end;
90*38fd1498Szrj
91*38fd1498Szrj /* The following booleans shouldn't end up in registers or memory
92*38fd1498Szrj but just direct control flow. */
93*38fd1498Szrj
94*38fd1498Szrj /* True if the iteration is over. */
95*38fd1498Szrj bool m_done;
96*38fd1498Szrj
97*38fd1498Szrj /* True if we should skip the subrtxes of M_CURRENT. */
98*38fd1498Szrj bool m_skip;
99*38fd1498Szrj
100*38fd1498Szrj /* True if M_CURRENT has been replaced with a different rtx. */
101*38fd1498Szrj bool m_substitute;
102*38fd1498Szrj
103*38fd1498Szrj static void free_array (array_type &);
104*38fd1498Szrj static size_t add_subrtxes_to_queue (array_type &, value_type *, size_t,
105*38fd1498Szrj rtx_type);
106*38fd1498Szrj static value_type *add_single_to_queue (array_type &, value_type *, size_t,
107*38fd1498Szrj value_type);
108*38fd1498Szrj };
109*38fd1498Szrj
110*38fd1498Szrj template <typename T>
array_type()111*38fd1498Szrj inline generic_subrtx_iterator <T>::array_type::array_type () : heap (0) {}
112*38fd1498Szrj
113*38fd1498Szrj template <typename T>
~array_type()114*38fd1498Szrj inline generic_subrtx_iterator <T>::array_type::~array_type ()
115*38fd1498Szrj {
116*38fd1498Szrj if (__builtin_expect (heap != 0, false))
117*38fd1498Szrj free_array (*this);
118*38fd1498Szrj }
119*38fd1498Szrj
120*38fd1498Szrj /* Iterate over X and its subrtxes, in arbitrary order. Use ARRAY to
121*38fd1498Szrj store the worklist. We use an external array in order to avoid
122*38fd1498Szrj capturing the fields of this structure when taking the address of
123*38fd1498Szrj the array. Use BOUNDS to find the bounds of simple "e"-string codes. */
124*38fd1498Szrj
125*38fd1498Szrj template <typename T>
126*38fd1498Szrj inline generic_subrtx_iterator <T>::
generic_subrtx_iterator(array_type & array,value_type x,const rtx_subrtx_bound_info * bounds)127*38fd1498Szrj generic_subrtx_iterator (array_type &array, value_type x,
128*38fd1498Szrj const rtx_subrtx_bound_info *bounds)
129*38fd1498Szrj : m_bounds (bounds),
130*38fd1498Szrj m_array (array),
131*38fd1498Szrj m_current (x),
132*38fd1498Szrj m_base (m_array.stack),
133*38fd1498Szrj m_end (0),
134*38fd1498Szrj m_done (false),
135*38fd1498Szrj m_skip (false),
136*38fd1498Szrj m_substitute (false)
137*38fd1498Szrj {
138*38fd1498Szrj }
139*38fd1498Szrj
140*38fd1498Szrj /* Return the current subrtx. */
141*38fd1498Szrj
142*38fd1498Szrj template <typename T>
143*38fd1498Szrj inline typename T::value_type
144*38fd1498Szrj generic_subrtx_iterator <T>::operator * () const
145*38fd1498Szrj {
146*38fd1498Szrj return m_current;
147*38fd1498Szrj }
148*38fd1498Szrj
149*38fd1498Szrj /* Return true if the iteration has finished. */
150*38fd1498Szrj
151*38fd1498Szrj template <typename T>
152*38fd1498Szrj inline bool
at_end()153*38fd1498Szrj generic_subrtx_iterator <T>::at_end () const
154*38fd1498Szrj {
155*38fd1498Szrj return m_done;
156*38fd1498Szrj }
157*38fd1498Szrj
158*38fd1498Szrj /* Move on to the next subrtx. */
159*38fd1498Szrj
160*38fd1498Szrj template <typename T>
161*38fd1498Szrj inline void
next()162*38fd1498Szrj generic_subrtx_iterator <T>::next ()
163*38fd1498Szrj {
164*38fd1498Szrj if (m_substitute)
165*38fd1498Szrj {
166*38fd1498Szrj m_substitute = false;
167*38fd1498Szrj m_skip = false;
168*38fd1498Szrj return;
169*38fd1498Szrj }
170*38fd1498Szrj if (!m_skip)
171*38fd1498Szrj {
172*38fd1498Szrj /* Add the subrtxes of M_CURRENT. */
173*38fd1498Szrj rtx_type x = T::get_rtx (m_current);
174*38fd1498Szrj if (__builtin_expect (x != 0, true))
175*38fd1498Szrj {
176*38fd1498Szrj enum rtx_code code = GET_CODE (x);
177*38fd1498Szrj ssize_t count = m_bounds[code].count;
178*38fd1498Szrj if (count > 0)
179*38fd1498Szrj {
180*38fd1498Szrj /* Handle the simple case of a single "e" block that is known
181*38fd1498Szrj to fit into the current array. */
182*38fd1498Szrj if (__builtin_expect (m_end + count <= LOCAL_ELEMS + 1, true))
183*38fd1498Szrj {
184*38fd1498Szrj /* Set M_CURRENT to the first subrtx and queue the rest. */
185*38fd1498Szrj ssize_t start = m_bounds[code].start;
186*38fd1498Szrj rtunion_type *src = &x->u.fld[start];
187*38fd1498Szrj if (__builtin_expect (count > 2, false))
188*38fd1498Szrj m_base[m_end++] = T::get_value (src[2].rt_rtx);
189*38fd1498Szrj if (count > 1)
190*38fd1498Szrj m_base[m_end++] = T::get_value (src[1].rt_rtx);
191*38fd1498Szrj m_current = T::get_value (src[0].rt_rtx);
192*38fd1498Szrj return;
193*38fd1498Szrj }
194*38fd1498Szrj /* Handle cases which aren't simple "e" sequences or where
195*38fd1498Szrj the sequence might overrun M_BASE. */
196*38fd1498Szrj count = add_subrtxes_to_queue (m_array, m_base, m_end, x);
197*38fd1498Szrj if (count > 0)
198*38fd1498Szrj {
199*38fd1498Szrj m_end += count;
200*38fd1498Szrj if (m_end > LOCAL_ELEMS)
201*38fd1498Szrj m_base = m_array.heap->address ();
202*38fd1498Szrj m_current = m_base[--m_end];
203*38fd1498Szrj return;
204*38fd1498Szrj }
205*38fd1498Szrj }
206*38fd1498Szrj }
207*38fd1498Szrj }
208*38fd1498Szrj else
209*38fd1498Szrj m_skip = false;
210*38fd1498Szrj if (m_end == 0)
211*38fd1498Szrj m_done = true;
212*38fd1498Szrj else
213*38fd1498Szrj m_current = m_base[--m_end];
214*38fd1498Szrj }
215*38fd1498Szrj
216*38fd1498Szrj /* Skip the subrtxes of the current rtx. */
217*38fd1498Szrj
218*38fd1498Szrj template <typename T>
219*38fd1498Szrj inline void
skip_subrtxes()220*38fd1498Szrj generic_subrtx_iterator <T>::skip_subrtxes ()
221*38fd1498Szrj {
222*38fd1498Szrj m_skip = true;
223*38fd1498Szrj }
224*38fd1498Szrj
225*38fd1498Szrj /* Ignore the subrtxes of the current rtx and look at X instead. */
226*38fd1498Szrj
227*38fd1498Szrj template <typename T>
228*38fd1498Szrj inline void
substitute(value_type x)229*38fd1498Szrj generic_subrtx_iterator <T>::substitute (value_type x)
230*38fd1498Szrj {
231*38fd1498Szrj m_substitute = true;
232*38fd1498Szrj m_current = x;
233*38fd1498Szrj }
234*38fd1498Szrj
235*38fd1498Szrj /* Iterators for const_rtx. */
236*38fd1498Szrj struct const_rtx_accessor
237*38fd1498Szrj {
238*38fd1498Szrj typedef const_rtx value_type;
239*38fd1498Szrj typedef const_rtx rtx_type;
240*38fd1498Szrj typedef const rtunion rtunion_type;
get_rtxconst_rtx_accessor241*38fd1498Szrj static rtx_type get_rtx (value_type x) { return x; }
get_valueconst_rtx_accessor242*38fd1498Szrj static value_type get_value (rtx_type x) { return x; }
243*38fd1498Szrj };
244*38fd1498Szrj typedef generic_subrtx_iterator <const_rtx_accessor> subrtx_iterator;
245*38fd1498Szrj
246*38fd1498Szrj /* Iterators for non-constant rtx. */
247*38fd1498Szrj struct rtx_var_accessor
248*38fd1498Szrj {
249*38fd1498Szrj typedef rtx value_type;
250*38fd1498Szrj typedef rtx rtx_type;
251*38fd1498Szrj typedef rtunion rtunion_type;
get_rtxrtx_var_accessor252*38fd1498Szrj static rtx_type get_rtx (value_type x) { return x; }
get_valuertx_var_accessor253*38fd1498Szrj static value_type get_value (rtx_type x) { return x; }
254*38fd1498Szrj };
255*38fd1498Szrj typedef generic_subrtx_iterator <rtx_var_accessor> subrtx_var_iterator;
256*38fd1498Szrj
257*38fd1498Szrj /* Iterators for rtx *. */
258*38fd1498Szrj struct rtx_ptr_accessor
259*38fd1498Szrj {
260*38fd1498Szrj typedef rtx *value_type;
261*38fd1498Szrj typedef rtx rtx_type;
262*38fd1498Szrj typedef rtunion rtunion_type;
get_rtxrtx_ptr_accessor263*38fd1498Szrj static rtx_type get_rtx (value_type ptr) { return *ptr; }
get_valuertx_ptr_accessor264*38fd1498Szrj static value_type get_value (rtx_type &x) { return &x; }
265*38fd1498Szrj };
266*38fd1498Szrj typedef generic_subrtx_iterator <rtx_ptr_accessor> subrtx_ptr_iterator;
267*38fd1498Szrj
268*38fd1498Szrj #define ALL_BOUNDS rtx_all_subrtx_bounds
269*38fd1498Szrj #define NONCONST_BOUNDS rtx_nonconst_subrtx_bounds
270*38fd1498Szrj
271*38fd1498Szrj /* Use ITER to iterate over const_rtx X and its recursive subrtxes,
272*38fd1498Szrj using subrtx_iterator::array ARRAY as the storage for the worklist.
273*38fd1498Szrj ARRAY can be reused for multiple consecutive iterations but shouldn't
274*38fd1498Szrj be shared by two concurrent iterations. TYPE is ALL if all subrtxes
275*38fd1498Szrj are of interest or NONCONST if it is safe to ignore subrtxes of
276*38fd1498Szrj constants. */
277*38fd1498Szrj #define FOR_EACH_SUBRTX(ITER, ARRAY, X, TYPE) \
278*38fd1498Szrj for (subrtx_iterator ITER (ARRAY, X, TYPE##_BOUNDS); !ITER.at_end (); \
279*38fd1498Szrj ITER.next ())
280*38fd1498Szrj
281*38fd1498Szrj /* Like FOR_EACH_SUBRTX, but iterate over subrtxes of an rtx X. */
282*38fd1498Szrj #define FOR_EACH_SUBRTX_VAR(ITER, ARRAY, X, TYPE) \
283*38fd1498Szrj for (subrtx_var_iterator ITER (ARRAY, X, TYPE##_BOUNDS); !ITER.at_end (); \
284*38fd1498Szrj ITER.next ())
285*38fd1498Szrj
286*38fd1498Szrj /* Like FOR_EACH_SUBRTX, but iterate over subrtx pointers of rtx pointer X.
287*38fd1498Szrj For example, if X is &PATTERN (insn) and the pattern is a SET, iterate
288*38fd1498Szrj over &PATTERN (insn), &SET_DEST (PATTERN (insn)), etc. */
289*38fd1498Szrj #define FOR_EACH_SUBRTX_PTR(ITER, ARRAY, X, TYPE) \
290*38fd1498Szrj for (subrtx_ptr_iterator ITER (ARRAY, X, TYPE##_BOUNDS); !ITER.at_end (); \
291*38fd1498Szrj ITER.next ())
292