Line data Source code
1 : /* Iterator routines for manipulating GENERIC and GIMPLE tree statements.
2 : Copyright (C) 2003-2026 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 873661589 : alloc_stmt_list (void)
35 : {
36 873661589 : tree list;
37 873661589 : if (!vec_safe_is_empty (stmt_list_cache))
38 : {
39 516021061 : list = stmt_list_cache->pop ();
40 516021061 : memset (list, 0, sizeof (struct tree_base));
41 516021061 : TREE_SET_CODE (list, STATEMENT_LIST);
42 : }
43 : else
44 : {
45 357640528 : list = make_node (STATEMENT_LIST);
46 357640528 : TREE_SIDE_EFFECTS (list) = 0;
47 : }
48 873661589 : TREE_TYPE (list) = void_type_node;
49 873661589 : return list;
50 : }
51 :
52 : void
53 516932509 : free_stmt_list (tree t)
54 : {
55 516932509 : gcc_assert (!STATEMENT_LIST_HEAD (t));
56 516932509 : gcc_assert (!STATEMENT_LIST_TAIL (t));
57 516932509 : vec_safe_push (stmt_list_cache, t);
58 516932509 : }
59 :
60 : /* A subroutine of append_to_statement_list{,_force}. T is not NULL. */
61 :
62 : static void
63 1410909346 : append_to_statement_list_1 (tree t, tree *list_p)
64 : {
65 1410909346 : tree list = *list_p;
66 1410909346 : tree_stmt_iterator i;
67 :
68 1410909346 : if (!list)
69 : {
70 12310318 : if (t && TREE_CODE (t) == STATEMENT_LIST)
71 : {
72 3173519 : *list_p = t;
73 3173519 : return;
74 : }
75 9136799 : *list_p = list = alloc_stmt_list ();
76 : }
77 1398599028 : else if (TREE_CODE (list) != STATEMENT_LIST)
78 : {
79 18698013 : tree first = list;
80 18698013 : *list_p = list = alloc_stmt_list ();
81 18698013 : i = tsi_last (list);
82 18698013 : tsi_link_after (&i, first, TSI_CONTINUE_LINKING);
83 : }
84 :
85 1407735827 : i = tsi_last (list);
86 1407735827 : 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 66500724 : append_to_statement_list (tree t, tree *list_p)
94 : {
95 66500724 : if (t && (TREE_SIDE_EFFECTS (t) || TREE_CODE (t) == DEBUG_BEGIN_STMT))
96 62790681 : append_to_statement_list_1 (t, list_p);
97 66500724 : }
98 :
99 : /* Similar, but the statement is always added, regardless of side effects. */
100 :
101 : void
102 1348118665 : append_to_statement_list_force (tree t, tree *list_p)
103 : {
104 1348118665 : if (t != NULL_TREE)
105 1348118665 : append_to_statement_list_1 (t, list_p);
106 1348118665 : }
107 :
108 : /* Links a statement, or a chain of statements, before the current stmt. */
109 :
110 : void
111 147519 : tsi_link_before (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
112 : {
113 147519 : struct tree_statement_list_node *head, *tail, *cur;
114 :
115 : /* Die on looping. */
116 147519 : gcc_assert (t != i->container);
117 :
118 147519 : if (TREE_CODE (t) == STATEMENT_LIST)
119 : {
120 12038 : head = STATEMENT_LIST_HEAD (t);
121 12038 : tail = STATEMENT_LIST_TAIL (t);
122 12038 : STATEMENT_LIST_HEAD (t) = NULL;
123 12038 : STATEMENT_LIST_TAIL (t) = NULL;
124 :
125 12038 : free_stmt_list (t);
126 :
127 : /* Empty statement lists need no work. */
128 12038 : if (!head || !tail)
129 : {
130 15 : gcc_assert (head == tail);
131 : return;
132 : }
133 : }
134 : else
135 : {
136 135481 : head = ggc_alloc<tree_statement_list_node> ();
137 135481 : head->prev = NULL;
138 135481 : head->next = NULL;
139 135481 : head->stmt = t;
140 135481 : tail = head;
141 : }
142 :
143 147504 : if (TREE_CODE (t) != DEBUG_BEGIN_STMT)
144 147504 : TREE_SIDE_EFFECTS (i->container) = 1;
145 :
146 147504 : cur = i->ptr;
147 :
148 : /* Link it into the list. */
149 147504 : if (cur)
150 : {
151 147501 : head->prev = cur->prev;
152 147501 : if (head->prev)
153 129 : head->prev->next = head;
154 : else
155 147372 : STATEMENT_LIST_HEAD (i->container) = head;
156 147501 : tail->next = cur;
157 147501 : cur->prev = tail;
158 : }
159 : else
160 : {
161 3 : head->prev = STATEMENT_LIST_TAIL (i->container);
162 3 : if (head->prev)
163 0 : head->prev->next = head;
164 : else
165 3 : STATEMENT_LIST_HEAD (i->container) = head;
166 3 : STATEMENT_LIST_TAIL (i->container) = tail;
167 : }
168 :
169 : /* Update the iterator, if requested. */
170 147504 : switch (mode)
171 : {
172 28390 : case TSI_NEW_STMT:
173 28390 : case TSI_CONTINUE_LINKING:
174 28390 : case TSI_CHAIN_START:
175 28390 : i->ptr = head;
176 28390 : 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 1506001650 : tsi_link_after (tree_stmt_iterator *i, tree t, enum tsi_iterator_update mode)
189 : {
190 1506001650 : struct tree_statement_list_node *head, *tail, *cur;
191 :
192 : /* Die on looping. */
193 1506001650 : gcc_assert (t != i->container);
194 :
195 1506001650 : if (TREE_CODE (t) == STATEMENT_LIST)
196 : {
197 48515577 : head = STATEMENT_LIST_HEAD (t);
198 48515577 : tail = STATEMENT_LIST_TAIL (t);
199 48515577 : STATEMENT_LIST_HEAD (t) = NULL;
200 48515577 : STATEMENT_LIST_TAIL (t) = NULL;
201 :
202 48515577 : free_stmt_list (t);
203 :
204 : /* Empty statement lists need no work. */
205 48515577 : if (!head || !tail)
206 : {
207 15857397 : gcc_assert (head == tail);
208 : return;
209 : }
210 : }
211 : else
212 : {
213 1457486073 : head = ggc_alloc<tree_statement_list_node> ();
214 1457486073 : head->prev = NULL;
215 1457486073 : head->next = NULL;
216 1457486073 : head->stmt = t;
217 1457486073 : tail = head;
218 : }
219 :
220 1490144253 : if (TREE_CODE (t) != DEBUG_BEGIN_STMT)
221 1115840817 : TREE_SIDE_EFFECTS (i->container) = 1;
222 :
223 1490144253 : cur = i->ptr;
224 :
225 : /* Link it into the list. */
226 1490144253 : if (cur)
227 : {
228 711523434 : tail->next = cur->next;
229 711523434 : if (tail->next)
230 35 : tail->next->prev = tail;
231 : else
232 711523399 : STATEMENT_LIST_TAIL (i->container) = tail;
233 711523434 : head->prev = cur;
234 711523434 : cur->next = head;
235 : }
236 : else
237 : {
238 778620819 : gcc_assert (!STATEMENT_LIST_TAIL (i->container));
239 778620819 : STATEMENT_LIST_HEAD (i->container) = head;
240 778620819 : STATEMENT_LIST_TAIL (i->container) = tail;
241 : }
242 :
243 : /* Update the iterator, if requested. */
244 1490144253 : switch (mode)
245 : {
246 0 : case TSI_NEW_STMT:
247 0 : case TSI_CHAIN_START:
248 0 : i->ptr = head;
249 0 : break;
250 1490144049 : case TSI_CONTINUE_LINKING:
251 1490144049 : case TSI_CHAIN_END:
252 1490144049 : i->ptr = tail;
253 1490144049 : break;
254 204 : case TSI_SAME_STMT:
255 204 : 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 506057779 : tsi_delink (tree_stmt_iterator *i)
265 : {
266 506057779 : struct tree_statement_list_node *cur, *next, *prev;
267 :
268 506057779 : cur = i->ptr;
269 506057779 : next = cur->next;
270 506057779 : prev = cur->prev;
271 :
272 506057779 : if (prev)
273 73916 : prev->next = next;
274 : else
275 505983863 : STATEMENT_LIST_HEAD (i->container) = next;
276 506057779 : if (next)
277 29471172 : next->prev = prev;
278 : else
279 476586607 : STATEMENT_LIST_TAIL (i->container) = prev;
280 :
281 506057779 : if (!next && !prev)
282 476576627 : TREE_SIDE_EFFECTS (i->container) = 0;
283 :
284 506057779 : i->ptr = next;
285 506057779 : }
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 9296 : tsi_split_stmt_list (location_t loc, tree_stmt_iterator i)
295 : {
296 9296 : if (tsi_one_before_end_p (i))
297 57 : return build_empty_stmt (loc);
298 9239 : tsi_next (&i);
299 9239 : tree ret = NULL_TREE;
300 81816 : while (!tsi_end_p (i))
301 : {
302 72577 : tree t = tsi_stmt (i);
303 72577 : tsi_delink (&i);
304 72577 : append_to_statement_list_force (t, &ret);
305 : }
306 9239 : 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 12358705 : expr_first (tree expr)
315 : {
316 12359991 : if (expr == NULL_TREE)
317 : return expr;
318 :
319 12359961 : if (TREE_CODE (expr) == STATEMENT_LIST)
320 : {
321 4368164 : struct tree_statement_list_node *n = STATEMENT_LIST_HEAD (expr);
322 4368164 : if (!n)
323 : return NULL_TREE;
324 8307727 : while (TREE_CODE (n->stmt) == DEBUG_BEGIN_STMT)
325 : {
326 4035793 : n = n->next;
327 4035793 : 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 4271934 : if (TREE_CODE (n->stmt) != STATEMENT_LIST)
333 : return n->stmt;
334 :
335 : return expr_first (n->stmt);
336 : }
337 :
338 7991798 : 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 10568509 : expr_last (tree expr)
350 : {
351 10569968 : if (expr == NULL_TREE)
352 : return expr;
353 :
354 10392691 : if (TREE_CODE (expr) == STATEMENT_LIST)
355 : {
356 5907552 : struct tree_statement_list_node *n = STATEMENT_LIST_TAIL (expr);
357 5907552 : if (!n)
358 : return NULL_TREE;
359 7778191 : while (TREE_CODE (n->stmt) == DEBUG_BEGIN_STMT)
360 : {
361 3617509 : n = n->prev;
362 3617509 : 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 4160682 : if (TREE_CODE (n->stmt) != STATEMENT_LIST)
368 : return n->stmt;
369 :
370 : return expr_last (n->stmt);
371 : }
372 :
373 4496380 : while (TREE_CODE (expr) == COMPOUND_EXPR)
374 11241 : 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 24284964 : expr_single (tree expr)
387 : {
388 24331485 : if (expr == NULL_TREE)
389 : return expr;
390 :
391 22142289 : 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 112145 : struct tree_statement_list_node *n = STATEMENT_LIST_HEAD (expr);
398 112145 : if (!n)
399 : return NULL_TREE;
400 158421 : while (TREE_CODE (n->stmt) == DEBUG_BEGIN_STMT)
401 : {
402 52621 : n = n->next;
403 52621 : if (!n)
404 : return NULL_TREE;
405 : }
406 112562 : expr = n->stmt;
407 112562 : do
408 : {
409 112562 : n = n->next;
410 112562 : if (!n)
411 : return expr_single (expr);
412 : }
413 66041 : 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"
|
