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"
29 #include "fold-const.h"
31 #include "hard-reg-set.h"
34 #include "dominance.h"
36 #include "basic-block.h"
37 #include "tree-ssa-alias.h"
38 #include "internal-fn.h"
40 #include "gimple-expr.h"
43 #include "gimple-iterator.h"
44 #include "gimple-ssa.h"
45 #include "plugin-api.h"
49 #include "tree-phinodes.h"
50 #include "ssa-iterators.h"
52 #include "value-prof.h"
55 /* Mark the statement STMT as modified, and update it. */
58 update_modified_stmt (gimple stmt
)
60 if (!ssa_operands_active (cfun
))
62 update_stmt_if_modified (stmt
);
66 /* Mark the statements in SEQ as modified, and update them. */
69 update_modified_stmts (gimple_seq seq
)
71 gimple_stmt_iterator gsi
;
73 if (!ssa_operands_active (cfun
))
75 for (gsi
= gsi_start (seq
); !gsi_end_p (gsi
); gsi_next (&gsi
))
76 update_stmt_if_modified (gsi_stmt (gsi
));
80 /* Set BB to be the basic block for all the statements in the list
81 starting at FIRST and LAST. */
84 update_bb_for_stmts (gimple_seq_node first
, gimple_seq_node last
,
89 for (n
= first
; n
; n
= n
->next
)
91 gimple_set_bb (n
, bb
);
97 /* Set the frequencies for the cgraph_edges for each of the calls
98 starting at FIRST for their new position within BB. */
101 update_call_edge_frequencies (gimple_seq_node first
, basic_block bb
)
103 struct cgraph_node
*cfun_node
= NULL
;
107 for (n
= first
; n
; n
= n
->next
)
108 if (is_gimple_call (n
))
110 struct cgraph_edge
*e
;
112 /* These function calls are expensive enough that we want
113 to avoid calling them if we never see any calls. */
114 if (cfun_node
== NULL
)
116 cfun_node
= cgraph_node::get (current_function_decl
);
117 bb_freq
= (compute_call_stmt_bb_frequency
118 (current_function_decl
, bb
));
121 e
= cfun_node
->get_edge (n
);
123 e
->frequency
= bb_freq
;
127 /* Insert the sequence delimited by nodes FIRST and LAST before
128 iterator I. M specifies how to update iterator I after insertion
129 (see enum gsi_iterator_update).
131 This routine assumes that there is a forward and backward path
132 between FIRST and LAST (i.e., they are linked in a doubly-linked
133 list). Additionally, if FIRST == LAST, this routine will properly
134 insert a single node. */
137 gsi_insert_seq_nodes_before (gimple_stmt_iterator
*i
,
138 gimple_seq_node first
,
139 gimple_seq_node last
,
140 enum gsi_iterator_update mode
)
143 gimple_seq_node cur
= i
->ptr
;
145 gcc_assert (!cur
|| cur
->prev
);
147 if ((bb
= gsi_bb (*i
)) != NULL
)
148 update_bb_for_stmts (first
, last
, bb
);
150 /* Link SEQ before CUR in the sequence. */
153 first
->prev
= cur
->prev
;
154 if (first
->prev
->next
)
155 first
->prev
->next
= first
;
157 gimple_seq_set_first (i
->seq
, first
);
163 gimple_seq_node itlast
= gimple_seq_last (*i
->seq
);
165 /* If CUR is NULL, we link at the end of the sequence (this case happens
166 when gsi_after_labels is called for a basic block that contains only
167 labels, so it returns an iterator after the end of the block, and
168 we need to insert before it; it might be cleaner to add a flag to the
169 iterator saying whether we are at the start or end of the list). */
173 first
->prev
= itlast
;
174 itlast
->next
= first
;
177 gimple_seq_set_first (i
->seq
, first
);
178 gimple_seq_set_last (i
->seq
, last
);
181 /* Update the iterator, if requested. */
185 case GSI_CONTINUE_LINKING
:
196 /* Inserts the sequence of statements SEQ before the statement pointed
197 by iterator I. MODE indicates what to do with the iterator after
198 insertion (see enum gsi_iterator_update).
200 This function does not scan for new operands. It is provided for
201 the use of the gimplifier, which manipulates statements for which
202 def/use information has not yet been constructed. Most callers
203 should use gsi_insert_seq_before. */
206 gsi_insert_seq_before_without_update (gimple_stmt_iterator
*i
, gimple_seq seq
,
207 enum gsi_iterator_update mode
)
209 gimple_seq_node first
, last
;
214 /* Don't allow inserting a sequence into itself. */
215 gcc_assert (seq
!= *i
->seq
);
217 first
= gimple_seq_first (seq
);
218 last
= gimple_seq_last (seq
);
220 /* Empty sequences need no work. */
223 gcc_assert (first
== last
);
227 gsi_insert_seq_nodes_before (i
, first
, last
, mode
);
231 /* Inserts the sequence of statements SEQ before the statement pointed
232 by iterator I. MODE indicates what to do with the iterator after
233 insertion (see enum gsi_iterator_update). Scan the statements in SEQ
237 gsi_insert_seq_before (gimple_stmt_iterator
*i
, gimple_seq seq
,
238 enum gsi_iterator_update mode
)
240 update_modified_stmts (seq
);
241 gsi_insert_seq_before_without_update (i
, seq
, mode
);
245 /* Insert the sequence delimited by nodes FIRST and LAST after
246 iterator I. M specifies how to update iterator I after insertion
247 (see enum gsi_iterator_update).
249 This routine assumes that there is a forward and backward path
250 between FIRST and LAST (i.e., they are linked in a doubly-linked
251 list). Additionally, if FIRST == LAST, this routine will properly
252 insert a single node. */
255 gsi_insert_seq_nodes_after (gimple_stmt_iterator
*i
,
256 gimple_seq_node first
,
257 gimple_seq_node last
,
258 enum gsi_iterator_update m
)
261 gimple_seq_node cur
= i
->ptr
;
263 gcc_assert (!cur
|| cur
->prev
);
265 /* If the iterator is inside a basic block, we need to update the
266 basic block information for all the nodes between FIRST and LAST. */
267 if ((bb
= gsi_bb (*i
)) != NULL
)
268 update_bb_for_stmts (first
, last
, bb
);
270 /* Link SEQ after CUR. */
273 last
->next
= cur
->next
;
276 last
->next
->prev
= last
;
279 gimple_seq_set_last (i
->seq
, last
);
285 gcc_assert (!gimple_seq_last (*i
->seq
));
287 gimple_seq_set_first (i
->seq
, first
);
288 gimple_seq_set_last (i
->seq
, last
);
291 /* Update the iterator, if requested. */
297 case GSI_CONTINUE_LINKING
:
309 /* Links sequence SEQ after the statement pointed-to by iterator I.
310 MODE is as in gsi_insert_after.
312 This function does not scan for new operands. It is provided for
313 the use of the gimplifier, which manipulates statements for which
314 def/use information has not yet been constructed. Most callers
315 should use gsi_insert_seq_after. */
318 gsi_insert_seq_after_without_update (gimple_stmt_iterator
*i
, gimple_seq seq
,
319 enum gsi_iterator_update mode
)
321 gimple_seq_node first
, last
;
326 /* Don't allow inserting a sequence into itself. */
327 gcc_assert (seq
!= *i
->seq
);
329 first
= gimple_seq_first (seq
);
330 last
= gimple_seq_last (seq
);
332 /* Empty sequences need no work. */
335 gcc_assert (first
== last
);
339 gsi_insert_seq_nodes_after (i
, first
, last
, mode
);
343 /* Links sequence SEQ after the statement pointed-to by iterator I.
344 MODE is as in gsi_insert_after. Scan the statements in SEQ
348 gsi_insert_seq_after (gimple_stmt_iterator
*i
, gimple_seq seq
,
349 enum gsi_iterator_update mode
)
351 update_modified_stmts (seq
);
352 gsi_insert_seq_after_without_update (i
, seq
, mode
);
356 /* Move all statements in the sequence after I to a new sequence.
357 Return this new sequence. */
360 gsi_split_seq_after (gimple_stmt_iterator i
)
362 gimple_seq_node cur
, next
;
363 gimple_seq
*pold_seq
, new_seq
;
367 /* How can we possibly split after the end, or before the beginning? */
368 gcc_assert (cur
&& cur
->next
);
373 gimple_seq_set_first (&new_seq
, next
);
374 gimple_seq_set_last (&new_seq
, gimple_seq_last (*pold_seq
));
375 gimple_seq_set_last (pold_seq
, cur
);
382 /* Set the statement to which GSI points to STMT. This only updates
383 the iterator and the gimple sequence, it doesn't do the bookkeeping
387 gsi_set_stmt (gimple_stmt_iterator
*gsi
, gimple stmt
)
389 gimple orig_stmt
= gsi_stmt (*gsi
);
392 stmt
->next
= next
= orig_stmt
->next
;
393 stmt
->prev
= prev
= orig_stmt
->prev
;
394 /* Note how we don't clear next/prev of orig_stmt. This is so that
395 copies of *GSI our callers might still hold (to orig_stmt)
396 can be advanced as if they too were replaced. */
400 gimple_seq_set_first (gsi
->seq
, stmt
);
404 gimple_seq_set_last (gsi
->seq
, stmt
);
410 /* Move all statements in the sequence before I to a new sequence.
411 Return this new sequence. I is set to the head of the new list. */
414 gsi_split_seq_before (gimple_stmt_iterator
*i
, gimple_seq
*pnew_seq
)
416 gimple_seq_node cur
, prev
;
421 /* How can we possibly split after the end? */
430 /* Set the limits on NEW_SEQ. */
431 gimple_seq_set_first (pnew_seq
, cur
);
432 gimple_seq_set_last (pnew_seq
, gimple_seq_last (old_seq
));
434 /* Cut OLD_SEQ before I. */
435 gimple_seq_set_last (&old_seq
, prev
);
441 /* Replace the statement pointed-to by GSI to STMT. If UPDATE_EH_INFO
442 is true, the exception handling information of the original
443 statement is moved to the new statement. Assignments must only be
444 replaced with assignments to the same LHS. Returns whether EH edge
445 cleanup is required. */
448 gsi_replace (gimple_stmt_iterator
*gsi
, gimple stmt
, bool update_eh_info
)
450 gimple orig_stmt
= gsi_stmt (*gsi
);
451 bool require_eh_edge_purge
= false;
453 if (stmt
== orig_stmt
)
456 gcc_assert (!gimple_has_lhs (orig_stmt
) || !gimple_has_lhs (stmt
)
457 || gimple_get_lhs (orig_stmt
) == gimple_get_lhs (stmt
));
459 gimple_set_location (stmt
, gimple_location (orig_stmt
));
460 gimple_set_bb (stmt
, gsi_bb (*gsi
));
462 /* Preserve EH region information from the original statement, if
463 requested by the caller. */
465 require_eh_edge_purge
= maybe_clean_or_replace_eh_stmt (orig_stmt
, stmt
);
467 gimple_duplicate_stmt_histograms (cfun
, stmt
, cfun
, orig_stmt
);
469 /* Free all the data flow information for ORIG_STMT. */
470 gimple_set_bb (orig_stmt
, NULL
);
471 gimple_remove_stmt_histograms (cfun
, orig_stmt
);
472 delink_stmt_imm_use (orig_stmt
);
474 gsi_set_stmt (gsi
, stmt
);
475 gimple_set_modified (stmt
, true);
476 update_modified_stmt (stmt
);
477 return require_eh_edge_purge
;
481 /* Replace the statement pointed-to by GSI with the sequence SEQ.
482 If UPDATE_EH_INFO is true, the exception handling information of
483 the original statement is moved to the last statement of the new
484 sequence. If the old statement is an assignment, then so must
485 be the last statement of the new sequence, and they must have the
489 gsi_replace_with_seq (gimple_stmt_iterator
*gsi
, gimple_seq seq
,
492 gimple_stmt_iterator seqi
;
494 if (gimple_seq_empty_p (seq
))
496 gsi_remove (gsi
, true);
499 seqi
= gsi_last (seq
);
500 last
= gsi_stmt (seqi
);
501 gsi_remove (&seqi
, false);
502 gsi_insert_seq_before (gsi
, seq
, GSI_SAME_STMT
);
503 gsi_replace (gsi
, last
, update_eh_info
);
507 /* Insert statement STMT before the statement pointed-to by iterator I.
508 M specifies how to update iterator I after insertion (see enum
509 gsi_iterator_update).
511 This function does not scan for new operands. It is provided for
512 the use of the gimplifier, which manipulates statements for which
513 def/use information has not yet been constructed. Most callers
514 should use gsi_insert_before. */
517 gsi_insert_before_without_update (gimple_stmt_iterator
*i
, gimple stmt
,
518 enum gsi_iterator_update m
)
520 gsi_insert_seq_nodes_before (i
, stmt
, stmt
, m
);
523 /* Insert statement STMT before the statement pointed-to by iterator I.
524 Update STMT's basic block and scan it for new operands. M
525 specifies how to update iterator I after insertion (see enum
526 gsi_iterator_update). */
529 gsi_insert_before (gimple_stmt_iterator
*i
, gimple stmt
,
530 enum gsi_iterator_update m
)
532 update_modified_stmt (stmt
);
533 gsi_insert_before_without_update (i
, stmt
, m
);
537 /* Insert statement STMT after the statement pointed-to by iterator I.
538 M specifies how to update iterator I after insertion (see enum
539 gsi_iterator_update).
541 This function does not scan for new operands. It is provided for
542 the use of the gimplifier, which manipulates statements for which
543 def/use information has not yet been constructed. Most callers
544 should use gsi_insert_after. */
547 gsi_insert_after_without_update (gimple_stmt_iterator
*i
, gimple stmt
,
548 enum gsi_iterator_update m
)
550 gsi_insert_seq_nodes_after (i
, stmt
, stmt
, m
);
554 /* Insert statement STMT after the statement pointed-to by iterator I.
555 Update STMT's basic block and scan it for new operands. M
556 specifies how to update iterator I after insertion (see enum
557 gsi_iterator_update). */
560 gsi_insert_after (gimple_stmt_iterator
*i
, gimple stmt
,
561 enum gsi_iterator_update m
)
563 update_modified_stmt (stmt
);
564 gsi_insert_after_without_update (i
, stmt
, m
);
568 /* Remove the current stmt from the sequence. The iterator is updated
569 to point to the next statement.
571 REMOVE_PERMANENTLY is true when the statement is going to be removed
572 from the IL and not reinserted elsewhere. In that case we remove the
573 statement pointed to by iterator I from the EH tables, and free its
574 operand caches. Otherwise we do not modify this information. Returns
575 true whether EH edge cleanup is required. */
578 gsi_remove (gimple_stmt_iterator
*i
, bool remove_permanently
)
580 gimple_seq_node cur
, next
, prev
;
581 gimple stmt
= gsi_stmt (*i
);
582 bool require_eh_edge_purge
= false;
584 if (gimple_code (stmt
) != GIMPLE_PHI
)
585 insert_debug_temps_for_defs (i
);
587 /* Free all the data flow information for STMT. */
588 gimple_set_bb (stmt
, NULL
);
589 delink_stmt_imm_use (stmt
);
590 gimple_set_modified (stmt
, true);
592 if (remove_permanently
)
594 require_eh_edge_purge
= remove_stmt_from_eh_lp (stmt
);
595 gimple_remove_stmt_histograms (cfun
, stmt
);
598 /* Update the iterator and re-wire the links in I->SEQ. */
602 /* See gsi_set_stmt for why we don't reset prev/next of STMT. */
605 /* Cur is not last. */
608 /* Cur is last but not first. */
609 gimple_seq_set_last (i
->seq
, prev
);
612 /* Cur is not first. */
620 return require_eh_edge_purge
;
624 /* Finds iterator for STMT. */
627 gsi_for_stmt (gimple stmt
)
629 gimple_stmt_iterator i
;
630 basic_block bb
= gimple_bb (stmt
);
632 if (gimple_code (stmt
) == GIMPLE_PHI
)
633 i
= gsi_start_phis (bb
);
635 i
= gsi_start_bb (bb
);
641 /* Finds iterator for PHI. */
644 gsi_for_phi (gphi
*phi
)
647 basic_block bb
= gimple_bb (phi
);
649 i
= gsi_start_phis (bb
);
655 /* Move the statement at FROM so it comes right after the statement at TO. */
658 gsi_move_after (gimple_stmt_iterator
*from
, gimple_stmt_iterator
*to
)
660 gimple stmt
= gsi_stmt (*from
);
661 gsi_remove (from
, false);
663 /* We must have GSI_NEW_STMT here, as gsi_move_after is sometimes used to
664 move statements to an empty block. */
665 gsi_insert_after (to
, stmt
, GSI_NEW_STMT
);
669 /* Move the statement at FROM so it comes right before the statement
673 gsi_move_before (gimple_stmt_iterator
*from
, gimple_stmt_iterator
*to
)
675 gimple stmt
= gsi_stmt (*from
);
676 gsi_remove (from
, false);
678 /* For consistency with gsi_move_after, it might be better to have
679 GSI_NEW_STMT here; however, that breaks several places that expect
680 that TO does not change. */
681 gsi_insert_before (to
, stmt
, GSI_SAME_STMT
);
685 /* Move the statement at FROM to the end of basic block BB. */
688 gsi_move_to_bb_end (gimple_stmt_iterator
*from
, basic_block bb
)
690 gimple_stmt_iterator last
= gsi_last_bb (bb
);
691 gcc_checking_assert (gsi_bb (last
) == bb
);
693 /* Have to check gsi_end_p because it could be an empty block. */
694 if (!gsi_end_p (last
) && is_ctrl_stmt (gsi_stmt (last
)))
695 gsi_move_before (from
, &last
);
697 gsi_move_after (from
, &last
);
701 /* Add STMT to the pending list of edge E. No actual insertion is
702 made until a call to gsi_commit_edge_inserts () is made. */
705 gsi_insert_on_edge (edge e
, gimple stmt
)
707 gimple_seq_add_stmt (&PENDING_STMT (e
), stmt
);
710 /* Add the sequence of statements SEQ to the pending list of edge E.
711 No actual insertion is made until a call to gsi_commit_edge_inserts
715 gsi_insert_seq_on_edge (edge e
, gimple_seq seq
)
717 gimple_seq_add_seq (&PENDING_STMT (e
), seq
);
720 /* Return a new iterator pointing to the first statement in sequence of
721 statements on edge E. Such statements need to be subsequently moved into a
722 basic block by calling gsi_commit_edge_inserts. */
725 gsi_start_edge (edge e
)
727 return gsi_start (PENDING_STMT (e
));
730 /* Insert the statement pointed-to by GSI into edge E. Every attempt
731 is made to place the statement in an existing basic block, but
732 sometimes that isn't possible. When it isn't possible, the edge is
733 split and the statement is added to the new block.
735 In all cases, the returned *GSI points to the correct location. The
736 return value is true if insertion should be done after the location,
737 or false if it should be done before the location. If a new basic block
738 has to be created, it is stored in *NEW_BB. */
741 gimple_find_edge_insert_loc (edge e
, gimple_stmt_iterator
*gsi
,
744 basic_block dest
, src
;
749 /* If the destination has one predecessor which has no PHI nodes,
750 insert there. Except for the exit block.
752 The requirement for no PHI nodes could be relaxed. Basically we
753 would have to examine the PHIs to prove that none of them used
754 the value set by the statement we want to insert on E. That
755 hardly seems worth the effort. */
757 if (single_pred_p (dest
)
758 && gimple_seq_empty_p (phi_nodes (dest
))
759 && dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
761 *gsi
= gsi_start_bb (dest
);
762 if (gsi_end_p (*gsi
))
765 /* Make sure we insert after any leading labels. */
766 tmp
= gsi_stmt (*gsi
);
767 while (gimple_code (tmp
) == GIMPLE_LABEL
)
770 if (gsi_end_p (*gsi
))
772 tmp
= gsi_stmt (*gsi
);
775 if (gsi_end_p (*gsi
))
777 *gsi
= gsi_last_bb (dest
);
784 /* If the source has one successor, the edge is not abnormal and
785 the last statement does not end a basic block, insert there.
786 Except for the entry block. */
788 if ((e
->flags
& EDGE_ABNORMAL
) == 0
789 && single_succ_p (src
)
790 && src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
792 *gsi
= gsi_last_bb (src
);
793 if (gsi_end_p (*gsi
))
796 tmp
= gsi_stmt (*gsi
);
797 if (!stmt_ends_bb_p (tmp
))
800 switch (gimple_code (tmp
))
810 /* Otherwise, create a new basic block, and split this edge. */
811 dest
= split_edge (e
);
814 e
= single_pred_edge (dest
);
819 /* Similar to gsi_insert_on_edge+gsi_commit_edge_inserts. If a new
820 block has to be created, it is returned. */
823 gsi_insert_on_edge_immediate (edge e
, gimple stmt
)
825 gimple_stmt_iterator gsi
;
826 basic_block new_bb
= NULL
;
829 gcc_assert (!PENDING_STMT (e
));
831 ins_after
= gimple_find_edge_insert_loc (e
, &gsi
, &new_bb
);
833 update_call_edge_frequencies (stmt
, gsi
.bb
);
836 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
838 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
843 /* Insert STMTS on edge E. If a new block has to be created, it
847 gsi_insert_seq_on_edge_immediate (edge e
, gimple_seq stmts
)
849 gimple_stmt_iterator gsi
;
850 basic_block new_bb
= NULL
;
853 gcc_assert (!PENDING_STMT (e
));
855 ins_after
= gimple_find_edge_insert_loc (e
, &gsi
, &new_bb
);
856 update_call_edge_frequencies (gimple_seq_first (stmts
), gsi
.bb
);
859 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
861 gsi_insert_seq_before (&gsi
, stmts
, GSI_NEW_STMT
);
866 /* This routine will commit all pending edge insertions, creating any new
867 basic blocks which are necessary. */
870 gsi_commit_edge_inserts (void)
876 gsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
)),
879 FOR_EACH_BB_FN (bb
, cfun
)
880 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
881 gsi_commit_one_edge_insert (e
, NULL
);
885 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
886 to this block, otherwise set it to NULL. */
889 gsi_commit_one_edge_insert (edge e
, basic_block
*new_bb
)
894 if (PENDING_STMT (e
))
896 gimple_stmt_iterator gsi
;
897 gimple_seq seq
= PENDING_STMT (e
);
900 PENDING_STMT (e
) = NULL
;
902 ins_after
= gimple_find_edge_insert_loc (e
, &gsi
, new_bb
);
903 update_call_edge_frequencies (gimple_seq_first (seq
), gsi
.bb
);
906 gsi_insert_seq_after (&gsi
, seq
, GSI_NEW_STMT
);
908 gsi_insert_seq_before (&gsi
, seq
, GSI_NEW_STMT
);
912 /* Returns iterator at the start of the list of phi nodes of BB. */
915 gsi_start_phis (basic_block bb
)
917 gimple_seq
*pseq
= phi_nodes_ptr (bb
);
919 /* Adapted from gsi_start_1. */
922 i
.ptr
= gimple_seq_first (*pseq
);
924 i
.bb
= i
.ptr
? gimple_bb (i
.ptr
) : NULL
;