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
>= basic_block_info
->length ())
355 size_t new_size
= last_basic_block
+ (last_basic_block
+ 3) / 4;
356 vec_safe_grow_cleared (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 */
459 OPTGROUP_NONE
, /* optinfo_flags */
461 rest_of_pass_free_cfg
, /* execute */
464 0, /* static_pass_number */
466 0, /* properties_required */
467 0, /* properties_provided */
468 PROP_cfg
, /* properties_destroyed */
469 0, /* todo_flags_start */
470 0, /* todo_flags_finish */
474 /* Return RTX to emit after when we want to emit code on the entry of function. */
476 entry_of_function (void)
478 return (n_basic_blocks
> NUM_FIXED_BLOCKS
?
479 BB_HEAD (ENTRY_BLOCK_PTR
->next_bb
) : get_insns ());
482 /* Emit INSN at the entry point of the function, ensuring that it is only
483 executed once per function. */
485 emit_insn_at_entry (rtx insn
)
487 edge_iterator ei
= ei_start (ENTRY_BLOCK_PTR
->succs
);
488 edge e
= ei_safe_edge (ei
);
489 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
491 insert_insn_on_edge (insn
, e
);
492 commit_edge_insertions ();
495 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
496 (or BARRIER if found) and notify df of the bb change.
497 The insn chain range is inclusive
498 (i.e. both BEGIN and END will be updated. */
501 update_bb_for_insn_chain (rtx begin
, rtx end
, basic_block bb
)
505 end
= NEXT_INSN (end
);
506 for (insn
= begin
; insn
!= end
; insn
= NEXT_INSN (insn
))
507 if (!BARRIER_P (insn
))
508 df_insn_change_bb (insn
, bb
);
511 /* Update BLOCK_FOR_INSN of insns in BB to BB,
512 and notify df of the change. */
515 update_bb_for_insn (basic_block bb
)
517 update_bb_for_insn_chain (BB_HEAD (bb
), BB_END (bb
), bb
);
521 /* Like active_insn_p, except keep the return value clobber around
522 even after reload. */
525 flow_active_insn_p (const_rtx insn
)
527 if (active_insn_p (insn
))
530 /* A clobber of the function return value exists for buggy
531 programs that fail to return a value. Its effect is to
532 keep the return value from being live across the entire
533 function. If we allow it to be skipped, we introduce the
534 possibility for register lifetime confusion. */
535 if (GET_CODE (PATTERN (insn
)) == CLOBBER
536 && REG_P (XEXP (PATTERN (insn
), 0))
537 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn
), 0)))
543 /* Return true if the block has no effect and only forwards control flow to
544 its single destination. */
547 contains_no_active_insn_p (const_basic_block bb
)
551 if (bb
== EXIT_BLOCK_PTR
|| bb
== ENTRY_BLOCK_PTR
552 || !single_succ_p (bb
))
555 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
556 if (INSN_P (insn
) && flow_active_insn_p (insn
))
559 return (!INSN_P (insn
)
560 || (JUMP_P (insn
) && simplejump_p (insn
))
561 || !flow_active_insn_p (insn
));
564 /* Likewise, but protect loop latches, headers and preheaders. */
565 /* FIXME: Make this a cfg hook. */
568 forwarder_block_p (const_basic_block bb
)
570 if (!contains_no_active_insn_p (bb
))
573 /* Protect loop latches, headers and preheaders. */
577 if (bb
->loop_father
->header
== bb
)
579 dest
= EDGE_SUCC (bb
, 0)->dest
;
580 if (dest
->loop_father
->header
== dest
)
587 /* Return nonzero if we can reach target from src by falling through. */
588 /* FIXME: Make this a cfg hook. */
591 can_fallthru (basic_block src
, basic_block target
)
593 rtx insn
= BB_END (src
);
598 if (target
== EXIT_BLOCK_PTR
)
600 if (src
->next_bb
!= target
)
602 FOR_EACH_EDGE (e
, ei
, src
->succs
)
603 if (e
->dest
== EXIT_BLOCK_PTR
604 && e
->flags
& EDGE_FALLTHRU
)
607 insn2
= BB_HEAD (target
);
608 if (insn2
&& !active_insn_p (insn2
))
609 insn2
= next_active_insn (insn2
);
611 /* ??? Later we may add code to move jump tables offline. */
612 return next_active_insn (insn
) == insn2
;
615 /* Return nonzero if we could reach target from src by falling through,
616 if the target was made adjacent. If we already have a fall-through
617 edge to the exit block, we can't do that. */
619 could_fall_through (basic_block src
, basic_block target
)
624 if (target
== EXIT_BLOCK_PTR
)
626 FOR_EACH_EDGE (e
, ei
, src
->succs
)
627 if (e
->dest
== EXIT_BLOCK_PTR
628 && e
->flags
& EDGE_FALLTHRU
)
633 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
635 bb_note (basic_block bb
)
641 note
= NEXT_INSN (note
);
643 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
647 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
648 note associated with the BLOCK. */
651 first_insn_after_basic_block_note (basic_block block
)
655 /* Get the first instruction in the block. */
656 insn
= BB_HEAD (block
);
658 if (insn
== NULL_RTX
)
661 insn
= NEXT_INSN (insn
);
662 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
664 return NEXT_INSN (insn
);
667 /* Creates a new basic block just after basic block B by splitting
668 everything after specified instruction I. */
671 rtl_split_block (basic_block bb
, void *insnp
)
674 rtx insn
= (rtx
) insnp
;
680 insn
= first_insn_after_basic_block_note (bb
);
686 insn
= PREV_INSN (insn
);
688 /* If the block contains only debug insns, insn would have
689 been NULL in a non-debug compilation, and then we'd end
690 up emitting a DELETED note. For -fcompare-debug
691 stability, emit the note too. */
692 if (insn
!= BB_END (bb
)
693 && DEBUG_INSN_P (next
)
694 && DEBUG_INSN_P (BB_END (bb
)))
696 while (next
!= BB_END (bb
) && DEBUG_INSN_P (next
))
697 next
= NEXT_INSN (next
);
699 if (next
== BB_END (bb
))
700 emit_note_after (NOTE_INSN_DELETED
, next
);
704 insn
= get_last_insn ();
707 /* We probably should check type of the insn so that we do not create
708 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
710 if (insn
== BB_END (bb
))
711 emit_note_after (NOTE_INSN_DELETED
, insn
);
713 /* Create the new basic block. */
714 new_bb
= create_basic_block (NEXT_INSN (insn
), BB_END (bb
), bb
);
715 BB_COPY_PARTITION (new_bb
, bb
);
718 /* Redirect the outgoing edges. */
719 new_bb
->succs
= bb
->succs
;
721 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
724 /* The new block starts off being dirty. */
725 df_set_bb_dirty (bb
);
729 /* Return true if the single edge between blocks A and B is the only place
730 in RTL which holds some unique locus. */
733 unique_locus_on_edge_between_p (basic_block a
, basic_block b
)
735 const location_t goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
738 if (LOCATION_LOCUS (goto_locus
) == UNKNOWN_LOCATION
)
741 /* First scan block A backward. */
743 end
= PREV_INSN (BB_HEAD (a
));
744 while (insn
!= end
&& (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
745 insn
= PREV_INSN (insn
);
747 if (insn
!= end
&& INSN_LOCATION (insn
) == goto_locus
)
750 /* Then scan block B forward. */
754 end
= NEXT_INSN (BB_END (b
));
755 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
756 insn
= NEXT_INSN (insn
);
758 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
759 && INSN_LOCATION (insn
) == goto_locus
)
766 /* If the single edge between blocks A and B is the only place in RTL which
767 holds some unique locus, emit a nop with that locus between the blocks. */
770 emit_nop_for_unique_locus_between (basic_block a
, basic_block b
)
772 if (!unique_locus_on_edge_between_p (a
, b
))
775 BB_END (a
) = emit_insn_after_noloc (gen_nop (), BB_END (a
), a
);
776 INSN_LOCATION (BB_END (a
)) = EDGE_SUCC (a
, 0)->goto_locus
;
779 /* Blocks A and B are to be merged into a single block A. The insns
780 are already contiguous. */
783 rtl_merge_blocks (basic_block a
, basic_block b
)
785 rtx b_head
= BB_HEAD (b
), b_end
= BB_END (b
), a_end
= BB_END (a
);
786 rtx del_first
= NULL_RTX
, del_last
= NULL_RTX
;
787 rtx b_debug_start
= b_end
, b_debug_end
= b_end
;
788 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
792 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
795 while (DEBUG_INSN_P (b_end
))
796 b_end
= PREV_INSN (b_debug_start
= b_end
);
798 /* If there was a CODE_LABEL beginning B, delete it. */
799 if (LABEL_P (b_head
))
801 /* Detect basic blocks with nothing but a label. This can happen
802 in particular at the end of a function. */
806 del_first
= del_last
= b_head
;
807 b_head
= NEXT_INSN (b_head
);
810 /* Delete the basic block note and handle blocks containing just that
812 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
820 b_head
= NEXT_INSN (b_head
);
823 /* If there was a jump out of A, delete it. */
828 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
830 || NOTE_INSN_BASIC_BLOCK_P (prev
)
831 || prev
== BB_HEAD (a
))
837 /* If this was a conditional jump, we need to also delete
838 the insn that set cc0. */
839 if (only_sets_cc0_p (prev
))
843 prev
= prev_nonnote_insn (prev
);
850 a_end
= PREV_INSN (del_first
);
852 else if (BARRIER_P (NEXT_INSN (a_end
)))
853 del_first
= NEXT_INSN (a_end
);
855 /* Delete everything marked above as well as crap that might be
856 hanging out between the two blocks. */
858 BB_HEAD (b
) = b_empty
? NULL_RTX
: b_head
;
859 delete_insn_chain (del_first
, del_last
, true);
861 /* When not optimizing CFG and the edge is the only place in RTL which holds
862 some unique locus, emit a nop with that locus in between. */
865 emit_nop_for_unique_locus_between (a
, b
);
869 /* Reassociate the insns of B with A. */
872 update_bb_for_insn_chain (a_end
, b_debug_end
, a
);
874 BB_END (a
) = b_debug_end
;
875 BB_HEAD (b
) = NULL_RTX
;
877 else if (b_end
!= b_debug_end
)
879 /* Move any deleted labels and other notes between the end of A
880 and the debug insns that make up B after the debug insns,
881 bringing the debug insns into A while keeping the notes after
883 if (NEXT_INSN (a_end
) != b_debug_start
)
884 reorder_insns_nobb (NEXT_INSN (a_end
), PREV_INSN (b_debug_start
),
886 update_bb_for_insn_chain (b_debug_start
, b_debug_end
, a
);
887 BB_END (a
) = b_debug_end
;
890 df_bb_delete (b
->index
);
892 /* If B was a forwarder block, propagate the locus on the edge. */
894 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
895 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
898 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
902 /* Return true when block A and B can be merged. */
905 rtl_can_merge_blocks (basic_block a
, basic_block b
)
907 /* If we are partitioning hot/cold basic blocks, we don't want to
908 mess up unconditional or indirect jumps that cross between hot
911 Basic block partitioning may result in some jumps that appear to
912 be optimizable (or blocks that appear to be mergeable), but which really
913 must be left untouched (they are required to make it safely across
914 partition boundaries). See the comments at the top of
915 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
917 if (BB_PARTITION (a
) != BB_PARTITION (b
))
920 /* Protect the loop latches. */
921 if (current_loops
&& b
->loop_father
->latch
== b
)
924 /* There must be exactly one edge in between the blocks. */
925 return (single_succ_p (a
)
926 && single_succ (a
) == b
929 /* Must be simple edge. */
930 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
932 && a
!= ENTRY_BLOCK_PTR
&& b
!= EXIT_BLOCK_PTR
933 /* If the jump insn has side effects,
934 we can't kill the edge. */
935 && (!JUMP_P (BB_END (a
))
937 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
940 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
944 block_label (basic_block block
)
946 if (block
== EXIT_BLOCK_PTR
)
949 if (!LABEL_P (BB_HEAD (block
)))
951 BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
954 return BB_HEAD (block
);
957 /* Attempt to perform edge redirection by replacing possibly complex jump
958 instruction by unconditional jump or removing jump completely. This can
959 apply only if all edges now point to the same block. The parameters and
960 return values are equivalent to redirect_edge_and_branch. */
963 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
965 basic_block src
= e
->src
;
966 rtx insn
= BB_END (src
), kill_from
;
970 /* If we are partitioning hot/cold basic blocks, we don't want to
971 mess up unconditional or indirect jumps that cross between hot
974 Basic block partitioning may result in some jumps that appear to
975 be optimizable (or blocks that appear to be mergeable), but which really
976 must be left untouched (they are required to make it safely across
977 partition boundaries). See the comments at the top of
978 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
980 if (find_reg_note (insn
, REG_CROSSING_JUMP
, NULL_RTX
)
981 || BB_PARTITION (src
) != BB_PARTITION (target
))
984 /* We can replace or remove a complex jump only when we have exactly
985 two edges. Also, if we have exactly one outgoing edge, we can
987 if (EDGE_COUNT (src
->succs
) >= 3
988 /* Verify that all targets will be TARGET. Specifically, the
989 edge that is not E must also go to TARGET. */
990 || (EDGE_COUNT (src
->succs
) == 2
991 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
994 if (!onlyjump_p (insn
))
996 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
999 /* Avoid removing branch with side effects. */
1000 set
= single_set (insn
);
1001 if (!set
|| side_effects_p (set
))
1004 /* In case we zap a conditional jump, we'll need to kill
1005 the cc0 setter too. */
1008 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
))
1009 && only_sets_cc0_p (PREV_INSN (insn
)))
1010 kill_from
= PREV_INSN (insn
);
1013 /* See if we can create the fallthru edge. */
1014 if (in_cfglayout
|| can_fallthru (src
, target
))
1017 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
1020 /* Selectively unlink whole insn chain. */
1023 rtx insn
= BB_FOOTER (src
);
1025 delete_insn_chain (kill_from
, BB_END (src
), false);
1027 /* Remove barriers but keep jumptables. */
1030 if (BARRIER_P (insn
))
1032 if (PREV_INSN (insn
))
1033 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1035 BB_FOOTER (src
) = NEXT_INSN (insn
);
1036 if (NEXT_INSN (insn
))
1037 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1041 insn
= NEXT_INSN (insn
);
1045 delete_insn_chain (kill_from
, PREV_INSN (BB_HEAD (target
)),
1049 /* If this already is simplejump, redirect it. */
1050 else if (simplejump_p (insn
))
1052 if (e
->dest
== target
)
1055 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
1056 INSN_UID (insn
), e
->dest
->index
, target
->index
);
1057 if (!redirect_jump (insn
, block_label (target
), 0))
1059 gcc_assert (target
== EXIT_BLOCK_PTR
);
1064 /* Cannot do anything for target exit block. */
1065 else if (target
== EXIT_BLOCK_PTR
)
1068 /* Or replace possibly complicated jump insn by simple jump insn. */
1071 rtx target_label
= block_label (target
);
1072 rtx barrier
, label
, table
;
1074 emit_jump_insn_after_noloc (gen_jump (target_label
), insn
);
1075 JUMP_LABEL (BB_END (src
)) = target_label
;
1076 LABEL_NUSES (target_label
)++;
1078 fprintf (dump_file
, "Replacing insn %i by jump %i\n",
1079 INSN_UID (insn
), INSN_UID (BB_END (src
)));
1082 delete_insn_chain (kill_from
, insn
, false);
1084 /* Recognize a tablejump that we are converting to a
1085 simple jump and remove its associated CODE_LABEL
1086 and ADDR_VEC or ADDR_DIFF_VEC. */
1087 if (tablejump_p (insn
, &label
, &table
))
1088 delete_insn_chain (label
, table
, false);
1090 barrier
= next_nonnote_insn (BB_END (src
));
1091 if (!barrier
|| !BARRIER_P (barrier
))
1092 emit_barrier_after (BB_END (src
));
1095 if (barrier
!= NEXT_INSN (BB_END (src
)))
1097 /* Move the jump before barrier so that the notes
1098 which originally were or were created before jump table are
1099 inside the basic block. */
1100 rtx new_insn
= BB_END (src
);
1102 update_bb_for_insn_chain (NEXT_INSN (BB_END (src
)),
1103 PREV_INSN (barrier
), src
);
1105 NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
1106 PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
1108 NEXT_INSN (new_insn
) = barrier
;
1109 NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
1111 PREV_INSN (new_insn
) = PREV_INSN (barrier
);
1112 PREV_INSN (barrier
) = new_insn
;
1117 /* Keep only one edge out and set proper flags. */
1118 if (!single_succ_p (src
))
1120 gcc_assert (single_succ_p (src
));
1122 e
= single_succ_edge (src
);
1124 e
->flags
= EDGE_FALLTHRU
;
1128 e
->probability
= REG_BR_PROB_BASE
;
1129 e
->count
= src
->count
;
1131 if (e
->dest
!= target
)
1132 redirect_edge_succ (e
, target
);
1136 /* Subroutine of redirect_branch_edge that tries to patch the jump
1137 instruction INSN so that it reaches block NEW. Do this
1138 only when it originally reached block OLD. Return true if this
1139 worked or the original target wasn't OLD, return false if redirection
1143 patch_jump_insn (rtx insn
, rtx old_label
, basic_block new_bb
)
1146 /* Recognize a tablejump and adjust all matching cases. */
1147 if (tablejump_p (insn
, NULL
, &tmp
))
1151 rtx new_label
= block_label (new_bb
);
1153 if (new_bb
== EXIT_BLOCK_PTR
)
1155 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
1156 vec
= XVEC (PATTERN (tmp
), 0);
1158 vec
= XVEC (PATTERN (tmp
), 1);
1160 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
1161 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
1163 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
1164 --LABEL_NUSES (old_label
);
1165 ++LABEL_NUSES (new_label
);
1168 /* Handle casesi dispatch insns. */
1169 if ((tmp
= single_set (insn
)) != NULL
1170 && SET_DEST (tmp
) == pc_rtx
1171 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
1172 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
1173 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
1175 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
1177 --LABEL_NUSES (old_label
);
1178 ++LABEL_NUSES (new_label
);
1181 else if ((tmp
= extract_asm_operands (PATTERN (insn
))) != NULL
)
1183 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (tmp
);
1184 rtx new_label
, note
;
1186 if (new_bb
== EXIT_BLOCK_PTR
)
1188 new_label
= block_label (new_bb
);
1190 for (i
= 0; i
< n
; ++i
)
1192 rtx old_ref
= ASM_OPERANDS_LABEL (tmp
, i
);
1193 gcc_assert (GET_CODE (old_ref
) == LABEL_REF
);
1194 if (XEXP (old_ref
, 0) == old_label
)
1196 ASM_OPERANDS_LABEL (tmp
, i
)
1197 = gen_rtx_LABEL_REF (Pmode
, new_label
);
1198 --LABEL_NUSES (old_label
);
1199 ++LABEL_NUSES (new_label
);
1203 if (JUMP_LABEL (insn
) == old_label
)
1205 JUMP_LABEL (insn
) = new_label
;
1206 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1208 remove_note (insn
, note
);
1212 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1214 remove_note (insn
, note
);
1215 if (JUMP_LABEL (insn
) != new_label
1216 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1217 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1219 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1221 XEXP (note
, 0) = new_label
;
1225 /* ?? We may play the games with moving the named labels from
1226 one basic block to the other in case only one computed_jump is
1228 if (computed_jump_p (insn
)
1229 /* A return instruction can't be redirected. */
1230 || returnjump_p (insn
))
1233 if (!currently_expanding_to_rtl
|| JUMP_LABEL (insn
) == old_label
)
1235 /* If the insn doesn't go where we think, we're confused. */
1236 gcc_assert (JUMP_LABEL (insn
) == old_label
);
1238 /* If the substitution doesn't succeed, die. This can happen
1239 if the back end emitted unrecognizable instructions or if
1240 target is exit block on some arches. */
1241 if (!redirect_jump (insn
, block_label (new_bb
), 0))
1243 gcc_assert (new_bb
== EXIT_BLOCK_PTR
);
1252 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1255 redirect_branch_edge (edge e
, basic_block target
)
1257 rtx old_label
= BB_HEAD (e
->dest
);
1258 basic_block src
= e
->src
;
1259 rtx insn
= BB_END (src
);
1261 /* We can only redirect non-fallthru edges of jump insn. */
1262 if (e
->flags
& EDGE_FALLTHRU
)
1264 else if (!JUMP_P (insn
) && !currently_expanding_to_rtl
)
1267 if (!currently_expanding_to_rtl
)
1269 if (!patch_jump_insn (insn
, old_label
, target
))
1273 /* When expanding this BB might actually contain multiple
1274 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1275 Redirect all of those that match our label. */
1276 FOR_BB_INSNS (src
, insn
)
1277 if (JUMP_P (insn
) && !patch_jump_insn (insn
, old_label
, target
))
1281 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
1282 e
->src
->index
, e
->dest
->index
, target
->index
);
1284 if (e
->dest
!= target
)
1285 e
= redirect_edge_succ_nodup (e
, target
);
1290 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1291 expense of adding new instructions or reordering basic blocks.
1293 Function can be also called with edge destination equivalent to the TARGET.
1294 Then it should try the simplifications and do nothing if none is possible.
1296 Return edge representing the branch if transformation succeeded. Return NULL
1298 We still return NULL in case E already destinated TARGET and we didn't
1299 managed to simplify instruction stream. */
1302 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
1305 basic_block src
= e
->src
;
1307 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1310 if (e
->dest
== target
)
1313 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
1315 df_set_bb_dirty (src
);
1319 ret
= redirect_branch_edge (e
, target
);
1323 df_set_bb_dirty (src
);
1327 /* Like force_nonfallthru below, but additionally performs redirection
1328 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1329 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1330 simple_return_rtx, indicating which kind of returnjump to create.
1331 It should be NULL otherwise. */
1334 force_nonfallthru_and_redirect (edge e
, basic_block target
, rtx jump_label
)
1336 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
1339 int abnormal_edge_flags
= 0;
1340 bool asm_goto_edge
= false;
1343 /* In the case the last instruction is conditional jump to the next
1344 instruction, first redirect the jump itself and then continue
1345 by creating a basic block afterwards to redirect fallthru edge. */
1346 if (e
->src
!= ENTRY_BLOCK_PTR
&& e
->dest
!= EXIT_BLOCK_PTR
1347 && any_condjump_p (BB_END (e
->src
))
1348 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1351 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1354 redirected
= redirect_jump (BB_END (e
->src
), block_label (target
), 0);
1355 gcc_assert (redirected
);
1357 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1360 int prob
= INTVAL (XEXP (note
, 0));
1362 b
->probability
= prob
;
1363 b
->count
= e
->count
* prob
/ REG_BR_PROB_BASE
;
1364 e
->probability
-= e
->probability
;
1365 e
->count
-= b
->count
;
1366 if (e
->probability
< 0)
1373 if (e
->flags
& EDGE_ABNORMAL
)
1375 /* Irritating special case - fallthru edge to the same block as abnormal
1377 We can't redirect abnormal edge, but we still can split the fallthru
1378 one and create separate abnormal edge to original destination.
1379 This allows bb-reorder to make such edge non-fallthru. */
1380 gcc_assert (e
->dest
== target
);
1381 abnormal_edge_flags
= e
->flags
& ~EDGE_FALLTHRU
;
1382 e
->flags
&= EDGE_FALLTHRU
;
1386 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1387 if (e
->src
== ENTRY_BLOCK_PTR
)
1389 /* We can't redirect the entry block. Create an empty block
1390 at the start of the function which we use to add the new
1396 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
, ENTRY_BLOCK_PTR
);
1398 /* Change the existing edge's source to be the new block, and add
1399 a new edge from the entry block to the new block. */
1401 for (ei
= ei_start (ENTRY_BLOCK_PTR
->succs
); (tmp
= ei_safe_edge (ei
)); )
1405 ENTRY_BLOCK_PTR
->succs
->unordered_remove (ei
.index
);
1415 vec_safe_push (bb
->succs
, e
);
1416 make_single_succ_edge (ENTRY_BLOCK_PTR
, bb
, EDGE_FALLTHRU
);
1420 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1421 don't point to the target or fallthru label. */
1422 if (JUMP_P (BB_END (e
->src
))
1423 && target
!= EXIT_BLOCK_PTR
1424 && (e
->flags
& EDGE_FALLTHRU
)
1425 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
1427 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
1428 bool adjust_jump_target
= false;
1430 for (i
= 0; i
< n
; ++i
)
1432 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (e
->dest
))
1434 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))--;
1435 XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) = block_label (target
);
1436 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))++;
1437 adjust_jump_target
= true;
1439 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (target
))
1440 asm_goto_edge
= true;
1442 if (adjust_jump_target
)
1444 rtx insn
= BB_END (e
->src
), note
;
1445 rtx old_label
= BB_HEAD (e
->dest
);
1446 rtx new_label
= BB_HEAD (target
);
1448 if (JUMP_LABEL (insn
) == old_label
)
1450 JUMP_LABEL (insn
) = new_label
;
1451 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1453 remove_note (insn
, note
);
1457 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1459 remove_note (insn
, note
);
1460 if (JUMP_LABEL (insn
) != new_label
1461 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1462 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1464 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1466 XEXP (note
, 0) = new_label
;
1470 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
|| asm_goto_edge
)
1472 gcov_type count
= e
->count
;
1473 int probability
= e
->probability
;
1474 /* Create the new structures. */
1476 /* If the old block ended with a tablejump, skip its table
1477 by searching forward from there. Otherwise start searching
1478 forward from the last instruction of the old block. */
1479 if (!tablejump_p (BB_END (e
->src
), NULL
, ¬e
))
1480 note
= BB_END (e
->src
);
1481 note
= NEXT_INSN (note
);
1483 jump_block
= create_basic_block (note
, NULL
, e
->src
);
1484 jump_block
->count
= count
;
1485 jump_block
->frequency
= EDGE_FREQUENCY (e
);
1487 /* Make sure new block ends up in correct hot/cold section. */
1489 BB_COPY_PARTITION (jump_block
, e
->src
);
1490 if (flag_reorder_blocks_and_partition
1491 && targetm_common
.have_named_sections
1492 && JUMP_P (BB_END (jump_block
))
1493 && !any_condjump_p (BB_END (jump_block
))
1494 && (EDGE_SUCC (jump_block
, 0)->flags
& EDGE_CROSSING
))
1495 add_reg_note (BB_END (jump_block
), REG_CROSSING_JUMP
, NULL_RTX
);
1498 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1499 new_edge
->probability
= probability
;
1500 new_edge
->count
= count
;
1502 /* Redirect old edge. */
1503 redirect_edge_pred (e
, jump_block
);
1504 e
->probability
= REG_BR_PROB_BASE
;
1506 /* If asm goto has any label refs to target's label,
1507 add also edge from asm goto bb to target. */
1510 new_edge
->probability
/= 2;
1511 new_edge
->count
/= 2;
1512 jump_block
->count
/= 2;
1513 jump_block
->frequency
/= 2;
1514 new_edge
= make_edge (new_edge
->src
, target
,
1515 e
->flags
& ~EDGE_FALLTHRU
);
1516 new_edge
->probability
= probability
- probability
/ 2;
1517 new_edge
->count
= count
- count
/ 2;
1520 new_bb
= jump_block
;
1523 jump_block
= e
->src
;
1525 loc
= e
->goto_locus
;
1526 e
->flags
&= ~EDGE_FALLTHRU
;
1527 if (target
== EXIT_BLOCK_PTR
)
1529 if (jump_label
== ret_rtx
)
1532 emit_jump_insn_after_setloc (gen_return (), BB_END (jump_block
), loc
);
1539 gcc_assert (jump_label
== simple_return_rtx
);
1540 #ifdef HAVE_simple_return
1541 emit_jump_insn_after_setloc (gen_simple_return (),
1542 BB_END (jump_block
), loc
);
1547 set_return_jump_label (BB_END (jump_block
));
1551 rtx label
= block_label (target
);
1552 emit_jump_insn_after_setloc (gen_jump (label
), BB_END (jump_block
), loc
);
1553 JUMP_LABEL (BB_END (jump_block
)) = label
;
1554 LABEL_NUSES (label
)++;
1557 emit_barrier_after (BB_END (jump_block
));
1558 redirect_edge_succ_nodup (e
, target
);
1560 if (abnormal_edge_flags
)
1561 make_edge (src
, target
, abnormal_edge_flags
);
1563 df_mark_solutions_dirty ();
1567 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1568 (and possibly create new basic block) to make edge non-fallthru.
1569 Return newly created BB or NULL if none. */
1572 rtl_force_nonfallthru (edge e
)
1574 return force_nonfallthru_and_redirect (e
, e
->dest
, NULL_RTX
);
1577 /* Redirect edge even at the expense of creating new jump insn or
1578 basic block. Return new basic block if created, NULL otherwise.
1579 Conversion must be possible. */
1582 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1584 if (redirect_edge_and_branch (e
, target
)
1585 || e
->dest
== target
)
1588 /* In case the edge redirection failed, try to force it to be non-fallthru
1589 and redirect newly created simplejump. */
1590 df_set_bb_dirty (e
->src
);
1591 return force_nonfallthru_and_redirect (e
, target
, NULL_RTX
);
1594 /* The given edge should potentially be a fallthru edge. If that is in
1595 fact true, delete the jump and barriers that are in the way. */
1598 rtl_tidy_fallthru_edge (edge e
)
1601 basic_block b
= e
->src
, c
= b
->next_bb
;
1603 /* ??? In a late-running flow pass, other folks may have deleted basic
1604 blocks by nopping out blocks, leaving multiple BARRIERs between here
1605 and the target label. They ought to be chastised and fixed.
1607 We can also wind up with a sequence of undeletable labels between
1608 one block and the next.
1610 So search through a sequence of barriers, labels, and notes for
1611 the head of block C and assert that we really do fall through. */
1613 for (q
= NEXT_INSN (BB_END (b
)); q
!= BB_HEAD (c
); q
= NEXT_INSN (q
))
1617 /* Remove what will soon cease being the jump insn from the source block.
1618 If block B consisted only of this single jump, turn it into a deleted
1623 && (any_uncondjump_p (q
)
1624 || single_succ_p (b
)))
1627 /* If this was a conditional jump, we need to also delete
1628 the insn that set cc0. */
1629 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1636 /* Selectively unlink the sequence. */
1637 if (q
!= PREV_INSN (BB_HEAD (c
)))
1638 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1640 e
->flags
|= EDGE_FALLTHRU
;
1643 /* Should move basic block BB after basic block AFTER. NIY. */
1646 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1647 basic_block after ATTRIBUTE_UNUSED
)
1652 /* Split a (typically critical) edge. Return the new block.
1653 The edge must not be abnormal.
1655 ??? The code generally expects to be called on critical edges.
1656 The case of a block ending in an unconditional jump to a
1657 block with multiple predecessors is not handled optimally. */
1660 rtl_split_edge (edge edge_in
)
1665 /* Abnormal edges cannot be split. */
1666 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1668 /* We are going to place the new block in front of edge destination.
1669 Avoid existence of fallthru predecessors. */
1670 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1672 edge e
= find_fallthru_edge (edge_in
->dest
->preds
);
1675 force_nonfallthru (e
);
1678 /* Create the basic block note. */
1679 if (edge_in
->dest
!= EXIT_BLOCK_PTR
)
1680 before
= BB_HEAD (edge_in
->dest
);
1684 /* If this is a fall through edge to the exit block, the blocks might be
1685 not adjacent, and the right place is after the source. */
1686 if ((edge_in
->flags
& EDGE_FALLTHRU
) && edge_in
->dest
== EXIT_BLOCK_PTR
)
1688 before
= NEXT_INSN (BB_END (edge_in
->src
));
1689 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1690 BB_COPY_PARTITION (bb
, edge_in
->src
);
1694 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1695 /* ??? Why not edge_in->dest->prev_bb here? */
1696 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1699 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1701 /* For non-fallthru edges, we must adjust the predecessor's
1702 jump instruction to target our new block. */
1703 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1705 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1706 gcc_assert (redirected
);
1710 if (edge_in
->src
!= ENTRY_BLOCK_PTR
)
1712 /* For asm goto even splitting of fallthru edge might
1713 need insn patching, as other labels might point to the
1715 rtx last
= BB_END (edge_in
->src
);
1718 && edge_in
->dest
!= EXIT_BLOCK_PTR
1719 && extract_asm_operands (PATTERN (last
)) != NULL_RTX
1720 && patch_jump_insn (last
, before
, bb
))
1721 df_set_bb_dirty (edge_in
->src
);
1723 redirect_edge_succ (edge_in
, bb
);
1729 /* Queue instructions for insertion on an edge between two basic blocks.
1730 The new instructions and basic blocks (if any) will not appear in the
1731 CFG until commit_edge_insertions is called. */
1734 insert_insn_on_edge (rtx pattern
, edge e
)
1736 /* We cannot insert instructions on an abnormal critical edge.
1737 It will be easier to find the culprit if we die now. */
1738 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1740 if (e
->insns
.r
== NULL_RTX
)
1743 push_to_sequence (e
->insns
.r
);
1745 emit_insn (pattern
);
1747 e
->insns
.r
= get_insns ();
1751 /* Update the CFG for the instructions queued on edge E. */
1754 commit_one_edge_insertion (edge e
)
1756 rtx before
= NULL_RTX
, after
= NULL_RTX
, insns
, tmp
, last
;
1759 /* Pull the insns off the edge now since the edge might go away. */
1761 e
->insns
.r
= NULL_RTX
;
1763 /* Figure out where to put these insns. If the destination has
1764 one predecessor, insert there. Except for the exit block. */
1765 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR
)
1769 /* Get the location correct wrt a code label, and "nice" wrt
1770 a basic block note, and before everything else. */
1773 tmp
= NEXT_INSN (tmp
);
1774 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1775 tmp
= NEXT_INSN (tmp
);
1776 if (tmp
== BB_HEAD (bb
))
1779 after
= PREV_INSN (tmp
);
1781 after
= get_last_insn ();
1784 /* If the source has one successor and the edge is not abnormal,
1785 insert there. Except for the entry block. */
1786 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1787 && single_succ_p (e
->src
)
1788 && e
->src
!= ENTRY_BLOCK_PTR
)
1792 /* It is possible to have a non-simple jump here. Consider a target
1793 where some forms of unconditional jumps clobber a register. This
1794 happens on the fr30 for example.
1796 We know this block has a single successor, so we can just emit
1797 the queued insns before the jump. */
1798 if (JUMP_P (BB_END (bb
)))
1799 before
= BB_END (bb
);
1802 /* We'd better be fallthru, or we've lost track of what's what. */
1803 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1805 after
= BB_END (bb
);
1809 /* Otherwise we must split the edge. */
1812 bb
= split_edge (e
);
1813 after
= BB_END (bb
);
1815 if (flag_reorder_blocks_and_partition
1816 && targetm_common
.have_named_sections
1817 && e
->src
!= ENTRY_BLOCK_PTR
1818 && BB_PARTITION (e
->src
) == BB_COLD_PARTITION
1819 && !(e
->flags
& EDGE_CROSSING
)
1821 && !any_condjump_p (after
)
1822 && (single_succ_edge (bb
)->flags
& EDGE_CROSSING
))
1823 add_reg_note (after
, REG_CROSSING_JUMP
, NULL_RTX
);
1826 /* Now that we've found the spot, do the insertion. */
1829 emit_insn_before_noloc (insns
, before
, bb
);
1830 last
= prev_nonnote_insn (before
);
1833 last
= emit_insn_after_noloc (insns
, after
, bb
);
1835 if (returnjump_p (last
))
1837 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1838 This is not currently a problem because this only happens
1839 for the (single) epilogue, which already has a fallthru edge
1842 e
= single_succ_edge (bb
);
1843 gcc_assert (e
->dest
== EXIT_BLOCK_PTR
1844 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
1846 e
->flags
&= ~EDGE_FALLTHRU
;
1847 emit_barrier_after (last
);
1850 delete_insn (before
);
1853 gcc_assert (!JUMP_P (last
));
1856 /* Update the CFG for all queued instructions. */
1859 commit_edge_insertions (void)
1863 #ifdef ENABLE_CHECKING
1864 verify_flow_info ();
1867 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
1872 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1874 commit_one_edge_insertion (e
);
1879 /* Print out RTL-specific basic block information (live information
1880 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
1881 documented in dumpfile.h. */
1884 rtl_dump_bb (FILE *outf
, basic_block bb
, int indent
, int flags
)
1890 s_indent
= (char *) alloca ((size_t) indent
+ 1);
1891 memset (s_indent
, ' ', (size_t) indent
);
1892 s_indent
[indent
] = '\0';
1894 if (df
&& (flags
& TDF_DETAILS
))
1896 df_dump_top (bb
, outf
);
1900 if (bb
->index
!= ENTRY_BLOCK
&& bb
->index
!= EXIT_BLOCK
)
1901 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
)); insn
!= last
;
1902 insn
= NEXT_INSN (insn
))
1904 if (flags
& TDF_DETAILS
)
1905 df_dump_insn_top (insn
, outf
);
1906 if (! (flags
& TDF_SLIM
))
1907 print_rtl_single (outf
, insn
);
1909 dump_insn_slim (outf
, insn
);
1910 if (flags
& TDF_DETAILS
)
1911 df_dump_insn_bottom (insn
, outf
);
1914 if (df
&& (flags
& TDF_DETAILS
))
1916 df_dump_bottom (bb
, outf
);
1922 /* Like dump_function_to_file, but for RTL. Print out dataflow information
1923 for the start of each basic block. FLAGS are the TDF_* masks documented
1927 print_rtl_with_bb (FILE *outf
, const_rtx rtx_first
, int flags
)
1931 fprintf (outf
, "(nil)\n");
1934 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
1935 int max_uid
= get_max_uid ();
1936 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
1937 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
1938 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
1941 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
1942 insns, but the CFG is not maintained so the basic block info
1943 is not reliable. Therefore it's omitted from the dumps. */
1944 if (! (cfun
->curr_properties
& PROP_cfg
))
1945 flags
&= ~TDF_BLOCKS
;
1948 df_dump_start (outf
);
1950 if (flags
& TDF_BLOCKS
)
1952 FOR_EACH_BB_REVERSE (bb
)
1956 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
1957 end
[INSN_UID (BB_END (bb
))] = bb
;
1958 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
1960 enum bb_state state
= IN_MULTIPLE_BB
;
1962 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
1964 in_bb_p
[INSN_UID (x
)] = state
;
1966 if (x
== BB_END (bb
))
1972 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
1974 if (flags
& TDF_BLOCKS
)
1976 bb
= start
[INSN_UID (tmp_rtx
)];
1979 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, true, false);
1980 if (df
&& (flags
& TDF_DETAILS
))
1981 df_dump_top (bb
, outf
);
1984 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
1985 && !NOTE_P (tmp_rtx
)
1986 && !BARRIER_P (tmp_rtx
))
1987 fprintf (outf
, ";; Insn is not within a basic block\n");
1988 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
1989 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
1992 if (flags
& TDF_DETAILS
)
1993 df_dump_insn_top (tmp_rtx
, outf
);
1994 if (! (flags
& TDF_SLIM
))
1995 print_rtl_single (outf
, tmp_rtx
);
1997 dump_insn_slim (outf
, tmp_rtx
);
1998 if (flags
& TDF_DETAILS
)
1999 df_dump_insn_bottom (tmp_rtx
, outf
);
2001 if (flags
& TDF_BLOCKS
)
2003 bb
= end
[INSN_UID (tmp_rtx
)];
2006 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, false, true);
2007 if (df
&& (flags
& TDF_DETAILS
))
2008 df_dump_bottom (bb
, outf
);
2019 if (crtl
->epilogue_delay_list
!= 0)
2021 fprintf (outf
, "\n;; Insns in epilogue delay list:\n\n");
2022 for (tmp_rtx
= crtl
->epilogue_delay_list
; tmp_rtx
!= 0;
2023 tmp_rtx
= XEXP (tmp_rtx
, 1))
2024 print_rtl_single (outf
, XEXP (tmp_rtx
, 0));
2028 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2031 update_br_prob_note (basic_block bb
)
2034 if (!JUMP_P (BB_END (bb
)))
2036 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
2037 if (!note
|| INTVAL (XEXP (note
, 0)) == BRANCH_EDGE (bb
)->probability
)
2039 XEXP (note
, 0) = GEN_INT (BRANCH_EDGE (bb
)->probability
);
2042 /* Get the last insn associated with block BB (that includes barriers and
2043 tablejumps after BB). */
2045 get_last_bb_insn (basic_block bb
)
2048 rtx end
= BB_END (bb
);
2050 /* Include any jump table following the basic block. */
2051 if (tablejump_p (end
, NULL
, &tmp
))
2054 /* Include any barriers that may follow the basic block. */
2055 tmp
= next_nonnote_insn_bb (end
);
2056 while (tmp
&& BARRIER_P (tmp
))
2059 tmp
= next_nonnote_insn_bb (end
);
2065 /* Verify the CFG and RTL consistency common for both underlying RTL and
2068 Currently it does following checks:
2070 - overlapping of basic blocks
2071 - insns with wrong BLOCK_FOR_INSN pointers
2072 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2073 - tails of basic blocks (ensure that boundary is necessary)
2074 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2075 and NOTE_INSN_BASIC_BLOCK
2076 - verify that no fall_thru edge crosses hot/cold partition boundaries
2077 - verify that there are no pending RTL branch predictions
2079 In future it can be extended check a lot of other stuff as well
2080 (reachability of basic blocks, life information, etc. etc.). */
2083 rtl_verify_flow_info_1 (void)
2089 /* Check the general integrity of the basic blocks. */
2090 FOR_EACH_BB_REVERSE (bb
)
2094 if (!(bb
->flags
& BB_RTL
))
2096 error ("BB_RTL flag not set for block %d", bb
->index
);
2100 FOR_BB_INSNS (bb
, insn
)
2101 if (BLOCK_FOR_INSN (insn
) != bb
)
2103 error ("insn %d basic block pointer is %d, should be %d",
2105 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
2110 for (insn
= BB_HEADER (bb
); insn
; insn
= NEXT_INSN (insn
))
2111 if (!BARRIER_P (insn
)
2112 && BLOCK_FOR_INSN (insn
) != NULL
)
2114 error ("insn %d in header of bb %d has non-NULL basic block",
2115 INSN_UID (insn
), bb
->index
);
2118 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
2119 if (!BARRIER_P (insn
)
2120 && BLOCK_FOR_INSN (insn
) != NULL
)
2122 error ("insn %d in footer of bb %d has non-NULL basic block",
2123 INSN_UID (insn
), bb
->index
);
2128 /* Now check the basic blocks (boundaries etc.) */
2129 FOR_EACH_BB_REVERSE (bb
)
2131 int n_fallthru
= 0, n_branch
= 0, n_abnormal_call
= 0, n_sibcall
= 0;
2132 int n_eh
= 0, n_abnormal
= 0;
2133 edge e
, fallthru
= NULL
;
2137 if (JUMP_P (BB_END (bb
))
2138 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
2139 && EDGE_COUNT (bb
->succs
) >= 2
2140 && any_condjump_p (BB_END (bb
)))
2142 if (INTVAL (XEXP (note
, 0)) != BRANCH_EDGE (bb
)->probability
2143 && profile_status
!= PROFILE_ABSENT
)
2145 error ("verify_flow_info: REG_BR_PROB does not match cfg %wi %i",
2146 INTVAL (XEXP (note
, 0)), BRANCH_EDGE (bb
)->probability
);
2150 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2154 if (e
->flags
& EDGE_FALLTHRU
)
2155 n_fallthru
++, fallthru
= e
;
2157 is_crossing
= (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
2158 && e
->src
!= ENTRY_BLOCK_PTR
2159 && e
->dest
!= EXIT_BLOCK_PTR
);
2160 if (e
->flags
& EDGE_CROSSING
)
2164 error ("EDGE_CROSSING incorrectly set across same section");
2167 if (e
->flags
& EDGE_FALLTHRU
)
2169 error ("fallthru edge crosses section boundary in bb %i",
2173 if (e
->flags
& EDGE_EH
)
2175 error ("EH edge crosses section boundary in bb %i",
2180 else if (is_crossing
)
2182 error ("EDGE_CROSSING missing across section boundary");
2186 if ((e
->flags
& ~(EDGE_DFS_BACK
2188 | EDGE_IRREDUCIBLE_LOOP
2191 | EDGE_PRESERVE
)) == 0)
2194 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2197 if (e
->flags
& EDGE_SIBCALL
)
2200 if (e
->flags
& EDGE_EH
)
2203 if (e
->flags
& EDGE_ABNORMAL
)
2207 if (n_eh
&& !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
2209 error ("missing REG_EH_REGION note at the end of bb %i", bb
->index
);
2214 error ("too many exception handling edges in bb %i", bb
->index
);
2218 && (!JUMP_P (BB_END (bb
))
2219 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
2220 || any_condjump_p (BB_END (bb
))))))
2222 error ("too many outgoing branch edges from bb %i", bb
->index
);
2225 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
2227 error ("fallthru edge after unconditional jump in bb %i", bb
->index
);
2230 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
2232 error ("wrong number of branch edges after unconditional jump"
2233 " in bb %i", bb
->index
);
2236 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
2237 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
2239 error ("wrong amount of branch edges after conditional jump"
2240 " in bb %i", bb
->index
);
2243 if (n_abnormal_call
&& !CALL_P (BB_END (bb
)))
2245 error ("abnormal call edges for non-call insn in bb %i", bb
->index
);
2248 if (n_sibcall
&& !CALL_P (BB_END (bb
)))
2250 error ("sibcall edges for non-call insn in bb %i", bb
->index
);
2253 if (n_abnormal
> n_eh
2254 && !(CALL_P (BB_END (bb
))
2255 && n_abnormal
== n_abnormal_call
+ n_sibcall
)
2256 && (!JUMP_P (BB_END (bb
))
2257 || any_condjump_p (BB_END (bb
))
2258 || any_uncondjump_p (BB_END (bb
))))
2260 error ("abnormal edges for no purpose in bb %i", bb
->index
);
2264 for (x
= BB_HEAD (bb
); x
!= NEXT_INSN (BB_END (bb
)); x
= NEXT_INSN (x
))
2265 /* We may have a barrier inside a basic block before dead code
2266 elimination. There is no BLOCK_FOR_INSN field in a barrier. */
2267 if (!BARRIER_P (x
) && BLOCK_FOR_INSN (x
) != bb
)
2270 if (! BLOCK_FOR_INSN (x
))
2272 ("insn %d inside basic block %d but block_for_insn is NULL",
2273 INSN_UID (x
), bb
->index
);
2276 ("insn %d inside basic block %d but block_for_insn is %i",
2277 INSN_UID (x
), bb
->index
, BLOCK_FOR_INSN (x
)->index
);
2282 /* OK pointers are correct. Now check the header of basic
2283 block. It ought to contain optional CODE_LABEL followed
2284 by NOTE_BASIC_BLOCK. */
2288 if (BB_END (bb
) == x
)
2290 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2298 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2300 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2305 if (BB_END (bb
) == x
)
2306 /* Do checks for empty blocks here. */
2309 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2311 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2313 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2314 INSN_UID (x
), bb
->index
);
2318 if (x
== BB_END (bb
))
2321 if (control_flow_insn_p (x
))
2323 error ("in basic block %d:", bb
->index
);
2324 fatal_insn ("flow control insn inside a basic block", x
);
2333 /* Verify the CFG and RTL consistency common for both underlying RTL and
2336 Currently it does following checks:
2337 - all checks of rtl_verify_flow_info_1
2338 - test head/end pointers
2339 - check that all insns are in the basic blocks
2340 (except the switch handling code, barriers and notes)
2341 - check that all returns are followed by barriers
2342 - check that all fallthru edge points to the adjacent blocks. */
2345 rtl_verify_flow_info (void)
2348 int err
= rtl_verify_flow_info_1 ();
2350 rtx last_head
= get_last_insn ();
2351 basic_block
*bb_info
;
2353 const rtx rtx_first
= get_insns ();
2354 basic_block last_bb_seen
= ENTRY_BLOCK_PTR
, curr_bb
= NULL
;
2355 const int max_uid
= get_max_uid ();
2357 bb_info
= XCNEWVEC (basic_block
, max_uid
);
2359 FOR_EACH_BB_REVERSE (bb
)
2362 rtx head
= BB_HEAD (bb
);
2363 rtx end
= BB_END (bb
);
2365 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2367 /* Verify the end of the basic block is in the INSN chain. */
2371 /* And that the code outside of basic blocks has NULL bb field. */
2373 && BLOCK_FOR_INSN (x
) != NULL
)
2375 error ("insn %d outside of basic blocks has non-NULL bb field",
2383 error ("end insn %d for block %d not found in the insn stream",
2384 INSN_UID (end
), bb
->index
);
2388 /* Work backwards from the end to the head of the basic block
2389 to verify the head is in the RTL chain. */
2390 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2392 /* While walking over the insn chain, verify insns appear
2393 in only one basic block. */
2394 if (bb_info
[INSN_UID (x
)] != NULL
)
2396 error ("insn %d is in multiple basic blocks (%d and %d)",
2397 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2401 bb_info
[INSN_UID (x
)] = bb
;
2408 error ("head insn %d for block %d not found in the insn stream",
2409 INSN_UID (head
), bb
->index
);
2413 last_head
= PREV_INSN (x
);
2415 e
= find_fallthru_edge (bb
->succs
);
2420 /* Ensure existence of barrier in BB with no fallthru edges. */
2421 for (insn
= NEXT_INSN (BB_END (bb
)); ; insn
= NEXT_INSN (insn
))
2423 if (!insn
|| NOTE_INSN_BASIC_BLOCK_P (insn
))
2425 error ("missing barrier after block %i", bb
->index
);
2429 if (BARRIER_P (insn
))
2433 else if (e
->src
!= ENTRY_BLOCK_PTR
2434 && e
->dest
!= EXIT_BLOCK_PTR
)
2438 if (e
->src
->next_bb
!= e
->dest
)
2441 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2442 e
->src
->index
, e
->dest
->index
);
2446 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
2447 insn
= NEXT_INSN (insn
))
2448 if (BARRIER_P (insn
) || INSN_P (insn
))
2450 error ("verify_flow_info: Incorrect fallthru %i->%i",
2451 e
->src
->index
, e
->dest
->index
);
2452 fatal_insn ("wrong insn in the fallthru edge", insn
);
2458 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2460 /* Check that the code before the first basic block has NULL
2463 && BLOCK_FOR_INSN (x
) != NULL
)
2465 error ("insn %d outside of basic blocks has non-NULL bb field",
2473 last_bb_seen
= ENTRY_BLOCK_PTR
;
2475 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2477 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2479 bb
= NOTE_BASIC_BLOCK (x
);
2482 if (bb
!= last_bb_seen
->next_bb
)
2483 internal_error ("basic blocks not laid down consecutively");
2485 curr_bb
= last_bb_seen
= bb
;
2490 switch (GET_CODE (x
))
2497 /* An addr_vec is placed outside any basic block. */
2499 && JUMP_TABLE_DATA_P (NEXT_INSN (x
)))
2502 /* But in any case, non-deletable labels can appear anywhere. */
2506 fatal_insn ("insn outside basic block", x
);
2511 && returnjump_p (x
) && ! condjump_p (x
)
2512 && ! (next_nonnote_insn (x
) && BARRIER_P (next_nonnote_insn (x
))))
2513 fatal_insn ("return not followed by barrier", x
);
2514 if (curr_bb
&& x
== BB_END (curr_bb
))
2518 if (num_bb_notes
!= n_basic_blocks
- NUM_FIXED_BLOCKS
)
2520 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2521 num_bb_notes
, n_basic_blocks
);
2526 /* Assume that the preceding pass has possibly eliminated jump instructions
2527 or converted the unconditional jumps. Eliminate the edges from CFG.
2528 Return true if any edges are eliminated. */
2531 purge_dead_edges (basic_block bb
)
2534 rtx insn
= BB_END (bb
), note
;
2535 bool purged
= false;
2539 if (DEBUG_INSN_P (insn
) && insn
!= BB_HEAD (bb
))
2541 insn
= PREV_INSN (insn
);
2542 while ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
));
2544 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2545 if (NONJUMP_INSN_P (insn
)
2546 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
2550 if (! may_trap_p (PATTERN (insn
))
2551 || ((eqnote
= find_reg_equal_equiv_note (insn
))
2552 && ! may_trap_p (XEXP (eqnote
, 0))))
2553 remove_note (insn
, note
);
2556 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
2557 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
2559 bool remove
= false;
2561 /* There are three types of edges we need to handle correctly here: EH
2562 edges, abnormal call EH edges, and abnormal call non-EH edges. The
2563 latter can appear when nonlocal gotos are used. */
2564 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2568 else if (can_nonlocal_goto (insn
))
2570 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
2572 else if (flag_tm
&& find_reg_note (insn
, REG_TM
, NULL
))
2577 else if (e
->flags
& EDGE_EH
)
2578 remove
= !can_throw_internal (insn
);
2583 df_set_bb_dirty (bb
);
2596 /* We do care only about conditional jumps and simplejumps. */
2597 if (!any_condjump_p (insn
)
2598 && !returnjump_p (insn
)
2599 && !simplejump_p (insn
))
2602 /* Branch probability/prediction notes are defined only for
2603 condjumps. We've possibly turned condjump into simplejump. */
2604 if (simplejump_p (insn
))
2606 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2608 remove_note (insn
, note
);
2609 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
2610 remove_note (insn
, note
);
2613 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
2615 /* Avoid abnormal flags to leak from computed jumps turned
2616 into simplejumps. */
2618 e
->flags
&= ~EDGE_ABNORMAL
;
2620 /* See if this edge is one we should keep. */
2621 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
2622 /* A conditional jump can fall through into the next
2623 block, so we should keep the edge. */
2628 else if (e
->dest
!= EXIT_BLOCK_PTR
2629 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
2630 /* If the destination block is the target of the jump,
2636 else if (e
->dest
== EXIT_BLOCK_PTR
&& returnjump_p (insn
))
2637 /* If the destination block is the exit block, and this
2638 instruction is a return, then keep the edge. */
2643 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
2644 /* Keep the edges that correspond to exceptions thrown by
2645 this instruction and rematerialize the EDGE_ABNORMAL
2646 flag we just cleared above. */
2648 e
->flags
|= EDGE_ABNORMAL
;
2653 /* We do not need this edge. */
2654 df_set_bb_dirty (bb
);
2659 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
2663 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
2668 /* Redistribute probabilities. */
2669 if (single_succ_p (bb
))
2671 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
2672 single_succ_edge (bb
)->count
= bb
->count
;
2676 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2680 b
= BRANCH_EDGE (bb
);
2681 f
= FALLTHRU_EDGE (bb
);
2682 b
->probability
= INTVAL (XEXP (note
, 0));
2683 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
2684 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
2685 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
2690 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
2692 /* First, there should not be any EH or ABCALL edges resulting
2693 from non-local gotos and the like. If there were, we shouldn't
2694 have created the sibcall in the first place. Second, there
2695 should of course never have been a fallthru edge. */
2696 gcc_assert (single_succ_p (bb
));
2697 gcc_assert (single_succ_edge (bb
)->flags
2698 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
2703 /* If we don't see a jump insn, we don't know exactly why the block would
2704 have been broken at this point. Look for a simple, non-fallthru edge,
2705 as these are only created by conditional branches. If we find such an
2706 edge we know that there used to be a jump here and can then safely
2707 remove all non-fallthru edges. */
2709 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2710 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
2719 /* Remove all but the fake and fallthru edges. The fake edge may be
2720 the only successor for this block in the case of noreturn
2722 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
2724 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
2726 df_set_bb_dirty (bb
);
2734 gcc_assert (single_succ_p (bb
));
2736 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
2737 single_succ_edge (bb
)->count
= bb
->count
;
2740 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
2745 /* Search all basic blocks for potentially dead edges and purge them. Return
2746 true if some edge has been eliminated. */
2749 purge_all_dead_edges (void)
2756 bool purged_here
= purge_dead_edges (bb
);
2758 purged
|= purged_here
;
2764 /* This is used by a few passes that emit some instructions after abnormal
2765 calls, moving the basic block's end, while they in fact do want to emit
2766 them on the fallthru edge. Look for abnormal call edges, find backward
2767 the call in the block and insert the instructions on the edge instead.
2769 Similarly, handle instructions throwing exceptions internally.
2771 Return true when instructions have been found and inserted on edges. */
2774 fixup_abnormal_edges (void)
2776 bool inserted
= false;
2784 /* Look for cases we are interested in - calls or instructions causing
2786 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2787 if ((e
->flags
& EDGE_ABNORMAL_CALL
)
2788 || ((e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
2789 == (EDGE_ABNORMAL
| EDGE_EH
)))
2792 if (e
&& !CALL_P (BB_END (bb
)) && !can_throw_internal (BB_END (bb
)))
2796 /* Get past the new insns generated. Allow notes, as the insns
2797 may be already deleted. */
2799 while ((NONJUMP_INSN_P (insn
) || NOTE_P (insn
))
2800 && !can_throw_internal (insn
)
2801 && insn
!= BB_HEAD (bb
))
2802 insn
= PREV_INSN (insn
);
2804 if (CALL_P (insn
) || can_throw_internal (insn
))
2808 e
= find_fallthru_edge (bb
->succs
);
2810 stop
= NEXT_INSN (BB_END (bb
));
2813 for (insn
= NEXT_INSN (insn
); insn
!= stop
; insn
= next
)
2815 next
= NEXT_INSN (insn
);
2820 /* Sometimes there's still the return value USE.
2821 If it's placed after a trapping call (i.e. that
2822 call is the last insn anyway), we have no fallthru
2823 edge. Simply delete this use and don't try to insert
2824 on the non-existent edge. */
2825 if (GET_CODE (PATTERN (insn
)) != USE
)
2827 /* We're not deleting it, we're moving it. */
2828 INSN_DELETED_P (insn
) = 0;
2829 PREV_INSN (insn
) = NULL_RTX
;
2830 NEXT_INSN (insn
) = NULL_RTX
;
2832 insert_insn_on_edge (insn
, e
);
2836 else if (!BARRIER_P (insn
))
2837 set_block_for_insn (insn
, NULL
);
2841 /* It may be that we don't find any trapping insn. In this
2842 case we discovered quite late that the insn that had been
2843 marked as can_throw_internal in fact couldn't trap at all.
2844 So we should in fact delete the EH edges out of the block. */
2846 purge_dead_edges (bb
);
2853 /* Cut the insns from FIRST to LAST out of the insns stream. */
2856 unlink_insn_chain (rtx first
, rtx last
)
2858 rtx prevfirst
= PREV_INSN (first
);
2859 rtx nextlast
= NEXT_INSN (last
);
2861 PREV_INSN (first
) = NULL
;
2862 NEXT_INSN (last
) = NULL
;
2864 NEXT_INSN (prevfirst
) = nextlast
;
2866 PREV_INSN (nextlast
) = prevfirst
;
2868 set_last_insn (prevfirst
);
2870 set_first_insn (nextlast
);
2874 /* Skip over inter-block insns occurring after BB which are typically
2875 associated with BB (e.g., barriers). If there are any such insns,
2876 we return the last one. Otherwise, we return the end of BB. */
2879 skip_insns_after_block (basic_block bb
)
2881 rtx insn
, last_insn
, next_head
, prev
;
2883 next_head
= NULL_RTX
;
2884 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
2885 next_head
= BB_HEAD (bb
->next_bb
);
2887 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
2889 if (insn
== next_head
)
2892 switch (GET_CODE (insn
))
2899 switch (NOTE_KIND (insn
))
2901 case NOTE_INSN_BLOCK_END
:
2911 if (NEXT_INSN (insn
)
2912 && JUMP_TABLE_DATA_P (NEXT_INSN (insn
)))
2914 insn
= NEXT_INSN (insn
);
2927 /* It is possible to hit contradictory sequence. For instance:
2933 Where barrier belongs to jump_insn, but the note does not. This can be
2934 created by removing the basic block originally following
2935 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
2937 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
2939 prev
= PREV_INSN (insn
);
2941 switch (NOTE_KIND (insn
))
2943 case NOTE_INSN_BLOCK_END
:
2946 case NOTE_INSN_DELETED
:
2947 case NOTE_INSN_DELETED_LABEL
:
2948 case NOTE_INSN_DELETED_DEBUG_LABEL
:
2951 reorder_insns (insn
, insn
, last_insn
);
2958 /* Locate or create a label for a given basic block. */
2961 label_for_bb (basic_block bb
)
2963 rtx label
= BB_HEAD (bb
);
2965 if (!LABEL_P (label
))
2968 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
2970 label
= block_label (bb
);
2976 /* Locate the effective beginning and end of the insn chain for each
2977 block, as defined by skip_insns_after_block above. */
2980 record_effective_endpoints (void)
2986 for (insn
= get_insns ();
2989 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
;
2990 insn
= NEXT_INSN (insn
))
2992 /* No basic blocks at all? */
2995 if (PREV_INSN (insn
))
2996 cfg_layout_function_header
=
2997 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
2999 cfg_layout_function_header
= NULL_RTX
;
3001 next_insn
= get_insns ();
3006 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
3007 BB_HEADER (bb
) = unlink_insn_chain (next_insn
,
3008 PREV_INSN (BB_HEAD (bb
)));
3009 end
= skip_insns_after_block (bb
);
3010 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
3011 BB_FOOTER (bb
) = unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
3012 next_insn
= NEXT_INSN (BB_END (bb
));
3015 cfg_layout_function_footer
= next_insn
;
3016 if (cfg_layout_function_footer
)
3017 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
3021 into_cfg_layout_mode (void)
3023 cfg_layout_initialize (0);
3028 outof_cfg_layout_mode (void)
3033 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
3034 bb
->aux
= bb
->next_bb
;
3036 cfg_layout_finalize ();
3041 struct rtl_opt_pass pass_into_cfg_layout_mode
=
3045 "into_cfglayout", /* name */
3046 OPTGROUP_NONE
, /* optinfo_flags */
3048 into_cfg_layout_mode
, /* execute */
3051 0, /* static_pass_number */
3053 0, /* properties_required */
3054 PROP_cfglayout
, /* properties_provided */
3055 0, /* properties_destroyed */
3056 0, /* todo_flags_start */
3057 0 /* todo_flags_finish */
3061 struct rtl_opt_pass pass_outof_cfg_layout_mode
=
3065 "outof_cfglayout", /* name */
3066 OPTGROUP_NONE
, /* optinfo_flags */
3068 outof_cfg_layout_mode
, /* execute */
3071 0, /* static_pass_number */
3073 0, /* properties_required */
3074 0, /* properties_provided */
3075 PROP_cfglayout
, /* properties_destroyed */
3076 0, /* todo_flags_start */
3077 0 /* todo_flags_finish */
3082 /* Link the basic blocks in the correct order, compacting the basic
3083 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3084 function also clears the basic block header and footer fields.
3086 This function is usually called after a pass (e.g. tracer) finishes
3087 some transformations while in cfglayout mode. The required sequence
3088 of the basic blocks is in a linked list along the bb->aux field.
3089 This functions re-links the basic block prev_bb and next_bb pointers
3090 accordingly, and it compacts and renumbers the blocks.
3092 FIXME: This currently works only for RTL, but the only RTL-specific
3093 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3094 to GIMPLE a long time ago, but it doesn't relink the basic block
3095 chain. It could do that (to give better initial RTL) if this function
3096 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3099 relink_block_chain (bool stay_in_cfglayout_mode
)
3101 basic_block bb
, prev_bb
;
3104 /* Maybe dump the re-ordered sequence. */
3107 fprintf (dump_file
, "Reordered sequence:\n");
3108 for (bb
= ENTRY_BLOCK_PTR
->next_bb
, index
= NUM_FIXED_BLOCKS
;
3110 bb
= (basic_block
) bb
->aux
, index
++)
3112 fprintf (dump_file
, " %i ", index
);
3113 if (get_bb_original (bb
))
3114 fprintf (dump_file
, "duplicate of %i ",
3115 get_bb_original (bb
)->index
);
3116 else if (forwarder_block_p (bb
)
3117 && !LABEL_P (BB_HEAD (bb
)))
3118 fprintf (dump_file
, "compensation ");
3120 fprintf (dump_file
, "bb %i ", bb
->index
);
3121 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
3125 /* Now reorder the blocks. */
3126 prev_bb
= ENTRY_BLOCK_PTR
;
3127 bb
= ENTRY_BLOCK_PTR
->next_bb
;
3128 for (; bb
; prev_bb
= bb
, bb
= (basic_block
) bb
->aux
)
3130 bb
->prev_bb
= prev_bb
;
3131 prev_bb
->next_bb
= bb
;
3133 prev_bb
->next_bb
= EXIT_BLOCK_PTR
;
3134 EXIT_BLOCK_PTR
->prev_bb
= prev_bb
;
3136 /* Then, clean up the aux fields. */
3140 if (!stay_in_cfglayout_mode
)
3141 BB_HEADER (bb
) = BB_FOOTER (bb
) = NULL
;
3144 /* Maybe reset the original copy tables, they are not valid anymore
3145 when we renumber the basic blocks in compact_blocks. If we are
3146 are going out of cfglayout mode, don't re-allocate the tables. */
3147 free_original_copy_tables ();
3148 if (stay_in_cfglayout_mode
)
3149 initialize_original_copy_tables ();
3151 /* Finally, put basic_block_info in the new order. */
3156 /* Given a reorder chain, rearrange the code to match. */
3159 fixup_reorder_chain (void)
3164 if (cfg_layout_function_header
)
3166 set_first_insn (cfg_layout_function_header
);
3167 insn
= cfg_layout_function_header
;
3168 while (NEXT_INSN (insn
))
3169 insn
= NEXT_INSN (insn
);
3172 /* First do the bulk reordering -- rechain the blocks without regard to
3173 the needed changes to jumps and labels. */
3175 for (bb
= ENTRY_BLOCK_PTR
->next_bb
; bb
; bb
= (basic_block
) bb
->aux
)
3180 NEXT_INSN (insn
) = BB_HEADER (bb
);
3182 set_first_insn (BB_HEADER (bb
));
3183 PREV_INSN (BB_HEADER (bb
)) = insn
;
3184 insn
= BB_HEADER (bb
);
3185 while (NEXT_INSN (insn
))
3186 insn
= NEXT_INSN (insn
);
3189 NEXT_INSN (insn
) = BB_HEAD (bb
);
3191 set_first_insn (BB_HEAD (bb
));
3192 PREV_INSN (BB_HEAD (bb
)) = insn
;
3196 NEXT_INSN (insn
) = BB_FOOTER (bb
);
3197 PREV_INSN (BB_FOOTER (bb
)) = insn
;
3198 while (NEXT_INSN (insn
))
3199 insn
= NEXT_INSN (insn
);
3203 NEXT_INSN (insn
) = cfg_layout_function_footer
;
3204 if (cfg_layout_function_footer
)
3205 PREV_INSN (cfg_layout_function_footer
) = insn
;
3207 while (NEXT_INSN (insn
))
3208 insn
= NEXT_INSN (insn
);
3210 set_last_insn (insn
);
3211 #ifdef ENABLE_CHECKING
3212 verify_insn_chain ();
3215 /* Now add jumps and labels as needed to match the blocks new
3218 for (bb
= ENTRY_BLOCK_PTR
->next_bb
; bb
; bb
= (basic_block
) bb
->aux
)
3220 edge e_fall
, e_taken
, e
;
3222 rtx ret_label
= NULL_RTX
;
3223 basic_block nb
, src_bb
;
3226 if (EDGE_COUNT (bb
->succs
) == 0)
3229 /* Find the old fallthru edge, and another non-EH edge for
3231 e_taken
= e_fall
= NULL
;
3233 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3234 if (e
->flags
& EDGE_FALLTHRU
)
3236 else if (! (e
->flags
& EDGE_EH
))
3239 bb_end_insn
= BB_END (bb
);
3240 if (JUMP_P (bb_end_insn
))
3242 ret_label
= JUMP_LABEL (bb_end_insn
);
3243 if (any_condjump_p (bb_end_insn
))
3245 /* This might happen if the conditional jump has side
3246 effects and could therefore not be optimized away.
3247 Make the basic block to end with a barrier in order
3248 to prevent rtl_verify_flow_info from complaining. */
3251 gcc_assert (!onlyjump_p (bb_end_insn
)
3252 || returnjump_p (bb_end_insn
));
3253 BB_FOOTER (bb
) = emit_barrier_after (bb_end_insn
);
3257 /* If the old fallthru is still next, nothing to do. */
3258 if (bb
->aux
== e_fall
->dest
3259 || e_fall
->dest
== EXIT_BLOCK_PTR
)
3262 /* The degenerated case of conditional jump jumping to the next
3263 instruction can happen for jumps with side effects. We need
3264 to construct a forwarder block and this will be done just
3265 fine by force_nonfallthru below. */
3269 /* There is another special case: if *neither* block is next,
3270 such as happens at the very end of a function, then we'll
3271 need to add a new unconditional jump. Choose the taken
3272 edge based on known or assumed probability. */
3273 else if (bb
->aux
!= e_taken
->dest
)
3275 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
3278 && INTVAL (XEXP (note
, 0)) < REG_BR_PROB_BASE
/ 2
3279 && invert_jump (bb_end_insn
,
3280 (e_fall
->dest
== EXIT_BLOCK_PTR
3282 : label_for_bb (e_fall
->dest
)), 0))
3284 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3285 gcc_checking_assert (could_fall_through
3286 (e_taken
->src
, e_taken
->dest
));
3287 e_taken
->flags
|= EDGE_FALLTHRU
;
3288 update_br_prob_note (bb
);
3289 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
3293 /* If the "jumping" edge is a crossing edge, and the fall
3294 through edge is non-crossing, leave things as they are. */
3295 else if ((e_taken
->flags
& EDGE_CROSSING
)
3296 && !(e_fall
->flags
& EDGE_CROSSING
))
3299 /* Otherwise we can try to invert the jump. This will
3300 basically never fail, however, keep up the pretense. */
3301 else if (invert_jump (bb_end_insn
,
3302 (e_fall
->dest
== EXIT_BLOCK_PTR
3304 : label_for_bb (e_fall
->dest
)), 0))
3306 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3307 gcc_checking_assert (could_fall_through
3308 (e_taken
->src
, e_taken
->dest
));
3309 e_taken
->flags
|= EDGE_FALLTHRU
;
3310 update_br_prob_note (bb
);
3311 if (LABEL_NUSES (ret_label
) == 0
3312 && single_pred_p (e_taken
->dest
))
3313 delete_insn (ret_label
);
3317 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
3319 /* If the old fallthru is still next or if
3320 asm goto doesn't have a fallthru (e.g. when followed by
3321 __builtin_unreachable ()), nothing to do. */
3323 || bb
->aux
== e_fall
->dest
3324 || e_fall
->dest
== EXIT_BLOCK_PTR
)
3327 /* Otherwise we'll have to use the fallthru fixup below. */
3331 /* Otherwise we have some return, switch or computed
3332 jump. In the 99% case, there should not have been a
3334 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
3340 /* No fallthru implies a noreturn function with EH edges, or
3341 something similarly bizarre. In any case, we don't need to
3346 /* If the fallthru block is still next, nothing to do. */
3347 if (bb
->aux
== e_fall
->dest
)
3350 /* A fallthru to exit block. */
3351 if (e_fall
->dest
== EXIT_BLOCK_PTR
)
3355 /* We got here if we need to add a new jump insn.
3356 Note force_nonfallthru can delete E_FALL and thus we have to
3357 save E_FALL->src prior to the call to force_nonfallthru. */
3358 src_bb
= e_fall
->src
;
3359 nb
= force_nonfallthru_and_redirect (e_fall
, e_fall
->dest
, ret_label
);
3364 /* Don't process this new block. */
3367 /* Make sure new bb is tagged for correct section (same as
3368 fall-thru source, since you cannot fall-thru across
3369 section boundaries). */
3370 BB_COPY_PARTITION (src_bb
, single_pred (bb
));
3371 if (flag_reorder_blocks_and_partition
3372 && targetm_common
.have_named_sections
3373 && JUMP_P (BB_END (bb
))
3374 && !any_condjump_p (BB_END (bb
))
3375 && (EDGE_SUCC (bb
, 0)->flags
& EDGE_CROSSING
))
3376 add_reg_note (BB_END (bb
), REG_CROSSING_JUMP
, NULL_RTX
);
3380 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3382 /* Annoying special case - jump around dead jumptables left in the code. */
3385 edge e
= find_fallthru_edge (bb
->succs
);
3387 if (e
&& !can_fallthru (e
->src
, e
->dest
))
3388 force_nonfallthru (e
);
3391 /* Ensure goto_locus from edges has some instructions with that locus
3399 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3400 if (LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
3401 && !(e
->flags
& EDGE_ABNORMAL
))
3405 basic_block dest
, nb
;
3408 insn
= BB_END (e
->src
);
3409 end
= PREV_INSN (BB_HEAD (e
->src
));
3411 && (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
3412 insn
= PREV_INSN (insn
);
3414 && INSN_LOCATION (insn
) == e
->goto_locus
)
3416 if (simplejump_p (BB_END (e
->src
))
3417 && !INSN_HAS_LOCATION (BB_END (e
->src
)))
3419 INSN_LOCATION (BB_END (e
->src
)) = e
->goto_locus
;
3423 if (dest
== EXIT_BLOCK_PTR
)
3425 /* Non-fallthru edges to the exit block cannot be split. */
3426 if (!(e
->flags
& EDGE_FALLTHRU
))
3431 insn
= BB_HEAD (dest
);
3432 end
= NEXT_INSN (BB_END (dest
));
3433 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
3434 insn
= NEXT_INSN (insn
);
3435 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
3436 && INSN_LOCATION (insn
) == e
->goto_locus
)
3439 nb
= split_edge (e
);
3440 if (!INSN_P (BB_END (nb
)))
3441 BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
3443 INSN_LOCATION (BB_END (nb
)) = e
->goto_locus
;
3445 /* If there are other incoming edges to the destination block
3446 with the same goto locus, redirect them to the new block as
3447 well, this can prevent other such blocks from being created
3448 in subsequent iterations of the loop. */
3449 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
3450 if (LOCATION_LOCUS (e2
->goto_locus
) != UNKNOWN_LOCATION
3451 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
3452 && e
->goto_locus
== e2
->goto_locus
)
3453 redirect_edge_and_branch (e2
, nb
);
3460 /* Perform sanity checks on the insn chain.
3461 1. Check that next/prev pointers are consistent in both the forward and
3463 2. Count insns in chain, going both directions, and check if equal.
3464 3. Check that get_last_insn () returns the actual end of chain. */
3467 verify_insn_chain (void)
3469 rtx x
, prevx
, nextx
;
3470 int insn_cnt1
, insn_cnt2
;
3472 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
3474 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
3475 gcc_assert (PREV_INSN (x
) == prevx
);
3477 gcc_assert (prevx
== get_last_insn ());
3479 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
3481 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
3482 gcc_assert (NEXT_INSN (x
) == nextx
);
3484 gcc_assert (insn_cnt1
== insn_cnt2
);
3487 /* If we have assembler epilogues, the block falling through to exit must
3488 be the last one in the reordered chain when we reach final. Ensure
3489 that this condition is met. */
3491 fixup_fallthru_exit_predecessor (void)
3494 basic_block bb
= NULL
;
3496 /* This transformation is not valid before reload, because we might
3497 separate a call from the instruction that copies the return
3499 gcc_assert (reload_completed
);
3501 e
= find_fallthru_edge (EXIT_BLOCK_PTR
->preds
);
3507 basic_block c
= ENTRY_BLOCK_PTR
->next_bb
;
3509 /* If the very first block is the one with the fall-through exit
3510 edge, we have to split that block. */
3513 bb
= split_block (bb
, NULL
)->dest
;
3516 BB_FOOTER (bb
) = BB_FOOTER (c
);
3517 BB_FOOTER (c
) = NULL
;
3520 while (c
->aux
!= bb
)
3521 c
= (basic_block
) c
->aux
;
3525 c
= (basic_block
) c
->aux
;
3532 /* In case there are more than one fallthru predecessors of exit, force that
3533 there is only one. */
3536 force_one_exit_fallthru (void)
3538 edge e
, predecessor
= NULL
;
3541 basic_block forwarder
, bb
;
3543 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
3544 if (e
->flags
& EDGE_FALLTHRU
)
3546 if (predecessor
== NULL
)
3558 /* Exit has several fallthru predecessors. Create a forwarder block for
3560 forwarder
= split_edge (predecessor
);
3561 for (ei
= ei_start (EXIT_BLOCK_PTR
->preds
); (e
= ei_safe_edge (ei
)); )
3563 if (e
->src
== forwarder
3564 || !(e
->flags
& EDGE_FALLTHRU
))
3567 redirect_edge_and_branch_force (e
, forwarder
);
3570 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
3574 if (bb
->aux
== NULL
&& bb
!= forwarder
)
3576 bb
->aux
= forwarder
;
3582 /* Return true in case it is possible to duplicate the basic block BB. */
3585 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
3587 /* Do not attempt to duplicate tablejumps, as we need to unshare
3588 the dispatch table. This is difficult to do, as the instructions
3589 computing jump destination may be hoisted outside the basic block. */
3590 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
3593 /* Do not duplicate blocks containing insns that can't be copied. */
3594 if (targetm
.cannot_copy_insn_p
)
3596 rtx insn
= BB_HEAD (bb
);
3599 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
3601 if (insn
== BB_END (bb
))
3603 insn
= NEXT_INSN (insn
);
3611 duplicate_insn_chain (rtx from
, rtx to
)
3613 rtx insn
, last
, copy
;
3615 /* Avoid updating of boundaries of previous basic block. The
3616 note will get removed from insn stream in fixup. */
3617 last
= emit_note (NOTE_INSN_DELETED
);
3619 /* Create copy at the end of INSN chain. The chain will
3620 be reordered later. */
3621 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
3623 switch (GET_CODE (insn
))
3626 /* Don't duplicate label debug insns. */
3627 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
)
3633 /* Avoid copying of dispatch tables. We never duplicate
3634 tablejumps, so this can hit only in case the table got
3635 moved far from original jump. */
3636 if (GET_CODE (PATTERN (insn
)) == ADDR_VEC
3637 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
)
3639 /* Avoid copying following barrier as well if any
3640 (and debug insns in between). */
3643 for (next
= NEXT_INSN (insn
);
3644 next
!= NEXT_INSN (to
);
3645 next
= NEXT_INSN (next
))
3646 if (!DEBUG_INSN_P (next
))
3648 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
3652 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
3653 if (JUMP_P (insn
) && JUMP_LABEL (insn
) != NULL_RTX
3654 && ANY_RETURN_P (JUMP_LABEL (insn
)))
3655 JUMP_LABEL (copy
) = JUMP_LABEL (insn
);
3656 maybe_copy_prologue_epilogue_insn (insn
, copy
);
3667 switch (NOTE_KIND (insn
))
3669 /* In case prologue is empty and function contain label
3670 in first BB, we may want to copy the block. */
3671 case NOTE_INSN_PROLOGUE_END
:
3673 case NOTE_INSN_DELETED
:
3674 case NOTE_INSN_DELETED_LABEL
:
3675 case NOTE_INSN_DELETED_DEBUG_LABEL
:
3676 /* No problem to strip these. */
3677 case NOTE_INSN_FUNCTION_BEG
:
3678 /* There is always just single entry to function. */
3679 case NOTE_INSN_BASIC_BLOCK
:
3682 case NOTE_INSN_EPILOGUE_BEG
:
3683 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
3684 emit_note_copy (insn
);
3688 /* All other notes should have already been eliminated. */
3696 insn
= NEXT_INSN (last
);
3701 /* Create a duplicate of the basic block BB. */
3704 cfg_layout_duplicate_bb (basic_block bb
)
3709 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
3710 new_bb
= create_basic_block (insn
,
3711 insn
? get_last_insn () : NULL
,
3712 EXIT_BLOCK_PTR
->prev_bb
);
3714 BB_COPY_PARTITION (new_bb
, bb
);
3717 insn
= BB_HEADER (bb
);
3718 while (NEXT_INSN (insn
))
3719 insn
= NEXT_INSN (insn
);
3720 insn
= duplicate_insn_chain (BB_HEADER (bb
), insn
);
3722 BB_HEADER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
3727 insn
= BB_FOOTER (bb
);
3728 while (NEXT_INSN (insn
))
3729 insn
= NEXT_INSN (insn
);
3730 insn
= duplicate_insn_chain (BB_FOOTER (bb
), insn
);
3732 BB_FOOTER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
3739 /* Main entry point to this module - initialize the datastructures for
3740 CFG layout changes. It keeps LOOPS up-to-date if not null.
3742 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
3745 cfg_layout_initialize (unsigned int flags
)
3750 initialize_original_copy_tables ();
3752 cfg_layout_rtl_register_cfg_hooks ();
3754 record_effective_endpoints ();
3756 /* Make sure that the targets of non local gotos are marked. */
3757 for (x
= nonlocal_goto_handler_labels
; x
; x
= XEXP (x
, 1))
3759 bb
= BLOCK_FOR_INSN (XEXP (x
, 0));
3760 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
3763 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
3766 /* Splits superblocks. */
3768 break_superblocks (void)
3770 sbitmap superblocks
;
3774 superblocks
= sbitmap_alloc (last_basic_block
);
3775 bitmap_clear (superblocks
);
3778 if (bb
->flags
& BB_SUPERBLOCK
)
3780 bb
->flags
&= ~BB_SUPERBLOCK
;
3781 bitmap_set_bit (superblocks
, bb
->index
);
3787 rebuild_jump_labels (get_insns ());
3788 find_many_sub_basic_blocks (superblocks
);
3794 /* Finalize the changes: reorder insn list according to the sequence specified
3795 by aux pointers, enter compensation code, rebuild scope forest. */
3798 cfg_layout_finalize (void)
3800 #ifdef ENABLE_CHECKING
3801 verify_flow_info ();
3803 force_one_exit_fallthru ();
3804 rtl_register_cfg_hooks ();
3805 if (reload_completed
3806 #ifdef HAVE_epilogue
3810 fixup_fallthru_exit_predecessor ();
3811 fixup_reorder_chain ();
3813 rebuild_jump_labels (get_insns ());
3814 delete_dead_jumptables ();
3816 #ifdef ENABLE_CHECKING
3817 verify_insn_chain ();
3818 verify_flow_info ();
3823 /* Same as split_block but update cfg_layout structures. */
3826 cfg_layout_split_block (basic_block bb
, void *insnp
)
3828 rtx insn
= (rtx
) insnp
;
3829 basic_block new_bb
= rtl_split_block (bb
, insn
);
3831 BB_FOOTER (new_bb
) = BB_FOOTER (bb
);
3832 BB_FOOTER (bb
) = NULL
;
3837 /* Redirect Edge to DEST. */
3839 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
3841 basic_block src
= e
->src
;
3844 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
3847 if (e
->dest
== dest
)
3850 if (e
->src
!= ENTRY_BLOCK_PTR
3851 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
3853 df_set_bb_dirty (src
);
3857 if (e
->src
== ENTRY_BLOCK_PTR
3858 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
3861 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
3862 e
->src
->index
, dest
->index
);
3864 df_set_bb_dirty (e
->src
);
3865 redirect_edge_succ (e
, dest
);
3869 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
3870 in the case the basic block appears to be in sequence. Avoid this
3873 if (e
->flags
& EDGE_FALLTHRU
)
3875 /* Redirect any branch edges unified with the fallthru one. */
3876 if (JUMP_P (BB_END (src
))
3877 && label_is_jump_target_p (BB_HEAD (e
->dest
),
3883 fprintf (dump_file
, "Fallthru edge unified with branch "
3884 "%i->%i redirected to %i\n",
3885 e
->src
->index
, e
->dest
->index
, dest
->index
);
3886 e
->flags
&= ~EDGE_FALLTHRU
;
3887 redirected
= redirect_branch_edge (e
, dest
);
3888 gcc_assert (redirected
);
3889 redirected
->flags
|= EDGE_FALLTHRU
;
3890 df_set_bb_dirty (redirected
->src
);
3893 /* In case we are redirecting fallthru edge to the branch edge
3894 of conditional jump, remove it. */
3895 if (EDGE_COUNT (src
->succs
) == 2)
3897 /* Find the edge that is different from E. */
3898 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
3901 && any_condjump_p (BB_END (src
))
3902 && onlyjump_p (BB_END (src
)))
3903 delete_insn (BB_END (src
));
3906 fprintf (dump_file
, "Redirecting fallthru edge %i->%i to %i\n",
3907 e
->src
->index
, e
->dest
->index
, dest
->index
);
3908 ret
= redirect_edge_succ_nodup (e
, dest
);
3911 ret
= redirect_branch_edge (e
, dest
);
3913 /* We don't want simplejumps in the insn stream during cfglayout. */
3914 gcc_assert (!simplejump_p (BB_END (src
)));
3916 df_set_bb_dirty (src
);
3920 /* Simple wrapper as we always can redirect fallthru edges. */
3922 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
3924 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
3926 gcc_assert (redirected
);
3930 /* Same as delete_basic_block but update cfg_layout structures. */
3933 cfg_layout_delete_block (basic_block bb
)
3935 rtx insn
, next
, prev
= PREV_INSN (BB_HEAD (bb
)), *to
, remaints
;
3939 next
= BB_HEAD (bb
);
3941 NEXT_INSN (prev
) = BB_HEADER (bb
);
3943 set_first_insn (BB_HEADER (bb
));
3944 PREV_INSN (BB_HEADER (bb
)) = prev
;
3945 insn
= BB_HEADER (bb
);
3946 while (NEXT_INSN (insn
))
3947 insn
= NEXT_INSN (insn
);
3948 NEXT_INSN (insn
) = next
;
3949 PREV_INSN (next
) = insn
;
3951 next
= NEXT_INSN (BB_END (bb
));
3954 insn
= BB_FOOTER (bb
);
3957 if (BARRIER_P (insn
))
3959 if (PREV_INSN (insn
))
3960 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
3962 BB_FOOTER (bb
) = NEXT_INSN (insn
);
3963 if (NEXT_INSN (insn
))
3964 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
3968 insn
= NEXT_INSN (insn
);
3973 NEXT_INSN (insn
) = BB_FOOTER (bb
);
3974 PREV_INSN (BB_FOOTER (bb
)) = insn
;
3975 while (NEXT_INSN (insn
))
3976 insn
= NEXT_INSN (insn
);
3977 NEXT_INSN (insn
) = next
;
3979 PREV_INSN (next
) = insn
;
3981 set_last_insn (insn
);
3984 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
3985 to
= &BB_HEADER (bb
->next_bb
);
3987 to
= &cfg_layout_function_footer
;
3989 rtl_delete_block (bb
);
3992 prev
= NEXT_INSN (prev
);
3994 prev
= get_insns ();
3996 next
= PREV_INSN (next
);
3998 next
= get_last_insn ();
4000 if (next
&& NEXT_INSN (next
) != prev
)
4002 remaints
= unlink_insn_chain (prev
, next
);
4004 while (NEXT_INSN (insn
))
4005 insn
= NEXT_INSN (insn
);
4006 NEXT_INSN (insn
) = *to
;
4008 PREV_INSN (*to
) = insn
;
4013 /* Return true when blocks A and B can be safely merged. */
4016 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
4018 /* If we are partitioning hot/cold basic blocks, we don't want to
4019 mess up unconditional or indirect jumps that cross between hot
4022 Basic block partitioning may result in some jumps that appear to
4023 be optimizable (or blocks that appear to be mergeable), but which really
4024 must be left untouched (they are required to make it safely across
4025 partition boundaries). See the comments at the top of
4026 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4028 if (BB_PARTITION (a
) != BB_PARTITION (b
))
4031 /* Protect the loop latches. */
4032 if (current_loops
&& b
->loop_father
->latch
== b
)
4035 /* If we would end up moving B's instructions, make sure it doesn't fall
4036 through into the exit block, since we cannot recover from a fallthrough
4037 edge into the exit block occurring in the middle of a function. */
4038 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4040 edge e
= find_fallthru_edge (b
->succs
);
4041 if (e
&& e
->dest
== EXIT_BLOCK_PTR
)
4045 /* There must be exactly one edge in between the blocks. */
4046 return (single_succ_p (a
)
4047 && single_succ (a
) == b
4048 && single_pred_p (b
) == 1
4050 /* Must be simple edge. */
4051 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
4052 && a
!= ENTRY_BLOCK_PTR
&& b
!= EXIT_BLOCK_PTR
4053 /* If the jump insn has side effects, we can't kill the edge.
4054 When not optimizing, try_redirect_by_replacing_jump will
4055 not allow us to redirect an edge by replacing a table jump. */
4056 && (!JUMP_P (BB_END (a
))
4057 || ((!optimize
|| reload_completed
)
4058 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
4061 /* Merge block A and B. The blocks must be mergeable. */
4064 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
4066 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
4069 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a
, b
));
4072 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
4075 /* If there was a CODE_LABEL beginning B, delete it. */
4076 if (LABEL_P (BB_HEAD (b
)))
4078 delete_insn (BB_HEAD (b
));
4081 /* We should have fallthru edge in a, or we can do dummy redirection to get
4083 if (JUMP_P (BB_END (a
)))
4084 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
4085 gcc_assert (!JUMP_P (BB_END (a
)));
4087 /* When not optimizing CFG and the edge is the only place in RTL which holds
4088 some unique locus, emit a nop with that locus in between. */
4090 emit_nop_for_unique_locus_between (a
, b
);
4092 /* Possible line number notes should appear in between. */
4095 rtx first
= BB_END (a
), last
;
4097 last
= emit_insn_after_noloc (BB_HEADER (b
), BB_END (a
), a
);
4098 /* The above might add a BARRIER as BB_END, but as barriers
4099 aren't valid parts of a bb, remove_insn doesn't update
4100 BB_END if it is a barrier. So adjust BB_END here. */
4101 while (BB_END (a
) != first
&& BARRIER_P (BB_END (a
)))
4102 BB_END (a
) = PREV_INSN (BB_END (a
));
4103 delete_insn_chain (NEXT_INSN (first
), last
, false);
4104 BB_HEADER (b
) = NULL
;
4107 /* In the case basic blocks are not adjacent, move them around. */
4108 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4110 insn
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
4112 emit_insn_after_noloc (insn
, BB_END (a
), a
);
4114 /* Otherwise just re-associate the instructions. */
4118 BB_END (a
) = BB_END (b
);
4121 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4122 We need to explicitly call. */
4123 update_bb_for_insn_chain (insn
, BB_END (b
), a
);
4125 /* Skip possible DELETED_LABEL insn. */
4126 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
4127 insn
= NEXT_INSN (insn
);
4128 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4132 df_bb_delete (b
->index
);
4134 /* Possible tablejumps and barriers should appear after the block. */
4138 BB_FOOTER (a
) = BB_FOOTER (b
);
4141 rtx last
= BB_FOOTER (a
);
4143 while (NEXT_INSN (last
))
4144 last
= NEXT_INSN (last
);
4145 NEXT_INSN (last
) = BB_FOOTER (b
);
4146 PREV_INSN (BB_FOOTER (b
)) = last
;
4148 BB_FOOTER (b
) = NULL
;
4151 /* If B was a forwarder block, propagate the locus on the edge. */
4153 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
4154 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
4157 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
4163 cfg_layout_split_edge (edge e
)
4165 basic_block new_bb
=
4166 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR
4167 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
4170 if (e
->dest
== EXIT_BLOCK_PTR
)
4171 BB_COPY_PARTITION (new_bb
, e
->src
);
4173 BB_COPY_PARTITION (new_bb
, e
->dest
);
4174 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
4175 redirect_edge_and_branch_force (e
, new_bb
);
4180 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4183 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
4187 /* Return true if BB contains only labels or non-executable
4191 rtl_block_empty_p (basic_block bb
)
4195 if (bb
== ENTRY_BLOCK_PTR
|| bb
== EXIT_BLOCK_PTR
)
4198 FOR_BB_INSNS (bb
, insn
)
4199 if (NONDEBUG_INSN_P (insn
) && !any_uncondjump_p (insn
))
4205 /* Split a basic block if it ends with a conditional branch and if
4206 the other part of the block is not empty. */
4209 rtl_split_block_before_cond_jump (basic_block bb
)
4212 rtx split_point
= NULL
;
4214 bool found_code
= false;
4216 FOR_BB_INSNS (bb
, insn
)
4218 if (any_condjump_p (insn
))
4220 else if (NONDEBUG_INSN_P (insn
))
4225 /* Did not find everything. */
4226 if (found_code
&& split_point
)
4227 return split_block (bb
, split_point
)->dest
;
4232 /* Return 1 if BB ends with a call, possibly followed by some
4233 instructions that must stay with the call, 0 otherwise. */
4236 rtl_block_ends_with_call_p (basic_block bb
)
4238 rtx insn
= BB_END (bb
);
4240 while (!CALL_P (insn
)
4241 && insn
!= BB_HEAD (bb
)
4242 && (keep_with_call_p (insn
)
4244 || DEBUG_INSN_P (insn
)))
4245 insn
= PREV_INSN (insn
);
4246 return (CALL_P (insn
));
4249 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4252 rtl_block_ends_with_condjump_p (const_basic_block bb
)
4254 return any_condjump_p (BB_END (bb
));
4257 /* Return true if we need to add fake edge to exit.
4258 Helper function for rtl_flow_call_edges_add. */
4261 need_fake_edge_p (const_rtx insn
)
4267 && !SIBLING_CALL_P (insn
)
4268 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
4269 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
4272 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
4273 && MEM_VOLATILE_P (PATTERN (insn
)))
4274 || (GET_CODE (PATTERN (insn
)) == PARALLEL
4275 && asm_noperands (insn
) != -1
4276 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
4277 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
4280 /* Add fake edges to the function exit for any non constant and non noreturn
4281 calls, volatile inline assembly in the bitmap of blocks specified by
4282 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4285 The goal is to expose cases in which entering a basic block does not imply
4286 that all subsequent instructions must be executed. */
4289 rtl_flow_call_edges_add (sbitmap blocks
)
4292 int blocks_split
= 0;
4293 int last_bb
= last_basic_block
;
4294 bool check_last_block
= false;
4296 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
4300 check_last_block
= true;
4302 check_last_block
= bitmap_bit_p (blocks
, EXIT_BLOCK_PTR
->prev_bb
->index
);
4304 /* In the last basic block, before epilogue generation, there will be
4305 a fallthru edge to EXIT. Special care is required if the last insn
4306 of the last basic block is a call because make_edge folds duplicate
4307 edges, which would result in the fallthru edge also being marked
4308 fake, which would result in the fallthru edge being removed by
4309 remove_fake_edges, which would result in an invalid CFG.
4311 Moreover, we can't elide the outgoing fake edge, since the block
4312 profiler needs to take this into account in order to solve the minimal
4313 spanning tree in the case that the call doesn't return.
4315 Handle this by adding a dummy instruction in a new last basic block. */
4316 if (check_last_block
)
4318 basic_block bb
= EXIT_BLOCK_PTR
->prev_bb
;
4319 rtx insn
= BB_END (bb
);
4321 /* Back up past insns that must be kept in the same block as a call. */
4322 while (insn
!= BB_HEAD (bb
)
4323 && keep_with_call_p (insn
))
4324 insn
= PREV_INSN (insn
);
4326 if (need_fake_edge_p (insn
))
4330 e
= find_edge (bb
, EXIT_BLOCK_PTR
);
4333 insert_insn_on_edge (gen_use (const0_rtx
), e
);
4334 commit_edge_insertions ();
4339 /* Now add fake edges to the function exit for any non constant
4340 calls since there is no way that we can determine if they will
4343 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
4345 basic_block bb
= BASIC_BLOCK (i
);
4352 if (blocks
&& !bitmap_bit_p (blocks
, i
))
4355 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
4357 prev_insn
= PREV_INSN (insn
);
4358 if (need_fake_edge_p (insn
))
4361 rtx split_at_insn
= insn
;
4363 /* Don't split the block between a call and an insn that should
4364 remain in the same block as the call. */
4366 while (split_at_insn
!= BB_END (bb
)
4367 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
4368 split_at_insn
= NEXT_INSN (split_at_insn
);
4370 /* The handling above of the final block before the epilogue
4371 should be enough to verify that there is no edge to the exit
4372 block in CFG already. Calling make_edge in such case would
4373 cause us to mark that edge as fake and remove it later. */
4375 #ifdef ENABLE_CHECKING
4376 if (split_at_insn
== BB_END (bb
))
4378 e
= find_edge (bb
, EXIT_BLOCK_PTR
);
4379 gcc_assert (e
== NULL
);
4383 /* Note that the following may create a new basic block
4384 and renumber the existing basic blocks. */
4385 if (split_at_insn
!= BB_END (bb
))
4387 e
= split_block (bb
, split_at_insn
);
4392 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
4395 if (insn
== BB_HEAD (bb
))
4401 verify_flow_info ();
4403 return blocks_split
;
4406 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4407 the conditional branch target, SECOND_HEAD should be the fall-thru
4408 there is no need to handle this here the loop versioning code handles
4409 this. the reason for SECON_HEAD is that it is needed for condition
4410 in trees, and this should be of the same type since it is a hook. */
4412 rtl_lv_add_condition_to_bb (basic_block first_head
,
4413 basic_block second_head ATTRIBUTE_UNUSED
,
4414 basic_block cond_bb
, void *comp_rtx
)
4416 rtx label
, seq
, jump
;
4417 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
4418 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
4419 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
4420 enum machine_mode mode
;
4423 label
= block_label (first_head
);
4424 mode
= GET_MODE (op0
);
4425 if (mode
== VOIDmode
)
4426 mode
= GET_MODE (op1
);
4429 op0
= force_operand (op0
, NULL_RTX
);
4430 op1
= force_operand (op1
, NULL_RTX
);
4431 do_compare_rtx_and_jump (op0
, op1
, comp
, 0,
4432 mode
, NULL_RTX
, NULL_RTX
, label
, -1);
4433 jump
= get_last_insn ();
4434 JUMP_LABEL (jump
) = label
;
4435 LABEL_NUSES (label
)++;
4439 /* Add the new cond , in the new head. */
4440 emit_insn_after(seq
, BB_END(cond_bb
));
4444 /* Given a block B with unconditional branch at its end, get the
4445 store the return the branch edge and the fall-thru edge in
4446 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4448 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
4449 edge
*fallthru_edge
)
4451 edge e
= EDGE_SUCC (b
, 0);
4453 if (e
->flags
& EDGE_FALLTHRU
)
4456 *branch_edge
= EDGE_SUCC (b
, 1);
4461 *fallthru_edge
= EDGE_SUCC (b
, 1);
4466 init_rtl_bb_info (basic_block bb
)
4468 gcc_assert (!bb
->il
.x
.rtl
);
4469 bb
->il
.x
.head_
= NULL
;
4470 bb
->il
.x
.rtl
= ggc_alloc_cleared_rtl_bb_info ();
4473 /* Returns true if it is possible to remove edge E by redirecting
4474 it to the destination of the other edge from E->src. */
4477 rtl_can_remove_branch_p (const_edge e
)
4479 const_basic_block src
= e
->src
;
4480 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
4481 const_rtx insn
= BB_END (src
), set
;
4483 /* The conditions are taken from try_redirect_by_replacing_jump. */
4484 if (target
== EXIT_BLOCK_PTR
)
4487 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4490 if (find_reg_note (insn
, REG_CROSSING_JUMP
, NULL_RTX
)
4491 || BB_PARTITION (src
) != BB_PARTITION (target
))
4494 if (!onlyjump_p (insn
)
4495 || tablejump_p (insn
, NULL
, NULL
))
4498 set
= single_set (insn
);
4499 if (!set
|| side_effects_p (set
))
4506 rtl_duplicate_bb (basic_block bb
)
4508 bb
= cfg_layout_duplicate_bb (bb
);
4513 /* Do book-keeping of basic block BB for the profile consistency checker.
4514 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
4515 then do post-pass accounting. Store the counting in RECORD. */
4517 rtl_account_profile_record (basic_block bb
, int after_pass
,
4518 struct profile_record
*record
)
4521 FOR_BB_INSNS (bb
, insn
)
4524 record
->size
[after_pass
]
4525 += insn_rtx_cost (PATTERN (insn
), false);
4526 if (profile_status
== PROFILE_READ
)
4527 record
->time
[after_pass
]
4528 += insn_rtx_cost (PATTERN (insn
), true) * bb
->count
;
4529 else if (profile_status
== PROFILE_GUESSED
)
4530 record
->time
[after_pass
]
4531 += insn_rtx_cost (PATTERN (insn
), true) * bb
->frequency
;
4535 /* Implementation of CFG manipulation for linearized RTL. */
4536 struct cfg_hooks rtl_cfg_hooks
= {
4538 rtl_verify_flow_info
,
4540 rtl_create_basic_block
,
4541 rtl_redirect_edge_and_branch
,
4542 rtl_redirect_edge_and_branch_force
,
4543 rtl_can_remove_branch_p
,
4546 rtl_move_block_after
,
4547 rtl_can_merge_blocks
, /* can_merge_blocks_p */
4551 cfg_layout_can_duplicate_bb_p
,
4554 rtl_make_forwarder_block
,
4555 rtl_tidy_fallthru_edge
,
4556 rtl_force_nonfallthru
,
4557 rtl_block_ends_with_call_p
,
4558 rtl_block_ends_with_condjump_p
,
4559 rtl_flow_call_edges_add
,
4560 NULL
, /* execute_on_growing_pred */
4561 NULL
, /* execute_on_shrinking_pred */
4562 NULL
, /* duplicate loop for trees */
4563 NULL
, /* lv_add_condition_to_bb */
4564 NULL
, /* lv_adjust_loop_header_phi*/
4565 NULL
, /* extract_cond_bb_edges */
4566 NULL
, /* flush_pending_stmts */
4567 rtl_block_empty_p
, /* block_empty_p */
4568 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
4569 rtl_account_profile_record
,
4572 /* Implementation of CFG manipulation for cfg layout RTL, where
4573 basic block connected via fallthru edges does not have to be adjacent.
4574 This representation will hopefully become the default one in future
4575 version of the compiler. */
4577 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
4579 rtl_verify_flow_info_1
,
4581 cfg_layout_create_basic_block
,
4582 cfg_layout_redirect_edge_and_branch
,
4583 cfg_layout_redirect_edge_and_branch_force
,
4584 rtl_can_remove_branch_p
,
4585 cfg_layout_delete_block
,
4586 cfg_layout_split_block
,
4587 rtl_move_block_after
,
4588 cfg_layout_can_merge_blocks_p
,
4589 cfg_layout_merge_blocks
,
4592 cfg_layout_can_duplicate_bb_p
,
4593 cfg_layout_duplicate_bb
,
4594 cfg_layout_split_edge
,
4595 rtl_make_forwarder_block
,
4596 NULL
, /* tidy_fallthru_edge */
4597 rtl_force_nonfallthru
,
4598 rtl_block_ends_with_call_p
,
4599 rtl_block_ends_with_condjump_p
,
4600 rtl_flow_call_edges_add
,
4601 NULL
, /* execute_on_growing_pred */
4602 NULL
, /* execute_on_shrinking_pred */
4603 duplicate_loop_to_header_edge
, /* duplicate loop for trees */
4604 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
4605 NULL
, /* lv_adjust_loop_header_phi*/
4606 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
4607 NULL
, /* flush_pending_stmts */
4608 rtl_block_empty_p
, /* block_empty_p */
4609 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
4610 rtl_account_profile_record
,
4613 #include "gt-cfgrtl.h"