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, 2010,
4 2011, 2012 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
33 - CFG fixing after coarse manipulation
36 Functions not supposed for generic use:
37 - Infrastructure to determine quickly basic block for insn
38 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
39 - Edge redirection with updating and optimizing of insn chain
40 block_label, tidy_fallthru_edge, force_nonfallthru */
44 #include "coretypes.h"
47 #include "hard-reg-set.h"
48 #include "basic-block.h"
53 #include "rtl-error.h"
56 #include "insn-attr.h"
57 #include "insn-config.h"
60 #include "common/common-target.h"
63 #include "tree-pass.h"
66 /* Holds the interesting leading and trailing notes for the function.
67 Only applicable if the CFG is in cfglayout mode. */
68 static GTY(()) rtx cfg_layout_function_footer
;
69 static GTY(()) rtx cfg_layout_function_header
;
71 static rtx
skip_insns_after_block (basic_block
);
72 static void record_effective_endpoints (void);
73 static rtx
label_for_bb (basic_block
);
74 static void fixup_reorder_chain (void);
76 void verify_insn_chain (void);
77 static void fixup_fallthru_exit_predecessor (void);
78 static int can_delete_note_p (const_rtx
);
79 static int can_delete_label_p (const_rtx
);
80 static basic_block
rtl_split_edge (edge
);
81 static bool rtl_move_block_after (basic_block
, basic_block
);
82 static int rtl_verify_flow_info (void);
83 static basic_block
cfg_layout_split_block (basic_block
, void *);
84 static edge
cfg_layout_redirect_edge_and_branch (edge
, basic_block
);
85 static basic_block
cfg_layout_redirect_edge_and_branch_force (edge
, basic_block
);
86 static void cfg_layout_delete_block (basic_block
);
87 static void rtl_delete_block (basic_block
);
88 static basic_block
rtl_redirect_edge_and_branch_force (edge
, basic_block
);
89 static edge
rtl_redirect_edge_and_branch (edge
, basic_block
);
90 static basic_block
rtl_split_block (basic_block
, void *);
91 static void rtl_dump_bb (FILE *, basic_block
, int, int);
92 static int rtl_verify_flow_info_1 (void);
93 static void rtl_make_forwarder_block (edge
);
95 /* Return true if NOTE is not one of the ones that must be kept paired,
96 so that we may simply delete it. */
99 can_delete_note_p (const_rtx note
)
101 switch (NOTE_KIND (note
))
103 case NOTE_INSN_DELETED
:
104 case NOTE_INSN_BASIC_BLOCK
:
105 case NOTE_INSN_EPILOGUE_BEG
:
113 /* True if a given label can be deleted. */
116 can_delete_label_p (const_rtx label
)
118 return (!LABEL_PRESERVE_P (label
)
119 /* User declared labels must be preserved. */
120 && LABEL_NAME (label
) == 0
121 && !in_expr_list_p (forced_labels
, label
));
124 /* Delete INSN by patching it out. */
127 delete_insn (rtx insn
)
130 bool really_delete
= true;
134 /* Some labels can't be directly removed from the INSN chain, as they
135 might be references via variables, constant pool etc.
136 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
137 if (! can_delete_label_p (insn
))
139 const char *name
= LABEL_NAME (insn
);
140 basic_block bb
= BLOCK_FOR_INSN (insn
);
141 rtx bb_note
= NEXT_INSN (insn
);
143 really_delete
= false;
144 PUT_CODE (insn
, NOTE
);
145 NOTE_KIND (insn
) = NOTE_INSN_DELETED_LABEL
;
146 NOTE_DELETED_LABEL_NAME (insn
) = name
;
148 if (bb_note
!= NULL_RTX
&& NOTE_INSN_BASIC_BLOCK_P (bb_note
)
149 && BLOCK_FOR_INSN (bb_note
) == bb
)
151 reorder_insns_nobb (insn
, insn
, bb_note
);
152 BB_HEAD (bb
) = bb_note
;
153 if (BB_END (bb
) == bb_note
)
158 remove_node_from_expr_list (insn
, &nonlocal_goto_handler_labels
);
163 /* If this insn has already been deleted, something is very wrong. */
164 gcc_assert (!INSN_DELETED_P (insn
));
166 INSN_DELETED_P (insn
) = 1;
169 /* If deleting a jump, decrement the use count of the label. Deleting
170 the label itself should happen in the normal course of block merging. */
173 if (JUMP_LABEL (insn
)
174 && LABEL_P (JUMP_LABEL (insn
)))
175 LABEL_NUSES (JUMP_LABEL (insn
))--;
177 /* If there are more targets, remove them too. */
179 = find_reg_note (insn
, REG_LABEL_TARGET
, NULL_RTX
)) != NULL_RTX
180 && LABEL_P (XEXP (note
, 0)))
182 LABEL_NUSES (XEXP (note
, 0))--;
183 remove_note (insn
, note
);
187 /* Also if deleting any insn that references a label as an operand. */
188 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, NULL_RTX
)) != NULL_RTX
189 && LABEL_P (XEXP (note
, 0)))
191 LABEL_NUSES (XEXP (note
, 0))--;
192 remove_note (insn
, note
);
195 if (JUMP_TABLE_DATA_P (insn
))
197 rtx pat
= PATTERN (insn
);
198 int diff_vec_p
= GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
;
199 int len
= XVECLEN (pat
, diff_vec_p
);
202 for (i
= 0; i
< len
; i
++)
204 rtx label
= XEXP (XVECEXP (pat
, diff_vec_p
, i
), 0);
206 /* When deleting code in bulk (e.g. removing many unreachable
207 blocks) we can delete a label that's a target of the vector
208 before deleting the vector itself. */
210 LABEL_NUSES (label
)--;
215 /* Like delete_insn but also purge dead edges from BB. */
218 delete_insn_and_edges (rtx insn
)
223 && BLOCK_FOR_INSN (insn
)
224 && BB_END (BLOCK_FOR_INSN (insn
)) == insn
)
228 purge_dead_edges (BLOCK_FOR_INSN (insn
));
231 /* Unlink a chain of insns between START and FINISH, leaving notes
232 that must be paired. If CLEAR_BB is true, we set bb field for
233 insns that cannot be removed to NULL. */
236 delete_insn_chain (rtx start
, rtx finish
, bool clear_bb
)
240 /* Unchain the insns one by one. It would be quicker to delete all of these
241 with a single unchaining, rather than one at a time, but we need to keep
246 prev
= PREV_INSN (current
);
247 if (NOTE_P (current
) && !can_delete_note_p (current
))
250 delete_insn (current
);
252 if (clear_bb
&& !INSN_DELETED_P (current
))
253 set_block_for_insn (current
, NULL
);
255 if (current
== start
)
261 /* Create a new basic block consisting of the instructions between HEAD and END
262 inclusive. This function is designed to allow fast BB construction - reuses
263 the note and basic block struct in BB_NOTE, if any and do not grow
264 BASIC_BLOCK chain and should be used directly only by CFG construction code.
265 END can be NULL in to create new empty basic block before HEAD. Both END
266 and HEAD can be NULL to create basic block at the end of INSN chain.
267 AFTER is the basic block we should be put after. */
270 create_basic_block_structure (rtx head
, rtx end
, rtx bb_note
, basic_block after
)
275 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
278 /* If we found an existing note, thread it back onto the chain. */
286 after
= PREV_INSN (head
);
290 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
291 reorder_insns_nobb (bb_note
, bb_note
, after
);
295 /* Otherwise we must create a note and a basic block structure. */
299 init_rtl_bb_info (bb
);
302 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
303 else if (LABEL_P (head
) && end
)
305 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
311 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
317 NOTE_BASIC_BLOCK (bb_note
) = bb
;
320 /* Always include the bb note in the block. */
321 if (NEXT_INSN (end
) == bb_note
)
326 bb
->index
= last_basic_block
++;
327 bb
->flags
= BB_NEW
| BB_RTL
;
328 link_block (bb
, after
);
329 SET_BASIC_BLOCK (bb
->index
, bb
);
330 df_bb_refs_record (bb
->index
, false);
331 update_bb_for_insn (bb
);
332 BB_SET_PARTITION (bb
, BB_UNPARTITIONED
);
334 /* Tag the block so that we know it has been used when considering
335 other basic block notes. */
341 /* Create new basic block consisting of instructions in between HEAD and END
342 and place it to the BB chain after block AFTER. END can be NULL to
343 create a new empty basic block before HEAD. Both END and HEAD can be
344 NULL to create basic block at the end of INSN chain. */
347 rtl_create_basic_block (void *headp
, void *endp
, basic_block after
)
349 rtx head
= (rtx
) headp
, end
= (rtx
) endp
;
352 /* Grow the basic block array if needed. */
353 if ((size_t) last_basic_block
>= VEC_length (basic_block
, basic_block_info
))
355 size_t new_size
= last_basic_block
+ (last_basic_block
+ 3) / 4;
356 VEC_safe_grow_cleared (basic_block
, gc
, basic_block_info
, new_size
);
361 bb
= create_basic_block_structure (head
, end
, NULL
, after
);
367 cfg_layout_create_basic_block (void *head
, void *end
, basic_block after
)
369 basic_block newbb
= rtl_create_basic_block (head
, end
, after
);
374 /* Delete the insns in a (non-live) block. We physically delete every
375 non-deleted-note insn, and update the flow graph appropriately.
377 Return nonzero if we deleted an exception handler. */
379 /* ??? Preserving all such notes strikes me as wrong. It would be nice
380 to post-process the stream to remove empty blocks, loops, ranges, etc. */
383 rtl_delete_block (basic_block b
)
387 /* If the head of this block is a CODE_LABEL, then it might be the
388 label for an exception handler which can't be reached. We need
389 to remove the label from the exception_handler_label list. */
392 end
= get_last_bb_insn (b
);
394 /* Selectively delete the entire chain. */
396 delete_insn_chain (insn
, end
, true);
400 fprintf (dump_file
, "deleting block %d\n", b
->index
);
401 df_bb_delete (b
->index
);
404 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
407 compute_bb_for_insn (void)
413 rtx end
= BB_END (bb
);
416 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
418 BLOCK_FOR_INSN (insn
) = bb
;
425 /* Release the basic_block_for_insn array. */
428 free_bb_for_insn (void)
431 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
432 if (!BARRIER_P (insn
))
433 BLOCK_FOR_INSN (insn
) = NULL
;
438 rest_of_pass_free_cfg (void)
441 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
442 valid at that point so it would be too late to call df_analyze. */
443 if (optimize
> 0 && flag_delayed_branch
)
445 df_note_add_problem ();
454 struct rtl_opt_pass pass_free_cfg
=
458 "*free_cfg", /* name */
460 rest_of_pass_free_cfg
, /* execute */
463 0, /* static_pass_number */
465 0, /* properties_required */
466 0, /* properties_provided */
467 PROP_cfg
, /* properties_destroyed */
468 0, /* todo_flags_start */
469 0, /* todo_flags_finish */
473 /* Return RTX to emit after when we want to emit code on the entry of function. */
475 entry_of_function (void)
477 return (n_basic_blocks
> NUM_FIXED_BLOCKS
?
478 BB_HEAD (ENTRY_BLOCK_PTR
->next_bb
) : get_insns ());
481 /* Emit INSN at the entry point of the function, ensuring that it is only
482 executed once per function. */
484 emit_insn_at_entry (rtx insn
)
486 edge_iterator ei
= ei_start (ENTRY_BLOCK_PTR
->succs
);
487 edge e
= ei_safe_edge (ei
);
488 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
490 insert_insn_on_edge (insn
, e
);
491 commit_edge_insertions ();
494 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
495 (or BARRIER if found) and notify df of the bb change.
496 The insn chain range is inclusive
497 (i.e. both BEGIN and END will be updated. */
500 update_bb_for_insn_chain (rtx begin
, rtx end
, basic_block bb
)
504 end
= NEXT_INSN (end
);
505 for (insn
= begin
; insn
!= end
; insn
= NEXT_INSN (insn
))
506 if (!BARRIER_P (insn
))
507 df_insn_change_bb (insn
, bb
);
510 /* Update BLOCK_FOR_INSN of insns in BB to BB,
511 and notify df of the change. */
514 update_bb_for_insn (basic_block bb
)
516 update_bb_for_insn_chain (BB_HEAD (bb
), BB_END (bb
), bb
);
520 /* Like active_insn_p, except keep the return value clobber around
521 even after reload. */
524 flow_active_insn_p (const_rtx insn
)
526 if (active_insn_p (insn
))
529 /* A clobber of the function return value exists for buggy
530 programs that fail to return a value. Its effect is to
531 keep the return value from being live across the entire
532 function. If we allow it to be skipped, we introduce the
533 possibility for register lifetime confusion. */
534 if (GET_CODE (PATTERN (insn
)) == CLOBBER
535 && REG_P (XEXP (PATTERN (insn
), 0))
536 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn
), 0)))
542 /* Return true if the block has no effect and only forwards control flow to
543 its single destination. */
544 /* FIXME: Make this a cfg hook. */
547 forwarder_block_p (const_basic_block bb
)
551 if (bb
== EXIT_BLOCK_PTR
|| bb
== ENTRY_BLOCK_PTR
552 || !single_succ_p (bb
))
555 /* Protect loop latches, headers and preheaders. */
559 if (bb
->loop_father
->header
== bb
)
561 dest
= EDGE_SUCC (bb
, 0)->dest
;
562 if (dest
->loop_father
->header
== dest
)
566 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
567 if (INSN_P (insn
) && flow_active_insn_p (insn
))
570 return (!INSN_P (insn
)
571 || (JUMP_P (insn
) && simplejump_p (insn
))
572 || !flow_active_insn_p (insn
));
575 /* Return nonzero if we can reach target from src by falling through. */
576 /* FIXME: Make this a cfg hook. */
579 can_fallthru (basic_block src
, basic_block target
)
581 rtx insn
= BB_END (src
);
586 if (target
== EXIT_BLOCK_PTR
)
588 if (src
->next_bb
!= target
)
590 FOR_EACH_EDGE (e
, ei
, src
->succs
)
591 if (e
->dest
== EXIT_BLOCK_PTR
592 && e
->flags
& EDGE_FALLTHRU
)
595 insn2
= BB_HEAD (target
);
596 if (insn2
&& !active_insn_p (insn2
))
597 insn2
= next_active_insn (insn2
);
599 /* ??? Later we may add code to move jump tables offline. */
600 return next_active_insn (insn
) == insn2
;
603 /* Return nonzero if we could reach target from src by falling through,
604 if the target was made adjacent. If we already have a fall-through
605 edge to the exit block, we can't do that. */
607 could_fall_through (basic_block src
, basic_block target
)
612 if (target
== EXIT_BLOCK_PTR
)
614 FOR_EACH_EDGE (e
, ei
, src
->succs
)
615 if (e
->dest
== EXIT_BLOCK_PTR
616 && e
->flags
& EDGE_FALLTHRU
)
621 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
623 bb_note (basic_block bb
)
629 note
= NEXT_INSN (note
);
631 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
635 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
636 note associated with the BLOCK. */
639 first_insn_after_basic_block_note (basic_block block
)
643 /* Get the first instruction in the block. */
644 insn
= BB_HEAD (block
);
646 if (insn
== NULL_RTX
)
649 insn
= NEXT_INSN (insn
);
650 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
652 return NEXT_INSN (insn
);
655 /* Creates a new basic block just after basic block B by splitting
656 everything after specified instruction I. */
659 rtl_split_block (basic_block bb
, void *insnp
)
662 rtx insn
= (rtx
) insnp
;
668 insn
= first_insn_after_basic_block_note (bb
);
674 insn
= PREV_INSN (insn
);
676 /* If the block contains only debug insns, insn would have
677 been NULL in a non-debug compilation, and then we'd end
678 up emitting a DELETED note. For -fcompare-debug
679 stability, emit the note too. */
680 if (insn
!= BB_END (bb
)
681 && DEBUG_INSN_P (next
)
682 && DEBUG_INSN_P (BB_END (bb
)))
684 while (next
!= BB_END (bb
) && DEBUG_INSN_P (next
))
685 next
= NEXT_INSN (next
);
687 if (next
== BB_END (bb
))
688 emit_note_after (NOTE_INSN_DELETED
, next
);
692 insn
= get_last_insn ();
695 /* We probably should check type of the insn so that we do not create
696 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
698 if (insn
== BB_END (bb
))
699 emit_note_after (NOTE_INSN_DELETED
, insn
);
701 /* Create the new basic block. */
702 new_bb
= create_basic_block (NEXT_INSN (insn
), BB_END (bb
), bb
);
703 BB_COPY_PARTITION (new_bb
, bb
);
706 /* Redirect the outgoing edges. */
707 new_bb
->succs
= bb
->succs
;
709 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
712 /* The new block starts off being dirty. */
713 df_set_bb_dirty (bb
);
717 /* Return true if the single edge between blocks A and B is the only place
718 in RTL which holds some unique locus. */
721 unique_locus_on_edge_between_p (basic_block a
, basic_block b
)
723 const int goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
729 /* First scan block A backward. */
731 end
= PREV_INSN (BB_HEAD (a
));
732 while (insn
!= end
&& (!NONDEBUG_INSN_P (insn
) || INSN_LOCATOR (insn
) == 0))
733 insn
= PREV_INSN (insn
);
735 if (insn
!= end
&& locator_eq (INSN_LOCATOR (insn
), goto_locus
))
738 /* Then scan block B forward. */
742 end
= NEXT_INSN (BB_END (b
));
743 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
744 insn
= NEXT_INSN (insn
);
746 if (insn
!= end
&& INSN_LOCATOR (insn
) != 0
747 && locator_eq (INSN_LOCATOR (insn
), goto_locus
))
754 /* If the single edge between blocks A and B is the only place in RTL which
755 holds some unique locus, emit a nop with that locus between the blocks. */
758 emit_nop_for_unique_locus_between (basic_block a
, basic_block b
)
760 if (!unique_locus_on_edge_between_p (a
, b
))
763 BB_END (a
) = emit_insn_after_noloc (gen_nop (), BB_END (a
), a
);
764 INSN_LOCATOR (BB_END (a
)) = EDGE_SUCC (a
, 0)->goto_locus
;
767 /* Blocks A and B are to be merged into a single block A. The insns
768 are already contiguous. */
771 rtl_merge_blocks (basic_block a
, basic_block b
)
773 rtx b_head
= BB_HEAD (b
), b_end
= BB_END (b
), a_end
= BB_END (a
);
774 rtx del_first
= NULL_RTX
, del_last
= NULL_RTX
;
775 rtx b_debug_start
= b_end
, b_debug_end
= b_end
;
776 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
780 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
783 while (DEBUG_INSN_P (b_end
))
784 b_end
= PREV_INSN (b_debug_start
= b_end
);
786 /* If there was a CODE_LABEL beginning B, delete it. */
787 if (LABEL_P (b_head
))
789 /* Detect basic blocks with nothing but a label. This can happen
790 in particular at the end of a function. */
794 del_first
= del_last
= b_head
;
795 b_head
= NEXT_INSN (b_head
);
798 /* Delete the basic block note and handle blocks containing just that
800 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
808 b_head
= NEXT_INSN (b_head
);
811 /* If there was a jump out of A, delete it. */
816 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
818 || NOTE_INSN_BASIC_BLOCK_P (prev
)
819 || prev
== BB_HEAD (a
))
825 /* If this was a conditional jump, we need to also delete
826 the insn that set cc0. */
827 if (only_sets_cc0_p (prev
))
831 prev
= prev_nonnote_insn (prev
);
838 a_end
= PREV_INSN (del_first
);
840 else if (BARRIER_P (NEXT_INSN (a_end
)))
841 del_first
= NEXT_INSN (a_end
);
843 /* Delete everything marked above as well as crap that might be
844 hanging out between the two blocks. */
846 BB_HEAD (b
) = b_empty
? NULL_RTX
: b_head
;
847 delete_insn_chain (del_first
, del_last
, true);
849 /* When not optimizing CFG and the edge is the only place in RTL which holds
850 some unique locus, emit a nop with that locus in between. */
853 emit_nop_for_unique_locus_between (a
, b
);
857 /* Reassociate the insns of B with A. */
860 update_bb_for_insn_chain (a_end
, b_debug_end
, a
);
862 BB_END (a
) = b_debug_end
;
863 BB_HEAD (b
) = NULL_RTX
;
865 else if (b_end
!= b_debug_end
)
867 /* Move any deleted labels and other notes between the end of A
868 and the debug insns that make up B after the debug insns,
869 bringing the debug insns into A while keeping the notes after
871 if (NEXT_INSN (a_end
) != b_debug_start
)
872 reorder_insns_nobb (NEXT_INSN (a_end
), PREV_INSN (b_debug_start
),
874 update_bb_for_insn_chain (b_debug_start
, b_debug_end
, a
);
875 BB_END (a
) = b_debug_end
;
878 df_bb_delete (b
->index
);
880 /* If B was a forwarder block, propagate the locus on the edge. */
881 if (forwarder_p
&& !EDGE_SUCC (b
, 0)->goto_locus
)
882 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
885 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
889 /* Return true when block A and B can be merged. */
892 rtl_can_merge_blocks (basic_block a
, basic_block b
)
894 /* If we are partitioning hot/cold basic blocks, we don't want to
895 mess up unconditional or indirect jumps that cross between hot
898 Basic block partitioning may result in some jumps that appear to
899 be optimizable (or blocks that appear to be mergeable), but which really
900 must be left untouched (they are required to make it safely across
901 partition boundaries). See the comments at the top of
902 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
904 if (BB_PARTITION (a
) != BB_PARTITION (b
))
907 /* Protect the loop latches. */
908 if (current_loops
&& b
->loop_father
->latch
== b
)
911 /* There must be exactly one edge in between the blocks. */
912 return (single_succ_p (a
)
913 && single_succ (a
) == b
916 /* Must be simple edge. */
917 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
919 && a
!= ENTRY_BLOCK_PTR
&& b
!= EXIT_BLOCK_PTR
920 /* If the jump insn has side effects,
921 we can't kill the edge. */
922 && (!JUMP_P (BB_END (a
))
924 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
927 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
931 block_label (basic_block block
)
933 if (block
== EXIT_BLOCK_PTR
)
936 if (!LABEL_P (BB_HEAD (block
)))
938 BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
941 return BB_HEAD (block
);
944 /* Attempt to perform edge redirection by replacing possibly complex jump
945 instruction by unconditional jump or removing jump completely. This can
946 apply only if all edges now point to the same block. The parameters and
947 return values are equivalent to redirect_edge_and_branch. */
950 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
952 basic_block src
= e
->src
;
953 rtx insn
= BB_END (src
), kill_from
;
957 /* If we are partitioning hot/cold basic blocks, we don't want to
958 mess up unconditional or indirect jumps that cross between hot
961 Basic block partitioning may result in some jumps that appear to
962 be optimizable (or blocks that appear to be mergeable), but which really
963 must be left untouched (they are required to make it safely across
964 partition boundaries). See the comments at the top of
965 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
967 if (find_reg_note (insn
, REG_CROSSING_JUMP
, NULL_RTX
)
968 || BB_PARTITION (src
) != BB_PARTITION (target
))
971 /* We can replace or remove a complex jump only when we have exactly
972 two edges. Also, if we have exactly one outgoing edge, we can
974 if (EDGE_COUNT (src
->succs
) >= 3
975 /* Verify that all targets will be TARGET. Specifically, the
976 edge that is not E must also go to TARGET. */
977 || (EDGE_COUNT (src
->succs
) == 2
978 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
981 if (!onlyjump_p (insn
))
983 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
986 /* Avoid removing branch with side effects. */
987 set
= single_set (insn
);
988 if (!set
|| side_effects_p (set
))
991 /* In case we zap a conditional jump, we'll need to kill
992 the cc0 setter too. */
995 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
))
996 && only_sets_cc0_p (PREV_INSN (insn
)))
997 kill_from
= PREV_INSN (insn
);
1000 /* See if we can create the fallthru edge. */
1001 if (in_cfglayout
|| can_fallthru (src
, target
))
1004 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
1007 /* Selectively unlink whole insn chain. */
1010 rtx insn
= BB_FOOTER (src
);
1012 delete_insn_chain (kill_from
, BB_END (src
), false);
1014 /* Remove barriers but keep jumptables. */
1017 if (BARRIER_P (insn
))
1019 if (PREV_INSN (insn
))
1020 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1022 BB_FOOTER (src
) = NEXT_INSN (insn
);
1023 if (NEXT_INSN (insn
))
1024 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1028 insn
= NEXT_INSN (insn
);
1032 delete_insn_chain (kill_from
, PREV_INSN (BB_HEAD (target
)),
1036 /* If this already is simplejump, redirect it. */
1037 else if (simplejump_p (insn
))
1039 if (e
->dest
== target
)
1042 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
1043 INSN_UID (insn
), e
->dest
->index
, target
->index
);
1044 if (!redirect_jump (insn
, block_label (target
), 0))
1046 gcc_assert (target
== EXIT_BLOCK_PTR
);
1051 /* Cannot do anything for target exit block. */
1052 else if (target
== EXIT_BLOCK_PTR
)
1055 /* Or replace possibly complicated jump insn by simple jump insn. */
1058 rtx target_label
= block_label (target
);
1059 rtx barrier
, label
, table
;
1061 emit_jump_insn_after_noloc (gen_jump (target_label
), insn
);
1062 JUMP_LABEL (BB_END (src
)) = target_label
;
1063 LABEL_NUSES (target_label
)++;
1065 fprintf (dump_file
, "Replacing insn %i by jump %i\n",
1066 INSN_UID (insn
), INSN_UID (BB_END (src
)));
1069 delete_insn_chain (kill_from
, insn
, false);
1071 /* Recognize a tablejump that we are converting to a
1072 simple jump and remove its associated CODE_LABEL
1073 and ADDR_VEC or ADDR_DIFF_VEC. */
1074 if (tablejump_p (insn
, &label
, &table
))
1075 delete_insn_chain (label
, table
, false);
1077 barrier
= next_nonnote_insn (BB_END (src
));
1078 if (!barrier
|| !BARRIER_P (barrier
))
1079 emit_barrier_after (BB_END (src
));
1082 if (barrier
!= NEXT_INSN (BB_END (src
)))
1084 /* Move the jump before barrier so that the notes
1085 which originally were or were created before jump table are
1086 inside the basic block. */
1087 rtx new_insn
= BB_END (src
);
1089 update_bb_for_insn_chain (NEXT_INSN (BB_END (src
)),
1090 PREV_INSN (barrier
), src
);
1092 NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
1093 PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
1095 NEXT_INSN (new_insn
) = barrier
;
1096 NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
1098 PREV_INSN (new_insn
) = PREV_INSN (barrier
);
1099 PREV_INSN (barrier
) = new_insn
;
1104 /* Keep only one edge out and set proper flags. */
1105 if (!single_succ_p (src
))
1107 gcc_assert (single_succ_p (src
));
1109 e
= single_succ_edge (src
);
1111 e
->flags
= EDGE_FALLTHRU
;
1115 e
->probability
= REG_BR_PROB_BASE
;
1116 e
->count
= src
->count
;
1118 if (e
->dest
!= target
)
1119 redirect_edge_succ (e
, target
);
1123 /* Subroutine of redirect_branch_edge that tries to patch the jump
1124 instruction INSN so that it reaches block NEW. Do this
1125 only when it originally reached block OLD. Return true if this
1126 worked or the original target wasn't OLD, return false if redirection
1130 patch_jump_insn (rtx insn
, rtx old_label
, basic_block new_bb
)
1133 /* Recognize a tablejump and adjust all matching cases. */
1134 if (tablejump_p (insn
, NULL
, &tmp
))
1138 rtx new_label
= block_label (new_bb
);
1140 if (new_bb
== EXIT_BLOCK_PTR
)
1142 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
1143 vec
= XVEC (PATTERN (tmp
), 0);
1145 vec
= XVEC (PATTERN (tmp
), 1);
1147 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
1148 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
1150 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
1151 --LABEL_NUSES (old_label
);
1152 ++LABEL_NUSES (new_label
);
1155 /* Handle casesi dispatch insns. */
1156 if ((tmp
= single_set (insn
)) != NULL
1157 && SET_DEST (tmp
) == pc_rtx
1158 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
1159 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
1160 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
1162 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
1164 --LABEL_NUSES (old_label
);
1165 ++LABEL_NUSES (new_label
);
1168 else if ((tmp
= extract_asm_operands (PATTERN (insn
))) != NULL
)
1170 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (tmp
);
1171 rtx new_label
, note
;
1173 if (new_bb
== EXIT_BLOCK_PTR
)
1175 new_label
= block_label (new_bb
);
1177 for (i
= 0; i
< n
; ++i
)
1179 rtx old_ref
= ASM_OPERANDS_LABEL (tmp
, i
);
1180 gcc_assert (GET_CODE (old_ref
) == LABEL_REF
);
1181 if (XEXP (old_ref
, 0) == old_label
)
1183 ASM_OPERANDS_LABEL (tmp
, i
)
1184 = gen_rtx_LABEL_REF (Pmode
, new_label
);
1185 --LABEL_NUSES (old_label
);
1186 ++LABEL_NUSES (new_label
);
1190 if (JUMP_LABEL (insn
) == old_label
)
1192 JUMP_LABEL (insn
) = new_label
;
1193 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1195 remove_note (insn
, note
);
1199 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1201 remove_note (insn
, note
);
1202 if (JUMP_LABEL (insn
) != new_label
1203 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1204 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1206 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1208 XEXP (note
, 0) = new_label
;
1212 /* ?? We may play the games with moving the named labels from
1213 one basic block to the other in case only one computed_jump is
1215 if (computed_jump_p (insn
)
1216 /* A return instruction can't be redirected. */
1217 || returnjump_p (insn
))
1220 if (!currently_expanding_to_rtl
|| JUMP_LABEL (insn
) == old_label
)
1222 /* If the insn doesn't go where we think, we're confused. */
1223 gcc_assert (JUMP_LABEL (insn
) == old_label
);
1225 /* If the substitution doesn't succeed, die. This can happen
1226 if the back end emitted unrecognizable instructions or if
1227 target is exit block on some arches. */
1228 if (!redirect_jump (insn
, block_label (new_bb
), 0))
1230 gcc_assert (new_bb
== EXIT_BLOCK_PTR
);
1239 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1242 redirect_branch_edge (edge e
, basic_block target
)
1244 rtx old_label
= BB_HEAD (e
->dest
);
1245 basic_block src
= e
->src
;
1246 rtx insn
= BB_END (src
);
1248 /* We can only redirect non-fallthru edges of jump insn. */
1249 if (e
->flags
& EDGE_FALLTHRU
)
1251 else if (!JUMP_P (insn
) && !currently_expanding_to_rtl
)
1254 if (!currently_expanding_to_rtl
)
1256 if (!patch_jump_insn (insn
, old_label
, target
))
1260 /* When expanding this BB might actually contain multiple
1261 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1262 Redirect all of those that match our label. */
1263 FOR_BB_INSNS (src
, insn
)
1264 if (JUMP_P (insn
) && !patch_jump_insn (insn
, old_label
, target
))
1268 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
1269 e
->src
->index
, e
->dest
->index
, target
->index
);
1271 if (e
->dest
!= target
)
1272 e
= redirect_edge_succ_nodup (e
, target
);
1277 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1278 expense of adding new instructions or reordering basic blocks.
1280 Function can be also called with edge destination equivalent to the TARGET.
1281 Then it should try the simplifications and do nothing if none is possible.
1283 Return edge representing the branch if transformation succeeded. Return NULL
1285 We still return NULL in case E already destinated TARGET and we didn't
1286 managed to simplify instruction stream. */
1289 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
1292 basic_block src
= e
->src
;
1294 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1297 if (e
->dest
== target
)
1300 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
1302 df_set_bb_dirty (src
);
1306 ret
= redirect_branch_edge (e
, target
);
1310 df_set_bb_dirty (src
);
1314 /* Like force_nonfallthru below, but additionally performs redirection
1315 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1316 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1317 simple_return_rtx, indicating which kind of returnjump to create.
1318 It should be NULL otherwise. */
1321 force_nonfallthru_and_redirect (edge e
, basic_block target
, rtx jump_label
)
1323 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
1326 int abnormal_edge_flags
= 0;
1327 bool asm_goto_edge
= false;
1330 /* In the case the last instruction is conditional jump to the next
1331 instruction, first redirect the jump itself and then continue
1332 by creating a basic block afterwards to redirect fallthru edge. */
1333 if (e
->src
!= ENTRY_BLOCK_PTR
&& e
->dest
!= EXIT_BLOCK_PTR
1334 && any_condjump_p (BB_END (e
->src
))
1335 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1338 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1341 redirected
= redirect_jump (BB_END (e
->src
), block_label (target
), 0);
1342 gcc_assert (redirected
);
1344 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1347 int prob
= INTVAL (XEXP (note
, 0));
1349 b
->probability
= prob
;
1350 b
->count
= e
->count
* prob
/ REG_BR_PROB_BASE
;
1351 e
->probability
-= e
->probability
;
1352 e
->count
-= b
->count
;
1353 if (e
->probability
< 0)
1360 if (e
->flags
& EDGE_ABNORMAL
)
1362 /* Irritating special case - fallthru edge to the same block as abnormal
1364 We can't redirect abnormal edge, but we still can split the fallthru
1365 one and create separate abnormal edge to original destination.
1366 This allows bb-reorder to make such edge non-fallthru. */
1367 gcc_assert (e
->dest
== target
);
1368 abnormal_edge_flags
= e
->flags
& ~EDGE_FALLTHRU
;
1369 e
->flags
&= EDGE_FALLTHRU
;
1373 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1374 if (e
->src
== ENTRY_BLOCK_PTR
)
1376 /* We can't redirect the entry block. Create an empty block
1377 at the start of the function which we use to add the new
1383 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
, ENTRY_BLOCK_PTR
);
1385 /* Change the existing edge's source to be the new block, and add
1386 a new edge from the entry block to the new block. */
1388 for (ei
= ei_start (ENTRY_BLOCK_PTR
->succs
); (tmp
= ei_safe_edge (ei
)); )
1392 VEC_unordered_remove (edge
, ENTRY_BLOCK_PTR
->succs
, ei
.index
);
1402 VEC_safe_push (edge
, gc
, bb
->succs
, e
);
1403 make_single_succ_edge (ENTRY_BLOCK_PTR
, bb
, EDGE_FALLTHRU
);
1407 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1408 don't point to the target or fallthru label. */
1409 if (JUMP_P (BB_END (e
->src
))
1410 && target
!= EXIT_BLOCK_PTR
1411 && (e
->flags
& EDGE_FALLTHRU
)
1412 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
1414 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
1416 for (i
= 0; i
< n
; ++i
)
1418 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (e
->dest
))
1419 XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) = block_label (target
);
1420 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (target
))
1421 asm_goto_edge
= true;
1425 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
|| asm_goto_edge
)
1427 gcov_type count
= e
->count
;
1428 int probability
= e
->probability
;
1429 /* Create the new structures. */
1431 /* If the old block ended with a tablejump, skip its table
1432 by searching forward from there. Otherwise start searching
1433 forward from the last instruction of the old block. */
1434 if (!tablejump_p (BB_END (e
->src
), NULL
, ¬e
))
1435 note
= BB_END (e
->src
);
1436 note
= NEXT_INSN (note
);
1438 jump_block
= create_basic_block (note
, NULL
, e
->src
);
1439 jump_block
->count
= count
;
1440 jump_block
->frequency
= EDGE_FREQUENCY (e
);
1441 jump_block
->loop_depth
= target
->loop_depth
;
1443 /* Make sure new block ends up in correct hot/cold section. */
1445 BB_COPY_PARTITION (jump_block
, e
->src
);
1446 if (flag_reorder_blocks_and_partition
1447 && targetm_common
.have_named_sections
1448 && JUMP_P (BB_END (jump_block
))
1449 && !any_condjump_p (BB_END (jump_block
))
1450 && (EDGE_SUCC (jump_block
, 0)->flags
& EDGE_CROSSING
))
1451 add_reg_note (BB_END (jump_block
), REG_CROSSING_JUMP
, NULL_RTX
);
1454 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1455 new_edge
->probability
= probability
;
1456 new_edge
->count
= count
;
1458 /* Redirect old edge. */
1459 redirect_edge_pred (e
, jump_block
);
1460 e
->probability
= REG_BR_PROB_BASE
;
1462 /* If asm goto has any label refs to target's label,
1463 add also edge from asm goto bb to target. */
1466 new_edge
->probability
/= 2;
1467 new_edge
->count
/= 2;
1468 jump_block
->count
/= 2;
1469 jump_block
->frequency
/= 2;
1470 new_edge
= make_edge (new_edge
->src
, target
,
1471 e
->flags
& ~EDGE_FALLTHRU
);
1472 new_edge
->probability
= probability
- probability
/ 2;
1473 new_edge
->count
= count
- count
/ 2;
1476 new_bb
= jump_block
;
1479 jump_block
= e
->src
;
1481 if (e
->goto_locus
&& e
->goto_block
== NULL
)
1482 loc
= e
->goto_locus
;
1485 e
->flags
&= ~EDGE_FALLTHRU
;
1486 if (target
== EXIT_BLOCK_PTR
)
1488 if (jump_label
== ret_rtx
)
1491 emit_jump_insn_after_setloc (gen_return (), BB_END (jump_block
), loc
);
1498 gcc_assert (jump_label
== simple_return_rtx
);
1499 #ifdef HAVE_simple_return
1500 emit_jump_insn_after_setloc (gen_simple_return (),
1501 BB_END (jump_block
), loc
);
1506 set_return_jump_label (BB_END (jump_block
));
1510 rtx label
= block_label (target
);
1511 emit_jump_insn_after_setloc (gen_jump (label
), BB_END (jump_block
), loc
);
1512 JUMP_LABEL (BB_END (jump_block
)) = label
;
1513 LABEL_NUSES (label
)++;
1516 emit_barrier_after (BB_END (jump_block
));
1517 redirect_edge_succ_nodup (e
, target
);
1519 if (abnormal_edge_flags
)
1520 make_edge (src
, target
, abnormal_edge_flags
);
1522 df_mark_solutions_dirty ();
1526 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1527 (and possibly create new basic block) to make edge non-fallthru.
1528 Return newly created BB or NULL if none. */
1531 rtl_force_nonfallthru (edge e
)
1533 return force_nonfallthru_and_redirect (e
, e
->dest
, NULL_RTX
);
1536 /* Redirect edge even at the expense of creating new jump insn or
1537 basic block. Return new basic block if created, NULL otherwise.
1538 Conversion must be possible. */
1541 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1543 if (redirect_edge_and_branch (e
, target
)
1544 || e
->dest
== target
)
1547 /* In case the edge redirection failed, try to force it to be non-fallthru
1548 and redirect newly created simplejump. */
1549 df_set_bb_dirty (e
->src
);
1550 return force_nonfallthru_and_redirect (e
, target
, NULL_RTX
);
1553 /* The given edge should potentially be a fallthru edge. If that is in
1554 fact true, delete the jump and barriers that are in the way. */
1557 rtl_tidy_fallthru_edge (edge e
)
1560 basic_block b
= e
->src
, c
= b
->next_bb
;
1562 /* ??? In a late-running flow pass, other folks may have deleted basic
1563 blocks by nopping out blocks, leaving multiple BARRIERs between here
1564 and the target label. They ought to be chastised and fixed.
1566 We can also wind up with a sequence of undeletable labels between
1567 one block and the next.
1569 So search through a sequence of barriers, labels, and notes for
1570 the head of block C and assert that we really do fall through. */
1572 for (q
= NEXT_INSN (BB_END (b
)); q
!= BB_HEAD (c
); q
= NEXT_INSN (q
))
1576 /* Remove what will soon cease being the jump insn from the source block.
1577 If block B consisted only of this single jump, turn it into a deleted
1582 && (any_uncondjump_p (q
)
1583 || single_succ_p (b
)))
1586 /* If this was a conditional jump, we need to also delete
1587 the insn that set cc0. */
1588 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1595 /* Selectively unlink the sequence. */
1596 if (q
!= PREV_INSN (BB_HEAD (c
)))
1597 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1599 e
->flags
|= EDGE_FALLTHRU
;
1602 /* Should move basic block BB after basic block AFTER. NIY. */
1605 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1606 basic_block after ATTRIBUTE_UNUSED
)
1611 /* Split a (typically critical) edge. Return the new block.
1612 The edge must not be abnormal.
1614 ??? The code generally expects to be called on critical edges.
1615 The case of a block ending in an unconditional jump to a
1616 block with multiple predecessors is not handled optimally. */
1619 rtl_split_edge (edge edge_in
)
1624 /* Abnormal edges cannot be split. */
1625 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1627 /* We are going to place the new block in front of edge destination.
1628 Avoid existence of fallthru predecessors. */
1629 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1631 edge e
= find_fallthru_edge (edge_in
->dest
->preds
);
1634 force_nonfallthru (e
);
1637 /* Create the basic block note. */
1638 if (edge_in
->dest
!= EXIT_BLOCK_PTR
)
1639 before
= BB_HEAD (edge_in
->dest
);
1643 /* If this is a fall through edge to the exit block, the blocks might be
1644 not adjacent, and the right place is after the source. */
1645 if ((edge_in
->flags
& EDGE_FALLTHRU
) && edge_in
->dest
== EXIT_BLOCK_PTR
)
1647 before
= NEXT_INSN (BB_END (edge_in
->src
));
1648 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1649 BB_COPY_PARTITION (bb
, edge_in
->src
);
1653 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1654 /* ??? Why not edge_in->dest->prev_bb here? */
1655 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1658 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1660 /* For non-fallthru edges, we must adjust the predecessor's
1661 jump instruction to target our new block. */
1662 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1664 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1665 gcc_assert (redirected
);
1669 if (edge_in
->src
!= ENTRY_BLOCK_PTR
)
1671 /* For asm goto even splitting of fallthru edge might
1672 need insn patching, as other labels might point to the
1674 rtx last
= BB_END (edge_in
->src
);
1677 && edge_in
->dest
!= EXIT_BLOCK_PTR
1678 && extract_asm_operands (PATTERN (last
)) != NULL_RTX
1679 && patch_jump_insn (last
, before
, bb
))
1680 df_set_bb_dirty (edge_in
->src
);
1682 redirect_edge_succ (edge_in
, bb
);
1688 /* Queue instructions for insertion on an edge between two basic blocks.
1689 The new instructions and basic blocks (if any) will not appear in the
1690 CFG until commit_edge_insertions is called. */
1693 insert_insn_on_edge (rtx pattern
, edge e
)
1695 /* We cannot insert instructions on an abnormal critical edge.
1696 It will be easier to find the culprit if we die now. */
1697 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1699 if (e
->insns
.r
== NULL_RTX
)
1702 push_to_sequence (e
->insns
.r
);
1704 emit_insn (pattern
);
1706 e
->insns
.r
= get_insns ();
1710 /* Update the CFG for the instructions queued on edge E. */
1713 commit_one_edge_insertion (edge e
)
1715 rtx before
= NULL_RTX
, after
= NULL_RTX
, insns
, tmp
, last
;
1718 /* Pull the insns off the edge now since the edge might go away. */
1720 e
->insns
.r
= NULL_RTX
;
1722 /* Figure out where to put these insns. If the destination has
1723 one predecessor, insert there. Except for the exit block. */
1724 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR
)
1728 /* Get the location correct wrt a code label, and "nice" wrt
1729 a basic block note, and before everything else. */
1732 tmp
= NEXT_INSN (tmp
);
1733 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1734 tmp
= NEXT_INSN (tmp
);
1735 if (tmp
== BB_HEAD (bb
))
1738 after
= PREV_INSN (tmp
);
1740 after
= get_last_insn ();
1743 /* If the source has one successor and the edge is not abnormal,
1744 insert there. Except for the entry block. */
1745 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1746 && single_succ_p (e
->src
)
1747 && e
->src
!= ENTRY_BLOCK_PTR
)
1751 /* It is possible to have a non-simple jump here. Consider a target
1752 where some forms of unconditional jumps clobber a register. This
1753 happens on the fr30 for example.
1755 We know this block has a single successor, so we can just emit
1756 the queued insns before the jump. */
1757 if (JUMP_P (BB_END (bb
)))
1758 before
= BB_END (bb
);
1761 /* We'd better be fallthru, or we've lost track of what's what. */
1762 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1764 after
= BB_END (bb
);
1768 /* Otherwise we must split the edge. */
1771 bb
= split_edge (e
);
1772 after
= BB_END (bb
);
1774 if (flag_reorder_blocks_and_partition
1775 && targetm_common
.have_named_sections
1776 && e
->src
!= ENTRY_BLOCK_PTR
1777 && BB_PARTITION (e
->src
) == BB_COLD_PARTITION
1778 && !(e
->flags
& EDGE_CROSSING
)
1780 && !any_condjump_p (after
)
1781 && (single_succ_edge (bb
)->flags
& EDGE_CROSSING
))
1782 add_reg_note (after
, REG_CROSSING_JUMP
, NULL_RTX
);
1785 /* Now that we've found the spot, do the insertion. */
1788 emit_insn_before_noloc (insns
, before
, bb
);
1789 last
= prev_nonnote_insn (before
);
1792 last
= emit_insn_after_noloc (insns
, after
, bb
);
1794 if (returnjump_p (last
))
1796 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1797 This is not currently a problem because this only happens
1798 for the (single) epilogue, which already has a fallthru edge
1801 e
= single_succ_edge (bb
);
1802 gcc_assert (e
->dest
== EXIT_BLOCK_PTR
1803 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
1805 e
->flags
&= ~EDGE_FALLTHRU
;
1806 emit_barrier_after (last
);
1809 delete_insn (before
);
1812 gcc_assert (!JUMP_P (last
));
1815 /* Update the CFG for all queued instructions. */
1818 commit_edge_insertions (void)
1822 #ifdef ENABLE_CHECKING
1823 verify_flow_info ();
1826 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
1831 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1833 commit_one_edge_insertion (e
);
1838 /* Print out RTL-specific basic block information (live information
1839 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
1840 documented in dumpfile.h. */
1843 rtl_dump_bb (FILE *outf
, basic_block bb
, int indent
, int flags
)
1849 s_indent
= (char *) alloca ((size_t) indent
+ 1);
1850 memset (s_indent
, ' ', (size_t) indent
);
1851 s_indent
[indent
] = '\0';
1853 if (df
&& (flags
& TDF_DETAILS
))
1855 df_dump_top (bb
, outf
);
1859 if (bb
->index
!= ENTRY_BLOCK
&& bb
->index
!= EXIT_BLOCK
)
1860 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
)); insn
!= last
;
1861 insn
= NEXT_INSN (insn
))
1863 if (! (flags
& TDF_SLIM
))
1864 print_rtl_single (outf
, insn
);
1866 dump_insn_slim (outf
, insn
);
1870 if (df
&& (flags
& TDF_DETAILS
))
1872 df_dump_bottom (bb
, outf
);
1878 /* Like dump_function_to_file, but for RTL. Print out dataflow information
1879 for the start of each basic block. FLAGS are the TDF_* masks documented
1883 print_rtl_with_bb (FILE *outf
, const_rtx rtx_first
, int flags
)
1887 fprintf (outf
, "(nil)\n");
1890 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
1891 int max_uid
= get_max_uid ();
1892 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
1893 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
1894 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
1897 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
1898 insns, but the CFG is not maintained so the basic block info
1899 is not reliable. Therefore it's omitted from the dumps. */
1900 if (! (cfun
->curr_properties
& PROP_cfg
))
1901 flags
&= ~TDF_BLOCKS
;
1904 df_dump_start (outf
);
1906 if (flags
& TDF_BLOCKS
)
1908 FOR_EACH_BB_REVERSE (bb
)
1912 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
1913 end
[INSN_UID (BB_END (bb
))] = bb
;
1914 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
1916 enum bb_state state
= IN_MULTIPLE_BB
;
1918 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
1920 in_bb_p
[INSN_UID (x
)] = state
;
1922 if (x
== BB_END (bb
))
1928 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
1930 if (flags
& TDF_BLOCKS
)
1932 bb
= start
[INSN_UID (tmp_rtx
)];
1935 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, true, false);
1936 if (df
&& (flags
& TDF_DETAILS
))
1937 df_dump_top (bb
, outf
);
1940 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
1941 && !NOTE_P (tmp_rtx
)
1942 && !BARRIER_P (tmp_rtx
))
1943 fprintf (outf
, ";; Insn is not within a basic block\n");
1944 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
1945 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
1948 if (! (flags
& TDF_SLIM
))
1949 print_rtl_single (outf
, tmp_rtx
);
1951 dump_insn_slim (outf
, tmp_rtx
);
1953 if (flags
& TDF_BLOCKS
)
1955 bb
= end
[INSN_UID (tmp_rtx
)];
1958 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, false, true);
1959 if (df
&& (flags
& TDF_DETAILS
))
1960 df_dump_bottom (bb
, outf
);
1971 if (crtl
->epilogue_delay_list
!= 0)
1973 fprintf (outf
, "\n;; Insns in epilogue delay list:\n\n");
1974 for (tmp_rtx
= crtl
->epilogue_delay_list
; tmp_rtx
!= 0;
1975 tmp_rtx
= XEXP (tmp_rtx
, 1))
1976 print_rtl_single (outf
, XEXP (tmp_rtx
, 0));
1980 /* Update the branch probability of BB if a REG_BR_PROB is present. */
1983 update_br_prob_note (basic_block bb
)
1986 if (!JUMP_P (BB_END (bb
)))
1988 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
1989 if (!note
|| INTVAL (XEXP (note
, 0)) == BRANCH_EDGE (bb
)->probability
)
1991 XEXP (note
, 0) = GEN_INT (BRANCH_EDGE (bb
)->probability
);
1994 /* Get the last insn associated with block BB (that includes barriers and
1995 tablejumps after BB). */
1997 get_last_bb_insn (basic_block bb
)
2000 rtx end
= BB_END (bb
);
2002 /* Include any jump table following the basic block. */
2003 if (tablejump_p (end
, NULL
, &tmp
))
2006 /* Include any barriers that may follow the basic block. */
2007 tmp
= next_nonnote_insn_bb (end
);
2008 while (tmp
&& BARRIER_P (tmp
))
2011 tmp
= next_nonnote_insn_bb (end
);
2017 /* Verify the CFG and RTL consistency common for both underlying RTL and
2020 Currently it does following checks:
2022 - overlapping of basic blocks
2023 - insns with wrong BLOCK_FOR_INSN pointers
2024 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2025 - tails of basic blocks (ensure that boundary is necessary)
2026 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2027 and NOTE_INSN_BASIC_BLOCK
2028 - verify that no fall_thru edge crosses hot/cold partition boundaries
2029 - verify that there are no pending RTL branch predictions
2031 In future it can be extended check a lot of other stuff as well
2032 (reachability of basic blocks, life information, etc. etc.). */
2035 rtl_verify_flow_info_1 (void)
2041 /* Check the general integrity of the basic blocks. */
2042 FOR_EACH_BB_REVERSE (bb
)
2046 if (!(bb
->flags
& BB_RTL
))
2048 error ("BB_RTL flag not set for block %d", bb
->index
);
2052 FOR_BB_INSNS (bb
, insn
)
2053 if (BLOCK_FOR_INSN (insn
) != bb
)
2055 error ("insn %d basic block pointer is %d, should be %d",
2057 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
2062 for (insn
= BB_HEADER (bb
); insn
; insn
= NEXT_INSN (insn
))
2063 if (!BARRIER_P (insn
)
2064 && BLOCK_FOR_INSN (insn
) != NULL
)
2066 error ("insn %d in header of bb %d has non-NULL basic block",
2067 INSN_UID (insn
), bb
->index
);
2070 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
2071 if (!BARRIER_P (insn
)
2072 && BLOCK_FOR_INSN (insn
) != NULL
)
2074 error ("insn %d in footer of bb %d has non-NULL basic block",
2075 INSN_UID (insn
), bb
->index
);
2080 /* Now check the basic blocks (boundaries etc.) */
2081 FOR_EACH_BB_REVERSE (bb
)
2083 int n_fallthru
= 0, n_eh
= 0, n_call
= 0, n_abnormal
= 0, n_branch
= 0;
2084 edge e
, fallthru
= NULL
;
2088 if (JUMP_P (BB_END (bb
))
2089 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
2090 && EDGE_COUNT (bb
->succs
) >= 2
2091 && any_condjump_p (BB_END (bb
)))
2093 if (INTVAL (XEXP (note
, 0)) != BRANCH_EDGE (bb
)->probability
2094 && profile_status
!= PROFILE_ABSENT
)
2096 error ("verify_flow_info: REG_BR_PROB does not match cfg %wi %i",
2097 INTVAL (XEXP (note
, 0)), BRANCH_EDGE (bb
)->probability
);
2101 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2105 if (e
->flags
& EDGE_FALLTHRU
)
2106 n_fallthru
++, fallthru
= e
;
2108 is_crossing
= (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
2109 && e
->src
!= ENTRY_BLOCK_PTR
2110 && e
->dest
!= EXIT_BLOCK_PTR
);
2111 if (e
->flags
& EDGE_CROSSING
)
2115 error ("EDGE_CROSSING incorrectly set across same section");
2118 if (e
->flags
& EDGE_FALLTHRU
)
2120 error ("fallthru edge crosses section boundary (bb %i)",
2124 if (e
->flags
& EDGE_EH
)
2126 error ("EH edge crosses section boundary (bb %i)",
2131 else if (is_crossing
)
2133 error ("EDGE_CROSSING missing across section boundary");
2137 if ((e
->flags
& ~(EDGE_DFS_BACK
2139 | EDGE_IRREDUCIBLE_LOOP
2142 | EDGE_PRESERVE
)) == 0)
2145 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2148 if (e
->flags
& EDGE_EH
)
2150 else if (e
->flags
& EDGE_ABNORMAL
)
2154 if (n_eh
&& !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
2156 error ("missing REG_EH_REGION note in the end of bb %i", bb
->index
);
2161 error ("too many eh edges %i", bb
->index
);
2165 && (!JUMP_P (BB_END (bb
))
2166 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
2167 || any_condjump_p (BB_END (bb
))))))
2169 error ("too many outgoing branch edges from bb %i", bb
->index
);
2172 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
2174 error ("fallthru edge after unconditional jump %i", bb
->index
);
2177 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
2179 error ("wrong number of branch edges after unconditional jump %i",
2183 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
2184 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
2186 error ("wrong amount of branch edges after conditional jump %i",
2190 if (n_call
&& !CALL_P (BB_END (bb
)))
2192 error ("call edges for non-call insn in bb %i", bb
->index
);
2196 && (!CALL_P (BB_END (bb
)) && n_call
!= n_abnormal
)
2197 && (!JUMP_P (BB_END (bb
))
2198 || any_condjump_p (BB_END (bb
))
2199 || any_uncondjump_p (BB_END (bb
))))
2201 error ("abnormal edges for no purpose in bb %i", bb
->index
);
2205 for (x
= BB_HEAD (bb
); x
!= NEXT_INSN (BB_END (bb
)); x
= NEXT_INSN (x
))
2206 /* We may have a barrier inside a basic block before dead code
2207 elimination. There is no BLOCK_FOR_INSN field in a barrier. */
2208 if (!BARRIER_P (x
) && BLOCK_FOR_INSN (x
) != bb
)
2211 if (! BLOCK_FOR_INSN (x
))
2213 ("insn %d inside basic block %d but block_for_insn is NULL",
2214 INSN_UID (x
), bb
->index
);
2217 ("insn %d inside basic block %d but block_for_insn is %i",
2218 INSN_UID (x
), bb
->index
, BLOCK_FOR_INSN (x
)->index
);
2223 /* OK pointers are correct. Now check the header of basic
2224 block. It ought to contain optional CODE_LABEL followed
2225 by NOTE_BASIC_BLOCK. */
2229 if (BB_END (bb
) == x
)
2231 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2239 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2241 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2246 if (BB_END (bb
) == x
)
2247 /* Do checks for empty blocks here. */
2250 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2252 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2254 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2255 INSN_UID (x
), bb
->index
);
2259 if (x
== BB_END (bb
))
2262 if (control_flow_insn_p (x
))
2264 error ("in basic block %d:", bb
->index
);
2265 fatal_insn ("flow control insn inside a basic block", x
);
2274 /* Verify the CFG and RTL consistency common for both underlying RTL and
2277 Currently it does following checks:
2278 - all checks of rtl_verify_flow_info_1
2279 - test head/end pointers
2280 - check that all insns are in the basic blocks
2281 (except the switch handling code, barriers and notes)
2282 - check that all returns are followed by barriers
2283 - check that all fallthru edge points to the adjacent blocks. */
2286 rtl_verify_flow_info (void)
2289 int err
= rtl_verify_flow_info_1 ();
2291 rtx last_head
= get_last_insn ();
2292 basic_block
*bb_info
;
2294 const rtx rtx_first
= get_insns ();
2295 basic_block last_bb_seen
= ENTRY_BLOCK_PTR
, curr_bb
= NULL
;
2296 const int max_uid
= get_max_uid ();
2298 bb_info
= XCNEWVEC (basic_block
, max_uid
);
2300 FOR_EACH_BB_REVERSE (bb
)
2303 rtx head
= BB_HEAD (bb
);
2304 rtx end
= BB_END (bb
);
2306 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2308 /* Verify the end of the basic block is in the INSN chain. */
2312 /* And that the code outside of basic blocks has NULL bb field. */
2314 && BLOCK_FOR_INSN (x
) != NULL
)
2316 error ("insn %d outside of basic blocks has non-NULL bb field",
2324 error ("end insn %d for block %d not found in the insn stream",
2325 INSN_UID (end
), bb
->index
);
2329 /* Work backwards from the end to the head of the basic block
2330 to verify the head is in the RTL chain. */
2331 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2333 /* While walking over the insn chain, verify insns appear
2334 in only one basic block. */
2335 if (bb_info
[INSN_UID (x
)] != NULL
)
2337 error ("insn %d is in multiple basic blocks (%d and %d)",
2338 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2342 bb_info
[INSN_UID (x
)] = bb
;
2349 error ("head insn %d for block %d not found in the insn stream",
2350 INSN_UID (head
), bb
->index
);
2354 last_head
= PREV_INSN (x
);
2356 e
= find_fallthru_edge (bb
->succs
);
2361 /* Ensure existence of barrier in BB with no fallthru edges. */
2362 for (insn
= NEXT_INSN (BB_END (bb
)); ; insn
= NEXT_INSN (insn
))
2364 if (!insn
|| NOTE_INSN_BASIC_BLOCK_P (insn
))
2366 error ("missing barrier after block %i", bb
->index
);
2370 if (BARRIER_P (insn
))
2374 else if (e
->src
!= ENTRY_BLOCK_PTR
2375 && e
->dest
!= EXIT_BLOCK_PTR
)
2379 if (e
->src
->next_bb
!= e
->dest
)
2382 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2383 e
->src
->index
, e
->dest
->index
);
2387 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
2388 insn
= NEXT_INSN (insn
))
2389 if (BARRIER_P (insn
) || INSN_P (insn
))
2391 error ("verify_flow_info: Incorrect fallthru %i->%i",
2392 e
->src
->index
, e
->dest
->index
);
2393 fatal_insn ("wrong insn in the fallthru edge", insn
);
2399 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2401 /* Check that the code before the first basic block has NULL
2404 && BLOCK_FOR_INSN (x
) != NULL
)
2406 error ("insn %d outside of basic blocks has non-NULL bb field",
2414 last_bb_seen
= ENTRY_BLOCK_PTR
;
2416 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2418 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2420 bb
= NOTE_BASIC_BLOCK (x
);
2423 if (bb
!= last_bb_seen
->next_bb
)
2424 internal_error ("basic blocks not laid down consecutively");
2426 curr_bb
= last_bb_seen
= bb
;
2431 switch (GET_CODE (x
))
2438 /* An addr_vec is placed outside any basic block. */
2440 && JUMP_TABLE_DATA_P (NEXT_INSN (x
)))
2443 /* But in any case, non-deletable labels can appear anywhere. */
2447 fatal_insn ("insn outside basic block", x
);
2452 && returnjump_p (x
) && ! condjump_p (x
)
2453 && ! (next_nonnote_insn (x
) && BARRIER_P (next_nonnote_insn (x
))))
2454 fatal_insn ("return not followed by barrier", x
);
2455 if (curr_bb
&& x
== BB_END (curr_bb
))
2459 if (num_bb_notes
!= n_basic_blocks
- NUM_FIXED_BLOCKS
)
2461 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2462 num_bb_notes
, n_basic_blocks
);
2467 /* Assume that the preceding pass has possibly eliminated jump instructions
2468 or converted the unconditional jumps. Eliminate the edges from CFG.
2469 Return true if any edges are eliminated. */
2472 purge_dead_edges (basic_block bb
)
2475 rtx insn
= BB_END (bb
), note
;
2476 bool purged
= false;
2480 if (DEBUG_INSN_P (insn
) && insn
!= BB_HEAD (bb
))
2482 insn
= PREV_INSN (insn
);
2483 while ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
));
2485 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2486 if (NONJUMP_INSN_P (insn
)
2487 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
2491 if (! may_trap_p (PATTERN (insn
))
2492 || ((eqnote
= find_reg_equal_equiv_note (insn
))
2493 && ! may_trap_p (XEXP (eqnote
, 0))))
2494 remove_note (insn
, note
);
2497 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
2498 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
2500 bool remove
= false;
2502 /* There are three types of edges we need to handle correctly here: EH
2503 edges, abnormal call EH edges, and abnormal call non-EH edges. The
2504 latter can appear when nonlocal gotos are used. */
2505 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2509 else if (can_nonlocal_goto (insn
))
2511 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
2513 else if (flag_tm
&& find_reg_note (insn
, REG_TM
, NULL
))
2518 else if (e
->flags
& EDGE_EH
)
2519 remove
= !can_throw_internal (insn
);
2524 df_set_bb_dirty (bb
);
2537 /* We do care only about conditional jumps and simplejumps. */
2538 if (!any_condjump_p (insn
)
2539 && !returnjump_p (insn
)
2540 && !simplejump_p (insn
))
2543 /* Branch probability/prediction notes are defined only for
2544 condjumps. We've possibly turned condjump into simplejump. */
2545 if (simplejump_p (insn
))
2547 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2549 remove_note (insn
, note
);
2550 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
2551 remove_note (insn
, note
);
2554 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
2556 /* Avoid abnormal flags to leak from computed jumps turned
2557 into simplejumps. */
2559 e
->flags
&= ~EDGE_ABNORMAL
;
2561 /* See if this edge is one we should keep. */
2562 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
2563 /* A conditional jump can fall through into the next
2564 block, so we should keep the edge. */
2569 else if (e
->dest
!= EXIT_BLOCK_PTR
2570 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
2571 /* If the destination block is the target of the jump,
2577 else if (e
->dest
== EXIT_BLOCK_PTR
&& returnjump_p (insn
))
2578 /* If the destination block is the exit block, and this
2579 instruction is a return, then keep the edge. */
2584 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
2585 /* Keep the edges that correspond to exceptions thrown by
2586 this instruction and rematerialize the EDGE_ABNORMAL
2587 flag we just cleared above. */
2589 e
->flags
|= EDGE_ABNORMAL
;
2594 /* We do not need this edge. */
2595 df_set_bb_dirty (bb
);
2600 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
2604 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
2609 /* Redistribute probabilities. */
2610 if (single_succ_p (bb
))
2612 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
2613 single_succ_edge (bb
)->count
= bb
->count
;
2617 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2621 b
= BRANCH_EDGE (bb
);
2622 f
= FALLTHRU_EDGE (bb
);
2623 b
->probability
= INTVAL (XEXP (note
, 0));
2624 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
2625 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
2626 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
2631 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
2633 /* First, there should not be any EH or ABCALL edges resulting
2634 from non-local gotos and the like. If there were, we shouldn't
2635 have created the sibcall in the first place. Second, there
2636 should of course never have been a fallthru edge. */
2637 gcc_assert (single_succ_p (bb
));
2638 gcc_assert (single_succ_edge (bb
)->flags
2639 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
2644 /* If we don't see a jump insn, we don't know exactly why the block would
2645 have been broken at this point. Look for a simple, non-fallthru edge,
2646 as these are only created by conditional branches. If we find such an
2647 edge we know that there used to be a jump here and can then safely
2648 remove all non-fallthru edges. */
2650 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2651 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
2660 /* Remove all but the fake and fallthru edges. The fake edge may be
2661 the only successor for this block in the case of noreturn
2663 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
2665 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
2667 df_set_bb_dirty (bb
);
2675 gcc_assert (single_succ_p (bb
));
2677 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
2678 single_succ_edge (bb
)->count
= bb
->count
;
2681 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
2686 /* Search all basic blocks for potentially dead edges and purge them. Return
2687 true if some edge has been eliminated. */
2690 purge_all_dead_edges (void)
2697 bool purged_here
= purge_dead_edges (bb
);
2699 purged
|= purged_here
;
2705 /* This is used by a few passes that emit some instructions after abnormal
2706 calls, moving the basic block's end, while they in fact do want to emit
2707 them on the fallthru edge. Look for abnormal call edges, find backward
2708 the call in the block and insert the instructions on the edge instead.
2710 Similarly, handle instructions throwing exceptions internally.
2712 Return true when instructions have been found and inserted on edges. */
2715 fixup_abnormal_edges (void)
2717 bool inserted
= false;
2725 /* Look for cases we are interested in - calls or instructions causing
2727 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2728 if ((e
->flags
& EDGE_ABNORMAL_CALL
)
2729 || ((e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
2730 == (EDGE_ABNORMAL
| EDGE_EH
)))
2733 if (e
&& !CALL_P (BB_END (bb
)) && !can_throw_internal (BB_END (bb
)))
2737 /* Get past the new insns generated. Allow notes, as the insns
2738 may be already deleted. */
2740 while ((NONJUMP_INSN_P (insn
) || NOTE_P (insn
))
2741 && !can_throw_internal (insn
)
2742 && insn
!= BB_HEAD (bb
))
2743 insn
= PREV_INSN (insn
);
2745 if (CALL_P (insn
) || can_throw_internal (insn
))
2749 e
= find_fallthru_edge (bb
->succs
);
2751 stop
= NEXT_INSN (BB_END (bb
));
2754 for (insn
= NEXT_INSN (insn
); insn
!= stop
; insn
= next
)
2756 next
= NEXT_INSN (insn
);
2761 /* Sometimes there's still the return value USE.
2762 If it's placed after a trapping call (i.e. that
2763 call is the last insn anyway), we have no fallthru
2764 edge. Simply delete this use and don't try to insert
2765 on the non-existent edge. */
2766 if (GET_CODE (PATTERN (insn
)) != USE
)
2768 /* We're not deleting it, we're moving it. */
2769 INSN_DELETED_P (insn
) = 0;
2770 PREV_INSN (insn
) = NULL_RTX
;
2771 NEXT_INSN (insn
) = NULL_RTX
;
2773 insert_insn_on_edge (insn
, e
);
2777 else if (!BARRIER_P (insn
))
2778 set_block_for_insn (insn
, NULL
);
2782 /* It may be that we don't find any trapping insn. In this
2783 case we discovered quite late that the insn that had been
2784 marked as can_throw_internal in fact couldn't trap at all.
2785 So we should in fact delete the EH edges out of the block. */
2787 purge_dead_edges (bb
);
2794 /* Cut the insns from FIRST to LAST out of the insns stream. */
2797 unlink_insn_chain (rtx first
, rtx last
)
2799 rtx prevfirst
= PREV_INSN (first
);
2800 rtx nextlast
= NEXT_INSN (last
);
2802 PREV_INSN (first
) = NULL
;
2803 NEXT_INSN (last
) = NULL
;
2805 NEXT_INSN (prevfirst
) = nextlast
;
2807 PREV_INSN (nextlast
) = prevfirst
;
2809 set_last_insn (prevfirst
);
2811 set_first_insn (nextlast
);
2815 /* Skip over inter-block insns occurring after BB which are typically
2816 associated with BB (e.g., barriers). If there are any such insns,
2817 we return the last one. Otherwise, we return the end of BB. */
2820 skip_insns_after_block (basic_block bb
)
2822 rtx insn
, last_insn
, next_head
, prev
;
2824 next_head
= NULL_RTX
;
2825 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
2826 next_head
= BB_HEAD (bb
->next_bb
);
2828 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
2830 if (insn
== next_head
)
2833 switch (GET_CODE (insn
))
2840 switch (NOTE_KIND (insn
))
2842 case NOTE_INSN_BLOCK_END
:
2852 if (NEXT_INSN (insn
)
2853 && JUMP_TABLE_DATA_P (NEXT_INSN (insn
)))
2855 insn
= NEXT_INSN (insn
);
2868 /* It is possible to hit contradictory sequence. For instance:
2874 Where barrier belongs to jump_insn, but the note does not. This can be
2875 created by removing the basic block originally following
2876 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
2878 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
2880 prev
= PREV_INSN (insn
);
2882 switch (NOTE_KIND (insn
))
2884 case NOTE_INSN_BLOCK_END
:
2887 case NOTE_INSN_DELETED
:
2888 case NOTE_INSN_DELETED_LABEL
:
2889 case NOTE_INSN_DELETED_DEBUG_LABEL
:
2892 reorder_insns (insn
, insn
, last_insn
);
2899 /* Locate or create a label for a given basic block. */
2902 label_for_bb (basic_block bb
)
2904 rtx label
= BB_HEAD (bb
);
2906 if (!LABEL_P (label
))
2909 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
2911 label
= block_label (bb
);
2917 /* Locate the effective beginning and end of the insn chain for each
2918 block, as defined by skip_insns_after_block above. */
2921 record_effective_endpoints (void)
2927 for (insn
= get_insns ();
2930 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
;
2931 insn
= NEXT_INSN (insn
))
2933 /* No basic blocks at all? */
2936 if (PREV_INSN (insn
))
2937 cfg_layout_function_header
=
2938 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
2940 cfg_layout_function_header
= NULL_RTX
;
2942 next_insn
= get_insns ();
2947 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
2948 BB_HEADER (bb
) = unlink_insn_chain (next_insn
,
2949 PREV_INSN (BB_HEAD (bb
)));
2950 end
= skip_insns_after_block (bb
);
2951 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
2952 BB_FOOTER (bb
) = unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
2953 next_insn
= NEXT_INSN (BB_END (bb
));
2956 cfg_layout_function_footer
= next_insn
;
2957 if (cfg_layout_function_footer
)
2958 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
2962 into_cfg_layout_mode (void)
2964 cfg_layout_initialize (0);
2969 outof_cfg_layout_mode (void)
2974 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
2975 bb
->aux
= bb
->next_bb
;
2977 cfg_layout_finalize ();
2982 struct rtl_opt_pass pass_into_cfg_layout_mode
=
2986 "into_cfglayout", /* name */
2988 into_cfg_layout_mode
, /* execute */
2991 0, /* static_pass_number */
2993 0, /* properties_required */
2994 PROP_cfglayout
, /* properties_provided */
2995 0, /* properties_destroyed */
2996 0, /* todo_flags_start */
2997 0 /* todo_flags_finish */
3001 struct rtl_opt_pass pass_outof_cfg_layout_mode
=
3005 "outof_cfglayout", /* name */
3007 outof_cfg_layout_mode
, /* execute */
3010 0, /* static_pass_number */
3012 0, /* properties_required */
3013 0, /* properties_provided */
3014 PROP_cfglayout
, /* properties_destroyed */
3015 0, /* todo_flags_start */
3016 0 /* todo_flags_finish */
3021 /* Link the basic blocks in the correct order, compacting the basic
3022 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3023 function also clears the basic block header and footer fields.
3025 This function is usually called after a pass (e.g. tracer) finishes
3026 some transformations while in cfglayout mode. The required sequence
3027 of the basic blocks is in a linked list along the bb->aux field.
3028 This functions re-links the basic block prev_bb and next_bb pointers
3029 accordingly, and it compacts and renumbers the blocks.
3031 FIXME: This currently works only for RTL, but the only RTL-specific
3032 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3033 to GIMPLE a long time ago, but it doesn't relink the basic block
3034 chain. It could do that (to give better initial RTL) if this function
3035 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3038 relink_block_chain (bool stay_in_cfglayout_mode
)
3040 basic_block bb
, prev_bb
;
3043 /* Maybe dump the re-ordered sequence. */
3046 fprintf (dump_file
, "Reordered sequence:\n");
3047 for (bb
= ENTRY_BLOCK_PTR
->next_bb
, index
= NUM_FIXED_BLOCKS
;
3049 bb
= (basic_block
) bb
->aux
, index
++)
3051 fprintf (dump_file
, " %i ", index
);
3052 if (get_bb_original (bb
))
3053 fprintf (dump_file
, "duplicate of %i ",
3054 get_bb_original (bb
)->index
);
3055 else if (forwarder_block_p (bb
)
3056 && !LABEL_P (BB_HEAD (bb
)))
3057 fprintf (dump_file
, "compensation ");
3059 fprintf (dump_file
, "bb %i ", bb
->index
);
3060 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
3064 /* Now reorder the blocks. */
3065 prev_bb
= ENTRY_BLOCK_PTR
;
3066 bb
= ENTRY_BLOCK_PTR
->next_bb
;
3067 for (; bb
; prev_bb
= bb
, bb
= (basic_block
) bb
->aux
)
3069 bb
->prev_bb
= prev_bb
;
3070 prev_bb
->next_bb
= bb
;
3072 prev_bb
->next_bb
= EXIT_BLOCK_PTR
;
3073 EXIT_BLOCK_PTR
->prev_bb
= prev_bb
;
3075 /* Then, clean up the aux fields. */
3079 if (!stay_in_cfglayout_mode
)
3080 BB_HEADER (bb
) = BB_FOOTER (bb
) = NULL
;
3083 /* Maybe reset the original copy tables, they are not valid anymore
3084 when we renumber the basic blocks in compact_blocks. If we are
3085 are going out of cfglayout mode, don't re-allocate the tables. */
3086 free_original_copy_tables ();
3087 if (stay_in_cfglayout_mode
)
3088 initialize_original_copy_tables ();
3090 /* Finally, put basic_block_info in the new order. */
3095 /* Given a reorder chain, rearrange the code to match. */
3098 fixup_reorder_chain (void)
3103 if (cfg_layout_function_header
)
3105 set_first_insn (cfg_layout_function_header
);
3106 insn
= cfg_layout_function_header
;
3107 while (NEXT_INSN (insn
))
3108 insn
= NEXT_INSN (insn
);
3111 /* First do the bulk reordering -- rechain the blocks without regard to
3112 the needed changes to jumps and labels. */
3114 for (bb
= ENTRY_BLOCK_PTR
->next_bb
; bb
; bb
= (basic_block
) bb
->aux
)
3119 NEXT_INSN (insn
) = BB_HEADER (bb
);
3121 set_first_insn (BB_HEADER (bb
));
3122 PREV_INSN (BB_HEADER (bb
)) = insn
;
3123 insn
= BB_HEADER (bb
);
3124 while (NEXT_INSN (insn
))
3125 insn
= NEXT_INSN (insn
);
3128 NEXT_INSN (insn
) = BB_HEAD (bb
);
3130 set_first_insn (BB_HEAD (bb
));
3131 PREV_INSN (BB_HEAD (bb
)) = insn
;
3135 NEXT_INSN (insn
) = BB_FOOTER (bb
);
3136 PREV_INSN (BB_FOOTER (bb
)) = insn
;
3137 while (NEXT_INSN (insn
))
3138 insn
= NEXT_INSN (insn
);
3142 NEXT_INSN (insn
) = cfg_layout_function_footer
;
3143 if (cfg_layout_function_footer
)
3144 PREV_INSN (cfg_layout_function_footer
) = insn
;
3146 while (NEXT_INSN (insn
))
3147 insn
= NEXT_INSN (insn
);
3149 set_last_insn (insn
);
3150 #ifdef ENABLE_CHECKING
3151 verify_insn_chain ();
3154 /* Now add jumps and labels as needed to match the blocks new
3157 for (bb
= ENTRY_BLOCK_PTR
->next_bb
; bb
; bb
= (basic_block
) bb
->aux
)
3159 edge e_fall
, e_taken
, e
;
3161 rtx ret_label
= NULL_RTX
;
3162 basic_block nb
, src_bb
;
3165 if (EDGE_COUNT (bb
->succs
) == 0)
3168 /* Find the old fallthru edge, and another non-EH edge for
3170 e_taken
= e_fall
= NULL
;
3172 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3173 if (e
->flags
& EDGE_FALLTHRU
)
3175 else if (! (e
->flags
& EDGE_EH
))
3178 bb_end_insn
= BB_END (bb
);
3179 if (JUMP_P (bb_end_insn
))
3181 ret_label
= JUMP_LABEL (bb_end_insn
);
3182 if (any_condjump_p (bb_end_insn
))
3184 /* This might happen if the conditional jump has side
3185 effects and could therefore not be optimized away.
3186 Make the basic block to end with a barrier in order
3187 to prevent rtl_verify_flow_info from complaining. */
3190 gcc_assert (!onlyjump_p (bb_end_insn
)
3191 || returnjump_p (bb_end_insn
));
3192 BB_FOOTER (bb
) = emit_barrier_after (bb_end_insn
);
3196 /* If the old fallthru is still next, nothing to do. */
3197 if (bb
->aux
== e_fall
->dest
3198 || e_fall
->dest
== EXIT_BLOCK_PTR
)
3201 /* The degenerated case of conditional jump jumping to the next
3202 instruction can happen for jumps with side effects. We need
3203 to construct a forwarder block and this will be done just
3204 fine by force_nonfallthru below. */
3208 /* There is another special case: if *neither* block is next,
3209 such as happens at the very end of a function, then we'll
3210 need to add a new unconditional jump. Choose the taken
3211 edge based on known or assumed probability. */
3212 else if (bb
->aux
!= e_taken
->dest
)
3214 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
3217 && INTVAL (XEXP (note
, 0)) < REG_BR_PROB_BASE
/ 2
3218 && invert_jump (bb_end_insn
,
3219 (e_fall
->dest
== EXIT_BLOCK_PTR
3221 : label_for_bb (e_fall
->dest
)), 0))
3223 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3224 gcc_checking_assert (could_fall_through
3225 (e_taken
->src
, e_taken
->dest
));
3226 e_taken
->flags
|= EDGE_FALLTHRU
;
3227 update_br_prob_note (bb
);
3228 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
3232 /* If the "jumping" edge is a crossing edge, and the fall
3233 through edge is non-crossing, leave things as they are. */
3234 else if ((e_taken
->flags
& EDGE_CROSSING
)
3235 && !(e_fall
->flags
& EDGE_CROSSING
))
3238 /* Otherwise we can try to invert the jump. This will
3239 basically never fail, however, keep up the pretense. */
3240 else if (invert_jump (bb_end_insn
,
3241 (e_fall
->dest
== EXIT_BLOCK_PTR
3243 : label_for_bb (e_fall
->dest
)), 0))
3245 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3246 gcc_checking_assert (could_fall_through
3247 (e_taken
->src
, e_taken
->dest
));
3248 e_taken
->flags
|= EDGE_FALLTHRU
;
3249 update_br_prob_note (bb
);
3250 if (LABEL_NUSES (ret_label
) == 0
3251 && single_pred_p (e_taken
->dest
))
3252 delete_insn (ret_label
);
3256 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
3258 /* If the old fallthru is still next or if
3259 asm goto doesn't have a fallthru (e.g. when followed by
3260 __builtin_unreachable ()), nothing to do. */
3262 || bb
->aux
== e_fall
->dest
3263 || e_fall
->dest
== EXIT_BLOCK_PTR
)
3266 /* Otherwise we'll have to use the fallthru fixup below. */
3270 /* Otherwise we have some return, switch or computed
3271 jump. In the 99% case, there should not have been a
3273 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
3279 /* No fallthru implies a noreturn function with EH edges, or
3280 something similarly bizarre. In any case, we don't need to
3285 /* If the fallthru block is still next, nothing to do. */
3286 if (bb
->aux
== e_fall
->dest
)
3289 /* A fallthru to exit block. */
3290 if (e_fall
->dest
== EXIT_BLOCK_PTR
)
3294 /* We got here if we need to add a new jump insn.
3295 Note force_nonfallthru can delete E_FALL and thus we have to
3296 save E_FALL->src prior to the call to force_nonfallthru. */
3297 src_bb
= e_fall
->src
;
3298 nb
= force_nonfallthru_and_redirect (e_fall
, e_fall
->dest
, ret_label
);
3303 /* Don't process this new block. */
3306 /* Make sure new bb is tagged for correct section (same as
3307 fall-thru source, since you cannot fall-thru across
3308 section boundaries). */
3309 BB_COPY_PARTITION (src_bb
, single_pred (bb
));
3310 if (flag_reorder_blocks_and_partition
3311 && targetm_common
.have_named_sections
3312 && JUMP_P (BB_END (bb
))
3313 && !any_condjump_p (BB_END (bb
))
3314 && (EDGE_SUCC (bb
, 0)->flags
& EDGE_CROSSING
))
3315 add_reg_note (BB_END (bb
), REG_CROSSING_JUMP
, NULL_RTX
);
3319 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3321 /* Annoying special case - jump around dead jumptables left in the code. */
3324 edge e
= find_fallthru_edge (bb
->succs
);
3326 if (e
&& !can_fallthru (e
->src
, e
->dest
))
3327 force_nonfallthru (e
);
3330 /* Ensure goto_locus from edges has some instructions with that locus
3338 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3339 if (e
->goto_locus
&& !(e
->flags
& EDGE_ABNORMAL
))
3343 basic_block dest
, nb
;
3346 insn
= BB_END (e
->src
);
3347 end
= PREV_INSN (BB_HEAD (e
->src
));
3349 && (!NONDEBUG_INSN_P (insn
) || INSN_LOCATOR (insn
) == 0))
3350 insn
= PREV_INSN (insn
);
3352 && locator_eq (INSN_LOCATOR (insn
), (int) e
->goto_locus
))
3354 if (simplejump_p (BB_END (e
->src
))
3355 && INSN_LOCATOR (BB_END (e
->src
)) == 0)
3357 INSN_LOCATOR (BB_END (e
->src
)) = e
->goto_locus
;
3361 if (dest
== EXIT_BLOCK_PTR
)
3363 /* Non-fallthru edges to the exit block cannot be split. */
3364 if (!(e
->flags
& EDGE_FALLTHRU
))
3369 insn
= BB_HEAD (dest
);
3370 end
= NEXT_INSN (BB_END (dest
));
3371 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
3372 insn
= NEXT_INSN (insn
);
3373 if (insn
!= end
&& INSN_LOCATOR (insn
)
3374 && locator_eq (INSN_LOCATOR (insn
), (int) e
->goto_locus
))
3377 nb
= split_edge (e
);
3378 if (!INSN_P (BB_END (nb
)))
3379 BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
3381 INSN_LOCATOR (BB_END (nb
)) = e
->goto_locus
;
3383 /* If there are other incoming edges to the destination block
3384 with the same goto locus, redirect them to the new block as
3385 well, this can prevent other such blocks from being created
3386 in subsequent iterations of the loop. */
3387 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
3389 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
3390 && locator_eq (e
->goto_locus
, e2
->goto_locus
))
3391 redirect_edge_and_branch (e2
, nb
);
3398 /* Perform sanity checks on the insn chain.
3399 1. Check that next/prev pointers are consistent in both the forward and
3401 2. Count insns in chain, going both directions, and check if equal.
3402 3. Check that get_last_insn () returns the actual end of chain. */
3405 verify_insn_chain (void)
3407 rtx x
, prevx
, nextx
;
3408 int insn_cnt1
, insn_cnt2
;
3410 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
3412 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
3413 gcc_assert (PREV_INSN (x
) == prevx
);
3415 gcc_assert (prevx
== get_last_insn ());
3417 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
3419 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
3420 gcc_assert (NEXT_INSN (x
) == nextx
);
3422 gcc_assert (insn_cnt1
== insn_cnt2
);
3425 /* If we have assembler epilogues, the block falling through to exit must
3426 be the last one in the reordered chain when we reach final. Ensure
3427 that this condition is met. */
3429 fixup_fallthru_exit_predecessor (void)
3432 basic_block bb
= NULL
;
3434 /* This transformation is not valid before reload, because we might
3435 separate a call from the instruction that copies the return
3437 gcc_assert (reload_completed
);
3439 e
= find_fallthru_edge (EXIT_BLOCK_PTR
->preds
);
3445 basic_block c
= ENTRY_BLOCK_PTR
->next_bb
;
3447 /* If the very first block is the one with the fall-through exit
3448 edge, we have to split that block. */
3451 bb
= split_block (bb
, NULL
)->dest
;
3454 BB_FOOTER (bb
) = BB_FOOTER (c
);
3455 BB_FOOTER (c
) = NULL
;
3458 while (c
->aux
!= bb
)
3459 c
= (basic_block
) c
->aux
;
3463 c
= (basic_block
) c
->aux
;
3470 /* In case there are more than one fallthru predecessors of exit, force that
3471 there is only one. */
3474 force_one_exit_fallthru (void)
3476 edge e
, predecessor
= NULL
;
3479 basic_block forwarder
, bb
;
3481 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
3482 if (e
->flags
& EDGE_FALLTHRU
)
3484 if (predecessor
== NULL
)
3496 /* Exit has several fallthru predecessors. Create a forwarder block for
3498 forwarder
= split_edge (predecessor
);
3499 for (ei
= ei_start (EXIT_BLOCK_PTR
->preds
); (e
= ei_safe_edge (ei
)); )
3501 if (e
->src
== forwarder
3502 || !(e
->flags
& EDGE_FALLTHRU
))
3505 redirect_edge_and_branch_force (e
, forwarder
);
3508 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
3512 if (bb
->aux
== NULL
&& bb
!= forwarder
)
3514 bb
->aux
= forwarder
;
3520 /* Return true in case it is possible to duplicate the basic block BB. */
3523 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
3525 /* Do not attempt to duplicate tablejumps, as we need to unshare
3526 the dispatch table. This is difficult to do, as the instructions
3527 computing jump destination may be hoisted outside the basic block. */
3528 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
3531 /* Do not duplicate blocks containing insns that can't be copied. */
3532 if (targetm
.cannot_copy_insn_p
)
3534 rtx insn
= BB_HEAD (bb
);
3537 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
3539 if (insn
== BB_END (bb
))
3541 insn
= NEXT_INSN (insn
);
3549 duplicate_insn_chain (rtx from
, rtx to
)
3551 rtx insn
, last
, copy
;
3553 /* Avoid updating of boundaries of previous basic block. The
3554 note will get removed from insn stream in fixup. */
3555 last
= emit_note (NOTE_INSN_DELETED
);
3557 /* Create copy at the end of INSN chain. The chain will
3558 be reordered later. */
3559 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
3561 switch (GET_CODE (insn
))
3564 /* Don't duplicate label debug insns. */
3565 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
)
3571 /* Avoid copying of dispatch tables. We never duplicate
3572 tablejumps, so this can hit only in case the table got
3573 moved far from original jump. */
3574 if (GET_CODE (PATTERN (insn
)) == ADDR_VEC
3575 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
)
3577 /* Avoid copying following barrier as well if any
3578 (and debug insns in between). */
3581 for (next
= NEXT_INSN (insn
);
3582 next
!= NEXT_INSN (to
);
3583 next
= NEXT_INSN (next
))
3584 if (!DEBUG_INSN_P (next
))
3586 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
3590 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
3591 if (JUMP_P (insn
) && JUMP_LABEL (insn
) != NULL_RTX
3592 && ANY_RETURN_P (JUMP_LABEL (insn
)))
3593 JUMP_LABEL (copy
) = JUMP_LABEL (insn
);
3594 maybe_copy_prologue_epilogue_insn (insn
, copy
);
3605 switch (NOTE_KIND (insn
))
3607 /* In case prologue is empty and function contain label
3608 in first BB, we may want to copy the block. */
3609 case NOTE_INSN_PROLOGUE_END
:
3611 case NOTE_INSN_DELETED
:
3612 case NOTE_INSN_DELETED_LABEL
:
3613 case NOTE_INSN_DELETED_DEBUG_LABEL
:
3614 /* No problem to strip these. */
3615 case NOTE_INSN_FUNCTION_BEG
:
3616 /* There is always just single entry to function. */
3617 case NOTE_INSN_BASIC_BLOCK
:
3620 case NOTE_INSN_EPILOGUE_BEG
:
3621 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
3622 emit_note_copy (insn
);
3626 /* All other notes should have already been eliminated. */
3634 insn
= NEXT_INSN (last
);
3639 /* Create a duplicate of the basic block BB. */
3642 cfg_layout_duplicate_bb (basic_block bb
)
3647 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
3648 new_bb
= create_basic_block (insn
,
3649 insn
? get_last_insn () : NULL
,
3650 EXIT_BLOCK_PTR
->prev_bb
);
3652 BB_COPY_PARTITION (new_bb
, bb
);
3655 insn
= BB_HEADER (bb
);
3656 while (NEXT_INSN (insn
))
3657 insn
= NEXT_INSN (insn
);
3658 insn
= duplicate_insn_chain (BB_HEADER (bb
), insn
);
3660 BB_HEADER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
3665 insn
= BB_FOOTER (bb
);
3666 while (NEXT_INSN (insn
))
3667 insn
= NEXT_INSN (insn
);
3668 insn
= duplicate_insn_chain (BB_FOOTER (bb
), insn
);
3670 BB_FOOTER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
3677 /* Main entry point to this module - initialize the datastructures for
3678 CFG layout changes. It keeps LOOPS up-to-date if not null.
3680 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
3683 cfg_layout_initialize (unsigned int flags
)
3688 initialize_original_copy_tables ();
3690 cfg_layout_rtl_register_cfg_hooks ();
3692 record_effective_endpoints ();
3694 /* Make sure that the targets of non local gotos are marked. */
3695 for (x
= nonlocal_goto_handler_labels
; x
; x
= XEXP (x
, 1))
3697 bb
= BLOCK_FOR_INSN (XEXP (x
, 0));
3698 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
3701 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
3704 /* Splits superblocks. */
3706 break_superblocks (void)
3708 sbitmap superblocks
;
3712 superblocks
= sbitmap_alloc (last_basic_block
);
3713 sbitmap_zero (superblocks
);
3716 if (bb
->flags
& BB_SUPERBLOCK
)
3718 bb
->flags
&= ~BB_SUPERBLOCK
;
3719 SET_BIT (superblocks
, bb
->index
);
3725 rebuild_jump_labels (get_insns ());
3726 find_many_sub_basic_blocks (superblocks
);
3732 /* Finalize the changes: reorder insn list according to the sequence specified
3733 by aux pointers, enter compensation code, rebuild scope forest. */
3736 cfg_layout_finalize (void)
3738 #ifdef ENABLE_CHECKING
3739 verify_flow_info ();
3741 force_one_exit_fallthru ();
3742 rtl_register_cfg_hooks ();
3743 if (reload_completed
3744 #ifdef HAVE_epilogue
3748 fixup_fallthru_exit_predecessor ();
3749 fixup_reorder_chain ();
3751 rebuild_jump_labels (get_insns ());
3752 delete_dead_jumptables ();
3754 #ifdef ENABLE_CHECKING
3755 verify_insn_chain ();
3756 verify_flow_info ();
3761 /* Same as split_block but update cfg_layout structures. */
3764 cfg_layout_split_block (basic_block bb
, void *insnp
)
3766 rtx insn
= (rtx
) insnp
;
3767 basic_block new_bb
= rtl_split_block (bb
, insn
);
3769 BB_FOOTER (new_bb
) = BB_FOOTER (bb
);
3770 BB_FOOTER (bb
) = NULL
;
3775 /* Redirect Edge to DEST. */
3777 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
3779 basic_block src
= e
->src
;
3782 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
3785 if (e
->dest
== dest
)
3788 if (e
->src
!= ENTRY_BLOCK_PTR
3789 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
3791 df_set_bb_dirty (src
);
3795 if (e
->src
== ENTRY_BLOCK_PTR
3796 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
3799 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
3800 e
->src
->index
, dest
->index
);
3802 df_set_bb_dirty (e
->src
);
3803 redirect_edge_succ (e
, dest
);
3807 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
3808 in the case the basic block appears to be in sequence. Avoid this
3811 if (e
->flags
& EDGE_FALLTHRU
)
3813 /* Redirect any branch edges unified with the fallthru one. */
3814 if (JUMP_P (BB_END (src
))
3815 && label_is_jump_target_p (BB_HEAD (e
->dest
),
3821 fprintf (dump_file
, "Fallthru edge unified with branch "
3822 "%i->%i redirected to %i\n",
3823 e
->src
->index
, e
->dest
->index
, dest
->index
);
3824 e
->flags
&= ~EDGE_FALLTHRU
;
3825 redirected
= redirect_branch_edge (e
, dest
);
3826 gcc_assert (redirected
);
3827 redirected
->flags
|= EDGE_FALLTHRU
;
3828 df_set_bb_dirty (redirected
->src
);
3831 /* In case we are redirecting fallthru edge to the branch edge
3832 of conditional jump, remove it. */
3833 if (EDGE_COUNT (src
->succs
) == 2)
3835 /* Find the edge that is different from E. */
3836 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
3839 && any_condjump_p (BB_END (src
))
3840 && onlyjump_p (BB_END (src
)))
3841 delete_insn (BB_END (src
));
3844 fprintf (dump_file
, "Redirecting fallthru edge %i->%i to %i\n",
3845 e
->src
->index
, e
->dest
->index
, dest
->index
);
3846 ret
= redirect_edge_succ_nodup (e
, dest
);
3849 ret
= redirect_branch_edge (e
, dest
);
3851 /* We don't want simplejumps in the insn stream during cfglayout. */
3852 gcc_assert (!simplejump_p (BB_END (src
)));
3854 df_set_bb_dirty (src
);
3858 /* Simple wrapper as we always can redirect fallthru edges. */
3860 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
3862 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
3864 gcc_assert (redirected
);
3868 /* Same as delete_basic_block but update cfg_layout structures. */
3871 cfg_layout_delete_block (basic_block bb
)
3873 rtx insn
, next
, prev
= PREV_INSN (BB_HEAD (bb
)), *to
, remaints
;
3877 next
= BB_HEAD (bb
);
3879 NEXT_INSN (prev
) = BB_HEADER (bb
);
3881 set_first_insn (BB_HEADER (bb
));
3882 PREV_INSN (BB_HEADER (bb
)) = prev
;
3883 insn
= BB_HEADER (bb
);
3884 while (NEXT_INSN (insn
))
3885 insn
= NEXT_INSN (insn
);
3886 NEXT_INSN (insn
) = next
;
3887 PREV_INSN (next
) = insn
;
3889 next
= NEXT_INSN (BB_END (bb
));
3892 insn
= BB_FOOTER (bb
);
3895 if (BARRIER_P (insn
))
3897 if (PREV_INSN (insn
))
3898 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
3900 BB_FOOTER (bb
) = NEXT_INSN (insn
);
3901 if (NEXT_INSN (insn
))
3902 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
3906 insn
= NEXT_INSN (insn
);
3911 NEXT_INSN (insn
) = BB_FOOTER (bb
);
3912 PREV_INSN (BB_FOOTER (bb
)) = insn
;
3913 while (NEXT_INSN (insn
))
3914 insn
= NEXT_INSN (insn
);
3915 NEXT_INSN (insn
) = next
;
3917 PREV_INSN (next
) = insn
;
3919 set_last_insn (insn
);
3922 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
3923 to
= &BB_HEADER (bb
->next_bb
);
3925 to
= &cfg_layout_function_footer
;
3927 rtl_delete_block (bb
);
3930 prev
= NEXT_INSN (prev
);
3932 prev
= get_insns ();
3934 next
= PREV_INSN (next
);
3936 next
= get_last_insn ();
3938 if (next
&& NEXT_INSN (next
) != prev
)
3940 remaints
= unlink_insn_chain (prev
, next
);
3942 while (NEXT_INSN (insn
))
3943 insn
= NEXT_INSN (insn
);
3944 NEXT_INSN (insn
) = *to
;
3946 PREV_INSN (*to
) = insn
;
3951 /* Return true when blocks A and B can be safely merged. */
3954 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
3956 /* If we are partitioning hot/cold basic blocks, we don't want to
3957 mess up unconditional or indirect jumps that cross between hot
3960 Basic block partitioning may result in some jumps that appear to
3961 be optimizable (or blocks that appear to be mergeable), but which really
3962 must be left untouched (they are required to make it safely across
3963 partition boundaries). See the comments at the top of
3964 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
3966 if (BB_PARTITION (a
) != BB_PARTITION (b
))
3969 /* Protect the loop latches. */
3970 if (current_loops
&& b
->loop_father
->latch
== b
)
3973 /* If we would end up moving B's instructions, make sure it doesn't fall
3974 through into the exit block, since we cannot recover from a fallthrough
3975 edge into the exit block occurring in the middle of a function. */
3976 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
3978 edge e
= find_fallthru_edge (b
->succs
);
3979 if (e
&& e
->dest
== EXIT_BLOCK_PTR
)
3983 /* There must be exactly one edge in between the blocks. */
3984 return (single_succ_p (a
)
3985 && single_succ (a
) == b
3986 && single_pred_p (b
) == 1
3988 /* Must be simple edge. */
3989 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
3990 && a
!= ENTRY_BLOCK_PTR
&& b
!= EXIT_BLOCK_PTR
3991 /* If the jump insn has side effects, we can't kill the edge.
3992 When not optimizing, try_redirect_by_replacing_jump will
3993 not allow us to redirect an edge by replacing a table jump. */
3994 && (!JUMP_P (BB_END (a
))
3995 || ((!optimize
|| reload_completed
)
3996 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
3999 /* Merge block A and B. The blocks must be mergeable. */
4002 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
4004 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
4007 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a
, b
));
4010 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
4013 /* If there was a CODE_LABEL beginning B, delete it. */
4014 if (LABEL_P (BB_HEAD (b
)))
4016 delete_insn (BB_HEAD (b
));
4019 /* We should have fallthru edge in a, or we can do dummy redirection to get
4021 if (JUMP_P (BB_END (a
)))
4022 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
4023 gcc_assert (!JUMP_P (BB_END (a
)));
4025 /* When not optimizing CFG and the edge is the only place in RTL which holds
4026 some unique locus, emit a nop with that locus in between. */
4028 emit_nop_for_unique_locus_between (a
, b
);
4030 /* Possible line number notes should appear in between. */
4033 rtx first
= BB_END (a
), last
;
4035 last
= emit_insn_after_noloc (BB_HEADER (b
), BB_END (a
), a
);
4036 /* The above might add a BARRIER as BB_END, but as barriers
4037 aren't valid parts of a bb, remove_insn doesn't update
4038 BB_END if it is a barrier. So adjust BB_END here. */
4039 while (BB_END (a
) != first
&& BARRIER_P (BB_END (a
)))
4040 BB_END (a
) = PREV_INSN (BB_END (a
));
4041 delete_insn_chain (NEXT_INSN (first
), last
, false);
4042 BB_HEADER (b
) = NULL
;
4045 /* In the case basic blocks are not adjacent, move them around. */
4046 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4048 insn
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
4050 emit_insn_after_noloc (insn
, BB_END (a
), a
);
4052 /* Otherwise just re-associate the instructions. */
4056 BB_END (a
) = BB_END (b
);
4059 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4060 We need to explicitly call. */
4061 update_bb_for_insn_chain (insn
, BB_END (b
), a
);
4063 /* Skip possible DELETED_LABEL insn. */
4064 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
4065 insn
= NEXT_INSN (insn
);
4066 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4070 df_bb_delete (b
->index
);
4072 /* Possible tablejumps and barriers should appear after the block. */
4076 BB_FOOTER (a
) = BB_FOOTER (b
);
4079 rtx last
= BB_FOOTER (a
);
4081 while (NEXT_INSN (last
))
4082 last
= NEXT_INSN (last
);
4083 NEXT_INSN (last
) = BB_FOOTER (b
);
4084 PREV_INSN (BB_FOOTER (b
)) = last
;
4086 BB_FOOTER (b
) = NULL
;
4089 /* If B was a forwarder block, propagate the locus on the edge. */
4090 if (forwarder_p
&& !EDGE_SUCC (b
, 0)->goto_locus
)
4091 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
4094 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
4100 cfg_layout_split_edge (edge e
)
4102 basic_block new_bb
=
4103 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR
4104 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
4107 if (e
->dest
== EXIT_BLOCK_PTR
)
4108 BB_COPY_PARTITION (new_bb
, e
->src
);
4110 BB_COPY_PARTITION (new_bb
, e
->dest
);
4111 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
4112 redirect_edge_and_branch_force (e
, new_bb
);
4117 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4120 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
4124 /* Return 1 if BB ends with a call, possibly followed by some
4125 instructions that must stay with the call, 0 otherwise. */
4128 rtl_block_ends_with_call_p (basic_block bb
)
4130 rtx insn
= BB_END (bb
);
4132 while (!CALL_P (insn
)
4133 && insn
!= BB_HEAD (bb
)
4134 && (keep_with_call_p (insn
)
4136 || DEBUG_INSN_P (insn
)))
4137 insn
= PREV_INSN (insn
);
4138 return (CALL_P (insn
));
4141 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4144 rtl_block_ends_with_condjump_p (const_basic_block bb
)
4146 return any_condjump_p (BB_END (bb
));
4149 /* Return true if we need to add fake edge to exit.
4150 Helper function for rtl_flow_call_edges_add. */
4153 need_fake_edge_p (const_rtx insn
)
4159 && !SIBLING_CALL_P (insn
)
4160 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
4161 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
4164 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
4165 && MEM_VOLATILE_P (PATTERN (insn
)))
4166 || (GET_CODE (PATTERN (insn
)) == PARALLEL
4167 && asm_noperands (insn
) != -1
4168 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
4169 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
4172 /* Add fake edges to the function exit for any non constant and non noreturn
4173 calls, volatile inline assembly in the bitmap of blocks specified by
4174 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4177 The goal is to expose cases in which entering a basic block does not imply
4178 that all subsequent instructions must be executed. */
4181 rtl_flow_call_edges_add (sbitmap blocks
)
4184 int blocks_split
= 0;
4185 int last_bb
= last_basic_block
;
4186 bool check_last_block
= false;
4188 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
4192 check_last_block
= true;
4194 check_last_block
= TEST_BIT (blocks
, EXIT_BLOCK_PTR
->prev_bb
->index
);
4196 /* In the last basic block, before epilogue generation, there will be
4197 a fallthru edge to EXIT. Special care is required if the last insn
4198 of the last basic block is a call because make_edge folds duplicate
4199 edges, which would result in the fallthru edge also being marked
4200 fake, which would result in the fallthru edge being removed by
4201 remove_fake_edges, which would result in an invalid CFG.
4203 Moreover, we can't elide the outgoing fake edge, since the block
4204 profiler needs to take this into account in order to solve the minimal
4205 spanning tree in the case that the call doesn't return.
4207 Handle this by adding a dummy instruction in a new last basic block. */
4208 if (check_last_block
)
4210 basic_block bb
= EXIT_BLOCK_PTR
->prev_bb
;
4211 rtx insn
= BB_END (bb
);
4213 /* Back up past insns that must be kept in the same block as a call. */
4214 while (insn
!= BB_HEAD (bb
)
4215 && keep_with_call_p (insn
))
4216 insn
= PREV_INSN (insn
);
4218 if (need_fake_edge_p (insn
))
4222 e
= find_edge (bb
, EXIT_BLOCK_PTR
);
4225 insert_insn_on_edge (gen_use (const0_rtx
), e
);
4226 commit_edge_insertions ();
4231 /* Now add fake edges to the function exit for any non constant
4232 calls since there is no way that we can determine if they will
4235 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
4237 basic_block bb
= BASIC_BLOCK (i
);
4244 if (blocks
&& !TEST_BIT (blocks
, i
))
4247 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
4249 prev_insn
= PREV_INSN (insn
);
4250 if (need_fake_edge_p (insn
))
4253 rtx split_at_insn
= insn
;
4255 /* Don't split the block between a call and an insn that should
4256 remain in the same block as the call. */
4258 while (split_at_insn
!= BB_END (bb
)
4259 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
4260 split_at_insn
= NEXT_INSN (split_at_insn
);
4262 /* The handling above of the final block before the epilogue
4263 should be enough to verify that there is no edge to the exit
4264 block in CFG already. Calling make_edge in such case would
4265 cause us to mark that edge as fake and remove it later. */
4267 #ifdef ENABLE_CHECKING
4268 if (split_at_insn
== BB_END (bb
))
4270 e
= find_edge (bb
, EXIT_BLOCK_PTR
);
4271 gcc_assert (e
== NULL
);
4275 /* Note that the following may create a new basic block
4276 and renumber the existing basic blocks. */
4277 if (split_at_insn
!= BB_END (bb
))
4279 e
= split_block (bb
, split_at_insn
);
4284 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
4287 if (insn
== BB_HEAD (bb
))
4293 verify_flow_info ();
4295 return blocks_split
;
4298 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4299 the conditional branch target, SECOND_HEAD should be the fall-thru
4300 there is no need to handle this here the loop versioning code handles
4301 this. the reason for SECON_HEAD is that it is needed for condition
4302 in trees, and this should be of the same type since it is a hook. */
4304 rtl_lv_add_condition_to_bb (basic_block first_head
,
4305 basic_block second_head ATTRIBUTE_UNUSED
,
4306 basic_block cond_bb
, void *comp_rtx
)
4308 rtx label
, seq
, jump
;
4309 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
4310 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
4311 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
4312 enum machine_mode mode
;
4315 label
= block_label (first_head
);
4316 mode
= GET_MODE (op0
);
4317 if (mode
== VOIDmode
)
4318 mode
= GET_MODE (op1
);
4321 op0
= force_operand (op0
, NULL_RTX
);
4322 op1
= force_operand (op1
, NULL_RTX
);
4323 do_compare_rtx_and_jump (op0
, op1
, comp
, 0,
4324 mode
, NULL_RTX
, NULL_RTX
, label
, -1);
4325 jump
= get_last_insn ();
4326 JUMP_LABEL (jump
) = label
;
4327 LABEL_NUSES (label
)++;
4331 /* Add the new cond , in the new head. */
4332 emit_insn_after(seq
, BB_END(cond_bb
));
4336 /* Given a block B with unconditional branch at its end, get the
4337 store the return the branch edge and the fall-thru edge in
4338 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4340 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
4341 edge
*fallthru_edge
)
4343 edge e
= EDGE_SUCC (b
, 0);
4345 if (e
->flags
& EDGE_FALLTHRU
)
4348 *branch_edge
= EDGE_SUCC (b
, 1);
4353 *fallthru_edge
= EDGE_SUCC (b
, 1);
4358 init_rtl_bb_info (basic_block bb
)
4360 gcc_assert (!bb
->il
.x
.rtl
);
4361 bb
->il
.x
.head_
= NULL
;
4362 bb
->il
.x
.rtl
= ggc_alloc_cleared_rtl_bb_info ();
4365 /* Returns true if it is possible to remove edge E by redirecting
4366 it to the destination of the other edge from E->src. */
4369 rtl_can_remove_branch_p (const_edge e
)
4371 const_basic_block src
= e
->src
;
4372 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
4373 const_rtx insn
= BB_END (src
), set
;
4375 /* The conditions are taken from try_redirect_by_replacing_jump. */
4376 if (target
== EXIT_BLOCK_PTR
)
4379 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4382 if (find_reg_note (insn
, REG_CROSSING_JUMP
, NULL_RTX
)
4383 || BB_PARTITION (src
) != BB_PARTITION (target
))
4386 if (!onlyjump_p (insn
)
4387 || tablejump_p (insn
, NULL
, NULL
))
4390 set
= single_set (insn
);
4391 if (!set
|| side_effects_p (set
))
4398 rtl_duplicate_bb (basic_block bb
)
4400 bb
= cfg_layout_duplicate_bb (bb
);
4405 /* Implementation of CFG manipulation for linearized RTL. */
4406 struct cfg_hooks rtl_cfg_hooks
= {
4408 rtl_verify_flow_info
,
4410 rtl_create_basic_block
,
4411 rtl_redirect_edge_and_branch
,
4412 rtl_redirect_edge_and_branch_force
,
4413 rtl_can_remove_branch_p
,
4416 rtl_move_block_after
,
4417 rtl_can_merge_blocks
, /* can_merge_blocks_p */
4421 cfg_layout_can_duplicate_bb_p
,
4424 rtl_make_forwarder_block
,
4425 rtl_tidy_fallthru_edge
,
4426 rtl_force_nonfallthru
,
4427 rtl_block_ends_with_call_p
,
4428 rtl_block_ends_with_condjump_p
,
4429 rtl_flow_call_edges_add
,
4430 NULL
, /* execute_on_growing_pred */
4431 NULL
, /* execute_on_shrinking_pred */
4432 NULL
, /* duplicate loop for trees */
4433 NULL
, /* lv_add_condition_to_bb */
4434 NULL
, /* lv_adjust_loop_header_phi*/
4435 NULL
, /* extract_cond_bb_edges */
4436 NULL
/* flush_pending_stmts */
4439 /* Implementation of CFG manipulation for cfg layout RTL, where
4440 basic block connected via fallthru edges does not have to be adjacent.
4441 This representation will hopefully become the default one in future
4442 version of the compiler. */
4444 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
4446 rtl_verify_flow_info_1
,
4448 cfg_layout_create_basic_block
,
4449 cfg_layout_redirect_edge_and_branch
,
4450 cfg_layout_redirect_edge_and_branch_force
,
4451 rtl_can_remove_branch_p
,
4452 cfg_layout_delete_block
,
4453 cfg_layout_split_block
,
4454 rtl_move_block_after
,
4455 cfg_layout_can_merge_blocks_p
,
4456 cfg_layout_merge_blocks
,
4459 cfg_layout_can_duplicate_bb_p
,
4460 cfg_layout_duplicate_bb
,
4461 cfg_layout_split_edge
,
4462 rtl_make_forwarder_block
,
4463 NULL
, /* tidy_fallthru_edge */
4464 rtl_force_nonfallthru
,
4465 rtl_block_ends_with_call_p
,
4466 rtl_block_ends_with_condjump_p
,
4467 rtl_flow_call_edges_add
,
4468 NULL
, /* execute_on_growing_pred */
4469 NULL
, /* execute_on_shrinking_pred */
4470 duplicate_loop_to_header_edge
, /* duplicate loop for trees */
4471 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
4472 NULL
, /* lv_adjust_loop_header_phi*/
4473 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
4474 NULL
/* flush_pending_stmts */
4477 #include "gt-cfgrtl.h"