Line data Source code
1 : /* Iterator routines for GIMPLE statements.
2 : Copyright (C) 2007-2026 Free Software Foundation, Inc.
3 : Contributed by Aldy Hernandez <aldy@quesejoda.com>
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it under
8 : the terms of the GNU General Public License as published by the Free
9 : Software Foundation; either version 3, or (at your option) any later
10 : version.
11 :
12 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : 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 "backend.h"
25 : #include "tree.h"
26 : #include "gimple.h"
27 : #include "cfghooks.h"
28 : #include "ssa.h"
29 : #include "cgraph.h"
30 : #include "tree-eh.h"
31 : #include "gimple-iterator.h"
32 : #include "tree-cfg.h"
33 : #include "tree-ssa.h"
34 : #include "value-prof.h"
35 : #include "gimplify.h"
36 :
37 : /* Return true if VAR has no uses at all, including no debug uses. */
38 :
39 : static inline bool
40 256 : completely_unused (const_tree var)
41 : {
42 256 : auto *head = &SSA_NAME_IMM_USE_NODE (var);
43 256 : return head->next == head;
44 : }
45 :
46 : /* Mark the statement STMT as modified, and update it. */
47 :
48 : static inline void
49 212816814 : update_modified_stmt (gimple *stmt)
50 : {
51 212816814 : if (!ssa_operands_active (cfun))
52 : return;
53 189799904 : update_stmt_if_modified (stmt);
54 : }
55 :
56 :
57 : /* Mark the statements in SEQ as modified, and update them. */
58 :
59 : void
60 48820925 : update_modified_stmts (gimple_seq seq)
61 : {
62 48820925 : gimple_stmt_iterator gsi;
63 :
64 48820925 : if (!ssa_operands_active (cfun))
65 48820925 : return;
66 124461395 : for (gsi = gsi_start (seq); !gsi_end_p (gsi); gsi_next (&gsi))
67 99451088 : update_stmt_if_modified (gsi_stmt (gsi));
68 : }
69 :
70 :
71 : /* Set BB to be the basic block for all the statements in the list
72 : starting at FIRST and LAST. */
73 :
74 : static void
75 188819864 : update_bb_for_stmts (gimple_seq_node first, gimple_seq_node last,
76 : basic_block bb)
77 : {
78 188819864 : gimple_seq_node n;
79 :
80 274280695 : for (n = first; n; n = n->next)
81 : {
82 274280695 : gimple_set_bb (n, bb);
83 274280695 : if (n == last)
84 : break;
85 : }
86 188819864 : }
87 :
88 : /* Set the frequencies for the cgraph_edges for each of the calls
89 : starting at FIRST for their new position within BB. */
90 :
91 : static void
92 1542866 : update_call_edge_frequencies (gimple_seq_node first, basic_block bb)
93 : {
94 1542866 : struct cgraph_node *cfun_node = NULL;
95 1542866 : gimple_seq_node n;
96 :
97 4748627 : for (n = first; n ; n = n->next)
98 3205761 : if (is_gimple_call (n))
99 : {
100 8148 : struct cgraph_edge *e;
101 :
102 : /* These function calls are expensive enough that we want
103 : to avoid calling them if we never see any calls. */
104 8148 : if (cfun_node == NULL)
105 6675 : cfun_node = cgraph_node::get (current_function_decl);
106 :
107 8148 : e = cfun_node->get_edge (n);
108 8148 : if (e != NULL)
109 970 : e->count = bb->count;
110 : }
111 1542866 : }
112 :
113 : /* Insert the sequence delimited by nodes FIRST and LAST before
114 : iterator I. M specifies how to update iterator I after insertion
115 : (see enum gsi_iterator_update).
116 :
117 : This routine assumes that there is a forward and backward path
118 : between FIRST and LAST (i.e., they are linked in a doubly-linked
119 : list). Additionally, if FIRST == LAST, this routine will properly
120 : insert a single node. */
121 :
122 : static void
123 49133985 : gsi_insert_seq_nodes_before (gimple_stmt_iterator *i,
124 : gimple_seq_node first,
125 : gimple_seq_node last,
126 : enum gsi_iterator_update mode)
127 : {
128 49133985 : basic_block bb;
129 49133985 : gimple_seq_node cur = i->ptr;
130 :
131 49133985 : gcc_assert (!cur || cur->prev);
132 :
133 49133985 : if ((bb = gsi_bb (*i)) != NULL)
134 36591530 : update_bb_for_stmts (first, last, bb);
135 :
136 : /* Link SEQ before CUR in the sequence. */
137 49133985 : if (cur)
138 : {
139 45048346 : first->prev = cur->prev;
140 45048346 : if (first->prev->next)
141 28792030 : first->prev->next = first;
142 : else
143 16256316 : gimple_seq_set_first (i->seq, first);
144 45048346 : last->next = cur;
145 45048346 : cur->prev = last;
146 : }
147 : else
148 : {
149 4085639 : gimple_seq_node itlast = gimple_seq_last (*i->seq);
150 :
151 : /* If CUR is NULL, we link at the end of the sequence (this case happens
152 : when gsi_after_labels is called for a basic block that contains only
153 : labels, so it returns an iterator after the end of the block, and
154 : we need to insert before it; it might be cleaner to add a flag to the
155 : iterator saying whether we are at the start or end of the list). */
156 4085639 : last->next = NULL;
157 4085639 : if (itlast)
158 : {
159 1552716 : first->prev = itlast;
160 1552716 : itlast->next = first;
161 : }
162 : else
163 2532923 : gimple_seq_set_first (i->seq, first);
164 4085639 : gimple_seq_set_last (i->seq, last);
165 : }
166 :
167 : /* Update the iterator, if requested. */
168 49133985 : switch (mode)
169 : {
170 5065186 : case GSI_NEW_STMT:
171 5065186 : case GSI_CONTINUE_LINKING:
172 5065186 : i->ptr = first;
173 5065186 : break;
174 0 : case GSI_LAST_NEW_STMT:
175 0 : i->ptr = last;
176 0 : break;
177 : case GSI_SAME_STMT:
178 : break;
179 0 : default:
180 0 : gcc_unreachable ();
181 : }
182 49133985 : }
183 :
184 :
185 : /* Inserts the sequence of statements SEQ before the statement pointed
186 : by iterator I. MODE indicates what to do with the iterator after
187 : insertion (see enum gsi_iterator_update).
188 :
189 : This function does not scan for new operands. It is provided for
190 : the use of the gimplifier, which manipulates statements for which
191 : def/use information has not yet been constructed. Most callers
192 : should use gsi_insert_seq_before. */
193 :
194 : void
195 22628728 : gsi_insert_seq_before_without_update (gimple_stmt_iterator *i, gimple_seq seq,
196 : enum gsi_iterator_update mode)
197 : {
198 22628728 : gimple_seq_node first, last;
199 :
200 22628728 : if (seq == NULL)
201 : return;
202 :
203 : /* Don't allow inserting a sequence into itself. */
204 17426101 : gcc_assert (seq != *i->seq);
205 :
206 17426101 : first = gimple_seq_first (seq);
207 17426101 : last = gimple_seq_last (seq);
208 :
209 : /* Empty sequences need no work. */
210 17426101 : if (!first || !last)
211 : {
212 0 : gcc_assert (first == last);
213 : return;
214 : }
215 :
216 17426101 : gsi_insert_seq_nodes_before (i, first, last, mode);
217 : }
218 :
219 :
220 : /* Inserts the sequence of statements SEQ before the statement pointed
221 : by iterator I. MODE indicates what to do with the iterator after
222 : insertion (see enum gsi_iterator_update). Scan the statements in SEQ
223 : for new operands. */
224 :
225 : void
226 18865285 : gsi_insert_seq_before (gimple_stmt_iterator *i, gimple_seq seq,
227 : enum gsi_iterator_update mode)
228 : {
229 18865285 : update_modified_stmts (seq);
230 18865285 : gsi_insert_seq_before_without_update (i, seq, mode);
231 18865285 : }
232 :
233 :
234 : /* Insert the sequence delimited by nodes FIRST and LAST after
235 : iterator I. M specifies how to update iterator I after insertion
236 : (see enum gsi_iterator_update).
237 :
238 : This routine assumes that there is a forward and backward path
239 : between FIRST and LAST (i.e., they are linked in a doubly-linked
240 : list). Additionally, if FIRST == LAST, this routine will properly
241 : insert a single node. */
242 :
243 : static void
244 394714123 : gsi_insert_seq_nodes_after (gimple_stmt_iterator *i,
245 : gimple_seq_node first,
246 : gimple_seq_node last,
247 : enum gsi_iterator_update m)
248 : {
249 394714123 : basic_block bb;
250 394714123 : gimple_seq_node cur = i->ptr;
251 :
252 394714123 : gcc_assert (!cur || cur->prev);
253 :
254 : /* If the iterator is inside a basic block, we need to update the
255 : basic block information for all the nodes between FIRST and LAST. */
256 394714123 : if ((bb = gsi_bb (*i)) != NULL)
257 152228334 : update_bb_for_stmts (first, last, bb);
258 :
259 : /* Link SEQ after CUR. */
260 394714123 : if (cur)
261 : {
262 231284264 : last->next = cur->next;
263 231284264 : if (last->next)
264 : {
265 9209226 : last->next->prev = last;
266 : }
267 : else
268 222075038 : gimple_seq_set_last (i->seq, last);
269 231284264 : first->prev = cur;
270 231284264 : cur->next = first;
271 : }
272 : else
273 : {
274 163429859 : gcc_assert (!gimple_seq_last (*i->seq));
275 163429859 : last->next = NULL;
276 163429859 : gimple_seq_set_first (i->seq, first);
277 163429859 : gimple_seq_set_last (i->seq, last);
278 : }
279 :
280 : /* Update the iterator, if requested. */
281 394714123 : switch (m)
282 : {
283 376586727 : case GSI_NEW_STMT:
284 376586727 : i->ptr = first;
285 376586727 : break;
286 6217170 : case GSI_LAST_NEW_STMT:
287 6217170 : case GSI_CONTINUE_LINKING:
288 6217170 : i->ptr = last;
289 6217170 : break;
290 11910226 : case GSI_SAME_STMT:
291 11910226 : gcc_assert (cur);
292 : break;
293 0 : default:
294 0 : gcc_unreachable ();
295 : }
296 394714123 : }
297 :
298 :
299 : /* Links sequence SEQ after the statement pointed-to by iterator I.
300 : MODE is as in gsi_insert_after.
301 :
302 : This function does not scan for new operands. It is provided for
303 : the use of the gimplifier, which manipulates statements for which
304 : def/use information has not yet been constructed. Most callers
305 : should use gsi_insert_seq_after. */
306 :
307 : void
308 36495831 : gsi_insert_seq_after_without_update (gimple_stmt_iterator *i, gimple_seq seq,
309 : enum gsi_iterator_update mode)
310 : {
311 36495831 : gimple_seq_node first, last;
312 :
313 36495831 : if (seq == NULL)
314 : return;
315 :
316 : /* Don't allow inserting a sequence into itself. */
317 34415219 : gcc_assert (seq != *i->seq);
318 :
319 34415219 : first = gimple_seq_first (seq);
320 34415219 : last = gimple_seq_last (seq);
321 :
322 : /* Empty sequences need no work. */
323 34415219 : if (!first || !last)
324 : {
325 0 : gcc_assert (first == last);
326 : return;
327 : }
328 :
329 34415219 : gsi_insert_seq_nodes_after (i, first, last, mode);
330 : }
331 :
332 :
333 : /* Links sequence SEQ after the statement pointed-to by iterator I.
334 : MODE is as in gsi_insert_after. Scan the statements in SEQ
335 : for new operands. */
336 :
337 : void
338 29902441 : gsi_insert_seq_after (gimple_stmt_iterator *i, gimple_seq seq,
339 : enum gsi_iterator_update mode)
340 : {
341 29902441 : update_modified_stmts (seq);
342 29902441 : gsi_insert_seq_after_without_update (i, seq, mode);
343 29902441 : }
344 :
345 :
346 : /* Move all statements in the sequence after I to a new sequence.
347 : Return this new sequence. */
348 :
349 : gimple_seq
350 581820 : gsi_split_seq_after (gimple_stmt_iterator i)
351 : {
352 581820 : gimple_seq_node cur, next;
353 581820 : gimple_seq *pold_seq, new_seq;
354 :
355 581820 : cur = i.ptr;
356 :
357 : /* How can we possibly split after the end, or before the beginning? */
358 581820 : gcc_assert (cur && cur->next);
359 581820 : next = cur->next;
360 :
361 581820 : pold_seq = i.seq;
362 :
363 581820 : gimple_seq_set_first (&new_seq, next);
364 581820 : gimple_seq_set_last (&new_seq, gimple_seq_last (*pold_seq));
365 581820 : gimple_seq_set_last (pold_seq, cur);
366 581820 : cur->next = NULL;
367 :
368 581820 : return new_seq;
369 : }
370 :
371 :
372 : /* Set the statement to which GSI points to STMT. This only updates
373 : the iterator and the gimple sequence, it doesn't do the bookkeeping
374 : of gsi_replace. */
375 :
376 : void
377 4975981 : gsi_set_stmt (gimple_stmt_iterator *gsi, gimple *stmt)
378 : {
379 4975981 : gimple *orig_stmt = gsi_stmt (*gsi);
380 4975981 : gimple *prev, *next;
381 :
382 4975981 : stmt->next = next = orig_stmt->next;
383 4975981 : stmt->prev = prev = orig_stmt->prev;
384 : /* Note how we don't clear next/prev of orig_stmt. This is so that
385 : copies of *GSI our callers might still hold (to orig_stmt)
386 : can be advanced as if they too were replaced. */
387 4975981 : if (prev->next)
388 3523118 : prev->next = stmt;
389 : else
390 1452863 : gimple_seq_set_first (gsi->seq, stmt);
391 4975981 : if (next)
392 3187012 : next->prev = stmt;
393 : else
394 1788969 : gimple_seq_set_last (gsi->seq, stmt);
395 :
396 4975981 : gsi->ptr = stmt;
397 4975981 : }
398 :
399 :
400 : /* Move all statements in the sequence starting at I to a new sequence.
401 : Set *PNEW_SEQ to this sequence. I is set to the head of the new list. */
402 :
403 : void
404 24034889 : gsi_split_seq_before (gimple_stmt_iterator *i, gimple_seq *pnew_seq)
405 : {
406 24034889 : gimple_seq_node cur, prev;
407 24034889 : gimple_seq old_seq;
408 :
409 24034889 : cur = i->ptr;
410 :
411 : /* How can we possibly split after the end? */
412 24034889 : gcc_assert (cur);
413 24034889 : prev = cur->prev;
414 :
415 24034889 : old_seq = *i->seq;
416 24034889 : if (!prev->next)
417 1358000 : *i->seq = NULL;
418 24034889 : i->seq = pnew_seq;
419 :
420 : /* Set the limits on NEW_SEQ. */
421 24034889 : gimple_seq_set_first (pnew_seq, cur);
422 48069778 : gimple_seq_set_last (pnew_seq, gimple_seq_last (old_seq));
423 :
424 : /* Cut OLD_SEQ before I. */
425 24034889 : gimple_seq_set_last (&old_seq, prev);
426 24034889 : if (prev->next)
427 22676889 : prev->next = NULL;
428 24034889 : }
429 :
430 :
431 : /* Replace the statement pointed-to by GSI to STMT. If UPDATE_EH_INFO
432 : is true, the exception handling information of the original
433 : statement is moved to the new statement. Returns whether EH edge
434 : cleanup is required.
435 :
436 : If the two statements assign to different SSA names, the caller must
437 : ensure that all uses of the old SSA name have been removed before
438 : calling this function. This includes removing all debug uses. */
439 :
440 : bool
441 3673303 : gsi_replace (gimple_stmt_iterator *gsi, gimple *stmt, bool update_eh_info)
442 : {
443 3673303 : gimple *orig_stmt = gsi_stmt (*gsi);
444 3673303 : bool require_eh_edge_purge = false;
445 :
446 3673303 : if (stmt == orig_stmt)
447 : return false;
448 :
449 7040511 : gcc_assert (!gimple_has_lhs (orig_stmt) || !gimple_has_lhs (stmt)
450 : || gimple_get_lhs (orig_stmt) == gimple_get_lhs (stmt)
451 : || completely_unused (gimple_get_lhs (orig_stmt)));
452 :
453 3673216 : gimple_set_location (stmt, gimple_location (orig_stmt));
454 3673216 : gimple_set_bb (stmt, gsi_bb (*gsi));
455 :
456 : /* Preserve EH region information from the original statement, if
457 : requested by the caller. */
458 3673216 : if (update_eh_info)
459 1147124 : require_eh_edge_purge = maybe_clean_or_replace_eh_stmt (orig_stmt, stmt);
460 :
461 3673216 : gimple_duplicate_stmt_histograms (cfun, stmt, cfun, orig_stmt);
462 :
463 : /* Free all the data flow information for ORIG_STMT. */
464 3673216 : gimple_set_bb (orig_stmt, NULL);
465 3673216 : gimple_remove_stmt_histograms (cfun, orig_stmt);
466 3673216 : delink_stmt_imm_use (orig_stmt);
467 :
468 3673216 : gsi_set_stmt (gsi, stmt);
469 3673216 : gimple_set_modified (stmt, true);
470 3673216 : update_modified_stmt (stmt);
471 3673216 : return require_eh_edge_purge;
472 : }
473 :
474 :
475 : /* Replace the statement pointed-to by GSI with the sequence SEQ.
476 : If UPDATE_EH_INFO is true, the exception handling information of
477 : the original statement is moved to the last statement of the new
478 : sequence. If the old statement is an assignment, then so must
479 : be the last statement of the new sequence, and they must have the
480 : same LHS. */
481 :
482 : void
483 202397 : gsi_replace_with_seq (gimple_stmt_iterator *gsi, gimple_seq seq,
484 : bool update_eh_info)
485 : {
486 202397 : if (gimple_seq_empty_p (seq))
487 : {
488 57 : gsi_remove (gsi, true);
489 57 : return;
490 : }
491 202340 : gimple_seq tail;
492 202340 : gimple_stmt_iterator lasti = gsi_last (seq);
493 202340 : gsi_split_seq_before (&lasti, &tail);
494 202340 : gsi_insert_seq_before (gsi, seq, GSI_SAME_STMT);
495 202340 : gsi_replace (gsi, gsi_stmt (lasti), update_eh_info);
496 : }
497 :
498 :
499 : /* Insert statement STMT before the statement pointed-to by iterator I.
500 : M specifies how to update iterator I after insertion (see enum
501 : gsi_iterator_update).
502 :
503 : This function does not scan for new operands. It is provided for
504 : the use of the gimplifier, which manipulates statements for which
505 : def/use information has not yet been constructed. Most callers
506 : should use gsi_insert_before. */
507 :
508 : void
509 31707884 : gsi_insert_before_without_update (gimple_stmt_iterator *i, gimple *stmt,
510 : enum gsi_iterator_update m)
511 : {
512 31707884 : gsi_insert_seq_nodes_before (i, stmt, stmt, m);
513 31707884 : }
514 :
515 : /* Insert statement STMT before the statement pointed-to by iterator I.
516 : Update STMT's basic block and scan it for new operands. M
517 : specifies how to update iterator I after insertion (see enum
518 : gsi_iterator_update). */
519 :
520 : void
521 31674779 : gsi_insert_before (gimple_stmt_iterator *i, gimple *stmt,
522 : enum gsi_iterator_update m)
523 : {
524 31674779 : update_modified_stmt (stmt);
525 31674779 : gsi_insert_before_without_update (i, stmt, m);
526 31674779 : }
527 :
528 :
529 : /* Insert statement STMT after the statement pointed-to by iterator I.
530 : M specifies how to update iterator I after insertion (see enum
531 : gsi_iterator_update).
532 :
533 : This function does not scan for new operands. It is provided for
534 : the use of the gimplifier, which manipulates statements for which
535 : def/use information has not yet been constructed. Most callers
536 : should use gsi_insert_after. */
537 :
538 : void
539 360298904 : gsi_insert_after_without_update (gimple_stmt_iterator *i, gimple *stmt,
540 : enum gsi_iterator_update m)
541 : {
542 360298904 : gsi_insert_seq_nodes_after (i, stmt, stmt, m);
543 360298904 : }
544 :
545 :
546 : /* Insert statement STMT after the statement pointed-to by iterator I.
547 : Update STMT's basic block and scan it for new operands. M
548 : specifies how to update iterator I after insertion (see enum
549 : gsi_iterator_update). */
550 :
551 : void
552 177468819 : gsi_insert_after (gimple_stmt_iterator *i, gimple *stmt,
553 : enum gsi_iterator_update m)
554 : {
555 177468819 : update_modified_stmt (stmt);
556 177468819 : gsi_insert_after_without_update (i, stmt, m);
557 177468819 : }
558 :
559 :
560 : /* Remove the current stmt from the sequence. The iterator is updated
561 : to point to the next statement.
562 :
563 : REMOVE_PERMANENTLY is true when the statement is going to be removed
564 : from the IL and not reinserted elsewhere. In that case we remove the
565 : statement pointed to by iterator I from the EH tables, and free its
566 : operand caches. Otherwise we do not modify this information. Returns
567 : true whether EH edge cleanup is required. */
568 :
569 : bool
570 160186215 : gsi_remove (gimple_stmt_iterator *i, bool remove_permanently)
571 : {
572 160186215 : gimple_seq_node cur, next, prev;
573 160186215 : gimple *stmt = gsi_stmt (*i);
574 160186215 : bool require_eh_edge_purge = false;
575 :
576 : /* ??? Do we want to do this for non-permanent operation? */
577 160186215 : if (gimple_code (stmt) != GIMPLE_PHI)
578 141878562 : insert_debug_temps_for_defs (i);
579 :
580 160186215 : gimple_set_bb (stmt, NULL);
581 :
582 160186215 : if (remove_permanently)
583 : {
584 : /* Free all the data flow information for STMT. */
585 115173473 : delink_stmt_imm_use (stmt);
586 115173473 : gimple_set_modified (stmt, true);
587 :
588 115173473 : if (gimple_debug_nonbind_marker_p (stmt))
589 : /* We don't need this to be exact, but try to keep it at least
590 : close. */
591 4623133 : cfun->debug_marker_count--;
592 115173473 : require_eh_edge_purge = remove_stmt_from_eh_lp (stmt);
593 115173473 : gimple_remove_stmt_histograms (cfun, stmt);
594 : }
595 :
596 : /* Update the iterator and re-wire the links in I->SEQ. */
597 160186215 : cur = i->ptr;
598 160186215 : next = cur->next;
599 160186215 : prev = cur->prev;
600 : /* See gsi_set_stmt for why we don't reset prev/next of STMT. */
601 :
602 160186215 : if (next)
603 : /* Cur is not last. */
604 100739671 : next->prev = prev;
605 59446544 : else if (prev->next)
606 : /* Cur is last but not first. */
607 35301947 : gimple_seq_set_last (i->seq, prev);
608 :
609 160186215 : if (prev->next)
610 : /* Cur is not first. */
611 97825244 : prev->next = next;
612 : else
613 : /* Cur is first. */
614 62360971 : *i->seq = next;
615 :
616 160186215 : i->ptr = next;
617 :
618 160186215 : return require_eh_edge_purge;
619 : }
620 :
621 :
622 : /* Finds iterator for STMT. */
623 :
624 : gimple_stmt_iterator
625 69766133 : gsi_for_stmt (gimple *stmt)
626 : {
627 69766133 : gimple_stmt_iterator i;
628 69766133 : basic_block bb = gimple_bb (stmt);
629 :
630 69766133 : if (gimple_code (stmt) == GIMPLE_PHI)
631 5909497 : i = gsi_start_phis (bb);
632 : else
633 127713272 : i = gsi_start_bb (bb);
634 :
635 69766133 : i.ptr = stmt;
636 69766133 : return i;
637 : }
638 :
639 : /* Get an iterator for STMT, which is known to belong to SEQ. This is
640 : equivalent to starting at the beginning of SEQ and searching forward
641 : until STMT is found. */
642 :
643 : gimple_stmt_iterator
644 11468 : gsi_for_stmt (gimple *stmt, gimple_seq *seq)
645 : {
646 11468 : gimple_stmt_iterator i = gsi_start (*seq);
647 11468 : i.ptr = stmt;
648 11468 : return i;
649 : }
650 :
651 : /* Finds iterator for PHI. */
652 :
653 : gphi_iterator
654 0 : gsi_for_phi (gphi *phi)
655 : {
656 0 : gphi_iterator i;
657 0 : basic_block bb = gimple_bb (phi);
658 :
659 0 : i = gsi_start_phis (bb);
660 0 : i.ptr = phi;
661 :
662 0 : return i;
663 : }
664 :
665 : /* Move the statement at FROM so it comes right after the statement at TO. */
666 :
667 : void
668 345156 : gsi_move_after (gimple_stmt_iterator *from, gimple_stmt_iterator *to)
669 : {
670 345156 : gimple *stmt = gsi_stmt (*from);
671 345156 : gsi_remove (from, false);
672 :
673 : /* We must have GSI_NEW_STMT here, as gsi_move_after is sometimes used to
674 : move statements to an empty block. */
675 345156 : gsi_insert_after (to, stmt, GSI_NEW_STMT);
676 345156 : }
677 :
678 :
679 : /* Move the statement at FROM so it comes right before the statement
680 : at TO using method M. M defaults to GSI_SAME_STMT. */
681 :
682 : void
683 14794553 : gsi_move_before (gimple_stmt_iterator *from, gimple_stmt_iterator *to,
684 : gsi_iterator_update m)
685 : {
686 14794553 : gimple *stmt = gsi_stmt (*from);
687 14794553 : gsi_remove (from, false);
688 :
689 : /* For consistency with gsi_move_after, it might be better to have
690 : GSI_NEW_STMT here; however, that breaks several places that expect
691 : that TO does not change. */
692 14794553 : gsi_insert_before (to, stmt, m);
693 14794553 : }
694 :
695 :
696 : /* Move the statement at FROM to the end of basic block BB. */
697 :
698 : void
699 145569 : gsi_move_to_bb_end (gimple_stmt_iterator *from, basic_block bb)
700 : {
701 145569 : gimple_stmt_iterator last = gsi_last_bb (bb);
702 145569 : gcc_checking_assert (gsi_bb (last) == bb);
703 :
704 : /* Have to check gsi_end_p because it could be an empty block. */
705 145569 : if (!gsi_end_p (last) && is_ctrl_stmt (gsi_stmt (last)))
706 11962 : gsi_move_before (from, &last);
707 : else
708 133607 : gsi_move_after (from, &last);
709 145569 : }
710 :
711 :
712 : /* Add STMT to the pending list of edge E. No actual insertion is
713 : made until a call to gsi_commit_edge_inserts () is made. */
714 :
715 : void
716 541681 : gsi_insert_on_edge (edge e, gimple *stmt)
717 : {
718 541681 : gimple_seq_add_stmt (&PENDING_STMT (e), stmt);
719 541681 : }
720 :
721 : /* Add the sequence of statements SEQ to the pending list of edge E.
722 : No actual insertion is made until a call to gsi_commit_edge_inserts
723 : is made. */
724 :
725 : void
726 24366 : gsi_insert_seq_on_edge (edge e, gimple_seq seq)
727 : {
728 24366 : gimple_seq_add_seq (&PENDING_STMT (e), seq);
729 24366 : }
730 :
731 : /* Return a new iterator pointing to the first statement in sequence of
732 : statements on edge E. Such statements need to be subsequently moved into a
733 : basic block by calling gsi_commit_edge_inserts. */
734 :
735 : gimple_stmt_iterator
736 134600 : gsi_start_edge (edge e)
737 : {
738 134600 : return gsi_start (PENDING_STMT (e));
739 : }
740 :
741 : /* Insert the statement pointed-to by GSI into edge E. Every attempt
742 : is made to place the statement in an existing basic block, but
743 : sometimes that isn't possible. When it isn't possible, the edge is
744 : split and the statement is added to the new block.
745 :
746 : In all cases, the returned *GSI points to the correct location. The
747 : return value is true if insertion should be done after the location,
748 : or false if it should be done before the location. If a new basic block
749 : has to be created, it is stored in *NEW_BB. */
750 :
751 : static bool
752 1542866 : gimple_find_edge_insert_loc (edge e, gimple_stmt_iterator *gsi,
753 : basic_block *new_bb)
754 : {
755 1542866 : basic_block dest, src;
756 1542866 : gimple *tmp;
757 :
758 1542866 : dest = e->dest;
759 :
760 : /* If the destination has one predecessor which has no PHI nodes,
761 : insert there. Except for the exit block.
762 :
763 : The requirement for no PHI nodes could be relaxed. Basically we
764 : would have to examine the PHIs to prove that none of them used
765 : the value set by the statement we want to insert on E. That
766 : hardly seems worth the effort. */
767 1588535 : restart:
768 1588535 : if (single_pred_p (dest)
769 248001 : && gimple_seq_empty_p (phi_nodes (dest))
770 1831793 : && dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
771 : {
772 242527 : *gsi = gsi_start_bb (dest);
773 242527 : if (gsi_end_p (*gsi))
774 : return true;
775 :
776 : /* Make sure we insert after any leading labels. */
777 201167 : tmp = gsi_stmt (*gsi);
778 201167 : while (gimple_code (tmp) == GIMPLE_LABEL)
779 : {
780 11022 : gsi_next (gsi);
781 11022 : if (gsi_end_p (*gsi))
782 : break;
783 201167 : tmp = gsi_stmt (*gsi);
784 : }
785 :
786 199266 : if (gsi_end_p (*gsi))
787 : {
788 9121 : *gsi = gsi_last_bb (dest);
789 9121 : return true;
790 : }
791 : else
792 : return false;
793 : }
794 :
795 : /* If the source has one successor, the edge is not abnormal and
796 : the last statement does not end a basic block, insert there.
797 : Except for the entry block. */
798 1346008 : src = e->src;
799 1346008 : if ((e->flags & EDGE_ABNORMAL) == 0
800 1346008 : && (single_succ_p (src)
801 : /* Do not count a fake edge as successor as added to infinite
802 : loops by connect_infinite_loops_to_exit. */
803 45414 : || (EDGE_COUNT (src->succs) == 2
804 45386 : && (EDGE_SUCC (src, 0)->flags & EDGE_FAKE
805 45386 : || EDGE_SUCC (src, 1)->flags & EDGE_FAKE)))
806 2646651 : && src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
807 : {
808 1300344 : *gsi = gsi_last_bb (src);
809 1300344 : if (gsi_end_p (*gsi))
810 : return true;
811 :
812 827913 : tmp = gsi_stmt (*gsi);
813 827913 : if (is_gimple_debug (tmp))
814 : {
815 64917 : gimple_stmt_iterator si = *gsi;
816 64917 : gsi_prev_nondebug (&si);
817 64917 : if (!gsi_end_p (si))
818 58327 : tmp = gsi_stmt (si);
819 : /* If we don't have a BB-ending nondebug stmt, we want to
820 : insert after the trailing debug stmts. Otherwise, we may
821 : insert before the BB-ending nondebug stmt, or split the
822 : edge. */
823 64917 : if (!stmt_ends_bb_p (tmp))
824 64917 : return true;
825 0 : *gsi = si;
826 : }
827 762996 : else if (!stmt_ends_bb_p (tmp))
828 : return true;
829 :
830 894 : switch (gimple_code (tmp))
831 : {
832 : case GIMPLE_RETURN:
833 : case GIMPLE_RESX:
834 : return false;
835 : default:
836 : break;
837 : }
838 : }
839 :
840 : /* Otherwise, create a new basic block, and split this edge. */
841 45669 : dest = split_edge (e);
842 45669 : if (new_bb)
843 388 : *new_bb = dest;
844 45669 : e = single_pred_edge (dest);
845 45669 : goto restart;
846 : }
847 :
848 :
849 : /* Similar to gsi_insert_on_edge+gsi_commit_edge_inserts. If a new
850 : block has to be created, it is returned. */
851 :
852 : basic_block
853 5529 : gsi_insert_on_edge_immediate (edge e, gimple *stmt)
854 : {
855 5529 : gimple_stmt_iterator gsi;
856 5529 : basic_block new_bb = NULL;
857 5529 : bool ins_after;
858 :
859 5529 : gcc_assert (!PENDING_STMT (e));
860 :
861 5529 : ins_after = gimple_find_edge_insert_loc (e, &gsi, &new_bb);
862 :
863 5529 : update_call_edge_frequencies (stmt, gsi.bb);
864 :
865 5529 : if (ins_after)
866 2544 : gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
867 : else
868 2985 : gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
869 :
870 5529 : return new_bb;
871 : }
872 :
873 : /* Insert STMTS on edge E. If a new block has to be created, it
874 : is returned. */
875 :
876 : basic_block
877 1219316 : gsi_insert_seq_on_edge_immediate (edge e, gimple_seq stmts)
878 : {
879 1219316 : gimple_stmt_iterator gsi;
880 1219316 : basic_block new_bb = NULL;
881 1219316 : bool ins_after;
882 :
883 1219316 : gcc_assert (!PENDING_STMT (e));
884 :
885 1219316 : ins_after = gimple_find_edge_insert_loc (e, &gsi, &new_bb);
886 1219316 : update_call_edge_frequencies (gimple_seq_first (stmts), gsi.bb);
887 :
888 1219316 : if (ins_after)
889 1165752 : gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
890 : else
891 53564 : gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
892 :
893 1219316 : return new_bb;
894 : }
895 :
896 : /* This routine will commit all pending edge insertions, creating any new
897 : basic blocks which are necessary. */
898 :
899 : void
900 2941130 : gsi_commit_edge_inserts (void)
901 : {
902 2941130 : basic_block bb;
903 2941130 : edge e;
904 2941130 : edge_iterator ei;
905 :
906 2941130 : gsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
907 : NULL);
908 :
909 49897375 : FOR_EACH_BB_FN (bb, cfun)
910 113300600 : FOR_EACH_EDGE (e, ei, bb->succs)
911 66344355 : gsi_commit_one_edge_insert (e, NULL);
912 2941130 : }
913 :
914 :
915 : /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
916 : to this block, otherwise set it to NULL. */
917 :
918 : void
919 69313079 : gsi_commit_one_edge_insert (edge e, basic_block *new_bb)
920 : {
921 69313079 : if (new_bb)
922 0 : *new_bb = NULL;
923 :
924 69313079 : if (PENDING_STMT (e))
925 : {
926 318021 : gimple_stmt_iterator gsi;
927 318021 : gimple_seq seq = PENDING_STMT (e);
928 318021 : bool ins_after;
929 :
930 318021 : PENDING_STMT (e) = NULL;
931 :
932 318021 : ins_after = gimple_find_edge_insert_loc (e, &gsi, new_bb);
933 318021 : update_call_edge_frequencies (gimple_seq_first (seq), gsi.bb);
934 :
935 318021 : if (ins_after)
936 183536 : gsi_insert_seq_after (&gsi, seq, GSI_NEW_STMT);
937 : else
938 134485 : gsi_insert_seq_before (&gsi, seq, GSI_NEW_STMT);
939 : }
940 69313079 : }
941 :
942 : /* Returns iterator at the start of the list of phi nodes of BB. */
943 :
944 : gphi_iterator
945 11787722639 : gsi_start_phis (basic_block bb)
946 : {
947 11787722639 : gimple_seq *pseq = phi_nodes_ptr (bb);
948 :
949 : /* Adapted from gsi_start. */
950 11787722639 : gphi_iterator i;
951 :
952 11787722639 : i.ptr = gimple_seq_first (*pseq);
953 11787722639 : i.seq = pseq;
954 11787722639 : i.bb = i.ptr ? gimple_bb (i.ptr) : NULL;
955 :
956 11787722639 : return i;
957 : }
958 :
959 : /* Helper function for gsi_safe_insert_before and gsi_safe_insert_seq_before.
960 : Find edge to insert statements before returns_twice call at the start of BB,
961 : if there isn't just one, split the bb and adjust PHIs to ensure that. */
962 :
963 : static edge
964 269 : edge_before_returns_twice_call (basic_block bb)
965 : {
966 269 : gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb);
967 269 : gcc_checking_assert (is_gimple_call (gsi_stmt (gsi))
968 : && (gimple_call_flags (gsi_stmt (gsi))
969 : & ECF_RETURNS_TWICE) != 0);
970 269 : edge_iterator ei;
971 269 : edge e, ad_edge = NULL, other_edge = NULL;
972 269 : bool split = false;
973 871 : FOR_EACH_EDGE (e, ei, bb->preds)
974 : {
975 602 : if ((e->flags & (EDGE_ABNORMAL | EDGE_EH)) == EDGE_ABNORMAL)
976 : {
977 269 : gimple_stmt_iterator gsi
978 269 : = gsi_start_nondebug_after_labels_bb (e->src);
979 269 : gimple *ad = gsi_stmt (gsi);
980 269 : if (ad && gimple_call_internal_p (ad, IFN_ABNORMAL_DISPATCHER))
981 : {
982 269 : gcc_checking_assert (ad_edge == NULL);
983 269 : ad_edge = e;
984 269 : continue;
985 : }
986 : }
987 333 : if (other_edge || e->flags & (EDGE_ABNORMAL | EDGE_EH))
988 64 : split = true;
989 : other_edge = e;
990 : }
991 269 : gcc_checking_assert (ad_edge);
992 269 : if (other_edge == NULL)
993 : split = true;
994 269 : if (split)
995 : {
996 33 : other_edge = split_block_after_labels (bb);
997 33 : e = make_edge (ad_edge->src, other_edge->dest, EDGE_ABNORMAL);
998 33 : for (gphi_iterator gsi = gsi_start_phis (other_edge->src);
999 115 : !gsi_end_p (gsi); gsi_next (&gsi))
1000 : {
1001 82 : gphi *phi = gsi.phi ();
1002 82 : tree lhs = gimple_phi_result (phi);
1003 82 : tree new_lhs = copy_ssa_name (lhs);
1004 82 : gimple_phi_set_result (phi, new_lhs);
1005 82 : gphi *new_phi = create_phi_node (lhs, other_edge->dest);
1006 82 : add_phi_arg (new_phi, new_lhs, other_edge, UNKNOWN_LOCATION);
1007 82 : add_phi_arg (new_phi, gimple_phi_arg_def_from_edge (phi, ad_edge),
1008 : e, gimple_phi_arg_location_from_edge (phi, ad_edge));
1009 : }
1010 33 : e->flags = ad_edge->flags;
1011 33 : e->probability = ad_edge->probability;
1012 33 : remove_edge (ad_edge);
1013 33 : if (dom_info_available_p (CDI_DOMINATORS))
1014 : {
1015 12 : set_immediate_dominator (CDI_DOMINATORS, other_edge->src,
1016 : recompute_dominator (CDI_DOMINATORS,
1017 : other_edge->src));
1018 12 : set_immediate_dominator (CDI_DOMINATORS, other_edge->dest,
1019 : recompute_dominator (CDI_DOMINATORS,
1020 : other_edge->dest));
1021 : }
1022 : }
1023 269 : return other_edge;
1024 : }
1025 :
1026 : /* Helper function for gsi_safe_insert_before and gsi_safe_insert_seq_before.
1027 : Replace SSA_NAME uses in G if they are PHI results of PHIs on E->dest
1028 : bb with the corresponding PHI argument from E edge. */
1029 :
1030 : static void
1031 269 : adjust_before_returns_twice_call (edge e, gimple *g)
1032 : {
1033 269 : use_operand_p use_p;
1034 269 : ssa_op_iter iter;
1035 269 : bool m = false;
1036 585 : FOR_EACH_SSA_USE_OPERAND (use_p, g, iter, SSA_OP_USE)
1037 : {
1038 316 : tree s = USE_FROM_PTR (use_p);
1039 316 : if (SSA_NAME_DEF_STMT (s)
1040 316 : && gimple_code (SSA_NAME_DEF_STMT (s)) == GIMPLE_PHI
1041 493 : && gimple_bb (SSA_NAME_DEF_STMT (s)) == e->dest)
1042 : {
1043 177 : tree r = gimple_phi_arg_def_from_edge (SSA_NAME_DEF_STMT (s), e);
1044 177 : SET_USE (use_p, unshare_expr (r));
1045 177 : m = true;
1046 : }
1047 : }
1048 269 : if (m)
1049 177 : update_stmt (g);
1050 269 : }
1051 :
1052 : /* Insert G stmt before ITER and keep ITER pointing to the same statement
1053 : as before. If ITER is a returns_twice call, insert it on an appropriate
1054 : edge instead. */
1055 :
1056 : void
1057 41405 : gsi_safe_insert_before (gimple_stmt_iterator *iter, gimple *g)
1058 : {
1059 41405 : gimple *stmt = gsi_stmt (*iter);
1060 41405 : if (stmt
1061 40387 : && is_gimple_call (stmt)
1062 1109 : && (gimple_call_flags (stmt) & ECF_RETURNS_TWICE) != 0
1063 41605 : && bb_has_abnormal_pred (gsi_bb (*iter)))
1064 : {
1065 199 : edge e = edge_before_returns_twice_call (gsi_bb (*iter));
1066 199 : basic_block new_bb = gsi_insert_on_edge_immediate (e, g);
1067 199 : if (new_bb)
1068 33 : e = single_succ_edge (new_bb);
1069 199 : adjust_before_returns_twice_call (e, g);
1070 199 : *iter = gsi_for_stmt (stmt);
1071 : }
1072 : else
1073 41206 : gsi_insert_before (iter, g, GSI_SAME_STMT);
1074 41405 : }
1075 :
1076 : /* Similarly for sequence SEQ. */
1077 :
1078 : void
1079 4394 : gsi_safe_insert_seq_before (gimple_stmt_iterator *iter, gimple_seq seq)
1080 : {
1081 4394 : if (gimple_seq_empty_p (seq))
1082 : return;
1083 3178 : gimple *stmt = gsi_stmt (*iter);
1084 3178 : if (stmt
1085 3178 : && is_gimple_call (stmt)
1086 82 : && (gimple_call_flags (stmt) & ECF_RETURNS_TWICE) != 0
1087 3248 : && bb_has_abnormal_pred (gsi_bb (*iter)))
1088 : {
1089 70 : edge e = edge_before_returns_twice_call (gsi_bb (*iter));
1090 70 : gimple *f = gimple_seq_first_stmt (seq);
1091 70 : gimple *l = gimple_seq_last_stmt (seq);
1092 70 : basic_block new_bb = gsi_insert_seq_on_edge_immediate (e, seq);
1093 70 : if (new_bb)
1094 0 : e = single_succ_edge (new_bb);
1095 70 : for (gimple_stmt_iterator gsi = gsi_for_stmt (f); ; gsi_next (&gsi))
1096 : {
1097 70 : gimple *g = gsi_stmt (gsi);
1098 70 : adjust_before_returns_twice_call (e, g);
1099 70 : if (g == l)
1100 : break;
1101 : }
1102 70 : *iter = gsi_for_stmt (stmt);
1103 : }
1104 : else
1105 3108 : gsi_insert_seq_before (iter, seq, GSI_SAME_STMT);
1106 : }
|
