Branch data Line data Source code
1 : : /* Iterator routines for manipulating GENERIC and GIMPLE tree statements.
2 : : Copyright (C) 2003-2025 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
34 : 721651013 : alloc_stmt_list (void)
35 : : {
36 : 721651013 : tree list;
37 : 721651013 : if (!vec_safe_is_empty (stmt_list_cache))
38 : : {
39 : 425865791 : list = stmt_list_cache->pop ();
40 : 425865791 : memset (list, 0, sizeof (struct tree_base));
41 : 425865791 : TREE_SET_CODE (list, STATEMENT_LIST);
42 : : }
43 : : else
44 : : {
45 : 295785222 : list = make_node (STATEMENT_LIST);
46 : 295785222 : TREE_SIDE_EFFECTS (list) = 0;
47 : : }
48 : 721651013 : TREE_TYPE (list) = void_type_node;
49 : 721651013 : return list;
50 : : }
51 : :
52 : : void
53 : 426761734 : free_stmt_list (tree t)
54 : : {
55 : 426761734 : gcc_assert (!STATEMENT_LIST_HEAD (t));
56 : 426761734 : gcc_assert (!STATEMENT_LIST_TAIL (t));
57 : 426761734 : vec_safe_push (stmt_list_cache, t);
58 : 426761734 : }
59 : :
60 : : /* A subroutine of append_to_statement_list{,_force}. T is not NULL. */
61 : :
62 : : static void
63 : 1171967913 : append_to_statement_list_1 (tree t, tree *list_p)
64 : : {
65 : 1171967913 : tree list = *list_p;
66 : 1171967913 : tree_stmt_iterator i;
67 : :
68 : 1171967913 : if (!list)
69 : : {
70 : 11439260 : if (t && TREE_CODE (t) == STATEMENT_LIST)
71 : : {
72 : 2957425 : *list_p = t;
73 : 2957425 : return;
74 : : }
75 : 8481835 : *list_p = list = alloc_stmt_list ();
76 : : }
77 : 1160528653 : else if (TREE_CODE (list) != STATEMENT_LIST)
78 : : {
79 : 13515955 : tree first = list;
80 : 13515955 : *list_p = list = alloc_stmt_list ();
81 : 13515955 : i = tsi_last (list);
82 : 13515955 : tsi_link_after (&i, first, TSI_CONTINUE_LINKING);
83 : : }
84 : :
85 : 1169010488 : i = tsi_last (list);
86 : 1169010488 : 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
93 : 57496496 : append_to_statement_list (tree t, tree *list_p)
94 : : {
95 : 57496496 : if (t && (TREE_SIDE_EFFECTS (t) || TREE_CODE (t) == DEBUG_BEGIN_STMT))
96 : 54279143 : append_to_statement_list_1 (t, list_p);
97 : 57496496 : }
98 : :
99 : : /* Similar, but the statement is always added, regardless of side effects. */
100 : :
101 : : void
102 : 1117688770 : append_to_statement_list_force (tree t, tree *list_p)
103 : : {
104 : 1117688770 : if (t != NULL_TREE)
105 : 1117688770 : append_to_statement_list_1 (t, list_p);
106 : 1117688770 : }
107 : :
108 : : /* Links a statement, or a chain of statements, before the current stmt. */
109 : :
110 : : void
111 : 148226 : tsi_link_before (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
112 : : {
113 : 148226 : struct tree_statement_list_node *head, *tail, *cur;
114 : :
115 : : /* Die on looping. */
116 : 148226 : gcc_assert (t != i->container);
117 : :
118 : 148226 : if (TREE_CODE (t) == STATEMENT_LIST)
119 : : {
120 : 11148 : head = STATEMENT_LIST_HEAD (t);
121 : 11148 : tail = STATEMENT_LIST_TAIL (t);
122 : 11148 : STATEMENT_LIST_HEAD (t) = NULL;
123 : 11148 : STATEMENT_LIST_TAIL (t) = NULL;
124 : :
125 : 11148 : free_stmt_list (t);
126 : :
127 : : /* Empty statement lists need no work. */
128 : 11148 : if (!head || !tail)
129 : : {
130 : 15 : gcc_assert (head == tail);
131 : : return;
132 : : }
133 : : }
134 : : else
135 : : {
136 : 137078 : head = ggc_alloc<tree_statement_list_node> ();
137 : 137078 : head->prev = NULL;
138 : 137078 : head->next = NULL;
139 : 137078 : head->stmt = t;
140 : 137078 : tail = head;
141 : : }
142 : :
143 : 148211 : if (TREE_CODE (t) != DEBUG_BEGIN_STMT)
144 : 148211 : TREE_SIDE_EFFECTS (i->container) = 1;
145 : :
146 : 148211 : cur = i->ptr;
147 : :
148 : : /* Link it into the list. */
149 : 148211 : if (cur)
150 : : {
151 : 148211 : head->prev = cur->prev;
152 : 148211 : if (head->prev)
153 : 99 : head->prev->next = head;
154 : : else
155 : 148112 : STATEMENT_LIST_HEAD (i->container) = head;
156 : 148211 : tail->next = cur;
157 : 148211 : cur->prev = tail;
158 : : }
159 : : else
160 : : {
161 : 0 : head->prev = STATEMENT_LIST_TAIL (i->container);
162 : 0 : if (head->prev)
163 : 0 : head->prev->next = head;
164 : : else
165 : 0 : STATEMENT_LIST_HEAD (i->container) = head;
166 : 0 : STATEMENT_LIST_TAIL (i->container) = tail;
167 : : }
168 : :
169 : : /* Update the iterator, if requested. */
170 : 148211 : switch (mode)
171 : : {
172 : 23855 : case TSI_NEW_STMT:
173 : 23855 : case TSI_CONTINUE_LINKING:
174 : 23855 : case TSI_CHAIN_START:
175 : 23855 : i->ptr = head;
176 : 23855 : break;
177 : 0 : case TSI_CHAIN_END:
178 : 0 : i->ptr = tail;
179 : 0 : 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
188 : 1241247705 : tsi_link_after (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
189 : : {
190 : 1241247705 : struct tree_statement_list_node *head, *tail, *cur;
191 : :
192 : : /* Die on looping. */
193 : 1241247705 : gcc_assert (t != i->container);
194 : :
195 : 1241247705 : if (TREE_CODE (t) == STATEMENT_LIST)
196 : : {
197 : 44308359 : head = STATEMENT_LIST_HEAD (t);
198 : 44308359 : tail = STATEMENT_LIST_TAIL (t);
199 : 44308359 : STATEMENT_LIST_HEAD (t) = NULL;
200 : 44308359 : STATEMENT_LIST_TAIL (t) = NULL;
201 : :
202 : 44308359 : free_stmt_list (t);
203 : :
204 : : /* Empty statement lists need no work. */
205 : 44308359 : if (!head || !tail)
206 : : {
207 : 14409020 : gcc_assert (head == tail);
208 : : return;
209 : : }
210 : : }
211 : : else
212 : : {
213 : 1196939346 : head = ggc_alloc<tree_statement_list_node> ();
214 : 1196939346 : head->prev = NULL;
215 : 1196939346 : head->next = NULL;
216 : 1196939346 : head->stmt = t;
217 : 1196939346 : tail = head;
218 : : }
219 : :
220 : 1226838685 : if (TREE_CODE (t) != DEBUG_BEGIN_STMT)
221 : 923378940 : TREE_SIDE_EFFECTS (i->container) = 1;
222 : :
223 : 1226838685 : cur = i->ptr;
224 : :
225 : : /* Link it into the list. */
226 : 1226838685 : if (cur)
227 : : {
228 : 580173723 : tail->next = cur->next;
229 : 580173723 : if (tail->next)
230 : 28 : tail->next->prev = tail;
231 : : else
232 : 580173695 : STATEMENT_LIST_TAIL (i->container) = tail;
233 : 580173723 : head->prev = cur;
234 : 580173723 : cur->next = head;
235 : : }
236 : : else
237 : : {
238 : 646664962 : gcc_assert (!STATEMENT_LIST_TAIL (i->container));
239 : 646664962 : STATEMENT_LIST_HEAD (i->container) = head;
240 : 646664962 : STATEMENT_LIST_TAIL (i->container) = tail;
241 : : }
242 : :
243 : : /* Update the iterator, if requested. */
244 : 1226838685 : switch (mode)
245 : : {
246 : 0 : case TSI_NEW_STMT:
247 : 0 : case TSI_CHAIN_START:
248 : 0 : i->ptr = head;
249 : 0 : break;
250 : 1226838487 : case TSI_CONTINUE_LINKING:
251 : 1226838487 : case TSI_CHAIN_END:
252 : 1226838487 : i->ptr = tail;
253 : 1226838487 : break;
254 : 198 : case TSI_SAME_STMT:
255 : 198 : 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
264 : 420253451 : tsi_delink (tree_stmt_iterator *i)
265 : : {
266 : 420253451 : struct tree_statement_list_node *cur, *next, *prev;
267 : :
268 : 420253451 : cur = i->ptr;
269 : 420253451 : next = cur->next;
270 : 420253451 : prev = cur->prev;
271 : :
272 : 420253451 : if (prev)
273 : 77740 : prev->next = next;
274 : : else
275 : 420175711 : STATEMENT_LIST_HEAD (i->container) = next;
276 : 420253451 : if (next)
277 : 29372993 : next->prev = prev;
278 : : else
279 : 390880458 : STATEMENT_LIST_TAIL (i->container) = prev;
280 : :
281 : 420253451 : if (!next && !prev)
282 : 390870077 : TREE_SIDE_EFFECTS (i->container) = 0;
283 : :
284 : 420253451 : i->ptr = next;
285 : 420253451 : }
286 : :
287 : : /* Split a STATEMENT_LIST in I.contrainer into two, all statements
288 : : from the start until I.ptr inclusive will remain in the original
289 : : one, all statements after I.ptr are removed from that STATEMENT_LIST
290 : : and returned as a new STATEMENT_LIST. If I is the last statement,
291 : : an empty statement with LOC location is returned. */
292 : :
293 : : tree
294 : 9787 : tsi_split_stmt_list (location_t loc, tree_stmt_iterator i)
295 : : {
296 : 9787 : if (tsi_one_before_end_p (i))
297 : 57 : return build_empty_stmt (loc);
298 : 9730 : tsi_next (&i);
299 : 9730 : tree ret = NULL_TREE;
300 : 86249 : while (!tsi_end_p (i))
301 : : {
302 : 76519 : tree t = tsi_stmt (i);
303 : 76519 : tsi_delink (&i);
304 : 76519 : append_to_statement_list_force (t, &ret);
305 : : }
306 : 9730 : return ret;
307 : : }
308 : :
309 : : /* Return the first expression in a sequence of COMPOUND_EXPRs, or in
310 : : a STATEMENT_LIST, disregarding DEBUG_BEGIN_STMTs, recursing into a
311 : : STATEMENT_LIST if that's the first non-DEBUG_BEGIN_STMT. */
312 : :
313 : : tree
314 : 10728200 : expr_first (tree expr)
315 : : {
316 : 10729460 : if (expr == NULL_TREE)
317 : : return expr;
318 : :
319 : 10729432 : if (TREE_CODE (expr) == STATEMENT_LIST)
320 : : {
321 : 3584936 : struct tree_statement_list_node *n = STATEMENT_LIST_HEAD (expr);
322 : 3584936 : if (!n)
323 : : return NULL_TREE;
324 : 6831377 : while (TREE_CODE (n->stmt) == DEBUG_BEGIN_STMT)
325 : : {
326 : 3320789 : n = n->next;
327 : 3320789 : if (!n)
328 : : return NULL_TREE;
329 : : }
330 : : /* If the first non-debug stmt is not a statement list, we
331 : : already know it's what we're looking for. */
332 : 3510588 : if (TREE_CODE (n->stmt) != STATEMENT_LIST)
333 : : return n->stmt;
334 : :
335 : : return expr_first (n->stmt);
336 : : }
337 : :
338 : 7144497 : while (TREE_CODE (expr) == COMPOUND_EXPR)
339 : 1 : expr = TREE_OPERAND (expr, 0);
340 : :
341 : : return expr;
342 : : }
343 : :
344 : : /* Return the last expression in a sequence of COMPOUND_EXPRs, or in a
345 : : STATEMENT_LIST, disregarding DEBUG_BEGIN_STMTs, recursing into a
346 : : STATEMENT_LIST if that's the last non-DEBUG_BEGIN_STMT. */
347 : :
348 : : tree
349 : 7601665 : expr_last (tree expr)
350 : : {
351 : 7603091 : if (expr == NULL_TREE)
352 : : return expr;
353 : :
354 : 7599210 : if (TREE_CODE (expr) == STATEMENT_LIST)
355 : : {
356 : 4266484 : struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr);
357 : 4266484 : if (!n)
358 : : return NULL_TREE;
359 : 4859165 : while (TREE_CODE (n->stmt) == DEBUG_BEGIN_STMT)
360 : : {
361 : 2267140 : n = n->prev;
362 : 2267140 : if (!n)
363 : : return NULL_TREE;
364 : : }
365 : : /* If the last non-debug stmt is not a statement list, we
366 : : already know it's what we're looking for. */
367 : 2592025 : if (TREE_CODE (n->stmt) != STATEMENT_LIST)
368 : : return n->stmt;
369 : :
370 : : return expr_last (n->stmt);
371 : : }
372 : :
373 : 3336388 : while (TREE_CODE (expr) == COMPOUND_EXPR)
374 : 3662 : expr = TREE_OPERAND (expr, 1);
375 : :
376 : : return expr;
377 : : }
378 : :
379 : : /* If EXPR is a STATEMENT_LIST containing just DEBUG_BEGIN_STMTs and
380 : : a single other stmt, return that other stmt (recursively).
381 : : If it is a STATEMENT_LIST containing no non-DEBUG_BEGIN_STMTs or
382 : : multiple, return NULL_TREE.
383 : : Otherwise return EXPR. */
384 : :
385 : : tree
386 : 20351774 : expr_single (tree expr)
387 : : {
388 : 20377736 : if (expr == NULL_TREE)
389 : : return expr;
390 : :
391 : 18488334 : if (TREE_CODE (expr) == STATEMENT_LIST)
392 : : {
393 : : /* With -gstatement-frontiers we could have a STATEMENT_LIST with
394 : : DEBUG_BEGIN_STMT(s) and only a single other stmt, which with
395 : : -g wouldn't be present and we'd have that single other stmt
396 : : directly instead. */
397 : 91054 : struct tree_statement_list_node *n = STATEMENT_LIST_HEAD (expr);
398 : 91054 : if (!n)
399 : : return NULL_TREE;
400 : 122148 : while (TREE_CODE (n->stmt) == DEBUG_BEGIN_STMT)
401 : : {
402 : 33313 : n = n->next;
403 : 33313 : if (!n)
404 : : return NULL_TREE;
405 : : }
406 : 96347 : expr = n->stmt;
407 : 96347 : do
408 : : {
409 : 96347 : n = n->next;
410 : 96347 : if (!n)
411 : : return expr_single (expr);
412 : : }
413 : 70385 : while (TREE_CODE (n->stmt) == DEBUG_BEGIN_STMT);
414 : : return NULL_TREE;
415 : : }
416 : :
417 : : return expr;
418 : : }
419 : :
420 : : #include "gt-tree-iterator.h"
|
