1/* Iterator routines for manipulating GENERIC and GIMPLE tree statements.
2   Copyright (C) 2003-2022 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 "tree.h"
25#include "tree-iterator.h"
26
27
28/* This is a cache of STATEMENT_LIST nodes.  We create and destroy them
29   fairly often during gimplification.  */
30
31static GTY ((deletable (""))) vec<tree, va_gc> *stmt_list_cache;
32
33tree
34alloc_stmt_list (void)
35{
36  tree list;
37  if (!vec_safe_is_empty (stmt_list_cache))
38    {
39      list = stmt_list_cache->pop ();
40      memset (list, 0, sizeof (struct tree_base));
41      TREE_SET_CODE (list, STATEMENT_LIST);
42    }
43  else
44    {
45      list = make_node (STATEMENT_LIST);
46      TREE_SIDE_EFFECTS (list) = 0;
47    }
48  TREE_TYPE (list) = void_type_node;
49  return list;
50}
51
52void
53free_stmt_list (tree t)
54{
55  gcc_assert (!STATEMENT_LIST_HEAD (t));
56  gcc_assert (!STATEMENT_LIST_TAIL (t));
57  vec_safe_push (stmt_list_cache, t);
58}
59
60/* A subroutine of append_to_statement_list{,_force}.  T is not NULL.  */
61
62static void
63append_to_statement_list_1 (tree t, tree *list_p)
64{
65  tree list = *list_p;
66  tree_stmt_iterator i;
67
68  if (!list)
69    {
70      if (t && TREE_CODE (t) == STATEMENT_LIST)
71	{
72	  *list_p = t;
73	  return;
74	}
75      *list_p = list = alloc_stmt_list ();
76    }
77  else if (TREE_CODE (list) != STATEMENT_LIST)
78    {
79      tree first = list;
80      *list_p = list = alloc_stmt_list ();
81      i = tsi_last (list);
82      tsi_link_after (&i, first, TSI_CONTINUE_LINKING);
83    }
84
85  i = tsi_last (list);
86  tsi_link_after (&i, t, TSI_CONTINUE_LINKING);
87}
88
89/* Add T to the end of the list container pointed to by LIST_P.
90   If T is an expression with no effects, it is ignored.  */
91
92void
93append_to_statement_list (tree t, tree *list_p)
94{
95  if (t && (TREE_SIDE_EFFECTS (t) || TREE_CODE (t) == DEBUG_BEGIN_STMT))
96    append_to_statement_list_1 (t, list_p);
97}
98
99/* Similar, but the statement is always added, regardless of side effects.  */
100
101void
102append_to_statement_list_force (tree t, tree *list_p)
103{
104  if (t != NULL_TREE)
105    append_to_statement_list_1 (t, list_p);
106}
107
108/* Links a statement, or a chain of statements, before the current stmt.  */
109
110void
111tsi_link_before (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
112{
113  struct tree_statement_list_node *head, *tail, *cur;
114
115  /* Die on looping.  */
116  gcc_assert (t != i->container);
117
118  if (TREE_CODE (t) == STATEMENT_LIST)
119    {
120      head = STATEMENT_LIST_HEAD (t);
121      tail = STATEMENT_LIST_TAIL (t);
122      STATEMENT_LIST_HEAD (t) = NULL;
123      STATEMENT_LIST_TAIL (t) = NULL;
124
125      free_stmt_list (t);
126
127      /* Empty statement lists need no work.  */
128      if (!head || !tail)
129	{
130	  gcc_assert (head == tail);
131	  return;
132	}
133    }
134  else
135    {
136      head = ggc_alloc<tree_statement_list_node> ();
137      head->prev = NULL;
138      head->next = NULL;
139      head->stmt = t;
140      tail = head;
141    }
142
143  if (TREE_CODE (t) != DEBUG_BEGIN_STMT)
144    TREE_SIDE_EFFECTS (i->container) = 1;
145
146  cur = i->ptr;
147
148  /* Link it into the list.  */
149  if (cur)
150    {
151      head->prev = cur->prev;
152      if (head->prev)
153	head->prev->next = head;
154      else
155	STATEMENT_LIST_HEAD (i->container) = head;
156      tail->next = cur;
157      cur->prev = tail;
158    }
159  else
160    {
161      head->prev = STATEMENT_LIST_TAIL (i->container);
162      if (head->prev)
163       head->prev->next = head;
164      else
165       STATEMENT_LIST_HEAD (i->container) = head;
166      STATEMENT_LIST_TAIL (i->container) = tail;
167    }
168
169  /* Update the iterator, if requested.  */
170  switch (mode)
171    {
172    case TSI_NEW_STMT:
173    case TSI_CONTINUE_LINKING:
174    case TSI_CHAIN_START:
175      i->ptr = head;
176      break;
177    case TSI_CHAIN_END:
178      i->ptr = tail;
179      break;
180    case TSI_SAME_STMT:
181      break;
182    }
183}
184
185/* Links a statement, or a chain of statements, after the current stmt.  */
186
187void
188tsi_link_after (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
189{
190  struct tree_statement_list_node *head, *tail, *cur;
191
192  /* Die on looping.  */
193  gcc_assert (t != i->container);
194
195  if (TREE_CODE (t) == STATEMENT_LIST)
196    {
197      head = STATEMENT_LIST_HEAD (t);
198      tail = STATEMENT_LIST_TAIL (t);
199      STATEMENT_LIST_HEAD (t) = NULL;
200      STATEMENT_LIST_TAIL (t) = NULL;
201
202      free_stmt_list (t);
203
204      /* Empty statement lists need no work.  */
205      if (!head || !tail)
206	{
207	  gcc_assert (head == tail);
208	  return;
209	}
210    }
211  else
212    {
213      head = ggc_alloc<tree_statement_list_node> ();
214      head->prev = NULL;
215      head->next = NULL;
216      head->stmt = t;
217      tail = head;
218    }
219
220  if (TREE_CODE (t) != DEBUG_BEGIN_STMT)
221    TREE_SIDE_EFFECTS (i->container) = 1;
222
223  cur = i->ptr;
224
225  /* Link it into the list.  */
226  if (cur)
227    {
228      tail->next = cur->next;
229      if (tail->next)
230	tail->next->prev = tail;
231      else
232	STATEMENT_LIST_TAIL (i->container) = tail;
233      head->prev = cur;
234      cur->next = head;
235    }
236  else
237    {
238      gcc_assert (!STATEMENT_LIST_TAIL (i->container));
239      STATEMENT_LIST_HEAD (i->container) = head;
240      STATEMENT_LIST_TAIL (i->container) = tail;
241    }
242
243  /* Update the iterator, if requested.  */
244  switch (mode)
245    {
246    case TSI_NEW_STMT:
247    case TSI_CHAIN_START:
248      i->ptr = head;
249      break;
250    case TSI_CONTINUE_LINKING:
251    case TSI_CHAIN_END:
252      i->ptr = tail;
253      break;
254    case TSI_SAME_STMT:
255      gcc_assert (cur);
256      break;
257    }
258}
259
260/* Remove a stmt from the tree list.  The iterator is updated to point to
261   the next stmt.  */
262
263void
264tsi_delink (tree_stmt_iterator *i)
265{
266  struct tree_statement_list_node *cur, *next, *prev;
267
268  cur = i->ptr;
269  next = cur->next;
270  prev = cur->prev;
271
272  if (prev)
273    prev->next = next;
274  else
275    STATEMENT_LIST_HEAD (i->container) = next;
276  if (next)
277    next->prev = prev;
278  else
279    STATEMENT_LIST_TAIL (i->container) = prev;
280
281  if (!next && !prev)
282    TREE_SIDE_EFFECTS (i->container) = 0;
283
284  i->ptr = next;
285}
286
287/* Return the first expression in a sequence of COMPOUND_EXPRs, or in
288   a STATEMENT_LIST, disregarding DEBUG_BEGIN_STMTs, recursing into a
289   STATEMENT_LIST if that's the first non-DEBUG_BEGIN_STMT.  */
290
291tree
292expr_first (tree expr)
293{
294  if (expr == NULL_TREE)
295    return expr;
296
297  if (TREE_CODE (expr) == STATEMENT_LIST)
298    {
299      struct tree_statement_list_node *n = STATEMENT_LIST_HEAD (expr);
300      if (!n)
301	return NULL_TREE;
302      while (TREE_CODE (n->stmt) == DEBUG_BEGIN_STMT)
303	{
304	  n = n->next;
305	  if (!n)
306	    return NULL_TREE;
307	}
308      /* If the first non-debug stmt is not a statement list, we
309	 already know it's what we're looking for.  */
310      if (TREE_CODE (n->stmt) != STATEMENT_LIST)
311	return n->stmt;
312
313      return expr_first (n->stmt);
314    }
315
316  while (TREE_CODE (expr) == COMPOUND_EXPR)
317    expr = TREE_OPERAND (expr, 0);
318
319  return expr;
320}
321
322/* Return the last expression in a sequence of COMPOUND_EXPRs, or in a
323   STATEMENT_LIST, disregarding DEBUG_BEGIN_STMTs, recursing into a
324   STATEMENT_LIST if that's the last non-DEBUG_BEGIN_STMT.  */
325
326tree
327expr_last (tree expr)
328{
329  if (expr == NULL_TREE)
330    return expr;
331
332  if (TREE_CODE (expr) == STATEMENT_LIST)
333    {
334      struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr);
335      if (!n)
336	return NULL_TREE;
337      while (TREE_CODE (n->stmt) == DEBUG_BEGIN_STMT)
338	{
339	  n = n->prev;
340	  if (!n)
341	    return NULL_TREE;
342	}
343      /* If the last non-debug stmt is not a statement list, we
344	 already know it's what we're looking for.  */
345      if (TREE_CODE (n->stmt) != STATEMENT_LIST)
346	return n->stmt;
347
348      return expr_last (n->stmt);
349    }
350
351  while (TREE_CODE (expr) == COMPOUND_EXPR)
352    expr = TREE_OPERAND (expr, 1);
353
354  return expr;
355}
356
357/* If EXPR is a STATEMENT_LIST containing just DEBUG_BEGIN_STMTs and
358   a single other stmt, return that other stmt (recursively).
359   If it is a STATEMENT_LIST containing no non-DEBUG_BEGIN_STMTs or
360   multiple, return NULL_TREE.
361   Otherwise return EXPR.  */
362
363tree
364expr_single (tree expr)
365{
366  if (expr == NULL_TREE)
367    return expr;
368
369  if (TREE_CODE (expr) == STATEMENT_LIST)
370    {
371      /* With -gstatement-frontiers we could have a STATEMENT_LIST with
372	 DEBUG_BEGIN_STMT(s) and only a single other stmt, which with
373	 -g wouldn't be present and we'd have that single other stmt
374	 directly instead.  */
375      struct tree_statement_list_node *n = STATEMENT_LIST_HEAD (expr);
376      if (!n)
377	return NULL_TREE;
378      while (TREE_CODE (n->stmt) == DEBUG_BEGIN_STMT)
379	{
380	  n = n->next;
381	  if (!n)
382	    return NULL_TREE;
383	}
384      expr = n->stmt;
385      do
386	{
387	  n = n->next;
388	  if (!n)
389	    return expr_single (expr);
390	}
391      while (TREE_CODE (n->stmt) == DEBUG_BEGIN_STMT);
392      return NULL_TREE;
393    }
394
395  return expr;
396}
397
398#include "gt-tree-iterator.h"
399