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 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
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-config.h"
57 #include "cfglayout.h"
62 #include "tree-pass.h"
64 static int can_delete_note_p (rtx
);
65 static int can_delete_label_p (rtx
);
66 static void commit_one_edge_insertion (edge
, int);
67 static basic_block
rtl_split_edge (edge
);
68 static bool rtl_move_block_after (basic_block
, basic_block
);
69 static int rtl_verify_flow_info (void);
70 static basic_block
cfg_layout_split_block (basic_block
, void *);
71 static edge
cfg_layout_redirect_edge_and_branch (edge
, basic_block
);
72 static basic_block
cfg_layout_redirect_edge_and_branch_force (edge
, basic_block
);
73 static void cfg_layout_delete_block (basic_block
);
74 static void rtl_delete_block (basic_block
);
75 static basic_block
rtl_redirect_edge_and_branch_force (edge
, basic_block
);
76 static edge
rtl_redirect_edge_and_branch (edge
, basic_block
);
77 static basic_block
rtl_split_block (basic_block
, void *);
78 static void rtl_dump_bb (basic_block
, FILE *, int);
79 static int rtl_verify_flow_info_1 (void);
80 static void mark_killed_regs (rtx
, rtx
, 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 (rtx note
)
89 return (NOTE_LINE_NUMBER (note
) == NOTE_INSN_DELETED
90 || NOTE_LINE_NUMBER (note
) == NOTE_INSN_BASIC_BLOCK
);
93 /* True if a given label can be deleted. */
96 can_delete_label_p (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_LINE_NUMBER (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 && LABEL_P (JUMP_LABEL (insn
)))
144 LABEL_NUSES (JUMP_LABEL (insn
))--;
146 /* Also if deleting an insn that references a label. */
149 while ((note
= find_reg_note (insn
, REG_LABEL
, NULL_RTX
)) != NULL_RTX
150 && LABEL_P (XEXP (note
, 0)))
152 LABEL_NUSES (XEXP (note
, 0))--;
153 remove_note (insn
, note
);
158 && (GET_CODE (PATTERN (insn
)) == ADDR_VEC
159 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
))
161 rtx pat
= PATTERN (insn
);
162 int diff_vec_p
= GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
;
163 int len
= XVECLEN (pat
, diff_vec_p
);
166 for (i
= 0; i
< len
; i
++)
168 rtx label
= XEXP (XVECEXP (pat
, diff_vec_p
, i
), 0);
170 /* When deleting code in bulk (e.g. removing many unreachable
171 blocks) we can delete a label that's a target of the vector
172 before deleting the vector itself. */
174 LABEL_NUSES (label
)--;
181 /* Like delete_insn but also purge dead edges from BB. */
183 delete_insn_and_edges (rtx insn
)
189 && BLOCK_FOR_INSN (insn
)
190 && BB_END (BLOCK_FOR_INSN (insn
)) == insn
)
192 x
= delete_insn (insn
);
194 purge_dead_edges (BLOCK_FOR_INSN (insn
));
198 /* Unlink a chain of insns between START and FINISH, leaving notes
199 that must be paired. */
202 delete_insn_chain (rtx start
, rtx finish
)
206 /* Unchain the insns one by one. It would be quicker to delete all of these
207 with a single unchaining, rather than one at a time, but we need to keep
211 next
= NEXT_INSN (start
);
212 if (NOTE_P (start
) && !can_delete_note_p (start
))
215 next
= delete_insn (start
);
223 /* Like delete_insn but also purge dead edges from BB. */
225 delete_insn_chain_and_edges (rtx first
, rtx last
)
230 && BLOCK_FOR_INSN (last
)
231 && BB_END (BLOCK_FOR_INSN (last
)) == last
)
233 delete_insn_chain (first
, last
);
235 purge_dead_edges (BLOCK_FOR_INSN (last
));
238 /* Create a new basic block consisting of the instructions between HEAD and END
239 inclusive. This function is designed to allow fast BB construction - reuses
240 the note and basic block struct in BB_NOTE, if any and do not grow
241 BASIC_BLOCK chain and should be used directly only by CFG construction code.
242 END can be NULL in to create new empty basic block before HEAD. Both END
243 and HEAD can be NULL to create basic block at the end of INSN chain.
244 AFTER is the basic block we should be put after. */
247 create_basic_block_structure (rtx head
, rtx end
, rtx bb_note
, basic_block after
)
252 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
255 /* If we found an existing note, thread it back onto the chain. */
263 after
= PREV_INSN (head
);
267 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
268 reorder_insns_nobb (bb_note
, bb_note
, after
);
272 /* Otherwise we must create a note and a basic block structure. */
276 init_rtl_bb_info (bb
);
279 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
280 else if (LABEL_P (head
) && end
)
282 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
288 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
294 NOTE_BASIC_BLOCK (bb_note
) = bb
;
297 /* Always include the bb note in the block. */
298 if (NEXT_INSN (end
) == bb_note
)
303 bb
->index
= last_basic_block
++;
304 bb
->flags
= BB_NEW
| BB_RTL
;
305 link_block (bb
, after
);
306 SET_BASIC_BLOCK (bb
->index
, bb
);
307 update_bb_for_insn (bb
);
308 BB_SET_PARTITION (bb
, BB_UNPARTITIONED
);
310 /* Tag the block so that we know it has been used when considering
311 other basic block notes. */
317 /* Create new basic block consisting of instructions in between HEAD and END
318 and place it to the BB chain after block AFTER. END can be NULL in to
319 create new empty basic block before HEAD. Both END and HEAD can be NULL to
320 create basic block at the end of INSN chain. */
323 rtl_create_basic_block (void *headp
, void *endp
, basic_block after
)
325 rtx head
= headp
, end
= endp
;
328 /* Grow the basic block array if needed. */
329 if ((size_t) last_basic_block
>= VEC_length (basic_block
, basic_block_info
))
331 size_t old_size
= VEC_length (basic_block
, basic_block_info
);
332 size_t new_size
= last_basic_block
+ (last_basic_block
+ 3) / 4;
334 VEC_safe_grow (basic_block
, gc
, basic_block_info
, new_size
);
335 p
= VEC_address (basic_block
, basic_block_info
);
336 memset (&p
[old_size
], 0, sizeof (basic_block
) * (new_size
- old_size
));
341 bb
= create_basic_block_structure (head
, end
, NULL
, after
);
347 cfg_layout_create_basic_block (void *head
, void *end
, basic_block after
)
349 basic_block newbb
= rtl_create_basic_block (head
, end
, after
);
354 /* Delete the insns in a (non-live) block. We physically delete every
355 non-deleted-note insn, and update the flow graph appropriately.
357 Return nonzero if we deleted an exception handler. */
359 /* ??? Preserving all such notes strikes me as wrong. It would be nice
360 to post-process the stream to remove empty blocks, loops, ranges, etc. */
363 rtl_delete_block (basic_block b
)
367 /* If the head of this block is a CODE_LABEL, then it might be the
368 label for an exception handler which can't be reached. We need
369 to remove the label from the exception_handler_label list. */
372 maybe_remove_eh_handler (insn
);
374 /* Include any jump table following the basic block. */
376 if (tablejump_p (end
, NULL
, &tmp
))
379 /* Include any barriers that may follow the basic block. */
380 tmp
= next_nonnote_insn (end
);
381 while (tmp
&& BARRIER_P (tmp
))
384 tmp
= next_nonnote_insn (end
);
387 /* Selectively delete the entire chain. */
389 delete_insn_chain (insn
, end
);
392 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
395 compute_bb_for_insn (void)
401 rtx end
= BB_END (bb
);
404 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
406 BLOCK_FOR_INSN (insn
) = bb
;
413 /* Release the basic_block_for_insn array. */
416 free_bb_for_insn (void)
419 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
420 if (!BARRIER_P (insn
))
421 BLOCK_FOR_INSN (insn
) = NULL
;
425 struct tree_opt_pass pass_free_cfg
=
429 free_bb_for_insn
, /* execute */
432 0, /* static_pass_number */
434 0, /* properties_required */
435 0, /* properties_provided */
436 PROP_cfg
, /* properties_destroyed */
437 0, /* todo_flags_start */
438 0, /* todo_flags_finish */
442 /* Return RTX to emit after when we want to emit code on the entry of function. */
444 entry_of_function (void)
446 return (n_basic_blocks
> NUM_FIXED_BLOCKS
?
447 BB_HEAD (ENTRY_BLOCK_PTR
->next_bb
) : get_insns ());
450 /* Update insns block within BB. */
453 update_bb_for_insn (basic_block bb
)
457 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
459 if (!BARRIER_P (insn
))
460 set_block_for_insn (insn
, bb
);
461 if (insn
== BB_END (bb
))
466 /* Creates a new basic block just after basic block B by splitting
467 everything after specified instruction I. */
470 rtl_split_block (basic_block bb
, void *insnp
)
479 insn
= first_insn_after_basic_block_note (bb
);
482 insn
= PREV_INSN (insn
);
484 insn
= get_last_insn ();
487 /* We probably should check type of the insn so that we do not create
488 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
490 if (insn
== BB_END (bb
))
491 emit_note_after (NOTE_INSN_DELETED
, insn
);
493 /* Create the new basic block. */
494 new_bb
= create_basic_block (NEXT_INSN (insn
), BB_END (bb
), bb
);
495 BB_COPY_PARTITION (new_bb
, bb
);
498 /* Redirect the outgoing edges. */
499 new_bb
->succs
= bb
->succs
;
501 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
504 if (bb
->il
.rtl
->global_live_at_start
)
506 new_bb
->il
.rtl
->global_live_at_start
= ALLOC_REG_SET (®_obstack
);
507 new_bb
->il
.rtl
->global_live_at_end
= ALLOC_REG_SET (®_obstack
);
508 COPY_REG_SET (new_bb
->il
.rtl
->global_live_at_end
, bb
->il
.rtl
->global_live_at_end
);
510 /* We now have to calculate which registers are live at the end
511 of the split basic block and at the start of the new basic
512 block. Start with those registers that are known to be live
513 at the end of the original basic block and get
514 propagate_block to determine which registers are live. */
515 COPY_REG_SET (new_bb
->il
.rtl
->global_live_at_start
, bb
->il
.rtl
->global_live_at_end
);
516 propagate_block (new_bb
, new_bb
->il
.rtl
->global_live_at_start
, NULL
, NULL
, 0);
517 COPY_REG_SET (bb
->il
.rtl
->global_live_at_end
,
518 new_bb
->il
.rtl
->global_live_at_start
);
519 #ifdef HAVE_conditional_execution
520 /* In the presence of conditional execution we are not able to update
521 liveness precisely. */
522 if (reload_completed
)
524 bb
->flags
|= BB_DIRTY
;
525 new_bb
->flags
|= BB_DIRTY
;
533 /* Blocks A and B are to be merged into a single block A. The insns
534 are already contiguous. */
537 rtl_merge_blocks (basic_block a
, basic_block b
)
539 rtx b_head
= BB_HEAD (b
), b_end
= BB_END (b
), a_end
= BB_END (a
);
540 rtx del_first
= NULL_RTX
, del_last
= NULL_RTX
;
543 /* If there was a CODE_LABEL beginning B, delete it. */
544 if (LABEL_P (b_head
))
546 /* This might have been an EH label that no longer has incoming
547 EH edges. Update data structures to match. */
548 maybe_remove_eh_handler (b_head
);
550 /* Detect basic blocks with nothing but a label. This can happen
551 in particular at the end of a function. */
555 del_first
= del_last
= b_head
;
556 b_head
= NEXT_INSN (b_head
);
559 /* Delete the basic block note and handle blocks containing just that
561 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
569 b_head
= NEXT_INSN (b_head
);
572 /* If there was a jump out of A, delete it. */
577 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
579 || NOTE_LINE_NUMBER (prev
) == NOTE_INSN_BASIC_BLOCK
580 || prev
== BB_HEAD (a
))
586 /* If this was a conditional jump, we need to also delete
587 the insn that set cc0. */
588 if (only_sets_cc0_p (prev
))
592 prev
= prev_nonnote_insn (prev
);
599 a_end
= PREV_INSN (del_first
);
601 else if (BARRIER_P (NEXT_INSN (a_end
)))
602 del_first
= NEXT_INSN (a_end
);
604 /* Delete everything marked above as well as crap that might be
605 hanging out between the two blocks. */
607 delete_insn_chain (del_first
, del_last
);
609 /* Reassociate the insns of B with A. */
614 for (x
= a_end
; x
!= b_end
; x
= NEXT_INSN (x
))
615 set_block_for_insn (x
, a
);
617 set_block_for_insn (b_end
, a
);
623 a
->il
.rtl
->global_live_at_end
= b
->il
.rtl
->global_live_at_end
;
626 /* Return true when block A and B can be merged. */
628 rtl_can_merge_blocks (basic_block a
,basic_block b
)
630 /* If we are partitioning hot/cold basic blocks, we don't want to
631 mess up unconditional or indirect jumps that cross between hot
634 Basic block partitioning may result in some jumps that appear to
635 be optimizable (or blocks that appear to be mergeable), but which really
636 must be left untouched (they are required to make it safely across
637 partition boundaries). See the comments at the top of
638 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
640 if (BB_PARTITION (a
) != BB_PARTITION (b
))
643 /* There must be exactly one edge in between the blocks. */
644 return (single_succ_p (a
)
645 && single_succ (a
) == b
648 /* Must be simple edge. */
649 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
651 && a
!= ENTRY_BLOCK_PTR
&& b
!= EXIT_BLOCK_PTR
652 /* If the jump insn has side effects,
653 we can't kill the edge. */
654 && (!JUMP_P (BB_END (a
))
656 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
659 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
663 block_label (basic_block block
)
665 if (block
== EXIT_BLOCK_PTR
)
668 if (!LABEL_P (BB_HEAD (block
)))
670 BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
673 return BB_HEAD (block
);
676 /* Attempt to perform edge redirection by replacing possibly complex jump
677 instruction by unconditional jump or removing jump completely. This can
678 apply only if all edges now point to the same block. The parameters and
679 return values are equivalent to redirect_edge_and_branch. */
682 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
684 basic_block src
= e
->src
;
685 rtx insn
= BB_END (src
), kill_from
;
689 /* If we are partitioning hot/cold basic blocks, we don't want to
690 mess up unconditional or indirect jumps that cross between hot
693 Basic block partitioning may result in some jumps that appear to
694 be optimizable (or blocks that appear to be mergeable), but which really
695 must be left untouched (they are required to make it safely across
696 partition boundaries). See the comments at the top of
697 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
699 if (find_reg_note (insn
, REG_CROSSING_JUMP
, NULL_RTX
)
700 || BB_PARTITION (src
) != BB_PARTITION (target
))
703 /* We can replace or remove a complex jump only when we have exactly
704 two edges. Also, if we have exactly one outgoing edge, we can
706 if (EDGE_COUNT (src
->succs
) >= 3
707 /* Verify that all targets will be TARGET. Specifically, the
708 edge that is not E must also go to TARGET. */
709 || (EDGE_COUNT (src
->succs
) == 2
710 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
713 if (!onlyjump_p (insn
))
715 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
718 /* Avoid removing branch with side effects. */
719 set
= single_set (insn
);
720 if (!set
|| side_effects_p (set
))
723 /* In case we zap a conditional jump, we'll need to kill
724 the cc0 setter too. */
727 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
)))
728 kill_from
= PREV_INSN (insn
);
731 /* See if we can create the fallthru edge. */
732 if (in_cfglayout
|| can_fallthru (src
, target
))
735 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
738 /* Selectively unlink whole insn chain. */
741 rtx insn
= src
->il
.rtl
->footer
;
743 delete_insn_chain (kill_from
, BB_END (src
));
745 /* Remove barriers but keep jumptables. */
748 if (BARRIER_P (insn
))
750 if (PREV_INSN (insn
))
751 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
753 src
->il
.rtl
->footer
= NEXT_INSN (insn
);
754 if (NEXT_INSN (insn
))
755 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
759 insn
= NEXT_INSN (insn
);
763 delete_insn_chain (kill_from
, PREV_INSN (BB_HEAD (target
)));
766 /* If this already is simplejump, redirect it. */
767 else if (simplejump_p (insn
))
769 if (e
->dest
== target
)
772 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
773 INSN_UID (insn
), e
->dest
->index
, target
->index
);
774 if (!redirect_jump (insn
, block_label (target
), 0))
776 gcc_assert (target
== EXIT_BLOCK_PTR
);
781 /* Cannot do anything for target exit block. */
782 else if (target
== EXIT_BLOCK_PTR
)
785 /* Or replace possibly complicated jump insn by simple jump insn. */
788 rtx target_label
= block_label (target
);
789 rtx barrier
, label
, table
;
791 emit_jump_insn_after_noloc (gen_jump (target_label
), insn
);
792 JUMP_LABEL (BB_END (src
)) = target_label
;
793 LABEL_NUSES (target_label
)++;
795 fprintf (dump_file
, "Replacing insn %i by jump %i\n",
796 INSN_UID (insn
), INSN_UID (BB_END (src
)));
799 delete_insn_chain (kill_from
, insn
);
801 /* Recognize a tablejump that we are converting to a
802 simple jump and remove its associated CODE_LABEL
803 and ADDR_VEC or ADDR_DIFF_VEC. */
804 if (tablejump_p (insn
, &label
, &table
))
805 delete_insn_chain (label
, table
);
807 barrier
= next_nonnote_insn (BB_END (src
));
808 if (!barrier
|| !BARRIER_P (barrier
))
809 emit_barrier_after (BB_END (src
));
812 if (barrier
!= NEXT_INSN (BB_END (src
)))
814 /* Move the jump before barrier so that the notes
815 which originally were or were created before jump table are
816 inside the basic block. */
817 rtx new_insn
= BB_END (src
);
820 for (tmp
= NEXT_INSN (BB_END (src
)); tmp
!= barrier
;
821 tmp
= NEXT_INSN (tmp
))
822 set_block_for_insn (tmp
, src
);
824 NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
825 PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
827 NEXT_INSN (new_insn
) = barrier
;
828 NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
830 PREV_INSN (new_insn
) = PREV_INSN (barrier
);
831 PREV_INSN (barrier
) = new_insn
;
836 /* Keep only one edge out and set proper flags. */
837 if (!single_succ_p (src
))
839 gcc_assert (single_succ_p (src
));
841 e
= single_succ_edge (src
);
843 e
->flags
= EDGE_FALLTHRU
;
847 e
->probability
= REG_BR_PROB_BASE
;
848 e
->count
= src
->count
;
850 /* We don't want a block to end on a line-number note since that has
851 the potential of changing the code between -g and not -g. */
852 while (NOTE_P (BB_END (e
->src
))
853 && NOTE_LINE_NUMBER (BB_END (e
->src
)) >= 0)
854 delete_insn (BB_END (e
->src
));
856 if (e
->dest
!= target
)
857 redirect_edge_succ (e
, target
);
862 /* Redirect edge representing branch of (un)conditional jump or tablejump,
865 redirect_branch_edge (edge e
, basic_block target
)
868 rtx old_label
= BB_HEAD (e
->dest
);
869 basic_block src
= e
->src
;
870 rtx insn
= BB_END (src
);
872 /* We can only redirect non-fallthru edges of jump insn. */
873 if (e
->flags
& EDGE_FALLTHRU
)
875 else if (!JUMP_P (insn
))
878 /* Recognize a tablejump and adjust all matching cases. */
879 if (tablejump_p (insn
, NULL
, &tmp
))
883 rtx new_label
= block_label (target
);
885 if (target
== EXIT_BLOCK_PTR
)
887 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
888 vec
= XVEC (PATTERN (tmp
), 0);
890 vec
= XVEC (PATTERN (tmp
), 1);
892 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
893 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
895 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
896 --LABEL_NUSES (old_label
);
897 ++LABEL_NUSES (new_label
);
900 /* Handle casesi dispatch insns. */
901 if ((tmp
= single_set (insn
)) != NULL
902 && SET_DEST (tmp
) == pc_rtx
903 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
904 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
905 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
907 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
909 --LABEL_NUSES (old_label
);
910 ++LABEL_NUSES (new_label
);
915 /* ?? We may play the games with moving the named labels from
916 one basic block to the other in case only one computed_jump is
918 if (computed_jump_p (insn
)
919 /* A return instruction can't be redirected. */
920 || returnjump_p (insn
))
923 /* If the insn doesn't go where we think, we're confused. */
924 gcc_assert (JUMP_LABEL (insn
) == old_label
);
926 /* If the substitution doesn't succeed, die. This can happen
927 if the back end emitted unrecognizable instructions or if
928 target is exit block on some arches. */
929 if (!redirect_jump (insn
, block_label (target
), 0))
931 gcc_assert (target
== EXIT_BLOCK_PTR
);
937 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
938 e
->src
->index
, e
->dest
->index
, target
->index
);
940 if (e
->dest
!= target
)
941 e
= redirect_edge_succ_nodup (e
, target
);
945 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
946 expense of adding new instructions or reordering basic blocks.
948 Function can be also called with edge destination equivalent to the TARGET.
949 Then it should try the simplifications and do nothing if none is possible.
951 Return edge representing the branch if transformation succeeded. Return NULL
953 We still return NULL in case E already destinated TARGET and we didn't
954 managed to simplify instruction stream. */
957 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
960 basic_block src
= e
->src
;
962 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
965 if (e
->dest
== target
)
968 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
970 src
->flags
|= BB_DIRTY
;
974 ret
= redirect_branch_edge (e
, target
);
978 src
->flags
|= BB_DIRTY
;
982 /* Like force_nonfallthru below, but additionally performs redirection
983 Used by redirect_edge_and_branch_force. */
986 force_nonfallthru_and_redirect (edge e
, basic_block target
)
988 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
991 int abnormal_edge_flags
= 0;
993 /* In the case the last instruction is conditional jump to the next
994 instruction, first redirect the jump itself and then continue
995 by creating a basic block afterwards to redirect fallthru edge. */
996 if (e
->src
!= ENTRY_BLOCK_PTR
&& e
->dest
!= EXIT_BLOCK_PTR
997 && any_condjump_p (BB_END (e
->src
))
998 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1001 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1004 redirected
= redirect_jump (BB_END (e
->src
), block_label (target
), 0);
1005 gcc_assert (redirected
);
1007 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1010 int prob
= INTVAL (XEXP (note
, 0));
1012 b
->probability
= prob
;
1013 b
->count
= e
->count
* prob
/ REG_BR_PROB_BASE
;
1014 e
->probability
-= e
->probability
;
1015 e
->count
-= b
->count
;
1016 if (e
->probability
< 0)
1023 if (e
->flags
& EDGE_ABNORMAL
)
1025 /* Irritating special case - fallthru edge to the same block as abnormal
1027 We can't redirect abnormal edge, but we still can split the fallthru
1028 one and create separate abnormal edge to original destination.
1029 This allows bb-reorder to make such edge non-fallthru. */
1030 gcc_assert (e
->dest
== target
);
1031 abnormal_edge_flags
= e
->flags
& ~(EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
);
1032 e
->flags
&= EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
;
1036 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1037 if (e
->src
== ENTRY_BLOCK_PTR
)
1039 /* We can't redirect the entry block. Create an empty block
1040 at the start of the function which we use to add the new
1046 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
, ENTRY_BLOCK_PTR
);
1048 /* Change the existing edge's source to be the new block, and add
1049 a new edge from the entry block to the new block. */
1051 for (ei
= ei_start (ENTRY_BLOCK_PTR
->succs
); (tmp
= ei_safe_edge (ei
)); )
1055 VEC_unordered_remove (edge
, ENTRY_BLOCK_PTR
->succs
, ei
.index
);
1065 VEC_safe_push (edge
, gc
, bb
->succs
, e
);
1066 make_single_succ_edge (ENTRY_BLOCK_PTR
, bb
, EDGE_FALLTHRU
);
1070 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
)
1072 /* Create the new structures. */
1074 /* If the old block ended with a tablejump, skip its table
1075 by searching forward from there. Otherwise start searching
1076 forward from the last instruction of the old block. */
1077 if (!tablejump_p (BB_END (e
->src
), NULL
, ¬e
))
1078 note
= BB_END (e
->src
);
1079 note
= NEXT_INSN (note
);
1081 jump_block
= create_basic_block (note
, NULL
, e
->src
);
1082 jump_block
->count
= e
->count
;
1083 jump_block
->frequency
= EDGE_FREQUENCY (e
);
1084 jump_block
->loop_depth
= target
->loop_depth
;
1086 if (target
->il
.rtl
->global_live_at_start
)
1088 jump_block
->il
.rtl
->global_live_at_start
= ALLOC_REG_SET (®_obstack
);
1089 jump_block
->il
.rtl
->global_live_at_end
= ALLOC_REG_SET (®_obstack
);
1090 COPY_REG_SET (jump_block
->il
.rtl
->global_live_at_start
,
1091 target
->il
.rtl
->global_live_at_start
);
1092 COPY_REG_SET (jump_block
->il
.rtl
->global_live_at_end
,
1093 target
->il
.rtl
->global_live_at_start
);
1096 /* Make sure new block ends up in correct hot/cold section. */
1098 BB_COPY_PARTITION (jump_block
, e
->src
);
1099 if (flag_reorder_blocks_and_partition
1100 && targetm
.have_named_sections
1101 && JUMP_P (BB_END (jump_block
))
1102 && !any_condjump_p (BB_END (jump_block
))
1103 && (EDGE_SUCC (jump_block
, 0)->flags
& EDGE_CROSSING
))
1104 REG_NOTES (BB_END (jump_block
)) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP
,
1111 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1112 new_edge
->probability
= e
->probability
;
1113 new_edge
->count
= e
->count
;
1115 /* Redirect old edge. */
1116 redirect_edge_pred (e
, jump_block
);
1117 e
->probability
= REG_BR_PROB_BASE
;
1119 new_bb
= jump_block
;
1122 jump_block
= e
->src
;
1124 e
->flags
&= ~EDGE_FALLTHRU
;
1125 if (target
== EXIT_BLOCK_PTR
)
1128 emit_jump_insn_after_noloc (gen_return (), BB_END (jump_block
));
1135 rtx label
= block_label (target
);
1136 emit_jump_insn_after_noloc (gen_jump (label
), BB_END (jump_block
));
1137 JUMP_LABEL (BB_END (jump_block
)) = label
;
1138 LABEL_NUSES (label
)++;
1141 emit_barrier_after (BB_END (jump_block
));
1142 redirect_edge_succ_nodup (e
, target
);
1144 if (abnormal_edge_flags
)
1145 make_edge (src
, target
, abnormal_edge_flags
);
1150 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1151 (and possibly create new basic block) to make edge non-fallthru.
1152 Return newly created BB or NULL if none. */
1155 force_nonfallthru (edge e
)
1157 return force_nonfallthru_and_redirect (e
, e
->dest
);
1160 /* Redirect edge even at the expense of creating new jump insn or
1161 basic block. Return new basic block if created, NULL otherwise.
1162 Conversion must be possible. */
1165 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1167 if (redirect_edge_and_branch (e
, target
)
1168 || e
->dest
== target
)
1171 /* In case the edge redirection failed, try to force it to be non-fallthru
1172 and redirect newly created simplejump. */
1173 return force_nonfallthru_and_redirect (e
, target
);
1176 /* The given edge should potentially be a fallthru edge. If that is in
1177 fact true, delete the jump and barriers that are in the way. */
1180 rtl_tidy_fallthru_edge (edge e
)
1183 basic_block b
= e
->src
, c
= b
->next_bb
;
1185 /* ??? In a late-running flow pass, other folks may have deleted basic
1186 blocks by nopping out blocks, leaving multiple BARRIERs between here
1187 and the target label. They ought to be chastised and fixed.
1189 We can also wind up with a sequence of undeletable labels between
1190 one block and the next.
1192 So search through a sequence of barriers, labels, and notes for
1193 the head of block C and assert that we really do fall through. */
1195 for (q
= NEXT_INSN (BB_END (b
)); q
!= BB_HEAD (c
); q
= NEXT_INSN (q
))
1199 /* Remove what will soon cease being the jump insn from the source block.
1200 If block B consisted only of this single jump, turn it into a deleted
1205 && (any_uncondjump_p (q
)
1206 || single_succ_p (b
)))
1209 /* If this was a conditional jump, we need to also delete
1210 the insn that set cc0. */
1211 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1217 /* We don't want a block to end on a line-number note since that has
1218 the potential of changing the code between -g and not -g. */
1219 while (NOTE_P (q
) && NOTE_LINE_NUMBER (q
) >= 0)
1223 /* Selectively unlink the sequence. */
1224 if (q
!= PREV_INSN (BB_HEAD (c
)))
1225 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)));
1227 e
->flags
|= EDGE_FALLTHRU
;
1230 /* Should move basic block BB after basic block AFTER. NIY. */
1233 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1234 basic_block after ATTRIBUTE_UNUSED
)
1239 /* Split a (typically critical) edge. Return the new block.
1240 The edge must not be abnormal.
1242 ??? The code generally expects to be called on critical edges.
1243 The case of a block ending in an unconditional jump to a
1244 block with multiple predecessors is not handled optimally. */
1247 rtl_split_edge (edge edge_in
)
1252 /* Abnormal edges cannot be split. */
1253 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1255 /* We are going to place the new block in front of edge destination.
1256 Avoid existence of fallthru predecessors. */
1257 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1262 FOR_EACH_EDGE (e
, ei
, edge_in
->dest
->preds
)
1263 if (e
->flags
& EDGE_FALLTHRU
)
1267 force_nonfallthru (e
);
1270 /* Create the basic block note. */
1271 if (edge_in
->dest
!= EXIT_BLOCK_PTR
)
1272 before
= BB_HEAD (edge_in
->dest
);
1276 /* If this is a fall through edge to the exit block, the blocks might be
1277 not adjacent, and the right place is the after the source. */
1278 if (edge_in
->flags
& EDGE_FALLTHRU
&& edge_in
->dest
== EXIT_BLOCK_PTR
)
1280 before
= NEXT_INSN (BB_END (edge_in
->src
));
1281 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1282 BB_COPY_PARTITION (bb
, edge_in
->src
);
1286 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1287 /* ??? Why not edge_in->dest->prev_bb here? */
1288 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1291 /* ??? This info is likely going to be out of date very soon. */
1292 if (edge_in
->dest
->il
.rtl
->global_live_at_start
)
1294 bb
->il
.rtl
->global_live_at_start
= ALLOC_REG_SET (®_obstack
);
1295 bb
->il
.rtl
->global_live_at_end
= ALLOC_REG_SET (®_obstack
);
1296 COPY_REG_SET (bb
->il
.rtl
->global_live_at_start
,
1297 edge_in
->dest
->il
.rtl
->global_live_at_start
);
1298 COPY_REG_SET (bb
->il
.rtl
->global_live_at_end
,
1299 edge_in
->dest
->il
.rtl
->global_live_at_start
);
1302 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1304 /* For non-fallthru edges, we must adjust the predecessor's
1305 jump instruction to target our new block. */
1306 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1308 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1309 gcc_assert (redirected
);
1312 redirect_edge_succ (edge_in
, bb
);
1317 /* Queue instructions for insertion on an edge between two basic blocks.
1318 The new instructions and basic blocks (if any) will not appear in the
1319 CFG until commit_edge_insertions is called. */
1322 insert_insn_on_edge (rtx pattern
, edge e
)
1324 /* We cannot insert instructions on an abnormal critical edge.
1325 It will be easier to find the culprit if we die now. */
1326 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1328 if (e
->insns
.r
== NULL_RTX
)
1331 push_to_sequence (e
->insns
.r
);
1333 emit_insn (pattern
);
1335 e
->insns
.r
= get_insns ();
1339 /* Called from safe_insert_insn_on_edge through note_stores, marks live
1340 registers that are killed by the store. */
1342 mark_killed_regs (rtx reg
, rtx set ATTRIBUTE_UNUSED
, void *data
)
1344 regset killed
= data
;
1347 if (GET_CODE (reg
) == SUBREG
)
1348 reg
= SUBREG_REG (reg
);
1351 regno
= REGNO (reg
);
1352 if (regno
>= FIRST_PSEUDO_REGISTER
)
1353 SET_REGNO_REG_SET (killed
, regno
);
1356 for (i
= 0; i
< (int) hard_regno_nregs
[regno
][GET_MODE (reg
)]; i
++)
1357 SET_REGNO_REG_SET (killed
, regno
+ i
);
1361 /* Similar to insert_insn_on_edge, tries to put INSN to edge E. Additionally
1362 it checks whether this will not clobber the registers that are live on the
1363 edge (i.e. it requires liveness information to be up-to-date) and if there
1364 are some, then it tries to save and restore them. Returns true if
1367 safe_insert_insn_on_edge (rtx insn
, edge e
)
1371 rtx save_regs
= NULL_RTX
;
1373 enum machine_mode mode
;
1374 reg_set_iterator rsi
;
1376 killed
= ALLOC_REG_SET (®_obstack
);
1378 for (x
= insn
; x
; x
= NEXT_INSN (x
))
1380 note_stores (PATTERN (x
), mark_killed_regs
, killed
);
1382 /* Mark all hard registers as killed. Register allocator/reload cannot
1383 cope with the situation when life range of hard register spans operation
1384 for that the appropriate register is needed, i.e. it would be unsafe to
1385 extend the life ranges of hard registers. */
1386 for (regno
= 0; regno
< FIRST_PSEUDO_REGISTER
; regno
++)
1387 if (!fixed_regs
[regno
]
1388 && !REGNO_PTR_FRAME_P (regno
))
1389 SET_REGNO_REG_SET (killed
, regno
);
1391 bitmap_and_into (killed
, e
->dest
->il
.rtl
->global_live_at_start
);
1393 EXECUTE_IF_SET_IN_REG_SET (killed
, 0, regno
, rsi
)
1395 mode
= regno
< FIRST_PSEUDO_REGISTER
1396 ? reg_raw_mode
[regno
]
1397 : GET_MODE (regno_reg_rtx
[regno
]);
1398 if (mode
== VOIDmode
)
1401 /* Avoid copying in CCmode if we can't. */
1402 if (!can_copy_p (mode
))
1405 save_regs
= alloc_EXPR_LIST (0,
1408 gen_raw_REG (mode
, regno
)),
1417 for (x
= save_regs
; x
; x
= XEXP (x
, 1))
1419 from
= XEXP (XEXP (x
, 0), 1);
1420 to
= XEXP (XEXP (x
, 0), 0);
1421 emit_move_insn (to
, from
);
1424 for (x
= save_regs
; x
; x
= XEXP (x
, 1))
1426 from
= XEXP (XEXP (x
, 0), 0);
1427 to
= XEXP (XEXP (x
, 0), 1);
1428 emit_move_insn (to
, from
);
1430 insn
= get_insns ();
1432 free_EXPR_LIST_list (&save_regs
);
1434 insert_insn_on_edge (insn
, e
);
1436 FREE_REG_SET (killed
);
1441 /* Update the CFG for the instructions queued on edge E. */
1444 commit_one_edge_insertion (edge e
, int watch_calls
)
1446 rtx before
= NULL_RTX
, after
= NULL_RTX
, insns
, tmp
, last
;
1447 basic_block bb
= NULL
;
1449 /* Pull the insns off the edge now since the edge might go away. */
1451 e
->insns
.r
= NULL_RTX
;
1453 /* Special case -- avoid inserting code between call and storing
1454 its return value. */
1455 if (watch_calls
&& (e
->flags
& EDGE_FALLTHRU
)
1456 && single_pred_p (e
->dest
)
1457 && e
->src
!= ENTRY_BLOCK_PTR
1458 && CALL_P (BB_END (e
->src
)))
1460 rtx next
= next_nonnote_insn (BB_END (e
->src
));
1462 after
= BB_HEAD (e
->dest
);
1463 /* The first insn after the call may be a stack pop, skip it. */
1465 && keep_with_call_p (next
))
1468 next
= next_nonnote_insn (next
);
1472 if (!before
&& !after
)
1474 /* Figure out where to put these things. If the destination has
1475 one predecessor, insert there. Except for the exit block. */
1476 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR
)
1480 /* Get the location correct wrt a code label, and "nice" wrt
1481 a basic block note, and before everything else. */
1484 tmp
= NEXT_INSN (tmp
);
1485 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1486 tmp
= NEXT_INSN (tmp
);
1487 if (tmp
== BB_HEAD (bb
))
1490 after
= PREV_INSN (tmp
);
1492 after
= get_last_insn ();
1495 /* If the source has one successor and the edge is not abnormal,
1496 insert there. Except for the entry block. */
1497 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1498 && single_succ_p (e
->src
)
1499 && e
->src
!= ENTRY_BLOCK_PTR
)
1503 /* It is possible to have a non-simple jump here. Consider a target
1504 where some forms of unconditional jumps clobber a register. This
1505 happens on the fr30 for example.
1507 We know this block has a single successor, so we can just emit
1508 the queued insns before the jump. */
1509 if (JUMP_P (BB_END (bb
)))
1510 before
= BB_END (bb
);
1513 /* We'd better be fallthru, or we've lost track of
1515 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1517 after
= BB_END (bb
);
1520 /* Otherwise we must split the edge. */
1523 bb
= split_edge (e
);
1524 after
= BB_END (bb
);
1526 if (flag_reorder_blocks_and_partition
1527 && targetm
.have_named_sections
1528 && e
->src
!= ENTRY_BLOCK_PTR
1529 && BB_PARTITION (e
->src
) == BB_COLD_PARTITION
1530 && !(e
->flags
& EDGE_CROSSING
))
1532 rtx bb_note
, cur_insn
;
1535 for (cur_insn
= BB_HEAD (bb
); cur_insn
!= NEXT_INSN (BB_END (bb
));
1536 cur_insn
= NEXT_INSN (cur_insn
))
1537 if (NOTE_P (cur_insn
)
1538 && NOTE_LINE_NUMBER (cur_insn
) == NOTE_INSN_BASIC_BLOCK
)
1544 if (JUMP_P (BB_END (bb
))
1545 && !any_condjump_p (BB_END (bb
))
1546 && (single_succ_edge (bb
)->flags
& EDGE_CROSSING
))
1547 REG_NOTES (BB_END (bb
)) = gen_rtx_EXPR_LIST
1548 (REG_CROSSING_JUMP
, NULL_RTX
, REG_NOTES (BB_END (bb
)));
1553 /* Now that we've found the spot, do the insertion. */
1557 emit_insn_before_noloc (insns
, before
);
1558 last
= prev_nonnote_insn (before
);
1561 last
= emit_insn_after_noloc (insns
, after
);
1563 if (returnjump_p (last
))
1565 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1566 This is not currently a problem because this only happens
1567 for the (single) epilogue, which already has a fallthru edge
1570 e
= single_succ_edge (bb
);
1571 gcc_assert (e
->dest
== EXIT_BLOCK_PTR
1572 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
1574 e
->flags
&= ~EDGE_FALLTHRU
;
1575 emit_barrier_after (last
);
1578 delete_insn (before
);
1581 gcc_assert (!JUMP_P (last
));
1583 /* Mark the basic block for find_many_sub_basic_blocks. */
1587 /* Update the CFG for all queued instructions. */
1590 commit_edge_insertions (void)
1594 bool changed
= false;
1596 #ifdef ENABLE_CHECKING
1597 verify_flow_info ();
1600 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
1605 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1609 commit_one_edge_insertion (e
, false);
1616 blocks
= sbitmap_alloc (last_basic_block
);
1617 sbitmap_zero (blocks
);
1621 SET_BIT (blocks
, bb
->index
);
1622 /* Check for forgotten bb->aux values before commit_edge_insertions
1624 gcc_assert (bb
->aux
== &bb
->aux
);
1627 find_many_sub_basic_blocks (blocks
);
1628 sbitmap_free (blocks
);
1631 /* Update the CFG for all queued instructions, taking special care of inserting
1632 code on edges between call and storing its return value. */
1635 commit_edge_insertions_watch_calls (void)
1639 bool changed
= false;
1641 #ifdef ENABLE_CHECKING
1642 verify_flow_info ();
1645 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
1650 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1654 commit_one_edge_insertion (e
, true);
1661 blocks
= sbitmap_alloc (last_basic_block
);
1662 sbitmap_zero (blocks
);
1666 SET_BIT (blocks
, bb
->index
);
1667 /* Check for forgotten bb->aux values before commit_edge_insertions
1669 gcc_assert (bb
->aux
== &bb
->aux
);
1672 find_many_sub_basic_blocks (blocks
);
1673 sbitmap_free (blocks
);
1676 /* Print out RTL-specific basic block information (live information
1677 at start and end). */
1680 rtl_dump_bb (basic_block bb
, FILE *outf
, int indent
)
1686 s_indent
= alloca ((size_t) indent
+ 1);
1687 memset (s_indent
, ' ', (size_t) indent
);
1688 s_indent
[indent
] = '\0';
1690 fprintf (outf
, ";;%s Registers live at start: ", s_indent
);
1691 dump_regset (bb
->il
.rtl
->global_live_at_start
, outf
);
1694 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
)); insn
!= last
;
1695 insn
= NEXT_INSN (insn
))
1696 print_rtl_single (outf
, insn
);
1698 fprintf (outf
, ";;%s Registers live at end: ", s_indent
);
1699 dump_regset (bb
->il
.rtl
->global_live_at_end
, outf
);
1703 /* Like print_rtl, but also print out live information for the start of each
1707 print_rtl_with_bb (FILE *outf
, rtx rtx_first
)
1712 fprintf (outf
, "(nil)\n");
1715 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
1716 int max_uid
= get_max_uid ();
1717 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
1718 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
1719 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
1723 FOR_EACH_BB_REVERSE (bb
)
1727 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
1728 end
[INSN_UID (BB_END (bb
))] = bb
;
1729 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
1731 enum bb_state state
= IN_MULTIPLE_BB
;
1733 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
1735 in_bb_p
[INSN_UID (x
)] = state
;
1737 if (x
== BB_END (bb
))
1742 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
1746 if ((bb
= start
[INSN_UID (tmp_rtx
)]) != NULL
)
1748 fprintf (outf
, ";; Start of basic block %d, registers live:",
1750 dump_regset (bb
->il
.rtl
->global_live_at_start
, outf
);
1754 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
1755 && !NOTE_P (tmp_rtx
)
1756 && !BARRIER_P (tmp_rtx
))
1757 fprintf (outf
, ";; Insn is not within a basic block\n");
1758 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
1759 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
1761 did_output
= print_rtl_single (outf
, tmp_rtx
);
1763 if ((bb
= end
[INSN_UID (tmp_rtx
)]) != NULL
)
1765 fprintf (outf
, ";; End of basic block %d, registers live:\n",
1767 dump_regset (bb
->il
.rtl
->global_live_at_end
, outf
);
1780 if (current_function_epilogue_delay_list
!= 0)
1782 fprintf (outf
, "\n;; Insns in epilogue delay list:\n\n");
1783 for (tmp_rtx
= current_function_epilogue_delay_list
; tmp_rtx
!= 0;
1784 tmp_rtx
= XEXP (tmp_rtx
, 1))
1785 print_rtl_single (outf
, XEXP (tmp_rtx
, 0));
1790 update_br_prob_note (basic_block bb
)
1793 if (!JUMP_P (BB_END (bb
)))
1795 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
1796 if (!note
|| INTVAL (XEXP (note
, 0)) == BRANCH_EDGE (bb
)->probability
)
1798 XEXP (note
, 0) = GEN_INT (BRANCH_EDGE (bb
)->probability
);
1801 /* Verify the CFG and RTL consistency common for both underlying RTL and
1804 Currently it does following checks:
1806 - test head/end pointers
1807 - overlapping of basic blocks
1808 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1809 - tails of basic blocks (ensure that boundary is necessary)
1810 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1811 and NOTE_INSN_BASIC_BLOCK
1812 - verify that no fall_thru edge crosses hot/cold partition boundaries
1814 In future it can be extended check a lot of other stuff as well
1815 (reachability of basic blocks, life information, etc. etc.). */
1818 rtl_verify_flow_info_1 (void)
1820 const int max_uid
= get_max_uid ();
1821 rtx last_head
= get_last_insn ();
1822 basic_block
*bb_info
;
1827 bb_info
= XCNEWVEC (basic_block
, max_uid
);
1829 FOR_EACH_BB_REVERSE (bb
)
1831 rtx head
= BB_HEAD (bb
);
1832 rtx end
= BB_END (bb
);
1834 /* Verify the end of the basic block is in the INSN chain. */
1835 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1839 if (!(bb
->flags
& BB_RTL
))
1841 error ("BB_RTL flag not set for block %d", bb
->index
);
1847 error ("end insn %d for block %d not found in the insn stream",
1848 INSN_UID (end
), bb
->index
);
1852 /* Work backwards from the end to the head of the basic block
1853 to verify the head is in the RTL chain. */
1854 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1856 /* While walking over the insn chain, verify insns appear
1857 in only one basic block and initialize the BB_INFO array
1858 used by other passes. */
1859 if (bb_info
[INSN_UID (x
)] != NULL
)
1861 error ("insn %d is in multiple basic blocks (%d and %d)",
1862 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
1866 bb_info
[INSN_UID (x
)] = bb
;
1873 error ("head insn %d for block %d not found in the insn stream",
1874 INSN_UID (head
), bb
->index
);
1881 /* Now check the basic blocks (boundaries etc.) */
1882 FOR_EACH_BB_REVERSE (bb
)
1884 int n_fallthru
= 0, n_eh
= 0, n_call
= 0, n_abnormal
= 0, n_branch
= 0;
1885 edge e
, fallthru
= NULL
;
1889 if (JUMP_P (BB_END (bb
))
1890 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
1891 && EDGE_COUNT (bb
->succs
) >= 2
1892 && any_condjump_p (BB_END (bb
)))
1894 if (INTVAL (XEXP (note
, 0)) != BRANCH_EDGE (bb
)->probability
1895 && profile_status
!= PROFILE_ABSENT
)
1897 error ("verify_flow_info: REG_BR_PROB does not match cfg %wi %i",
1898 INTVAL (XEXP (note
, 0)), BRANCH_EDGE (bb
)->probability
);
1902 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1904 if (e
->flags
& EDGE_FALLTHRU
)
1906 n_fallthru
++, fallthru
= e
;
1907 if ((e
->flags
& EDGE_CROSSING
)
1908 || (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
1909 && e
->src
!= ENTRY_BLOCK_PTR
1910 && e
->dest
!= EXIT_BLOCK_PTR
))
1912 error ("fallthru edge crosses section boundary (bb %i)",
1918 if ((e
->flags
& ~(EDGE_DFS_BACK
1920 | EDGE_IRREDUCIBLE_LOOP
1922 | EDGE_CROSSING
)) == 0)
1925 if (e
->flags
& EDGE_ABNORMAL_CALL
)
1928 if (e
->flags
& EDGE_EH
)
1930 else if (e
->flags
& EDGE_ABNORMAL
)
1934 if (n_eh
&& GET_CODE (PATTERN (BB_END (bb
))) != RESX
1935 && !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
1937 error ("missing REG_EH_REGION note in the end of bb %i", bb
->index
);
1941 && (!JUMP_P (BB_END (bb
))
1942 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
1943 || any_condjump_p (BB_END (bb
))))))
1945 error ("too many outgoing branch edges from bb %i", bb
->index
);
1948 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
1950 error ("fallthru edge after unconditional jump %i", bb
->index
);
1953 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
1955 error ("wrong amount of branch edges after unconditional jump %i", bb
->index
);
1958 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
1959 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
1961 error ("wrong amount of branch edges after conditional jump %i",
1965 if (n_call
&& !CALL_P (BB_END (bb
)))
1967 error ("call edges for non-call insn in bb %i", bb
->index
);
1971 && (!CALL_P (BB_END (bb
)) && n_call
!= n_abnormal
)
1972 && (!JUMP_P (BB_END (bb
))
1973 || any_condjump_p (BB_END (bb
))
1974 || any_uncondjump_p (BB_END (bb
))))
1976 error ("abnormal edges for no purpose in bb %i", bb
->index
);
1980 for (x
= BB_HEAD (bb
); x
!= NEXT_INSN (BB_END (bb
)); x
= NEXT_INSN (x
))
1981 /* We may have a barrier inside a basic block before dead code
1982 elimination. There is no BLOCK_FOR_INSN field in a barrier. */
1983 if (!BARRIER_P (x
) && BLOCK_FOR_INSN (x
) != bb
)
1986 if (! BLOCK_FOR_INSN (x
))
1988 ("insn %d inside basic block %d but block_for_insn is NULL",
1989 INSN_UID (x
), bb
->index
);
1992 ("insn %d inside basic block %d but block_for_insn is %i",
1993 INSN_UID (x
), bb
->index
, BLOCK_FOR_INSN (x
)->index
);
1998 /* OK pointers are correct. Now check the header of basic
1999 block. It ought to contain optional CODE_LABEL followed
2000 by NOTE_BASIC_BLOCK. */
2004 if (BB_END (bb
) == x
)
2006 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2014 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2016 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2021 if (BB_END (bb
) == x
)
2022 /* Do checks for empty blocks here. */
2025 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2027 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2029 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2030 INSN_UID (x
), bb
->index
);
2034 if (x
== BB_END (bb
))
2037 if (control_flow_insn_p (x
))
2039 error ("in basic block %d:", bb
->index
);
2040 fatal_insn ("flow control insn inside a basic block", x
);
2050 /* Verify the CFG and RTL consistency common for both underlying RTL and
2053 Currently it does following checks:
2054 - all checks of rtl_verify_flow_info_1
2055 - check that all insns are in the basic blocks
2056 (except the switch handling code, barriers and notes)
2057 - check that all returns are followed by barriers
2058 - check that all fallthru edge points to the adjacent blocks. */
2060 rtl_verify_flow_info (void)
2063 int err
= rtl_verify_flow_info_1 ();
2066 const rtx rtx_first
= get_insns ();
2067 basic_block last_bb_seen
= ENTRY_BLOCK_PTR
, curr_bb
= NULL
;
2069 FOR_EACH_BB_REVERSE (bb
)
2074 if (bb
->predictions
)
2076 error ("bb prediction set for block %i, but it is not used in RTL land", bb
->index
);
2080 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2081 if (e
->flags
& EDGE_FALLTHRU
)
2087 /* Ensure existence of barrier in BB with no fallthru edges. */
2088 for (insn
= BB_END (bb
); !insn
|| !BARRIER_P (insn
);
2089 insn
= NEXT_INSN (insn
))
2092 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BASIC_BLOCK
))
2094 error ("missing barrier after block %i", bb
->index
);
2099 else if (e
->src
!= ENTRY_BLOCK_PTR
2100 && e
->dest
!= EXIT_BLOCK_PTR
)
2104 if (e
->src
->next_bb
!= e
->dest
)
2107 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2108 e
->src
->index
, e
->dest
->index
);
2112 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
2113 insn
= NEXT_INSN (insn
))
2114 if (BARRIER_P (insn
) || INSN_P (insn
))
2116 error ("verify_flow_info: Incorrect fallthru %i->%i",
2117 e
->src
->index
, e
->dest
->index
);
2118 fatal_insn ("wrong insn in the fallthru edge", insn
);
2125 last_bb_seen
= ENTRY_BLOCK_PTR
;
2127 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2129 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2131 bb
= NOTE_BASIC_BLOCK (x
);
2134 if (bb
!= last_bb_seen
->next_bb
)
2135 internal_error ("basic blocks not laid down consecutively");
2137 curr_bb
= last_bb_seen
= bb
;
2142 switch (GET_CODE (x
))
2149 /* An addr_vec is placed outside any basic block. */
2151 && JUMP_P (NEXT_INSN (x
))
2152 && (GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_DIFF_VEC
2153 || GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_VEC
))
2156 /* But in any case, non-deletable labels can appear anywhere. */
2160 fatal_insn ("insn outside basic block", x
);
2165 && returnjump_p (x
) && ! condjump_p (x
)
2166 && ! (NEXT_INSN (x
) && BARRIER_P (NEXT_INSN (x
))))
2167 fatal_insn ("return not followed by barrier", x
);
2168 if (curr_bb
&& x
== BB_END (curr_bb
))
2172 if (num_bb_notes
!= n_basic_blocks
- NUM_FIXED_BLOCKS
)
2174 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2175 num_bb_notes
, n_basic_blocks
);
2180 /* Assume that the preceding pass has possibly eliminated jump instructions
2181 or converted the unconditional jumps. Eliminate the edges from CFG.
2182 Return true if any edges are eliminated. */
2185 purge_dead_edges (basic_block bb
)
2188 rtx insn
= BB_END (bb
), note
;
2189 bool purged
= false;
2193 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2194 if (NONJUMP_INSN_P (insn
)
2195 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
2199 if (! may_trap_p (PATTERN (insn
))
2200 || ((eqnote
= find_reg_equal_equiv_note (insn
))
2201 && ! may_trap_p (XEXP (eqnote
, 0))))
2202 remove_note (insn
, note
);
2205 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
2206 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
2208 /* There are three types of edges we need to handle correctly here: EH
2209 edges, abnormal call EH edges, and abnormal call non-EH edges. The
2210 latter can appear when nonlocal gotos are used. */
2211 if (e
->flags
& EDGE_EH
)
2213 if (can_throw_internal (BB_END (bb
))
2214 /* If this is a call edge, verify that this is a call insn. */
2215 && (! (e
->flags
& EDGE_ABNORMAL_CALL
)
2216 || CALL_P (BB_END (bb
))))
2222 else if (e
->flags
& EDGE_ABNORMAL_CALL
)
2224 if (CALL_P (BB_END (bb
))
2225 && (! (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
))
2226 || INTVAL (XEXP (note
, 0)) >= 0))
2239 bb
->flags
|= BB_DIRTY
;
2249 /* We do care only about conditional jumps and simplejumps. */
2250 if (!any_condjump_p (insn
)
2251 && !returnjump_p (insn
)
2252 && !simplejump_p (insn
))
2255 /* Branch probability/prediction notes are defined only for
2256 condjumps. We've possibly turned condjump into simplejump. */
2257 if (simplejump_p (insn
))
2259 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2261 remove_note (insn
, note
);
2262 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
2263 remove_note (insn
, note
);
2266 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
2268 /* Avoid abnormal flags to leak from computed jumps turned
2269 into simplejumps. */
2271 e
->flags
&= ~EDGE_ABNORMAL
;
2273 /* See if this edge is one we should keep. */
2274 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
2275 /* A conditional jump can fall through into the next
2276 block, so we should keep the edge. */
2281 else if (e
->dest
!= EXIT_BLOCK_PTR
2282 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
2283 /* If the destination block is the target of the jump,
2289 else if (e
->dest
== EXIT_BLOCK_PTR
&& returnjump_p (insn
))
2290 /* If the destination block is the exit block, and this
2291 instruction is a return, then keep the edge. */
2296 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
2297 /* Keep the edges that correspond to exceptions thrown by
2298 this instruction and rematerialize the EDGE_ABNORMAL
2299 flag we just cleared above. */
2301 e
->flags
|= EDGE_ABNORMAL
;
2306 /* We do not need this edge. */
2307 bb
->flags
|= BB_DIRTY
;
2312 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
2316 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
2321 /* Redistribute probabilities. */
2322 if (single_succ_p (bb
))
2324 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
2325 single_succ_edge (bb
)->count
= bb
->count
;
2329 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2333 b
= BRANCH_EDGE (bb
);
2334 f
= FALLTHRU_EDGE (bb
);
2335 b
->probability
= INTVAL (XEXP (note
, 0));
2336 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
2337 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
2338 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
2343 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
2345 /* First, there should not be any EH or ABCALL edges resulting
2346 from non-local gotos and the like. If there were, we shouldn't
2347 have created the sibcall in the first place. Second, there
2348 should of course never have been a fallthru edge. */
2349 gcc_assert (single_succ_p (bb
));
2350 gcc_assert (single_succ_edge (bb
)->flags
2351 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
2356 /* If we don't see a jump insn, we don't know exactly why the block would
2357 have been broken at this point. Look for a simple, non-fallthru edge,
2358 as these are only created by conditional branches. If we find such an
2359 edge we know that there used to be a jump here and can then safely
2360 remove all non-fallthru edges. */
2362 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2363 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
2372 /* Remove all but the fake and fallthru edges. The fake edge may be
2373 the only successor for this block in the case of noreturn
2375 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
2377 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
2379 bb
->flags
|= BB_DIRTY
;
2387 gcc_assert (single_succ_p (bb
));
2389 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
2390 single_succ_edge (bb
)->count
= bb
->count
;
2393 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
2398 /* Search all basic blocks for potentially dead edges and purge them. Return
2399 true if some edge has been eliminated. */
2402 purge_all_dead_edges (void)
2409 bool purged_here
= purge_dead_edges (bb
);
2411 purged
|= purged_here
;
2417 /* Same as split_block but update cfg_layout structures. */
2420 cfg_layout_split_block (basic_block bb
, void *insnp
)
2423 basic_block new_bb
= rtl_split_block (bb
, insn
);
2425 new_bb
->il
.rtl
->footer
= bb
->il
.rtl
->footer
;
2426 bb
->il
.rtl
->footer
= NULL
;
2432 /* Redirect Edge to DEST. */
2434 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
2436 basic_block src
= e
->src
;
2439 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
2442 if (e
->dest
== dest
)
2445 if (e
->src
!= ENTRY_BLOCK_PTR
2446 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
2448 src
->flags
|= BB_DIRTY
;
2452 if (e
->src
== ENTRY_BLOCK_PTR
2453 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
2456 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
2457 e
->src
->index
, dest
->index
);
2459 e
->src
->flags
|= BB_DIRTY
;
2460 redirect_edge_succ (e
, dest
);
2464 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
2465 in the case the basic block appears to be in sequence. Avoid this
2468 if (e
->flags
& EDGE_FALLTHRU
)
2470 /* Redirect any branch edges unified with the fallthru one. */
2471 if (JUMP_P (BB_END (src
))
2472 && label_is_jump_target_p (BB_HEAD (e
->dest
),
2478 fprintf (dump_file
, "Fallthru edge unified with branch "
2479 "%i->%i redirected to %i\n",
2480 e
->src
->index
, e
->dest
->index
, dest
->index
);
2481 e
->flags
&= ~EDGE_FALLTHRU
;
2482 redirected
= redirect_branch_edge (e
, dest
);
2483 gcc_assert (redirected
);
2484 e
->flags
|= EDGE_FALLTHRU
;
2485 e
->src
->flags
|= BB_DIRTY
;
2488 /* In case we are redirecting fallthru edge to the branch edge
2489 of conditional jump, remove it. */
2490 if (EDGE_COUNT (src
->succs
) == 2)
2492 /* Find the edge that is different from E. */
2493 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
2496 && any_condjump_p (BB_END (src
))
2497 && onlyjump_p (BB_END (src
)))
2498 delete_insn (BB_END (src
));
2500 ret
= redirect_edge_succ_nodup (e
, dest
);
2502 fprintf (dump_file
, "Fallthru edge %i->%i redirected to %i\n",
2503 e
->src
->index
, e
->dest
->index
, dest
->index
);
2506 ret
= redirect_branch_edge (e
, dest
);
2508 /* We don't want simplejumps in the insn stream during cfglayout. */
2509 gcc_assert (!simplejump_p (BB_END (src
)));
2511 src
->flags
|= BB_DIRTY
;
2515 /* Simple wrapper as we always can redirect fallthru edges. */
2517 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
2519 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
2521 gcc_assert (redirected
);
2525 /* Same as delete_basic_block but update cfg_layout structures. */
2528 cfg_layout_delete_block (basic_block bb
)
2530 rtx insn
, next
, prev
= PREV_INSN (BB_HEAD (bb
)), *to
, remaints
;
2532 if (bb
->il
.rtl
->header
)
2534 next
= BB_HEAD (bb
);
2536 NEXT_INSN (prev
) = bb
->il
.rtl
->header
;
2538 set_first_insn (bb
->il
.rtl
->header
);
2539 PREV_INSN (bb
->il
.rtl
->header
) = prev
;
2540 insn
= bb
->il
.rtl
->header
;
2541 while (NEXT_INSN (insn
))
2542 insn
= NEXT_INSN (insn
);
2543 NEXT_INSN (insn
) = next
;
2544 PREV_INSN (next
) = insn
;
2546 next
= NEXT_INSN (BB_END (bb
));
2547 if (bb
->il
.rtl
->footer
)
2549 insn
= bb
->il
.rtl
->footer
;
2552 if (BARRIER_P (insn
))
2554 if (PREV_INSN (insn
))
2555 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
2557 bb
->il
.rtl
->footer
= NEXT_INSN (insn
);
2558 if (NEXT_INSN (insn
))
2559 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
2563 insn
= NEXT_INSN (insn
);
2565 if (bb
->il
.rtl
->footer
)
2568 NEXT_INSN (insn
) = bb
->il
.rtl
->footer
;
2569 PREV_INSN (bb
->il
.rtl
->footer
) = insn
;
2570 while (NEXT_INSN (insn
))
2571 insn
= NEXT_INSN (insn
);
2572 NEXT_INSN (insn
) = next
;
2574 PREV_INSN (next
) = insn
;
2576 set_last_insn (insn
);
2579 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
2580 to
= &bb
->next_bb
->il
.rtl
->header
;
2582 to
= &cfg_layout_function_footer
;
2584 rtl_delete_block (bb
);
2587 prev
= NEXT_INSN (prev
);
2589 prev
= get_insns ();
2591 next
= PREV_INSN (next
);
2593 next
= get_last_insn ();
2595 if (next
&& NEXT_INSN (next
) != prev
)
2597 remaints
= unlink_insn_chain (prev
, next
);
2599 while (NEXT_INSN (insn
))
2600 insn
= NEXT_INSN (insn
);
2601 NEXT_INSN (insn
) = *to
;
2603 PREV_INSN (*to
) = insn
;
2608 /* Return true when blocks A and B can be safely merged. */
2610 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
2612 /* If we are partitioning hot/cold basic blocks, we don't want to
2613 mess up unconditional or indirect jumps that cross between hot
2616 Basic block partitioning may result in some jumps that appear to
2617 be optimizable (or blocks that appear to be mergeable), but which really
2618 must be left untouched (they are required to make it safely across
2619 partition boundaries). See the comments at the top of
2620 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
2622 if (BB_PARTITION (a
) != BB_PARTITION (b
))
2625 /* There must be exactly one edge in between the blocks. */
2626 return (single_succ_p (a
)
2627 && single_succ (a
) == b
2628 && single_pred_p (b
) == 1
2630 /* Must be simple edge. */
2631 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
2632 && a
!= ENTRY_BLOCK_PTR
&& b
!= EXIT_BLOCK_PTR
2633 /* If the jump insn has side effects,
2634 we can't kill the edge. */
2635 && (!JUMP_P (BB_END (a
))
2636 || (reload_completed
2637 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
2640 /* Merge block A and B. The blocks must be mergeable. */
2643 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
2645 #ifdef ENABLE_CHECKING
2646 gcc_assert (cfg_layout_can_merge_blocks_p (a
, b
));
2649 /* If there was a CODE_LABEL beginning B, delete it. */
2650 if (LABEL_P (BB_HEAD (b
)))
2652 /* This might have been an EH label that no longer has incoming
2653 EH edges. Update data structures to match. */
2654 maybe_remove_eh_handler (BB_HEAD (b
));
2656 delete_insn (BB_HEAD (b
));
2659 /* We should have fallthru edge in a, or we can do dummy redirection to get
2661 if (JUMP_P (BB_END (a
)))
2662 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
2663 gcc_assert (!JUMP_P (BB_END (a
)));
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
));
2671 delete_insn_chain (NEXT_INSN (first
), last
);
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
));
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
));
2686 delete_insn (first
);
2688 /* Otherwise just re-associate the instructions. */
2693 for (insn
= BB_HEAD (b
);
2694 insn
!= NEXT_INSN (BB_END (b
));
2695 insn
= NEXT_INSN (insn
))
2696 set_block_for_insn (insn
, a
);
2698 /* Skip possible DELETED_LABEL insn. */
2699 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
2700 insn
= NEXT_INSN (insn
);
2701 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
2703 BB_END (a
) = BB_END (b
);
2707 /* Possible tablejumps and barriers should appear after the block. */
2708 if (b
->il
.rtl
->footer
)
2710 if (!a
->il
.rtl
->footer
)
2711 a
->il
.rtl
->footer
= b
->il
.rtl
->footer
;
2714 rtx last
= a
->il
.rtl
->footer
;
2716 while (NEXT_INSN (last
))
2717 last
= NEXT_INSN (last
);
2718 NEXT_INSN (last
) = b
->il
.rtl
->footer
;
2719 PREV_INSN (b
->il
.rtl
->footer
) = last
;
2721 b
->il
.rtl
->footer
= NULL
;
2723 a
->il
.rtl
->global_live_at_end
= b
->il
.rtl
->global_live_at_end
;
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 /* ??? This info is likely going to be out of date very soon, but we must
2741 create it to avoid getting an ICE later. */
2742 if (e
->dest
->il
.rtl
->global_live_at_start
)
2744 new_bb
->il
.rtl
->global_live_at_start
= ALLOC_REG_SET (®_obstack
);
2745 new_bb
->il
.rtl
->global_live_at_end
= ALLOC_REG_SET (®_obstack
);
2746 COPY_REG_SET (new_bb
->il
.rtl
->global_live_at_start
,
2747 e
->dest
->il
.rtl
->global_live_at_start
);
2748 COPY_REG_SET (new_bb
->il
.rtl
->global_live_at_end
,
2749 e
->dest
->il
.rtl
->global_live_at_start
);
2752 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
2753 redirect_edge_and_branch_force (e
, new_bb
);
2758 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
2761 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
2765 /* Return 1 if BB ends with a call, possibly followed by some
2766 instructions that must stay with the call, 0 otherwise. */
2769 rtl_block_ends_with_call_p (basic_block bb
)
2771 rtx insn
= BB_END (bb
);
2773 while (!CALL_P (insn
)
2774 && insn
!= BB_HEAD (bb
)
2775 && keep_with_call_p (insn
))
2776 insn
= PREV_INSN (insn
);
2777 return (CALL_P (insn
));
2780 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
2783 rtl_block_ends_with_condjump_p (basic_block bb
)
2785 return any_condjump_p (BB_END (bb
));
2788 /* Return true if we need to add fake edge to exit.
2789 Helper function for rtl_flow_call_edges_add. */
2792 need_fake_edge_p (rtx insn
)
2798 && !SIBLING_CALL_P (insn
)
2799 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
2800 && !CONST_OR_PURE_CALL_P (insn
)))
2803 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
2804 && MEM_VOLATILE_P (PATTERN (insn
)))
2805 || (GET_CODE (PATTERN (insn
)) == PARALLEL
2806 && asm_noperands (insn
) != -1
2807 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
2808 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
2811 /* Add fake edges to the function exit for any non constant and non noreturn
2812 calls, volatile inline assembly in the bitmap of blocks specified by
2813 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
2816 The goal is to expose cases in which entering a basic block does not imply
2817 that all subsequent instructions must be executed. */
2820 rtl_flow_call_edges_add (sbitmap blocks
)
2823 int blocks_split
= 0;
2824 int last_bb
= last_basic_block
;
2825 bool check_last_block
= false;
2827 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
2831 check_last_block
= true;
2833 check_last_block
= TEST_BIT (blocks
, EXIT_BLOCK_PTR
->prev_bb
->index
);
2835 /* In the last basic block, before epilogue generation, there will be
2836 a fallthru edge to EXIT. Special care is required if the last insn
2837 of the last basic block is a call because make_edge folds duplicate
2838 edges, which would result in the fallthru edge also being marked
2839 fake, which would result in the fallthru edge being removed by
2840 remove_fake_edges, which would result in an invalid CFG.
2842 Moreover, we can't elide the outgoing fake edge, since the block
2843 profiler needs to take this into account in order to solve the minimal
2844 spanning tree in the case that the call doesn't return.
2846 Handle this by adding a dummy instruction in a new last basic block. */
2847 if (check_last_block
)
2849 basic_block bb
= EXIT_BLOCK_PTR
->prev_bb
;
2850 rtx insn
= BB_END (bb
);
2852 /* Back up past insns that must be kept in the same block as a call. */
2853 while (insn
!= BB_HEAD (bb
)
2854 && keep_with_call_p (insn
))
2855 insn
= PREV_INSN (insn
);
2857 if (need_fake_edge_p (insn
))
2861 e
= find_edge (bb
, EXIT_BLOCK_PTR
);
2864 insert_insn_on_edge (gen_rtx_USE (VOIDmode
, const0_rtx
), e
);
2865 commit_edge_insertions ();
2870 /* Now add fake edges to the function exit for any non constant
2871 calls since there is no way that we can determine if they will
2874 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
2876 basic_block bb
= BASIC_BLOCK (i
);
2883 if (blocks
&& !TEST_BIT (blocks
, i
))
2886 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
2888 prev_insn
= PREV_INSN (insn
);
2889 if (need_fake_edge_p (insn
))
2892 rtx split_at_insn
= insn
;
2894 /* Don't split the block between a call and an insn that should
2895 remain in the same block as the call. */
2897 while (split_at_insn
!= BB_END (bb
)
2898 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
2899 split_at_insn
= NEXT_INSN (split_at_insn
);
2901 /* The handling above of the final block before the epilogue
2902 should be enough to verify that there is no edge to the exit
2903 block in CFG already. Calling make_edge in such case would
2904 cause us to mark that edge as fake and remove it later. */
2906 #ifdef ENABLE_CHECKING
2907 if (split_at_insn
== BB_END (bb
))
2909 e
= find_edge (bb
, EXIT_BLOCK_PTR
);
2910 gcc_assert (e
== NULL
);
2914 /* Note that the following may create a new basic block
2915 and renumber the existing basic blocks. */
2916 if (split_at_insn
!= BB_END (bb
))
2918 e
= split_block (bb
, split_at_insn
);
2923 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
2926 if (insn
== BB_HEAD (bb
))
2932 verify_flow_info ();
2934 return blocks_split
;
2937 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
2938 the conditional branch target, SECOND_HEAD should be the fall-thru
2939 there is no need to handle this here the loop versioning code handles
2940 this. the reason for SECON_HEAD is that it is needed for condition
2941 in trees, and this should be of the same type since it is a hook. */
2943 rtl_lv_add_condition_to_bb (basic_block first_head
,
2944 basic_block second_head ATTRIBUTE_UNUSED
,
2945 basic_block cond_bb
, void *comp_rtx
)
2947 rtx label
, seq
, jump
;
2948 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
2949 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
2950 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
2951 enum machine_mode mode
;
2954 label
= block_label (first_head
);
2955 mode
= GET_MODE (op0
);
2956 if (mode
== VOIDmode
)
2957 mode
= GET_MODE (op1
);
2960 op0
= force_operand (op0
, NULL_RTX
);
2961 op1
= force_operand (op1
, NULL_RTX
);
2962 do_compare_rtx_and_jump (op0
, op1
, comp
, 0,
2963 mode
, NULL_RTX
, NULL_RTX
, label
);
2964 jump
= get_last_insn ();
2965 JUMP_LABEL (jump
) = label
;
2966 LABEL_NUSES (label
)++;
2970 /* Add the new cond , in the new head. */
2971 emit_insn_after(seq
, BB_END(cond_bb
));
2975 /* Given a block B with unconditional branch at its end, get the
2976 store the return the branch edge and the fall-thru edge in
2977 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
2979 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
2980 edge
*fallthru_edge
)
2982 edge e
= EDGE_SUCC (b
, 0);
2984 if (e
->flags
& EDGE_FALLTHRU
)
2987 *branch_edge
= EDGE_SUCC (b
, 1);
2992 *fallthru_edge
= EDGE_SUCC (b
, 1);
2997 init_rtl_bb_info (basic_block bb
)
2999 gcc_assert (!bb
->il
.rtl
);
3000 bb
->il
.rtl
= ggc_alloc_cleared (sizeof (struct rtl_bb_info
));
3004 /* Implementation of CFG manipulation for linearized RTL. */
3005 struct cfg_hooks rtl_cfg_hooks
= {
3007 rtl_verify_flow_info
,
3009 rtl_create_basic_block
,
3010 rtl_redirect_edge_and_branch
,
3011 rtl_redirect_edge_and_branch_force
,
3014 rtl_move_block_after
,
3015 rtl_can_merge_blocks
, /* can_merge_blocks_p */
3019 NULL
, /* can_duplicate_block_p */
3020 NULL
, /* duplicate_block */
3022 rtl_make_forwarder_block
,
3023 rtl_tidy_fallthru_edge
,
3024 rtl_block_ends_with_call_p
,
3025 rtl_block_ends_with_condjump_p
,
3026 rtl_flow_call_edges_add
,
3027 NULL
, /* execute_on_growing_pred */
3028 NULL
, /* execute_on_shrinking_pred */
3029 NULL
, /* duplicate loop for trees */
3030 NULL
, /* lv_add_condition_to_bb */
3031 NULL
, /* lv_adjust_loop_header_phi*/
3032 NULL
, /* extract_cond_bb_edges */
3033 NULL
/* flush_pending_stmts */
3036 /* Implementation of CFG manipulation for cfg layout RTL, where
3037 basic block connected via fallthru edges does not have to be adjacent.
3038 This representation will hopefully become the default one in future
3039 version of the compiler. */
3041 /* We do not want to declare these functions in a header file, since they
3042 should only be used through the cfghooks interface, and we do not want to
3043 move them here since it would require also moving quite a lot of related
3045 extern bool cfg_layout_can_duplicate_bb_p (basic_block
);
3046 extern basic_block
cfg_layout_duplicate_bb (basic_block
);
3048 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
3050 rtl_verify_flow_info_1
,
3052 cfg_layout_create_basic_block
,
3053 cfg_layout_redirect_edge_and_branch
,
3054 cfg_layout_redirect_edge_and_branch_force
,
3055 cfg_layout_delete_block
,
3056 cfg_layout_split_block
,
3057 rtl_move_block_after
,
3058 cfg_layout_can_merge_blocks_p
,
3059 cfg_layout_merge_blocks
,
3062 cfg_layout_can_duplicate_bb_p
,
3063 cfg_layout_duplicate_bb
,
3064 cfg_layout_split_edge
,
3065 rtl_make_forwarder_block
,
3067 rtl_block_ends_with_call_p
,
3068 rtl_block_ends_with_condjump_p
,
3069 rtl_flow_call_edges_add
,
3070 NULL
, /* execute_on_growing_pred */
3071 NULL
, /* execute_on_shrinking_pred */
3072 duplicate_loop_to_header_edge
, /* duplicate loop for trees */
3073 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
3074 NULL
, /* lv_adjust_loop_header_phi*/
3075 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
3076 NULL
/* flush_pending_stmts */