1/* Iterator routines for manipulating GENERIC and GIMPLE tree statements.
2   Copyright (C) 2003-2015 Free Software Foundation, Inc.
3   Contributed by Andrew MacLeod  <amacleod@redhat.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3.  If not see
19<http://www.gnu.org/licenses/>.  */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "hash-set.h"
25#include "machmode.h"
26#include "vec.h"
27#include "double-int.h"
28#include "input.h"
29#include "alias.h"
30#include "symtab.h"
31#include "options.h"
32#include "wide-int.h"
33#include "inchash.h"
34#include "tree.h"
35#include "tree-iterator.h"
36#include "ggc.h"
37
38
39/* This is a cache of STATEMENT_LIST nodes.  We create and destroy them
40   fairly often during gimplification.  */
41
42static GTY ((deletable (""))) vec<tree, va_gc> *stmt_list_cache;
43
44tree
45alloc_stmt_list (void)
46{
47  tree list;
48  if (!vec_safe_is_empty (stmt_list_cache))
49    {
50      list = stmt_list_cache->pop ();
51      memset (list, 0, sizeof (struct tree_base));
52      TREE_SET_CODE (list, STATEMENT_LIST);
53    }
54  else
55    list = make_node (STATEMENT_LIST);
56  TREE_TYPE (list) = void_type_node;
57  return list;
58}
59
60void
61free_stmt_list (tree t)
62{
63  gcc_assert (!STATEMENT_LIST_HEAD (t));
64  gcc_assert (!STATEMENT_LIST_TAIL (t));
65  vec_safe_push (stmt_list_cache, t);
66}
67
68/* A subroutine of append_to_statement_list{,_force}.  T is not NULL.  */
69
70static void
71append_to_statement_list_1 (tree t, tree *list_p)
72{
73  tree list = *list_p;
74  tree_stmt_iterator i;
75
76  if (!list)
77    {
78      if (t && TREE_CODE (t) == STATEMENT_LIST)
79	{
80	  *list_p = t;
81	  return;
82	}
83      *list_p = list = alloc_stmt_list ();
84    }
85  else if (TREE_CODE (list) != STATEMENT_LIST)
86    {
87      tree first = list;
88      *list_p = list = alloc_stmt_list ();
89      i = tsi_last (list);
90      tsi_link_after (&i, first, TSI_CONTINUE_LINKING);
91    }
92
93  i = tsi_last (list);
94  tsi_link_after (&i, t, TSI_CONTINUE_LINKING);
95}
96
97/* Add T to the end of the list container pointed to by LIST_P.
98   If T is an expression with no effects, it is ignored.  */
99
100void
101append_to_statement_list (tree t, tree *list_p)
102{
103  if (t && TREE_SIDE_EFFECTS (t))
104    append_to_statement_list_1 (t, list_p);
105}
106
107/* Similar, but the statement is always added, regardless of side effects.  */
108
109void
110append_to_statement_list_force (tree t, tree *list_p)
111{
112  if (t != NULL_TREE)
113    append_to_statement_list_1 (t, list_p);
114}
115
116/* Links a statement, or a chain of statements, before the current stmt.  */
117
118void
119tsi_link_before (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
120{
121  struct tree_statement_list_node *head, *tail, *cur;
122
123  /* Die on looping.  */
124  gcc_assert (t != i->container);
125
126  if (TREE_CODE (t) == STATEMENT_LIST)
127    {
128      head = STATEMENT_LIST_HEAD (t);
129      tail = STATEMENT_LIST_TAIL (t);
130      STATEMENT_LIST_HEAD (t) = NULL;
131      STATEMENT_LIST_TAIL (t) = NULL;
132
133      free_stmt_list (t);
134
135      /* Empty statement lists need no work.  */
136      if (!head || !tail)
137	{
138	  gcc_assert (head == tail);
139	  return;
140	}
141    }
142  else
143    {
144      head = ggc_alloc<tree_statement_list_node> ();
145      head->prev = NULL;
146      head->next = NULL;
147      head->stmt = t;
148      tail = head;
149    }
150
151  TREE_SIDE_EFFECTS (i->container) = 1;
152
153  cur = i->ptr;
154
155  /* Link it into the list.  */
156  if (cur)
157    {
158      head->prev = cur->prev;
159      if (head->prev)
160	head->prev->next = head;
161      else
162	STATEMENT_LIST_HEAD (i->container) = head;
163      tail->next = cur;
164      cur->prev = tail;
165    }
166  else
167    {
168      head->prev = STATEMENT_LIST_TAIL (i->container);
169      if (head->prev)
170       head->prev->next = head;
171      else
172       STATEMENT_LIST_HEAD (i->container) = head;
173      STATEMENT_LIST_TAIL (i->container) = tail;
174    }
175
176  /* Update the iterator, if requested.  */
177  switch (mode)
178    {
179    case TSI_NEW_STMT:
180    case TSI_CONTINUE_LINKING:
181    case TSI_CHAIN_START:
182      i->ptr = head;
183      break;
184    case TSI_CHAIN_END:
185      i->ptr = tail;
186      break;
187    case TSI_SAME_STMT:
188      break;
189    }
190}
191
192/* Links a statement, or a chain of statements, after the current stmt.  */
193
194void
195tsi_link_after (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
196{
197  struct tree_statement_list_node *head, *tail, *cur;
198
199  /* Die on looping.  */
200  gcc_assert (t != i->container);
201
202  if (TREE_CODE (t) == STATEMENT_LIST)
203    {
204      head = STATEMENT_LIST_HEAD (t);
205      tail = STATEMENT_LIST_TAIL (t);
206      STATEMENT_LIST_HEAD (t) = NULL;
207      STATEMENT_LIST_TAIL (t) = NULL;
208
209      free_stmt_list (t);
210
211      /* Empty statement lists need no work.  */
212      if (!head || !tail)
213	{
214	  gcc_assert (head == tail);
215	  return;
216	}
217    }
218  else
219    {
220      head = ggc_alloc<tree_statement_list_node> ();
221      head->prev = NULL;
222      head->next = NULL;
223      head->stmt = t;
224      tail = head;
225    }
226
227  TREE_SIDE_EFFECTS (i->container) = 1;
228
229  cur = i->ptr;
230
231  /* Link it into the list.  */
232  if (cur)
233    {
234      tail->next = cur->next;
235      if (tail->next)
236	tail->next->prev = tail;
237      else
238	STATEMENT_LIST_TAIL (i->container) = tail;
239      head->prev = cur;
240      cur->next = head;
241    }
242  else
243    {
244      gcc_assert (!STATEMENT_LIST_TAIL (i->container));
245      STATEMENT_LIST_HEAD (i->container) = head;
246      STATEMENT_LIST_TAIL (i->container) = tail;
247    }
248
249  /* Update the iterator, if requested.  */
250  switch (mode)
251    {
252    case TSI_NEW_STMT:
253    case TSI_CHAIN_START:
254      i->ptr = head;
255      break;
256    case TSI_CONTINUE_LINKING:
257    case TSI_CHAIN_END:
258      i->ptr = tail;
259      break;
260    case TSI_SAME_STMT:
261      gcc_assert (cur);
262      break;
263    }
264}
265
266/* Remove a stmt from the tree list.  The iterator is updated to point to
267   the next stmt.  */
268
269void
270tsi_delink (tree_stmt_iterator *i)
271{
272  struct tree_statement_list_node *cur, *next, *prev;
273
274  cur = i->ptr;
275  next = cur->next;
276  prev = cur->prev;
277
278  if (prev)
279    prev->next = next;
280  else
281    STATEMENT_LIST_HEAD (i->container) = next;
282  if (next)
283    next->prev = prev;
284  else
285    STATEMENT_LIST_TAIL (i->container) = prev;
286
287  if (!next && !prev)
288    TREE_SIDE_EFFECTS (i->container) = 0;
289
290  i->ptr = next;
291}
292
293/* Return the first expression in a sequence of COMPOUND_EXPRs,
294   or in a STATEMENT_LIST.  */
295
296tree
297expr_first (tree expr)
298{
299  if (expr == NULL_TREE)
300    return expr;
301
302  if (TREE_CODE (expr) == STATEMENT_LIST)
303    {
304      struct tree_statement_list_node *n = STATEMENT_LIST_HEAD (expr);
305      return n ? n->stmt : NULL_TREE;
306    }
307
308  while (TREE_CODE (expr) == COMPOUND_EXPR)
309    expr = TREE_OPERAND (expr, 0);
310
311  return expr;
312}
313
314/* Return the last expression in a sequence of COMPOUND_EXPRs,
315   or in a STATEMENT_LIST.  */
316
317tree
318expr_last (tree expr)
319{
320  if (expr == NULL_TREE)
321    return expr;
322
323  if (TREE_CODE (expr) == STATEMENT_LIST)
324    {
325      struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr);
326      return n ? n->stmt : NULL_TREE;
327    }
328
329  while (TREE_CODE (expr) == COMPOUND_EXPR)
330    expr = TREE_OPERAND (expr, 1);
331
332  return expr;
333}
334
335#include "gt-tree-iterator.h"
336