1 /* Iterator routines for manipulating GENERIC and GIMPLE tree statements.
2 Copyright (C) 2003-2021 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along 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
31 static GTY ((deletable (""))) vec<tree, va_gc> *stmt_list_cache;
32
33 tree
alloc_stmt_list(void)34 alloc_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
52 void
free_stmt_list(tree t)53 free_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
62 static void
append_to_statement_list_1(tree t,tree * list_p)63 append_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
92 void
append_to_statement_list(tree t,tree * list_p)93 append_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
101 void
append_to_statement_list_force(tree t,tree * list_p)102 append_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
110 void
tsi_link_before(tree_stmt_iterator * i,tree t,enum tsi_iterator_update mode)111 tsi_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
187 void
tsi_link_after(tree_stmt_iterator * i,tree t,enum tsi_iterator_update mode)188 tsi_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
263 void
tsi_delink(tree_stmt_iterator * i)264 tsi_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
291 tree
expr_first(tree expr)292 expr_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
326 tree
expr_last(tree expr)327 expr_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
363 tree
expr_single(tree expr)364 expr_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