1 /* Iterator routines for GIMPLE statements.
2 Copyright (C) 2007, 2008 Free Software Foundation, Inc.
3 Contributed by Aldy Hernandez <aldy@quesejoda.com>
5 This file is part of GCC.
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
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
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/>. */
23 #include "coretypes.h"
27 #include "tree-flow.h"
28 #include "value-prof.h"
31 /* Mark the statement STMT as modified, and update it. */
34 update_modified_stmt (gimple stmt)
36 if (!ssa_operands_active ())
38 update_stmt_if_modified (stmt);
42 /* Mark the statements in SEQ as modified, and update them. */
45 update_modified_stmts (gimple_seq seq)
47 gimple_stmt_iterator gsi;
49 if (!ssa_operands_active ())
51 for (gsi = gsi_start (seq); !gsi_end_p (gsi); gsi_next (&gsi))
52 update_stmt_if_modified (gsi_stmt (gsi));
56 /* Set BB to be the basic block for all the statements in the list
57 starting at FIRST and LAST. */
60 update_bb_for_stmts (gimple_seq_node first, basic_block bb)
64 for (n = first; n; n = n->next)
65 gimple_set_bb (n->stmt, bb);
69 /* Insert the sequence delimited by nodes FIRST and LAST before
70 iterator I. M specifies how to update iterator I after insertion
71 (see enum gsi_iterator_update).
73 This routine assumes that there is a forward and backward path
74 between FIRST and LAST (i.e., they are linked in a doubly-linked
75 list). Additionally, if FIRST == LAST, this routine will properly
76 insert a single node. */
79 gsi_insert_seq_nodes_before (gimple_stmt_iterator *i,
80 gimple_seq_node first,
82 enum gsi_iterator_update mode)
85 gimple_seq_node cur = i->ptr;
87 if ((bb = gsi_bb (*i)) != NULL)
88 update_bb_for_stmts (first, bb);
90 /* Link SEQ before CUR in the sequence. */
93 first->prev = cur->prev;
95 first->prev->next = first;
97 gimple_seq_set_first (i->seq, first);
103 gimple_seq_node itlast = gimple_seq_last (i->seq);
105 /* If CUR is NULL, we link at the end of the sequence (this case happens
106 when gsi_after_labels is called for a basic block that contains only
107 labels, so it returns an iterator after the end of the block, and
108 we need to insert before it; it might be cleaner to add a flag to the
109 iterator saying whether we are at the start or end of the list). */
110 first->prev = itlast;
112 itlast->next = first;
114 gimple_seq_set_first (i->seq, first);
115 gimple_seq_set_last (i->seq, last);
118 /* Update the iterator, if requested. */
122 case GSI_CONTINUE_LINKING:
133 /* Inserts the sequence of statements SEQ before the statement pointed
134 by iterator I. MODE indicates what to do with the iterator after
135 insertion (see enum gsi_iterator_update).
137 This function does not scan for new operands. It is provided for
138 the use of the gimplifier, which manipulates statements for which
139 def/use information has not yet been constructed. Most callers
140 should use gsi_insert_seq_before. */
143 gsi_insert_seq_before_without_update (gimple_stmt_iterator *i, gimple_seq seq,
144 enum gsi_iterator_update mode)
146 gimple_seq_node first, last;
151 /* Don't allow inserting a sequence into itself. */
152 gcc_assert (seq != i->seq);
154 first = gimple_seq_first (seq);
155 last = gimple_seq_last (seq);
157 gimple_seq_set_first (seq, NULL);
158 gimple_seq_set_last (seq, NULL);
159 gimple_seq_free (seq);
161 /* Empty sequences need no work. */
164 gcc_assert (first == last);
168 gsi_insert_seq_nodes_before (i, first, last, mode);
172 /* Inserts the sequence of statements SEQ before the statement pointed
173 by iterator I. MODE indicates what to do with the iterator after
174 insertion (see enum gsi_iterator_update). Scan the statements in SEQ
178 gsi_insert_seq_before (gimple_stmt_iterator *i, gimple_seq seq,
179 enum gsi_iterator_update mode)
181 update_modified_stmts (seq);
182 gsi_insert_seq_before_without_update (i, seq, mode);
186 /* Insert the sequence delimited by nodes FIRST and LAST after
187 iterator I. M specifies how to update iterator I after insertion
188 (see enum gsi_iterator_update).
190 This routine assumes that there is a forward and backward path
191 between FIRST and LAST (i.e., they are linked in a doubly-linked
192 list). Additionally, if FIRST == LAST, this routine will properly
193 insert a single node. */
196 gsi_insert_seq_nodes_after (gimple_stmt_iterator *i,
197 gimple_seq_node first,
198 gimple_seq_node last,
199 enum gsi_iterator_update m)
202 gimple_seq_node cur = i->ptr;
204 /* If the iterator is inside a basic block, we need to update the
205 basic block information for all the nodes between FIRST and LAST. */
206 if ((bb = gsi_bb (*i)) != NULL)
207 update_bb_for_stmts (first, bb);
209 /* Link SEQ after CUR. */
212 last->next = cur->next;
214 last->next->prev = last;
216 gimple_seq_set_last (i->seq, last);
222 gcc_assert (!gimple_seq_last (i->seq));
223 gimple_seq_set_first (i->seq, first);
224 gimple_seq_set_last (i->seq, last);
227 /* Update the iterator, if requested. */
233 case GSI_CONTINUE_LINKING:
245 /* Links sequence SEQ after the statement pointed-to by iterator I.
246 MODE is as in gsi_insert_after.
248 This function does not scan for new operands. It is provided for
249 the use of the gimplifier, which manipulates statements for which
250 def/use information has not yet been constructed. Most callers
251 should use gsi_insert_seq_after. */
254 gsi_insert_seq_after_without_update (gimple_stmt_iterator *i, gimple_seq seq,
255 enum gsi_iterator_update mode)
257 gimple_seq_node first, last;
262 /* Don't allow inserting a sequence into itself. */
263 gcc_assert (seq != i->seq);
265 first = gimple_seq_first (seq);
266 last = gimple_seq_last (seq);
268 gimple_seq_set_first (seq, NULL);
269 gimple_seq_set_last (seq, NULL);
270 gimple_seq_free (seq);
272 /* Empty sequences need no work. */
275 gcc_assert (first == last);
279 gsi_insert_seq_nodes_after (i, first, last, mode);
283 /* Links sequence SEQ after the statement pointed-to by iterator I.
284 MODE is as in gsi_insert_after. Scan the statements in SEQ
288 gsi_insert_seq_after (gimple_stmt_iterator *i, gimple_seq seq,
289 enum gsi_iterator_update mode)
291 update_modified_stmts (seq);
292 gsi_insert_seq_after_without_update (i, seq, mode);
296 /* Move all statements in the sequence after I to a new sequence.
297 Return this new sequence. */
300 gsi_split_seq_after (gimple_stmt_iterator i)
302 gimple_seq_node cur, next;
303 gimple_seq old_seq, new_seq;
307 /* How can we possibly split after the end, or before the beginning? */
308 gcc_assert (cur && cur->next);
312 new_seq = gimple_seq_alloc ();
314 gimple_seq_set_first (new_seq, next);
315 gimple_seq_set_last (new_seq, gimple_seq_last (old_seq));
316 gimple_seq_set_last (old_seq, cur);
324 /* Move all statements in the sequence before I to a new sequence.
325 Return this new sequence. I is set to the head of the new list. */
328 gsi_split_seq_before (gimple_stmt_iterator *i)
330 gimple_seq_node cur, prev;
331 gimple_seq old_seq, new_seq;
335 /* How can we possibly split after the end? */
340 new_seq = gimple_seq_alloc ();
343 /* Set the limits on NEW_SEQ. */
344 gimple_seq_set_first (new_seq, cur);
345 gimple_seq_set_last (new_seq, gimple_seq_last (old_seq));
347 /* Cut OLD_SEQ before I. */
348 gimple_seq_set_last (old_seq, prev);
353 gimple_seq_set_first (old_seq, NULL);
359 /* Replace the statement pointed-to by GSI to STMT. If UPDATE_EH_INFO
360 is true, the exception handling information of the original
361 statement is moved to the new statement. */
364 gsi_replace (gimple_stmt_iterator *gsi, gimple stmt, bool update_eh_info)
366 gimple orig_stmt = gsi_stmt (*gsi);
368 if (stmt == orig_stmt)
371 gimple_set_location (stmt, gimple_location (orig_stmt));
372 gimple_set_bb (stmt, gsi_bb (*gsi));
374 /* Preserve EH region information from the original statement, if
375 requested by the caller. */
377 maybe_clean_or_replace_eh_stmt (orig_stmt, stmt);
379 gimple_duplicate_stmt_histograms (cfun, stmt, cfun, orig_stmt);
380 gimple_remove_stmt_histograms (cfun, orig_stmt);
381 delink_stmt_imm_use (orig_stmt);
382 *gsi_stmt_ptr (gsi) = stmt;
383 gimple_set_modified (stmt, true);
384 update_modified_stmt (stmt);
388 /* Insert statement STMT before the statement pointed-to by iterator I.
389 M specifies how to update iterator I after insertion (see enum
390 gsi_iterator_update).
392 This function does not scan for new operands. It is provided for
393 the use of the gimplifier, which manipulates statements for which
394 def/use information has not yet been constructed. Most callers
395 should use gsi_insert_before. */
398 gsi_insert_before_without_update (gimple_stmt_iterator *i, gimple stmt,
399 enum gsi_iterator_update m)
403 n = GGC_NEW (struct gimple_seq_node_d);
404 n->prev = n->next = NULL;
406 gsi_insert_seq_nodes_before (i, n, n, m);
409 /* Insert statement STMT before the statement pointed-to by iterator I.
410 Update STMT's basic block and scan it for new operands. M
411 specifies how to update iterator I after insertion (see enum
412 gsi_iterator_update). */
415 gsi_insert_before (gimple_stmt_iterator *i, gimple stmt,
416 enum gsi_iterator_update m)
418 update_modified_stmt (stmt);
419 gsi_insert_before_without_update (i, stmt, m);
423 /* Insert statement STMT after the statement pointed-to by iterator I.
424 M specifies how to update iterator I after insertion (see enum
425 gsi_iterator_update).
427 This function does not scan for new operands. It is provided for
428 the use of the gimplifier, which manipulates statements for which
429 def/use information has not yet been constructed. Most callers
430 should use gsi_insert_after. */
433 gsi_insert_after_without_update (gimple_stmt_iterator *i, gimple stmt,
434 enum gsi_iterator_update m)
438 n = GGC_NEW (struct gimple_seq_node_d);
439 n->prev = n->next = NULL;
441 gsi_insert_seq_nodes_after (i, n, n, m);
445 /* Insert statement STMT after the statement pointed-to by iterator I.
446 Update STMT's basic block and scan it for new operands. M
447 specifies how to update iterator I after insertion (see enum
448 gsi_iterator_update). */
451 gsi_insert_after (gimple_stmt_iterator *i, gimple stmt,
452 enum gsi_iterator_update m)
454 update_modified_stmt (stmt);
455 gsi_insert_after_without_update (i, stmt, m);
459 /* Remove the current stmt from the sequence. The iterator is updated
460 to point to the next statement.
462 REMOVE_PERMANENTLY is true when the statement is going to be removed
463 from the IL and not reinserted elsewhere. In that case we remove the
464 statement pointed to by iterator I from the EH tables, and free its
465 operand caches. Otherwise we do not modify this information. */
468 gsi_remove (gimple_stmt_iterator *i, bool remove_permanently)
470 gimple_seq_node cur, next, prev;
471 gimple stmt = gsi_stmt (*i);
473 /* Free all the data flow information for STMT. */
474 gimple_set_bb (stmt, NULL);
475 delink_stmt_imm_use (stmt);
476 gimple_set_modified (stmt, true);
478 if (remove_permanently)
480 remove_stmt_from_eh_lp (stmt);
481 gimple_remove_stmt_histograms (cfun, stmt);
484 /* Update the iterator and re-wire the links in I->SEQ. */
492 gimple_seq_set_first (i->seq, next);
497 gimple_seq_set_last (i->seq, prev);
503 /* Finds iterator for STMT. */
506 gsi_for_stmt (gimple stmt)
508 gimple_stmt_iterator i;
509 basic_block bb = gimple_bb (stmt);
511 if (gimple_code (stmt) == GIMPLE_PHI)
512 i = gsi_start_phis (bb);
514 i = gsi_start_bb (bb);
516 for (; !gsi_end_p (i); gsi_next (&i))
517 if (gsi_stmt (i) == stmt)
524 /* Move the statement at FROM so it comes right after the statement at TO. */
527 gsi_move_after (gimple_stmt_iterator *from, gimple_stmt_iterator *to)
529 gimple stmt = gsi_stmt (*from);
530 gsi_remove (from, false);
532 /* We must have GSI_NEW_STMT here, as gsi_move_after is sometimes used to
533 move statements to an empty block. */
534 gsi_insert_after (to, stmt, GSI_NEW_STMT);
538 /* Move the statement at FROM so it comes right before the statement
542 gsi_move_before (gimple_stmt_iterator *from, gimple_stmt_iterator *to)
544 gimple stmt = gsi_stmt (*from);
545 gsi_remove (from, false);
547 /* For consistency with gsi_move_after, it might be better to have
548 GSI_NEW_STMT here; however, that breaks several places that expect
549 that TO does not change. */
550 gsi_insert_before (to, stmt, GSI_SAME_STMT);
554 /* Move the statement at FROM to the end of basic block BB. */
557 gsi_move_to_bb_end (gimple_stmt_iterator *from, basic_block bb)
559 gimple_stmt_iterator last = gsi_last_bb (bb);
560 #ifdef ENABLE_CHECKING
561 gcc_assert (gsi_bb (last) == bb);
564 /* Have to check gsi_end_p because it could be an empty block. */
565 if (!gsi_end_p (last) && is_ctrl_stmt (gsi_stmt (last)))
566 gsi_move_before (from, &last);
568 gsi_move_after (from, &last);
572 /* Add STMT to the pending list of edge E. No actual insertion is
573 made until a call to gsi_commit_edge_inserts () is made. */
576 gsi_insert_on_edge (edge e, gimple stmt)
578 gimple_seq_add_stmt (&PENDING_STMT (e), stmt);
581 /* Add the sequence of statements SEQ to the pending list of edge E.
582 No actual insertion is made until a call to gsi_commit_edge_inserts
586 gsi_insert_seq_on_edge (edge e, gimple_seq seq)
588 gimple_seq_add_seq (&PENDING_STMT (e), seq);
592 /* Insert the statement pointed-to by GSI into edge E. Every attempt
593 is made to place the statement in an existing basic block, but
594 sometimes that isn't possible. When it isn't possible, the edge is
595 split and the statement is added to the new block.
597 In all cases, the returned *GSI points to the correct location. The
598 return value is true if insertion should be done after the location,
599 or false if it should be done before the location. If a new basic block
600 has to be created, it is stored in *NEW_BB. */
603 gimple_find_edge_insert_loc (edge e, gimple_stmt_iterator *gsi,
606 basic_block dest, src;
611 /* If the destination has one predecessor which has no PHI nodes,
612 insert there. Except for the exit block.
614 The requirement for no PHI nodes could be relaxed. Basically we
615 would have to examine the PHIs to prove that none of them used
616 the value set by the statement we want to insert on E. That
617 hardly seems worth the effort. */
619 if (single_pred_p (dest)
620 && gimple_seq_empty_p (phi_nodes (dest))
621 && dest != EXIT_BLOCK_PTR)
623 *gsi = gsi_start_bb (dest);
624 if (gsi_end_p (*gsi))
627 /* Make sure we insert after any leading labels. */
628 tmp = gsi_stmt (*gsi);
629 while (gimple_code (tmp) == GIMPLE_LABEL)
632 if (gsi_end_p (*gsi))
634 tmp = gsi_stmt (*gsi);
637 if (gsi_end_p (*gsi))
639 *gsi = gsi_last_bb (dest);
646 /* If the source has one successor, the edge is not abnormal and
647 the last statement does not end a basic block, insert there.
648 Except for the entry block. */
650 if ((e->flags & EDGE_ABNORMAL) == 0
651 && single_succ_p (src)
652 && src != ENTRY_BLOCK_PTR)
654 *gsi = gsi_last_bb (src);
655 if (gsi_end_p (*gsi))
658 tmp = gsi_stmt (*gsi);
659 if (!stmt_ends_bb_p (tmp))
662 switch (gimple_code (tmp))
672 /* Otherwise, create a new basic block, and split this edge. */
673 dest = split_edge (e);
676 e = single_pred_edge (dest);
681 /* Similar to gsi_insert_on_edge+gsi_commit_edge_inserts. If a new
682 block has to be created, it is returned. */
685 gsi_insert_on_edge_immediate (edge e, gimple stmt)
687 gimple_stmt_iterator gsi;
688 basic_block new_bb = NULL;
690 gcc_assert (!PENDING_STMT (e));
692 if (gimple_find_edge_insert_loc (e, &gsi, &new_bb))
693 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
695 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
700 /* Insert STMTS on edge E. If a new block has to be created, it
704 gsi_insert_seq_on_edge_immediate (edge e, gimple_seq stmts)
706 gimple_stmt_iterator gsi;
707 basic_block new_bb = NULL;
709 gcc_assert (!PENDING_STMT (e));
711 if (gimple_find_edge_insert_loc (e, &gsi, &new_bb))
712 gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
714 gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
719 /* This routine will commit all pending edge insertions, creating any new
720 basic blocks which are necessary. */
723 gsi_commit_edge_inserts (void)
729 gsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR), NULL);
732 FOR_EACH_EDGE (e, ei, bb->succs)
733 gsi_commit_one_edge_insert (e, NULL);
737 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
738 to this block, otherwise set it to NULL. */
741 gsi_commit_one_edge_insert (edge e, basic_block *new_bb)
746 if (PENDING_STMT (e))
748 gimple_stmt_iterator gsi;
749 gimple_seq seq = PENDING_STMT (e);
751 PENDING_STMT (e) = NULL;
753 if (gimple_find_edge_insert_loc (e, &gsi, new_bb))
754 gsi_insert_seq_after (&gsi, seq, GSI_NEW_STMT);
756 gsi_insert_seq_before (&gsi, seq, GSI_NEW_STMT);
760 /* Returns iterator at the start of the list of phi nodes of BB. */
763 gsi_start_phis (basic_block bb)
765 return gsi_start (phi_nodes (bb));