1 /* Iterator routines for GIMPLE statements.
2 Copyright (C) 2007-2015 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"
32 #include "fold-const.h"
34 #include "hard-reg-set.h"
37 #include "dominance.h"
39 #include "basic-block.h"
40 #include "tree-ssa-alias.h"
41 #include "internal-fn.h"
43 #include "gimple-expr.h"
46 #include "gimple-iterator.h"
47 #include "gimple-ssa.h"
49 #include "plugin-api.h"
53 #include "tree-phinodes.h"
54 #include "ssa-iterators.h"
56 #include "value-prof.h"
59 /* Mark the statement STMT as modified, and update it. */
62 update_modified_stmt (gimple stmt
)
64 if (!ssa_operands_active (cfun
))
66 update_stmt_if_modified (stmt
);
70 /* Mark the statements in SEQ as modified, and update them. */
73 update_modified_stmts (gimple_seq seq
)
75 gimple_stmt_iterator gsi
;
77 if (!ssa_operands_active (cfun
))
79 for (gsi
= gsi_start (seq
); !gsi_end_p (gsi
); gsi_next (&gsi
))
80 update_stmt_if_modified (gsi_stmt (gsi
));
84 /* Set BB to be the basic block for all the statements in the list
85 starting at FIRST and LAST. */
88 update_bb_for_stmts (gimple_seq_node first
, gimple_seq_node last
,
93 for (n
= first
; n
; n
= n
->next
)
95 gimple_set_bb (n
, bb
);
101 /* Set the frequencies for the cgraph_edges for each of the calls
102 starting at FIRST for their new position within BB. */
105 update_call_edge_frequencies (gimple_seq_node first
, basic_block bb
)
107 struct cgraph_node
*cfun_node
= NULL
;
111 for (n
= first
; n
; n
= n
->next
)
112 if (is_gimple_call (n
))
114 struct cgraph_edge
*e
;
116 /* These function calls are expensive enough that we want
117 to avoid calling them if we never see any calls. */
118 if (cfun_node
== NULL
)
120 cfun_node
= cgraph_node::get (current_function_decl
);
121 bb_freq
= (compute_call_stmt_bb_frequency
122 (current_function_decl
, bb
));
125 e
= cfun_node
->get_edge (n
);
127 e
->frequency
= bb_freq
;
131 /* Insert the sequence delimited by nodes FIRST and LAST before
132 iterator I. M specifies how to update iterator I after insertion
133 (see enum gsi_iterator_update).
135 This routine assumes that there is a forward and backward path
136 between FIRST and LAST (i.e., they are linked in a doubly-linked
137 list). Additionally, if FIRST == LAST, this routine will properly
138 insert a single node. */
141 gsi_insert_seq_nodes_before (gimple_stmt_iterator
*i
,
142 gimple_seq_node first
,
143 gimple_seq_node last
,
144 enum gsi_iterator_update mode
)
147 gimple_seq_node cur
= i
->ptr
;
149 gcc_assert (!cur
|| cur
->prev
);
151 if ((bb
= gsi_bb (*i
)) != NULL
)
152 update_bb_for_stmts (first
, last
, bb
);
154 /* Link SEQ before CUR in the sequence. */
157 first
->prev
= cur
->prev
;
158 if (first
->prev
->next
)
159 first
->prev
->next
= first
;
161 gimple_seq_set_first (i
->seq
, first
);
167 gimple_seq_node itlast
= gimple_seq_last (*i
->seq
);
169 /* If CUR is NULL, we link at the end of the sequence (this case happens
170 when gsi_after_labels is called for a basic block that contains only
171 labels, so it returns an iterator after the end of the block, and
172 we need to insert before it; it might be cleaner to add a flag to the
173 iterator saying whether we are at the start or end of the list). */
177 first
->prev
= itlast
;
178 itlast
->next
= first
;
181 gimple_seq_set_first (i
->seq
, first
);
182 gimple_seq_set_last (i
->seq
, last
);
185 /* Update the iterator, if requested. */
189 case GSI_CONTINUE_LINKING
:
200 /* Inserts the sequence of statements SEQ before the statement pointed
201 by iterator I. MODE indicates what to do with the iterator after
202 insertion (see enum gsi_iterator_update).
204 This function does not scan for new operands. It is provided for
205 the use of the gimplifier, which manipulates statements for which
206 def/use information has not yet been constructed. Most callers
207 should use gsi_insert_seq_before. */
210 gsi_insert_seq_before_without_update (gimple_stmt_iterator
*i
, gimple_seq seq
,
211 enum gsi_iterator_update mode
)
213 gimple_seq_node first
, last
;
218 /* Don't allow inserting a sequence into itself. */
219 gcc_assert (seq
!= *i
->seq
);
221 first
= gimple_seq_first (seq
);
222 last
= gimple_seq_last (seq
);
224 /* Empty sequences need no work. */
227 gcc_assert (first
== last
);
231 gsi_insert_seq_nodes_before (i
, first
, last
, mode
);
235 /* Inserts the sequence of statements SEQ before the statement pointed
236 by iterator I. MODE indicates what to do with the iterator after
237 insertion (see enum gsi_iterator_update). Scan the statements in SEQ
241 gsi_insert_seq_before (gimple_stmt_iterator
*i
, gimple_seq seq
,
242 enum gsi_iterator_update mode
)
244 update_modified_stmts (seq
);
245 gsi_insert_seq_before_without_update (i
, seq
, mode
);
249 /* Insert the sequence delimited by nodes FIRST and LAST after
250 iterator I. M specifies how to update iterator I after insertion
251 (see enum gsi_iterator_update).
253 This routine assumes that there is a forward and backward path
254 between FIRST and LAST (i.e., they are linked in a doubly-linked
255 list). Additionally, if FIRST == LAST, this routine will properly
256 insert a single node. */
259 gsi_insert_seq_nodes_after (gimple_stmt_iterator
*i
,
260 gimple_seq_node first
,
261 gimple_seq_node last
,
262 enum gsi_iterator_update m
)
265 gimple_seq_node cur
= i
->ptr
;
267 gcc_assert (!cur
|| cur
->prev
);
269 /* If the iterator is inside a basic block, we need to update the
270 basic block information for all the nodes between FIRST and LAST. */
271 if ((bb
= gsi_bb (*i
)) != NULL
)
272 update_bb_for_stmts (first
, last
, bb
);
274 /* Link SEQ after CUR. */
277 last
->next
= cur
->next
;
280 last
->next
->prev
= last
;
283 gimple_seq_set_last (i
->seq
, last
);
289 gcc_assert (!gimple_seq_last (*i
->seq
));
291 gimple_seq_set_first (i
->seq
, first
);
292 gimple_seq_set_last (i
->seq
, last
);
295 /* Update the iterator, if requested. */
301 case GSI_CONTINUE_LINKING
:
313 /* Links sequence SEQ after the statement pointed-to by iterator I.
314 MODE is as in gsi_insert_after.
316 This function does not scan for new operands. It is provided for
317 the use of the gimplifier, which manipulates statements for which
318 def/use information has not yet been constructed. Most callers
319 should use gsi_insert_seq_after. */
322 gsi_insert_seq_after_without_update (gimple_stmt_iterator
*i
, gimple_seq seq
,
323 enum gsi_iterator_update mode
)
325 gimple_seq_node first
, last
;
330 /* Don't allow inserting a sequence into itself. */
331 gcc_assert (seq
!= *i
->seq
);
333 first
= gimple_seq_first (seq
);
334 last
= gimple_seq_last (seq
);
336 /* Empty sequences need no work. */
339 gcc_assert (first
== last
);
343 gsi_insert_seq_nodes_after (i
, first
, last
, mode
);
347 /* Links sequence SEQ after the statement pointed-to by iterator I.
348 MODE is as in gsi_insert_after. Scan the statements in SEQ
352 gsi_insert_seq_after (gimple_stmt_iterator
*i
, gimple_seq seq
,
353 enum gsi_iterator_update mode
)
355 update_modified_stmts (seq
);
356 gsi_insert_seq_after_without_update (i
, seq
, mode
);
360 /* Move all statements in the sequence after I to a new sequence.
361 Return this new sequence. */
364 gsi_split_seq_after (gimple_stmt_iterator i
)
366 gimple_seq_node cur
, next
;
367 gimple_seq
*pold_seq
, new_seq
;
371 /* How can we possibly split after the end, or before the beginning? */
372 gcc_assert (cur
&& cur
->next
);
377 gimple_seq_set_first (&new_seq
, next
);
378 gimple_seq_set_last (&new_seq
, gimple_seq_last (*pold_seq
));
379 gimple_seq_set_last (pold_seq
, cur
);
386 /* Set the statement to which GSI points to STMT. This only updates
387 the iterator and the gimple sequence, it doesn't do the bookkeeping
391 gsi_set_stmt (gimple_stmt_iterator
*gsi
, gimple stmt
)
393 gimple orig_stmt
= gsi_stmt (*gsi
);
396 stmt
->next
= next
= orig_stmt
->next
;
397 stmt
->prev
= prev
= orig_stmt
->prev
;
398 /* Note how we don't clear next/prev of orig_stmt. This is so that
399 copies of *GSI our callers might still hold (to orig_stmt)
400 can be advanced as if they too were replaced. */
404 gimple_seq_set_first (gsi
->seq
, stmt
);
408 gimple_seq_set_last (gsi
->seq
, stmt
);
414 /* Move all statements in the sequence before I to a new sequence.
415 Return this new sequence. I is set to the head of the new list. */
418 gsi_split_seq_before (gimple_stmt_iterator
*i
, gimple_seq
*pnew_seq
)
420 gimple_seq_node cur
, prev
;
425 /* How can we possibly split after the end? */
434 /* Set the limits on NEW_SEQ. */
435 gimple_seq_set_first (pnew_seq
, cur
);
436 gimple_seq_set_last (pnew_seq
, gimple_seq_last (old_seq
));
438 /* Cut OLD_SEQ before I. */
439 gimple_seq_set_last (&old_seq
, prev
);
445 /* Replace the statement pointed-to by GSI to STMT. If UPDATE_EH_INFO
446 is true, the exception handling information of the original
447 statement is moved to the new statement. Assignments must only be
448 replaced with assignments to the same LHS. Returns whether EH edge
449 cleanup is required. */
452 gsi_replace (gimple_stmt_iterator
*gsi
, gimple stmt
, bool update_eh_info
)
454 gimple orig_stmt
= gsi_stmt (*gsi
);
455 bool require_eh_edge_purge
= false;
457 if (stmt
== orig_stmt
)
460 gcc_assert (!gimple_has_lhs (orig_stmt
) || !gimple_has_lhs (stmt
)
461 || gimple_get_lhs (orig_stmt
) == gimple_get_lhs (stmt
));
463 gimple_set_location (stmt
, gimple_location (orig_stmt
));
464 gimple_set_bb (stmt
, gsi_bb (*gsi
));
466 /* Preserve EH region information from the original statement, if
467 requested by the caller. */
469 require_eh_edge_purge
= maybe_clean_or_replace_eh_stmt (orig_stmt
, stmt
);
471 gimple_duplicate_stmt_histograms (cfun
, stmt
, cfun
, orig_stmt
);
473 /* Free all the data flow information for ORIG_STMT. */
474 gimple_set_bb (orig_stmt
, NULL
);
475 gimple_remove_stmt_histograms (cfun
, orig_stmt
);
476 delink_stmt_imm_use (orig_stmt
);
478 gsi_set_stmt (gsi
, stmt
);
479 gimple_set_modified (stmt
, true);
480 update_modified_stmt (stmt
);
481 return require_eh_edge_purge
;
485 /* Replace the statement pointed-to by GSI with the sequence SEQ.
486 If UPDATE_EH_INFO is true, the exception handling information of
487 the original statement is moved to the last statement of the new
488 sequence. If the old statement is an assignment, then so must
489 be the last statement of the new sequence, and they must have the
493 gsi_replace_with_seq (gimple_stmt_iterator
*gsi
, gimple_seq seq
,
496 gimple_stmt_iterator seqi
;
498 if (gimple_seq_empty_p (seq
))
500 gsi_remove (gsi
, true);
503 seqi
= gsi_last (seq
);
504 last
= gsi_stmt (seqi
);
505 gsi_remove (&seqi
, false);
506 gsi_insert_seq_before (gsi
, seq
, GSI_SAME_STMT
);
507 gsi_replace (gsi
, last
, update_eh_info
);
511 /* Insert statement STMT before the statement pointed-to by iterator I.
512 M specifies how to update iterator I after insertion (see enum
513 gsi_iterator_update).
515 This function does not scan for new operands. It is provided for
516 the use of the gimplifier, which manipulates statements for which
517 def/use information has not yet been constructed. Most callers
518 should use gsi_insert_before. */
521 gsi_insert_before_without_update (gimple_stmt_iterator
*i
, gimple stmt
,
522 enum gsi_iterator_update m
)
524 gsi_insert_seq_nodes_before (i
, stmt
, stmt
, m
);
527 /* Insert statement STMT before the statement pointed-to by iterator I.
528 Update STMT's basic block and scan it for new operands. M
529 specifies how to update iterator I after insertion (see enum
530 gsi_iterator_update). */
533 gsi_insert_before (gimple_stmt_iterator
*i
, gimple stmt
,
534 enum gsi_iterator_update m
)
536 update_modified_stmt (stmt
);
537 gsi_insert_before_without_update (i
, stmt
, m
);
541 /* Insert statement STMT after the statement pointed-to by iterator I.
542 M specifies how to update iterator I after insertion (see enum
543 gsi_iterator_update).
545 This function does not scan for new operands. It is provided for
546 the use of the gimplifier, which manipulates statements for which
547 def/use information has not yet been constructed. Most callers
548 should use gsi_insert_after. */
551 gsi_insert_after_without_update (gimple_stmt_iterator
*i
, gimple stmt
,
552 enum gsi_iterator_update m
)
554 gsi_insert_seq_nodes_after (i
, stmt
, stmt
, m
);
558 /* Insert statement STMT after the statement pointed-to by iterator I.
559 Update STMT's basic block and scan it for new operands. M
560 specifies how to update iterator I after insertion (see enum
561 gsi_iterator_update). */
564 gsi_insert_after (gimple_stmt_iterator
*i
, gimple stmt
,
565 enum gsi_iterator_update m
)
567 update_modified_stmt (stmt
);
568 gsi_insert_after_without_update (i
, stmt
, m
);
572 /* Remove the current stmt from the sequence. The iterator is updated
573 to point to the next statement.
575 REMOVE_PERMANENTLY is true when the statement is going to be removed
576 from the IL and not reinserted elsewhere. In that case we remove the
577 statement pointed to by iterator I from the EH tables, and free its
578 operand caches. Otherwise we do not modify this information. Returns
579 true whether EH edge cleanup is required. */
582 gsi_remove (gimple_stmt_iterator
*i
, bool remove_permanently
)
584 gimple_seq_node cur
, next
, prev
;
585 gimple stmt
= gsi_stmt (*i
);
586 bool require_eh_edge_purge
= false;
588 if (gimple_code (stmt
) != GIMPLE_PHI
)
589 insert_debug_temps_for_defs (i
);
591 /* Free all the data flow information for STMT. */
592 gimple_set_bb (stmt
, NULL
);
593 delink_stmt_imm_use (stmt
);
594 gimple_set_modified (stmt
, true);
596 if (remove_permanently
)
598 require_eh_edge_purge
= remove_stmt_from_eh_lp (stmt
);
599 gimple_remove_stmt_histograms (cfun
, stmt
);
602 /* Update the iterator and re-wire the links in I->SEQ. */
606 /* See gsi_set_stmt for why we don't reset prev/next of STMT. */
609 /* Cur is not last. */
612 /* Cur is last but not first. */
613 gimple_seq_set_last (i
->seq
, prev
);
616 /* Cur is not first. */
624 return require_eh_edge_purge
;
628 /* Finds iterator for STMT. */
631 gsi_for_stmt (gimple stmt
)
633 gimple_stmt_iterator i
;
634 basic_block bb
= gimple_bb (stmt
);
636 if (gimple_code (stmt
) == GIMPLE_PHI
)
637 i
= gsi_start_phis (bb
);
639 i
= gsi_start_bb (bb
);
645 /* Finds iterator for PHI. */
648 gsi_for_phi (gphi
*phi
)
651 basic_block bb
= gimple_bb (phi
);
653 i
= gsi_start_phis (bb
);
659 /* Move the statement at FROM so it comes right after the statement at TO. */
662 gsi_move_after (gimple_stmt_iterator
*from
, gimple_stmt_iterator
*to
)
664 gimple stmt
= gsi_stmt (*from
);
665 gsi_remove (from
, false);
667 /* We must have GSI_NEW_STMT here, as gsi_move_after is sometimes used to
668 move statements to an empty block. */
669 gsi_insert_after (to
, stmt
, GSI_NEW_STMT
);
673 /* Move the statement at FROM so it comes right before the statement
677 gsi_move_before (gimple_stmt_iterator
*from
, gimple_stmt_iterator
*to
)
679 gimple stmt
= gsi_stmt (*from
);
680 gsi_remove (from
, false);
682 /* For consistency with gsi_move_after, it might be better to have
683 GSI_NEW_STMT here; however, that breaks several places that expect
684 that TO does not change. */
685 gsi_insert_before (to
, stmt
, GSI_SAME_STMT
);
689 /* Move the statement at FROM to the end of basic block BB. */
692 gsi_move_to_bb_end (gimple_stmt_iterator
*from
, basic_block bb
)
694 gimple_stmt_iterator last
= gsi_last_bb (bb
);
695 gcc_checking_assert (gsi_bb (last
) == bb
);
697 /* Have to check gsi_end_p because it could be an empty block. */
698 if (!gsi_end_p (last
) && is_ctrl_stmt (gsi_stmt (last
)))
699 gsi_move_before (from
, &last
);
701 gsi_move_after (from
, &last
);
705 /* Add STMT to the pending list of edge E. No actual insertion is
706 made until a call to gsi_commit_edge_inserts () is made. */
709 gsi_insert_on_edge (edge e
, gimple stmt
)
711 gimple_seq_add_stmt (&PENDING_STMT (e
), stmt
);
714 /* Add the sequence of statements SEQ to the pending list of edge E.
715 No actual insertion is made until a call to gsi_commit_edge_inserts
719 gsi_insert_seq_on_edge (edge e
, gimple_seq seq
)
721 gimple_seq_add_seq (&PENDING_STMT (e
), seq
);
724 /* Return a new iterator pointing to the first statement in sequence of
725 statements on edge E. Such statements need to be subsequently moved into a
726 basic block by calling gsi_commit_edge_inserts. */
729 gsi_start_edge (edge e
)
731 return gsi_start (PENDING_STMT (e
));
734 /* Insert the statement pointed-to by GSI into edge E. Every attempt
735 is made to place the statement in an existing basic block, but
736 sometimes that isn't possible. When it isn't possible, the edge is
737 split and the statement is added to the new block.
739 In all cases, the returned *GSI points to the correct location. The
740 return value is true if insertion should be done after the location,
741 or false if it should be done before the location. If a new basic block
742 has to be created, it is stored in *NEW_BB. */
745 gimple_find_edge_insert_loc (edge e
, gimple_stmt_iterator
*gsi
,
748 basic_block dest
, src
;
753 /* If the destination has one predecessor which has no PHI nodes,
754 insert there. Except for the exit block.
756 The requirement for no PHI nodes could be relaxed. Basically we
757 would have to examine the PHIs to prove that none of them used
758 the value set by the statement we want to insert on E. That
759 hardly seems worth the effort. */
761 if (single_pred_p (dest
)
762 && gimple_seq_empty_p (phi_nodes (dest
))
763 && dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
765 *gsi
= gsi_start_bb (dest
);
766 if (gsi_end_p (*gsi
))
769 /* Make sure we insert after any leading labels. */
770 tmp
= gsi_stmt (*gsi
);
771 while (gimple_code (tmp
) == GIMPLE_LABEL
)
774 if (gsi_end_p (*gsi
))
776 tmp
= gsi_stmt (*gsi
);
779 if (gsi_end_p (*gsi
))
781 *gsi
= gsi_last_bb (dest
);
788 /* If the source has one successor, the edge is not abnormal and
789 the last statement does not end a basic block, insert there.
790 Except for the entry block. */
792 if ((e
->flags
& EDGE_ABNORMAL
) == 0
793 && single_succ_p (src
)
794 && src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
796 *gsi
= gsi_last_bb (src
);
797 if (gsi_end_p (*gsi
))
800 tmp
= gsi_stmt (*gsi
);
801 if (!stmt_ends_bb_p (tmp
))
804 switch (gimple_code (tmp
))
814 /* Otherwise, create a new basic block, and split this edge. */
815 dest
= split_edge (e
);
818 e
= single_pred_edge (dest
);
823 /* Similar to gsi_insert_on_edge+gsi_commit_edge_inserts. If a new
824 block has to be created, it is returned. */
827 gsi_insert_on_edge_immediate (edge e
, gimple stmt
)
829 gimple_stmt_iterator gsi
;
830 basic_block new_bb
= NULL
;
833 gcc_assert (!PENDING_STMT (e
));
835 ins_after
= gimple_find_edge_insert_loc (e
, &gsi
, &new_bb
);
837 update_call_edge_frequencies (stmt
, gsi
.bb
);
840 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
842 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
847 /* Insert STMTS on edge E. If a new block has to be created, it
851 gsi_insert_seq_on_edge_immediate (edge e
, gimple_seq stmts
)
853 gimple_stmt_iterator gsi
;
854 basic_block new_bb
= NULL
;
857 gcc_assert (!PENDING_STMT (e
));
859 ins_after
= gimple_find_edge_insert_loc (e
, &gsi
, &new_bb
);
860 update_call_edge_frequencies (gimple_seq_first (stmts
), gsi
.bb
);
863 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
865 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
870 /* This routine will commit all pending edge insertions, creating any new
871 basic blocks which are necessary. */
874 gsi_commit_edge_inserts (void)
880 gsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
)),
883 FOR_EACH_BB_FN (bb
, cfun
)
884 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
885 gsi_commit_one_edge_insert (e
, NULL
);
889 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
890 to this block, otherwise set it to NULL. */
893 gsi_commit_one_edge_insert (edge e
, basic_block
*new_bb
)
898 if (PENDING_STMT (e
))
900 gimple_stmt_iterator gsi
;
901 gimple_seq seq
= PENDING_STMT (e
);
904 PENDING_STMT (e
) = NULL
;
906 ins_after
= gimple_find_edge_insert_loc (e
, &gsi
, new_bb
);
907 update_call_edge_frequencies (gimple_seq_first (seq
), gsi
.bb
);
910 gsi_insert_seq_after (&gsi
, seq
, GSI_NEW_STMT
);
912 gsi_insert_seq_before (&gsi
, seq
, GSI_NEW_STMT
);
916 /* Returns iterator at the start of the list of phi nodes of BB. */
919 gsi_start_phis (basic_block bb
)
921 gimple_seq
*pseq
= phi_nodes_ptr (bb
);
923 /* Adapted from gsi_start_1. */
926 i
.ptr
= gimple_seq_first (*pseq
);
928 i
.bb
= i
.ptr
? gimple_bb (i
.ptr
) : NULL
;