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 return (NOTE_KIND (note
) == NOTE_INSN_DELETED
90 || NOTE_KIND (note
) == NOTE_INSN_BASIC_BLOCK
);
93 /* True if a given label can be deleted. */
96 can_delete_label_p (const_rtx label
)
98 return (!LABEL_PRESERVE_P (label
)
99 /* User declared labels must be preserved. */
100 && LABEL_NAME (label
) == 0
101 && !in_expr_list_p (forced_labels
, label
));
104 /* Delete INSN by patching it out. Return the next insn. */
107 delete_insn (rtx insn
)
109 rtx next
= NEXT_INSN (insn
);
111 bool really_delete
= true;
115 /* Some labels can't be directly removed from the INSN chain, as they
116 might be references via variables, constant pool etc.
117 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
118 if (! can_delete_label_p (insn
))
120 const char *name
= LABEL_NAME (insn
);
122 really_delete
= false;
123 PUT_CODE (insn
, NOTE
);
124 NOTE_KIND (insn
) = NOTE_INSN_DELETED_LABEL
;
125 NOTE_DELETED_LABEL_NAME (insn
) = name
;
128 remove_node_from_expr_list (insn
, &nonlocal_goto_handler_labels
);
133 /* If this insn has already been deleted, something is very wrong. */
134 gcc_assert (!INSN_DELETED_P (insn
));
136 INSN_DELETED_P (insn
) = 1;
139 /* If deleting a jump, decrement the use count of the label. Deleting
140 the label itself should happen in the normal course of block merging. */
143 if (JUMP_LABEL (insn
)
144 && LABEL_P (JUMP_LABEL (insn
)))
145 LABEL_NUSES (JUMP_LABEL (insn
))--;
147 /* If there are more targets, remove them too. */
149 = find_reg_note (insn
, REG_LABEL_TARGET
, NULL_RTX
)) != NULL_RTX
150 && LABEL_P (XEXP (note
, 0)))
152 LABEL_NUSES (XEXP (note
, 0))--;
153 remove_note (insn
, note
);
157 /* Also if deleting any insn that references a label as an operand. */
158 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, NULL_RTX
)) != NULL_RTX
159 && LABEL_P (XEXP (note
, 0)))
161 LABEL_NUSES (XEXP (note
, 0))--;
162 remove_note (insn
, note
);
166 && (GET_CODE (PATTERN (insn
)) == ADDR_VEC
167 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
))
169 rtx pat
= PATTERN (insn
);
170 int diff_vec_p
= GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
;
171 int len
= XVECLEN (pat
, diff_vec_p
);
174 for (i
= 0; i
< len
; i
++)
176 rtx label
= XEXP (XVECEXP (pat
, diff_vec_p
, i
), 0);
178 /* When deleting code in bulk (e.g. removing many unreachable
179 blocks) we can delete a label that's a target of the vector
180 before deleting the vector itself. */
182 LABEL_NUSES (label
)--;
189 /* Like delete_insn but also purge dead edges from BB. */
192 delete_insn_and_edges (rtx insn
)
198 && BLOCK_FOR_INSN (insn
)
199 && BB_END (BLOCK_FOR_INSN (insn
)) == insn
)
201 x
= delete_insn (insn
);
203 purge_dead_edges (BLOCK_FOR_INSN (insn
));
207 /* Unlink a chain of insns between START and FINISH, leaving notes
208 that must be paired. If CLEAR_BB is true, we set bb field for
209 insns that cannot be removed to NULL. */
212 delete_insn_chain (rtx start
, rtx finish
, bool clear_bb
)
216 /* Unchain the insns one by one. It would be quicker to delete all of these
217 with a single unchaining, rather than one at a time, but we need to keep
221 next
= NEXT_INSN (start
);
222 if (NOTE_P (start
) && !can_delete_note_p (start
))
225 next
= delete_insn (start
);
227 if (clear_bb
&& !INSN_DELETED_P (start
))
228 set_block_for_insn (start
, NULL
);
236 /* Create a new basic block consisting of the instructions between HEAD and END
237 inclusive. This function is designed to allow fast BB construction - reuses
238 the note and basic block struct in BB_NOTE, if any and do not grow
239 BASIC_BLOCK chain and should be used directly only by CFG construction code.
240 END can be NULL in to create new empty basic block before HEAD. Both END
241 and HEAD can be NULL to create basic block at the end of INSN chain.
242 AFTER is the basic block we should be put after. */
245 create_basic_block_structure (rtx head
, rtx end
, rtx bb_note
, basic_block after
)
250 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
253 /* If we found an existing note, thread it back onto the chain. */
261 after
= PREV_INSN (head
);
265 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
266 reorder_insns_nobb (bb_note
, bb_note
, after
);
270 /* Otherwise we must create a note and a basic block structure. */
274 init_rtl_bb_info (bb
);
277 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
278 else if (LABEL_P (head
) && end
)
280 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
286 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
292 NOTE_BASIC_BLOCK (bb_note
) = bb
;
295 /* Always include the bb note in the block. */
296 if (NEXT_INSN (end
) == bb_note
)
301 bb
->index
= last_basic_block
++;
302 bb
->flags
= BB_NEW
| BB_RTL
;
303 link_block (bb
, after
);
304 SET_BASIC_BLOCK (bb
->index
, bb
);
305 df_bb_refs_record (bb
->index
, false);
306 update_bb_for_insn (bb
);
307 BB_SET_PARTITION (bb
, BB_UNPARTITIONED
);
309 /* Tag the block so that we know it has been used when considering
310 other basic block notes. */
316 /* Create new basic block consisting of instructions in between HEAD and END
317 and place it to the BB chain after block AFTER. END can be NULL in to
318 create new empty basic block before HEAD. Both END and HEAD can be NULL to
319 create basic block at the end of INSN chain. */
322 rtl_create_basic_block (void *headp
, void *endp
, basic_block after
)
324 rtx head
= (rtx
) headp
, end
= (rtx
) endp
;
327 /* Grow the basic block array if needed. */
328 if ((size_t) last_basic_block
>= VEC_length (basic_block
, basic_block_info
))
330 size_t new_size
= last_basic_block
+ (last_basic_block
+ 3) / 4;
331 VEC_safe_grow_cleared (basic_block
, gc
, basic_block_info
, new_size
);
336 bb
= create_basic_block_structure (head
, end
, NULL
, after
);
342 cfg_layout_create_basic_block (void *head
, void *end
, basic_block after
)
344 basic_block newbb
= rtl_create_basic_block (head
, end
, after
);
349 /* Delete the insns in a (non-live) block. We physically delete every
350 non-deleted-note insn, and update the flow graph appropriately.
352 Return nonzero if we deleted an exception handler. */
354 /* ??? Preserving all such notes strikes me as wrong. It would be nice
355 to post-process the stream to remove empty blocks, loops, ranges, etc. */
358 rtl_delete_block (basic_block b
)
362 /* If the head of this block is a CODE_LABEL, then it might be the
363 label for an exception handler which can't be reached. We need
364 to remove the label from the exception_handler_label list. */
367 end
= get_last_bb_insn (b
);
369 /* Selectively delete the entire chain. */
371 delete_insn_chain (insn
, end
, true);
375 fprintf (dump_file
, "deleting block %d\n", b
->index
);
376 df_bb_delete (b
->index
);
379 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
382 compute_bb_for_insn (void)
388 rtx end
= BB_END (bb
);
391 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
393 BLOCK_FOR_INSN (insn
) = bb
;
400 /* Release the basic_block_for_insn array. */
403 free_bb_for_insn (void)
406 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
407 if (!BARRIER_P (insn
))
408 BLOCK_FOR_INSN (insn
) = NULL
;
413 rest_of_pass_free_cfg (void)
416 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
417 valid at that point so it would be too late to call df_analyze. */
418 if (optimize
> 0 && flag_delayed_branch
)
426 struct rtl_opt_pass pass_free_cfg
=
432 rest_of_pass_free_cfg
, /* execute */
435 0, /* static_pass_number */
437 0, /* properties_required */
438 0, /* properties_provided */
439 PROP_cfg
, /* properties_destroyed */
440 0, /* todo_flags_start */
441 0, /* todo_flags_finish */
445 /* Return RTX to emit after when we want to emit code on the entry of function. */
447 entry_of_function (void)
449 return (n_basic_blocks
> NUM_FIXED_BLOCKS
?
450 BB_HEAD (ENTRY_BLOCK_PTR
->next_bb
) : get_insns ());
453 /* Emit INSN at the entry point of the function, ensuring that it is only
454 executed once per function. */
456 emit_insn_at_entry (rtx insn
)
458 edge_iterator ei
= ei_start (ENTRY_BLOCK_PTR
->succs
);
459 edge e
= ei_safe_edge (ei
);
460 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
462 insert_insn_on_edge (insn
, e
);
463 commit_edge_insertions ();
466 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
467 (or BARRIER if found) and notify df of the bb change.
468 The insn chain range is inclusive
469 (i.e. both BEGIN and END will be updated. */
472 update_bb_for_insn_chain (rtx begin
, rtx end
, basic_block bb
)
476 end
= NEXT_INSN (end
);
477 for (insn
= begin
; insn
!= end
; insn
= NEXT_INSN (insn
))
478 if (!BARRIER_P (insn
))
479 df_insn_change_bb (insn
, bb
);
482 /* Update BLOCK_FOR_INSN of insns in BB to BB,
483 and notify df of the change. */
486 update_bb_for_insn (basic_block bb
)
488 update_bb_for_insn_chain (BB_HEAD (bb
), BB_END (bb
), bb
);
492 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
493 note associated with the BLOCK. */
496 first_insn_after_basic_block_note (basic_block block
)
500 /* Get the first instruction in the block. */
501 insn
= BB_HEAD (block
);
503 if (insn
== NULL_RTX
)
506 insn
= NEXT_INSN (insn
);
507 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
509 return NEXT_INSN (insn
);
512 /* Creates a new basic block just after basic block B by splitting
513 everything after specified instruction I. */
516 rtl_split_block (basic_block bb
, void *insnp
)
519 rtx insn
= (rtx
) insnp
;
525 insn
= first_insn_after_basic_block_note (bb
);
528 insn
= PREV_INSN (insn
);
530 insn
= get_last_insn ();
533 /* We probably should check type of the insn so that we do not create
534 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
536 if (insn
== BB_END (bb
))
537 emit_note_after (NOTE_INSN_DELETED
, insn
);
539 /* Create the new basic block. */
540 new_bb
= create_basic_block (NEXT_INSN (insn
), BB_END (bb
), bb
);
541 BB_COPY_PARTITION (new_bb
, bb
);
544 /* Redirect the outgoing edges. */
545 new_bb
->succs
= bb
->succs
;
547 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
550 /* The new block starts off being dirty. */
551 df_set_bb_dirty (bb
);
555 /* Blocks A and B are to be merged into a single block A. The insns
556 are already contiguous. */
559 rtl_merge_blocks (basic_block a
, basic_block b
)
561 rtx b_head
= BB_HEAD (b
), b_end
= BB_END (b
), a_end
= BB_END (a
);
562 rtx del_first
= NULL_RTX
, del_last
= NULL_RTX
;
566 fprintf (dump_file
, "merging block %d into block %d\n", b
->index
, a
->index
);
568 /* If there was a CODE_LABEL beginning B, delete it. */
569 if (LABEL_P (b_head
))
571 /* Detect basic blocks with nothing but a label. This can happen
572 in particular at the end of a function. */
576 del_first
= del_last
= b_head
;
577 b_head
= NEXT_INSN (b_head
);
580 /* Delete the basic block note and handle blocks containing just that
582 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
590 b_head
= NEXT_INSN (b_head
);
593 /* If there was a jump out of A, delete it. */
598 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
600 || NOTE_INSN_BASIC_BLOCK_P (prev
)
601 || prev
== BB_HEAD (a
))
607 /* If this was a conditional jump, we need to also delete
608 the insn that set cc0. */
609 if (only_sets_cc0_p (prev
))
613 prev
= prev_nonnote_insn (prev
);
620 a_end
= PREV_INSN (del_first
);
622 else if (BARRIER_P (NEXT_INSN (a_end
)))
623 del_first
= NEXT_INSN (a_end
);
625 /* Delete everything marked above as well as crap that might be
626 hanging out between the two blocks. */
628 delete_insn_chain (del_first
, del_last
, true);
630 /* Reassociate the insns of B with A. */
633 update_bb_for_insn_chain (a_end
, b_end
, a
);
638 df_bb_delete (b
->index
);
643 /* Return true when block A and B can be merged. */
646 rtl_can_merge_blocks (basic_block a
, basic_block b
)
648 /* If we are partitioning hot/cold basic blocks, we don't want to
649 mess up unconditional or indirect jumps that cross between hot
652 Basic block partitioning may result in some jumps that appear to
653 be optimizable (or blocks that appear to be mergeable), but which really
654 must be left untouched (they are required to make it safely across
655 partition boundaries). See the comments at the top of
656 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
658 if (BB_PARTITION (a
) != BB_PARTITION (b
))
661 /* There must be exactly one edge in between the blocks. */
662 return (single_succ_p (a
)
663 && single_succ (a
) == b
666 /* Must be simple edge. */
667 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
669 && a
!= ENTRY_BLOCK_PTR
&& b
!= EXIT_BLOCK_PTR
670 /* If the jump insn has side effects,
671 we can't kill the edge. */
672 && (!JUMP_P (BB_END (a
))
674 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
677 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
681 block_label (basic_block block
)
683 if (block
== EXIT_BLOCK_PTR
)
686 if (!LABEL_P (BB_HEAD (block
)))
688 BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
691 return BB_HEAD (block
);
694 /* Attempt to perform edge redirection by replacing possibly complex jump
695 instruction by unconditional jump or removing jump completely. This can
696 apply only if all edges now point to the same block. The parameters and
697 return values are equivalent to redirect_edge_and_branch. */
700 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
702 basic_block src
= e
->src
;
703 rtx insn
= BB_END (src
), kill_from
;
707 /* If we are partitioning hot/cold basic blocks, we don't want to
708 mess up unconditional or indirect jumps that cross between hot
711 Basic block partitioning may result in some jumps that appear to
712 be optimizable (or blocks that appear to be mergeable), but which really
713 must be left untouched (they are required to make it safely across
714 partition boundaries). See the comments at the top of
715 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
717 if (find_reg_note (insn
, REG_CROSSING_JUMP
, NULL_RTX
)
718 || BB_PARTITION (src
) != BB_PARTITION (target
))
721 /* We can replace or remove a complex jump only when we have exactly
722 two edges. Also, if we have exactly one outgoing edge, we can
724 if (EDGE_COUNT (src
->succs
) >= 3
725 /* Verify that all targets will be TARGET. Specifically, the
726 edge that is not E must also go to TARGET. */
727 || (EDGE_COUNT (src
->succs
) == 2
728 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
731 if (!onlyjump_p (insn
))
733 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
736 /* Avoid removing branch with side effects. */
737 set
= single_set (insn
);
738 if (!set
|| side_effects_p (set
))
741 /* In case we zap a conditional jump, we'll need to kill
742 the cc0 setter too. */
745 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
))
746 && only_sets_cc0_p (PREV_INSN (insn
)))
747 kill_from
= PREV_INSN (insn
);
750 /* See if we can create the fallthru edge. */
751 if (in_cfglayout
|| can_fallthru (src
, target
))
754 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
757 /* Selectively unlink whole insn chain. */
760 rtx insn
= src
->il
.rtl
->footer
;
762 delete_insn_chain (kill_from
, BB_END (src
), false);
764 /* Remove barriers but keep jumptables. */
767 if (BARRIER_P (insn
))
769 if (PREV_INSN (insn
))
770 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
772 src
->il
.rtl
->footer
= NEXT_INSN (insn
);
773 if (NEXT_INSN (insn
))
774 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
778 insn
= NEXT_INSN (insn
);
782 delete_insn_chain (kill_from
, PREV_INSN (BB_HEAD (target
)),
786 /* If this already is simplejump, redirect it. */
787 else if (simplejump_p (insn
))
789 if (e
->dest
== target
)
792 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
793 INSN_UID (insn
), e
->dest
->index
, target
->index
);
794 if (!redirect_jump (insn
, block_label (target
), 0))
796 gcc_assert (target
== EXIT_BLOCK_PTR
);
801 /* Cannot do anything for target exit block. */
802 else if (target
== EXIT_BLOCK_PTR
)
805 /* Or replace possibly complicated jump insn by simple jump insn. */
808 rtx target_label
= block_label (target
);
809 rtx barrier
, label
, table
;
811 emit_jump_insn_after_noloc (gen_jump (target_label
), insn
);
812 JUMP_LABEL (BB_END (src
)) = target_label
;
813 LABEL_NUSES (target_label
)++;
815 fprintf (dump_file
, "Replacing insn %i by jump %i\n",
816 INSN_UID (insn
), INSN_UID (BB_END (src
)));
819 delete_insn_chain (kill_from
, insn
, false);
821 /* Recognize a tablejump that we are converting to a
822 simple jump and remove its associated CODE_LABEL
823 and ADDR_VEC or ADDR_DIFF_VEC. */
824 if (tablejump_p (insn
, &label
, &table
))
825 delete_insn_chain (label
, table
, false);
827 barrier
= next_nonnote_insn (BB_END (src
));
828 if (!barrier
|| !BARRIER_P (barrier
))
829 emit_barrier_after (BB_END (src
));
832 if (barrier
!= NEXT_INSN (BB_END (src
)))
834 /* Move the jump before barrier so that the notes
835 which originally were or were created before jump table are
836 inside the basic block. */
837 rtx new_insn
= BB_END (src
);
839 update_bb_for_insn_chain (NEXT_INSN (BB_END (src
)),
840 PREV_INSN (barrier
), src
);
842 NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
843 PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
845 NEXT_INSN (new_insn
) = barrier
;
846 NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
848 PREV_INSN (new_insn
) = PREV_INSN (barrier
);
849 PREV_INSN (barrier
) = new_insn
;
854 /* Keep only one edge out and set proper flags. */
855 if (!single_succ_p (src
))
857 gcc_assert (single_succ_p (src
));
859 e
= single_succ_edge (src
);
861 e
->flags
= EDGE_FALLTHRU
;
865 e
->probability
= REG_BR_PROB_BASE
;
866 e
->count
= src
->count
;
868 if (e
->dest
!= target
)
869 redirect_edge_succ (e
, target
);
873 /* Subroutine of redirect_branch_edge that tries to patch the jump
874 instruction INSN so that it reaches block NEW. Do this
875 only when it originally reached block OLD. Return true if this
876 worked or the original target wasn't OLD, return false if redirection
880 patch_jump_insn (rtx insn
, rtx old_label
, basic_block new_bb
)
883 /* Recognize a tablejump and adjust all matching cases. */
884 if (tablejump_p (insn
, NULL
, &tmp
))
888 rtx new_label
= block_label (new_bb
);
890 if (new_bb
== EXIT_BLOCK_PTR
)
892 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
893 vec
= XVEC (PATTERN (tmp
), 0);
895 vec
= XVEC (PATTERN (tmp
), 1);
897 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
898 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
900 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
901 --LABEL_NUSES (old_label
);
902 ++LABEL_NUSES (new_label
);
905 /* Handle casesi dispatch insns. */
906 if ((tmp
= single_set (insn
)) != NULL
907 && SET_DEST (tmp
) == pc_rtx
908 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
909 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
910 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
912 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
914 --LABEL_NUSES (old_label
);
915 ++LABEL_NUSES (new_label
);
920 /* ?? We may play the games with moving the named labels from
921 one basic block to the other in case only one computed_jump is
923 if (computed_jump_p (insn
)
924 /* A return instruction can't be redirected. */
925 || returnjump_p (insn
))
928 if (!currently_expanding_to_rtl
|| JUMP_LABEL (insn
) == old_label
)
930 /* If the insn doesn't go where we think, we're confused. */
931 gcc_assert (JUMP_LABEL (insn
) == old_label
);
933 /* If the substitution doesn't succeed, die. This can happen
934 if the back end emitted unrecognizable instructions or if
935 target is exit block on some arches. */
936 if (!redirect_jump (insn
, block_label (new_bb
), 0))
938 gcc_assert (new_bb
== EXIT_BLOCK_PTR
);
947 /* Redirect edge representing branch of (un)conditional jump or tablejump,
950 redirect_branch_edge (edge e
, basic_block target
)
952 rtx old_label
= BB_HEAD (e
->dest
);
953 basic_block src
= e
->src
;
954 rtx insn
= BB_END (src
);
956 /* We can only redirect non-fallthru edges of jump insn. */
957 if (e
->flags
& EDGE_FALLTHRU
)
959 else if (!JUMP_P (insn
) && !currently_expanding_to_rtl
)
962 if (!currently_expanding_to_rtl
)
964 if (!patch_jump_insn (insn
, old_label
, target
))
968 /* When expanding this BB might actually contain multiple
969 jumps (i.e. not yet split by find_many_sub_basic_blocks).
970 Redirect all of those that match our label. */
971 for (insn
= BB_HEAD (src
); insn
!= NEXT_INSN (BB_END (src
));
972 insn
= NEXT_INSN (insn
))
973 if (JUMP_P (insn
) && !patch_jump_insn (insn
, old_label
, target
))
977 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
978 e
->src
->index
, e
->dest
->index
, target
->index
);
980 if (e
->dest
!= target
)
981 e
= redirect_edge_succ_nodup (e
, target
);
986 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
987 expense of adding new instructions or reordering basic blocks.
989 Function can be also called with edge destination equivalent to the TARGET.
990 Then it should try the simplifications and do nothing if none is possible.
992 Return edge representing the branch if transformation succeeded. Return NULL
994 We still return NULL in case E already destinated TARGET and we didn't
995 managed to simplify instruction stream. */
998 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
1001 basic_block src
= e
->src
;
1003 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1006 if (e
->dest
== target
)
1009 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
1011 df_set_bb_dirty (src
);
1015 ret
= redirect_branch_edge (e
, target
);
1019 df_set_bb_dirty (src
);
1023 /* Like force_nonfallthru below, but additionally performs redirection
1024 Used by redirect_edge_and_branch_force. */
1027 force_nonfallthru_and_redirect (edge e
, basic_block target
)
1029 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
1032 int abnormal_edge_flags
= 0;
1035 /* In the case the last instruction is conditional jump to the next
1036 instruction, first redirect the jump itself and then continue
1037 by creating a basic block afterwards to redirect fallthru edge. */
1038 if (e
->src
!= ENTRY_BLOCK_PTR
&& e
->dest
!= EXIT_BLOCK_PTR
1039 && any_condjump_p (BB_END (e
->src
))
1040 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1043 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1046 redirected
= redirect_jump (BB_END (e
->src
), block_label (target
), 0);
1047 gcc_assert (redirected
);
1049 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1052 int prob
= INTVAL (XEXP (note
, 0));
1054 b
->probability
= prob
;
1055 b
->count
= e
->count
* prob
/ REG_BR_PROB_BASE
;
1056 e
->probability
-= e
->probability
;
1057 e
->count
-= b
->count
;
1058 if (e
->probability
< 0)
1065 if (e
->flags
& EDGE_ABNORMAL
)
1067 /* Irritating special case - fallthru edge to the same block as abnormal
1069 We can't redirect abnormal edge, but we still can split the fallthru
1070 one and create separate abnormal edge to original destination.
1071 This allows bb-reorder to make such edge non-fallthru. */
1072 gcc_assert (e
->dest
== target
);
1073 abnormal_edge_flags
= e
->flags
& ~(EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
);
1074 e
->flags
&= EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
;
1078 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1079 if (e
->src
== ENTRY_BLOCK_PTR
)
1081 /* We can't redirect the entry block. Create an empty block
1082 at the start of the function which we use to add the new
1088 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
, ENTRY_BLOCK_PTR
);
1090 /* Change the existing edge's source to be the new block, and add
1091 a new edge from the entry block to the new block. */
1093 for (ei
= ei_start (ENTRY_BLOCK_PTR
->succs
); (tmp
= ei_safe_edge (ei
)); )
1097 VEC_unordered_remove (edge
, ENTRY_BLOCK_PTR
->succs
, ei
.index
);
1107 VEC_safe_push (edge
, gc
, bb
->succs
, e
);
1108 make_single_succ_edge (ENTRY_BLOCK_PTR
, bb
, EDGE_FALLTHRU
);
1112 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
)
1114 /* Create the new structures. */
1116 /* If the old block ended with a tablejump, skip its table
1117 by searching forward from there. Otherwise start searching
1118 forward from the last instruction of the old block. */
1119 if (!tablejump_p (BB_END (e
->src
), NULL
, ¬e
))
1120 note
= BB_END (e
->src
);
1121 note
= NEXT_INSN (note
);
1123 jump_block
= create_basic_block (note
, NULL
, e
->src
);
1124 jump_block
->count
= e
->count
;
1125 jump_block
->frequency
= EDGE_FREQUENCY (e
);
1126 jump_block
->loop_depth
= target
->loop_depth
;
1128 /* Make sure new block ends up in correct hot/cold section. */
1130 BB_COPY_PARTITION (jump_block
, e
->src
);
1131 if (flag_reorder_blocks_and_partition
1132 && targetm
.have_named_sections
1133 && JUMP_P (BB_END (jump_block
))
1134 && !any_condjump_p (BB_END (jump_block
))
1135 && (EDGE_SUCC (jump_block
, 0)->flags
& EDGE_CROSSING
))
1136 add_reg_note (BB_END (jump_block
), REG_CROSSING_JUMP
, NULL_RTX
);
1139 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1140 new_edge
->probability
= e
->probability
;
1141 new_edge
->count
= e
->count
;
1143 /* Redirect old edge. */
1144 redirect_edge_pred (e
, jump_block
);
1145 e
->probability
= REG_BR_PROB_BASE
;
1147 new_bb
= jump_block
;
1150 jump_block
= e
->src
;
1152 if (e
->goto_locus
&& e
->goto_block
== NULL
)
1153 loc
= e
->goto_locus
;
1156 e
->flags
&= ~EDGE_FALLTHRU
;
1157 if (target
== EXIT_BLOCK_PTR
)
1160 emit_jump_insn_after_setloc (gen_return (), BB_END (jump_block
), loc
);
1167 rtx label
= block_label (target
);
1168 emit_jump_insn_after_setloc (gen_jump (label
), BB_END (jump_block
), loc
);
1169 JUMP_LABEL (BB_END (jump_block
)) = label
;
1170 LABEL_NUSES (label
)++;
1173 emit_barrier_after (BB_END (jump_block
));
1174 redirect_edge_succ_nodup (e
, target
);
1176 if (abnormal_edge_flags
)
1177 make_edge (src
, target
, abnormal_edge_flags
);
1179 df_mark_solutions_dirty ();
1183 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1184 (and possibly create new basic block) to make edge non-fallthru.
1185 Return newly created BB or NULL if none. */
1188 force_nonfallthru (edge e
)
1190 return force_nonfallthru_and_redirect (e
, e
->dest
);
1193 /* Redirect edge even at the expense of creating new jump insn or
1194 basic block. Return new basic block if created, NULL otherwise.
1195 Conversion must be possible. */
1198 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1200 if (redirect_edge_and_branch (e
, target
)
1201 || e
->dest
== target
)
1204 /* In case the edge redirection failed, try to force it to be non-fallthru
1205 and redirect newly created simplejump. */
1206 df_set_bb_dirty (e
->src
);
1207 return force_nonfallthru_and_redirect (e
, target
);
1210 /* The given edge should potentially be a fallthru edge. If that is in
1211 fact true, delete the jump and barriers that are in the way. */
1214 rtl_tidy_fallthru_edge (edge e
)
1217 basic_block b
= e
->src
, c
= b
->next_bb
;
1219 /* ??? In a late-running flow pass, other folks may have deleted basic
1220 blocks by nopping out blocks, leaving multiple BARRIERs between here
1221 and the target label. They ought to be chastised and fixed.
1223 We can also wind up with a sequence of undeletable labels between
1224 one block and the next.
1226 So search through a sequence of barriers, labels, and notes for
1227 the head of block C and assert that we really do fall through. */
1229 for (q
= NEXT_INSN (BB_END (b
)); q
!= BB_HEAD (c
); q
= NEXT_INSN (q
))
1233 /* Remove what will soon cease being the jump insn from the source block.
1234 If block B consisted only of this single jump, turn it into a deleted
1239 && (any_uncondjump_p (q
)
1240 || single_succ_p (b
)))
1243 /* If this was a conditional jump, we need to also delete
1244 the insn that set cc0. */
1245 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1252 /* Selectively unlink the sequence. */
1253 if (q
!= PREV_INSN (BB_HEAD (c
)))
1254 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1256 e
->flags
|= EDGE_FALLTHRU
;
1259 /* Should move basic block BB after basic block AFTER. NIY. */
1262 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1263 basic_block after ATTRIBUTE_UNUSED
)
1268 /* Split a (typically critical) edge. Return the new block.
1269 The edge must not be abnormal.
1271 ??? The code generally expects to be called on critical edges.
1272 The case of a block ending in an unconditional jump to a
1273 block with multiple predecessors is not handled optimally. */
1276 rtl_split_edge (edge edge_in
)
1281 /* Abnormal edges cannot be split. */
1282 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1284 /* We are going to place the new block in front of edge destination.
1285 Avoid existence of fallthru predecessors. */
1286 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1291 FOR_EACH_EDGE (e
, ei
, edge_in
->dest
->preds
)
1292 if (e
->flags
& EDGE_FALLTHRU
)
1296 force_nonfallthru (e
);
1299 /* Create the basic block note. */
1300 if (edge_in
->dest
!= EXIT_BLOCK_PTR
)
1301 before
= BB_HEAD (edge_in
->dest
);
1305 /* If this is a fall through edge to the exit block, the blocks might be
1306 not adjacent, and the right place is the after the source. */
1307 if (edge_in
->flags
& EDGE_FALLTHRU
&& edge_in
->dest
== EXIT_BLOCK_PTR
)
1309 before
= NEXT_INSN (BB_END (edge_in
->src
));
1310 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1311 BB_COPY_PARTITION (bb
, edge_in
->src
);
1315 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1316 /* ??? Why not edge_in->dest->prev_bb here? */
1317 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1320 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1322 /* For non-fallthru edges, we must adjust the predecessor's
1323 jump instruction to target our new block. */
1324 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1326 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1327 gcc_assert (redirected
);
1330 redirect_edge_succ (edge_in
, bb
);
1335 /* Queue instructions for insertion on an edge between two basic blocks.
1336 The new instructions and basic blocks (if any) will not appear in the
1337 CFG until commit_edge_insertions is called. */
1340 insert_insn_on_edge (rtx pattern
, edge e
)
1342 /* We cannot insert instructions on an abnormal critical edge.
1343 It will be easier to find the culprit if we die now. */
1344 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1346 if (e
->insns
.r
== NULL_RTX
)
1349 push_to_sequence (e
->insns
.r
);
1351 emit_insn (pattern
);
1353 e
->insns
.r
= get_insns ();
1357 /* Update the CFG for the instructions queued on edge E. */
1360 commit_one_edge_insertion (edge e
)
1362 rtx before
= NULL_RTX
, after
= NULL_RTX
, insns
, tmp
, last
;
1363 basic_block bb
= NULL
;
1365 /* Pull the insns off the edge now since the edge might go away. */
1367 e
->insns
.r
= NULL_RTX
;
1369 if (!before
&& !after
)
1371 /* Figure out where to put these things. If the destination has
1372 one predecessor, insert there. Except for the exit block. */
1373 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR
)
1377 /* Get the location correct wrt a code label, and "nice" wrt
1378 a basic block note, and before everything else. */
1381 tmp
= NEXT_INSN (tmp
);
1382 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1383 tmp
= NEXT_INSN (tmp
);
1384 if (tmp
== BB_HEAD (bb
))
1387 after
= PREV_INSN (tmp
);
1389 after
= get_last_insn ();
1392 /* If the source has one successor and the edge is not abnormal,
1393 insert there. Except for the entry block. */
1394 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1395 && single_succ_p (e
->src
)
1396 && e
->src
!= ENTRY_BLOCK_PTR
)
1400 /* It is possible to have a non-simple jump here. Consider a target
1401 where some forms of unconditional jumps clobber a register. This
1402 happens on the fr30 for example.
1404 We know this block has a single successor, so we can just emit
1405 the queued insns before the jump. */
1406 if (JUMP_P (BB_END (bb
)))
1407 before
= BB_END (bb
);
1410 /* We'd better be fallthru, or we've lost track of
1412 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1414 after
= BB_END (bb
);
1417 /* Otherwise we must split the edge. */
1420 bb
= split_edge (e
);
1421 after
= BB_END (bb
);
1423 if (flag_reorder_blocks_and_partition
1424 && targetm
.have_named_sections
1425 && e
->src
!= ENTRY_BLOCK_PTR
1426 && BB_PARTITION (e
->src
) == BB_COLD_PARTITION
1427 && !(e
->flags
& EDGE_CROSSING
))
1429 rtx bb_note
, cur_insn
;
1432 for (cur_insn
= BB_HEAD (bb
); cur_insn
!= NEXT_INSN (BB_END (bb
));
1433 cur_insn
= NEXT_INSN (cur_insn
))
1434 if (NOTE_INSN_BASIC_BLOCK_P (cur_insn
))
1440 if (JUMP_P (BB_END (bb
))
1441 && !any_condjump_p (BB_END (bb
))
1442 && (single_succ_edge (bb
)->flags
& EDGE_CROSSING
))
1443 add_reg_note (BB_END (bb
), REG_CROSSING_JUMP
, NULL_RTX
);
1448 /* Now that we've found the spot, do the insertion. */
1452 emit_insn_before_noloc (insns
, before
, bb
);
1453 last
= prev_nonnote_insn (before
);
1456 last
= emit_insn_after_noloc (insns
, after
, bb
);
1458 if (returnjump_p (last
))
1460 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1461 This is not currently a problem because this only happens
1462 for the (single) epilogue, which already has a fallthru edge
1465 e
= single_succ_edge (bb
);
1466 gcc_assert (e
->dest
== EXIT_BLOCK_PTR
1467 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
1469 e
->flags
&= ~EDGE_FALLTHRU
;
1470 emit_barrier_after (last
);
1473 delete_insn (before
);
1476 gcc_assert (!JUMP_P (last
));
1478 /* Mark the basic block for find_many_sub_basic_blocks. */
1479 if (current_ir_type () != IR_RTL_CFGLAYOUT
)
1483 /* Update the CFG for all queued instructions. */
1486 commit_edge_insertions (void)
1490 bool changed
= false;
1492 #ifdef ENABLE_CHECKING
1493 verify_flow_info ();
1496 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
1501 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1505 commit_one_edge_insertion (e
);
1512 /* In the old rtl CFG API, it was OK to insert control flow on an
1513 edge, apparently? In cfglayout mode, this will *not* work, and
1514 the caller is responsible for making sure that control flow is
1515 valid at all times. */
1516 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
1519 blocks
= sbitmap_alloc (last_basic_block
);
1520 sbitmap_zero (blocks
);
1524 SET_BIT (blocks
, bb
->index
);
1525 /* Check for forgotten bb->aux values before commit_edge_insertions
1527 gcc_assert (bb
->aux
== &bb
->aux
);
1530 find_many_sub_basic_blocks (blocks
);
1531 sbitmap_free (blocks
);
1535 /* Print out RTL-specific basic block information (live information
1536 at start and end). */
1539 rtl_dump_bb (basic_block bb
, FILE *outf
, int indent
, int flags ATTRIBUTE_UNUSED
)
1545 s_indent
= (char *) alloca ((size_t) indent
+ 1);
1546 memset (s_indent
, ' ', (size_t) indent
);
1547 s_indent
[indent
] = '\0';
1551 df_dump_top (bb
, outf
);
1555 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
)); insn
!= last
;
1556 insn
= NEXT_INSN (insn
))
1557 print_rtl_single (outf
, insn
);
1561 df_dump_bottom (bb
, outf
);
1567 /* Like print_rtl, but also print out live information for the start of each
1571 print_rtl_with_bb (FILE *outf
, const_rtx rtx_first
)
1575 fprintf (outf
, "(nil)\n");
1578 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
1579 int max_uid
= get_max_uid ();
1580 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
1581 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
1582 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
1587 df_dump_start (outf
);
1589 FOR_EACH_BB_REVERSE (bb
)
1593 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
1594 end
[INSN_UID (BB_END (bb
))] = bb
;
1595 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
1597 enum bb_state state
= IN_MULTIPLE_BB
;
1599 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
1601 in_bb_p
[INSN_UID (x
)] = state
;
1603 if (x
== BB_END (bb
))
1608 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
1611 if ((bb
= start
[INSN_UID (tmp_rtx
)]) != NULL
)
1616 fprintf (outf
, ";; Start of basic block (");
1617 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1618 fprintf (outf
, " %d", e
->src
->index
);
1619 fprintf (outf
, ") -> %d\n", bb
->index
);
1623 df_dump_top (bb
, outf
);
1626 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1628 fputs (";; Pred edge ", outf
);
1629 dump_edge_info (outf
, e
, 0);
1634 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
1635 && !NOTE_P (tmp_rtx
)
1636 && !BARRIER_P (tmp_rtx
))
1637 fprintf (outf
, ";; Insn is not within a basic block\n");
1638 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
1639 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
1641 did_output
= print_rtl_single (outf
, tmp_rtx
);
1643 if ((bb
= end
[INSN_UID (tmp_rtx
)]) != NULL
)
1648 fprintf (outf
, ";; End of basic block %d -> (", bb
->index
);
1649 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1650 fprintf (outf
, " %d", e
->dest
->index
);
1651 fprintf (outf
, ")\n");
1655 df_dump_bottom (bb
, outf
);
1659 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1661 fputs (";; Succ edge ", outf
);
1662 dump_edge_info (outf
, e
, 1);
1675 if (crtl
->epilogue_delay_list
!= 0)
1677 fprintf (outf
, "\n;; Insns in epilogue delay list:\n\n");
1678 for (tmp_rtx
= crtl
->epilogue_delay_list
; tmp_rtx
!= 0;
1679 tmp_rtx
= XEXP (tmp_rtx
, 1))
1680 print_rtl_single (outf
, XEXP (tmp_rtx
, 0));
1685 update_br_prob_note (basic_block bb
)
1688 if (!JUMP_P (BB_END (bb
)))
1690 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
1691 if (!note
|| INTVAL (XEXP (note
, 0)) == BRANCH_EDGE (bb
)->probability
)
1693 XEXP (note
, 0) = GEN_INT (BRANCH_EDGE (bb
)->probability
);
1696 /* Get the last insn associated with block BB (that includes barriers and
1697 tablejumps after BB). */
1699 get_last_bb_insn (basic_block bb
)
1702 rtx end
= BB_END (bb
);
1704 /* Include any jump table following the basic block. */
1705 if (tablejump_p (end
, NULL
, &tmp
))
1708 /* Include any barriers that may follow the basic block. */
1709 tmp
= next_nonnote_insn (end
);
1710 while (tmp
&& BARRIER_P (tmp
))
1713 tmp
= next_nonnote_insn (end
);
1719 /* Verify the CFG and RTL consistency common for both underlying RTL and
1722 Currently it does following checks:
1724 - overlapping of basic blocks
1725 - insns with wrong BLOCK_FOR_INSN pointers
1726 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1727 - tails of basic blocks (ensure that boundary is necessary)
1728 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1729 and NOTE_INSN_BASIC_BLOCK
1730 - verify that no fall_thru edge crosses hot/cold partition boundaries
1731 - verify that there are no pending RTL branch predictions
1733 In future it can be extended check a lot of other stuff as well
1734 (reachability of basic blocks, life information, etc. etc.). */
1737 rtl_verify_flow_info_1 (void)
1743 /* Check the general integrity of the basic blocks. */
1744 FOR_EACH_BB_REVERSE (bb
)
1748 if (!(bb
->flags
& BB_RTL
))
1750 error ("BB_RTL flag not set for block %d", bb
->index
);
1754 FOR_BB_INSNS (bb
, insn
)
1755 if (BLOCK_FOR_INSN (insn
) != bb
)
1757 error ("insn %d basic block pointer is %d, should be %d",
1759 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
1764 for (insn
= bb
->il
.rtl
->header
; insn
; insn
= NEXT_INSN (insn
))
1765 if (!BARRIER_P (insn
)
1766 && BLOCK_FOR_INSN (insn
) != NULL
)
1768 error ("insn %d in header of bb %d has non-NULL basic block",
1769 INSN_UID (insn
), bb
->index
);
1772 for (insn
= bb
->il
.rtl
->footer
; insn
; insn
= NEXT_INSN (insn
))
1773 if (!BARRIER_P (insn
)
1774 && BLOCK_FOR_INSN (insn
) != NULL
)
1776 error ("insn %d in footer of bb %d has non-NULL basic block",
1777 INSN_UID (insn
), bb
->index
);
1782 /* Now check the basic blocks (boundaries etc.) */
1783 FOR_EACH_BB_REVERSE (bb
)
1785 int n_fallthru
= 0, n_eh
= 0, n_call
= 0, n_abnormal
= 0, n_branch
= 0;
1786 edge e
, fallthru
= NULL
;
1790 if (JUMP_P (BB_END (bb
))
1791 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
1792 && EDGE_COUNT (bb
->succs
) >= 2
1793 && any_condjump_p (BB_END (bb
)))
1795 if (INTVAL (XEXP (note
, 0)) != BRANCH_EDGE (bb
)->probability
1796 && profile_status
!= PROFILE_ABSENT
)
1798 error ("verify_flow_info: REG_BR_PROB does not match cfg %wi %i",
1799 INTVAL (XEXP (note
, 0)), BRANCH_EDGE (bb
)->probability
);
1803 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1805 if (e
->flags
& EDGE_FALLTHRU
)
1807 n_fallthru
++, fallthru
= e
;
1808 if ((e
->flags
& EDGE_CROSSING
)
1809 || (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
1810 && e
->src
!= ENTRY_BLOCK_PTR
1811 && e
->dest
!= EXIT_BLOCK_PTR
))
1813 error ("fallthru edge crosses section boundary (bb %i)",
1819 if ((e
->flags
& ~(EDGE_DFS_BACK
1821 | EDGE_IRREDUCIBLE_LOOP
1823 | EDGE_CROSSING
)) == 0)
1826 if (e
->flags
& EDGE_ABNORMAL_CALL
)
1829 if (e
->flags
& EDGE_EH
)
1831 else if (e
->flags
& EDGE_ABNORMAL
)
1835 if (n_eh
&& GET_CODE (PATTERN (BB_END (bb
))) != RESX
1836 && !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
1838 error ("missing REG_EH_REGION note in the end of bb %i", bb
->index
);
1842 && (!JUMP_P (BB_END (bb
))
1843 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
1844 || any_condjump_p (BB_END (bb
))))))
1846 error ("too many outgoing branch edges from bb %i", bb
->index
);
1849 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
1851 error ("fallthru edge after unconditional jump %i", bb
->index
);
1854 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
1856 error ("wrong amount of branch edges after unconditional jump %i", bb
->index
);
1859 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
1860 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
1862 error ("wrong amount of branch edges after conditional jump %i",
1866 if (n_call
&& !CALL_P (BB_END (bb
)))
1868 error ("call edges for non-call insn in bb %i", bb
->index
);
1872 && (!CALL_P (BB_END (bb
)) && n_call
!= n_abnormal
)
1873 && (!JUMP_P (BB_END (bb
))
1874 || any_condjump_p (BB_END (bb
))
1875 || any_uncondjump_p (BB_END (bb
))))
1877 error ("abnormal edges for no purpose in bb %i", bb
->index
);
1881 for (x
= BB_HEAD (bb
); x
!= NEXT_INSN (BB_END (bb
)); x
= NEXT_INSN (x
))
1882 /* We may have a barrier inside a basic block before dead code
1883 elimination. There is no BLOCK_FOR_INSN field in a barrier. */
1884 if (!BARRIER_P (x
) && BLOCK_FOR_INSN (x
) != bb
)
1887 if (! BLOCK_FOR_INSN (x
))
1889 ("insn %d inside basic block %d but block_for_insn is NULL",
1890 INSN_UID (x
), bb
->index
);
1893 ("insn %d inside basic block %d but block_for_insn is %i",
1894 INSN_UID (x
), bb
->index
, BLOCK_FOR_INSN (x
)->index
);
1899 /* OK pointers are correct. Now check the header of basic
1900 block. It ought to contain optional CODE_LABEL followed
1901 by NOTE_BASIC_BLOCK. */
1905 if (BB_END (bb
) == x
)
1907 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1915 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
1917 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1922 if (BB_END (bb
) == x
)
1923 /* Do checks for empty blocks here. */
1926 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
1928 if (NOTE_INSN_BASIC_BLOCK_P (x
))
1930 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
1931 INSN_UID (x
), bb
->index
);
1935 if (x
== BB_END (bb
))
1938 if (control_flow_insn_p (x
))
1940 error ("in basic block %d:", bb
->index
);
1941 fatal_insn ("flow control insn inside a basic block", x
);
1950 /* Verify the CFG and RTL consistency common for both underlying RTL and
1953 Currently it does following checks:
1954 - all checks of rtl_verify_flow_info_1
1955 - test head/end pointers
1956 - check that all insns are in the basic blocks
1957 (except the switch handling code, barriers and notes)
1958 - check that all returns are followed by barriers
1959 - check that all fallthru edge points to the adjacent blocks. */
1962 rtl_verify_flow_info (void)
1965 int err
= rtl_verify_flow_info_1 ();
1967 rtx last_head
= get_last_insn ();
1968 basic_block
*bb_info
;
1970 const rtx rtx_first
= get_insns ();
1971 basic_block last_bb_seen
= ENTRY_BLOCK_PTR
, curr_bb
= NULL
;
1972 const int max_uid
= get_max_uid ();
1974 bb_info
= XCNEWVEC (basic_block
, max_uid
);
1976 FOR_EACH_BB_REVERSE (bb
)
1980 rtx head
= BB_HEAD (bb
);
1981 rtx end
= BB_END (bb
);
1983 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1985 /* Verify the end of the basic block is in the INSN chain. */
1989 /* And that the code outside of basic blocks has NULL bb field. */
1991 && BLOCK_FOR_INSN (x
) != NULL
)
1993 error ("insn %d outside of basic blocks has non-NULL bb field",
2001 error ("end insn %d for block %d not found in the insn stream",
2002 INSN_UID (end
), bb
->index
);
2006 /* Work backwards from the end to the head of the basic block
2007 to verify the head is in the RTL chain. */
2008 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2010 /* While walking over the insn chain, verify insns appear
2011 in only one basic block. */
2012 if (bb_info
[INSN_UID (x
)] != NULL
)
2014 error ("insn %d is in multiple basic blocks (%d and %d)",
2015 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2019 bb_info
[INSN_UID (x
)] = bb
;
2026 error ("head insn %d for block %d not found in the insn stream",
2027 INSN_UID (head
), bb
->index
);
2031 last_head
= PREV_INSN (x
);
2033 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2034 if (e
->flags
& EDGE_FALLTHRU
)
2040 /* Ensure existence of barrier in BB with no fallthru edges. */
2041 for (insn
= BB_END (bb
); !insn
|| !BARRIER_P (insn
);
2042 insn
= NEXT_INSN (insn
))
2044 || NOTE_INSN_BASIC_BLOCK_P (insn
))
2046 error ("missing barrier after block %i", bb
->index
);
2051 else if (e
->src
!= ENTRY_BLOCK_PTR
2052 && e
->dest
!= EXIT_BLOCK_PTR
)
2056 if (e
->src
->next_bb
!= e
->dest
)
2059 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2060 e
->src
->index
, e
->dest
->index
);
2064 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
2065 insn
= NEXT_INSN (insn
))
2066 if (BARRIER_P (insn
) || INSN_P (insn
))
2068 error ("verify_flow_info: Incorrect fallthru %i->%i",
2069 e
->src
->index
, e
->dest
->index
);
2070 fatal_insn ("wrong insn in the fallthru edge", insn
);
2076 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2078 /* Check that the code before the first basic block has NULL
2081 && BLOCK_FOR_INSN (x
) != NULL
)
2083 error ("insn %d outside of basic blocks has non-NULL bb field",
2091 last_bb_seen
= ENTRY_BLOCK_PTR
;
2093 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2095 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2097 bb
= NOTE_BASIC_BLOCK (x
);
2100 if (bb
!= last_bb_seen
->next_bb
)
2101 internal_error ("basic blocks not laid down consecutively");
2103 curr_bb
= last_bb_seen
= bb
;
2108 switch (GET_CODE (x
))
2115 /* An addr_vec is placed outside any basic block. */
2117 && JUMP_P (NEXT_INSN (x
))
2118 && (GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_DIFF_VEC
2119 || GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_VEC
))
2122 /* But in any case, non-deletable labels can appear anywhere. */
2126 fatal_insn ("insn outside basic block", x
);
2131 && returnjump_p (x
) && ! condjump_p (x
)
2132 && ! (next_nonnote_insn (x
) && BARRIER_P (next_nonnote_insn (x
))))
2133 fatal_insn ("return not followed by barrier", x
);
2134 if (curr_bb
&& x
== BB_END (curr_bb
))
2138 if (num_bb_notes
!= n_basic_blocks
- NUM_FIXED_BLOCKS
)
2140 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2141 num_bb_notes
, n_basic_blocks
);
2146 /* Assume that the preceding pass has possibly eliminated jump instructions
2147 or converted the unconditional jumps. Eliminate the edges from CFG.
2148 Return true if any edges are eliminated. */
2151 purge_dead_edges (basic_block bb
)
2154 rtx insn
= BB_END (bb
), note
;
2155 bool purged
= false;
2159 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2160 if (NONJUMP_INSN_P (insn
)
2161 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
2165 if (! may_trap_p (PATTERN (insn
))
2166 || ((eqnote
= find_reg_equal_equiv_note (insn
))
2167 && ! may_trap_p (XEXP (eqnote
, 0))))
2168 remove_note (insn
, note
);
2171 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
2172 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
2174 /* There are three types of edges we need to handle correctly here: EH
2175 edges, abnormal call EH edges, and abnormal call non-EH edges. The
2176 latter can appear when nonlocal gotos are used. */
2177 if (e
->flags
& EDGE_EH
)
2179 if (can_throw_internal (BB_END (bb
))
2180 /* If this is a call edge, verify that this is a call insn. */
2181 && (! (e
->flags
& EDGE_ABNORMAL_CALL
)
2182 || CALL_P (BB_END (bb
))))
2188 else if (e
->flags
& EDGE_ABNORMAL_CALL
)
2190 if (CALL_P (BB_END (bb
))
2191 && (! (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
))
2192 || INTVAL (XEXP (note
, 0)) >= 0))
2205 df_set_bb_dirty (bb
);
2215 /* We do care only about conditional jumps and simplejumps. */
2216 if (!any_condjump_p (insn
)
2217 && !returnjump_p (insn
)
2218 && !simplejump_p (insn
))
2221 /* Branch probability/prediction notes are defined only for
2222 condjumps. We've possibly turned condjump into simplejump. */
2223 if (simplejump_p (insn
))
2225 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2227 remove_note (insn
, note
);
2228 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
2229 remove_note (insn
, note
);
2232 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
2234 /* Avoid abnormal flags to leak from computed jumps turned
2235 into simplejumps. */
2237 e
->flags
&= ~EDGE_ABNORMAL
;
2239 /* See if this edge is one we should keep. */
2240 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
2241 /* A conditional jump can fall through into the next
2242 block, so we should keep the edge. */
2247 else if (e
->dest
!= EXIT_BLOCK_PTR
2248 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
2249 /* If the destination block is the target of the jump,
2255 else if (e
->dest
== EXIT_BLOCK_PTR
&& returnjump_p (insn
))
2256 /* If the destination block is the exit block, and this
2257 instruction is a return, then keep the edge. */
2262 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
2263 /* Keep the edges that correspond to exceptions thrown by
2264 this instruction and rematerialize the EDGE_ABNORMAL
2265 flag we just cleared above. */
2267 e
->flags
|= EDGE_ABNORMAL
;
2272 /* We do not need this edge. */
2273 df_set_bb_dirty (bb
);
2278 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
2282 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
2287 /* Redistribute probabilities. */
2288 if (single_succ_p (bb
))
2290 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
2291 single_succ_edge (bb
)->count
= bb
->count
;
2295 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2299 b
= BRANCH_EDGE (bb
);
2300 f
= FALLTHRU_EDGE (bb
);
2301 b
->probability
= INTVAL (XEXP (note
, 0));
2302 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
2303 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
2304 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
2309 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
2311 /* First, there should not be any EH or ABCALL edges resulting
2312 from non-local gotos and the like. If there were, we shouldn't
2313 have created the sibcall in the first place. Second, there
2314 should of course never have been a fallthru edge. */
2315 gcc_assert (single_succ_p (bb
));
2316 gcc_assert (single_succ_edge (bb
)->flags
2317 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
2322 /* If we don't see a jump insn, we don't know exactly why the block would
2323 have been broken at this point. Look for a simple, non-fallthru edge,
2324 as these are only created by conditional branches. If we find such an
2325 edge we know that there used to be a jump here and can then safely
2326 remove all non-fallthru edges. */
2328 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2329 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
2338 /* Remove all but the fake and fallthru edges. The fake edge may be
2339 the only successor for this block in the case of noreturn
2341 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
2343 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
2345 df_set_bb_dirty (bb
);
2353 gcc_assert (single_succ_p (bb
));
2355 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
2356 single_succ_edge (bb
)->count
= bb
->count
;
2359 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
2364 /* Search all basic blocks for potentially dead edges and purge them. Return
2365 true if some edge has been eliminated. */
2368 purge_all_dead_edges (void)
2375 bool purged_here
= purge_dead_edges (bb
);
2377 purged
|= purged_here
;
2383 /* Same as split_block but update cfg_layout structures. */
2386 cfg_layout_split_block (basic_block bb
, void *insnp
)
2388 rtx insn
= (rtx
) insnp
;
2389 basic_block new_bb
= rtl_split_block (bb
, insn
);
2391 new_bb
->il
.rtl
->footer
= bb
->il
.rtl
->footer
;
2392 bb
->il
.rtl
->footer
= NULL
;
2397 /* Redirect Edge to DEST. */
2399 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
2401 basic_block src
= e
->src
;
2404 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
2407 if (e
->dest
== dest
)
2410 if (e
->src
!= ENTRY_BLOCK_PTR
2411 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
2413 df_set_bb_dirty (src
);
2417 if (e
->src
== ENTRY_BLOCK_PTR
2418 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
2421 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
2422 e
->src
->index
, dest
->index
);
2424 df_set_bb_dirty (e
->src
);
2425 redirect_edge_succ (e
, dest
);
2429 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
2430 in the case the basic block appears to be in sequence. Avoid this
2433 if (e
->flags
& EDGE_FALLTHRU
)
2435 /* Redirect any branch edges unified with the fallthru one. */
2436 if (JUMP_P (BB_END (src
))
2437 && label_is_jump_target_p (BB_HEAD (e
->dest
),
2443 fprintf (dump_file
, "Fallthru edge unified with branch "
2444 "%i->%i redirected to %i\n",
2445 e
->src
->index
, e
->dest
->index
, dest
->index
);
2446 e
->flags
&= ~EDGE_FALLTHRU
;
2447 redirected
= redirect_branch_edge (e
, dest
);
2448 gcc_assert (redirected
);
2449 e
->flags
|= EDGE_FALLTHRU
;
2450 df_set_bb_dirty (e
->src
);
2453 /* In case we are redirecting fallthru edge to the branch edge
2454 of conditional jump, remove it. */
2455 if (EDGE_COUNT (src
->succs
) == 2)
2457 /* Find the edge that is different from E. */
2458 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
2461 && any_condjump_p (BB_END (src
))
2462 && onlyjump_p (BB_END (src
)))
2463 delete_insn (BB_END (src
));
2465 ret
= redirect_edge_succ_nodup (e
, dest
);
2467 fprintf (dump_file
, "Fallthru edge %i->%i redirected to %i\n",
2468 e
->src
->index
, e
->dest
->index
, dest
->index
);
2471 ret
= redirect_branch_edge (e
, dest
);
2473 /* We don't want simplejumps in the insn stream during cfglayout. */
2474 gcc_assert (!simplejump_p (BB_END (src
)));
2476 df_set_bb_dirty (src
);
2480 /* Simple wrapper as we always can redirect fallthru edges. */
2482 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
2484 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
2486 gcc_assert (redirected
);
2490 /* Same as delete_basic_block but update cfg_layout structures. */
2493 cfg_layout_delete_block (basic_block bb
)
2495 rtx insn
, next
, prev
= PREV_INSN (BB_HEAD (bb
)), *to
, remaints
;
2497 if (bb
->il
.rtl
->header
)
2499 next
= BB_HEAD (bb
);
2501 NEXT_INSN (prev
) = bb
->il
.rtl
->header
;
2503 set_first_insn (bb
->il
.rtl
->header
);
2504 PREV_INSN (bb
->il
.rtl
->header
) = prev
;
2505 insn
= bb
->il
.rtl
->header
;
2506 while (NEXT_INSN (insn
))
2507 insn
= NEXT_INSN (insn
);
2508 NEXT_INSN (insn
) = next
;
2509 PREV_INSN (next
) = insn
;
2511 next
= NEXT_INSN (BB_END (bb
));
2512 if (bb
->il
.rtl
->footer
)
2514 insn
= bb
->il
.rtl
->footer
;
2517 if (BARRIER_P (insn
))
2519 if (PREV_INSN (insn
))
2520 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
2522 bb
->il
.rtl
->footer
= NEXT_INSN (insn
);
2523 if (NEXT_INSN (insn
))
2524 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
2528 insn
= NEXT_INSN (insn
);
2530 if (bb
->il
.rtl
->footer
)
2533 NEXT_INSN (insn
) = bb
->il
.rtl
->footer
;
2534 PREV_INSN (bb
->il
.rtl
->footer
) = insn
;
2535 while (NEXT_INSN (insn
))
2536 insn
= NEXT_INSN (insn
);
2537 NEXT_INSN (insn
) = next
;
2539 PREV_INSN (next
) = insn
;
2541 set_last_insn (insn
);
2544 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
2545 to
= &bb
->next_bb
->il
.rtl
->header
;
2547 to
= &cfg_layout_function_footer
;
2549 rtl_delete_block (bb
);
2552 prev
= NEXT_INSN (prev
);
2554 prev
= get_insns ();
2556 next
= PREV_INSN (next
);
2558 next
= get_last_insn ();
2560 if (next
&& NEXT_INSN (next
) != prev
)
2562 remaints
= unlink_insn_chain (prev
, next
);
2564 while (NEXT_INSN (insn
))
2565 insn
= NEXT_INSN (insn
);
2566 NEXT_INSN (insn
) = *to
;
2568 PREV_INSN (*to
) = insn
;
2573 /* Return true when blocks A and B can be safely merged. */
2576 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
2578 /* If we are partitioning hot/cold basic blocks, we don't want to
2579 mess up unconditional or indirect jumps that cross between hot
2582 Basic block partitioning may result in some jumps that appear to
2583 be optimizable (or blocks that appear to be mergeable), but which really
2584 must be left untouched (they are required to make it safely across
2585 partition boundaries). See the comments at the top of
2586 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
2588 if (BB_PARTITION (a
) != BB_PARTITION (b
))
2591 /* There must be exactly one edge in between the blocks. */
2592 return (single_succ_p (a
)
2593 && single_succ (a
) == b
2594 && single_pred_p (b
) == 1
2596 /* Must be simple edge. */
2597 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
2598 && a
!= ENTRY_BLOCK_PTR
&& b
!= EXIT_BLOCK_PTR
2599 /* If the jump insn has side effects, we can't kill the edge.
2600 When not optimizing, try_redirect_by_replacing_jump will
2601 not allow us to redirect an edge by replacing a table jump. */
2602 && (!JUMP_P (BB_END (a
))
2603 || ((!optimize
|| reload_completed
)
2604 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
2607 /* Merge block A and B. The blocks must be mergeable. */
2610 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
2612 #ifdef ENABLE_CHECKING
2613 gcc_assert (cfg_layout_can_merge_blocks_p (a
, b
));
2617 fprintf (dump_file
, "merging block %d into block %d\n", b
->index
, a
->index
);
2619 /* If there was a CODE_LABEL beginning B, delete it. */
2620 if (LABEL_P (BB_HEAD (b
)))
2622 delete_insn (BB_HEAD (b
));
2625 /* We should have fallthru edge in a, or we can do dummy redirection to get
2627 if (JUMP_P (BB_END (a
)))
2628 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
2629 gcc_assert (!JUMP_P (BB_END (a
)));
2631 /* When not optimizing and the edge is the only place in RTL which holds
2632 some unique locus, emit a nop with that locus in between. */
2633 if (!optimize
&& EDGE_SUCC (a
, 0)->goto_locus
)
2635 rtx insn
= BB_END (a
), end
= PREV_INSN (BB_HEAD (a
));
2636 int goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
2638 while (insn
!= end
&& (!INSN_P (insn
) || INSN_LOCATOR (insn
) == 0))
2639 insn
= PREV_INSN (insn
);
2640 if (insn
!= end
&& locator_eq (INSN_LOCATOR (insn
), goto_locus
))
2645 end
= NEXT_INSN (BB_END (b
));
2646 while (insn
!= end
&& !INSN_P (insn
))
2647 insn
= NEXT_INSN (insn
);
2648 if (insn
!= end
&& INSN_LOCATOR (insn
) != 0
2649 && locator_eq (INSN_LOCATOR (insn
), goto_locus
))
2654 BB_END (a
) = emit_insn_after_noloc (gen_nop (), BB_END (a
), a
);
2655 INSN_LOCATOR (BB_END (a
)) = goto_locus
;
2659 /* Possible line number notes should appear in between. */
2660 if (b
->il
.rtl
->header
)
2662 rtx first
= BB_END (a
), last
;
2664 last
= emit_insn_after_noloc (b
->il
.rtl
->header
, BB_END (a
), a
);
2665 delete_insn_chain (NEXT_INSN (first
), last
, false);
2666 b
->il
.rtl
->header
= NULL
;
2669 /* In the case basic blocks are not adjacent, move them around. */
2670 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
2672 rtx first
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
2674 emit_insn_after_noloc (first
, BB_END (a
), a
);
2675 /* Skip possible DELETED_LABEL insn. */
2676 if (!NOTE_INSN_BASIC_BLOCK_P (first
))
2677 first
= NEXT_INSN (first
);
2678 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (first
));
2681 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
2682 We need to explicitly call. */
2683 update_bb_for_insn_chain (NEXT_INSN (first
),
2687 delete_insn (first
);
2689 /* Otherwise just re-associate the instructions. */
2694 update_bb_for_insn_chain (BB_HEAD (b
), BB_END (b
), a
);
2697 /* Skip possible DELETED_LABEL insn. */
2698 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
2699 insn
= NEXT_INSN (insn
);
2700 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
2702 BB_END (a
) = BB_END (b
);
2706 df_bb_delete (b
->index
);
2708 /* Possible tablejumps and barriers should appear after the block. */
2709 if (b
->il
.rtl
->footer
)
2711 if (!a
->il
.rtl
->footer
)
2712 a
->il
.rtl
->footer
= b
->il
.rtl
->footer
;
2715 rtx last
= a
->il
.rtl
->footer
;
2717 while (NEXT_INSN (last
))
2718 last
= NEXT_INSN (last
);
2719 NEXT_INSN (last
) = b
->il
.rtl
->footer
;
2720 PREV_INSN (b
->il
.rtl
->footer
) = last
;
2722 b
->il
.rtl
->footer
= NULL
;
2726 fprintf (dump_file
, "Merged blocks %d and %d.\n",
2727 a
->index
, b
->index
);
2733 cfg_layout_split_edge (edge e
)
2735 basic_block new_bb
=
2736 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR
2737 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
2740 if (e
->dest
== EXIT_BLOCK_PTR
)
2741 BB_COPY_PARTITION (new_bb
, e
->src
);
2743 BB_COPY_PARTITION (new_bb
, e
->dest
);
2744 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
2745 redirect_edge_and_branch_force (e
, new_bb
);
2750 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
2753 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
2757 /* Return 1 if BB ends with a call, possibly followed by some
2758 instructions that must stay with the call, 0 otherwise. */
2761 rtl_block_ends_with_call_p (basic_block bb
)
2763 rtx insn
= BB_END (bb
);
2765 while (!CALL_P (insn
)
2766 && insn
!= BB_HEAD (bb
)
2767 && (keep_with_call_p (insn
)
2769 insn
= PREV_INSN (insn
);
2770 return (CALL_P (insn
));
2773 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
2776 rtl_block_ends_with_condjump_p (const_basic_block bb
)
2778 return any_condjump_p (BB_END (bb
));
2781 /* Return true if we need to add fake edge to exit.
2782 Helper function for rtl_flow_call_edges_add. */
2785 need_fake_edge_p (const_rtx insn
)
2791 && !SIBLING_CALL_P (insn
)
2792 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
2793 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
2796 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
2797 && MEM_VOLATILE_P (PATTERN (insn
)))
2798 || (GET_CODE (PATTERN (insn
)) == PARALLEL
2799 && asm_noperands (insn
) != -1
2800 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
2801 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
2804 /* Add fake edges to the function exit for any non constant and non noreturn
2805 calls, volatile inline assembly in the bitmap of blocks specified by
2806 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
2809 The goal is to expose cases in which entering a basic block does not imply
2810 that all subsequent instructions must be executed. */
2813 rtl_flow_call_edges_add (sbitmap blocks
)
2816 int blocks_split
= 0;
2817 int last_bb
= last_basic_block
;
2818 bool check_last_block
= false;
2820 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
2824 check_last_block
= true;
2826 check_last_block
= TEST_BIT (blocks
, EXIT_BLOCK_PTR
->prev_bb
->index
);
2828 /* In the last basic block, before epilogue generation, there will be
2829 a fallthru edge to EXIT. Special care is required if the last insn
2830 of the last basic block is a call because make_edge folds duplicate
2831 edges, which would result in the fallthru edge also being marked
2832 fake, which would result in the fallthru edge being removed by
2833 remove_fake_edges, which would result in an invalid CFG.
2835 Moreover, we can't elide the outgoing fake edge, since the block
2836 profiler needs to take this into account in order to solve the minimal
2837 spanning tree in the case that the call doesn't return.
2839 Handle this by adding a dummy instruction in a new last basic block. */
2840 if (check_last_block
)
2842 basic_block bb
= EXIT_BLOCK_PTR
->prev_bb
;
2843 rtx insn
= BB_END (bb
);
2845 /* Back up past insns that must be kept in the same block as a call. */
2846 while (insn
!= BB_HEAD (bb
)
2847 && keep_with_call_p (insn
))
2848 insn
= PREV_INSN (insn
);
2850 if (need_fake_edge_p (insn
))
2854 e
= find_edge (bb
, EXIT_BLOCK_PTR
);
2857 insert_insn_on_edge (gen_use (const0_rtx
), e
);
2858 commit_edge_insertions ();
2863 /* Now add fake edges to the function exit for any non constant
2864 calls since there is no way that we can determine if they will
2867 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
2869 basic_block bb
= BASIC_BLOCK (i
);
2876 if (blocks
&& !TEST_BIT (blocks
, i
))
2879 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
2881 prev_insn
= PREV_INSN (insn
);
2882 if (need_fake_edge_p (insn
))
2885 rtx split_at_insn
= insn
;
2887 /* Don't split the block between a call and an insn that should
2888 remain in the same block as the call. */
2890 while (split_at_insn
!= BB_END (bb
)
2891 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
2892 split_at_insn
= NEXT_INSN (split_at_insn
);
2894 /* The handling above of the final block before the epilogue
2895 should be enough to verify that there is no edge to the exit
2896 block in CFG already. Calling make_edge in such case would
2897 cause us to mark that edge as fake and remove it later. */
2899 #ifdef ENABLE_CHECKING
2900 if (split_at_insn
== BB_END (bb
))
2902 e
= find_edge (bb
, EXIT_BLOCK_PTR
);
2903 gcc_assert (e
== NULL
);
2907 /* Note that the following may create a new basic block
2908 and renumber the existing basic blocks. */
2909 if (split_at_insn
!= BB_END (bb
))
2911 e
= split_block (bb
, split_at_insn
);
2916 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
2919 if (insn
== BB_HEAD (bb
))
2925 verify_flow_info ();
2927 return blocks_split
;
2930 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
2931 the conditional branch target, SECOND_HEAD should be the fall-thru
2932 there is no need to handle this here the loop versioning code handles
2933 this. the reason for SECON_HEAD is that it is needed for condition
2934 in trees, and this should be of the same type since it is a hook. */
2936 rtl_lv_add_condition_to_bb (basic_block first_head
,
2937 basic_block second_head ATTRIBUTE_UNUSED
,
2938 basic_block cond_bb
, void *comp_rtx
)
2940 rtx label
, seq
, jump
;
2941 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
2942 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
2943 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
2944 enum machine_mode mode
;
2947 label
= block_label (first_head
);
2948 mode
= GET_MODE (op0
);
2949 if (mode
== VOIDmode
)
2950 mode
= GET_MODE (op1
);
2953 op0
= force_operand (op0
, NULL_RTX
);
2954 op1
= force_operand (op1
, NULL_RTX
);
2955 do_compare_rtx_and_jump (op0
, op1
, comp
, 0,
2956 mode
, NULL_RTX
, NULL_RTX
, label
);
2957 jump
= get_last_insn ();
2958 JUMP_LABEL (jump
) = label
;
2959 LABEL_NUSES (label
)++;
2963 /* Add the new cond , in the new head. */
2964 emit_insn_after(seq
, BB_END(cond_bb
));
2968 /* Given a block B with unconditional branch at its end, get the
2969 store the return the branch edge and the fall-thru edge in
2970 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
2972 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
2973 edge
*fallthru_edge
)
2975 edge e
= EDGE_SUCC (b
, 0);
2977 if (e
->flags
& EDGE_FALLTHRU
)
2980 *branch_edge
= EDGE_SUCC (b
, 1);
2985 *fallthru_edge
= EDGE_SUCC (b
, 1);
2990 init_rtl_bb_info (basic_block bb
)
2992 gcc_assert (!bb
->il
.rtl
);
2993 bb
->il
.rtl
= GGC_CNEW (struct rtl_bb_info
);
2997 /* Add EXPR to the end of basic block BB. */
3000 insert_insn_end_bb_new (rtx pat
, basic_block bb
)
3002 rtx insn
= BB_END (bb
);
3006 while (NEXT_INSN (pat_end
) != NULL_RTX
)
3007 pat_end
= NEXT_INSN (pat_end
);
3009 /* If the last insn is a jump, insert EXPR in front [taking care to
3010 handle cc0, etc. properly]. Similarly we need to care trapping
3011 instructions in presence of non-call exceptions. */
3014 || (NONJUMP_INSN_P (insn
)
3015 && (!single_succ_p (bb
)
3016 || single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
)))
3021 /* If this is a jump table, then we can't insert stuff here. Since
3022 we know the previous real insn must be the tablejump, we insert
3023 the new instruction just before the tablejump. */
3024 if (GET_CODE (PATTERN (insn
)) == ADDR_VEC
3025 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
)
3026 insn
= prev_real_insn (insn
);
3029 /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts
3030 if cc0 isn't set. */
3031 note
= find_reg_note (insn
, REG_CC_SETTER
, NULL_RTX
);
3033 insn
= XEXP (note
, 0);
3036 rtx maybe_cc0_setter
= prev_nonnote_insn (insn
);
3037 if (maybe_cc0_setter
3038 && INSN_P (maybe_cc0_setter
)
3039 && sets_cc0_p (PATTERN (maybe_cc0_setter
)))
3040 insn
= maybe_cc0_setter
;
3043 /* FIXME: What if something in cc0/jump uses value set in new
3045 new_insn
= emit_insn_before_noloc (pat
, insn
, bb
);
3048 /* Likewise if the last insn is a call, as will happen in the presence
3049 of exception handling. */
3050 else if (CALL_P (insn
)
3051 && (!single_succ_p (bb
)
3052 || single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
))
3054 /* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers,
3055 we search backward and place the instructions before the first
3056 parameter is loaded. Do this for everyone for consistency and a
3057 presumption that we'll get better code elsewhere as well. */
3059 /* Since different machines initialize their parameter registers
3060 in different orders, assume nothing. Collect the set of all
3061 parameter registers. */
3062 insn
= find_first_parameter_load (insn
, BB_HEAD (bb
));
3064 /* If we found all the parameter loads, then we want to insert
3065 before the first parameter load.
3067 If we did not find all the parameter loads, then we might have
3068 stopped on the head of the block, which could be a CODE_LABEL.
3069 If we inserted before the CODE_LABEL, then we would be putting
3070 the insn in the wrong basic block. In that case, put the insn
3071 after the CODE_LABEL. Also, respect NOTE_INSN_BASIC_BLOCK. */
3072 while (LABEL_P (insn
)
3073 || NOTE_INSN_BASIC_BLOCK_P (insn
))
3074 insn
= NEXT_INSN (insn
);
3076 new_insn
= emit_insn_before_noloc (pat
, insn
, bb
);
3079 new_insn
= emit_insn_after_noloc (pat
, insn
, bb
);
3084 /* Returns true if it is possible to remove edge E by redirecting
3085 it to the destination of the other edge from E->src. */
3088 rtl_can_remove_branch_p (const_edge e
)
3090 const_basic_block src
= e
->src
;
3091 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
3092 const_rtx insn
= BB_END (src
), set
;
3094 /* The conditions are taken from try_redirect_by_replacing_jump. */
3095 if (target
== EXIT_BLOCK_PTR
)
3098 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
3101 if (find_reg_note (insn
, REG_CROSSING_JUMP
, NULL_RTX
)
3102 || BB_PARTITION (src
) != BB_PARTITION (target
))
3105 if (!onlyjump_p (insn
)
3106 || tablejump_p (insn
, NULL
, NULL
))
3109 set
= single_set (insn
);
3110 if (!set
|| side_effects_p (set
))
3116 /* Implementation of CFG manipulation for linearized RTL. */
3117 struct cfg_hooks rtl_cfg_hooks
= {
3119 rtl_verify_flow_info
,
3121 rtl_create_basic_block
,
3122 rtl_redirect_edge_and_branch
,
3123 rtl_redirect_edge_and_branch_force
,
3124 rtl_can_remove_branch_p
,
3127 rtl_move_block_after
,
3128 rtl_can_merge_blocks
, /* can_merge_blocks_p */
3132 NULL
, /* can_duplicate_block_p */
3133 NULL
, /* duplicate_block */
3135 rtl_make_forwarder_block
,
3136 rtl_tidy_fallthru_edge
,
3137 rtl_block_ends_with_call_p
,
3138 rtl_block_ends_with_condjump_p
,
3139 rtl_flow_call_edges_add
,
3140 NULL
, /* execute_on_growing_pred */
3141 NULL
, /* execute_on_shrinking_pred */
3142 NULL
, /* duplicate loop for trees */
3143 NULL
, /* lv_add_condition_to_bb */
3144 NULL
, /* lv_adjust_loop_header_phi*/
3145 NULL
, /* extract_cond_bb_edges */
3146 NULL
/* flush_pending_stmts */
3149 /* Implementation of CFG manipulation for cfg layout RTL, where
3150 basic block connected via fallthru edges does not have to be adjacent.
3151 This representation will hopefully become the default one in future
3152 version of the compiler. */
3154 /* We do not want to declare these functions in a header file, since they
3155 should only be used through the cfghooks interface, and we do not want to
3156 move them here since it would require also moving quite a lot of related
3157 code. They are in cfglayout.c. */
3158 extern bool cfg_layout_can_duplicate_bb_p (const_basic_block
);
3159 extern basic_block
cfg_layout_duplicate_bb (basic_block
);
3161 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
3163 rtl_verify_flow_info_1
,
3165 cfg_layout_create_basic_block
,
3166 cfg_layout_redirect_edge_and_branch
,
3167 cfg_layout_redirect_edge_and_branch_force
,
3168 rtl_can_remove_branch_p
,
3169 cfg_layout_delete_block
,
3170 cfg_layout_split_block
,
3171 rtl_move_block_after
,
3172 cfg_layout_can_merge_blocks_p
,
3173 cfg_layout_merge_blocks
,
3176 cfg_layout_can_duplicate_bb_p
,
3177 cfg_layout_duplicate_bb
,
3178 cfg_layout_split_edge
,
3179 rtl_make_forwarder_block
,
3181 rtl_block_ends_with_call_p
,
3182 rtl_block_ends_with_condjump_p
,
3183 rtl_flow_call_edges_add
,
3184 NULL
, /* execute_on_growing_pred */
3185 NULL
, /* execute_on_shrinking_pred */
3186 duplicate_loop_to_header_edge
, /* duplicate loop for trees */
3187 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
3188 NULL
, /* lv_adjust_loop_header_phi*/
3189 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
3190 NULL
/* flush_pending_stmts */