1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This file contains low level functions to manipulate the CFG and analyze it
23 that are aware of the RTL intermediate language.
25 Available functionality:
26 - Basic CFG/RTL manipulation API documented in cfghooks.h
27 - CFG-aware instruction chain manipulation
28 delete_insn, delete_insn_chain
29 - Edge splitting and committing to edges
30 insert_insn_on_edge, commit_edge_insertions
31 - CFG updating after insn simplification
32 purge_dead_edges, purge_all_dead_edges
34 Functions not supposed for generic use:
35 - Infrastructure to determine quickly basic block for insn
36 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
37 - Edge redirection with updating and optimizing of insn chain
38 block_label, tidy_fallthru_edge, force_nonfallthru */
42 #include "coretypes.h"
46 #include "hard-reg-set.h"
47 #include "basic-block.h"
56 #include "insn-attr.h"
57 #include "insn-config.h"
58 #include "cfglayout.h"
63 #include "tree-pass.h"
66 static int can_delete_note_p (const_rtx
);
67 static int can_delete_label_p (const_rtx
);
68 static basic_block
rtl_split_edge (edge
);
69 static bool rtl_move_block_after (basic_block
, basic_block
);
70 static int rtl_verify_flow_info (void);
71 static basic_block
cfg_layout_split_block (basic_block
, void *);
72 static edge
cfg_layout_redirect_edge_and_branch (edge
, basic_block
);
73 static basic_block
cfg_layout_redirect_edge_and_branch_force (edge
, basic_block
);
74 static void cfg_layout_delete_block (basic_block
);
75 static void rtl_delete_block (basic_block
);
76 static basic_block
rtl_redirect_edge_and_branch_force (edge
, basic_block
);
77 static edge
rtl_redirect_edge_and_branch (edge
, basic_block
);
78 static basic_block
rtl_split_block (basic_block
, void *);
79 static void rtl_dump_bb (basic_block
, FILE *, int, int);
80 static int rtl_verify_flow_info_1 (void);
81 static void rtl_make_forwarder_block (edge
);
83 /* Return true if NOTE is not one of the ones that must be kept paired,
84 so that we may simply delete it. */
87 can_delete_note_p (const_rtx note
)
89 switch (NOTE_KIND (note
))
91 case NOTE_INSN_DELETED
:
92 case NOTE_INSN_BASIC_BLOCK
:
93 case NOTE_INSN_EPILOGUE_BEG
:
101 /* True if a given label can be deleted. */
104 can_delete_label_p (const_rtx label
)
106 return (!LABEL_PRESERVE_P (label
)
107 /* User declared labels must be preserved. */
108 && LABEL_NAME (label
) == 0
109 && !in_expr_list_p (forced_labels
, label
));
112 /* Delete INSN by patching it out. Return the next insn. */
115 delete_insn (rtx insn
)
117 rtx next
= NEXT_INSN (insn
);
119 bool really_delete
= true;
123 /* Some labels can't be directly removed from the INSN chain, as they
124 might be references via variables, constant pool etc.
125 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
126 if (! can_delete_label_p (insn
))
128 const char *name
= LABEL_NAME (insn
);
130 really_delete
= false;
131 PUT_CODE (insn
, NOTE
);
132 NOTE_KIND (insn
) = NOTE_INSN_DELETED_LABEL
;
133 NOTE_DELETED_LABEL_NAME (insn
) = name
;
136 remove_node_from_expr_list (insn
, &nonlocal_goto_handler_labels
);
141 /* If this insn has already been deleted, something is very wrong. */
142 gcc_assert (!INSN_DELETED_P (insn
));
144 INSN_DELETED_P (insn
) = 1;
147 /* If deleting a jump, decrement the use count of the label. Deleting
148 the label itself should happen in the normal course of block merging. */
151 if (JUMP_LABEL (insn
)
152 && LABEL_P (JUMP_LABEL (insn
)))
153 LABEL_NUSES (JUMP_LABEL (insn
))--;
155 /* If there are more targets, remove them too. */
157 = find_reg_note (insn
, REG_LABEL_TARGET
, NULL_RTX
)) != NULL_RTX
158 && LABEL_P (XEXP (note
, 0)))
160 LABEL_NUSES (XEXP (note
, 0))--;
161 remove_note (insn
, note
);
165 /* Also if deleting any insn that references a label as an operand. */
166 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, NULL_RTX
)) != NULL_RTX
167 && LABEL_P (XEXP (note
, 0)))
169 LABEL_NUSES (XEXP (note
, 0))--;
170 remove_note (insn
, note
);
173 if (JUMP_TABLE_DATA_P (insn
))
175 rtx pat
= PATTERN (insn
);
176 int diff_vec_p
= GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
;
177 int len
= XVECLEN (pat
, diff_vec_p
);
180 for (i
= 0; i
< len
; i
++)
182 rtx label
= XEXP (XVECEXP (pat
, diff_vec_p
, i
), 0);
184 /* When deleting code in bulk (e.g. removing many unreachable
185 blocks) we can delete a label that's a target of the vector
186 before deleting the vector itself. */
188 LABEL_NUSES (label
)--;
195 /* Like delete_insn but also purge dead edges from BB. */
198 delete_insn_and_edges (rtx insn
)
204 && BLOCK_FOR_INSN (insn
)
205 && BB_END (BLOCK_FOR_INSN (insn
)) == insn
)
207 x
= delete_insn (insn
);
209 purge_dead_edges (BLOCK_FOR_INSN (insn
));
213 /* Unlink a chain of insns between START and FINISH, leaving notes
214 that must be paired. If CLEAR_BB is true, we set bb field for
215 insns that cannot be removed to NULL. */
218 delete_insn_chain (rtx start
, rtx finish
, bool clear_bb
)
222 /* Unchain the insns one by one. It would be quicker to delete all of these
223 with a single unchaining, rather than one at a time, but we need to keep
227 next
= NEXT_INSN (start
);
228 if (NOTE_P (start
) && !can_delete_note_p (start
))
231 next
= delete_insn (start
);
233 if (clear_bb
&& !INSN_DELETED_P (start
))
234 set_block_for_insn (start
, NULL
);
242 /* Create a new basic block consisting of the instructions between HEAD and END
243 inclusive. This function is designed to allow fast BB construction - reuses
244 the note and basic block struct in BB_NOTE, if any and do not grow
245 BASIC_BLOCK chain and should be used directly only by CFG construction code.
246 END can be NULL in to create new empty basic block before HEAD. Both END
247 and HEAD can be NULL to create basic block at the end of INSN chain.
248 AFTER is the basic block we should be put after. */
251 create_basic_block_structure (rtx head
, rtx end
, rtx bb_note
, basic_block after
)
256 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
259 /* If we found an existing note, thread it back onto the chain. */
267 after
= PREV_INSN (head
);
271 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
272 reorder_insns_nobb (bb_note
, bb_note
, after
);
276 /* Otherwise we must create a note and a basic block structure. */
280 init_rtl_bb_info (bb
);
283 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
284 else if (LABEL_P (head
) && end
)
286 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
292 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
298 NOTE_BASIC_BLOCK (bb_note
) = bb
;
301 /* Always include the bb note in the block. */
302 if (NEXT_INSN (end
) == bb_note
)
307 bb
->index
= last_basic_block
++;
308 bb
->flags
= BB_NEW
| BB_RTL
;
309 link_block (bb
, after
);
310 SET_BASIC_BLOCK (bb
->index
, bb
);
311 df_bb_refs_record (bb
->index
, false);
312 update_bb_for_insn (bb
);
313 BB_SET_PARTITION (bb
, BB_UNPARTITIONED
);
315 /* Tag the block so that we know it has been used when considering
316 other basic block notes. */
322 /* Create new basic block consisting of instructions in between HEAD and END
323 and place it to the BB chain after block AFTER. END can be NULL in to
324 create new empty basic block before HEAD. Both END and HEAD can be NULL to
325 create basic block at the end of INSN chain. */
328 rtl_create_basic_block (void *headp
, void *endp
, basic_block after
)
330 rtx head
= (rtx
) headp
, end
= (rtx
) endp
;
333 /* Grow the basic block array if needed. */
334 if ((size_t) last_basic_block
>= VEC_length (basic_block
, basic_block_info
))
336 size_t new_size
= last_basic_block
+ (last_basic_block
+ 3) / 4;
337 VEC_safe_grow_cleared (basic_block
, gc
, basic_block_info
, new_size
);
342 bb
= create_basic_block_structure (head
, end
, NULL
, after
);
348 cfg_layout_create_basic_block (void *head
, void *end
, basic_block after
)
350 basic_block newbb
= rtl_create_basic_block (head
, end
, after
);
355 /* Delete the insns in a (non-live) block. We physically delete every
356 non-deleted-note insn, and update the flow graph appropriately.
358 Return nonzero if we deleted an exception handler. */
360 /* ??? Preserving all such notes strikes me as wrong. It would be nice
361 to post-process the stream to remove empty blocks, loops, ranges, etc. */
364 rtl_delete_block (basic_block b
)
368 /* If the head of this block is a CODE_LABEL, then it might be the
369 label for an exception handler which can't be reached. We need
370 to remove the label from the exception_handler_label list. */
373 end
= get_last_bb_insn (b
);
375 /* Selectively delete the entire chain. */
377 delete_insn_chain (insn
, end
, true);
381 fprintf (dump_file
, "deleting block %d\n", b
->index
);
382 df_bb_delete (b
->index
);
385 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
388 compute_bb_for_insn (void)
394 rtx end
= BB_END (bb
);
397 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
399 BLOCK_FOR_INSN (insn
) = bb
;
406 /* Release the basic_block_for_insn array. */
409 free_bb_for_insn (void)
412 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
413 if (!BARRIER_P (insn
))
414 BLOCK_FOR_INSN (insn
) = NULL
;
419 rest_of_pass_free_cfg (void)
422 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
423 valid at that point so it would be too late to call df_analyze. */
424 if (optimize
> 0 && flag_delayed_branch
)
432 struct rtl_opt_pass pass_free_cfg
=
438 rest_of_pass_free_cfg
, /* execute */
441 0, /* static_pass_number */
443 0, /* properties_required */
444 0, /* properties_provided */
445 PROP_cfg
, /* properties_destroyed */
446 0, /* todo_flags_start */
447 0, /* todo_flags_finish */
451 /* Return RTX to emit after when we want to emit code on the entry of function. */
453 entry_of_function (void)
455 return (n_basic_blocks
> NUM_FIXED_BLOCKS
?
456 BB_HEAD (ENTRY_BLOCK_PTR
->next_bb
) : get_insns ());
459 /* Emit INSN at the entry point of the function, ensuring that it is only
460 executed once per function. */
462 emit_insn_at_entry (rtx insn
)
464 edge_iterator ei
= ei_start (ENTRY_BLOCK_PTR
->succs
);
465 edge e
= ei_safe_edge (ei
);
466 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
468 insert_insn_on_edge (insn
, e
);
469 commit_edge_insertions ();
472 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
473 (or BARRIER if found) and notify df of the bb change.
474 The insn chain range is inclusive
475 (i.e. both BEGIN and END will be updated. */
478 update_bb_for_insn_chain (rtx begin
, rtx end
, basic_block bb
)
482 end
= NEXT_INSN (end
);
483 for (insn
= begin
; insn
!= end
; insn
= NEXT_INSN (insn
))
484 if (!BARRIER_P (insn
))
485 df_insn_change_bb (insn
, bb
);
488 /* Update BLOCK_FOR_INSN of insns in BB to BB,
489 and notify df of the change. */
492 update_bb_for_insn (basic_block bb
)
494 update_bb_for_insn_chain (BB_HEAD (bb
), BB_END (bb
), bb
);
498 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
499 note associated with the BLOCK. */
502 first_insn_after_basic_block_note (basic_block block
)
506 /* Get the first instruction in the block. */
507 insn
= BB_HEAD (block
);
509 if (insn
== NULL_RTX
)
512 insn
= NEXT_INSN (insn
);
513 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
515 return NEXT_INSN (insn
);
518 /* Creates a new basic block just after basic block B by splitting
519 everything after specified instruction I. */
522 rtl_split_block (basic_block bb
, void *insnp
)
525 rtx insn
= (rtx
) insnp
;
531 insn
= first_insn_after_basic_block_note (bb
);
534 insn
= PREV_INSN (insn
);
536 insn
= get_last_insn ();
539 /* We probably should check type of the insn so that we do not create
540 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
542 if (insn
== BB_END (bb
))
543 emit_note_after (NOTE_INSN_DELETED
, insn
);
545 /* Create the new basic block. */
546 new_bb
= create_basic_block (NEXT_INSN (insn
), BB_END (bb
), bb
);
547 BB_COPY_PARTITION (new_bb
, bb
);
550 /* Redirect the outgoing edges. */
551 new_bb
->succs
= bb
->succs
;
553 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
556 /* The new block starts off being dirty. */
557 df_set_bb_dirty (bb
);
561 /* Blocks A and B are to be merged into a single block A. The insns
562 are already contiguous. */
565 rtl_merge_blocks (basic_block a
, basic_block b
)
567 rtx b_head
= BB_HEAD (b
), b_end
= BB_END (b
), a_end
= BB_END (a
);
568 rtx del_first
= NULL_RTX
, del_last
= NULL_RTX
;
572 fprintf (dump_file
, "merging block %d into block %d\n", b
->index
, a
->index
);
574 /* If there was a CODE_LABEL beginning B, delete it. */
575 if (LABEL_P (b_head
))
577 /* Detect basic blocks with nothing but a label. This can happen
578 in particular at the end of a function. */
582 del_first
= del_last
= b_head
;
583 b_head
= NEXT_INSN (b_head
);
586 /* Delete the basic block note and handle blocks containing just that
588 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
596 b_head
= NEXT_INSN (b_head
);
599 /* If there was a jump out of A, delete it. */
604 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
606 || NOTE_INSN_BASIC_BLOCK_P (prev
)
607 || prev
== BB_HEAD (a
))
613 /* If this was a conditional jump, we need to also delete
614 the insn that set cc0. */
615 if (only_sets_cc0_p (prev
))
619 prev
= prev_nonnote_insn (prev
);
626 a_end
= PREV_INSN (del_first
);
628 else if (BARRIER_P (NEXT_INSN (a_end
)))
629 del_first
= NEXT_INSN (a_end
);
631 /* Delete everything marked above as well as crap that might be
632 hanging out between the two blocks. */
634 delete_insn_chain (del_first
, del_last
, true);
636 /* Reassociate the insns of B with A. */
639 update_bb_for_insn_chain (a_end
, b_end
, a
);
644 df_bb_delete (b
->index
);
649 /* Return true when block A and B can be merged. */
652 rtl_can_merge_blocks (basic_block a
, basic_block b
)
654 /* If we are partitioning hot/cold basic blocks, we don't want to
655 mess up unconditional or indirect jumps that cross between hot
658 Basic block partitioning may result in some jumps that appear to
659 be optimizable (or blocks that appear to be mergeable), but which really
660 must be left untouched (they are required to make it safely across
661 partition boundaries). See the comments at the top of
662 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
664 if (BB_PARTITION (a
) != BB_PARTITION (b
))
667 /* There must be exactly one edge in between the blocks. */
668 return (single_succ_p (a
)
669 && single_succ (a
) == b
672 /* Must be simple edge. */
673 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
675 && a
!= ENTRY_BLOCK_PTR
&& b
!= EXIT_BLOCK_PTR
676 /* If the jump insn has side effects,
677 we can't kill the edge. */
678 && (!JUMP_P (BB_END (a
))
680 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
683 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
687 block_label (basic_block block
)
689 if (block
== EXIT_BLOCK_PTR
)
692 if (!LABEL_P (BB_HEAD (block
)))
694 BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
697 return BB_HEAD (block
);
700 /* Attempt to perform edge redirection by replacing possibly complex jump
701 instruction by unconditional jump or removing jump completely. This can
702 apply only if all edges now point to the same block. The parameters and
703 return values are equivalent to redirect_edge_and_branch. */
706 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
708 basic_block src
= e
->src
;
709 rtx insn
= BB_END (src
), kill_from
;
713 /* If we are partitioning hot/cold basic blocks, we don't want to
714 mess up unconditional or indirect jumps that cross between hot
717 Basic block partitioning may result in some jumps that appear to
718 be optimizable (or blocks that appear to be mergeable), but which really
719 must be left untouched (they are required to make it safely across
720 partition boundaries). See the comments at the top of
721 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
723 if (find_reg_note (insn
, REG_CROSSING_JUMP
, NULL_RTX
)
724 || BB_PARTITION (src
) != BB_PARTITION (target
))
727 /* We can replace or remove a complex jump only when we have exactly
728 two edges. Also, if we have exactly one outgoing edge, we can
730 if (EDGE_COUNT (src
->succs
) >= 3
731 /* Verify that all targets will be TARGET. Specifically, the
732 edge that is not E must also go to TARGET. */
733 || (EDGE_COUNT (src
->succs
) == 2
734 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
737 if (!onlyjump_p (insn
))
739 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
742 /* Avoid removing branch with side effects. */
743 set
= single_set (insn
);
744 if (!set
|| side_effects_p (set
))
747 /* In case we zap a conditional jump, we'll need to kill
748 the cc0 setter too. */
751 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
))
752 && only_sets_cc0_p (PREV_INSN (insn
)))
753 kill_from
= PREV_INSN (insn
);
756 /* See if we can create the fallthru edge. */
757 if (in_cfglayout
|| can_fallthru (src
, target
))
760 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
763 /* Selectively unlink whole insn chain. */
766 rtx insn
= src
->il
.rtl
->footer
;
768 delete_insn_chain (kill_from
, BB_END (src
), false);
770 /* Remove barriers but keep jumptables. */
773 if (BARRIER_P (insn
))
775 if (PREV_INSN (insn
))
776 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
778 src
->il
.rtl
->footer
= NEXT_INSN (insn
);
779 if (NEXT_INSN (insn
))
780 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
784 insn
= NEXT_INSN (insn
);
788 delete_insn_chain (kill_from
, PREV_INSN (BB_HEAD (target
)),
792 /* If this already is simplejump, redirect it. */
793 else if (simplejump_p (insn
))
795 if (e
->dest
== target
)
798 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
799 INSN_UID (insn
), e
->dest
->index
, target
->index
);
800 if (!redirect_jump (insn
, block_label (target
), 0))
802 gcc_assert (target
== EXIT_BLOCK_PTR
);
807 /* Cannot do anything for target exit block. */
808 else if (target
== EXIT_BLOCK_PTR
)
811 /* Or replace possibly complicated jump insn by simple jump insn. */
814 rtx target_label
= block_label (target
);
815 rtx barrier
, label
, table
;
817 emit_jump_insn_after_noloc (gen_jump (target_label
), insn
);
818 JUMP_LABEL (BB_END (src
)) = target_label
;
819 LABEL_NUSES (target_label
)++;
821 fprintf (dump_file
, "Replacing insn %i by jump %i\n",
822 INSN_UID (insn
), INSN_UID (BB_END (src
)));
825 delete_insn_chain (kill_from
, insn
, false);
827 /* Recognize a tablejump that we are converting to a
828 simple jump and remove its associated CODE_LABEL
829 and ADDR_VEC or ADDR_DIFF_VEC. */
830 if (tablejump_p (insn
, &label
, &table
))
831 delete_insn_chain (label
, table
, false);
833 barrier
= next_nonnote_insn (BB_END (src
));
834 if (!barrier
|| !BARRIER_P (barrier
))
835 emit_barrier_after (BB_END (src
));
838 if (barrier
!= NEXT_INSN (BB_END (src
)))
840 /* Move the jump before barrier so that the notes
841 which originally were or were created before jump table are
842 inside the basic block. */
843 rtx new_insn
= BB_END (src
);
845 update_bb_for_insn_chain (NEXT_INSN (BB_END (src
)),
846 PREV_INSN (barrier
), src
);
848 NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
849 PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
851 NEXT_INSN (new_insn
) = barrier
;
852 NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
854 PREV_INSN (new_insn
) = PREV_INSN (barrier
);
855 PREV_INSN (barrier
) = new_insn
;
860 /* Keep only one edge out and set proper flags. */
861 if (!single_succ_p (src
))
863 gcc_assert (single_succ_p (src
));
865 e
= single_succ_edge (src
);
867 e
->flags
= EDGE_FALLTHRU
;
871 e
->probability
= REG_BR_PROB_BASE
;
872 e
->count
= src
->count
;
874 if (e
->dest
!= target
)
875 redirect_edge_succ (e
, target
);
879 /* Subroutine of redirect_branch_edge that tries to patch the jump
880 instruction INSN so that it reaches block NEW. Do this
881 only when it originally reached block OLD. Return true if this
882 worked or the original target wasn't OLD, return false if redirection
886 patch_jump_insn (rtx insn
, rtx old_label
, basic_block new_bb
)
889 /* Recognize a tablejump and adjust all matching cases. */
890 if (tablejump_p (insn
, NULL
, &tmp
))
894 rtx new_label
= block_label (new_bb
);
896 if (new_bb
== EXIT_BLOCK_PTR
)
898 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
899 vec
= XVEC (PATTERN (tmp
), 0);
901 vec
= XVEC (PATTERN (tmp
), 1);
903 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
904 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
906 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
907 --LABEL_NUSES (old_label
);
908 ++LABEL_NUSES (new_label
);
911 /* Handle casesi dispatch insns. */
912 if ((tmp
= single_set (insn
)) != NULL
913 && SET_DEST (tmp
) == pc_rtx
914 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
915 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
916 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
918 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
920 --LABEL_NUSES (old_label
);
921 ++LABEL_NUSES (new_label
);
926 /* ?? We may play the games with moving the named labels from
927 one basic block to the other in case only one computed_jump is
929 if (computed_jump_p (insn
)
930 /* A return instruction can't be redirected. */
931 || returnjump_p (insn
))
934 if (!currently_expanding_to_rtl
|| JUMP_LABEL (insn
) == old_label
)
936 /* If the insn doesn't go where we think, we're confused. */
937 gcc_assert (JUMP_LABEL (insn
) == old_label
);
939 /* If the substitution doesn't succeed, die. This can happen
940 if the back end emitted unrecognizable instructions or if
941 target is exit block on some arches. */
942 if (!redirect_jump (insn
, block_label (new_bb
), 0))
944 gcc_assert (new_bb
== EXIT_BLOCK_PTR
);
953 /* Redirect edge representing branch of (un)conditional jump or tablejump,
956 redirect_branch_edge (edge e
, basic_block target
)
958 rtx old_label
= BB_HEAD (e
->dest
);
959 basic_block src
= e
->src
;
960 rtx insn
= BB_END (src
);
962 /* We can only redirect non-fallthru edges of jump insn. */
963 if (e
->flags
& EDGE_FALLTHRU
)
965 else if (!JUMP_P (insn
) && !currently_expanding_to_rtl
)
968 if (!currently_expanding_to_rtl
)
970 if (!patch_jump_insn (insn
, old_label
, target
))
974 /* When expanding this BB might actually contain multiple
975 jumps (i.e. not yet split by find_many_sub_basic_blocks).
976 Redirect all of those that match our label. */
977 for (insn
= BB_HEAD (src
); insn
!= NEXT_INSN (BB_END (src
));
978 insn
= NEXT_INSN (insn
))
979 if (JUMP_P (insn
) && !patch_jump_insn (insn
, old_label
, target
))
983 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
984 e
->src
->index
, e
->dest
->index
, target
->index
);
986 if (e
->dest
!= target
)
987 e
= redirect_edge_succ_nodup (e
, target
);
992 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
993 expense of adding new instructions or reordering basic blocks.
995 Function can be also called with edge destination equivalent to the TARGET.
996 Then it should try the simplifications and do nothing if none is possible.
998 Return edge representing the branch if transformation succeeded. Return NULL
1000 We still return NULL in case E already destinated TARGET and we didn't
1001 managed to simplify instruction stream. */
1004 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
1007 basic_block src
= e
->src
;
1009 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1012 if (e
->dest
== target
)
1015 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
1017 df_set_bb_dirty (src
);
1021 ret
= redirect_branch_edge (e
, target
);
1025 df_set_bb_dirty (src
);
1029 /* Like force_nonfallthru below, but additionally performs redirection
1030 Used by redirect_edge_and_branch_force. */
1033 force_nonfallthru_and_redirect (edge e
, basic_block target
)
1035 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
1038 int abnormal_edge_flags
= 0;
1041 /* In the case the last instruction is conditional jump to the next
1042 instruction, first redirect the jump itself and then continue
1043 by creating a basic block afterwards to redirect fallthru edge. */
1044 if (e
->src
!= ENTRY_BLOCK_PTR
&& e
->dest
!= EXIT_BLOCK_PTR
1045 && any_condjump_p (BB_END (e
->src
))
1046 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1049 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1052 redirected
= redirect_jump (BB_END (e
->src
), block_label (target
), 0);
1053 gcc_assert (redirected
);
1055 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1058 int prob
= INTVAL (XEXP (note
, 0));
1060 b
->probability
= prob
;
1061 b
->count
= e
->count
* prob
/ REG_BR_PROB_BASE
;
1062 e
->probability
-= e
->probability
;
1063 e
->count
-= b
->count
;
1064 if (e
->probability
< 0)
1071 if (e
->flags
& EDGE_ABNORMAL
)
1073 /* Irritating special case - fallthru edge to the same block as abnormal
1075 We can't redirect abnormal edge, but we still can split the fallthru
1076 one and create separate abnormal edge to original destination.
1077 This allows bb-reorder to make such edge non-fallthru. */
1078 gcc_assert (e
->dest
== target
);
1079 abnormal_edge_flags
= e
->flags
& ~(EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
);
1080 e
->flags
&= EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
;
1084 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1085 if (e
->src
== ENTRY_BLOCK_PTR
)
1087 /* We can't redirect the entry block. Create an empty block
1088 at the start of the function which we use to add the new
1094 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
, ENTRY_BLOCK_PTR
);
1096 /* Change the existing edge's source to be the new block, and add
1097 a new edge from the entry block to the new block. */
1099 for (ei
= ei_start (ENTRY_BLOCK_PTR
->succs
); (tmp
= ei_safe_edge (ei
)); )
1103 VEC_unordered_remove (edge
, ENTRY_BLOCK_PTR
->succs
, ei
.index
);
1113 VEC_safe_push (edge
, gc
, bb
->succs
, e
);
1114 make_single_succ_edge (ENTRY_BLOCK_PTR
, bb
, EDGE_FALLTHRU
);
1118 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
)
1120 /* Create the new structures. */
1122 /* If the old block ended with a tablejump, skip its table
1123 by searching forward from there. Otherwise start searching
1124 forward from the last instruction of the old block. */
1125 if (!tablejump_p (BB_END (e
->src
), NULL
, ¬e
))
1126 note
= BB_END (e
->src
);
1127 note
= NEXT_INSN (note
);
1129 jump_block
= create_basic_block (note
, NULL
, e
->src
);
1130 jump_block
->count
= e
->count
;
1131 jump_block
->frequency
= EDGE_FREQUENCY (e
);
1132 jump_block
->loop_depth
= target
->loop_depth
;
1134 /* Make sure new block ends up in correct hot/cold section. */
1136 BB_COPY_PARTITION (jump_block
, e
->src
);
1137 if (flag_reorder_blocks_and_partition
1138 && targetm
.have_named_sections
1139 && JUMP_P (BB_END (jump_block
))
1140 && !any_condjump_p (BB_END (jump_block
))
1141 && (EDGE_SUCC (jump_block
, 0)->flags
& EDGE_CROSSING
))
1142 add_reg_note (BB_END (jump_block
), REG_CROSSING_JUMP
, NULL_RTX
);
1145 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1146 new_edge
->probability
= e
->probability
;
1147 new_edge
->count
= e
->count
;
1149 /* Redirect old edge. */
1150 redirect_edge_pred (e
, jump_block
);
1151 e
->probability
= REG_BR_PROB_BASE
;
1153 new_bb
= jump_block
;
1156 jump_block
= e
->src
;
1158 if (e
->goto_locus
&& e
->goto_block
== NULL
)
1159 loc
= e
->goto_locus
;
1162 e
->flags
&= ~EDGE_FALLTHRU
;
1163 if (target
== EXIT_BLOCK_PTR
)
1166 emit_jump_insn_after_setloc (gen_return (), BB_END (jump_block
), loc
);
1173 rtx label
= block_label (target
);
1174 emit_jump_insn_after_setloc (gen_jump (label
), BB_END (jump_block
), loc
);
1175 JUMP_LABEL (BB_END (jump_block
)) = label
;
1176 LABEL_NUSES (label
)++;
1179 emit_barrier_after (BB_END (jump_block
));
1180 redirect_edge_succ_nodup (e
, target
);
1182 if (abnormal_edge_flags
)
1183 make_edge (src
, target
, abnormal_edge_flags
);
1185 df_mark_solutions_dirty ();
1189 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1190 (and possibly create new basic block) to make edge non-fallthru.
1191 Return newly created BB or NULL if none. */
1194 force_nonfallthru (edge e
)
1196 return force_nonfallthru_and_redirect (e
, e
->dest
);
1199 /* Redirect edge even at the expense of creating new jump insn or
1200 basic block. Return new basic block if created, NULL otherwise.
1201 Conversion must be possible. */
1204 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1206 if (redirect_edge_and_branch (e
, target
)
1207 || e
->dest
== target
)
1210 /* In case the edge redirection failed, try to force it to be non-fallthru
1211 and redirect newly created simplejump. */
1212 df_set_bb_dirty (e
->src
);
1213 return force_nonfallthru_and_redirect (e
, target
);
1216 /* The given edge should potentially be a fallthru edge. If that is in
1217 fact true, delete the jump and barriers that are in the way. */
1220 rtl_tidy_fallthru_edge (edge e
)
1223 basic_block b
= e
->src
, c
= b
->next_bb
;
1225 /* ??? In a late-running flow pass, other folks may have deleted basic
1226 blocks by nopping out blocks, leaving multiple BARRIERs between here
1227 and the target label. They ought to be chastised and fixed.
1229 We can also wind up with a sequence of undeletable labels between
1230 one block and the next.
1232 So search through a sequence of barriers, labels, and notes for
1233 the head of block C and assert that we really do fall through. */
1235 for (q
= NEXT_INSN (BB_END (b
)); q
!= BB_HEAD (c
); q
= NEXT_INSN (q
))
1239 /* Remove what will soon cease being the jump insn from the source block.
1240 If block B consisted only of this single jump, turn it into a deleted
1245 && (any_uncondjump_p (q
)
1246 || single_succ_p (b
)))
1249 /* If this was a conditional jump, we need to also delete
1250 the insn that set cc0. */
1251 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1258 /* Selectively unlink the sequence. */
1259 if (q
!= PREV_INSN (BB_HEAD (c
)))
1260 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1262 e
->flags
|= EDGE_FALLTHRU
;
1265 /* Should move basic block BB after basic block AFTER. NIY. */
1268 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1269 basic_block after ATTRIBUTE_UNUSED
)
1274 /* Split a (typically critical) edge. Return the new block.
1275 The edge must not be abnormal.
1277 ??? The code generally expects to be called on critical edges.
1278 The case of a block ending in an unconditional jump to a
1279 block with multiple predecessors is not handled optimally. */
1282 rtl_split_edge (edge edge_in
)
1287 /* Abnormal edges cannot be split. */
1288 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1290 /* We are going to place the new block in front of edge destination.
1291 Avoid existence of fallthru predecessors. */
1292 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1297 FOR_EACH_EDGE (e
, ei
, edge_in
->dest
->preds
)
1298 if (e
->flags
& EDGE_FALLTHRU
)
1302 force_nonfallthru (e
);
1305 /* Create the basic block note. */
1306 if (edge_in
->dest
!= EXIT_BLOCK_PTR
)
1307 before
= BB_HEAD (edge_in
->dest
);
1311 /* If this is a fall through edge to the exit block, the blocks might be
1312 not adjacent, and the right place is the after the source. */
1313 if (edge_in
->flags
& EDGE_FALLTHRU
&& edge_in
->dest
== EXIT_BLOCK_PTR
)
1315 before
= NEXT_INSN (BB_END (edge_in
->src
));
1316 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1317 BB_COPY_PARTITION (bb
, edge_in
->src
);
1321 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1322 /* ??? Why not edge_in->dest->prev_bb here? */
1323 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1326 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1328 /* For non-fallthru edges, we must adjust the predecessor's
1329 jump instruction to target our new block. */
1330 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1332 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1333 gcc_assert (redirected
);
1336 redirect_edge_succ (edge_in
, bb
);
1341 /* Queue instructions for insertion on an edge between two basic blocks.
1342 The new instructions and basic blocks (if any) will not appear in the
1343 CFG until commit_edge_insertions is called. */
1346 insert_insn_on_edge (rtx pattern
, edge e
)
1348 /* We cannot insert instructions on an abnormal critical edge.
1349 It will be easier to find the culprit if we die now. */
1350 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1352 if (e
->insns
.r
== NULL_RTX
)
1355 push_to_sequence (e
->insns
.r
);
1357 emit_insn (pattern
);
1359 e
->insns
.r
= get_insns ();
1363 /* Update the CFG for the instructions queued on edge E. */
1366 commit_one_edge_insertion (edge e
)
1368 rtx before
= NULL_RTX
, after
= NULL_RTX
, insns
, tmp
, last
;
1369 basic_block bb
= NULL
;
1371 /* Pull the insns off the edge now since the edge might go away. */
1373 e
->insns
.r
= NULL_RTX
;
1375 if (!before
&& !after
)
1377 /* Figure out where to put these things. If the destination has
1378 one predecessor, insert there. Except for the exit block. */
1379 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR
)
1383 /* Get the location correct wrt a code label, and "nice" wrt
1384 a basic block note, and before everything else. */
1387 tmp
= NEXT_INSN (tmp
);
1388 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1389 tmp
= NEXT_INSN (tmp
);
1390 if (tmp
== BB_HEAD (bb
))
1393 after
= PREV_INSN (tmp
);
1395 after
= get_last_insn ();
1398 /* If the source has one successor and the edge is not abnormal,
1399 insert there. Except for the entry block. */
1400 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1401 && single_succ_p (e
->src
)
1402 && e
->src
!= ENTRY_BLOCK_PTR
)
1406 /* It is possible to have a non-simple jump here. Consider a target
1407 where some forms of unconditional jumps clobber a register. This
1408 happens on the fr30 for example.
1410 We know this block has a single successor, so we can just emit
1411 the queued insns before the jump. */
1412 if (JUMP_P (BB_END (bb
)))
1413 before
= BB_END (bb
);
1416 /* We'd better be fallthru, or we've lost track of
1418 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1420 after
= BB_END (bb
);
1423 /* Otherwise we must split the edge. */
1426 bb
= split_edge (e
);
1427 after
= BB_END (bb
);
1429 if (flag_reorder_blocks_and_partition
1430 && targetm
.have_named_sections
1431 && e
->src
!= ENTRY_BLOCK_PTR
1432 && BB_PARTITION (e
->src
) == BB_COLD_PARTITION
1433 && !(e
->flags
& EDGE_CROSSING
))
1435 rtx bb_note
, cur_insn
;
1438 for (cur_insn
= BB_HEAD (bb
); cur_insn
!= NEXT_INSN (BB_END (bb
));
1439 cur_insn
= NEXT_INSN (cur_insn
))
1440 if (NOTE_INSN_BASIC_BLOCK_P (cur_insn
))
1446 if (JUMP_P (BB_END (bb
))
1447 && !any_condjump_p (BB_END (bb
))
1448 && (single_succ_edge (bb
)->flags
& EDGE_CROSSING
))
1449 add_reg_note (BB_END (bb
), REG_CROSSING_JUMP
, NULL_RTX
);
1454 /* Now that we've found the spot, do the insertion. */
1458 emit_insn_before_noloc (insns
, before
, bb
);
1459 last
= prev_nonnote_insn (before
);
1462 last
= emit_insn_after_noloc (insns
, after
, bb
);
1464 if (returnjump_p (last
))
1466 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1467 This is not currently a problem because this only happens
1468 for the (single) epilogue, which already has a fallthru edge
1471 e
= single_succ_edge (bb
);
1472 gcc_assert (e
->dest
== EXIT_BLOCK_PTR
1473 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
1475 e
->flags
&= ~EDGE_FALLTHRU
;
1476 emit_barrier_after (last
);
1479 delete_insn (before
);
1482 gcc_assert (!JUMP_P (last
));
1484 /* Mark the basic block for find_many_sub_basic_blocks. */
1485 if (current_ir_type () != IR_RTL_CFGLAYOUT
)
1489 /* Update the CFG for all queued instructions. */
1492 commit_edge_insertions (void)
1496 bool changed
= false;
1498 #ifdef ENABLE_CHECKING
1499 verify_flow_info ();
1502 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
1507 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1511 commit_one_edge_insertion (e
);
1518 /* In the old rtl CFG API, it was OK to insert control flow on an
1519 edge, apparently? In cfglayout mode, this will *not* work, and
1520 the caller is responsible for making sure that control flow is
1521 valid at all times. */
1522 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
1525 blocks
= sbitmap_alloc (last_basic_block
);
1526 sbitmap_zero (blocks
);
1530 SET_BIT (blocks
, bb
->index
);
1531 /* Check for forgotten bb->aux values before commit_edge_insertions
1533 gcc_assert (bb
->aux
== &bb
->aux
);
1536 find_many_sub_basic_blocks (blocks
);
1537 sbitmap_free (blocks
);
1541 /* Print out RTL-specific basic block information (live information
1542 at start and end). */
1545 rtl_dump_bb (basic_block bb
, FILE *outf
, int indent
, int flags ATTRIBUTE_UNUSED
)
1551 s_indent
= (char *) alloca ((size_t) indent
+ 1);
1552 memset (s_indent
, ' ', (size_t) indent
);
1553 s_indent
[indent
] = '\0';
1557 df_dump_top (bb
, outf
);
1561 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
)); insn
!= last
;
1562 insn
= NEXT_INSN (insn
))
1563 print_rtl_single (outf
, insn
);
1567 df_dump_bottom (bb
, outf
);
1573 /* Like print_rtl, but also print out live information for the start of each
1577 print_rtl_with_bb (FILE *outf
, const_rtx rtx_first
)
1581 fprintf (outf
, "(nil)\n");
1584 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
1585 int max_uid
= get_max_uid ();
1586 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
1587 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
1588 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
1593 df_dump_start (outf
);
1595 FOR_EACH_BB_REVERSE (bb
)
1599 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
1600 end
[INSN_UID (BB_END (bb
))] = bb
;
1601 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
1603 enum bb_state state
= IN_MULTIPLE_BB
;
1605 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
1607 in_bb_p
[INSN_UID (x
)] = state
;
1609 if (x
== BB_END (bb
))
1614 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
1617 if ((bb
= start
[INSN_UID (tmp_rtx
)]) != NULL
)
1622 fprintf (outf
, ";; Start of basic block (");
1623 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1624 fprintf (outf
, " %d", e
->src
->index
);
1625 fprintf (outf
, ") -> %d\n", bb
->index
);
1629 df_dump_top (bb
, outf
);
1632 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1634 fputs (";; Pred edge ", outf
);
1635 dump_edge_info (outf
, e
, 0);
1640 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
1641 && !NOTE_P (tmp_rtx
)
1642 && !BARRIER_P (tmp_rtx
))
1643 fprintf (outf
, ";; Insn is not within a basic block\n");
1644 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
1645 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
1647 did_output
= print_rtl_single (outf
, tmp_rtx
);
1649 if ((bb
= end
[INSN_UID (tmp_rtx
)]) != NULL
)
1654 fprintf (outf
, ";; End of basic block %d -> (", bb
->index
);
1655 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1656 fprintf (outf
, " %d", e
->dest
->index
);
1657 fprintf (outf
, ")\n");
1661 df_dump_bottom (bb
, outf
);
1665 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1667 fputs (";; Succ edge ", outf
);
1668 dump_edge_info (outf
, e
, 1);
1681 if (crtl
->epilogue_delay_list
!= 0)
1683 fprintf (outf
, "\n;; Insns in epilogue delay list:\n\n");
1684 for (tmp_rtx
= crtl
->epilogue_delay_list
; tmp_rtx
!= 0;
1685 tmp_rtx
= XEXP (tmp_rtx
, 1))
1686 print_rtl_single (outf
, XEXP (tmp_rtx
, 0));
1691 update_br_prob_note (basic_block bb
)
1694 if (!JUMP_P (BB_END (bb
)))
1696 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
1697 if (!note
|| INTVAL (XEXP (note
, 0)) == BRANCH_EDGE (bb
)->probability
)
1699 XEXP (note
, 0) = GEN_INT (BRANCH_EDGE (bb
)->probability
);
1702 /* Get the last insn associated with block BB (that includes barriers and
1703 tablejumps after BB). */
1705 get_last_bb_insn (basic_block bb
)
1708 rtx end
= BB_END (bb
);
1710 /* Include any jump table following the basic block. */
1711 if (tablejump_p (end
, NULL
, &tmp
))
1714 /* Include any barriers that may follow the basic block. */
1715 tmp
= next_nonnote_insn_bb (end
);
1716 while (tmp
&& BARRIER_P (tmp
))
1719 tmp
= next_nonnote_insn_bb (end
);
1725 /* Verify the CFG and RTL consistency common for both underlying RTL and
1728 Currently it does following checks:
1730 - overlapping of basic blocks
1731 - insns with wrong BLOCK_FOR_INSN pointers
1732 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1733 - tails of basic blocks (ensure that boundary is necessary)
1734 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1735 and NOTE_INSN_BASIC_BLOCK
1736 - verify that no fall_thru edge crosses hot/cold partition boundaries
1737 - verify that there are no pending RTL branch predictions
1739 In future it can be extended check a lot of other stuff as well
1740 (reachability of basic blocks, life information, etc. etc.). */
1743 rtl_verify_flow_info_1 (void)
1749 /* Check the general integrity of the basic blocks. */
1750 FOR_EACH_BB_REVERSE (bb
)
1754 if (!(bb
->flags
& BB_RTL
))
1756 error ("BB_RTL flag not set for block %d", bb
->index
);
1760 FOR_BB_INSNS (bb
, insn
)
1761 if (BLOCK_FOR_INSN (insn
) != bb
)
1763 error ("insn %d basic block pointer is %d, should be %d",
1765 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
1770 for (insn
= bb
->il
.rtl
->header
; insn
; insn
= NEXT_INSN (insn
))
1771 if (!BARRIER_P (insn
)
1772 && BLOCK_FOR_INSN (insn
) != NULL
)
1774 error ("insn %d in header of bb %d has non-NULL basic block",
1775 INSN_UID (insn
), bb
->index
);
1778 for (insn
= bb
->il
.rtl
->footer
; insn
; insn
= NEXT_INSN (insn
))
1779 if (!BARRIER_P (insn
)
1780 && BLOCK_FOR_INSN (insn
) != NULL
)
1782 error ("insn %d in footer of bb %d has non-NULL basic block",
1783 INSN_UID (insn
), bb
->index
);
1788 /* Now check the basic blocks (boundaries etc.) */
1789 FOR_EACH_BB_REVERSE (bb
)
1791 int n_fallthru
= 0, n_eh
= 0, n_call
= 0, n_abnormal
= 0, n_branch
= 0;
1792 edge e
, fallthru
= NULL
;
1796 if (JUMP_P (BB_END (bb
))
1797 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
1798 && EDGE_COUNT (bb
->succs
) >= 2
1799 && any_condjump_p (BB_END (bb
)))
1801 if (INTVAL (XEXP (note
, 0)) != BRANCH_EDGE (bb
)->probability
1802 && profile_status
!= PROFILE_ABSENT
)
1804 error ("verify_flow_info: REG_BR_PROB does not match cfg %wi %i",
1805 INTVAL (XEXP (note
, 0)), BRANCH_EDGE (bb
)->probability
);
1809 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1811 if (e
->flags
& EDGE_FALLTHRU
)
1813 n_fallthru
++, fallthru
= e
;
1814 if ((e
->flags
& EDGE_CROSSING
)
1815 || (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
1816 && e
->src
!= ENTRY_BLOCK_PTR
1817 && e
->dest
!= EXIT_BLOCK_PTR
))
1819 error ("fallthru edge crosses section boundary (bb %i)",
1825 if ((e
->flags
& ~(EDGE_DFS_BACK
1827 | EDGE_IRREDUCIBLE_LOOP
1829 | EDGE_CROSSING
)) == 0)
1832 if (e
->flags
& EDGE_ABNORMAL_CALL
)
1835 if (e
->flags
& EDGE_EH
)
1837 else if (e
->flags
& EDGE_ABNORMAL
)
1841 if (n_eh
&& GET_CODE (PATTERN (BB_END (bb
))) != RESX
1842 && !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
1844 error ("missing REG_EH_REGION note in the end of bb %i", bb
->index
);
1848 && (!JUMP_P (BB_END (bb
))
1849 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
1850 || any_condjump_p (BB_END (bb
))))))
1852 error ("too many outgoing branch edges from bb %i", bb
->index
);
1855 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
1857 error ("fallthru edge after unconditional jump %i", bb
->index
);
1860 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
1862 error ("wrong amount of branch edges after unconditional jump %i", bb
->index
);
1865 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
1866 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
1868 error ("wrong amount of branch edges after conditional jump %i",
1872 if (n_call
&& !CALL_P (BB_END (bb
)))
1874 error ("call edges for non-call insn in bb %i", bb
->index
);
1878 && (!CALL_P (BB_END (bb
)) && n_call
!= n_abnormal
)
1879 && (!JUMP_P (BB_END (bb
))
1880 || any_condjump_p (BB_END (bb
))
1881 || any_uncondjump_p (BB_END (bb
))))
1883 error ("abnormal edges for no purpose in bb %i", bb
->index
);
1887 for (x
= BB_HEAD (bb
); x
!= NEXT_INSN (BB_END (bb
)); x
= NEXT_INSN (x
))
1888 /* We may have a barrier inside a basic block before dead code
1889 elimination. There is no BLOCK_FOR_INSN field in a barrier. */
1890 if (!BARRIER_P (x
) && BLOCK_FOR_INSN (x
) != bb
)
1893 if (! BLOCK_FOR_INSN (x
))
1895 ("insn %d inside basic block %d but block_for_insn is NULL",
1896 INSN_UID (x
), bb
->index
);
1899 ("insn %d inside basic block %d but block_for_insn is %i",
1900 INSN_UID (x
), bb
->index
, BLOCK_FOR_INSN (x
)->index
);
1905 /* OK pointers are correct. Now check the header of basic
1906 block. It ought to contain optional CODE_LABEL followed
1907 by NOTE_BASIC_BLOCK. */
1911 if (BB_END (bb
) == x
)
1913 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1921 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
1923 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1928 if (BB_END (bb
) == x
)
1929 /* Do checks for empty blocks here. */
1932 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
1934 if (NOTE_INSN_BASIC_BLOCK_P (x
))
1936 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
1937 INSN_UID (x
), bb
->index
);
1941 if (x
== BB_END (bb
))
1944 if (control_flow_insn_p (x
))
1946 error ("in basic block %d:", bb
->index
);
1947 fatal_insn ("flow control insn inside a basic block", x
);
1956 /* Verify the CFG and RTL consistency common for both underlying RTL and
1959 Currently it does following checks:
1960 - all checks of rtl_verify_flow_info_1
1961 - test head/end pointers
1962 - check that all insns are in the basic blocks
1963 (except the switch handling code, barriers and notes)
1964 - check that all returns are followed by barriers
1965 - check that all fallthru edge points to the adjacent blocks. */
1968 rtl_verify_flow_info (void)
1971 int err
= rtl_verify_flow_info_1 ();
1973 rtx last_head
= get_last_insn ();
1974 basic_block
*bb_info
;
1976 const rtx rtx_first
= get_insns ();
1977 basic_block last_bb_seen
= ENTRY_BLOCK_PTR
, curr_bb
= NULL
;
1978 const int max_uid
= get_max_uid ();
1980 bb_info
= XCNEWVEC (basic_block
, max_uid
);
1982 FOR_EACH_BB_REVERSE (bb
)
1986 rtx head
= BB_HEAD (bb
);
1987 rtx end
= BB_END (bb
);
1989 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1991 /* Verify the end of the basic block is in the INSN chain. */
1995 /* And that the code outside of basic blocks has NULL bb field. */
1997 && BLOCK_FOR_INSN (x
) != NULL
)
1999 error ("insn %d outside of basic blocks has non-NULL bb field",
2007 error ("end insn %d for block %d not found in the insn stream",
2008 INSN_UID (end
), bb
->index
);
2012 /* Work backwards from the end to the head of the basic block
2013 to verify the head is in the RTL chain. */
2014 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2016 /* While walking over the insn chain, verify insns appear
2017 in only one basic block. */
2018 if (bb_info
[INSN_UID (x
)] != NULL
)
2020 error ("insn %d is in multiple basic blocks (%d and %d)",
2021 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2025 bb_info
[INSN_UID (x
)] = bb
;
2032 error ("head insn %d for block %d not found in the insn stream",
2033 INSN_UID (head
), bb
->index
);
2037 last_head
= PREV_INSN (x
);
2039 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2040 if (e
->flags
& EDGE_FALLTHRU
)
2046 /* Ensure existence of barrier in BB with no fallthru edges. */
2047 for (insn
= NEXT_INSN (BB_END (bb
)); ; insn
= NEXT_INSN (insn
))
2049 if (!insn
|| NOTE_INSN_BASIC_BLOCK_P (insn
))
2051 error ("missing barrier after block %i", bb
->index
);
2055 if (BARRIER_P (insn
))
2059 else if (e
->src
!= ENTRY_BLOCK_PTR
2060 && e
->dest
!= EXIT_BLOCK_PTR
)
2064 if (e
->src
->next_bb
!= e
->dest
)
2067 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2068 e
->src
->index
, e
->dest
->index
);
2072 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
2073 insn
= NEXT_INSN (insn
))
2074 if (BARRIER_P (insn
) || INSN_P (insn
))
2076 error ("verify_flow_info: Incorrect fallthru %i->%i",
2077 e
->src
->index
, e
->dest
->index
);
2078 fatal_insn ("wrong insn in the fallthru edge", insn
);
2084 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2086 /* Check that the code before the first basic block has NULL
2089 && BLOCK_FOR_INSN (x
) != NULL
)
2091 error ("insn %d outside of basic blocks has non-NULL bb field",
2099 last_bb_seen
= ENTRY_BLOCK_PTR
;
2101 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2103 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2105 bb
= NOTE_BASIC_BLOCK (x
);
2108 if (bb
!= last_bb_seen
->next_bb
)
2109 internal_error ("basic blocks not laid down consecutively");
2111 curr_bb
= last_bb_seen
= bb
;
2116 switch (GET_CODE (x
))
2123 /* An addr_vec is placed outside any basic block. */
2125 && JUMP_TABLE_DATA_P (NEXT_INSN (x
)))
2128 /* But in any case, non-deletable labels can appear anywhere. */
2132 fatal_insn ("insn outside basic block", x
);
2137 && returnjump_p (x
) && ! condjump_p (x
)
2138 && ! (next_nonnote_insn (x
) && BARRIER_P (next_nonnote_insn (x
))))
2139 fatal_insn ("return not followed by barrier", x
);
2140 if (curr_bb
&& x
== BB_END (curr_bb
))
2144 if (num_bb_notes
!= n_basic_blocks
- NUM_FIXED_BLOCKS
)
2146 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2147 num_bb_notes
, n_basic_blocks
);
2152 /* Assume that the preceding pass has possibly eliminated jump instructions
2153 or converted the unconditional jumps. Eliminate the edges from CFG.
2154 Return true if any edges are eliminated. */
2157 purge_dead_edges (basic_block bb
)
2160 rtx insn
= BB_END (bb
), note
;
2161 bool purged
= false;
2165 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2166 if (NONJUMP_INSN_P (insn
)
2167 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
2171 if (! may_trap_p (PATTERN (insn
))
2172 || ((eqnote
= find_reg_equal_equiv_note (insn
))
2173 && ! may_trap_p (XEXP (eqnote
, 0))))
2174 remove_note (insn
, note
);
2177 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
2178 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
2180 /* There are three types of edges we need to handle correctly here: EH
2181 edges, abnormal call EH edges, and abnormal call non-EH edges. The
2182 latter can appear when nonlocal gotos are used. */
2183 if (e
->flags
& EDGE_EH
)
2185 if (can_throw_internal (BB_END (bb
))
2186 /* If this is a call edge, verify that this is a call insn. */
2187 && (! (e
->flags
& EDGE_ABNORMAL_CALL
)
2188 || CALL_P (BB_END (bb
))))
2194 else if (e
->flags
& EDGE_ABNORMAL_CALL
)
2196 if (CALL_P (BB_END (bb
))
2197 && (! (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
))
2198 || INTVAL (XEXP (note
, 0)) >= 0))
2211 df_set_bb_dirty (bb
);
2221 /* We do care only about conditional jumps and simplejumps. */
2222 if (!any_condjump_p (insn
)
2223 && !returnjump_p (insn
)
2224 && !simplejump_p (insn
))
2227 /* Branch probability/prediction notes are defined only for
2228 condjumps. We've possibly turned condjump into simplejump. */
2229 if (simplejump_p (insn
))
2231 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2233 remove_note (insn
, note
);
2234 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
2235 remove_note (insn
, note
);
2238 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
2240 /* Avoid abnormal flags to leak from computed jumps turned
2241 into simplejumps. */
2243 e
->flags
&= ~EDGE_ABNORMAL
;
2245 /* See if this edge is one we should keep. */
2246 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
2247 /* A conditional jump can fall through into the next
2248 block, so we should keep the edge. */
2253 else if (e
->dest
!= EXIT_BLOCK_PTR
2254 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
2255 /* If the destination block is the target of the jump,
2261 else if (e
->dest
== EXIT_BLOCK_PTR
&& returnjump_p (insn
))
2262 /* If the destination block is the exit block, and this
2263 instruction is a return, then keep the edge. */
2268 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
2269 /* Keep the edges that correspond to exceptions thrown by
2270 this instruction and rematerialize the EDGE_ABNORMAL
2271 flag we just cleared above. */
2273 e
->flags
|= EDGE_ABNORMAL
;
2278 /* We do not need this edge. */
2279 df_set_bb_dirty (bb
);
2284 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
2288 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
2293 /* Redistribute probabilities. */
2294 if (single_succ_p (bb
))
2296 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
2297 single_succ_edge (bb
)->count
= bb
->count
;
2301 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2305 b
= BRANCH_EDGE (bb
);
2306 f
= FALLTHRU_EDGE (bb
);
2307 b
->probability
= INTVAL (XEXP (note
, 0));
2308 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
2309 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
2310 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
2315 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
2317 /* First, there should not be any EH or ABCALL edges resulting
2318 from non-local gotos and the like. If there were, we shouldn't
2319 have created the sibcall in the first place. Second, there
2320 should of course never have been a fallthru edge. */
2321 gcc_assert (single_succ_p (bb
));
2322 gcc_assert (single_succ_edge (bb
)->flags
2323 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
2328 /* If we don't see a jump insn, we don't know exactly why the block would
2329 have been broken at this point. Look for a simple, non-fallthru edge,
2330 as these are only created by conditional branches. If we find such an
2331 edge we know that there used to be a jump here and can then safely
2332 remove all non-fallthru edges. */
2334 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2335 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
2344 /* Remove all but the fake and fallthru edges. The fake edge may be
2345 the only successor for this block in the case of noreturn
2347 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
2349 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
2351 df_set_bb_dirty (bb
);
2359 gcc_assert (single_succ_p (bb
));
2361 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
2362 single_succ_edge (bb
)->count
= bb
->count
;
2365 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
2370 /* Search all basic blocks for potentially dead edges and purge them. Return
2371 true if some edge has been eliminated. */
2374 purge_all_dead_edges (void)
2381 bool purged_here
= purge_dead_edges (bb
);
2383 purged
|= purged_here
;
2389 /* Same as split_block but update cfg_layout structures. */
2392 cfg_layout_split_block (basic_block bb
, void *insnp
)
2394 rtx insn
= (rtx
) insnp
;
2395 basic_block new_bb
= rtl_split_block (bb
, insn
);
2397 new_bb
->il
.rtl
->footer
= bb
->il
.rtl
->footer
;
2398 bb
->il
.rtl
->footer
= NULL
;
2403 /* Redirect Edge to DEST. */
2405 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
2407 basic_block src
= e
->src
;
2410 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
2413 if (e
->dest
== dest
)
2416 if (e
->src
!= ENTRY_BLOCK_PTR
2417 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
2419 df_set_bb_dirty (src
);
2423 if (e
->src
== ENTRY_BLOCK_PTR
2424 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
2427 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
2428 e
->src
->index
, dest
->index
);
2430 df_set_bb_dirty (e
->src
);
2431 redirect_edge_succ (e
, dest
);
2435 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
2436 in the case the basic block appears to be in sequence. Avoid this
2439 if (e
->flags
& EDGE_FALLTHRU
)
2441 /* Redirect any branch edges unified with the fallthru one. */
2442 if (JUMP_P (BB_END (src
))
2443 && label_is_jump_target_p (BB_HEAD (e
->dest
),
2449 fprintf (dump_file
, "Fallthru edge unified with branch "
2450 "%i->%i redirected to %i\n",
2451 e
->src
->index
, e
->dest
->index
, dest
->index
);
2452 e
->flags
&= ~EDGE_FALLTHRU
;
2453 redirected
= redirect_branch_edge (e
, dest
);
2454 gcc_assert (redirected
);
2455 e
->flags
|= EDGE_FALLTHRU
;
2456 df_set_bb_dirty (e
->src
);
2459 /* In case we are redirecting fallthru edge to the branch edge
2460 of conditional jump, remove it. */
2461 if (EDGE_COUNT (src
->succs
) == 2)
2463 /* Find the edge that is different from E. */
2464 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
2467 && any_condjump_p (BB_END (src
))
2468 && onlyjump_p (BB_END (src
)))
2469 delete_insn (BB_END (src
));
2471 ret
= redirect_edge_succ_nodup (e
, dest
);
2473 fprintf (dump_file
, "Fallthru edge %i->%i redirected to %i\n",
2474 e
->src
->index
, e
->dest
->index
, dest
->index
);
2477 ret
= redirect_branch_edge (e
, dest
);
2479 /* We don't want simplejumps in the insn stream during cfglayout. */
2480 gcc_assert (!simplejump_p (BB_END (src
)));
2482 df_set_bb_dirty (src
);
2486 /* Simple wrapper as we always can redirect fallthru edges. */
2488 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
2490 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
2492 gcc_assert (redirected
);
2496 /* Same as delete_basic_block but update cfg_layout structures. */
2499 cfg_layout_delete_block (basic_block bb
)
2501 rtx insn
, next
, prev
= PREV_INSN (BB_HEAD (bb
)), *to
, remaints
;
2503 if (bb
->il
.rtl
->header
)
2505 next
= BB_HEAD (bb
);
2507 NEXT_INSN (prev
) = bb
->il
.rtl
->header
;
2509 set_first_insn (bb
->il
.rtl
->header
);
2510 PREV_INSN (bb
->il
.rtl
->header
) = prev
;
2511 insn
= bb
->il
.rtl
->header
;
2512 while (NEXT_INSN (insn
))
2513 insn
= NEXT_INSN (insn
);
2514 NEXT_INSN (insn
) = next
;
2515 PREV_INSN (next
) = insn
;
2517 next
= NEXT_INSN (BB_END (bb
));
2518 if (bb
->il
.rtl
->footer
)
2520 insn
= bb
->il
.rtl
->footer
;
2523 if (BARRIER_P (insn
))
2525 if (PREV_INSN (insn
))
2526 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
2528 bb
->il
.rtl
->footer
= NEXT_INSN (insn
);
2529 if (NEXT_INSN (insn
))
2530 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
2534 insn
= NEXT_INSN (insn
);
2536 if (bb
->il
.rtl
->footer
)
2539 NEXT_INSN (insn
) = bb
->il
.rtl
->footer
;
2540 PREV_INSN (bb
->il
.rtl
->footer
) = insn
;
2541 while (NEXT_INSN (insn
))
2542 insn
= NEXT_INSN (insn
);
2543 NEXT_INSN (insn
) = next
;
2545 PREV_INSN (next
) = insn
;
2547 set_last_insn (insn
);
2550 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
2551 to
= &bb
->next_bb
->il
.rtl
->header
;
2553 to
= &cfg_layout_function_footer
;
2555 rtl_delete_block (bb
);
2558 prev
= NEXT_INSN (prev
);
2560 prev
= get_insns ();
2562 next
= PREV_INSN (next
);
2564 next
= get_last_insn ();
2566 if (next
&& NEXT_INSN (next
) != prev
)
2568 remaints
= unlink_insn_chain (prev
, next
);
2570 while (NEXT_INSN (insn
))
2571 insn
= NEXT_INSN (insn
);
2572 NEXT_INSN (insn
) = *to
;
2574 PREV_INSN (*to
) = insn
;
2579 /* Return true when blocks A and B can be safely merged. */
2582 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
2584 /* If we are partitioning hot/cold basic blocks, we don't want to
2585 mess up unconditional or indirect jumps that cross between hot
2588 Basic block partitioning may result in some jumps that appear to
2589 be optimizable (or blocks that appear to be mergeable), but which really
2590 must be left untouched (they are required to make it safely across
2591 partition boundaries). See the comments at the top of
2592 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
2594 if (BB_PARTITION (a
) != BB_PARTITION (b
))
2597 /* There must be exactly one edge in between the blocks. */
2598 return (single_succ_p (a
)
2599 && single_succ (a
) == b
2600 && single_pred_p (b
) == 1
2602 /* Must be simple edge. */
2603 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
2604 && a
!= ENTRY_BLOCK_PTR
&& b
!= EXIT_BLOCK_PTR
2605 /* If the jump insn has side effects, we can't kill the edge.
2606 When not optimizing, try_redirect_by_replacing_jump will
2607 not allow us to redirect an edge by replacing a table jump. */
2608 && (!JUMP_P (BB_END (a
))
2609 || ((!optimize
|| reload_completed
)
2610 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
2613 /* Merge block A and B. The blocks must be mergeable. */
2616 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
2618 #ifdef ENABLE_CHECKING
2619 gcc_assert (cfg_layout_can_merge_blocks_p (a
, b
));
2623 fprintf (dump_file
, "merging block %d into block %d\n", b
->index
, a
->index
);
2625 /* If there was a CODE_LABEL beginning B, delete it. */
2626 if (LABEL_P (BB_HEAD (b
)))
2628 delete_insn (BB_HEAD (b
));
2631 /* We should have fallthru edge in a, or we can do dummy redirection to get
2633 if (JUMP_P (BB_END (a
)))
2634 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
2635 gcc_assert (!JUMP_P (BB_END (a
)));
2637 /* When not optimizing and the edge is the only place in RTL which holds
2638 some unique locus, emit a nop with that locus in between. */
2639 if (!optimize
&& EDGE_SUCC (a
, 0)->goto_locus
)
2641 rtx insn
= BB_END (a
), end
= PREV_INSN (BB_HEAD (a
));
2642 int goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
2644 while (insn
!= end
&& (!INSN_P (insn
) || INSN_LOCATOR (insn
) == 0))
2645 insn
= PREV_INSN (insn
);
2646 if (insn
!= end
&& locator_eq (INSN_LOCATOR (insn
), goto_locus
))
2651 end
= NEXT_INSN (BB_END (b
));
2652 while (insn
!= end
&& !INSN_P (insn
))
2653 insn
= NEXT_INSN (insn
);
2654 if (insn
!= end
&& INSN_LOCATOR (insn
) != 0
2655 && locator_eq (INSN_LOCATOR (insn
), goto_locus
))
2660 BB_END (a
) = emit_insn_after_noloc (gen_nop (), BB_END (a
), a
);
2661 INSN_LOCATOR (BB_END (a
)) = goto_locus
;
2665 /* Possible line number notes should appear in between. */
2666 if (b
->il
.rtl
->header
)
2668 rtx first
= BB_END (a
), last
;
2670 last
= emit_insn_after_noloc (b
->il
.rtl
->header
, BB_END (a
), a
);
2671 delete_insn_chain (NEXT_INSN (first
), last
, false);
2672 b
->il
.rtl
->header
= NULL
;
2675 /* In the case basic blocks are not adjacent, move them around. */
2676 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
2678 rtx first
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
2680 emit_insn_after_noloc (first
, BB_END (a
), a
);
2681 /* Skip possible DELETED_LABEL insn. */
2682 if (!NOTE_INSN_BASIC_BLOCK_P (first
))
2683 first
= NEXT_INSN (first
);
2684 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (first
));
2687 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
2688 We need to explicitly call. */
2689 update_bb_for_insn_chain (NEXT_INSN (first
),
2693 delete_insn (first
);
2695 /* Otherwise just re-associate the instructions. */
2700 update_bb_for_insn_chain (BB_HEAD (b
), BB_END (b
), a
);
2703 /* Skip possible DELETED_LABEL insn. */
2704 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
2705 insn
= NEXT_INSN (insn
);
2706 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
2708 BB_END (a
) = BB_END (b
);
2712 df_bb_delete (b
->index
);
2714 /* Possible tablejumps and barriers should appear after the block. */
2715 if (b
->il
.rtl
->footer
)
2717 if (!a
->il
.rtl
->footer
)
2718 a
->il
.rtl
->footer
= b
->il
.rtl
->footer
;
2721 rtx last
= a
->il
.rtl
->footer
;
2723 while (NEXT_INSN (last
))
2724 last
= NEXT_INSN (last
);
2725 NEXT_INSN (last
) = b
->il
.rtl
->footer
;
2726 PREV_INSN (b
->il
.rtl
->footer
) = last
;
2728 b
->il
.rtl
->footer
= NULL
;
2732 fprintf (dump_file
, "Merged blocks %d and %d.\n",
2733 a
->index
, b
->index
);
2739 cfg_layout_split_edge (edge e
)
2741 basic_block new_bb
=
2742 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR
2743 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
2746 if (e
->dest
== EXIT_BLOCK_PTR
)
2747 BB_COPY_PARTITION (new_bb
, e
->src
);
2749 BB_COPY_PARTITION (new_bb
, e
->dest
);
2750 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
2751 redirect_edge_and_branch_force (e
, new_bb
);
2756 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
2759 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
2763 /* Return 1 if BB ends with a call, possibly followed by some
2764 instructions that must stay with the call, 0 otherwise. */
2767 rtl_block_ends_with_call_p (basic_block bb
)
2769 rtx insn
= BB_END (bb
);
2771 while (!CALL_P (insn
)
2772 && insn
!= BB_HEAD (bb
)
2773 && (keep_with_call_p (insn
)
2775 insn
= PREV_INSN (insn
);
2776 return (CALL_P (insn
));
2779 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
2782 rtl_block_ends_with_condjump_p (const_basic_block bb
)
2784 return any_condjump_p (BB_END (bb
));
2787 /* Return true if we need to add fake edge to exit.
2788 Helper function for rtl_flow_call_edges_add. */
2791 need_fake_edge_p (const_rtx insn
)
2797 && !SIBLING_CALL_P (insn
)
2798 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
2799 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
2802 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
2803 && MEM_VOLATILE_P (PATTERN (insn
)))
2804 || (GET_CODE (PATTERN (insn
)) == PARALLEL
2805 && asm_noperands (insn
) != -1
2806 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
2807 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
2810 /* Add fake edges to the function exit for any non constant and non noreturn
2811 calls, volatile inline assembly in the bitmap of blocks specified by
2812 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
2815 The goal is to expose cases in which entering a basic block does not imply
2816 that all subsequent instructions must be executed. */
2819 rtl_flow_call_edges_add (sbitmap blocks
)
2822 int blocks_split
= 0;
2823 int last_bb
= last_basic_block
;
2824 bool check_last_block
= false;
2826 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
2830 check_last_block
= true;
2832 check_last_block
= TEST_BIT (blocks
, EXIT_BLOCK_PTR
->prev_bb
->index
);
2834 /* In the last basic block, before epilogue generation, there will be
2835 a fallthru edge to EXIT. Special care is required if the last insn
2836 of the last basic block is a call because make_edge folds duplicate
2837 edges, which would result in the fallthru edge also being marked
2838 fake, which would result in the fallthru edge being removed by
2839 remove_fake_edges, which would result in an invalid CFG.
2841 Moreover, we can't elide the outgoing fake edge, since the block
2842 profiler needs to take this into account in order to solve the minimal
2843 spanning tree in the case that the call doesn't return.
2845 Handle this by adding a dummy instruction in a new last basic block. */
2846 if (check_last_block
)
2848 basic_block bb
= EXIT_BLOCK_PTR
->prev_bb
;
2849 rtx insn
= BB_END (bb
);
2851 /* Back up past insns that must be kept in the same block as a call. */
2852 while (insn
!= BB_HEAD (bb
)
2853 && keep_with_call_p (insn
))
2854 insn
= PREV_INSN (insn
);
2856 if (need_fake_edge_p (insn
))
2860 e
= find_edge (bb
, EXIT_BLOCK_PTR
);
2863 insert_insn_on_edge (gen_use (const0_rtx
), e
);
2864 commit_edge_insertions ();
2869 /* Now add fake edges to the function exit for any non constant
2870 calls since there is no way that we can determine if they will
2873 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
2875 basic_block bb
= BASIC_BLOCK (i
);
2882 if (blocks
&& !TEST_BIT (blocks
, i
))
2885 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
2887 prev_insn
= PREV_INSN (insn
);
2888 if (need_fake_edge_p (insn
))
2891 rtx split_at_insn
= insn
;
2893 /* Don't split the block between a call and an insn that should
2894 remain in the same block as the call. */
2896 while (split_at_insn
!= BB_END (bb
)
2897 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
2898 split_at_insn
= NEXT_INSN (split_at_insn
);
2900 /* The handling above of the final block before the epilogue
2901 should be enough to verify that there is no edge to the exit
2902 block in CFG already. Calling make_edge in such case would
2903 cause us to mark that edge as fake and remove it later. */
2905 #ifdef ENABLE_CHECKING
2906 if (split_at_insn
== BB_END (bb
))
2908 e
= find_edge (bb
, EXIT_BLOCK_PTR
);
2909 gcc_assert (e
== NULL
);
2913 /* Note that the following may create a new basic block
2914 and renumber the existing basic blocks. */
2915 if (split_at_insn
!= BB_END (bb
))
2917 e
= split_block (bb
, split_at_insn
);
2922 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
2925 if (insn
== BB_HEAD (bb
))
2931 verify_flow_info ();
2933 return blocks_split
;
2936 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
2937 the conditional branch target, SECOND_HEAD should be the fall-thru
2938 there is no need to handle this here the loop versioning code handles
2939 this. the reason for SECON_HEAD is that it is needed for condition
2940 in trees, and this should be of the same type since it is a hook. */
2942 rtl_lv_add_condition_to_bb (basic_block first_head
,
2943 basic_block second_head ATTRIBUTE_UNUSED
,
2944 basic_block cond_bb
, void *comp_rtx
)
2946 rtx label
, seq
, jump
;
2947 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
2948 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
2949 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
2950 enum machine_mode mode
;
2953 label
= block_label (first_head
);
2954 mode
= GET_MODE (op0
);
2955 if (mode
== VOIDmode
)
2956 mode
= GET_MODE (op1
);
2959 op0
= force_operand (op0
, NULL_RTX
);
2960 op1
= force_operand (op1
, NULL_RTX
);
2961 do_compare_rtx_and_jump (op0
, op1
, comp
, 0,
2962 mode
, NULL_RTX
, NULL_RTX
, label
);
2963 jump
= get_last_insn ();
2964 JUMP_LABEL (jump
) = label
;
2965 LABEL_NUSES (label
)++;
2969 /* Add the new cond , in the new head. */
2970 emit_insn_after(seq
, BB_END(cond_bb
));
2974 /* Given a block B with unconditional branch at its end, get the
2975 store the return the branch edge and the fall-thru edge in
2976 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
2978 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
2979 edge
*fallthru_edge
)
2981 edge e
= EDGE_SUCC (b
, 0);
2983 if (e
->flags
& EDGE_FALLTHRU
)
2986 *branch_edge
= EDGE_SUCC (b
, 1);
2991 *fallthru_edge
= EDGE_SUCC (b
, 1);
2996 init_rtl_bb_info (basic_block bb
)
2998 gcc_assert (!bb
->il
.rtl
);
2999 bb
->il
.rtl
= GGC_CNEW (struct rtl_bb_info
);
3003 /* Add EXPR to the end of basic block BB. */
3006 insert_insn_end_bb_new (rtx pat
, basic_block bb
)
3008 rtx insn
= BB_END (bb
);
3012 while (NEXT_INSN (pat_end
) != NULL_RTX
)
3013 pat_end
= NEXT_INSN (pat_end
);
3015 /* If the last insn is a jump, insert EXPR in front [taking care to
3016 handle cc0, etc. properly]. Similarly we need to care trapping
3017 instructions in presence of non-call exceptions. */
3020 || (NONJUMP_INSN_P (insn
)
3021 && (!single_succ_p (bb
)
3022 || single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
)))
3027 /* If this is a jump table, then we can't insert stuff here. Since
3028 we know the previous real insn must be the tablejump, we insert
3029 the new instruction just before the tablejump. */
3030 if (GET_CODE (PATTERN (insn
)) == ADDR_VEC
3031 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
)
3032 insn
= prev_real_insn (insn
);
3035 /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts
3036 if cc0 isn't set. */
3037 note
= find_reg_note (insn
, REG_CC_SETTER
, NULL_RTX
);
3039 insn
= XEXP (note
, 0);
3042 rtx maybe_cc0_setter
= prev_nonnote_insn (insn
);
3043 if (maybe_cc0_setter
3044 && INSN_P (maybe_cc0_setter
)
3045 && sets_cc0_p (PATTERN (maybe_cc0_setter
)))
3046 insn
= maybe_cc0_setter
;
3049 /* FIXME: What if something in cc0/jump uses value set in new
3051 new_insn
= emit_insn_before_noloc (pat
, insn
, bb
);
3054 /* Likewise if the last insn is a call, as will happen in the presence
3055 of exception handling. */
3056 else if (CALL_P (insn
)
3057 && (!single_succ_p (bb
)
3058 || single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
3060 /* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers,
3061 we search backward and place the instructions before the first
3062 parameter is loaded. Do this for everyone for consistency and a
3063 presumption that we'll get better code elsewhere as well. */
3065 /* Since different machines initialize their parameter registers
3066 in different orders, assume nothing. Collect the set of all
3067 parameter registers. */
3068 insn
= find_first_parameter_load (insn
, BB_HEAD (bb
));
3070 /* If we found all the parameter loads, then we want to insert
3071 before the first parameter load.
3073 If we did not find all the parameter loads, then we might have
3074 stopped on the head of the block, which could be a CODE_LABEL.
3075 If we inserted before the CODE_LABEL, then we would be putting
3076 the insn in the wrong basic block. In that case, put the insn
3077 after the CODE_LABEL. Also, respect NOTE_INSN_BASIC_BLOCK. */
3078 while (LABEL_P (insn
)
3079 || NOTE_INSN_BASIC_BLOCK_P (insn
))
3080 insn
= NEXT_INSN (insn
);
3082 new_insn
= emit_insn_before_noloc (pat
, insn
, bb
);
3085 new_insn
= emit_insn_after_noloc (pat
, insn
, bb
);
3090 /* Returns true if it is possible to remove edge E by redirecting
3091 it to the destination of the other edge from E->src. */
3094 rtl_can_remove_branch_p (const_edge e
)
3096 const_basic_block src
= e
->src
;
3097 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
3098 const_rtx insn
= BB_END (src
), set
;
3100 /* The conditions are taken from try_redirect_by_replacing_jump. */
3101 if (target
== EXIT_BLOCK_PTR
)
3104 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
3107 if (find_reg_note (insn
, REG_CROSSING_JUMP
, NULL_RTX
)
3108 || BB_PARTITION (src
) != BB_PARTITION (target
))
3111 if (!onlyjump_p (insn
)
3112 || tablejump_p (insn
, NULL
, NULL
))
3115 set
= single_set (insn
);
3116 if (!set
|| side_effects_p (set
))
3122 /* Implementation of CFG manipulation for linearized RTL. */
3123 struct cfg_hooks rtl_cfg_hooks
= {
3125 rtl_verify_flow_info
,
3127 rtl_create_basic_block
,
3128 rtl_redirect_edge_and_branch
,
3129 rtl_redirect_edge_and_branch_force
,
3130 rtl_can_remove_branch_p
,
3133 rtl_move_block_after
,
3134 rtl_can_merge_blocks
, /* can_merge_blocks_p */
3138 NULL
, /* can_duplicate_block_p */
3139 NULL
, /* duplicate_block */
3141 rtl_make_forwarder_block
,
3142 rtl_tidy_fallthru_edge
,
3143 rtl_block_ends_with_call_p
,
3144 rtl_block_ends_with_condjump_p
,
3145 rtl_flow_call_edges_add
,
3146 NULL
, /* execute_on_growing_pred */
3147 NULL
, /* execute_on_shrinking_pred */
3148 NULL
, /* duplicate loop for trees */
3149 NULL
, /* lv_add_condition_to_bb */
3150 NULL
, /* lv_adjust_loop_header_phi*/
3151 NULL
, /* extract_cond_bb_edges */
3152 NULL
/* flush_pending_stmts */
3155 /* Implementation of CFG manipulation for cfg layout RTL, where
3156 basic block connected via fallthru edges does not have to be adjacent.
3157 This representation will hopefully become the default one in future
3158 version of the compiler. */
3160 /* We do not want to declare these functions in a header file, since they
3161 should only be used through the cfghooks interface, and we do not want to
3162 move them here since it would require also moving quite a lot of related
3163 code. They are in cfglayout.c. */
3164 extern bool cfg_layout_can_duplicate_bb_p (const_basic_block
);
3165 extern basic_block
cfg_layout_duplicate_bb (basic_block
);
3167 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
3169 rtl_verify_flow_info_1
,
3171 cfg_layout_create_basic_block
,
3172 cfg_layout_redirect_edge_and_branch
,
3173 cfg_layout_redirect_edge_and_branch_force
,
3174 rtl_can_remove_branch_p
,
3175 cfg_layout_delete_block
,
3176 cfg_layout_split_block
,
3177 rtl_move_block_after
,
3178 cfg_layout_can_merge_blocks_p
,
3179 cfg_layout_merge_blocks
,
3182 cfg_layout_can_duplicate_bb_p
,
3183 cfg_layout_duplicate_bb
,
3184 cfg_layout_split_edge
,
3185 rtl_make_forwarder_block
,
3187 rtl_block_ends_with_call_p
,
3188 rtl_block_ends_with_condjump_p
,
3189 rtl_flow_call_edges_add
,
3190 NULL
, /* execute_on_growing_pred */
3191 NULL
, /* execute_on_shrinking_pred */
3192 duplicate_loop_to_header_edge
, /* duplicate loop for trees */
3193 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
3194 NULL
, /* lv_adjust_loop_header_phi*/
3195 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
3196 NULL
/* flush_pending_stmts */