1/* RTL iterators
2   Copyright (C) 2014-2015 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  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
75private:
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
110template <typename T>
111inline generic_subrtx_iterator <T>::array_type::array_type () : heap (0) {}
112
113template <typename T>
114inline 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
125template <typename T>
126inline generic_subrtx_iterator <T>::
127generic_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
142template <typename T>
143inline typename T::value_type
144generic_subrtx_iterator <T>::operator * () const
145{
146  return m_current;
147}
148
149/* Return true if the iteration has finished.  */
150
151template <typename T>
152inline bool
153generic_subrtx_iterator <T>::at_end () const
154{
155  return m_done;
156}
157
158/* Move on to the next subrtx.  */
159
160template <typename T>
161inline void
162generic_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
218template <typename T>
219inline void
220generic_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
227template <typename T>
228inline void
229generic_subrtx_iterator <T>::substitute (value_type x)
230{
231  m_substitute = true;
232  m_current = x;
233}
234
235/* Iterators for const_rtx.  */
236struct 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};
244typedef generic_subrtx_iterator <const_rtx_accessor> subrtx_iterator;
245
246/* Iterators for non-constant rtx.  */
247struct 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};
255typedef generic_subrtx_iterator <rtx_var_accessor> subrtx_var_iterator;
256
257/* Iterators for rtx *.  */
258struct 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};
266typedef 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 ())
292