1/* RTL iterators
2   Copyright (C) 2014-2020 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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.  */
33struct rtx_subrtx_bound_info {
34  unsigned char start;
35  unsigned char count;
36};
37extern rtx_subrtx_bound_info rtx_all_subrtx_bounds[];
38extern rtx_subrtx_bound_info rtx_nonconst_subrtx_bounds[];
39
40/* Return true if CODE has no subrtxes.  */
41
42static inline bool
43leaf_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.  */
50template <typename T>
51class 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
58public:
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
76private:
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
111template <typename T>
112inline generic_subrtx_iterator <T>::array_type::array_type () : heap (0) {}
113
114template <typename T>
115inline 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
126template <typename T>
127inline generic_subrtx_iterator <T>::
128generic_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
143template <typename T>
144inline typename T::value_type
145generic_subrtx_iterator <T>::operator * () const
146{
147  return m_current;
148}
149
150/* Return true if the iteration has finished.  */
151
152template <typename T>
153inline bool
154generic_subrtx_iterator <T>::at_end () const
155{
156  return m_done;
157}
158
159/* Move on to the next subrtx.  */
160
161template <typename T>
162inline void
163generic_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
219template <typename T>
220inline void
221generic_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
228template <typename T>
229inline void
230generic_subrtx_iterator <T>::substitute (value_type x)
231{
232  m_substitute = true;
233  m_current = x;
234}
235
236/* Iterators for const_rtx.  */
237struct 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};
245typedef generic_subrtx_iterator <const_rtx_accessor> subrtx_iterator;
246
247/* Iterators for non-constant rtx.  */
248struct 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};
256typedef generic_subrtx_iterator <rtx_var_accessor> subrtx_var_iterator;
257
258/* Iterators for rtx *.  */
259struct 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};
267typedef 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 ())
293