1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4 2011, 2012 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This file contains low level functions to manipulate the CFG and analyze it
23 that are aware of the RTL intermediate language.
25 Available functionality:
26 - Basic CFG/RTL manipulation API documented in cfghooks.h
27 - CFG-aware instruction chain manipulation
28 delete_insn, delete_insn_chain
29 - Edge splitting and committing to edges
30 insert_insn_on_edge, commit_edge_insertions
31 - CFG updating after insn simplification
32 purge_dead_edges, purge_all_dead_edges
33 - CFG fixing after coarse manipulation
36 Functions not supposed for generic use:
37 - Infrastructure to determine quickly basic block for insn
38 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
39 - Edge redirection with updating and optimizing of insn chain
40 block_label, tidy_fallthru_edge, force_nonfallthru */
44 #include "coretypes.h"
47 #include "hard-reg-set.h"
48 #include "basic-block.h"
53 #include "rtl-error.h"
56 #include "insn-attr.h"
57 #include "insn-config.h"
60 #include "common/common-target.h"
63 #include "tree-pass.h"
66 /* Holds the interesting leading and trailing notes for the function.
67 Only applicable if the CFG is in cfglayout mode. */
68 static GTY(()) rtx cfg_layout_function_footer
;
69 static GTY(()) rtx cfg_layout_function_header
;
71 static rtx
skip_insns_after_block (basic_block
);
72 static void record_effective_endpoints (void);
73 static rtx
label_for_bb (basic_block
);
74 static void fixup_reorder_chain (void);
76 void verify_insn_chain (void);
77 static void fixup_fallthru_exit_predecessor (void);
78 static int can_delete_note_p (const_rtx
);
79 static int can_delete_label_p (const_rtx
);
80 static basic_block
rtl_split_edge (edge
);
81 static bool rtl_move_block_after (basic_block
, basic_block
);
82 static int rtl_verify_flow_info (void);
83 static basic_block
cfg_layout_split_block (basic_block
, void *);
84 static edge
cfg_layout_redirect_edge_and_branch (edge
, basic_block
);
85 static basic_block
cfg_layout_redirect_edge_and_branch_force (edge
, basic_block
);
86 static void cfg_layout_delete_block (basic_block
);
87 static void rtl_delete_block (basic_block
);
88 static basic_block
rtl_redirect_edge_and_branch_force (edge
, basic_block
);
89 static edge
rtl_redirect_edge_and_branch (edge
, basic_block
);
90 static basic_block
rtl_split_block (basic_block
, void *);
91 static void rtl_dump_bb (FILE *, basic_block
, int, int);
92 static int rtl_verify_flow_info_1 (void);
93 static void rtl_make_forwarder_block (edge
);
95 /* Return true if NOTE is not one of the ones that must be kept paired,
96 so that we may simply delete it. */
99 can_delete_note_p (const_rtx note
)
101 switch (NOTE_KIND (note
))
103 case NOTE_INSN_DELETED
:
104 case NOTE_INSN_BASIC_BLOCK
:
105 case NOTE_INSN_EPILOGUE_BEG
:
113 /* True if a given label can be deleted. */
116 can_delete_label_p (const_rtx label
)
118 return (!LABEL_PRESERVE_P (label
)
119 /* User declared labels must be preserved. */
120 && LABEL_NAME (label
) == 0
121 && !in_expr_list_p (forced_labels
, label
));
124 /* Delete INSN by patching it out. */
127 delete_insn (rtx insn
)
130 bool really_delete
= true;
134 /* Some labels can't be directly removed from the INSN chain, as they
135 might be references via variables, constant pool etc.
136 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
137 if (! can_delete_label_p (insn
))
139 const char *name
= LABEL_NAME (insn
);
140 basic_block bb
= BLOCK_FOR_INSN (insn
);
141 rtx bb_note
= NEXT_INSN (insn
);
143 really_delete
= false;
144 PUT_CODE (insn
, NOTE
);
145 NOTE_KIND (insn
) = NOTE_INSN_DELETED_LABEL
;
146 NOTE_DELETED_LABEL_NAME (insn
) = name
;
148 if (bb_note
!= NULL_RTX
&& NOTE_INSN_BASIC_BLOCK_P (bb_note
)
149 && BLOCK_FOR_INSN (bb_note
) == bb
)
151 reorder_insns_nobb (insn
, insn
, bb_note
);
152 BB_HEAD (bb
) = bb_note
;
153 if (BB_END (bb
) == bb_note
)
158 remove_node_from_expr_list (insn
, &nonlocal_goto_handler_labels
);
163 /* If this insn has already been deleted, something is very wrong. */
164 gcc_assert (!INSN_DELETED_P (insn
));
166 INSN_DELETED_P (insn
) = 1;
169 /* If deleting a jump, decrement the use count of the label. Deleting
170 the label itself should happen in the normal course of block merging. */
173 if (JUMP_LABEL (insn
)
174 && LABEL_P (JUMP_LABEL (insn
)))
175 LABEL_NUSES (JUMP_LABEL (insn
))--;
177 /* If there are more targets, remove them too. */
179 = find_reg_note (insn
, REG_LABEL_TARGET
, NULL_RTX
)) != NULL_RTX
180 && LABEL_P (XEXP (note
, 0)))
182 LABEL_NUSES (XEXP (note
, 0))--;
183 remove_note (insn
, note
);
187 /* Also if deleting any insn that references a label as an operand. */
188 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, NULL_RTX
)) != NULL_RTX
189 && LABEL_P (XEXP (note
, 0)))
191 LABEL_NUSES (XEXP (note
, 0))--;
192 remove_note (insn
, note
);
195 if (JUMP_TABLE_DATA_P (insn
))
197 rtx pat
= PATTERN (insn
);
198 int diff_vec_p
= GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
;
199 int len
= XVECLEN (pat
, diff_vec_p
);
202 for (i
= 0; i
< len
; i
++)
204 rtx label
= XEXP (XVECEXP (pat
, diff_vec_p
, i
), 0);
206 /* When deleting code in bulk (e.g. removing many unreachable
207 blocks) we can delete a label that's a target of the vector
208 before deleting the vector itself. */
210 LABEL_NUSES (label
)--;
215 /* Like delete_insn but also purge dead edges from BB. */
218 delete_insn_and_edges (rtx insn
)
223 && BLOCK_FOR_INSN (insn
)
224 && BB_END (BLOCK_FOR_INSN (insn
)) == insn
)
228 purge_dead_edges (BLOCK_FOR_INSN (insn
));
231 /* Unlink a chain of insns between START and FINISH, leaving notes
232 that must be paired. If CLEAR_BB is true, we set bb field for
233 insns that cannot be removed to NULL. */
236 delete_insn_chain (rtx start
, rtx finish
, bool clear_bb
)
240 /* Unchain the insns one by one. It would be quicker to delete all of these
241 with a single unchaining, rather than one at a time, but we need to keep
246 prev
= PREV_INSN (current
);
247 if (NOTE_P (current
) && !can_delete_note_p (current
))
250 delete_insn (current
);
252 if (clear_bb
&& !INSN_DELETED_P (current
))
253 set_block_for_insn (current
, NULL
);
255 if (current
== start
)
261 /* Create a new basic block consisting of the instructions between HEAD and END
262 inclusive. This function is designed to allow fast BB construction - reuses
263 the note and basic block struct in BB_NOTE, if any and do not grow
264 BASIC_BLOCK chain and should be used directly only by CFG construction code.
265 END can be NULL in to create new empty basic block before HEAD. Both END
266 and HEAD can be NULL to create basic block at the end of INSN chain.
267 AFTER is the basic block we should be put after. */
270 create_basic_block_structure (rtx head
, rtx end
, rtx bb_note
, basic_block after
)
275 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
278 /* If we found an existing note, thread it back onto the chain. */
286 after
= PREV_INSN (head
);
290 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
291 reorder_insns_nobb (bb_note
, bb_note
, after
);
295 /* Otherwise we must create a note and a basic block structure. */
299 init_rtl_bb_info (bb
);
302 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
303 else if (LABEL_P (head
) && end
)
305 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
311 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
317 NOTE_BASIC_BLOCK (bb_note
) = bb
;
320 /* Always include the bb note in the block. */
321 if (NEXT_INSN (end
) == bb_note
)
326 bb
->index
= last_basic_block
++;
327 bb
->flags
= BB_NEW
| BB_RTL
;
328 link_block (bb
, after
);
329 SET_BASIC_BLOCK (bb
->index
, bb
);
330 df_bb_refs_record (bb
->index
, false);
331 update_bb_for_insn (bb
);
332 BB_SET_PARTITION (bb
, BB_UNPARTITIONED
);
334 /* Tag the block so that we know it has been used when considering
335 other basic block notes. */
341 /* Create new basic block consisting of instructions in between HEAD and END
342 and place it to the BB chain after block AFTER. END can be NULL to
343 create a new empty basic block before HEAD. Both END and HEAD can be
344 NULL to create basic block at the end of INSN chain. */
347 rtl_create_basic_block (void *headp
, void *endp
, basic_block after
)
349 rtx head
= (rtx
) headp
, end
= (rtx
) endp
;
352 /* Grow the basic block array if needed. */
353 if ((size_t) last_basic_block
>= VEC_length (basic_block
, basic_block_info
))
355 size_t new_size
= last_basic_block
+ (last_basic_block
+ 3) / 4;
356 VEC_safe_grow_cleared (basic_block
, gc
, basic_block_info
, new_size
);
361 bb
= create_basic_block_structure (head
, end
, NULL
, after
);
367 cfg_layout_create_basic_block (void *head
, void *end
, basic_block after
)
369 basic_block newbb
= rtl_create_basic_block (head
, end
, after
);
374 /* Delete the insns in a (non-live) block. We physically delete every
375 non-deleted-note insn, and update the flow graph appropriately.
377 Return nonzero if we deleted an exception handler. */
379 /* ??? Preserving all such notes strikes me as wrong. It would be nice
380 to post-process the stream to remove empty blocks, loops, ranges, etc. */
383 rtl_delete_block (basic_block b
)
387 /* If the head of this block is a CODE_LABEL, then it might be the
388 label for an exception handler which can't be reached. We need
389 to remove the label from the exception_handler_label list. */
392 end
= get_last_bb_insn (b
);
394 /* Selectively delete the entire chain. */
396 delete_insn_chain (insn
, end
, true);
400 fprintf (dump_file
, "deleting block %d\n", b
->index
);
401 df_bb_delete (b
->index
);
404 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
407 compute_bb_for_insn (void)
413 rtx end
= BB_END (bb
);
416 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
418 BLOCK_FOR_INSN (insn
) = bb
;
425 /* Release the basic_block_for_insn array. */
428 free_bb_for_insn (void)
431 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
432 if (!BARRIER_P (insn
))
433 BLOCK_FOR_INSN (insn
) = NULL
;
438 rest_of_pass_free_cfg (void)
441 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
442 valid at that point so it would be too late to call df_analyze. */
443 if (optimize
> 0 && flag_delayed_branch
)
445 df_note_add_problem ();
454 struct rtl_opt_pass pass_free_cfg
=
458 "*free_cfg", /* name */
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. */
893 if (forwarder_p
&& !EDGE_SUCC (b
, 0)->goto_locus
)
894 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
897 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
901 /* Return true when block A and B can be merged. */
904 rtl_can_merge_blocks (basic_block a
, basic_block b
)
906 /* If we are partitioning hot/cold basic blocks, we don't want to
907 mess up unconditional or indirect jumps that cross between hot
910 Basic block partitioning may result in some jumps that appear to
911 be optimizable (or blocks that appear to be mergeable), but which really
912 must be left untouched (they are required to make it safely across
913 partition boundaries). See the comments at the top of
914 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
916 if (BB_PARTITION (a
) != BB_PARTITION (b
))
919 /* Protect the loop latches. */
920 if (current_loops
&& b
->loop_father
->latch
== b
)
923 /* There must be exactly one edge in between the blocks. */
924 return (single_succ_p (a
)
925 && single_succ (a
) == b
928 /* Must be simple edge. */
929 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
931 && a
!= ENTRY_BLOCK_PTR
&& b
!= EXIT_BLOCK_PTR
932 /* If the jump insn has side effects,
933 we can't kill the edge. */
934 && (!JUMP_P (BB_END (a
))
936 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
939 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
943 block_label (basic_block block
)
945 if (block
== EXIT_BLOCK_PTR
)
948 if (!LABEL_P (BB_HEAD (block
)))
950 BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
953 return BB_HEAD (block
);
956 /* Attempt to perform edge redirection by replacing possibly complex jump
957 instruction by unconditional jump or removing jump completely. This can
958 apply only if all edges now point to the same block. The parameters and
959 return values are equivalent to redirect_edge_and_branch. */
962 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
964 basic_block src
= e
->src
;
965 rtx insn
= BB_END (src
), kill_from
;
969 /* If we are partitioning hot/cold basic blocks, we don't want to
970 mess up unconditional or indirect jumps that cross between hot
973 Basic block partitioning may result in some jumps that appear to
974 be optimizable (or blocks that appear to be mergeable), but which really
975 must be left untouched (they are required to make it safely across
976 partition boundaries). See the comments at the top of
977 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
979 if (find_reg_note (insn
, REG_CROSSING_JUMP
, NULL_RTX
)
980 || BB_PARTITION (src
) != BB_PARTITION (target
))
983 /* We can replace or remove a complex jump only when we have exactly
984 two edges. Also, if we have exactly one outgoing edge, we can
986 if (EDGE_COUNT (src
->succs
) >= 3
987 /* Verify that all targets will be TARGET. Specifically, the
988 edge that is not E must also go to TARGET. */
989 || (EDGE_COUNT (src
->succs
) == 2
990 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
993 if (!onlyjump_p (insn
))
995 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
998 /* Avoid removing branch with side effects. */
999 set
= single_set (insn
);
1000 if (!set
|| side_effects_p (set
))
1003 /* In case we zap a conditional jump, we'll need to kill
1004 the cc0 setter too. */
1007 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
))
1008 && only_sets_cc0_p (PREV_INSN (insn
)))
1009 kill_from
= PREV_INSN (insn
);
1012 /* See if we can create the fallthru edge. */
1013 if (in_cfglayout
|| can_fallthru (src
, target
))
1016 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
1019 /* Selectively unlink whole insn chain. */
1022 rtx insn
= BB_FOOTER (src
);
1024 delete_insn_chain (kill_from
, BB_END (src
), false);
1026 /* Remove barriers but keep jumptables. */
1029 if (BARRIER_P (insn
))
1031 if (PREV_INSN (insn
))
1032 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1034 BB_FOOTER (src
) = NEXT_INSN (insn
);
1035 if (NEXT_INSN (insn
))
1036 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1040 insn
= NEXT_INSN (insn
);
1044 delete_insn_chain (kill_from
, PREV_INSN (BB_HEAD (target
)),
1048 /* If this already is simplejump, redirect it. */
1049 else if (simplejump_p (insn
))
1051 if (e
->dest
== target
)
1054 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
1055 INSN_UID (insn
), e
->dest
->index
, target
->index
);
1056 if (!redirect_jump (insn
, block_label (target
), 0))
1058 gcc_assert (target
== EXIT_BLOCK_PTR
);
1063 /* Cannot do anything for target exit block. */
1064 else if (target
== EXIT_BLOCK_PTR
)
1067 /* Or replace possibly complicated jump insn by simple jump insn. */
1070 rtx target_label
= block_label (target
);
1071 rtx barrier
, label
, table
;
1073 emit_jump_insn_after_noloc (gen_jump (target_label
), insn
);
1074 JUMP_LABEL (BB_END (src
)) = target_label
;
1075 LABEL_NUSES (target_label
)++;
1077 fprintf (dump_file
, "Replacing insn %i by jump %i\n",
1078 INSN_UID (insn
), INSN_UID (BB_END (src
)));
1081 delete_insn_chain (kill_from
, insn
, false);
1083 /* Recognize a tablejump that we are converting to a
1084 simple jump and remove its associated CODE_LABEL
1085 and ADDR_VEC or ADDR_DIFF_VEC. */
1086 if (tablejump_p (insn
, &label
, &table
))
1087 delete_insn_chain (label
, table
, false);
1089 barrier
= next_nonnote_insn (BB_END (src
));
1090 if (!barrier
|| !BARRIER_P (barrier
))
1091 emit_barrier_after (BB_END (src
));
1094 if (barrier
!= NEXT_INSN (BB_END (src
)))
1096 /* Move the jump before barrier so that the notes
1097 which originally were or were created before jump table are
1098 inside the basic block. */
1099 rtx new_insn
= BB_END (src
);
1101 update_bb_for_insn_chain (NEXT_INSN (BB_END (src
)),
1102 PREV_INSN (barrier
), src
);
1104 NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
1105 PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
1107 NEXT_INSN (new_insn
) = barrier
;
1108 NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
1110 PREV_INSN (new_insn
) = PREV_INSN (barrier
);
1111 PREV_INSN (barrier
) = new_insn
;
1116 /* Keep only one edge out and set proper flags. */
1117 if (!single_succ_p (src
))
1119 gcc_assert (single_succ_p (src
));
1121 e
= single_succ_edge (src
);
1123 e
->flags
= EDGE_FALLTHRU
;
1127 e
->probability
= REG_BR_PROB_BASE
;
1128 e
->count
= src
->count
;
1130 if (e
->dest
!= target
)
1131 redirect_edge_succ (e
, target
);
1135 /* Subroutine of redirect_branch_edge that tries to patch the jump
1136 instruction INSN so that it reaches block NEW. Do this
1137 only when it originally reached block OLD. Return true if this
1138 worked or the original target wasn't OLD, return false if redirection
1142 patch_jump_insn (rtx insn
, rtx old_label
, basic_block new_bb
)
1145 /* Recognize a tablejump and adjust all matching cases. */
1146 if (tablejump_p (insn
, NULL
, &tmp
))
1150 rtx new_label
= block_label (new_bb
);
1152 if (new_bb
== EXIT_BLOCK_PTR
)
1154 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
1155 vec
= XVEC (PATTERN (tmp
), 0);
1157 vec
= XVEC (PATTERN (tmp
), 1);
1159 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
1160 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
1162 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
1163 --LABEL_NUSES (old_label
);
1164 ++LABEL_NUSES (new_label
);
1167 /* Handle casesi dispatch insns. */
1168 if ((tmp
= single_set (insn
)) != NULL
1169 && SET_DEST (tmp
) == pc_rtx
1170 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
1171 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
1172 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
1174 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
1176 --LABEL_NUSES (old_label
);
1177 ++LABEL_NUSES (new_label
);
1180 else if ((tmp
= extract_asm_operands (PATTERN (insn
))) != NULL
)
1182 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (tmp
);
1183 rtx new_label
, note
;
1185 if (new_bb
== EXIT_BLOCK_PTR
)
1187 new_label
= block_label (new_bb
);
1189 for (i
= 0; i
< n
; ++i
)
1191 rtx old_ref
= ASM_OPERANDS_LABEL (tmp
, i
);
1192 gcc_assert (GET_CODE (old_ref
) == LABEL_REF
);
1193 if (XEXP (old_ref
, 0) == old_label
)
1195 ASM_OPERANDS_LABEL (tmp
, i
)
1196 = gen_rtx_LABEL_REF (Pmode
, new_label
);
1197 --LABEL_NUSES (old_label
);
1198 ++LABEL_NUSES (new_label
);
1202 if (JUMP_LABEL (insn
) == old_label
)
1204 JUMP_LABEL (insn
) = new_label
;
1205 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1207 remove_note (insn
, note
);
1211 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1213 remove_note (insn
, note
);
1214 if (JUMP_LABEL (insn
) != new_label
1215 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1216 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1218 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1220 XEXP (note
, 0) = new_label
;
1224 /* ?? We may play the games with moving the named labels from
1225 one basic block to the other in case only one computed_jump is
1227 if (computed_jump_p (insn
)
1228 /* A return instruction can't be redirected. */
1229 || returnjump_p (insn
))
1232 if (!currently_expanding_to_rtl
|| JUMP_LABEL (insn
) == old_label
)
1234 /* If the insn doesn't go where we think, we're confused. */
1235 gcc_assert (JUMP_LABEL (insn
) == old_label
);
1237 /* If the substitution doesn't succeed, die. This can happen
1238 if the back end emitted unrecognizable instructions or if
1239 target is exit block on some arches. */
1240 if (!redirect_jump (insn
, block_label (new_bb
), 0))
1242 gcc_assert (new_bb
== EXIT_BLOCK_PTR
);
1251 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1254 redirect_branch_edge (edge e
, basic_block target
)
1256 rtx old_label
= BB_HEAD (e
->dest
);
1257 basic_block src
= e
->src
;
1258 rtx insn
= BB_END (src
);
1260 /* We can only redirect non-fallthru edges of jump insn. */
1261 if (e
->flags
& EDGE_FALLTHRU
)
1263 else if (!JUMP_P (insn
) && !currently_expanding_to_rtl
)
1266 if (!currently_expanding_to_rtl
)
1268 if (!patch_jump_insn (insn
, old_label
, target
))
1272 /* When expanding this BB might actually contain multiple
1273 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1274 Redirect all of those that match our label. */
1275 FOR_BB_INSNS (src
, insn
)
1276 if (JUMP_P (insn
) && !patch_jump_insn (insn
, old_label
, target
))
1280 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
1281 e
->src
->index
, e
->dest
->index
, target
->index
);
1283 if (e
->dest
!= target
)
1284 e
= redirect_edge_succ_nodup (e
, target
);
1289 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1290 expense of adding new instructions or reordering basic blocks.
1292 Function can be also called with edge destination equivalent to the TARGET.
1293 Then it should try the simplifications and do nothing if none is possible.
1295 Return edge representing the branch if transformation succeeded. Return NULL
1297 We still return NULL in case E already destinated TARGET and we didn't
1298 managed to simplify instruction stream. */
1301 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
1304 basic_block src
= e
->src
;
1306 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1309 if (e
->dest
== target
)
1312 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
1314 df_set_bb_dirty (src
);
1318 ret
= redirect_branch_edge (e
, target
);
1322 df_set_bb_dirty (src
);
1326 /* Like force_nonfallthru below, but additionally performs redirection
1327 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1328 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1329 simple_return_rtx, indicating which kind of returnjump to create.
1330 It should be NULL otherwise. */
1333 force_nonfallthru_and_redirect (edge e
, basic_block target
, rtx jump_label
)
1335 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
1338 int abnormal_edge_flags
= 0;
1339 bool asm_goto_edge
= false;
1342 /* In the case the last instruction is conditional jump to the next
1343 instruction, first redirect the jump itself and then continue
1344 by creating a basic block afterwards to redirect fallthru edge. */
1345 if (e
->src
!= ENTRY_BLOCK_PTR
&& e
->dest
!= EXIT_BLOCK_PTR
1346 && any_condjump_p (BB_END (e
->src
))
1347 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1350 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1353 redirected
= redirect_jump (BB_END (e
->src
), block_label (target
), 0);
1354 gcc_assert (redirected
);
1356 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1359 int prob
= INTVAL (XEXP (note
, 0));
1361 b
->probability
= prob
;
1362 b
->count
= e
->count
* prob
/ REG_BR_PROB_BASE
;
1363 e
->probability
-= e
->probability
;
1364 e
->count
-= b
->count
;
1365 if (e
->probability
< 0)
1372 if (e
->flags
& EDGE_ABNORMAL
)
1374 /* Irritating special case - fallthru edge to the same block as abnormal
1376 We can't redirect abnormal edge, but we still can split the fallthru
1377 one and create separate abnormal edge to original destination.
1378 This allows bb-reorder to make such edge non-fallthru. */
1379 gcc_assert (e
->dest
== target
);
1380 abnormal_edge_flags
= e
->flags
& ~EDGE_FALLTHRU
;
1381 e
->flags
&= EDGE_FALLTHRU
;
1385 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1386 if (e
->src
== ENTRY_BLOCK_PTR
)
1388 /* We can't redirect the entry block. Create an empty block
1389 at the start of the function which we use to add the new
1395 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
, ENTRY_BLOCK_PTR
);
1397 /* Change the existing edge's source to be the new block, and add
1398 a new edge from the entry block to the new block. */
1400 for (ei
= ei_start (ENTRY_BLOCK_PTR
->succs
); (tmp
= ei_safe_edge (ei
)); )
1404 VEC_unordered_remove (edge
, ENTRY_BLOCK_PTR
->succs
, ei
.index
);
1414 VEC_safe_push (edge
, gc
, bb
->succs
, e
);
1415 make_single_succ_edge (ENTRY_BLOCK_PTR
, bb
, EDGE_FALLTHRU
);
1419 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1420 don't point to the target or fallthru label. */
1421 if (JUMP_P (BB_END (e
->src
))
1422 && target
!= EXIT_BLOCK_PTR
1423 && (e
->flags
& EDGE_FALLTHRU
)
1424 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
1426 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
1427 bool adjust_jump_target
= false;
1429 for (i
= 0; i
< n
; ++i
)
1431 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (e
->dest
))
1433 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))--;
1434 XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) = block_label (target
);
1435 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))++;
1436 adjust_jump_target
= true;
1438 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (target
))
1439 asm_goto_edge
= true;
1441 if (adjust_jump_target
)
1443 rtx insn
= BB_END (e
->src
), note
;
1444 rtx old_label
= BB_HEAD (e
->dest
);
1445 rtx new_label
= BB_HEAD (target
);
1447 if (JUMP_LABEL (insn
) == old_label
)
1449 JUMP_LABEL (insn
) = new_label
;
1450 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1452 remove_note (insn
, note
);
1456 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1458 remove_note (insn
, note
);
1459 if (JUMP_LABEL (insn
) != new_label
1460 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1461 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1463 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1465 XEXP (note
, 0) = new_label
;
1469 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
|| asm_goto_edge
)
1471 gcov_type count
= e
->count
;
1472 int probability
= e
->probability
;
1473 /* Create the new structures. */
1475 /* If the old block ended with a tablejump, skip its table
1476 by searching forward from there. Otherwise start searching
1477 forward from the last instruction of the old block. */
1478 if (!tablejump_p (BB_END (e
->src
), NULL
, ¬e
))
1479 note
= BB_END (e
->src
);
1480 note
= NEXT_INSN (note
);
1482 jump_block
= create_basic_block (note
, NULL
, e
->src
);
1483 jump_block
->count
= count
;
1484 jump_block
->frequency
= EDGE_FREQUENCY (e
);
1486 /* Make sure new block ends up in correct hot/cold section. */
1488 BB_COPY_PARTITION (jump_block
, e
->src
);
1489 if (flag_reorder_blocks_and_partition
1490 && targetm_common
.have_named_sections
1491 && JUMP_P (BB_END (jump_block
))
1492 && !any_condjump_p (BB_END (jump_block
))
1493 && (EDGE_SUCC (jump_block
, 0)->flags
& EDGE_CROSSING
))
1494 add_reg_note (BB_END (jump_block
), REG_CROSSING_JUMP
, NULL_RTX
);
1497 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1498 new_edge
->probability
= probability
;
1499 new_edge
->count
= count
;
1501 /* Redirect old edge. */
1502 redirect_edge_pred (e
, jump_block
);
1503 e
->probability
= REG_BR_PROB_BASE
;
1505 /* If asm goto has any label refs to target's label,
1506 add also edge from asm goto bb to target. */
1509 new_edge
->probability
/= 2;
1510 new_edge
->count
/= 2;
1511 jump_block
->count
/= 2;
1512 jump_block
->frequency
/= 2;
1513 new_edge
= make_edge (new_edge
->src
, target
,
1514 e
->flags
& ~EDGE_FALLTHRU
);
1515 new_edge
->probability
= probability
- probability
/ 2;
1516 new_edge
->count
= count
- count
/ 2;
1519 new_bb
= jump_block
;
1522 jump_block
= e
->src
;
1524 loc
= e
->goto_locus
;
1525 e
->flags
&= ~EDGE_FALLTHRU
;
1526 if (target
== EXIT_BLOCK_PTR
)
1528 if (jump_label
== ret_rtx
)
1531 emit_jump_insn_after_setloc (gen_return (), BB_END (jump_block
), loc
);
1538 gcc_assert (jump_label
== simple_return_rtx
);
1539 #ifdef HAVE_simple_return
1540 emit_jump_insn_after_setloc (gen_simple_return (),
1541 BB_END (jump_block
), loc
);
1546 set_return_jump_label (BB_END (jump_block
));
1550 rtx label
= block_label (target
);
1551 emit_jump_insn_after_setloc (gen_jump (label
), BB_END (jump_block
), loc
);
1552 JUMP_LABEL (BB_END (jump_block
)) = label
;
1553 LABEL_NUSES (label
)++;
1556 emit_barrier_after (BB_END (jump_block
));
1557 redirect_edge_succ_nodup (e
, target
);
1559 if (abnormal_edge_flags
)
1560 make_edge (src
, target
, abnormal_edge_flags
);
1562 df_mark_solutions_dirty ();
1566 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1567 (and possibly create new basic block) to make edge non-fallthru.
1568 Return newly created BB or NULL if none. */
1571 rtl_force_nonfallthru (edge e
)
1573 return force_nonfallthru_and_redirect (e
, e
->dest
, NULL_RTX
);
1576 /* Redirect edge even at the expense of creating new jump insn or
1577 basic block. Return new basic block if created, NULL otherwise.
1578 Conversion must be possible. */
1581 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1583 if (redirect_edge_and_branch (e
, target
)
1584 || e
->dest
== target
)
1587 /* In case the edge redirection failed, try to force it to be non-fallthru
1588 and redirect newly created simplejump. */
1589 df_set_bb_dirty (e
->src
);
1590 return force_nonfallthru_and_redirect (e
, target
, NULL_RTX
);
1593 /* The given edge should potentially be a fallthru edge. If that is in
1594 fact true, delete the jump and barriers that are in the way. */
1597 rtl_tidy_fallthru_edge (edge e
)
1600 basic_block b
= e
->src
, c
= b
->next_bb
;
1602 /* ??? In a late-running flow pass, other folks may have deleted basic
1603 blocks by nopping out blocks, leaving multiple BARRIERs between here
1604 and the target label. They ought to be chastised and fixed.
1606 We can also wind up with a sequence of undeletable labels between
1607 one block and the next.
1609 So search through a sequence of barriers, labels, and notes for
1610 the head of block C and assert that we really do fall through. */
1612 for (q
= NEXT_INSN (BB_END (b
)); q
!= BB_HEAD (c
); q
= NEXT_INSN (q
))
1616 /* Remove what will soon cease being the jump insn from the source block.
1617 If block B consisted only of this single jump, turn it into a deleted
1622 && (any_uncondjump_p (q
)
1623 || single_succ_p (b
)))
1626 /* If this was a conditional jump, we need to also delete
1627 the insn that set cc0. */
1628 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1635 /* Selectively unlink the sequence. */
1636 if (q
!= PREV_INSN (BB_HEAD (c
)))
1637 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1639 e
->flags
|= EDGE_FALLTHRU
;
1642 /* Should move basic block BB after basic block AFTER. NIY. */
1645 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1646 basic_block after ATTRIBUTE_UNUSED
)
1651 /* Split a (typically critical) edge. Return the new block.
1652 The edge must not be abnormal.
1654 ??? The code generally expects to be called on critical edges.
1655 The case of a block ending in an unconditional jump to a
1656 block with multiple predecessors is not handled optimally. */
1659 rtl_split_edge (edge edge_in
)
1664 /* Abnormal edges cannot be split. */
1665 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1667 /* We are going to place the new block in front of edge destination.
1668 Avoid existence of fallthru predecessors. */
1669 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1671 edge e
= find_fallthru_edge (edge_in
->dest
->preds
);
1674 force_nonfallthru (e
);
1677 /* Create the basic block note. */
1678 if (edge_in
->dest
!= EXIT_BLOCK_PTR
)
1679 before
= BB_HEAD (edge_in
->dest
);
1683 /* If this is a fall through edge to the exit block, the blocks might be
1684 not adjacent, and the right place is after the source. */
1685 if ((edge_in
->flags
& EDGE_FALLTHRU
) && edge_in
->dest
== EXIT_BLOCK_PTR
)
1687 before
= NEXT_INSN (BB_END (edge_in
->src
));
1688 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1689 BB_COPY_PARTITION (bb
, edge_in
->src
);
1693 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1694 /* ??? Why not edge_in->dest->prev_bb here? */
1695 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1698 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1700 /* For non-fallthru edges, we must adjust the predecessor's
1701 jump instruction to target our new block. */
1702 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1704 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1705 gcc_assert (redirected
);
1709 if (edge_in
->src
!= ENTRY_BLOCK_PTR
)
1711 /* For asm goto even splitting of fallthru edge might
1712 need insn patching, as other labels might point to the
1714 rtx last
= BB_END (edge_in
->src
);
1717 && edge_in
->dest
!= EXIT_BLOCK_PTR
1718 && extract_asm_operands (PATTERN (last
)) != NULL_RTX
1719 && patch_jump_insn (last
, before
, bb
))
1720 df_set_bb_dirty (edge_in
->src
);
1722 redirect_edge_succ (edge_in
, bb
);
1728 /* Queue instructions for insertion on an edge between two basic blocks.
1729 The new instructions and basic blocks (if any) will not appear in the
1730 CFG until commit_edge_insertions is called. */
1733 insert_insn_on_edge (rtx pattern
, edge e
)
1735 /* We cannot insert instructions on an abnormal critical edge.
1736 It will be easier to find the culprit if we die now. */
1737 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1739 if (e
->insns
.r
== NULL_RTX
)
1742 push_to_sequence (e
->insns
.r
);
1744 emit_insn (pattern
);
1746 e
->insns
.r
= get_insns ();
1750 /* Update the CFG for the instructions queued on edge E. */
1753 commit_one_edge_insertion (edge e
)
1755 rtx before
= NULL_RTX
, after
= NULL_RTX
, insns
, tmp
, last
;
1758 /* Pull the insns off the edge now since the edge might go away. */
1760 e
->insns
.r
= NULL_RTX
;
1762 /* Figure out where to put these insns. If the destination has
1763 one predecessor, insert there. Except for the exit block. */
1764 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR
)
1768 /* Get the location correct wrt a code label, and "nice" wrt
1769 a basic block note, and before everything else. */
1772 tmp
= NEXT_INSN (tmp
);
1773 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1774 tmp
= NEXT_INSN (tmp
);
1775 if (tmp
== BB_HEAD (bb
))
1778 after
= PREV_INSN (tmp
);
1780 after
= get_last_insn ();
1783 /* If the source has one successor and the edge is not abnormal,
1784 insert there. Except for the entry block. */
1785 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1786 && single_succ_p (e
->src
)
1787 && e
->src
!= ENTRY_BLOCK_PTR
)
1791 /* It is possible to have a non-simple jump here. Consider a target
1792 where some forms of unconditional jumps clobber a register. This
1793 happens on the fr30 for example.
1795 We know this block has a single successor, so we can just emit
1796 the queued insns before the jump. */
1797 if (JUMP_P (BB_END (bb
)))
1798 before
= BB_END (bb
);
1801 /* We'd better be fallthru, or we've lost track of what's what. */
1802 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1804 after
= BB_END (bb
);
1808 /* Otherwise we must split the edge. */
1811 bb
= split_edge (e
);
1812 after
= BB_END (bb
);
1814 if (flag_reorder_blocks_and_partition
1815 && targetm_common
.have_named_sections
1816 && e
->src
!= ENTRY_BLOCK_PTR
1817 && BB_PARTITION (e
->src
) == BB_COLD_PARTITION
1818 && !(e
->flags
& EDGE_CROSSING
)
1820 && !any_condjump_p (after
)
1821 && (single_succ_edge (bb
)->flags
& EDGE_CROSSING
))
1822 add_reg_note (after
, REG_CROSSING_JUMP
, NULL_RTX
);
1825 /* Now that we've found the spot, do the insertion. */
1828 emit_insn_before_noloc (insns
, before
, bb
);
1829 last
= prev_nonnote_insn (before
);
1832 last
= emit_insn_after_noloc (insns
, after
, bb
);
1834 if (returnjump_p (last
))
1836 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1837 This is not currently a problem because this only happens
1838 for the (single) epilogue, which already has a fallthru edge
1841 e
= single_succ_edge (bb
);
1842 gcc_assert (e
->dest
== EXIT_BLOCK_PTR
1843 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
1845 e
->flags
&= ~EDGE_FALLTHRU
;
1846 emit_barrier_after (last
);
1849 delete_insn (before
);
1852 gcc_assert (!JUMP_P (last
));
1855 /* Update the CFG for all queued instructions. */
1858 commit_edge_insertions (void)
1862 #ifdef ENABLE_CHECKING
1863 verify_flow_info ();
1866 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
1871 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1873 commit_one_edge_insertion (e
);
1878 /* Print out RTL-specific basic block information (live information
1879 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
1880 documented in dumpfile.h. */
1883 rtl_dump_bb (FILE *outf
, basic_block bb
, int indent
, int flags
)
1889 s_indent
= (char *) alloca ((size_t) indent
+ 1);
1890 memset (s_indent
, ' ', (size_t) indent
);
1891 s_indent
[indent
] = '\0';
1893 if (df
&& (flags
& TDF_DETAILS
))
1895 df_dump_top (bb
, outf
);
1899 if (bb
->index
!= ENTRY_BLOCK
&& bb
->index
!= EXIT_BLOCK
)
1900 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
)); insn
!= last
;
1901 insn
= NEXT_INSN (insn
))
1903 if (flags
& TDF_DETAILS
)
1904 df_dump_insn_top (insn
, outf
);
1905 if (! (flags
& TDF_SLIM
))
1906 print_rtl_single (outf
, insn
);
1908 dump_insn_slim (outf
, insn
);
1909 if (flags
& TDF_DETAILS
)
1910 df_dump_insn_bottom (insn
, outf
);
1913 if (df
&& (flags
& TDF_DETAILS
))
1915 df_dump_bottom (bb
, outf
);
1921 /* Like dump_function_to_file, but for RTL. Print out dataflow information
1922 for the start of each basic block. FLAGS are the TDF_* masks documented
1926 print_rtl_with_bb (FILE *outf
, const_rtx rtx_first
, int flags
)
1930 fprintf (outf
, "(nil)\n");
1933 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
1934 int max_uid
= get_max_uid ();
1935 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
1936 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
1937 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
1940 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
1941 insns, but the CFG is not maintained so the basic block info
1942 is not reliable. Therefore it's omitted from the dumps. */
1943 if (! (cfun
->curr_properties
& PROP_cfg
))
1944 flags
&= ~TDF_BLOCKS
;
1947 df_dump_start (outf
);
1949 if (flags
& TDF_BLOCKS
)
1951 FOR_EACH_BB_REVERSE (bb
)
1955 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
1956 end
[INSN_UID (BB_END (bb
))] = bb
;
1957 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
1959 enum bb_state state
= IN_MULTIPLE_BB
;
1961 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
1963 in_bb_p
[INSN_UID (x
)] = state
;
1965 if (x
== BB_END (bb
))
1971 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
1973 if (flags
& TDF_BLOCKS
)
1975 bb
= start
[INSN_UID (tmp_rtx
)];
1978 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, true, false);
1979 if (df
&& (flags
& TDF_DETAILS
))
1980 df_dump_top (bb
, outf
);
1983 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
1984 && !NOTE_P (tmp_rtx
)
1985 && !BARRIER_P (tmp_rtx
))
1986 fprintf (outf
, ";; Insn is not within a basic block\n");
1987 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
1988 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
1991 if (flags
& TDF_DETAILS
)
1992 df_dump_insn_top (tmp_rtx
, outf
);
1993 if (! (flags
& TDF_SLIM
))
1994 print_rtl_single (outf
, tmp_rtx
);
1996 dump_insn_slim (outf
, tmp_rtx
);
1997 if (flags
& TDF_DETAILS
)
1998 df_dump_insn_bottom (tmp_rtx
, outf
);
2000 if (flags
& TDF_BLOCKS
)
2002 bb
= end
[INSN_UID (tmp_rtx
)];
2005 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, false, true);
2006 if (df
&& (flags
& TDF_DETAILS
))
2007 df_dump_bottom (bb
, outf
);
2018 if (crtl
->epilogue_delay_list
!= 0)
2020 fprintf (outf
, "\n;; Insns in epilogue delay list:\n\n");
2021 for (tmp_rtx
= crtl
->epilogue_delay_list
; tmp_rtx
!= 0;
2022 tmp_rtx
= XEXP (tmp_rtx
, 1))
2023 print_rtl_single (outf
, XEXP (tmp_rtx
, 0));
2027 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2030 update_br_prob_note (basic_block bb
)
2033 if (!JUMP_P (BB_END (bb
)))
2035 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
2036 if (!note
|| INTVAL (XEXP (note
, 0)) == BRANCH_EDGE (bb
)->probability
)
2038 XEXP (note
, 0) = GEN_INT (BRANCH_EDGE (bb
)->probability
);
2041 /* Get the last insn associated with block BB (that includes barriers and
2042 tablejumps after BB). */
2044 get_last_bb_insn (basic_block bb
)
2047 rtx end
= BB_END (bb
);
2049 /* Include any jump table following the basic block. */
2050 if (tablejump_p (end
, NULL
, &tmp
))
2053 /* Include any barriers that may follow the basic block. */
2054 tmp
= next_nonnote_insn_bb (end
);
2055 while (tmp
&& BARRIER_P (tmp
))
2058 tmp
= next_nonnote_insn_bb (end
);
2064 /* Verify the CFG and RTL consistency common for both underlying RTL and
2067 Currently it does following checks:
2069 - overlapping of basic blocks
2070 - insns with wrong BLOCK_FOR_INSN pointers
2071 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2072 - tails of basic blocks (ensure that boundary is necessary)
2073 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2074 and NOTE_INSN_BASIC_BLOCK
2075 - verify that no fall_thru edge crosses hot/cold partition boundaries
2076 - verify that there are no pending RTL branch predictions
2078 In future it can be extended check a lot of other stuff as well
2079 (reachability of basic blocks, life information, etc. etc.). */
2082 rtl_verify_flow_info_1 (void)
2088 /* Check the general integrity of the basic blocks. */
2089 FOR_EACH_BB_REVERSE (bb
)
2093 if (!(bb
->flags
& BB_RTL
))
2095 error ("BB_RTL flag not set for block %d", bb
->index
);
2099 FOR_BB_INSNS (bb
, insn
)
2100 if (BLOCK_FOR_INSN (insn
) != bb
)
2102 error ("insn %d basic block pointer is %d, should be %d",
2104 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
2109 for (insn
= BB_HEADER (bb
); insn
; insn
= NEXT_INSN (insn
))
2110 if (!BARRIER_P (insn
)
2111 && BLOCK_FOR_INSN (insn
) != NULL
)
2113 error ("insn %d in header of bb %d has non-NULL basic block",
2114 INSN_UID (insn
), bb
->index
);
2117 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
2118 if (!BARRIER_P (insn
)
2119 && BLOCK_FOR_INSN (insn
) != NULL
)
2121 error ("insn %d in footer of bb %d has non-NULL basic block",
2122 INSN_UID (insn
), bb
->index
);
2127 /* Now check the basic blocks (boundaries etc.) */
2128 FOR_EACH_BB_REVERSE (bb
)
2130 int n_fallthru
= 0, n_branch
= 0, n_abnormal_call
= 0, n_sibcall
= 0;
2131 int n_eh
= 0, n_abnormal
= 0;
2132 edge e
, fallthru
= NULL
;
2136 if (JUMP_P (BB_END (bb
))
2137 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
2138 && EDGE_COUNT (bb
->succs
) >= 2
2139 && any_condjump_p (BB_END (bb
)))
2141 if (INTVAL (XEXP (note
, 0)) != BRANCH_EDGE (bb
)->probability
2142 && profile_status
!= PROFILE_ABSENT
)
2144 error ("verify_flow_info: REG_BR_PROB does not match cfg %wi %i",
2145 INTVAL (XEXP (note
, 0)), BRANCH_EDGE (bb
)->probability
);
2149 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2153 if (e
->flags
& EDGE_FALLTHRU
)
2154 n_fallthru
++, fallthru
= e
;
2156 is_crossing
= (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
2157 && e
->src
!= ENTRY_BLOCK_PTR
2158 && e
->dest
!= EXIT_BLOCK_PTR
);
2159 if (e
->flags
& EDGE_CROSSING
)
2163 error ("EDGE_CROSSING incorrectly set across same section");
2166 if (e
->flags
& EDGE_FALLTHRU
)
2168 error ("fallthru edge crosses section boundary in bb %i",
2172 if (e
->flags
& EDGE_EH
)
2174 error ("EH edge crosses section boundary in bb %i",
2179 else if (is_crossing
)
2181 error ("EDGE_CROSSING missing across section boundary");
2185 if ((e
->flags
& ~(EDGE_DFS_BACK
2187 | EDGE_IRREDUCIBLE_LOOP
2190 | EDGE_PRESERVE
)) == 0)
2193 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2196 if (e
->flags
& EDGE_SIBCALL
)
2199 if (e
->flags
& EDGE_EH
)
2202 if (e
->flags
& EDGE_ABNORMAL
)
2206 if (n_eh
&& !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
2208 error ("missing REG_EH_REGION note at the end of bb %i", bb
->index
);
2213 error ("too many exception handling edges in bb %i", bb
->index
);
2217 && (!JUMP_P (BB_END (bb
))
2218 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
2219 || any_condjump_p (BB_END (bb
))))))
2221 error ("too many outgoing branch edges from bb %i", bb
->index
);
2224 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
2226 error ("fallthru edge after unconditional jump in bb %i", bb
->index
);
2229 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
2231 error ("wrong number of branch edges after unconditional jump"
2232 " in bb %i", bb
->index
);
2235 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
2236 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
2238 error ("wrong amount of branch edges after conditional jump"
2239 " in bb %i", bb
->index
);
2242 if (n_abnormal_call
&& !CALL_P (BB_END (bb
)))
2244 error ("abnormal call edges for non-call insn in bb %i", bb
->index
);
2247 if (n_sibcall
&& !CALL_P (BB_END (bb
)))
2249 error ("sibcall edges for non-call insn in bb %i", bb
->index
);
2252 if (n_abnormal
> n_eh
2253 && !(CALL_P (BB_END (bb
))
2254 && n_abnormal
== n_abnormal_call
+ n_sibcall
)
2255 && (!JUMP_P (BB_END (bb
))
2256 || any_condjump_p (BB_END (bb
))
2257 || any_uncondjump_p (BB_END (bb
))))
2259 error ("abnormal edges for no purpose in bb %i", bb
->index
);
2263 for (x
= BB_HEAD (bb
); x
!= NEXT_INSN (BB_END (bb
)); x
= NEXT_INSN (x
))
2264 /* We may have a barrier inside a basic block before dead code
2265 elimination. There is no BLOCK_FOR_INSN field in a barrier. */
2266 if (!BARRIER_P (x
) && BLOCK_FOR_INSN (x
) != bb
)
2269 if (! BLOCK_FOR_INSN (x
))
2271 ("insn %d inside basic block %d but block_for_insn is NULL",
2272 INSN_UID (x
), bb
->index
);
2275 ("insn %d inside basic block %d but block_for_insn is %i",
2276 INSN_UID (x
), bb
->index
, BLOCK_FOR_INSN (x
)->index
);
2281 /* OK pointers are correct. Now check the header of basic
2282 block. It ought to contain optional CODE_LABEL followed
2283 by NOTE_BASIC_BLOCK. */
2287 if (BB_END (bb
) == x
)
2289 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2297 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2299 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2304 if (BB_END (bb
) == x
)
2305 /* Do checks for empty blocks here. */
2308 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2310 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2312 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2313 INSN_UID (x
), bb
->index
);
2317 if (x
== BB_END (bb
))
2320 if (control_flow_insn_p (x
))
2322 error ("in basic block %d:", bb
->index
);
2323 fatal_insn ("flow control insn inside a basic block", x
);
2332 /* Verify the CFG and RTL consistency common for both underlying RTL and
2335 Currently it does following checks:
2336 - all checks of rtl_verify_flow_info_1
2337 - test head/end pointers
2338 - check that all insns are in the basic blocks
2339 (except the switch handling code, barriers and notes)
2340 - check that all returns are followed by barriers
2341 - check that all fallthru edge points to the adjacent blocks. */
2344 rtl_verify_flow_info (void)
2347 int err
= rtl_verify_flow_info_1 ();
2349 rtx last_head
= get_last_insn ();
2350 basic_block
*bb_info
;
2352 const rtx rtx_first
= get_insns ();
2353 basic_block last_bb_seen
= ENTRY_BLOCK_PTR
, curr_bb
= NULL
;
2354 const int max_uid
= get_max_uid ();
2356 bb_info
= XCNEWVEC (basic_block
, max_uid
);
2358 FOR_EACH_BB_REVERSE (bb
)
2361 rtx head
= BB_HEAD (bb
);
2362 rtx end
= BB_END (bb
);
2364 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2366 /* Verify the end of the basic block is in the INSN chain. */
2370 /* And that the code outside of basic blocks has NULL bb field. */
2372 && BLOCK_FOR_INSN (x
) != NULL
)
2374 error ("insn %d outside of basic blocks has non-NULL bb field",
2382 error ("end insn %d for block %d not found in the insn stream",
2383 INSN_UID (end
), bb
->index
);
2387 /* Work backwards from the end to the head of the basic block
2388 to verify the head is in the RTL chain. */
2389 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2391 /* While walking over the insn chain, verify insns appear
2392 in only one basic block. */
2393 if (bb_info
[INSN_UID (x
)] != NULL
)
2395 error ("insn %d is in multiple basic blocks (%d and %d)",
2396 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2400 bb_info
[INSN_UID (x
)] = bb
;
2407 error ("head insn %d for block %d not found in the insn stream",
2408 INSN_UID (head
), bb
->index
);
2412 last_head
= PREV_INSN (x
);
2414 e
= find_fallthru_edge (bb
->succs
);
2419 /* Ensure existence of barrier in BB with no fallthru edges. */
2420 for (insn
= NEXT_INSN (BB_END (bb
)); ; insn
= NEXT_INSN (insn
))
2422 if (!insn
|| NOTE_INSN_BASIC_BLOCK_P (insn
))
2424 error ("missing barrier after block %i", bb
->index
);
2428 if (BARRIER_P (insn
))
2432 else if (e
->src
!= ENTRY_BLOCK_PTR
2433 && e
->dest
!= EXIT_BLOCK_PTR
)
2437 if (e
->src
->next_bb
!= e
->dest
)
2440 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2441 e
->src
->index
, e
->dest
->index
);
2445 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
2446 insn
= NEXT_INSN (insn
))
2447 if (BARRIER_P (insn
) || INSN_P (insn
))
2449 error ("verify_flow_info: Incorrect fallthru %i->%i",
2450 e
->src
->index
, e
->dest
->index
);
2451 fatal_insn ("wrong insn in the fallthru edge", insn
);
2457 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2459 /* Check that the code before the first basic block has NULL
2462 && BLOCK_FOR_INSN (x
) != NULL
)
2464 error ("insn %d outside of basic blocks has non-NULL bb field",
2472 last_bb_seen
= ENTRY_BLOCK_PTR
;
2474 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2476 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2478 bb
= NOTE_BASIC_BLOCK (x
);
2481 if (bb
!= last_bb_seen
->next_bb
)
2482 internal_error ("basic blocks not laid down consecutively");
2484 curr_bb
= last_bb_seen
= bb
;
2489 switch (GET_CODE (x
))
2496 /* An addr_vec is placed outside any basic block. */
2498 && JUMP_TABLE_DATA_P (NEXT_INSN (x
)))
2501 /* But in any case, non-deletable labels can appear anywhere. */
2505 fatal_insn ("insn outside basic block", x
);
2510 && returnjump_p (x
) && ! condjump_p (x
)
2511 && ! (next_nonnote_insn (x
) && BARRIER_P (next_nonnote_insn (x
))))
2512 fatal_insn ("return not followed by barrier", x
);
2513 if (curr_bb
&& x
== BB_END (curr_bb
))
2517 if (num_bb_notes
!= n_basic_blocks
- NUM_FIXED_BLOCKS
)
2519 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2520 num_bb_notes
, n_basic_blocks
);
2525 /* Assume that the preceding pass has possibly eliminated jump instructions
2526 or converted the unconditional jumps. Eliminate the edges from CFG.
2527 Return true if any edges are eliminated. */
2530 purge_dead_edges (basic_block bb
)
2533 rtx insn
= BB_END (bb
), note
;
2534 bool purged
= false;
2538 if (DEBUG_INSN_P (insn
) && insn
!= BB_HEAD (bb
))
2540 insn
= PREV_INSN (insn
);
2541 while ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
));
2543 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2544 if (NONJUMP_INSN_P (insn
)
2545 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
2549 if (! may_trap_p (PATTERN (insn
))
2550 || ((eqnote
= find_reg_equal_equiv_note (insn
))
2551 && ! may_trap_p (XEXP (eqnote
, 0))))
2552 remove_note (insn
, note
);
2555 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
2556 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
2558 bool remove
= false;
2560 /* There are three types of edges we need to handle correctly here: EH
2561 edges, abnormal call EH edges, and abnormal call non-EH edges. The
2562 latter can appear when nonlocal gotos are used. */
2563 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2567 else if (can_nonlocal_goto (insn
))
2569 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
2571 else if (flag_tm
&& find_reg_note (insn
, REG_TM
, NULL
))
2576 else if (e
->flags
& EDGE_EH
)
2577 remove
= !can_throw_internal (insn
);
2582 df_set_bb_dirty (bb
);
2595 /* We do care only about conditional jumps and simplejumps. */
2596 if (!any_condjump_p (insn
)
2597 && !returnjump_p (insn
)
2598 && !simplejump_p (insn
))
2601 /* Branch probability/prediction notes are defined only for
2602 condjumps. We've possibly turned condjump into simplejump. */
2603 if (simplejump_p (insn
))
2605 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2607 remove_note (insn
, note
);
2608 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
2609 remove_note (insn
, note
);
2612 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
2614 /* Avoid abnormal flags to leak from computed jumps turned
2615 into simplejumps. */
2617 e
->flags
&= ~EDGE_ABNORMAL
;
2619 /* See if this edge is one we should keep. */
2620 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
2621 /* A conditional jump can fall through into the next
2622 block, so we should keep the edge. */
2627 else if (e
->dest
!= EXIT_BLOCK_PTR
2628 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
2629 /* If the destination block is the target of the jump,
2635 else if (e
->dest
== EXIT_BLOCK_PTR
&& returnjump_p (insn
))
2636 /* If the destination block is the exit block, and this
2637 instruction is a return, then keep the edge. */
2642 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
2643 /* Keep the edges that correspond to exceptions thrown by
2644 this instruction and rematerialize the EDGE_ABNORMAL
2645 flag we just cleared above. */
2647 e
->flags
|= EDGE_ABNORMAL
;
2652 /* We do not need this edge. */
2653 df_set_bb_dirty (bb
);
2658 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
2662 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
2667 /* Redistribute probabilities. */
2668 if (single_succ_p (bb
))
2670 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
2671 single_succ_edge (bb
)->count
= bb
->count
;
2675 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2679 b
= BRANCH_EDGE (bb
);
2680 f
= FALLTHRU_EDGE (bb
);
2681 b
->probability
= INTVAL (XEXP (note
, 0));
2682 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
2683 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
2684 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
2689 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
2691 /* First, there should not be any EH or ABCALL edges resulting
2692 from non-local gotos and the like. If there were, we shouldn't
2693 have created the sibcall in the first place. Second, there
2694 should of course never have been a fallthru edge. */
2695 gcc_assert (single_succ_p (bb
));
2696 gcc_assert (single_succ_edge (bb
)->flags
2697 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
2702 /* If we don't see a jump insn, we don't know exactly why the block would
2703 have been broken at this point. Look for a simple, non-fallthru edge,
2704 as these are only created by conditional branches. If we find such an
2705 edge we know that there used to be a jump here and can then safely
2706 remove all non-fallthru edges. */
2708 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2709 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
2718 /* Remove all but the fake and fallthru edges. The fake edge may be
2719 the only successor for this block in the case of noreturn
2721 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
2723 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
2725 df_set_bb_dirty (bb
);
2733 gcc_assert (single_succ_p (bb
));
2735 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
2736 single_succ_edge (bb
)->count
= bb
->count
;
2739 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
2744 /* Search all basic blocks for potentially dead edges and purge them. Return
2745 true if some edge has been eliminated. */
2748 purge_all_dead_edges (void)
2755 bool purged_here
= purge_dead_edges (bb
);
2757 purged
|= purged_here
;
2763 /* This is used by a few passes that emit some instructions after abnormal
2764 calls, moving the basic block's end, while they in fact do want to emit
2765 them on the fallthru edge. Look for abnormal call edges, find backward
2766 the call in the block and insert the instructions on the edge instead.
2768 Similarly, handle instructions throwing exceptions internally.
2770 Return true when instructions have been found and inserted on edges. */
2773 fixup_abnormal_edges (void)
2775 bool inserted
= false;
2783 /* Look for cases we are interested in - calls or instructions causing
2785 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2786 if ((e
->flags
& EDGE_ABNORMAL_CALL
)
2787 || ((e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
2788 == (EDGE_ABNORMAL
| EDGE_EH
)))
2791 if (e
&& !CALL_P (BB_END (bb
)) && !can_throw_internal (BB_END (bb
)))
2795 /* Get past the new insns generated. Allow notes, as the insns
2796 may be already deleted. */
2798 while ((NONJUMP_INSN_P (insn
) || NOTE_P (insn
))
2799 && !can_throw_internal (insn
)
2800 && insn
!= BB_HEAD (bb
))
2801 insn
= PREV_INSN (insn
);
2803 if (CALL_P (insn
) || can_throw_internal (insn
))
2807 e
= find_fallthru_edge (bb
->succs
);
2809 stop
= NEXT_INSN (BB_END (bb
));
2812 for (insn
= NEXT_INSN (insn
); insn
!= stop
; insn
= next
)
2814 next
= NEXT_INSN (insn
);
2819 /* Sometimes there's still the return value USE.
2820 If it's placed after a trapping call (i.e. that
2821 call is the last insn anyway), we have no fallthru
2822 edge. Simply delete this use and don't try to insert
2823 on the non-existent edge. */
2824 if (GET_CODE (PATTERN (insn
)) != USE
)
2826 /* We're not deleting it, we're moving it. */
2827 INSN_DELETED_P (insn
) = 0;
2828 PREV_INSN (insn
) = NULL_RTX
;
2829 NEXT_INSN (insn
) = NULL_RTX
;
2831 insert_insn_on_edge (insn
, e
);
2835 else if (!BARRIER_P (insn
))
2836 set_block_for_insn (insn
, NULL
);
2840 /* It may be that we don't find any trapping insn. In this
2841 case we discovered quite late that the insn that had been
2842 marked as can_throw_internal in fact couldn't trap at all.
2843 So we should in fact delete the EH edges out of the block. */
2845 purge_dead_edges (bb
);
2852 /* Cut the insns from FIRST to LAST out of the insns stream. */
2855 unlink_insn_chain (rtx first
, rtx last
)
2857 rtx prevfirst
= PREV_INSN (first
);
2858 rtx nextlast
= NEXT_INSN (last
);
2860 PREV_INSN (first
) = NULL
;
2861 NEXT_INSN (last
) = NULL
;
2863 NEXT_INSN (prevfirst
) = nextlast
;
2865 PREV_INSN (nextlast
) = prevfirst
;
2867 set_last_insn (prevfirst
);
2869 set_first_insn (nextlast
);
2873 /* Skip over inter-block insns occurring after BB which are typically
2874 associated with BB (e.g., barriers). If there are any such insns,
2875 we return the last one. Otherwise, we return the end of BB. */
2878 skip_insns_after_block (basic_block bb
)
2880 rtx insn
, last_insn
, next_head
, prev
;
2882 next_head
= NULL_RTX
;
2883 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
2884 next_head
= BB_HEAD (bb
->next_bb
);
2886 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
2888 if (insn
== next_head
)
2891 switch (GET_CODE (insn
))
2898 switch (NOTE_KIND (insn
))
2900 case NOTE_INSN_BLOCK_END
:
2910 if (NEXT_INSN (insn
)
2911 && JUMP_TABLE_DATA_P (NEXT_INSN (insn
)))
2913 insn
= NEXT_INSN (insn
);
2926 /* It is possible to hit contradictory sequence. For instance:
2932 Where barrier belongs to jump_insn, but the note does not. This can be
2933 created by removing the basic block originally following
2934 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
2936 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
2938 prev
= PREV_INSN (insn
);
2940 switch (NOTE_KIND (insn
))
2942 case NOTE_INSN_BLOCK_END
:
2945 case NOTE_INSN_DELETED
:
2946 case NOTE_INSN_DELETED_LABEL
:
2947 case NOTE_INSN_DELETED_DEBUG_LABEL
:
2950 reorder_insns (insn
, insn
, last_insn
);
2957 /* Locate or create a label for a given basic block. */
2960 label_for_bb (basic_block bb
)
2962 rtx label
= BB_HEAD (bb
);
2964 if (!LABEL_P (label
))
2967 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
2969 label
= block_label (bb
);
2975 /* Locate the effective beginning and end of the insn chain for each
2976 block, as defined by skip_insns_after_block above. */
2979 record_effective_endpoints (void)
2985 for (insn
= get_insns ();
2988 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
;
2989 insn
= NEXT_INSN (insn
))
2991 /* No basic blocks at all? */
2994 if (PREV_INSN (insn
))
2995 cfg_layout_function_header
=
2996 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
2998 cfg_layout_function_header
= NULL_RTX
;
3000 next_insn
= get_insns ();
3005 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
3006 BB_HEADER (bb
) = unlink_insn_chain (next_insn
,
3007 PREV_INSN (BB_HEAD (bb
)));
3008 end
= skip_insns_after_block (bb
);
3009 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
3010 BB_FOOTER (bb
) = unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
3011 next_insn
= NEXT_INSN (BB_END (bb
));
3014 cfg_layout_function_footer
= next_insn
;
3015 if (cfg_layout_function_footer
)
3016 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
3020 into_cfg_layout_mode (void)
3022 cfg_layout_initialize (0);
3027 outof_cfg_layout_mode (void)
3032 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
3033 bb
->aux
= bb
->next_bb
;
3035 cfg_layout_finalize ();
3040 struct rtl_opt_pass pass_into_cfg_layout_mode
=
3044 "into_cfglayout", /* name */
3045 OPTGROUP_NONE
, /* optinfo_flags */
3047 into_cfg_layout_mode
, /* execute */
3050 0, /* static_pass_number */
3052 0, /* properties_required */
3053 PROP_cfglayout
, /* properties_provided */
3054 0, /* properties_destroyed */
3055 0, /* todo_flags_start */
3056 0 /* todo_flags_finish */
3060 struct rtl_opt_pass pass_outof_cfg_layout_mode
=
3064 "outof_cfglayout", /* name */
3065 OPTGROUP_NONE
, /* optinfo_flags */
3067 outof_cfg_layout_mode
, /* execute */
3070 0, /* static_pass_number */
3072 0, /* properties_required */
3073 0, /* properties_provided */
3074 PROP_cfglayout
, /* properties_destroyed */
3075 0, /* todo_flags_start */
3076 0 /* todo_flags_finish */
3081 /* Link the basic blocks in the correct order, compacting the basic
3082 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3083 function also clears the basic block header and footer fields.
3085 This function is usually called after a pass (e.g. tracer) finishes
3086 some transformations while in cfglayout mode. The required sequence
3087 of the basic blocks is in a linked list along the bb->aux field.
3088 This functions re-links the basic block prev_bb and next_bb pointers
3089 accordingly, and it compacts and renumbers the blocks.
3091 FIXME: This currently works only for RTL, but the only RTL-specific
3092 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3093 to GIMPLE a long time ago, but it doesn't relink the basic block
3094 chain. It could do that (to give better initial RTL) if this function
3095 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3098 relink_block_chain (bool stay_in_cfglayout_mode
)
3100 basic_block bb
, prev_bb
;
3103 /* Maybe dump the re-ordered sequence. */
3106 fprintf (dump_file
, "Reordered sequence:\n");
3107 for (bb
= ENTRY_BLOCK_PTR
->next_bb
, index
= NUM_FIXED_BLOCKS
;
3109 bb
= (basic_block
) bb
->aux
, index
++)
3111 fprintf (dump_file
, " %i ", index
);
3112 if (get_bb_original (bb
))
3113 fprintf (dump_file
, "duplicate of %i ",
3114 get_bb_original (bb
)->index
);
3115 else if (forwarder_block_p (bb
)
3116 && !LABEL_P (BB_HEAD (bb
)))
3117 fprintf (dump_file
, "compensation ");
3119 fprintf (dump_file
, "bb %i ", bb
->index
);
3120 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
3124 /* Now reorder the blocks. */
3125 prev_bb
= ENTRY_BLOCK_PTR
;
3126 bb
= ENTRY_BLOCK_PTR
->next_bb
;
3127 for (; bb
; prev_bb
= bb
, bb
= (basic_block
) bb
->aux
)
3129 bb
->prev_bb
= prev_bb
;
3130 prev_bb
->next_bb
= bb
;
3132 prev_bb
->next_bb
= EXIT_BLOCK_PTR
;
3133 EXIT_BLOCK_PTR
->prev_bb
= prev_bb
;
3135 /* Then, clean up the aux fields. */
3139 if (!stay_in_cfglayout_mode
)
3140 BB_HEADER (bb
) = BB_FOOTER (bb
) = NULL
;
3143 /* Maybe reset the original copy tables, they are not valid anymore
3144 when we renumber the basic blocks in compact_blocks. If we are
3145 are going out of cfglayout mode, don't re-allocate the tables. */
3146 free_original_copy_tables ();
3147 if (stay_in_cfglayout_mode
)
3148 initialize_original_copy_tables ();
3150 /* Finally, put basic_block_info in the new order. */
3155 /* Given a reorder chain, rearrange the code to match. */
3158 fixup_reorder_chain (void)
3163 if (cfg_layout_function_header
)
3165 set_first_insn (cfg_layout_function_header
);
3166 insn
= cfg_layout_function_header
;
3167 while (NEXT_INSN (insn
))
3168 insn
= NEXT_INSN (insn
);
3171 /* First do the bulk reordering -- rechain the blocks without regard to
3172 the needed changes to jumps and labels. */
3174 for (bb
= ENTRY_BLOCK_PTR
->next_bb
; bb
; bb
= (basic_block
) bb
->aux
)
3179 NEXT_INSN (insn
) = BB_HEADER (bb
);
3181 set_first_insn (BB_HEADER (bb
));
3182 PREV_INSN (BB_HEADER (bb
)) = insn
;
3183 insn
= BB_HEADER (bb
);
3184 while (NEXT_INSN (insn
))
3185 insn
= NEXT_INSN (insn
);
3188 NEXT_INSN (insn
) = BB_HEAD (bb
);
3190 set_first_insn (BB_HEAD (bb
));
3191 PREV_INSN (BB_HEAD (bb
)) = insn
;
3195 NEXT_INSN (insn
) = BB_FOOTER (bb
);
3196 PREV_INSN (BB_FOOTER (bb
)) = insn
;
3197 while (NEXT_INSN (insn
))
3198 insn
= NEXT_INSN (insn
);
3202 NEXT_INSN (insn
) = cfg_layout_function_footer
;
3203 if (cfg_layout_function_footer
)
3204 PREV_INSN (cfg_layout_function_footer
) = insn
;
3206 while (NEXT_INSN (insn
))
3207 insn
= NEXT_INSN (insn
);
3209 set_last_insn (insn
);
3210 #ifdef ENABLE_CHECKING
3211 verify_insn_chain ();
3214 /* Now add jumps and labels as needed to match the blocks new
3217 for (bb
= ENTRY_BLOCK_PTR
->next_bb
; bb
; bb
= (basic_block
) bb
->aux
)
3219 edge e_fall
, e_taken
, e
;
3221 rtx ret_label
= NULL_RTX
;
3222 basic_block nb
, src_bb
;
3225 if (EDGE_COUNT (bb
->succs
) == 0)
3228 /* Find the old fallthru edge, and another non-EH edge for
3230 e_taken
= e_fall
= NULL
;
3232 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3233 if (e
->flags
& EDGE_FALLTHRU
)
3235 else if (! (e
->flags
& EDGE_EH
))
3238 bb_end_insn
= BB_END (bb
);
3239 if (JUMP_P (bb_end_insn
))
3241 ret_label
= JUMP_LABEL (bb_end_insn
);
3242 if (any_condjump_p (bb_end_insn
))
3244 /* This might happen if the conditional jump has side
3245 effects and could therefore not be optimized away.
3246 Make the basic block to end with a barrier in order
3247 to prevent rtl_verify_flow_info from complaining. */
3250 gcc_assert (!onlyjump_p (bb_end_insn
)
3251 || returnjump_p (bb_end_insn
));
3252 BB_FOOTER (bb
) = emit_barrier_after (bb_end_insn
);
3256 /* If the old fallthru is still next, nothing to do. */
3257 if (bb
->aux
== e_fall
->dest
3258 || e_fall
->dest
== EXIT_BLOCK_PTR
)
3261 /* The degenerated case of conditional jump jumping to the next
3262 instruction can happen for jumps with side effects. We need
3263 to construct a forwarder block and this will be done just
3264 fine by force_nonfallthru below. */
3268 /* There is another special case: if *neither* block is next,
3269 such as happens at the very end of a function, then we'll
3270 need to add a new unconditional jump. Choose the taken
3271 edge based on known or assumed probability. */
3272 else if (bb
->aux
!= e_taken
->dest
)
3274 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
3277 && INTVAL (XEXP (note
, 0)) < REG_BR_PROB_BASE
/ 2
3278 && invert_jump (bb_end_insn
,
3279 (e_fall
->dest
== EXIT_BLOCK_PTR
3281 : label_for_bb (e_fall
->dest
)), 0))
3283 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3284 gcc_checking_assert (could_fall_through
3285 (e_taken
->src
, e_taken
->dest
));
3286 e_taken
->flags
|= EDGE_FALLTHRU
;
3287 update_br_prob_note (bb
);
3288 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
3292 /* If the "jumping" edge is a crossing edge, and the fall
3293 through edge is non-crossing, leave things as they are. */
3294 else if ((e_taken
->flags
& EDGE_CROSSING
)
3295 && !(e_fall
->flags
& EDGE_CROSSING
))
3298 /* Otherwise we can try to invert the jump. This will
3299 basically never fail, however, keep up the pretense. */
3300 else if (invert_jump (bb_end_insn
,
3301 (e_fall
->dest
== EXIT_BLOCK_PTR
3303 : label_for_bb (e_fall
->dest
)), 0))
3305 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3306 gcc_checking_assert (could_fall_through
3307 (e_taken
->src
, e_taken
->dest
));
3308 e_taken
->flags
|= EDGE_FALLTHRU
;
3309 update_br_prob_note (bb
);
3310 if (LABEL_NUSES (ret_label
) == 0
3311 && single_pred_p (e_taken
->dest
))
3312 delete_insn (ret_label
);
3316 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
3318 /* If the old fallthru is still next or if
3319 asm goto doesn't have a fallthru (e.g. when followed by
3320 __builtin_unreachable ()), nothing to do. */
3322 || bb
->aux
== e_fall
->dest
3323 || e_fall
->dest
== EXIT_BLOCK_PTR
)
3326 /* Otherwise we'll have to use the fallthru fixup below. */
3330 /* Otherwise we have some return, switch or computed
3331 jump. In the 99% case, there should not have been a
3333 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
3339 /* No fallthru implies a noreturn function with EH edges, or
3340 something similarly bizarre. In any case, we don't need to
3345 /* If the fallthru block is still next, nothing to do. */
3346 if (bb
->aux
== e_fall
->dest
)
3349 /* A fallthru to exit block. */
3350 if (e_fall
->dest
== EXIT_BLOCK_PTR
)
3354 /* We got here if we need to add a new jump insn.
3355 Note force_nonfallthru can delete E_FALL and thus we have to
3356 save E_FALL->src prior to the call to force_nonfallthru. */
3357 src_bb
= e_fall
->src
;
3358 nb
= force_nonfallthru_and_redirect (e_fall
, e_fall
->dest
, ret_label
);
3363 /* Don't process this new block. */
3366 /* Make sure new bb is tagged for correct section (same as
3367 fall-thru source, since you cannot fall-thru across
3368 section boundaries). */
3369 BB_COPY_PARTITION (src_bb
, single_pred (bb
));
3370 if (flag_reorder_blocks_and_partition
3371 && targetm_common
.have_named_sections
3372 && JUMP_P (BB_END (bb
))
3373 && !any_condjump_p (BB_END (bb
))
3374 && (EDGE_SUCC (bb
, 0)->flags
& EDGE_CROSSING
))
3375 add_reg_note (BB_END (bb
), REG_CROSSING_JUMP
, NULL_RTX
);
3379 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3381 /* Annoying special case - jump around dead jumptables left in the code. */
3384 edge e
= find_fallthru_edge (bb
->succs
);
3386 if (e
&& !can_fallthru (e
->src
, e
->dest
))
3387 force_nonfallthru (e
);
3390 /* Ensure goto_locus from edges has some instructions with that locus
3398 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3399 if (LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
3400 && !(e
->flags
& EDGE_ABNORMAL
))
3404 basic_block dest
, nb
;
3407 insn
= BB_END (e
->src
);
3408 end
= PREV_INSN (BB_HEAD (e
->src
));
3410 && (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
3411 insn
= PREV_INSN (insn
);
3413 && INSN_LOCATION (insn
) == e
->goto_locus
)
3415 if (simplejump_p (BB_END (e
->src
))
3416 && !INSN_HAS_LOCATION (BB_END (e
->src
)))
3418 INSN_LOCATION (BB_END (e
->src
)) = e
->goto_locus
;
3422 if (dest
== EXIT_BLOCK_PTR
)
3424 /* Non-fallthru edges to the exit block cannot be split. */
3425 if (!(e
->flags
& EDGE_FALLTHRU
))
3430 insn
= BB_HEAD (dest
);
3431 end
= NEXT_INSN (BB_END (dest
));
3432 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
3433 insn
= NEXT_INSN (insn
);
3434 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
3435 && INSN_LOCATION (insn
) == e
->goto_locus
)
3438 nb
= split_edge (e
);
3439 if (!INSN_P (BB_END (nb
)))
3440 BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
3442 INSN_LOCATION (BB_END (nb
)) = e
->goto_locus
;
3444 /* If there are other incoming edges to the destination block
3445 with the same goto locus, redirect them to the new block as
3446 well, this can prevent other such blocks from being created
3447 in subsequent iterations of the loop. */
3448 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
3449 if (LOCATION_LOCUS (e2
->goto_locus
) != UNKNOWN_LOCATION
3450 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
3451 && e
->goto_locus
== e2
->goto_locus
)
3452 redirect_edge_and_branch (e2
, nb
);
3459 /* Perform sanity checks on the insn chain.
3460 1. Check that next/prev pointers are consistent in both the forward and
3462 2. Count insns in chain, going both directions, and check if equal.
3463 3. Check that get_last_insn () returns the actual end of chain. */
3466 verify_insn_chain (void)
3468 rtx x
, prevx
, nextx
;
3469 int insn_cnt1
, insn_cnt2
;
3471 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
3473 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
3474 gcc_assert (PREV_INSN (x
) == prevx
);
3476 gcc_assert (prevx
== get_last_insn ());
3478 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
3480 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
3481 gcc_assert (NEXT_INSN (x
) == nextx
);
3483 gcc_assert (insn_cnt1
== insn_cnt2
);
3486 /* If we have assembler epilogues, the block falling through to exit must
3487 be the last one in the reordered chain when we reach final. Ensure
3488 that this condition is met. */
3490 fixup_fallthru_exit_predecessor (void)
3493 basic_block bb
= NULL
;
3495 /* This transformation is not valid before reload, because we might
3496 separate a call from the instruction that copies the return
3498 gcc_assert (reload_completed
);
3500 e
= find_fallthru_edge (EXIT_BLOCK_PTR
->preds
);
3506 basic_block c
= ENTRY_BLOCK_PTR
->next_bb
;
3508 /* If the very first block is the one with the fall-through exit
3509 edge, we have to split that block. */
3512 bb
= split_block (bb
, NULL
)->dest
;
3515 BB_FOOTER (bb
) = BB_FOOTER (c
);
3516 BB_FOOTER (c
) = NULL
;
3519 while (c
->aux
!= bb
)
3520 c
= (basic_block
) c
->aux
;
3524 c
= (basic_block
) c
->aux
;
3531 /* In case there are more than one fallthru predecessors of exit, force that
3532 there is only one. */
3535 force_one_exit_fallthru (void)
3537 edge e
, predecessor
= NULL
;
3540 basic_block forwarder
, bb
;
3542 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
3543 if (e
->flags
& EDGE_FALLTHRU
)
3545 if (predecessor
== NULL
)
3557 /* Exit has several fallthru predecessors. Create a forwarder block for
3559 forwarder
= split_edge (predecessor
);
3560 for (ei
= ei_start (EXIT_BLOCK_PTR
->preds
); (e
= ei_safe_edge (ei
)); )
3562 if (e
->src
== forwarder
3563 || !(e
->flags
& EDGE_FALLTHRU
))
3566 redirect_edge_and_branch_force (e
, forwarder
);
3569 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
3573 if (bb
->aux
== NULL
&& bb
!= forwarder
)
3575 bb
->aux
= forwarder
;
3581 /* Return true in case it is possible to duplicate the basic block BB. */
3584 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
3586 /* Do not attempt to duplicate tablejumps, as we need to unshare
3587 the dispatch table. This is difficult to do, as the instructions
3588 computing jump destination may be hoisted outside the basic block. */
3589 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
3592 /* Do not duplicate blocks containing insns that can't be copied. */
3593 if (targetm
.cannot_copy_insn_p
)
3595 rtx insn
= BB_HEAD (bb
);
3598 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
3600 if (insn
== BB_END (bb
))
3602 insn
= NEXT_INSN (insn
);
3610 duplicate_insn_chain (rtx from
, rtx to
)
3612 rtx insn
, last
, copy
;
3614 /* Avoid updating of boundaries of previous basic block. The
3615 note will get removed from insn stream in fixup. */
3616 last
= emit_note (NOTE_INSN_DELETED
);
3618 /* Create copy at the end of INSN chain. The chain will
3619 be reordered later. */
3620 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
3622 switch (GET_CODE (insn
))
3625 /* Don't duplicate label debug insns. */
3626 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
)
3632 /* Avoid copying of dispatch tables. We never duplicate
3633 tablejumps, so this can hit only in case the table got
3634 moved far from original jump. */
3635 if (GET_CODE (PATTERN (insn
)) == ADDR_VEC
3636 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
)
3638 /* Avoid copying following barrier as well if any
3639 (and debug insns in between). */
3642 for (next
= NEXT_INSN (insn
);
3643 next
!= NEXT_INSN (to
);
3644 next
= NEXT_INSN (next
))
3645 if (!DEBUG_INSN_P (next
))
3647 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
3651 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
3652 if (JUMP_P (insn
) && JUMP_LABEL (insn
) != NULL_RTX
3653 && ANY_RETURN_P (JUMP_LABEL (insn
)))
3654 JUMP_LABEL (copy
) = JUMP_LABEL (insn
);
3655 maybe_copy_prologue_epilogue_insn (insn
, copy
);
3666 switch (NOTE_KIND (insn
))
3668 /* In case prologue is empty and function contain label
3669 in first BB, we may want to copy the block. */
3670 case NOTE_INSN_PROLOGUE_END
:
3672 case NOTE_INSN_DELETED
:
3673 case NOTE_INSN_DELETED_LABEL
:
3674 case NOTE_INSN_DELETED_DEBUG_LABEL
:
3675 /* No problem to strip these. */
3676 case NOTE_INSN_FUNCTION_BEG
:
3677 /* There is always just single entry to function. */
3678 case NOTE_INSN_BASIC_BLOCK
:
3681 case NOTE_INSN_EPILOGUE_BEG
:
3682 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
3683 emit_note_copy (insn
);
3687 /* All other notes should have already been eliminated. */
3695 insn
= NEXT_INSN (last
);
3700 /* Create a duplicate of the basic block BB. */
3703 cfg_layout_duplicate_bb (basic_block bb
)
3708 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
3709 new_bb
= create_basic_block (insn
,
3710 insn
? get_last_insn () : NULL
,
3711 EXIT_BLOCK_PTR
->prev_bb
);
3713 BB_COPY_PARTITION (new_bb
, bb
);
3716 insn
= BB_HEADER (bb
);
3717 while (NEXT_INSN (insn
))
3718 insn
= NEXT_INSN (insn
);
3719 insn
= duplicate_insn_chain (BB_HEADER (bb
), insn
);
3721 BB_HEADER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
3726 insn
= BB_FOOTER (bb
);
3727 while (NEXT_INSN (insn
))
3728 insn
= NEXT_INSN (insn
);
3729 insn
= duplicate_insn_chain (BB_FOOTER (bb
), insn
);
3731 BB_FOOTER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
3738 /* Main entry point to this module - initialize the datastructures for
3739 CFG layout changes. It keeps LOOPS up-to-date if not null.
3741 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
3744 cfg_layout_initialize (unsigned int flags
)
3749 initialize_original_copy_tables ();
3751 cfg_layout_rtl_register_cfg_hooks ();
3753 record_effective_endpoints ();
3755 /* Make sure that the targets of non local gotos are marked. */
3756 for (x
= nonlocal_goto_handler_labels
; x
; x
= XEXP (x
, 1))
3758 bb
= BLOCK_FOR_INSN (XEXP (x
, 0));
3759 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
3762 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
3765 /* Splits superblocks. */
3767 break_superblocks (void)
3769 sbitmap superblocks
;
3773 superblocks
= sbitmap_alloc (last_basic_block
);
3774 bitmap_clear (superblocks
);
3777 if (bb
->flags
& BB_SUPERBLOCK
)
3779 bb
->flags
&= ~BB_SUPERBLOCK
;
3780 bitmap_set_bit (superblocks
, bb
->index
);
3786 rebuild_jump_labels (get_insns ());
3787 find_many_sub_basic_blocks (superblocks
);
3793 /* Finalize the changes: reorder insn list according to the sequence specified
3794 by aux pointers, enter compensation code, rebuild scope forest. */
3797 cfg_layout_finalize (void)
3799 #ifdef ENABLE_CHECKING
3800 verify_flow_info ();
3802 force_one_exit_fallthru ();
3803 rtl_register_cfg_hooks ();
3804 if (reload_completed
3805 #ifdef HAVE_epilogue
3809 fixup_fallthru_exit_predecessor ();
3810 fixup_reorder_chain ();
3812 rebuild_jump_labels (get_insns ());
3813 delete_dead_jumptables ();
3815 #ifdef ENABLE_CHECKING
3816 verify_insn_chain ();
3817 verify_flow_info ();
3822 /* Same as split_block but update cfg_layout structures. */
3825 cfg_layout_split_block (basic_block bb
, void *insnp
)
3827 rtx insn
= (rtx
) insnp
;
3828 basic_block new_bb
= rtl_split_block (bb
, insn
);
3830 BB_FOOTER (new_bb
) = BB_FOOTER (bb
);
3831 BB_FOOTER (bb
) = NULL
;
3836 /* Redirect Edge to DEST. */
3838 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
3840 basic_block src
= e
->src
;
3843 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
3846 if (e
->dest
== dest
)
3849 if (e
->src
!= ENTRY_BLOCK_PTR
3850 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
3852 df_set_bb_dirty (src
);
3856 if (e
->src
== ENTRY_BLOCK_PTR
3857 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
3860 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
3861 e
->src
->index
, dest
->index
);
3863 df_set_bb_dirty (e
->src
);
3864 redirect_edge_succ (e
, dest
);
3868 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
3869 in the case the basic block appears to be in sequence. Avoid this
3872 if (e
->flags
& EDGE_FALLTHRU
)
3874 /* Redirect any branch edges unified with the fallthru one. */
3875 if (JUMP_P (BB_END (src
))
3876 && label_is_jump_target_p (BB_HEAD (e
->dest
),
3882 fprintf (dump_file
, "Fallthru edge unified with branch "
3883 "%i->%i redirected to %i\n",
3884 e
->src
->index
, e
->dest
->index
, dest
->index
);
3885 e
->flags
&= ~EDGE_FALLTHRU
;
3886 redirected
= redirect_branch_edge (e
, dest
);
3887 gcc_assert (redirected
);
3888 redirected
->flags
|= EDGE_FALLTHRU
;
3889 df_set_bb_dirty (redirected
->src
);
3892 /* In case we are redirecting fallthru edge to the branch edge
3893 of conditional jump, remove it. */
3894 if (EDGE_COUNT (src
->succs
) == 2)
3896 /* Find the edge that is different from E. */
3897 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
3900 && any_condjump_p (BB_END (src
))
3901 && onlyjump_p (BB_END (src
)))
3902 delete_insn (BB_END (src
));
3905 fprintf (dump_file
, "Redirecting fallthru edge %i->%i to %i\n",
3906 e
->src
->index
, e
->dest
->index
, dest
->index
);
3907 ret
= redirect_edge_succ_nodup (e
, dest
);
3910 ret
= redirect_branch_edge (e
, dest
);
3912 /* We don't want simplejumps in the insn stream during cfglayout. */
3913 gcc_assert (!simplejump_p (BB_END (src
)));
3915 df_set_bb_dirty (src
);
3919 /* Simple wrapper as we always can redirect fallthru edges. */
3921 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
3923 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
3925 gcc_assert (redirected
);
3929 /* Same as delete_basic_block but update cfg_layout structures. */
3932 cfg_layout_delete_block (basic_block bb
)
3934 rtx insn
, next
, prev
= PREV_INSN (BB_HEAD (bb
)), *to
, remaints
;
3938 next
= BB_HEAD (bb
);
3940 NEXT_INSN (prev
) = BB_HEADER (bb
);
3942 set_first_insn (BB_HEADER (bb
));
3943 PREV_INSN (BB_HEADER (bb
)) = prev
;
3944 insn
= BB_HEADER (bb
);
3945 while (NEXT_INSN (insn
))
3946 insn
= NEXT_INSN (insn
);
3947 NEXT_INSN (insn
) = next
;
3948 PREV_INSN (next
) = insn
;
3950 next
= NEXT_INSN (BB_END (bb
));
3953 insn
= BB_FOOTER (bb
);
3956 if (BARRIER_P (insn
))
3958 if (PREV_INSN (insn
))
3959 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
3961 BB_FOOTER (bb
) = NEXT_INSN (insn
);
3962 if (NEXT_INSN (insn
))
3963 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
3967 insn
= NEXT_INSN (insn
);
3972 NEXT_INSN (insn
) = BB_FOOTER (bb
);
3973 PREV_INSN (BB_FOOTER (bb
)) = insn
;
3974 while (NEXT_INSN (insn
))
3975 insn
= NEXT_INSN (insn
);
3976 NEXT_INSN (insn
) = next
;
3978 PREV_INSN (next
) = insn
;
3980 set_last_insn (insn
);
3983 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
3984 to
= &BB_HEADER (bb
->next_bb
);
3986 to
= &cfg_layout_function_footer
;
3988 rtl_delete_block (bb
);
3991 prev
= NEXT_INSN (prev
);
3993 prev
= get_insns ();
3995 next
= PREV_INSN (next
);
3997 next
= get_last_insn ();
3999 if (next
&& NEXT_INSN (next
) != prev
)
4001 remaints
= unlink_insn_chain (prev
, next
);
4003 while (NEXT_INSN (insn
))
4004 insn
= NEXT_INSN (insn
);
4005 NEXT_INSN (insn
) = *to
;
4007 PREV_INSN (*to
) = insn
;
4012 /* Return true when blocks A and B can be safely merged. */
4015 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
4017 /* If we are partitioning hot/cold basic blocks, we don't want to
4018 mess up unconditional or indirect jumps that cross between hot
4021 Basic block partitioning may result in some jumps that appear to
4022 be optimizable (or blocks that appear to be mergeable), but which really
4023 must be left untouched (they are required to make it safely across
4024 partition boundaries). See the comments at the top of
4025 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4027 if (BB_PARTITION (a
) != BB_PARTITION (b
))
4030 /* Protect the loop latches. */
4031 if (current_loops
&& b
->loop_father
->latch
== b
)
4034 /* If we would end up moving B's instructions, make sure it doesn't fall
4035 through into the exit block, since we cannot recover from a fallthrough
4036 edge into the exit block occurring in the middle of a function. */
4037 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4039 edge e
= find_fallthru_edge (b
->succs
);
4040 if (e
&& e
->dest
== EXIT_BLOCK_PTR
)
4044 /* There must be exactly one edge in between the blocks. */
4045 return (single_succ_p (a
)
4046 && single_succ (a
) == b
4047 && single_pred_p (b
) == 1
4049 /* Must be simple edge. */
4050 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
4051 && a
!= ENTRY_BLOCK_PTR
&& b
!= EXIT_BLOCK_PTR
4052 /* If the jump insn has side effects, we can't kill the edge.
4053 When not optimizing, try_redirect_by_replacing_jump will
4054 not allow us to redirect an edge by replacing a table jump. */
4055 && (!JUMP_P (BB_END (a
))
4056 || ((!optimize
|| reload_completed
)
4057 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
4060 /* Merge block A and B. The blocks must be mergeable. */
4063 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
4065 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
4068 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a
, b
));
4071 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
4074 /* If there was a CODE_LABEL beginning B, delete it. */
4075 if (LABEL_P (BB_HEAD (b
)))
4077 delete_insn (BB_HEAD (b
));
4080 /* We should have fallthru edge in a, or we can do dummy redirection to get
4082 if (JUMP_P (BB_END (a
)))
4083 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
4084 gcc_assert (!JUMP_P (BB_END (a
)));
4086 /* When not optimizing CFG and the edge is the only place in RTL which holds
4087 some unique locus, emit a nop with that locus in between. */
4089 emit_nop_for_unique_locus_between (a
, b
);
4091 /* Possible line number notes should appear in between. */
4094 rtx first
= BB_END (a
), last
;
4096 last
= emit_insn_after_noloc (BB_HEADER (b
), BB_END (a
), a
);
4097 /* The above might add a BARRIER as BB_END, but as barriers
4098 aren't valid parts of a bb, remove_insn doesn't update
4099 BB_END if it is a barrier. So adjust BB_END here. */
4100 while (BB_END (a
) != first
&& BARRIER_P (BB_END (a
)))
4101 BB_END (a
) = PREV_INSN (BB_END (a
));
4102 delete_insn_chain (NEXT_INSN (first
), last
, false);
4103 BB_HEADER (b
) = NULL
;
4106 /* In the case basic blocks are not adjacent, move them around. */
4107 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4109 insn
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
4111 emit_insn_after_noloc (insn
, BB_END (a
), a
);
4113 /* Otherwise just re-associate the instructions. */
4117 BB_END (a
) = BB_END (b
);
4120 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4121 We need to explicitly call. */
4122 update_bb_for_insn_chain (insn
, BB_END (b
), a
);
4124 /* Skip possible DELETED_LABEL insn. */
4125 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
4126 insn
= NEXT_INSN (insn
);
4127 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4131 df_bb_delete (b
->index
);
4133 /* Possible tablejumps and barriers should appear after the block. */
4137 BB_FOOTER (a
) = BB_FOOTER (b
);
4140 rtx last
= BB_FOOTER (a
);
4142 while (NEXT_INSN (last
))
4143 last
= NEXT_INSN (last
);
4144 NEXT_INSN (last
) = BB_FOOTER (b
);
4145 PREV_INSN (BB_FOOTER (b
)) = last
;
4147 BB_FOOTER (b
) = NULL
;
4150 /* If B was a forwarder block, propagate the locus on the edge. */
4152 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) != UNKNOWN_LOCATION
)
4153 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
4156 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
4162 cfg_layout_split_edge (edge e
)
4164 basic_block new_bb
=
4165 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR
4166 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
4169 if (e
->dest
== EXIT_BLOCK_PTR
)
4170 BB_COPY_PARTITION (new_bb
, e
->src
);
4172 BB_COPY_PARTITION (new_bb
, e
->dest
);
4173 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
4174 redirect_edge_and_branch_force (e
, new_bb
);
4179 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4182 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
4186 /* Return true if BB contains only labels or non-executable
4190 rtl_block_empty_p (basic_block bb
)
4194 if (bb
== ENTRY_BLOCK_PTR
|| bb
== EXIT_BLOCK_PTR
)
4197 FOR_BB_INSNS (bb
, insn
)
4198 if (NONDEBUG_INSN_P (insn
) && !any_uncondjump_p (insn
))
4204 /* Split a basic block if it ends with a conditional branch and if
4205 the other part of the block is not empty. */
4208 rtl_split_block_before_cond_jump (basic_block bb
)
4211 rtx split_point
= NULL
;
4213 bool found_code
= false;
4215 FOR_BB_INSNS (bb
, insn
)
4217 if (any_condjump_p (insn
))
4219 else if (NONDEBUG_INSN_P (insn
))
4224 /* Did not find everything. */
4225 if (found_code
&& split_point
)
4226 return split_block (bb
, split_point
)->dest
;
4231 /* Return 1 if BB ends with a call, possibly followed by some
4232 instructions that must stay with the call, 0 otherwise. */
4235 rtl_block_ends_with_call_p (basic_block bb
)
4237 rtx insn
= BB_END (bb
);
4239 while (!CALL_P (insn
)
4240 && insn
!= BB_HEAD (bb
)
4241 && (keep_with_call_p (insn
)
4243 || DEBUG_INSN_P (insn
)))
4244 insn
= PREV_INSN (insn
);
4245 return (CALL_P (insn
));
4248 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4251 rtl_block_ends_with_condjump_p (const_basic_block bb
)
4253 return any_condjump_p (BB_END (bb
));
4256 /* Return true if we need to add fake edge to exit.
4257 Helper function for rtl_flow_call_edges_add. */
4260 need_fake_edge_p (const_rtx insn
)
4266 && !SIBLING_CALL_P (insn
)
4267 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
4268 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
4271 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
4272 && MEM_VOLATILE_P (PATTERN (insn
)))
4273 || (GET_CODE (PATTERN (insn
)) == PARALLEL
4274 && asm_noperands (insn
) != -1
4275 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
4276 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
4279 /* Add fake edges to the function exit for any non constant and non noreturn
4280 calls, volatile inline assembly in the bitmap of blocks specified by
4281 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4284 The goal is to expose cases in which entering a basic block does not imply
4285 that all subsequent instructions must be executed. */
4288 rtl_flow_call_edges_add (sbitmap blocks
)
4291 int blocks_split
= 0;
4292 int last_bb
= last_basic_block
;
4293 bool check_last_block
= false;
4295 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
4299 check_last_block
= true;
4301 check_last_block
= bitmap_bit_p (blocks
, EXIT_BLOCK_PTR
->prev_bb
->index
);
4303 /* In the last basic block, before epilogue generation, there will be
4304 a fallthru edge to EXIT. Special care is required if the last insn
4305 of the last basic block is a call because make_edge folds duplicate
4306 edges, which would result in the fallthru edge also being marked
4307 fake, which would result in the fallthru edge being removed by
4308 remove_fake_edges, which would result in an invalid CFG.
4310 Moreover, we can't elide the outgoing fake edge, since the block
4311 profiler needs to take this into account in order to solve the minimal
4312 spanning tree in the case that the call doesn't return.
4314 Handle this by adding a dummy instruction in a new last basic block. */
4315 if (check_last_block
)
4317 basic_block bb
= EXIT_BLOCK_PTR
->prev_bb
;
4318 rtx insn
= BB_END (bb
);
4320 /* Back up past insns that must be kept in the same block as a call. */
4321 while (insn
!= BB_HEAD (bb
)
4322 && keep_with_call_p (insn
))
4323 insn
= PREV_INSN (insn
);
4325 if (need_fake_edge_p (insn
))
4329 e
= find_edge (bb
, EXIT_BLOCK_PTR
);
4332 insert_insn_on_edge (gen_use (const0_rtx
), e
);
4333 commit_edge_insertions ();
4338 /* Now add fake edges to the function exit for any non constant
4339 calls since there is no way that we can determine if they will
4342 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
4344 basic_block bb
= BASIC_BLOCK (i
);
4351 if (blocks
&& !bitmap_bit_p (blocks
, i
))
4354 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
4356 prev_insn
= PREV_INSN (insn
);
4357 if (need_fake_edge_p (insn
))
4360 rtx split_at_insn
= insn
;
4362 /* Don't split the block between a call and an insn that should
4363 remain in the same block as the call. */
4365 while (split_at_insn
!= BB_END (bb
)
4366 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
4367 split_at_insn
= NEXT_INSN (split_at_insn
);
4369 /* The handling above of the final block before the epilogue
4370 should be enough to verify that there is no edge to the exit
4371 block in CFG already. Calling make_edge in such case would
4372 cause us to mark that edge as fake and remove it later. */
4374 #ifdef ENABLE_CHECKING
4375 if (split_at_insn
== BB_END (bb
))
4377 e
= find_edge (bb
, EXIT_BLOCK_PTR
);
4378 gcc_assert (e
== NULL
);
4382 /* Note that the following may create a new basic block
4383 and renumber the existing basic blocks. */
4384 if (split_at_insn
!= BB_END (bb
))
4386 e
= split_block (bb
, split_at_insn
);
4391 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
4394 if (insn
== BB_HEAD (bb
))
4400 verify_flow_info ();
4402 return blocks_split
;
4405 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4406 the conditional branch target, SECOND_HEAD should be the fall-thru
4407 there is no need to handle this here the loop versioning code handles
4408 this. the reason for SECON_HEAD is that it is needed for condition
4409 in trees, and this should be of the same type since it is a hook. */
4411 rtl_lv_add_condition_to_bb (basic_block first_head
,
4412 basic_block second_head ATTRIBUTE_UNUSED
,
4413 basic_block cond_bb
, void *comp_rtx
)
4415 rtx label
, seq
, jump
;
4416 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
4417 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
4418 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
4419 enum machine_mode mode
;
4422 label
= block_label (first_head
);
4423 mode
= GET_MODE (op0
);
4424 if (mode
== VOIDmode
)
4425 mode
= GET_MODE (op1
);
4428 op0
= force_operand (op0
, NULL_RTX
);
4429 op1
= force_operand (op1
, NULL_RTX
);
4430 do_compare_rtx_and_jump (op0
, op1
, comp
, 0,
4431 mode
, NULL_RTX
, NULL_RTX
, label
, -1);
4432 jump
= get_last_insn ();
4433 JUMP_LABEL (jump
) = label
;
4434 LABEL_NUSES (label
)++;
4438 /* Add the new cond , in the new head. */
4439 emit_insn_after(seq
, BB_END(cond_bb
));
4443 /* Given a block B with unconditional branch at its end, get the
4444 store the return the branch edge and the fall-thru edge in
4445 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4447 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
4448 edge
*fallthru_edge
)
4450 edge e
= EDGE_SUCC (b
, 0);
4452 if (e
->flags
& EDGE_FALLTHRU
)
4455 *branch_edge
= EDGE_SUCC (b
, 1);
4460 *fallthru_edge
= EDGE_SUCC (b
, 1);
4465 init_rtl_bb_info (basic_block bb
)
4467 gcc_assert (!bb
->il
.x
.rtl
);
4468 bb
->il
.x
.head_
= NULL
;
4469 bb
->il
.x
.rtl
= ggc_alloc_cleared_rtl_bb_info ();
4472 /* Returns true if it is possible to remove edge E by redirecting
4473 it to the destination of the other edge from E->src. */
4476 rtl_can_remove_branch_p (const_edge e
)
4478 const_basic_block src
= e
->src
;
4479 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
4480 const_rtx insn
= BB_END (src
), set
;
4482 /* The conditions are taken from try_redirect_by_replacing_jump. */
4483 if (target
== EXIT_BLOCK_PTR
)
4486 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4489 if (find_reg_note (insn
, REG_CROSSING_JUMP
, NULL_RTX
)
4490 || BB_PARTITION (src
) != BB_PARTITION (target
))
4493 if (!onlyjump_p (insn
)
4494 || tablejump_p (insn
, NULL
, NULL
))
4497 set
= single_set (insn
);
4498 if (!set
|| side_effects_p (set
))
4505 rtl_duplicate_bb (basic_block bb
)
4507 bb
= cfg_layout_duplicate_bb (bb
);
4512 /* Do book-keeping of basic block BB for the profile consistency checker.
4513 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
4514 then do post-pass accounting. Store the counting in RECORD. */
4516 rtl_account_profile_record (basic_block bb
, int after_pass
,
4517 struct profile_record
*record
)
4520 FOR_BB_INSNS (bb
, insn
)
4523 record
->size
[after_pass
]
4524 += insn_rtx_cost (PATTERN (insn
), false);
4525 if (profile_status
== PROFILE_READ
)
4526 record
->time
[after_pass
]
4527 += insn_rtx_cost (PATTERN (insn
), true) * bb
->count
;
4528 else if (profile_status
== PROFILE_GUESSED
)
4529 record
->time
[after_pass
]
4530 += insn_rtx_cost (PATTERN (insn
), true) * bb
->frequency
;
4534 /* Implementation of CFG manipulation for linearized RTL. */
4535 struct cfg_hooks rtl_cfg_hooks
= {
4537 rtl_verify_flow_info
,
4539 rtl_create_basic_block
,
4540 rtl_redirect_edge_and_branch
,
4541 rtl_redirect_edge_and_branch_force
,
4542 rtl_can_remove_branch_p
,
4545 rtl_move_block_after
,
4546 rtl_can_merge_blocks
, /* can_merge_blocks_p */
4550 cfg_layout_can_duplicate_bb_p
,
4553 rtl_make_forwarder_block
,
4554 rtl_tidy_fallthru_edge
,
4555 rtl_force_nonfallthru
,
4556 rtl_block_ends_with_call_p
,
4557 rtl_block_ends_with_condjump_p
,
4558 rtl_flow_call_edges_add
,
4559 NULL
, /* execute_on_growing_pred */
4560 NULL
, /* execute_on_shrinking_pred */
4561 NULL
, /* duplicate loop for trees */
4562 NULL
, /* lv_add_condition_to_bb */
4563 NULL
, /* lv_adjust_loop_header_phi*/
4564 NULL
, /* extract_cond_bb_edges */
4565 NULL
, /* flush_pending_stmts */
4566 rtl_block_empty_p
, /* block_empty_p */
4567 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
4568 rtl_account_profile_record
,
4571 /* Implementation of CFG manipulation for cfg layout RTL, where
4572 basic block connected via fallthru edges does not have to be adjacent.
4573 This representation will hopefully become the default one in future
4574 version of the compiler. */
4576 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
4578 rtl_verify_flow_info_1
,
4580 cfg_layout_create_basic_block
,
4581 cfg_layout_redirect_edge_and_branch
,
4582 cfg_layout_redirect_edge_and_branch_force
,
4583 rtl_can_remove_branch_p
,
4584 cfg_layout_delete_block
,
4585 cfg_layout_split_block
,
4586 rtl_move_block_after
,
4587 cfg_layout_can_merge_blocks_p
,
4588 cfg_layout_merge_blocks
,
4591 cfg_layout_can_duplicate_bb_p
,
4592 cfg_layout_duplicate_bb
,
4593 cfg_layout_split_edge
,
4594 rtl_make_forwarder_block
,
4595 NULL
, /* tidy_fallthru_edge */
4596 rtl_force_nonfallthru
,
4597 rtl_block_ends_with_call_p
,
4598 rtl_block_ends_with_condjump_p
,
4599 rtl_flow_call_edges_add
,
4600 NULL
, /* execute_on_growing_pred */
4601 NULL
, /* execute_on_shrinking_pred */
4602 duplicate_loop_to_header_edge
, /* duplicate loop for trees */
4603 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
4604 NULL
, /* lv_adjust_loop_header_phi*/
4605 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
4606 NULL
, /* flush_pending_stmts */
4607 rtl_block_empty_p
, /* block_empty_p */
4608 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
4609 rtl_account_profile_record
,
4612 #include "gt-cfgrtl.h"