1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This file contains low level functions to manipulate the CFG and analyze it
21 that are aware of the RTL intermediate language.
23 Available functionality:
24 - Basic CFG/RTL manipulation API documented in cfghooks.h
25 - CFG-aware instruction chain manipulation
26 delete_insn, delete_insn_chain
27 - Edge splitting and committing to edges
28 insert_insn_on_edge, commit_edge_insertions
29 - CFG updating after insn simplification
30 purge_dead_edges, purge_all_dead_edges
31 - CFG fixing after coarse manipulation
34 Functions not supposed for generic use:
35 - Infrastructure to determine quickly basic block for insn
36 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
37 - Edge redirection with updating and optimizing of insn chain
38 block_label, tidy_fallthru_edge, force_nonfallthru */
42 #include "coretypes.h"
45 #include "hard-reg-set.h"
46 #include "basic-block.h"
47 #include "bb-reorder.h"
57 #include "rtl-error.h"
60 #include "insn-attr.h"
61 #include "insn-config.h"
64 #include "common/common-target.h"
67 #include "tree-pass.h"
70 /* Holds the interesting leading and trailing notes for the function.
71 Only applicable if the CFG is in cfglayout mode. */
72 static GTY(()) rtx_insn
*cfg_layout_function_footer
;
73 static GTY(()) rtx_insn
*cfg_layout_function_header
;
75 static rtx_insn
*skip_insns_after_block (basic_block
);
76 static void record_effective_endpoints (void);
77 static rtx
label_for_bb (basic_block
);
78 static void fixup_reorder_chain (void);
80 void verify_insn_chain (void);
81 static void fixup_fallthru_exit_predecessor (void);
82 static int can_delete_note_p (const rtx_note
*);
83 static int can_delete_label_p (const rtx_code_label
*);
84 static basic_block
rtl_split_edge (edge
);
85 static bool rtl_move_block_after (basic_block
, basic_block
);
86 static int rtl_verify_flow_info (void);
87 static basic_block
cfg_layout_split_block (basic_block
, void *);
88 static edge
cfg_layout_redirect_edge_and_branch (edge
, basic_block
);
89 static basic_block
cfg_layout_redirect_edge_and_branch_force (edge
, basic_block
);
90 static void cfg_layout_delete_block (basic_block
);
91 static void rtl_delete_block (basic_block
);
92 static basic_block
rtl_redirect_edge_and_branch_force (edge
, basic_block
);
93 static edge
rtl_redirect_edge_and_branch (edge
, basic_block
);
94 static basic_block
rtl_split_block (basic_block
, void *);
95 static void rtl_dump_bb (FILE *, basic_block
, int, int);
96 static int rtl_verify_flow_info_1 (void);
97 static void rtl_make_forwarder_block (edge
);
99 /* Return true if NOTE is not one of the ones that must be kept paired,
100 so that we may simply delete it. */
103 can_delete_note_p (const rtx_note
*note
)
105 switch (NOTE_KIND (note
))
107 case NOTE_INSN_DELETED
:
108 case NOTE_INSN_BASIC_BLOCK
:
109 case NOTE_INSN_EPILOGUE_BEG
:
117 /* True if a given label can be deleted. */
120 can_delete_label_p (const rtx_code_label
*label
)
122 return (!LABEL_PRESERVE_P (label
)
123 /* User declared labels must be preserved. */
124 && LABEL_NAME (label
) == 0
125 && !in_expr_list_p (forced_labels
, label
));
128 /* Delete INSN by patching it out. */
131 delete_insn (rtx uncast_insn
)
133 rtx_insn
*insn
= as_a
<rtx_insn
*> (uncast_insn
);
135 bool really_delete
= true;
139 /* Some labels can't be directly removed from the INSN chain, as they
140 might be references via variables, constant pool etc.
141 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
142 if (! can_delete_label_p (as_a
<rtx_code_label
*> (insn
)))
144 const char *name
= LABEL_NAME (insn
);
145 basic_block bb
= BLOCK_FOR_INSN (insn
);
146 rtx_insn
*bb_note
= NEXT_INSN (insn
);
148 really_delete
= false;
149 PUT_CODE (insn
, NOTE
);
150 NOTE_KIND (insn
) = NOTE_INSN_DELETED_LABEL
;
151 NOTE_DELETED_LABEL_NAME (insn
) = name
;
153 /* If the note following the label starts a basic block, and the
154 label is a member of the same basic block, interchange the two. */
155 if (bb_note
!= NULL_RTX
156 && NOTE_INSN_BASIC_BLOCK_P (bb_note
)
158 && bb
== BLOCK_FOR_INSN (bb_note
))
160 reorder_insns_nobb (insn
, insn
, bb_note
);
161 BB_HEAD (bb
) = bb_note
;
162 if (BB_END (bb
) == bb_note
)
167 remove_node_from_insn_list (insn
, &nonlocal_goto_handler_labels
);
172 /* If this insn has already been deleted, something is very wrong. */
173 gcc_assert (!insn
->deleted ());
175 df_insn_delete (insn
);
177 insn
->set_deleted ();
180 /* If deleting a jump, decrement the use count of the label. Deleting
181 the label itself should happen in the normal course of block merging. */
184 if (JUMP_LABEL (insn
)
185 && LABEL_P (JUMP_LABEL (insn
)))
186 LABEL_NUSES (JUMP_LABEL (insn
))--;
188 /* If there are more targets, remove them too. */
190 = find_reg_note (insn
, REG_LABEL_TARGET
, NULL_RTX
)) != NULL_RTX
191 && LABEL_P (XEXP (note
, 0)))
193 LABEL_NUSES (XEXP (note
, 0))--;
194 remove_note (insn
, note
);
198 /* Also if deleting any insn that references a label as an operand. */
199 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, NULL_RTX
)) != NULL_RTX
200 && LABEL_P (XEXP (note
, 0)))
202 LABEL_NUSES (XEXP (note
, 0))--;
203 remove_note (insn
, note
);
206 if (rtx_jump_table_data
*table
= dyn_cast
<rtx_jump_table_data
*> (insn
))
208 rtvec vec
= table
->get_labels ();
209 int len
= GET_NUM_ELEM (vec
);
212 for (i
= 0; i
< len
; i
++)
214 rtx label
= XEXP (RTVEC_ELT (vec
, i
), 0);
216 /* When deleting code in bulk (e.g. removing many unreachable
217 blocks) we can delete a label that's a target of the vector
218 before deleting the vector itself. */
220 LABEL_NUSES (label
)--;
225 /* Like delete_insn but also purge dead edges from BB. */
228 delete_insn_and_edges (rtx_insn
*insn
)
233 && BLOCK_FOR_INSN (insn
)
234 && BB_END (BLOCK_FOR_INSN (insn
)) == insn
)
238 purge_dead_edges (BLOCK_FOR_INSN (insn
));
241 /* Unlink a chain of insns between START and FINISH, leaving notes
242 that must be paired. If CLEAR_BB is true, we set bb field for
243 insns that cannot be removed to NULL. */
246 delete_insn_chain (rtx start
, rtx finish
, bool clear_bb
)
248 rtx_insn
*prev
, *current
;
250 /* Unchain the insns one by one. It would be quicker to delete all of these
251 with a single unchaining, rather than one at a time, but we need to keep
253 current
= safe_as_a
<rtx_insn
*> (finish
);
256 prev
= PREV_INSN (current
);
257 if (NOTE_P (current
) && !can_delete_note_p (as_a
<rtx_note
*> (current
)))
260 delete_insn (current
);
262 if (clear_bb
&& !current
->deleted ())
263 set_block_for_insn (current
, NULL
);
265 if (current
== start
)
271 /* Create a new basic block consisting of the instructions between HEAD and END
272 inclusive. This function is designed to allow fast BB construction - reuses
273 the note and basic block struct in BB_NOTE, if any and do not grow
274 BASIC_BLOCK chain and should be used directly only by CFG construction code.
275 END can be NULL in to create new empty basic block before HEAD. Both END
276 and HEAD can be NULL to create basic block at the end of INSN chain.
277 AFTER is the basic block we should be put after. */
280 create_basic_block_structure (rtx_insn
*head
, rtx_insn
*end
, rtx_note
*bb_note
,
286 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
289 /* If we found an existing note, thread it back onto the chain. */
297 after
= PREV_INSN (head
);
301 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
302 reorder_insns_nobb (bb_note
, bb_note
, after
);
306 /* Otherwise we must create a note and a basic block structure. */
310 init_rtl_bb_info (bb
);
313 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
314 else if (LABEL_P (head
) && end
)
316 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
322 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
328 NOTE_BASIC_BLOCK (bb_note
) = bb
;
331 /* Always include the bb note in the block. */
332 if (NEXT_INSN (end
) == bb_note
)
337 bb
->index
= last_basic_block_for_fn (cfun
)++;
338 bb
->flags
= BB_NEW
| BB_RTL
;
339 link_block (bb
, after
);
340 SET_BASIC_BLOCK_FOR_FN (cfun
, bb
->index
, bb
);
341 df_bb_refs_record (bb
->index
, false);
342 update_bb_for_insn (bb
);
343 BB_SET_PARTITION (bb
, BB_UNPARTITIONED
);
345 /* Tag the block so that we know it has been used when considering
346 other basic block notes. */
352 /* Create new basic block consisting of instructions in between HEAD and END
353 and place it to the BB chain after block AFTER. END can be NULL to
354 create a new empty basic block before HEAD. Both END and HEAD can be
355 NULL to create basic block at the end of INSN chain. */
358 rtl_create_basic_block (void *headp
, void *endp
, basic_block after
)
360 rtx_insn
*head
= (rtx_insn
*) headp
;
361 rtx_insn
*end
= (rtx_insn
*) endp
;
364 /* Grow the basic block array if needed. */
365 if ((size_t) last_basic_block_for_fn (cfun
)
366 >= basic_block_info_for_fn (cfun
)->length ())
369 (last_basic_block_for_fn (cfun
)
370 + (last_basic_block_for_fn (cfun
) + 3) / 4);
371 vec_safe_grow_cleared (basic_block_info_for_fn (cfun
), new_size
);
374 n_basic_blocks_for_fn (cfun
)++;
376 bb
= create_basic_block_structure (head
, end
, NULL
, after
);
382 cfg_layout_create_basic_block (void *head
, void *end
, basic_block after
)
384 basic_block newbb
= rtl_create_basic_block (head
, end
, after
);
389 /* Delete the insns in a (non-live) block. We physically delete every
390 non-deleted-note insn, and update the flow graph appropriately.
392 Return nonzero if we deleted an exception handler. */
394 /* ??? Preserving all such notes strikes me as wrong. It would be nice
395 to post-process the stream to remove empty blocks, loops, ranges, etc. */
398 rtl_delete_block (basic_block b
)
400 rtx_insn
*insn
, *end
;
402 /* If the head of this block is a CODE_LABEL, then it might be the
403 label for an exception handler which can't be reached. We need
404 to remove the label from the exception_handler_label list. */
407 end
= get_last_bb_insn (b
);
409 /* Selectively delete the entire chain. */
411 delete_insn_chain (insn
, end
, true);
415 fprintf (dump_file
, "deleting block %d\n", b
->index
);
416 df_bb_delete (b
->index
);
419 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
422 compute_bb_for_insn (void)
426 FOR_EACH_BB_FN (bb
, cfun
)
428 rtx_insn
*end
= BB_END (bb
);
431 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
433 BLOCK_FOR_INSN (insn
) = bb
;
440 /* Release the basic_block_for_insn array. */
443 free_bb_for_insn (void)
446 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
447 if (!BARRIER_P (insn
))
448 BLOCK_FOR_INSN (insn
) = NULL
;
454 const pass_data pass_data_free_cfg
=
457 "*free_cfg", /* name */
458 OPTGROUP_NONE
, /* optinfo_flags */
460 0, /* properties_required */
461 0, /* properties_provided */
462 PROP_cfg
, /* properties_destroyed */
463 0, /* todo_flags_start */
464 0, /* todo_flags_finish */
467 class pass_free_cfg
: public rtl_opt_pass
470 pass_free_cfg (gcc::context
*ctxt
)
471 : rtl_opt_pass (pass_data_free_cfg
, ctxt
)
474 /* opt_pass methods: */
475 virtual unsigned int execute (function
*);
477 }; // class pass_free_cfg
480 pass_free_cfg::execute (function
*)
483 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
484 valid at that point so it would be too late to call df_analyze. */
485 if (optimize
> 0 && flag_delayed_branch
)
487 df_note_add_problem ();
492 if (crtl
->has_bb_partition
)
493 insert_section_boundary_note ();
502 make_pass_free_cfg (gcc::context
*ctxt
)
504 return new pass_free_cfg (ctxt
);
507 /* Return RTX to emit after when we want to emit code on the entry of function. */
509 entry_of_function (void)
511 return (n_basic_blocks_for_fn (cfun
) > NUM_FIXED_BLOCKS
?
512 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
) : get_insns ());
515 /* Emit INSN at the entry point of the function, ensuring that it is only
516 executed once per function. */
518 emit_insn_at_entry (rtx insn
)
520 edge_iterator ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
521 edge e
= ei_safe_edge (ei
);
522 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
524 insert_insn_on_edge (insn
, e
);
525 commit_edge_insertions ();
528 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
529 (or BARRIER if found) and notify df of the bb change.
530 The insn chain range is inclusive
531 (i.e. both BEGIN and END will be updated. */
534 update_bb_for_insn_chain (rtx_insn
*begin
, rtx_insn
*end
, basic_block bb
)
538 end
= NEXT_INSN (end
);
539 for (insn
= begin
; insn
!= end
; insn
= NEXT_INSN (insn
))
540 if (!BARRIER_P (insn
))
541 df_insn_change_bb (insn
, bb
);
544 /* Update BLOCK_FOR_INSN of insns in BB to BB,
545 and notify df of the change. */
548 update_bb_for_insn (basic_block bb
)
550 update_bb_for_insn_chain (BB_HEAD (bb
), BB_END (bb
), bb
);
554 /* Like active_insn_p, except keep the return value clobber around
555 even after reload. */
558 flow_active_insn_p (const rtx_insn
*insn
)
560 if (active_insn_p (insn
))
563 /* A clobber of the function return value exists for buggy
564 programs that fail to return a value. Its effect is to
565 keep the return value from being live across the entire
566 function. If we allow it to be skipped, we introduce the
567 possibility for register lifetime confusion. */
568 if (GET_CODE (PATTERN (insn
)) == CLOBBER
569 && REG_P (XEXP (PATTERN (insn
), 0))
570 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn
), 0)))
576 /* Return true if the block has no effect and only forwards control flow to
577 its single destination. */
580 contains_no_active_insn_p (const_basic_block bb
)
584 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
585 || !single_succ_p (bb
))
588 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
589 if (INSN_P (insn
) && flow_active_insn_p (insn
))
592 return (!INSN_P (insn
)
593 || (JUMP_P (insn
) && simplejump_p (insn
))
594 || !flow_active_insn_p (insn
));
597 /* Likewise, but protect loop latches, headers and preheaders. */
598 /* FIXME: Make this a cfg hook. */
601 forwarder_block_p (const_basic_block bb
)
603 if (!contains_no_active_insn_p (bb
))
606 /* Protect loop latches, headers and preheaders. */
610 if (bb
->loop_father
->header
== bb
)
612 dest
= EDGE_SUCC (bb
, 0)->dest
;
613 if (dest
->loop_father
->header
== dest
)
620 /* Return nonzero if we can reach target from src by falling through. */
621 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
624 can_fallthru (basic_block src
, basic_block target
)
626 rtx_insn
*insn
= BB_END (src
);
631 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
633 if (src
->next_bb
!= target
)
636 /* ??? Later we may add code to move jump tables offline. */
637 if (tablejump_p (insn
, NULL
, NULL
))
640 FOR_EACH_EDGE (e
, ei
, src
->succs
)
641 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
642 && e
->flags
& EDGE_FALLTHRU
)
645 insn2
= BB_HEAD (target
);
646 if (!active_insn_p (insn2
))
647 insn2
= next_active_insn (insn2
);
649 return next_active_insn (insn
) == insn2
;
652 /* Return nonzero if we could reach target from src by falling through,
653 if the target was made adjacent. If we already have a fall-through
654 edge to the exit block, we can't do that. */
656 could_fall_through (basic_block src
, basic_block target
)
661 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
663 FOR_EACH_EDGE (e
, ei
, src
->succs
)
664 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
665 && e
->flags
& EDGE_FALLTHRU
)
670 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
672 bb_note (basic_block bb
)
678 note
= NEXT_INSN (note
);
680 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
681 return as_a
<rtx_note
*> (note
);
684 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
685 note associated with the BLOCK. */
688 first_insn_after_basic_block_note (basic_block block
)
692 /* Get the first instruction in the block. */
693 insn
= BB_HEAD (block
);
695 if (insn
== NULL_RTX
)
698 insn
= NEXT_INSN (insn
);
699 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
701 return NEXT_INSN (insn
);
704 /* Creates a new basic block just after basic block BB by splitting
705 everything after specified instruction INSNP. */
708 rtl_split_block (basic_block bb
, void *insnp
)
711 rtx_insn
*insn
= (rtx_insn
*) insnp
;
717 insn
= first_insn_after_basic_block_note (bb
);
721 rtx_insn
*next
= insn
;
723 insn
= PREV_INSN (insn
);
725 /* If the block contains only debug insns, insn would have
726 been NULL in a non-debug compilation, and then we'd end
727 up emitting a DELETED note. For -fcompare-debug
728 stability, emit the note too. */
729 if (insn
!= BB_END (bb
)
730 && DEBUG_INSN_P (next
)
731 && DEBUG_INSN_P (BB_END (bb
)))
733 while (next
!= BB_END (bb
) && DEBUG_INSN_P (next
))
734 next
= NEXT_INSN (next
);
736 if (next
== BB_END (bb
))
737 emit_note_after (NOTE_INSN_DELETED
, next
);
741 insn
= get_last_insn ();
744 /* We probably should check type of the insn so that we do not create
745 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
747 if (insn
== BB_END (bb
))
748 emit_note_after (NOTE_INSN_DELETED
, insn
);
750 /* Create the new basic block. */
751 new_bb
= create_basic_block (NEXT_INSN (insn
), BB_END (bb
), bb
);
752 BB_COPY_PARTITION (new_bb
, bb
);
755 /* Redirect the outgoing edges. */
756 new_bb
->succs
= bb
->succs
;
758 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
761 /* The new block starts off being dirty. */
762 df_set_bb_dirty (bb
);
766 /* Return true if the single edge between blocks A and B is the only place
767 in RTL which holds some unique locus. */
770 unique_locus_on_edge_between_p (basic_block a
, basic_block b
)
772 const location_t goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
773 rtx_insn
*insn
, *end
;
775 if (LOCATION_LOCUS (goto_locus
) == UNKNOWN_LOCATION
)
778 /* First scan block A backward. */
780 end
= PREV_INSN (BB_HEAD (a
));
781 while (insn
!= end
&& (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
782 insn
= PREV_INSN (insn
);
784 if (insn
!= end
&& INSN_LOCATION (insn
) == goto_locus
)
787 /* Then scan block B forward. */
791 end
= NEXT_INSN (BB_END (b
));
792 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
793 insn
= NEXT_INSN (insn
);
795 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
796 && INSN_LOCATION (insn
) == goto_locus
)
803 /* If the single edge between blocks A and B is the only place in RTL which
804 holds some unique locus, emit a nop with that locus between the blocks. */
807 emit_nop_for_unique_locus_between (basic_block a
, basic_block b
)
809 if (!unique_locus_on_edge_between_p (a
, b
))
812 BB_END (a
) = emit_insn_after_noloc (gen_nop (), BB_END (a
), a
);
813 INSN_LOCATION (BB_END (a
)) = EDGE_SUCC (a
, 0)->goto_locus
;
816 /* Blocks A and B are to be merged into a single block A. The insns
817 are already contiguous. */
820 rtl_merge_blocks (basic_block a
, basic_block b
)
822 rtx_insn
*b_head
= BB_HEAD (b
), *b_end
= BB_END (b
), *a_end
= BB_END (a
);
823 rtx_insn
*del_first
= NULL
, *del_last
= NULL
;
824 rtx_insn
*b_debug_start
= b_end
, *b_debug_end
= b_end
;
825 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
829 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
832 while (DEBUG_INSN_P (b_end
))
833 b_end
= PREV_INSN (b_debug_start
= b_end
);
835 /* If there was a CODE_LABEL beginning B, delete it. */
836 if (LABEL_P (b_head
))
838 /* Detect basic blocks with nothing but a label. This can happen
839 in particular at the end of a function. */
843 del_first
= del_last
= b_head
;
844 b_head
= NEXT_INSN (b_head
);
847 /* Delete the basic block note and handle blocks containing just that
849 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
857 b_head
= NEXT_INSN (b_head
);
860 /* If there was a jump out of A, delete it. */
865 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
867 || NOTE_INSN_BASIC_BLOCK_P (prev
)
868 || prev
== BB_HEAD (a
))
874 /* If this was a conditional jump, we need to also delete
875 the insn that set cc0. */
876 if (only_sets_cc0_p (prev
))
878 rtx_insn
*tmp
= prev
;
880 prev
= prev_nonnote_insn (prev
);
887 a_end
= PREV_INSN (del_first
);
889 else if (BARRIER_P (NEXT_INSN (a_end
)))
890 del_first
= NEXT_INSN (a_end
);
892 /* Delete everything marked above as well as crap that might be
893 hanging out between the two blocks. */
895 BB_HEAD (b
) = b_empty
? NULL
: b_head
;
896 delete_insn_chain (del_first
, del_last
, true);
898 /* When not optimizing and the edge is the only place in RTL which holds
899 some unique locus, emit a nop with that locus in between. */
902 emit_nop_for_unique_locus_between (a
, b
);
906 /* Reassociate the insns of B with A. */
909 update_bb_for_insn_chain (a_end
, b_debug_end
, a
);
911 BB_END (a
) = b_debug_end
;
914 else if (b_end
!= b_debug_end
)
916 /* Move any deleted labels and other notes between the end of A
917 and the debug insns that make up B after the debug insns,
918 bringing the debug insns into A while keeping the notes after
920 if (NEXT_INSN (a_end
) != b_debug_start
)
921 reorder_insns_nobb (NEXT_INSN (a_end
), PREV_INSN (b_debug_start
),
923 update_bb_for_insn_chain (b_debug_start
, b_debug_end
, a
);
924 BB_END (a
) = b_debug_end
;
927 df_bb_delete (b
->index
);
929 /* If B was a forwarder block, propagate the locus on the edge. */
931 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
932 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
935 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
939 /* Return true when block A and B can be merged. */
942 rtl_can_merge_blocks (basic_block a
, basic_block b
)
944 /* If we are partitioning hot/cold basic blocks, we don't want to
945 mess up unconditional or indirect jumps that cross between hot
948 Basic block partitioning may result in some jumps that appear to
949 be optimizable (or blocks that appear to be mergeable), but which really
950 must be left untouched (they are required to make it safely across
951 partition boundaries). See the comments at the top of
952 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
954 if (BB_PARTITION (a
) != BB_PARTITION (b
))
957 /* Protect the loop latches. */
958 if (current_loops
&& b
->loop_father
->latch
== b
)
961 /* There must be exactly one edge in between the blocks. */
962 return (single_succ_p (a
)
963 && single_succ (a
) == b
966 /* Must be simple edge. */
967 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
969 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
970 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
971 /* If the jump insn has side effects,
972 we can't kill the edge. */
973 && (!JUMP_P (BB_END (a
))
975 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
978 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
982 block_label (basic_block block
)
984 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
987 if (!LABEL_P (BB_HEAD (block
)))
989 BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
992 return BB_HEAD (block
);
995 /* Attempt to perform edge redirection by replacing possibly complex jump
996 instruction by unconditional jump or removing jump completely. This can
997 apply only if all edges now point to the same block. The parameters and
998 return values are equivalent to redirect_edge_and_branch. */
1001 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
1003 basic_block src
= e
->src
;
1004 rtx_insn
*insn
= BB_END (src
), *kill_from
;
1008 /* If we are partitioning hot/cold basic blocks, we don't want to
1009 mess up unconditional or indirect jumps that cross between hot
1012 Basic block partitioning may result in some jumps that appear to
1013 be optimizable (or blocks that appear to be mergeable), but which really
1014 must be left untouched (they are required to make it safely across
1015 partition boundaries). See the comments at the top of
1016 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1018 if (BB_PARTITION (src
) != BB_PARTITION (target
))
1021 /* We can replace or remove a complex jump only when we have exactly
1022 two edges. Also, if we have exactly one outgoing edge, we can
1024 if (EDGE_COUNT (src
->succs
) >= 3
1025 /* Verify that all targets will be TARGET. Specifically, the
1026 edge that is not E must also go to TARGET. */
1027 || (EDGE_COUNT (src
->succs
) == 2
1028 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
1031 if (!onlyjump_p (insn
))
1033 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
1036 /* Avoid removing branch with side effects. */
1037 set
= single_set (insn
);
1038 if (!set
|| side_effects_p (set
))
1041 /* In case we zap a conditional jump, we'll need to kill
1042 the cc0 setter too. */
1045 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
))
1046 && only_sets_cc0_p (PREV_INSN (insn
)))
1047 kill_from
= PREV_INSN (insn
);
1050 /* See if we can create the fallthru edge. */
1051 if (in_cfglayout
|| can_fallthru (src
, target
))
1054 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
1057 /* Selectively unlink whole insn chain. */
1060 rtx_insn
*insn
= BB_FOOTER (src
);
1062 delete_insn_chain (kill_from
, BB_END (src
), false);
1064 /* Remove barriers but keep jumptables. */
1067 if (BARRIER_P (insn
))
1069 if (PREV_INSN (insn
))
1070 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1072 BB_FOOTER (src
) = NEXT_INSN (insn
);
1073 if (NEXT_INSN (insn
))
1074 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1078 insn
= NEXT_INSN (insn
);
1082 delete_insn_chain (kill_from
, PREV_INSN (BB_HEAD (target
)),
1086 /* If this already is simplejump, redirect it. */
1087 else if (simplejump_p (insn
))
1089 if (e
->dest
== target
)
1092 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
1093 INSN_UID (insn
), e
->dest
->index
, target
->index
);
1094 if (!redirect_jump (insn
, block_label (target
), 0))
1096 gcc_assert (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1101 /* Cannot do anything for target exit block. */
1102 else if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1105 /* Or replace possibly complicated jump insn by simple jump insn. */
1108 rtx target_label
= block_label (target
);
1111 rtx_jump_table_data
*table
;
1113 emit_jump_insn_after_noloc (gen_jump (target_label
), insn
);
1114 JUMP_LABEL (BB_END (src
)) = target_label
;
1115 LABEL_NUSES (target_label
)++;
1117 fprintf (dump_file
, "Replacing insn %i by jump %i\n",
1118 INSN_UID (insn
), INSN_UID (BB_END (src
)));
1121 delete_insn_chain (kill_from
, insn
, false);
1123 /* Recognize a tablejump that we are converting to a
1124 simple jump and remove its associated CODE_LABEL
1125 and ADDR_VEC or ADDR_DIFF_VEC. */
1126 if (tablejump_p (insn
, &label
, &table
))
1127 delete_insn_chain (label
, table
, false);
1129 barrier
= next_nonnote_insn (BB_END (src
));
1130 if (!barrier
|| !BARRIER_P (barrier
))
1131 emit_barrier_after (BB_END (src
));
1134 if (barrier
!= NEXT_INSN (BB_END (src
)))
1136 /* Move the jump before barrier so that the notes
1137 which originally were or were created before jump table are
1138 inside the basic block. */
1139 rtx_insn
*new_insn
= BB_END (src
);
1141 update_bb_for_insn_chain (NEXT_INSN (BB_END (src
)),
1142 PREV_INSN (barrier
), src
);
1144 SET_NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
1145 SET_PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
1147 SET_NEXT_INSN (new_insn
) = barrier
;
1148 SET_NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
1150 SET_PREV_INSN (new_insn
) = PREV_INSN (barrier
);
1151 SET_PREV_INSN (barrier
) = new_insn
;
1156 /* Keep only one edge out and set proper flags. */
1157 if (!single_succ_p (src
))
1159 gcc_assert (single_succ_p (src
));
1161 e
= single_succ_edge (src
);
1163 e
->flags
= EDGE_FALLTHRU
;
1167 e
->probability
= REG_BR_PROB_BASE
;
1168 e
->count
= src
->count
;
1170 if (e
->dest
!= target
)
1171 redirect_edge_succ (e
, target
);
1175 /* Subroutine of redirect_branch_edge that tries to patch the jump
1176 instruction INSN so that it reaches block NEW. Do this
1177 only when it originally reached block OLD. Return true if this
1178 worked or the original target wasn't OLD, return false if redirection
1182 patch_jump_insn (rtx_insn
*insn
, rtx_insn
*old_label
, basic_block new_bb
)
1184 rtx_jump_table_data
*table
;
1186 /* Recognize a tablejump and adjust all matching cases. */
1187 if (tablejump_p (insn
, NULL
, &table
))
1191 rtx new_label
= block_label (new_bb
);
1193 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1195 vec
= table
->get_labels ();
1197 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
1198 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
1200 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
1201 --LABEL_NUSES (old_label
);
1202 ++LABEL_NUSES (new_label
);
1205 /* Handle casesi dispatch insns. */
1206 if ((tmp
= single_set (insn
)) != NULL
1207 && SET_DEST (tmp
) == pc_rtx
1208 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
1209 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
1210 && LABEL_REF_LABEL (XEXP (SET_SRC (tmp
), 2)) == old_label
)
1212 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
1214 --LABEL_NUSES (old_label
);
1215 ++LABEL_NUSES (new_label
);
1218 else if ((tmp
= extract_asm_operands (PATTERN (insn
))) != NULL
)
1220 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (tmp
);
1221 rtx new_label
, note
;
1223 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1225 new_label
= block_label (new_bb
);
1227 for (i
= 0; i
< n
; ++i
)
1229 rtx old_ref
= ASM_OPERANDS_LABEL (tmp
, i
);
1230 gcc_assert (GET_CODE (old_ref
) == LABEL_REF
);
1231 if (XEXP (old_ref
, 0) == old_label
)
1233 ASM_OPERANDS_LABEL (tmp
, i
)
1234 = gen_rtx_LABEL_REF (Pmode
, new_label
);
1235 --LABEL_NUSES (old_label
);
1236 ++LABEL_NUSES (new_label
);
1240 if (JUMP_LABEL (insn
) == old_label
)
1242 JUMP_LABEL (insn
) = new_label
;
1243 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1245 remove_note (insn
, note
);
1249 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1251 remove_note (insn
, note
);
1252 if (JUMP_LABEL (insn
) != new_label
1253 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1254 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1256 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1258 XEXP (note
, 0) = new_label
;
1262 /* ?? We may play the games with moving the named labels from
1263 one basic block to the other in case only one computed_jump is
1265 if (computed_jump_p (insn
)
1266 /* A return instruction can't be redirected. */
1267 || returnjump_p (insn
))
1270 if (!currently_expanding_to_rtl
|| JUMP_LABEL (insn
) == old_label
)
1272 /* If the insn doesn't go where we think, we're confused. */
1273 gcc_assert (JUMP_LABEL (insn
) == old_label
);
1275 /* If the substitution doesn't succeed, die. This can happen
1276 if the back end emitted unrecognizable instructions or if
1277 target is exit block on some arches. */
1278 if (!redirect_jump (insn
, block_label (new_bb
), 0))
1280 gcc_assert (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1289 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1292 redirect_branch_edge (edge e
, basic_block target
)
1294 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1295 basic_block src
= e
->src
;
1296 rtx_insn
*insn
= BB_END (src
);
1298 /* We can only redirect non-fallthru edges of jump insn. */
1299 if (e
->flags
& EDGE_FALLTHRU
)
1301 else if (!JUMP_P (insn
) && !currently_expanding_to_rtl
)
1304 if (!currently_expanding_to_rtl
)
1306 if (!patch_jump_insn (insn
, old_label
, target
))
1310 /* When expanding this BB might actually contain multiple
1311 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1312 Redirect all of those that match our label. */
1313 FOR_BB_INSNS (src
, insn
)
1314 if (JUMP_P (insn
) && !patch_jump_insn (insn
, old_label
, target
))
1318 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
1319 e
->src
->index
, e
->dest
->index
, target
->index
);
1321 if (e
->dest
!= target
)
1322 e
= redirect_edge_succ_nodup (e
, target
);
1327 /* Called when edge E has been redirected to a new destination,
1328 in order to update the region crossing flag on the edge and
1332 fixup_partition_crossing (edge e
)
1334 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || e
->dest
1335 == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1337 /* If we redirected an existing edge, it may already be marked
1338 crossing, even though the new src is missing a reg crossing note.
1339 But make sure reg crossing note doesn't already exist before
1341 if (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1343 e
->flags
|= EDGE_CROSSING
;
1344 if (JUMP_P (BB_END (e
->src
))
1345 && !CROSSING_JUMP_P (BB_END (e
->src
)))
1346 CROSSING_JUMP_P (BB_END (e
->src
)) = 1;
1348 else if (BB_PARTITION (e
->src
) == BB_PARTITION (e
->dest
))
1350 e
->flags
&= ~EDGE_CROSSING
;
1351 /* Remove the section crossing note from jump at end of
1352 src if it exists, and if no other successors are
1354 if (JUMP_P (BB_END (e
->src
)) && CROSSING_JUMP_P (BB_END (e
->src
)))
1356 bool has_crossing_succ
= false;
1359 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
1361 has_crossing_succ
|= (e2
->flags
& EDGE_CROSSING
);
1362 if (has_crossing_succ
)
1365 if (!has_crossing_succ
)
1366 CROSSING_JUMP_P (BB_END (e
->src
)) = 0;
1371 /* Called when block BB has been reassigned to the cold partition,
1372 because it is now dominated by another cold block,
1373 to ensure that the region crossing attributes are updated. */
1376 fixup_new_cold_bb (basic_block bb
)
1381 /* This is called when a hot bb is found to now be dominated
1382 by a cold bb and therefore needs to become cold. Therefore,
1383 its preds will no longer be region crossing. Any non-dominating
1384 preds that were previously hot would also have become cold
1385 in the caller for the same region. Any preds that were previously
1386 region-crossing will be adjusted in fixup_partition_crossing. */
1387 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1389 fixup_partition_crossing (e
);
1392 /* Possibly need to make bb's successor edges region crossing,
1393 or remove stale region crossing. */
1394 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1396 /* We can't have fall-through edges across partition boundaries.
1397 Note that force_nonfallthru will do any necessary partition
1398 boundary fixup by calling fixup_partition_crossing itself. */
1399 if ((e
->flags
& EDGE_FALLTHRU
)
1400 && BB_PARTITION (bb
) != BB_PARTITION (e
->dest
)
1401 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1402 force_nonfallthru (e
);
1404 fixup_partition_crossing (e
);
1408 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1409 expense of adding new instructions or reordering basic blocks.
1411 Function can be also called with edge destination equivalent to the TARGET.
1412 Then it should try the simplifications and do nothing if none is possible.
1414 Return edge representing the branch if transformation succeeded. Return NULL
1416 We still return NULL in case E already destinated TARGET and we didn't
1417 managed to simplify instruction stream. */
1420 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
1423 basic_block src
= e
->src
;
1424 basic_block dest
= e
->dest
;
1426 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1432 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
1434 df_set_bb_dirty (src
);
1435 fixup_partition_crossing (ret
);
1439 ret
= redirect_branch_edge (e
, target
);
1443 df_set_bb_dirty (src
);
1444 fixup_partition_crossing (ret
);
1448 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1451 emit_barrier_after_bb (basic_block bb
)
1453 rtx_barrier
*barrier
= emit_barrier_after (BB_END (bb
));
1454 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1455 || current_ir_type () == IR_RTL_CFGLAYOUT
);
1456 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
1457 BB_FOOTER (bb
) = unlink_insn_chain (barrier
, barrier
);
1460 /* Like force_nonfallthru below, but additionally performs redirection
1461 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1462 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1463 simple_return_rtx, indicating which kind of returnjump to create.
1464 It should be NULL otherwise. */
1467 force_nonfallthru_and_redirect (edge e
, basic_block target
, rtx jump_label
)
1469 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
1472 int abnormal_edge_flags
= 0;
1473 bool asm_goto_edge
= false;
1476 /* In the case the last instruction is conditional jump to the next
1477 instruction, first redirect the jump itself and then continue
1478 by creating a basic block afterwards to redirect fallthru edge. */
1479 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1480 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1481 && any_condjump_p (BB_END (e
->src
))
1482 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1485 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1488 redirected
= redirect_jump (BB_END (e
->src
), block_label (target
), 0);
1489 gcc_assert (redirected
);
1491 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1494 int prob
= XINT (note
, 0);
1496 b
->probability
= prob
;
1497 /* Update this to use GCOV_COMPUTE_SCALE. */
1498 b
->count
= e
->count
* prob
/ REG_BR_PROB_BASE
;
1499 e
->probability
-= e
->probability
;
1500 e
->count
-= b
->count
;
1501 if (e
->probability
< 0)
1508 if (e
->flags
& EDGE_ABNORMAL
)
1510 /* Irritating special case - fallthru edge to the same block as abnormal
1512 We can't redirect abnormal edge, but we still can split the fallthru
1513 one and create separate abnormal edge to original destination.
1514 This allows bb-reorder to make such edge non-fallthru. */
1515 gcc_assert (e
->dest
== target
);
1516 abnormal_edge_flags
= e
->flags
& ~EDGE_FALLTHRU
;
1517 e
->flags
&= EDGE_FALLTHRU
;
1521 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1522 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1524 /* We can't redirect the entry block. Create an empty block
1525 at the start of the function which we use to add the new
1531 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
,
1532 ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1534 /* Change the existing edge's source to be the new block, and add
1535 a new edge from the entry block to the new block. */
1537 for (ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
1538 (tmp
= ei_safe_edge (ei
)); )
1542 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
->unordered_remove (ei
.index
);
1552 vec_safe_push (bb
->succs
, e
);
1553 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
,
1558 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1559 don't point to the target or fallthru label. */
1560 if (JUMP_P (BB_END (e
->src
))
1561 && target
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1562 && (e
->flags
& EDGE_FALLTHRU
)
1563 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
1565 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
1566 bool adjust_jump_target
= false;
1568 for (i
= 0; i
< n
; ++i
)
1570 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (e
->dest
))
1572 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))--;
1573 XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) = block_label (target
);
1574 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))++;
1575 adjust_jump_target
= true;
1577 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (target
))
1578 asm_goto_edge
= true;
1580 if (adjust_jump_target
)
1582 rtx_insn
*insn
= BB_END (e
->src
);
1584 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1585 rtx_insn
*new_label
= BB_HEAD (target
);
1587 if (JUMP_LABEL (insn
) == old_label
)
1589 JUMP_LABEL (insn
) = new_label
;
1590 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1592 remove_note (insn
, note
);
1596 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1598 remove_note (insn
, note
);
1599 if (JUMP_LABEL (insn
) != new_label
1600 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1601 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1603 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1605 XEXP (note
, 0) = new_label
;
1609 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
|| asm_goto_edge
)
1612 gcov_type count
= e
->count
;
1613 int probability
= e
->probability
;
1614 /* Create the new structures. */
1616 /* If the old block ended with a tablejump, skip its table
1617 by searching forward from there. Otherwise start searching
1618 forward from the last instruction of the old block. */
1619 rtx_jump_table_data
*table
;
1620 if (tablejump_p (BB_END (e
->src
), NULL
, &table
))
1623 new_head
= BB_END (e
->src
);
1624 new_head
= NEXT_INSN (new_head
);
1626 jump_block
= create_basic_block (new_head
, NULL
, e
->src
);
1627 jump_block
->count
= count
;
1628 jump_block
->frequency
= EDGE_FREQUENCY (e
);
1630 /* Make sure new block ends up in correct hot/cold section. */
1632 BB_COPY_PARTITION (jump_block
, e
->src
);
1635 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1636 new_edge
->probability
= probability
;
1637 new_edge
->count
= count
;
1639 /* Redirect old edge. */
1640 redirect_edge_pred (e
, jump_block
);
1641 e
->probability
= REG_BR_PROB_BASE
;
1643 /* If e->src was previously region crossing, it no longer is
1644 and the reg crossing note should be removed. */
1645 fixup_partition_crossing (new_edge
);
1647 /* If asm goto has any label refs to target's label,
1648 add also edge from asm goto bb to target. */
1651 new_edge
->probability
/= 2;
1652 new_edge
->count
/= 2;
1653 jump_block
->count
/= 2;
1654 jump_block
->frequency
/= 2;
1655 new_edge
= make_edge (new_edge
->src
, target
,
1656 e
->flags
& ~EDGE_FALLTHRU
);
1657 new_edge
->probability
= probability
- probability
/ 2;
1658 new_edge
->count
= count
- count
/ 2;
1661 new_bb
= jump_block
;
1664 jump_block
= e
->src
;
1666 loc
= e
->goto_locus
;
1667 e
->flags
&= ~EDGE_FALLTHRU
;
1668 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1670 if (jump_label
== ret_rtx
)
1673 emit_jump_insn_after_setloc (gen_return (), BB_END (jump_block
), loc
);
1680 gcc_assert (jump_label
== simple_return_rtx
);
1681 #ifdef HAVE_simple_return
1682 emit_jump_insn_after_setloc (gen_simple_return (),
1683 BB_END (jump_block
), loc
);
1688 set_return_jump_label (BB_END (jump_block
));
1692 rtx label
= block_label (target
);
1693 emit_jump_insn_after_setloc (gen_jump (label
), BB_END (jump_block
), loc
);
1694 JUMP_LABEL (BB_END (jump_block
)) = label
;
1695 LABEL_NUSES (label
)++;
1698 /* We might be in cfg layout mode, and if so, the following routine will
1699 insert the barrier correctly. */
1700 emit_barrier_after_bb (jump_block
);
1701 redirect_edge_succ_nodup (e
, target
);
1703 if (abnormal_edge_flags
)
1704 make_edge (src
, target
, abnormal_edge_flags
);
1706 df_mark_solutions_dirty ();
1707 fixup_partition_crossing (e
);
1711 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1712 (and possibly create new basic block) to make edge non-fallthru.
1713 Return newly created BB or NULL if none. */
1716 rtl_force_nonfallthru (edge e
)
1718 return force_nonfallthru_and_redirect (e
, e
->dest
, NULL_RTX
);
1721 /* Redirect edge even at the expense of creating new jump insn or
1722 basic block. Return new basic block if created, NULL otherwise.
1723 Conversion must be possible. */
1726 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1728 if (redirect_edge_and_branch (e
, target
)
1729 || e
->dest
== target
)
1732 /* In case the edge redirection failed, try to force it to be non-fallthru
1733 and redirect newly created simplejump. */
1734 df_set_bb_dirty (e
->src
);
1735 return force_nonfallthru_and_redirect (e
, target
, NULL_RTX
);
1738 /* The given edge should potentially be a fallthru edge. If that is in
1739 fact true, delete the jump and barriers that are in the way. */
1742 rtl_tidy_fallthru_edge (edge e
)
1745 basic_block b
= e
->src
, c
= b
->next_bb
;
1747 /* ??? In a late-running flow pass, other folks may have deleted basic
1748 blocks by nopping out blocks, leaving multiple BARRIERs between here
1749 and the target label. They ought to be chastised and fixed.
1751 We can also wind up with a sequence of undeletable labels between
1752 one block and the next.
1754 So search through a sequence of barriers, labels, and notes for
1755 the head of block C and assert that we really do fall through. */
1757 for (q
= NEXT_INSN (BB_END (b
)); q
!= BB_HEAD (c
); q
= NEXT_INSN (q
))
1761 /* Remove what will soon cease being the jump insn from the source block.
1762 If block B consisted only of this single jump, turn it into a deleted
1767 && (any_uncondjump_p (q
)
1768 || single_succ_p (b
)))
1771 /* If this was a conditional jump, we need to also delete
1772 the insn that set cc0. */
1773 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1780 /* Selectively unlink the sequence. */
1781 if (q
!= PREV_INSN (BB_HEAD (c
)))
1782 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1784 e
->flags
|= EDGE_FALLTHRU
;
1787 /* Should move basic block BB after basic block AFTER. NIY. */
1790 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1791 basic_block after ATTRIBUTE_UNUSED
)
1796 /* Locate the last bb in the same partition as START_BB. */
1799 last_bb_in_partition (basic_block start_bb
)
1802 FOR_BB_BETWEEN (bb
, start_bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1804 if (BB_PARTITION (start_bb
) != BB_PARTITION (bb
->next_bb
))
1807 /* Return bb before the exit block. */
1811 /* Split a (typically critical) edge. Return the new block.
1812 The edge must not be abnormal.
1814 ??? The code generally expects to be called on critical edges.
1815 The case of a block ending in an unconditional jump to a
1816 block with multiple predecessors is not handled optimally. */
1819 rtl_split_edge (edge edge_in
)
1821 basic_block bb
, new_bb
;
1824 /* Abnormal edges cannot be split. */
1825 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1827 /* We are going to place the new block in front of edge destination.
1828 Avoid existence of fallthru predecessors. */
1829 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1831 edge e
= find_fallthru_edge (edge_in
->dest
->preds
);
1834 force_nonfallthru (e
);
1837 /* Create the basic block note. */
1838 if (edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1839 before
= BB_HEAD (edge_in
->dest
);
1843 /* If this is a fall through edge to the exit block, the blocks might be
1844 not adjacent, and the right place is after the source. */
1845 if ((edge_in
->flags
& EDGE_FALLTHRU
)
1846 && edge_in
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1848 before
= NEXT_INSN (BB_END (edge_in
->src
));
1849 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1850 BB_COPY_PARTITION (bb
, edge_in
->src
);
1854 if (edge_in
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1856 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1857 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1861 basic_block after
= edge_in
->dest
->prev_bb
;
1862 /* If this is post-bb reordering, and the edge crosses a partition
1863 boundary, the new block needs to be inserted in the bb chain
1864 at the end of the src partition (since we put the new bb into
1865 that partition, see below). Otherwise we may end up creating
1866 an extra partition crossing in the chain, which is illegal.
1867 It can't go after the src, because src may have a fall-through
1868 to a different block. */
1869 if (crtl
->bb_reorder_complete
1870 && (edge_in
->flags
& EDGE_CROSSING
))
1872 after
= last_bb_in_partition (edge_in
->src
);
1873 before
= NEXT_INSN (BB_END (after
));
1874 /* The instruction following the last bb in partition should
1875 be a barrier, since it cannot end in a fall-through. */
1876 gcc_checking_assert (BARRIER_P (before
));
1877 before
= NEXT_INSN (before
);
1879 bb
= create_basic_block (before
, NULL
, after
);
1880 /* Put the split bb into the src partition, to avoid creating
1881 a situation where a cold bb dominates a hot bb, in the case
1882 where src is cold and dest is hot. The src will dominate
1883 the new bb (whereas it might not have dominated dest). */
1884 BB_COPY_PARTITION (bb
, edge_in
->src
);
1888 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1890 /* Can't allow a region crossing edge to be fallthrough. */
1891 if (BB_PARTITION (bb
) != BB_PARTITION (edge_in
->dest
)
1892 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1894 new_bb
= force_nonfallthru (single_succ_edge (bb
));
1895 gcc_assert (!new_bb
);
1898 /* For non-fallthru edges, we must adjust the predecessor's
1899 jump instruction to target our new block. */
1900 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1902 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1903 gcc_assert (redirected
);
1907 if (edge_in
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1909 /* For asm goto even splitting of fallthru edge might
1910 need insn patching, as other labels might point to the
1912 rtx_insn
*last
= BB_END (edge_in
->src
);
1915 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1916 && extract_asm_operands (PATTERN (last
)) != NULL_RTX
1917 && patch_jump_insn (last
, before
, bb
))
1918 df_set_bb_dirty (edge_in
->src
);
1920 redirect_edge_succ (edge_in
, bb
);
1926 /* Queue instructions for insertion on an edge between two basic blocks.
1927 The new instructions and basic blocks (if any) will not appear in the
1928 CFG until commit_edge_insertions is called. */
1931 insert_insn_on_edge (rtx pattern
, edge e
)
1933 /* We cannot insert instructions on an abnormal critical edge.
1934 It will be easier to find the culprit if we die now. */
1935 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1937 if (e
->insns
.r
== NULL_RTX
)
1940 push_to_sequence (e
->insns
.r
);
1942 emit_insn (pattern
);
1944 e
->insns
.r
= get_insns ();
1948 /* Update the CFG for the instructions queued on edge E. */
1951 commit_one_edge_insertion (edge e
)
1953 rtx_insn
*before
= NULL
, *after
= NULL
, *insns
, *tmp
, *last
;
1956 /* Pull the insns off the edge now since the edge might go away. */
1960 /* Figure out where to put these insns. If the destination has
1961 one predecessor, insert there. Except for the exit block. */
1962 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1966 /* Get the location correct wrt a code label, and "nice" wrt
1967 a basic block note, and before everything else. */
1970 tmp
= NEXT_INSN (tmp
);
1971 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1972 tmp
= NEXT_INSN (tmp
);
1973 if (tmp
== BB_HEAD (bb
))
1976 after
= PREV_INSN (tmp
);
1978 after
= get_last_insn ();
1981 /* If the source has one successor and the edge is not abnormal,
1982 insert there. Except for the entry block.
1983 Don't do this if the predecessor ends in a jump other than
1984 unconditional simple jump. E.g. for asm goto that points all
1985 its labels at the fallthru basic block, we can't insert instructions
1986 before the asm goto, as the asm goto can have various of side effects,
1987 and can't emit instructions after the asm goto, as it must end
1989 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1990 && single_succ_p (e
->src
)
1991 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1992 && (!JUMP_P (BB_END (e
->src
))
1993 || simplejump_p (BB_END (e
->src
))))
1997 /* It is possible to have a non-simple jump here. Consider a target
1998 where some forms of unconditional jumps clobber a register. This
1999 happens on the fr30 for example.
2001 We know this block has a single successor, so we can just emit
2002 the queued insns before the jump. */
2003 if (JUMP_P (BB_END (bb
)))
2004 before
= BB_END (bb
);
2007 /* We'd better be fallthru, or we've lost track of what's what. */
2008 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
2010 after
= BB_END (bb
);
2014 /* Otherwise we must split the edge. */
2017 bb
= split_edge (e
);
2019 /* If E crossed a partition boundary, we needed to make bb end in
2020 a region-crossing jump, even though it was originally fallthru. */
2021 if (JUMP_P (BB_END (bb
)))
2022 before
= BB_END (bb
);
2024 after
= BB_END (bb
);
2027 /* Now that we've found the spot, do the insertion. */
2030 emit_insn_before_noloc (insns
, before
, bb
);
2031 last
= prev_nonnote_insn (before
);
2034 last
= emit_insn_after_noloc (insns
, after
, bb
);
2036 if (returnjump_p (last
))
2038 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2039 This is not currently a problem because this only happens
2040 for the (single) epilogue, which already has a fallthru edge
2043 e
= single_succ_edge (bb
);
2044 gcc_assert (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2045 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
2047 e
->flags
&= ~EDGE_FALLTHRU
;
2048 emit_barrier_after (last
);
2051 delete_insn (before
);
2054 gcc_assert (!JUMP_P (last
));
2057 /* Update the CFG for all queued instructions. */
2060 commit_edge_insertions (void)
2064 /* Optimization passes that invoke this routine can cause hot blocks
2065 previously reached by both hot and cold blocks to become dominated only
2066 by cold blocks. This will cause the verification below to fail,
2067 and lead to now cold code in the hot section. In some cases this
2068 may only be visible after newly unreachable blocks are deleted,
2069 which will be done by fixup_partitions. */
2070 fixup_partitions ();
2072 #ifdef ENABLE_CHECKING
2073 verify_flow_info ();
2076 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
2077 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
2082 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2084 commit_one_edge_insertion (e
);
2089 /* Print out RTL-specific basic block information (live information
2090 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2091 documented in dumpfile.h. */
2094 rtl_dump_bb (FILE *outf
, basic_block bb
, int indent
, int flags
)
2100 s_indent
= (char *) alloca ((size_t) indent
+ 1);
2101 memset (s_indent
, ' ', (size_t) indent
);
2102 s_indent
[indent
] = '\0';
2104 if (df
&& (flags
& TDF_DETAILS
))
2106 df_dump_top (bb
, outf
);
2110 if (bb
->index
!= ENTRY_BLOCK
&& bb
->index
!= EXIT_BLOCK
)
2111 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
)); insn
!= last
;
2112 insn
= NEXT_INSN (insn
))
2114 if (flags
& TDF_DETAILS
)
2115 df_dump_insn_top (insn
, outf
);
2116 if (! (flags
& TDF_SLIM
))
2117 print_rtl_single (outf
, insn
);
2119 dump_insn_slim (outf
, insn
);
2120 if (flags
& TDF_DETAILS
)
2121 df_dump_insn_bottom (insn
, outf
);
2124 if (df
&& (flags
& TDF_DETAILS
))
2126 df_dump_bottom (bb
, outf
);
2132 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2133 for the start of each basic block. FLAGS are the TDF_* masks documented
2137 print_rtl_with_bb (FILE *outf
, const rtx_insn
*rtx_first
, int flags
)
2139 const rtx_insn
*tmp_rtx
;
2141 fprintf (outf
, "(nil)\n");
2144 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
2145 int max_uid
= get_max_uid ();
2146 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
2147 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
2148 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
2151 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2152 insns, but the CFG is not maintained so the basic block info
2153 is not reliable. Therefore it's omitted from the dumps. */
2154 if (! (cfun
->curr_properties
& PROP_cfg
))
2155 flags
&= ~TDF_BLOCKS
;
2158 df_dump_start (outf
);
2160 if (flags
& TDF_BLOCKS
)
2162 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2166 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
2167 end
[INSN_UID (BB_END (bb
))] = bb
;
2168 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
2170 enum bb_state state
= IN_MULTIPLE_BB
;
2172 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
2174 in_bb_p
[INSN_UID (x
)] = state
;
2176 if (x
== BB_END (bb
))
2182 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
2184 if (flags
& TDF_BLOCKS
)
2186 bb
= start
[INSN_UID (tmp_rtx
)];
2189 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, true, false);
2190 if (df
&& (flags
& TDF_DETAILS
))
2191 df_dump_top (bb
, outf
);
2194 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
2195 && !NOTE_P (tmp_rtx
)
2196 && !BARRIER_P (tmp_rtx
))
2197 fprintf (outf
, ";; Insn is not within a basic block\n");
2198 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
2199 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
2202 if (flags
& TDF_DETAILS
)
2203 df_dump_insn_top (tmp_rtx
, outf
);
2204 if (! (flags
& TDF_SLIM
))
2205 print_rtl_single (outf
, tmp_rtx
);
2207 dump_insn_slim (outf
, tmp_rtx
);
2208 if (flags
& TDF_DETAILS
)
2209 df_dump_insn_bottom (tmp_rtx
, outf
);
2211 if (flags
& TDF_BLOCKS
)
2213 bb
= end
[INSN_UID (tmp_rtx
)];
2216 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, false, true);
2217 if (df
&& (flags
& TDF_DETAILS
))
2218 df_dump_bottom (bb
, outf
);
2230 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2233 update_br_prob_note (basic_block bb
)
2236 if (!JUMP_P (BB_END (bb
)))
2238 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
2239 if (!note
|| XINT (note
, 0) == BRANCH_EDGE (bb
)->probability
)
2241 XINT (note
, 0) = BRANCH_EDGE (bb
)->probability
;
2244 /* Get the last insn associated with block BB (that includes barriers and
2245 tablejumps after BB). */
2247 get_last_bb_insn (basic_block bb
)
2249 rtx_jump_table_data
*table
;
2251 rtx_insn
*end
= BB_END (bb
);
2253 /* Include any jump table following the basic block. */
2254 if (tablejump_p (end
, NULL
, &table
))
2257 /* Include any barriers that may follow the basic block. */
2258 tmp
= next_nonnote_insn_bb (end
);
2259 while (tmp
&& BARRIER_P (tmp
))
2262 tmp
= next_nonnote_insn_bb (end
);
2268 /* Sanity check partition hotness to ensure that basic blocks in
2269 Â the cold partition don't dominate basic blocks in the hot partition.
2270 If FLAG_ONLY is true, report violations as errors. Otherwise
2271 re-mark the dominated blocks as cold, since this is run after
2272 cfg optimizations that may make hot blocks previously reached
2273 by both hot and cold blocks now only reachable along cold paths. */
2275 static vec
<basic_block
>
2276 find_partition_fixes (bool flag_only
)
2279 vec
<basic_block
> bbs_in_cold_partition
= vNULL
;
2280 vec
<basic_block
> bbs_to_fix
= vNULL
;
2282 /* Callers check this. */
2283 gcc_checking_assert (crtl
->has_bb_partition
);
2285 FOR_EACH_BB_FN (bb
, cfun
)
2286 if ((BB_PARTITION (bb
) == BB_COLD_PARTITION
))
2287 bbs_in_cold_partition
.safe_push (bb
);
2289 if (bbs_in_cold_partition
.is_empty ())
2292 bool dom_calculated_here
= !dom_info_available_p (CDI_DOMINATORS
);
2294 if (dom_calculated_here
)
2295 calculate_dominance_info (CDI_DOMINATORS
);
2297 while (! bbs_in_cold_partition
.is_empty ())
2299 bb
= bbs_in_cold_partition
.pop ();
2300 /* Any blocks dominated by a block in the cold section
2301 must also be cold. */
2303 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2305 son
= next_dom_son (CDI_DOMINATORS
, son
))
2307 /* If son is not yet cold, then mark it cold here and
2308 enqueue it for further processing. */
2309 if ((BB_PARTITION (son
) != BB_COLD_PARTITION
))
2312 error ("non-cold basic block %d dominated "
2313 "by a block in the cold partition (%d)", son
->index
, bb
->index
);
2315 BB_SET_PARTITION (son
, BB_COLD_PARTITION
);
2316 bbs_to_fix
.safe_push (son
);
2317 bbs_in_cold_partition
.safe_push (son
);
2322 if (dom_calculated_here
)
2323 free_dominance_info (CDI_DOMINATORS
);
2328 /* Perform cleanup on the hot/cold bb partitioning after optimization
2329 passes that modify the cfg. */
2332 fixup_partitions (void)
2336 if (!crtl
->has_bb_partition
)
2339 /* Delete any blocks that became unreachable and weren't
2340 already cleaned up, for example during edge forwarding
2341 and convert_jumps_to_returns. This will expose more
2342 opportunities for fixing the partition boundaries here.
2343 Also, the calculation of the dominance graph during verification
2344 will assert if there are unreachable nodes. */
2345 delete_unreachable_blocks ();
2347 /* If there are partitions, do a sanity check on them: A basic block in
2348 Â a cold partition cannot dominate a basic block in a hot partition.
2349 Fixup any that now violate this requirement, as a result of edge
2350 forwarding and unreachable block deletion. Â */
2351 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (false);
2353 /* Do the partition fixup after all necessary blocks have been converted to
2354 cold, so that we only update the region crossings the minimum number of
2355 places, which can require forcing edges to be non fallthru. */
2356 while (! bbs_to_fix
.is_empty ())
2358 bb
= bbs_to_fix
.pop ();
2359 fixup_new_cold_bb (bb
);
2363 /* Verify, in the basic block chain, that there is at most one switch
2364 between hot/cold partitions. This condition will not be true until
2365 after reorder_basic_blocks is called. */
2368 verify_hot_cold_block_grouping (void)
2372 bool switched_sections
= false;
2373 int current_partition
= BB_UNPARTITIONED
;
2375 /* Even after bb reordering is complete, we go into cfglayout mode
2376 again (in compgoto). Ensure we don't call this before going back
2377 into linearized RTL when any layout fixes would have been committed. */
2378 if (!crtl
->bb_reorder_complete
2379 || current_ir_type () != IR_RTL_CFGRTL
)
2382 FOR_EACH_BB_FN (bb
, cfun
)
2384 if (current_partition
!= BB_UNPARTITIONED
2385 && BB_PARTITION (bb
) != current_partition
)
2387 if (switched_sections
)
2389 error ("multiple hot/cold transitions found (bb %i)",
2394 switched_sections
= true;
2396 if (!crtl
->has_bb_partition
)
2397 error ("partition found but function partition flag not set");
2399 current_partition
= BB_PARTITION (bb
);
2406 /* Perform several checks on the edges out of each block, such as
2407 the consistency of the branch probabilities, the correctness
2408 of hot/cold partition crossing edges, and the number of expected
2409 successor edges. Also verify that the dominance relationship
2410 between hot/cold blocks is sane. */
2413 rtl_verify_edges (void)
2418 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2420 int n_fallthru
= 0, n_branch
= 0, n_abnormal_call
= 0, n_sibcall
= 0;
2421 int n_eh
= 0, n_abnormal
= 0;
2422 edge e
, fallthru
= NULL
;
2425 bool has_crossing_edge
= false;
2427 if (JUMP_P (BB_END (bb
))
2428 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
2429 && EDGE_COUNT (bb
->succs
) >= 2
2430 && any_condjump_p (BB_END (bb
)))
2432 if (XINT (note
, 0) != BRANCH_EDGE (bb
)->probability
2433 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2435 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2436 XINT (note
, 0), BRANCH_EDGE (bb
)->probability
);
2441 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2445 if (e
->flags
& EDGE_FALLTHRU
)
2446 n_fallthru
++, fallthru
= e
;
2448 is_crossing
= (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
2449 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2450 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
2451 has_crossing_edge
|= is_crossing
;
2452 if (e
->flags
& EDGE_CROSSING
)
2456 error ("EDGE_CROSSING incorrectly set across same section");
2459 if (e
->flags
& EDGE_FALLTHRU
)
2461 error ("fallthru edge crosses section boundary in bb %i",
2465 if (e
->flags
& EDGE_EH
)
2467 error ("EH edge crosses section boundary in bb %i",
2471 if (JUMP_P (BB_END (bb
)) && !CROSSING_JUMP_P (BB_END (bb
)))
2473 error ("No region crossing jump at section boundary in bb %i",
2478 else if (is_crossing
)
2480 error ("EDGE_CROSSING missing across section boundary");
2484 if ((e
->flags
& ~(EDGE_DFS_BACK
2486 | EDGE_IRREDUCIBLE_LOOP
2489 | EDGE_PRESERVE
)) == 0)
2492 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2495 if (e
->flags
& EDGE_SIBCALL
)
2498 if (e
->flags
& EDGE_EH
)
2501 if (e
->flags
& EDGE_ABNORMAL
)
2505 if (!has_crossing_edge
2506 && JUMP_P (BB_END (bb
))
2507 && CROSSING_JUMP_P (BB_END (bb
)))
2509 print_rtl_with_bb (stderr
, get_insns (), TDF_RTL
| TDF_BLOCKS
| TDF_DETAILS
);
2510 error ("Region crossing jump across same section in bb %i",
2515 if (n_eh
&& !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
2517 error ("missing REG_EH_REGION note at the end of bb %i", bb
->index
);
2522 error ("too many exception handling edges in bb %i", bb
->index
);
2526 && (!JUMP_P (BB_END (bb
))
2527 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
2528 || any_condjump_p (BB_END (bb
))))))
2530 error ("too many outgoing branch edges from bb %i", bb
->index
);
2533 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
2535 error ("fallthru edge after unconditional jump in bb %i", bb
->index
);
2538 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
2540 error ("wrong number of branch edges after unconditional jump"
2541 " in bb %i", bb
->index
);
2544 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
2545 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
2547 error ("wrong amount of branch edges after conditional jump"
2548 " in bb %i", bb
->index
);
2551 if (n_abnormal_call
&& !CALL_P (BB_END (bb
)))
2553 error ("abnormal call edges for non-call insn in bb %i", bb
->index
);
2556 if (n_sibcall
&& !CALL_P (BB_END (bb
)))
2558 error ("sibcall edges for non-call insn in bb %i", bb
->index
);
2561 if (n_abnormal
> n_eh
2562 && !(CALL_P (BB_END (bb
))
2563 && n_abnormal
== n_abnormal_call
+ n_sibcall
)
2564 && (!JUMP_P (BB_END (bb
))
2565 || any_condjump_p (BB_END (bb
))
2566 || any_uncondjump_p (BB_END (bb
))))
2568 error ("abnormal edges for no purpose in bb %i", bb
->index
);
2573 /* If there are partitions, do a sanity check on them: A basic block in
2574 Â a cold partition cannot dominate a basic block in a hot partition. Â */
2575 if (crtl
->has_bb_partition
&& !err
)
2577 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (true);
2578 err
= !bbs_to_fix
.is_empty ();
2585 /* Checks on the instructions within blocks. Currently checks that each
2586 block starts with a basic block note, and that basic block notes and
2587 control flow jumps are not found in the middle of the block. */
2590 rtl_verify_bb_insns (void)
2596 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2598 /* Now check the header of basic
2599 block. It ought to contain optional CODE_LABEL followed
2600 by NOTE_BASIC_BLOCK. */
2604 if (BB_END (bb
) == x
)
2606 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2614 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2616 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2621 if (BB_END (bb
) == x
)
2622 /* Do checks for empty blocks here. */
2625 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2627 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2629 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2630 INSN_UID (x
), bb
->index
);
2634 if (x
== BB_END (bb
))
2637 if (control_flow_insn_p (x
))
2639 error ("in basic block %d:", bb
->index
);
2640 fatal_insn ("flow control insn inside a basic block", x
);
2649 /* Verify that block pointers for instructions in basic blocks, headers and
2650 footers are set appropriately. */
2653 rtl_verify_bb_pointers (void)
2658 /* Check the general integrity of the basic blocks. */
2659 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2663 if (!(bb
->flags
& BB_RTL
))
2665 error ("BB_RTL flag not set for block %d", bb
->index
);
2669 FOR_BB_INSNS (bb
, insn
)
2670 if (BLOCK_FOR_INSN (insn
) != bb
)
2672 error ("insn %d basic block pointer is %d, should be %d",
2674 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
2679 for (insn
= BB_HEADER (bb
); insn
; insn
= NEXT_INSN (insn
))
2680 if (!BARRIER_P (insn
)
2681 && BLOCK_FOR_INSN (insn
) != NULL
)
2683 error ("insn %d in header of bb %d has non-NULL basic block",
2684 INSN_UID (insn
), bb
->index
);
2687 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
2688 if (!BARRIER_P (insn
)
2689 && BLOCK_FOR_INSN (insn
) != NULL
)
2691 error ("insn %d in footer of bb %d has non-NULL basic block",
2692 INSN_UID (insn
), bb
->index
);
2701 /* Verify the CFG and RTL consistency common for both underlying RTL and
2704 Currently it does following checks:
2706 - overlapping of basic blocks
2707 - insns with wrong BLOCK_FOR_INSN pointers
2708 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2709 - tails of basic blocks (ensure that boundary is necessary)
2710 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2711 and NOTE_INSN_BASIC_BLOCK
2712 - verify that no fall_thru edge crosses hot/cold partition boundaries
2713 - verify that there are no pending RTL branch predictions
2714 - verify that hot blocks are not dominated by cold blocks
2716 In future it can be extended check a lot of other stuff as well
2717 (reachability of basic blocks, life information, etc. etc.). */
2720 rtl_verify_flow_info_1 (void)
2724 err
|= rtl_verify_bb_pointers ();
2726 err
|= rtl_verify_bb_insns ();
2728 err
|= rtl_verify_edges ();
2733 /* Walk the instruction chain and verify that bb head/end pointers
2734 are correct, and that instructions are in exactly one bb and have
2735 correct block pointers. */
2738 rtl_verify_bb_insn_chain (void)
2743 rtx_insn
*last_head
= get_last_insn ();
2744 basic_block
*bb_info
;
2745 const int max_uid
= get_max_uid ();
2747 bb_info
= XCNEWVEC (basic_block
, max_uid
);
2749 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2751 rtx_insn
*head
= BB_HEAD (bb
);
2752 rtx_insn
*end
= BB_END (bb
);
2754 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2756 /* Verify the end of the basic block is in the INSN chain. */
2760 /* And that the code outside of basic blocks has NULL bb field. */
2762 && BLOCK_FOR_INSN (x
) != NULL
)
2764 error ("insn %d outside of basic blocks has non-NULL bb field",
2772 error ("end insn %d for block %d not found in the insn stream",
2773 INSN_UID (end
), bb
->index
);
2777 /* Work backwards from the end to the head of the basic block
2778 to verify the head is in the RTL chain. */
2779 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2781 /* While walking over the insn chain, verify insns appear
2782 in only one basic block. */
2783 if (bb_info
[INSN_UID (x
)] != NULL
)
2785 error ("insn %d is in multiple basic blocks (%d and %d)",
2786 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2790 bb_info
[INSN_UID (x
)] = bb
;
2797 error ("head insn %d for block %d not found in the insn stream",
2798 INSN_UID (head
), bb
->index
);
2802 last_head
= PREV_INSN (x
);
2805 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2807 /* Check that the code before the first basic block has NULL
2810 && BLOCK_FOR_INSN (x
) != NULL
)
2812 error ("insn %d outside of basic blocks has non-NULL bb field",
2822 /* Verify that fallthru edges point to adjacent blocks in layout order and
2823 that barriers exist after non-fallthru blocks. */
2826 rtl_verify_fallthru (void)
2831 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2835 e
= find_fallthru_edge (bb
->succs
);
2840 /* Ensure existence of barrier in BB with no fallthru edges. */
2841 for (insn
= NEXT_INSN (BB_END (bb
)); ; insn
= NEXT_INSN (insn
))
2843 if (!insn
|| NOTE_INSN_BASIC_BLOCK_P (insn
))
2845 error ("missing barrier after block %i", bb
->index
);
2849 if (BARRIER_P (insn
))
2853 else if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2854 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2858 if (e
->src
->next_bb
!= e
->dest
)
2861 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2862 e
->src
->index
, e
->dest
->index
);
2866 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
2867 insn
= NEXT_INSN (insn
))
2868 if (BARRIER_P (insn
) || INSN_P (insn
))
2870 error ("verify_flow_info: Incorrect fallthru %i->%i",
2871 e
->src
->index
, e
->dest
->index
);
2872 fatal_insn ("wrong insn in the fallthru edge", insn
);
2881 /* Verify that blocks are laid out in consecutive order. While walking the
2882 instructions, verify that all expected instructions are inside the basic
2883 blocks, and that all returns are followed by barriers. */
2886 rtl_verify_bb_layout (void)
2892 rtx_insn
* const rtx_first
= get_insns ();
2893 basic_block last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
), curr_bb
= NULL
;
2896 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
2898 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2900 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2902 bb
= NOTE_BASIC_BLOCK (x
);
2905 if (bb
!= last_bb_seen
->next_bb
)
2906 internal_error ("basic blocks not laid down consecutively");
2908 curr_bb
= last_bb_seen
= bb
;
2913 switch (GET_CODE (x
))
2920 /* An ADDR_VEC is placed outside any basic block. */
2922 && JUMP_TABLE_DATA_P (NEXT_INSN (x
)))
2925 /* But in any case, non-deletable labels can appear anywhere. */
2929 fatal_insn ("insn outside basic block", x
);
2934 && returnjump_p (x
) && ! condjump_p (x
)
2935 && ! (next_nonnote_insn (x
) && BARRIER_P (next_nonnote_insn (x
))))
2936 fatal_insn ("return not followed by barrier", x
);
2938 if (curr_bb
&& x
== BB_END (curr_bb
))
2942 if (num_bb_notes
!= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
)
2944 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2945 num_bb_notes
, n_basic_blocks_for_fn (cfun
));
2950 /* Verify the CFG and RTL consistency common for both underlying RTL and
2951 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
2953 Currently it does following checks:
2954 - all checks of rtl_verify_flow_info_1
2955 - test head/end pointers
2956 - check that blocks are laid out in consecutive order
2957 - check that all insns are in the basic blocks
2958 (except the switch handling code, barriers and notes)
2959 - check that all returns are followed by barriers
2960 - check that all fallthru edge points to the adjacent blocks
2961 - verify that there is a single hot/cold partition boundary after bbro */
2964 rtl_verify_flow_info (void)
2968 err
|= rtl_verify_flow_info_1 ();
2970 err
|= rtl_verify_bb_insn_chain ();
2972 err
|= rtl_verify_fallthru ();
2974 err
|= rtl_verify_bb_layout ();
2976 err
|= verify_hot_cold_block_grouping ();
2981 /* Assume that the preceding pass has possibly eliminated jump instructions
2982 or converted the unconditional jumps. Eliminate the edges from CFG.
2983 Return true if any edges are eliminated. */
2986 purge_dead_edges (basic_block bb
)
2989 rtx_insn
*insn
= BB_END (bb
);
2991 bool purged
= false;
2995 if (DEBUG_INSN_P (insn
) && insn
!= BB_HEAD (bb
))
2997 insn
= PREV_INSN (insn
);
2998 while ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
));
3000 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3001 if (NONJUMP_INSN_P (insn
)
3002 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
3006 if (! may_trap_p (PATTERN (insn
))
3007 || ((eqnote
= find_reg_equal_equiv_note (insn
))
3008 && ! may_trap_p (XEXP (eqnote
, 0))))
3009 remove_note (insn
, note
);
3012 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3013 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3015 bool remove
= false;
3017 /* There are three types of edges we need to handle correctly here: EH
3018 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3019 latter can appear when nonlocal gotos are used. */
3020 if (e
->flags
& EDGE_ABNORMAL_CALL
)
3024 else if (can_nonlocal_goto (insn
))
3026 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3028 else if (flag_tm
&& find_reg_note (insn
, REG_TM
, NULL
))
3033 else if (e
->flags
& EDGE_EH
)
3034 remove
= !can_throw_internal (insn
);
3039 df_set_bb_dirty (bb
);
3052 /* We do care only about conditional jumps and simplejumps. */
3053 if (!any_condjump_p (insn
)
3054 && !returnjump_p (insn
)
3055 && !simplejump_p (insn
))
3058 /* Branch probability/prediction notes are defined only for
3059 condjumps. We've possibly turned condjump into simplejump. */
3060 if (simplejump_p (insn
))
3062 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3064 remove_note (insn
, note
);
3065 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
3066 remove_note (insn
, note
);
3069 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3071 /* Avoid abnormal flags to leak from computed jumps turned
3072 into simplejumps. */
3074 e
->flags
&= ~EDGE_ABNORMAL
;
3076 /* See if this edge is one we should keep. */
3077 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
3078 /* A conditional jump can fall through into the next
3079 block, so we should keep the edge. */
3084 else if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3085 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
3086 /* If the destination block is the target of the jump,
3092 else if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
3093 && returnjump_p (insn
))
3094 /* If the destination block is the exit block, and this
3095 instruction is a return, then keep the edge. */
3100 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3101 /* Keep the edges that correspond to exceptions thrown by
3102 this instruction and rematerialize the EDGE_ABNORMAL
3103 flag we just cleared above. */
3105 e
->flags
|= EDGE_ABNORMAL
;
3110 /* We do not need this edge. */
3111 df_set_bb_dirty (bb
);
3116 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
3120 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
3125 /* Redistribute probabilities. */
3126 if (single_succ_p (bb
))
3128 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3129 single_succ_edge (bb
)->count
= bb
->count
;
3133 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3137 b
= BRANCH_EDGE (bb
);
3138 f
= FALLTHRU_EDGE (bb
);
3139 b
->probability
= XINT (note
, 0);
3140 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
3141 /* Update these to use GCOV_COMPUTE_SCALE. */
3142 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
3143 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
3148 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
3150 /* First, there should not be any EH or ABCALL edges resulting
3151 from non-local gotos and the like. If there were, we shouldn't
3152 have created the sibcall in the first place. Second, there
3153 should of course never have been a fallthru edge. */
3154 gcc_assert (single_succ_p (bb
));
3155 gcc_assert (single_succ_edge (bb
)->flags
3156 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
3161 /* If we don't see a jump insn, we don't know exactly why the block would
3162 have been broken at this point. Look for a simple, non-fallthru edge,
3163 as these are only created by conditional branches. If we find such an
3164 edge we know that there used to be a jump here and can then safely
3165 remove all non-fallthru edges. */
3167 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3168 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
3177 /* Remove all but the fake and fallthru edges. The fake edge may be
3178 the only successor for this block in the case of noreturn
3180 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3182 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
3184 df_set_bb_dirty (bb
);
3192 gcc_assert (single_succ_p (bb
));
3194 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3195 single_succ_edge (bb
)->count
= bb
->count
;
3198 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
3203 /* Search all basic blocks for potentially dead edges and purge them. Return
3204 true if some edge has been eliminated. */
3207 purge_all_dead_edges (void)
3212 FOR_EACH_BB_FN (bb
, cfun
)
3214 bool purged_here
= purge_dead_edges (bb
);
3216 purged
|= purged_here
;
3222 /* This is used by a few passes that emit some instructions after abnormal
3223 calls, moving the basic block's end, while they in fact do want to emit
3224 them on the fallthru edge. Look for abnormal call edges, find backward
3225 the call in the block and insert the instructions on the edge instead.
3227 Similarly, handle instructions throwing exceptions internally.
3229 Return true when instructions have been found and inserted on edges. */
3232 fixup_abnormal_edges (void)
3234 bool inserted
= false;
3237 FOR_EACH_BB_FN (bb
, cfun
)
3242 /* Look for cases we are interested in - calls or instructions causing
3244 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3245 if ((e
->flags
& EDGE_ABNORMAL_CALL
)
3246 || ((e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
3247 == (EDGE_ABNORMAL
| EDGE_EH
)))
3250 if (e
&& !CALL_P (BB_END (bb
)) && !can_throw_internal (BB_END (bb
)))
3254 /* Get past the new insns generated. Allow notes, as the insns
3255 may be already deleted. */
3257 while ((NONJUMP_INSN_P (insn
) || NOTE_P (insn
))
3258 && !can_throw_internal (insn
)
3259 && insn
!= BB_HEAD (bb
))
3260 insn
= PREV_INSN (insn
);
3262 if (CALL_P (insn
) || can_throw_internal (insn
))
3264 rtx_insn
*stop
, *next
;
3266 e
= find_fallthru_edge (bb
->succs
);
3268 stop
= NEXT_INSN (BB_END (bb
));
3271 for (insn
= NEXT_INSN (insn
); insn
!= stop
; insn
= next
)
3273 next
= NEXT_INSN (insn
);
3278 /* Sometimes there's still the return value USE.
3279 If it's placed after a trapping call (i.e. that
3280 call is the last insn anyway), we have no fallthru
3281 edge. Simply delete this use and don't try to insert
3282 on the non-existent edge. */
3283 if (GET_CODE (PATTERN (insn
)) != USE
)
3285 /* We're not deleting it, we're moving it. */
3286 insn
->set_undeleted ();
3287 SET_PREV_INSN (insn
) = NULL_RTX
;
3288 SET_NEXT_INSN (insn
) = NULL_RTX
;
3290 insert_insn_on_edge (insn
, e
);
3294 else if (!BARRIER_P (insn
))
3295 set_block_for_insn (insn
, NULL
);
3299 /* It may be that we don't find any trapping insn. In this
3300 case we discovered quite late that the insn that had been
3301 marked as can_throw_internal in fact couldn't trap at all.
3302 So we should in fact delete the EH edges out of the block. */
3304 purge_dead_edges (bb
);
3311 /* Cut the insns from FIRST to LAST out of the insns stream. */
3314 unlink_insn_chain (rtx_insn
*first
, rtx_insn
*last
)
3316 rtx_insn
*prevfirst
= PREV_INSN (first
);
3317 rtx_insn
*nextlast
= NEXT_INSN (last
);
3319 SET_PREV_INSN (first
) = NULL
;
3320 SET_NEXT_INSN (last
) = NULL
;
3322 SET_NEXT_INSN (prevfirst
) = nextlast
;
3324 SET_PREV_INSN (nextlast
) = prevfirst
;
3326 set_last_insn (prevfirst
);
3328 set_first_insn (nextlast
);
3332 /* Skip over inter-block insns occurring after BB which are typically
3333 associated with BB (e.g., barriers). If there are any such insns,
3334 we return the last one. Otherwise, we return the end of BB. */
3337 skip_insns_after_block (basic_block bb
)
3339 rtx_insn
*insn
, *last_insn
, *next_head
, *prev
;
3342 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3343 next_head
= BB_HEAD (bb
->next_bb
);
3345 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
3347 if (insn
== next_head
)
3350 switch (GET_CODE (insn
))
3357 switch (NOTE_KIND (insn
))
3359 case NOTE_INSN_BLOCK_END
:
3369 if (NEXT_INSN (insn
)
3370 && JUMP_TABLE_DATA_P (NEXT_INSN (insn
)))
3372 insn
= NEXT_INSN (insn
);
3385 /* It is possible to hit contradictory sequence. For instance:
3391 Where barrier belongs to jump_insn, but the note does not. This can be
3392 created by removing the basic block originally following
3393 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3395 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
3397 prev
= PREV_INSN (insn
);
3399 switch (NOTE_KIND (insn
))
3401 case NOTE_INSN_BLOCK_END
:
3404 case NOTE_INSN_DELETED
:
3405 case NOTE_INSN_DELETED_LABEL
:
3406 case NOTE_INSN_DELETED_DEBUG_LABEL
:
3409 reorder_insns (insn
, insn
, last_insn
);
3416 /* Locate or create a label for a given basic block. */
3419 label_for_bb (basic_block bb
)
3421 rtx label
= BB_HEAD (bb
);
3423 if (!LABEL_P (label
))
3426 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
3428 label
= block_label (bb
);
3434 /* Locate the effective beginning and end of the insn chain for each
3435 block, as defined by skip_insns_after_block above. */
3438 record_effective_endpoints (void)
3440 rtx_insn
*next_insn
;
3444 for (insn
= get_insns ();
3447 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
;
3448 insn
= NEXT_INSN (insn
))
3450 /* No basic blocks at all? */
3453 if (PREV_INSN (insn
))
3454 cfg_layout_function_header
=
3455 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
3457 cfg_layout_function_header
= NULL
;
3459 next_insn
= get_insns ();
3460 FOR_EACH_BB_FN (bb
, cfun
)
3464 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
3465 BB_HEADER (bb
) = unlink_insn_chain (next_insn
,
3466 PREV_INSN (BB_HEAD (bb
)));
3467 end
= skip_insns_after_block (bb
);
3468 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
3469 BB_FOOTER (bb
) = unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
3470 next_insn
= NEXT_INSN (BB_END (bb
));
3473 cfg_layout_function_footer
= next_insn
;
3474 if (cfg_layout_function_footer
)
3475 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
3480 const pass_data pass_data_into_cfg_layout_mode
=
3482 RTL_PASS
, /* type */
3483 "into_cfglayout", /* name */
3484 OPTGROUP_NONE
, /* optinfo_flags */
3486 0, /* properties_required */
3487 PROP_cfglayout
, /* properties_provided */
3488 0, /* properties_destroyed */
3489 0, /* todo_flags_start */
3490 0, /* todo_flags_finish */
3493 class pass_into_cfg_layout_mode
: public rtl_opt_pass
3496 pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3497 : rtl_opt_pass (pass_data_into_cfg_layout_mode
, ctxt
)
3500 /* opt_pass methods: */
3501 virtual unsigned int execute (function
*)
3503 cfg_layout_initialize (0);
3507 }; // class pass_into_cfg_layout_mode
3512 make_pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3514 return new pass_into_cfg_layout_mode (ctxt
);
3519 const pass_data pass_data_outof_cfg_layout_mode
=
3521 RTL_PASS
, /* type */
3522 "outof_cfglayout", /* name */
3523 OPTGROUP_NONE
, /* optinfo_flags */
3525 0, /* properties_required */
3526 0, /* properties_provided */
3527 PROP_cfglayout
, /* properties_destroyed */
3528 0, /* todo_flags_start */
3529 0, /* todo_flags_finish */
3532 class pass_outof_cfg_layout_mode
: public rtl_opt_pass
3535 pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3536 : rtl_opt_pass (pass_data_outof_cfg_layout_mode
, ctxt
)
3539 /* opt_pass methods: */
3540 virtual unsigned int execute (function
*);
3542 }; // class pass_outof_cfg_layout_mode
3545 pass_outof_cfg_layout_mode::execute (function
*fun
)
3549 FOR_EACH_BB_FN (bb
, fun
)
3550 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3551 bb
->aux
= bb
->next_bb
;
3553 cfg_layout_finalize ();
3561 make_pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3563 return new pass_outof_cfg_layout_mode (ctxt
);
3567 /* Link the basic blocks in the correct order, compacting the basic
3568 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3569 function also clears the basic block header and footer fields.
3571 This function is usually called after a pass (e.g. tracer) finishes
3572 some transformations while in cfglayout mode. The required sequence
3573 of the basic blocks is in a linked list along the bb->aux field.
3574 This functions re-links the basic block prev_bb and next_bb pointers
3575 accordingly, and it compacts and renumbers the blocks.
3577 FIXME: This currently works only for RTL, but the only RTL-specific
3578 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3579 to GIMPLE a long time ago, but it doesn't relink the basic block
3580 chain. It could do that (to give better initial RTL) if this function
3581 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3584 relink_block_chain (bool stay_in_cfglayout_mode
)
3586 basic_block bb
, prev_bb
;
3589 /* Maybe dump the re-ordered sequence. */
3592 fprintf (dump_file
, "Reordered sequence:\n");
3593 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, index
=
3596 bb
= (basic_block
) bb
->aux
, index
++)
3598 fprintf (dump_file
, " %i ", index
);
3599 if (get_bb_original (bb
))
3600 fprintf (dump_file
, "duplicate of %i ",
3601 get_bb_original (bb
)->index
);
3602 else if (forwarder_block_p (bb
)
3603 && !LABEL_P (BB_HEAD (bb
)))
3604 fprintf (dump_file
, "compensation ");
3606 fprintf (dump_file
, "bb %i ", bb
->index
);
3607 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
3611 /* Now reorder the blocks. */
3612 prev_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
3613 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
3614 for (; bb
; prev_bb
= bb
, bb
= (basic_block
) bb
->aux
)
3616 bb
->prev_bb
= prev_bb
;
3617 prev_bb
->next_bb
= bb
;
3619 prev_bb
->next_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
3620 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
= prev_bb
;
3622 /* Then, clean up the aux fields. */
3623 FOR_ALL_BB_FN (bb
, cfun
)
3626 if (!stay_in_cfglayout_mode
)
3627 BB_HEADER (bb
) = BB_FOOTER (bb
) = NULL
;
3630 /* Maybe reset the original copy tables, they are not valid anymore
3631 when we renumber the basic blocks in compact_blocks. If we are
3632 are going out of cfglayout mode, don't re-allocate the tables. */
3633 free_original_copy_tables ();
3634 if (stay_in_cfglayout_mode
)
3635 initialize_original_copy_tables ();
3637 /* Finally, put basic_block_info in the new order. */
3642 /* Given a reorder chain, rearrange the code to match. */
3645 fixup_reorder_chain (void)
3648 rtx_insn
*insn
= NULL
;
3650 if (cfg_layout_function_header
)
3652 set_first_insn (cfg_layout_function_header
);
3653 insn
= cfg_layout_function_header
;
3654 while (NEXT_INSN (insn
))
3655 insn
= NEXT_INSN (insn
);
3658 /* First do the bulk reordering -- rechain the blocks without regard to
3659 the needed changes to jumps and labels. */
3661 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3667 SET_NEXT_INSN (insn
) = BB_HEADER (bb
);
3669 set_first_insn (BB_HEADER (bb
));
3670 SET_PREV_INSN (BB_HEADER (bb
)) = insn
;
3671 insn
= BB_HEADER (bb
);
3672 while (NEXT_INSN (insn
))
3673 insn
= NEXT_INSN (insn
);
3676 SET_NEXT_INSN (insn
) = BB_HEAD (bb
);
3678 set_first_insn (BB_HEAD (bb
));
3679 SET_PREV_INSN (BB_HEAD (bb
)) = insn
;
3683 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
3684 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
3685 while (NEXT_INSN (insn
))
3686 insn
= NEXT_INSN (insn
);
3690 SET_NEXT_INSN (insn
) = cfg_layout_function_footer
;
3691 if (cfg_layout_function_footer
)
3692 SET_PREV_INSN (cfg_layout_function_footer
) = insn
;
3694 while (NEXT_INSN (insn
))
3695 insn
= NEXT_INSN (insn
);
3697 set_last_insn (insn
);
3698 #ifdef ENABLE_CHECKING
3699 verify_insn_chain ();
3702 /* Now add jumps and labels as needed to match the blocks new
3705 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3708 edge e_fall
, e_taken
, e
;
3709 rtx_insn
*bb_end_insn
;
3710 rtx ret_label
= NULL_RTX
;
3714 if (EDGE_COUNT (bb
->succs
) == 0)
3717 /* Find the old fallthru edge, and another non-EH edge for
3719 e_taken
= e_fall
= NULL
;
3721 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3722 if (e
->flags
& EDGE_FALLTHRU
)
3724 else if (! (e
->flags
& EDGE_EH
))
3727 bb_end_insn
= BB_END (bb
);
3728 if (JUMP_P (bb_end_insn
))
3730 ret_label
= JUMP_LABEL (bb_end_insn
);
3731 if (any_condjump_p (bb_end_insn
))
3733 /* This might happen if the conditional jump has side
3734 effects and could therefore not be optimized away.
3735 Make the basic block to end with a barrier in order
3736 to prevent rtl_verify_flow_info from complaining. */
3739 gcc_assert (!onlyjump_p (bb_end_insn
)
3740 || returnjump_p (bb_end_insn
)
3741 || (e_taken
->flags
& EDGE_CROSSING
));
3742 emit_barrier_after (bb_end_insn
);
3746 /* If the old fallthru is still next, nothing to do. */
3747 if (bb
->aux
== e_fall
->dest
3748 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3751 /* The degenerated case of conditional jump jumping to the next
3752 instruction can happen for jumps with side effects. We need
3753 to construct a forwarder block and this will be done just
3754 fine by force_nonfallthru below. */
3758 /* There is another special case: if *neither* block is next,
3759 such as happens at the very end of a function, then we'll
3760 need to add a new unconditional jump. Choose the taken
3761 edge based on known or assumed probability. */
3762 else if (bb
->aux
!= e_taken
->dest
)
3764 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
3767 && XINT (note
, 0) < REG_BR_PROB_BASE
/ 2
3768 && invert_jump (bb_end_insn
,
3770 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3772 : label_for_bb (e_fall
->dest
)), 0))
3774 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3775 gcc_checking_assert (could_fall_through
3776 (e_taken
->src
, e_taken
->dest
));
3777 e_taken
->flags
|= EDGE_FALLTHRU
;
3778 update_br_prob_note (bb
);
3779 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
3783 /* If the "jumping" edge is a crossing edge, and the fall
3784 through edge is non-crossing, leave things as they are. */
3785 else if ((e_taken
->flags
& EDGE_CROSSING
)
3786 && !(e_fall
->flags
& EDGE_CROSSING
))
3789 /* Otherwise we can try to invert the jump. This will
3790 basically never fail, however, keep up the pretense. */
3791 else if (invert_jump (bb_end_insn
,
3793 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3795 : label_for_bb (e_fall
->dest
)), 0))
3797 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3798 gcc_checking_assert (could_fall_through
3799 (e_taken
->src
, e_taken
->dest
));
3800 e_taken
->flags
|= EDGE_FALLTHRU
;
3801 update_br_prob_note (bb
);
3802 if (LABEL_NUSES (ret_label
) == 0
3803 && single_pred_p (e_taken
->dest
))
3804 delete_insn (ret_label
);
3808 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
3810 /* If the old fallthru is still next or if
3811 asm goto doesn't have a fallthru (e.g. when followed by
3812 __builtin_unreachable ()), nothing to do. */
3814 || bb
->aux
== e_fall
->dest
3815 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3818 /* Otherwise we'll have to use the fallthru fixup below. */
3822 /* Otherwise we have some return, switch or computed
3823 jump. In the 99% case, there should not have been a
3825 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
3831 /* No fallthru implies a noreturn function with EH edges, or
3832 something similarly bizarre. In any case, we don't need to
3837 /* If the fallthru block is still next, nothing to do. */
3838 if (bb
->aux
== e_fall
->dest
)
3841 /* A fallthru to exit block. */
3842 if (e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3846 /* We got here if we need to add a new jump insn.
3847 Note force_nonfallthru can delete E_FALL and thus we have to
3848 save E_FALL->src prior to the call to force_nonfallthru. */
3849 nb
= force_nonfallthru_and_redirect (e_fall
, e_fall
->dest
, ret_label
);
3854 /* Don't process this new block. */
3859 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3861 /* Annoying special case - jump around dead jumptables left in the code. */
3862 FOR_EACH_BB_FN (bb
, cfun
)
3864 edge e
= find_fallthru_edge (bb
->succs
);
3866 if (e
&& !can_fallthru (e
->src
, e
->dest
))
3867 force_nonfallthru (e
);
3870 /* Ensure goto_locus from edges has some instructions with that locus
3873 FOR_EACH_BB_FN (bb
, cfun
)
3878 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3879 if (LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
3880 && !(e
->flags
& EDGE_ABNORMAL
))
3884 basic_block dest
, nb
;
3887 insn
= BB_END (e
->src
);
3888 end
= PREV_INSN (BB_HEAD (e
->src
));
3890 && (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
3891 insn
= PREV_INSN (insn
);
3893 && INSN_LOCATION (insn
) == e
->goto_locus
)
3895 if (simplejump_p (BB_END (e
->src
))
3896 && !INSN_HAS_LOCATION (BB_END (e
->src
)))
3898 INSN_LOCATION (BB_END (e
->src
)) = e
->goto_locus
;
3902 if (dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3904 /* Non-fallthru edges to the exit block cannot be split. */
3905 if (!(e
->flags
& EDGE_FALLTHRU
))
3910 insn
= BB_HEAD (dest
);
3911 end
= NEXT_INSN (BB_END (dest
));
3912 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
3913 insn
= NEXT_INSN (insn
);
3914 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
3915 && INSN_LOCATION (insn
) == e
->goto_locus
)
3918 nb
= split_edge (e
);
3919 if (!INSN_P (BB_END (nb
)))
3920 BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
3922 INSN_LOCATION (BB_END (nb
)) = e
->goto_locus
;
3924 /* If there are other incoming edges to the destination block
3925 with the same goto locus, redirect them to the new block as
3926 well, this can prevent other such blocks from being created
3927 in subsequent iterations of the loop. */
3928 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
3929 if (LOCATION_LOCUS (e2
->goto_locus
) != UNKNOWN_LOCATION
3930 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
3931 && e
->goto_locus
== e2
->goto_locus
)
3932 redirect_edge_and_branch (e2
, nb
);
3939 /* Perform sanity checks on the insn chain.
3940 1. Check that next/prev pointers are consistent in both the forward and
3942 2. Count insns in chain, going both directions, and check if equal.
3943 3. Check that get_last_insn () returns the actual end of chain. */
3946 verify_insn_chain (void)
3948 rtx_insn
*x
, *prevx
, *nextx
;
3949 int insn_cnt1
, insn_cnt2
;
3951 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
3953 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
3954 gcc_assert (PREV_INSN (x
) == prevx
);
3956 gcc_assert (prevx
== get_last_insn ());
3958 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
3960 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
3961 gcc_assert (NEXT_INSN (x
) == nextx
);
3963 gcc_assert (insn_cnt1
== insn_cnt2
);
3966 /* If we have assembler epilogues, the block falling through to exit must
3967 be the last one in the reordered chain when we reach final. Ensure
3968 that this condition is met. */
3970 fixup_fallthru_exit_predecessor (void)
3973 basic_block bb
= NULL
;
3975 /* This transformation is not valid before reload, because we might
3976 separate a call from the instruction that copies the return
3978 gcc_assert (reload_completed
);
3980 e
= find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
3986 basic_block c
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
3988 /* If the very first block is the one with the fall-through exit
3989 edge, we have to split that block. */
3992 bb
= split_block (bb
, NULL
)->dest
;
3995 BB_FOOTER (bb
) = BB_FOOTER (c
);
3996 BB_FOOTER (c
) = NULL
;
3999 while (c
->aux
!= bb
)
4000 c
= (basic_block
) c
->aux
;
4004 c
= (basic_block
) c
->aux
;
4011 /* In case there are more than one fallthru predecessors of exit, force that
4012 there is only one. */
4015 force_one_exit_fallthru (void)
4017 edge e
, predecessor
= NULL
;
4020 basic_block forwarder
, bb
;
4022 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
4023 if (e
->flags
& EDGE_FALLTHRU
)
4025 if (predecessor
== NULL
)
4037 /* Exit has several fallthru predecessors. Create a forwarder block for
4039 forwarder
= split_edge (predecessor
);
4040 for (ei
= ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4041 (e
= ei_safe_edge (ei
)); )
4043 if (e
->src
== forwarder
4044 || !(e
->flags
& EDGE_FALLTHRU
))
4047 redirect_edge_and_branch_force (e
, forwarder
);
4050 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4052 FOR_EACH_BB_FN (bb
, cfun
)
4054 if (bb
->aux
== NULL
&& bb
!= forwarder
)
4056 bb
->aux
= forwarder
;
4062 /* Return true in case it is possible to duplicate the basic block BB. */
4065 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
4067 /* Do not attempt to duplicate tablejumps, as we need to unshare
4068 the dispatch table. This is difficult to do, as the instructions
4069 computing jump destination may be hoisted outside the basic block. */
4070 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
4073 /* Do not duplicate blocks containing insns that can't be copied. */
4074 if (targetm
.cannot_copy_insn_p
)
4076 rtx_insn
*insn
= BB_HEAD (bb
);
4079 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
4081 if (insn
== BB_END (bb
))
4083 insn
= NEXT_INSN (insn
);
4091 duplicate_insn_chain (rtx_insn
*from
, rtx_insn
*to
)
4093 rtx_insn
*insn
, *next
, *copy
;
4096 /* Avoid updating of boundaries of previous basic block. The
4097 note will get removed from insn stream in fixup. */
4098 last
= emit_note (NOTE_INSN_DELETED
);
4100 /* Create copy at the end of INSN chain. The chain will
4101 be reordered later. */
4102 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
4104 switch (GET_CODE (insn
))
4107 /* Don't duplicate label debug insns. */
4108 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
)
4114 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
4115 if (JUMP_P (insn
) && JUMP_LABEL (insn
) != NULL_RTX
4116 && ANY_RETURN_P (JUMP_LABEL (insn
)))
4117 JUMP_LABEL (copy
) = JUMP_LABEL (insn
);
4118 maybe_copy_prologue_epilogue_insn (insn
, copy
);
4121 case JUMP_TABLE_DATA
:
4122 /* Avoid copying of dispatch tables. We never duplicate
4123 tablejumps, so this can hit only in case the table got
4124 moved far from original jump.
4125 Avoid copying following barrier as well if any
4126 (and debug insns in between). */
4127 for (next
= NEXT_INSN (insn
);
4128 next
!= NEXT_INSN (to
);
4129 next
= NEXT_INSN (next
))
4130 if (!DEBUG_INSN_P (next
))
4132 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
4144 switch (NOTE_KIND (insn
))
4146 /* In case prologue is empty and function contain label
4147 in first BB, we may want to copy the block. */
4148 case NOTE_INSN_PROLOGUE_END
:
4150 case NOTE_INSN_DELETED
:
4151 case NOTE_INSN_DELETED_LABEL
:
4152 case NOTE_INSN_DELETED_DEBUG_LABEL
:
4153 /* No problem to strip these. */
4154 case NOTE_INSN_FUNCTION_BEG
:
4155 /* There is always just single entry to function. */
4156 case NOTE_INSN_BASIC_BLOCK
:
4157 /* We should only switch text sections once. */
4158 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
4161 case NOTE_INSN_EPILOGUE_BEG
:
4162 emit_note_copy (as_a
<rtx_note
*> (insn
));
4166 /* All other notes should have already been eliminated. */
4174 insn
= NEXT_INSN (last
);
4179 /* Create a duplicate of the basic block BB. */
4182 cfg_layout_duplicate_bb (basic_block bb
)
4187 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
4188 new_bb
= create_basic_block (insn
,
4189 insn
? get_last_insn () : NULL
,
4190 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
);
4192 BB_COPY_PARTITION (new_bb
, bb
);
4195 insn
= BB_HEADER (bb
);
4196 while (NEXT_INSN (insn
))
4197 insn
= NEXT_INSN (insn
);
4198 insn
= duplicate_insn_chain (BB_HEADER (bb
), insn
);
4200 BB_HEADER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4205 insn
= BB_FOOTER (bb
);
4206 while (NEXT_INSN (insn
))
4207 insn
= NEXT_INSN (insn
);
4208 insn
= duplicate_insn_chain (BB_FOOTER (bb
), insn
);
4210 BB_FOOTER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4217 /* Main entry point to this module - initialize the datastructures for
4218 CFG layout changes. It keeps LOOPS up-to-date if not null.
4220 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4223 cfg_layout_initialize (unsigned int flags
)
4228 /* Once bb partitioning is complete, cfg layout mode should not be
4229 re-entered. Entering cfg layout mode may require fixups. As an
4230 example, if edge forwarding performed when optimizing the cfg
4231 layout required moving a block from the hot to the cold
4232 section. This would create an illegal partitioning unless some
4233 manual fixup was performed. */
4234 gcc_assert (!(crtl
->bb_reorder_complete
4235 && flag_reorder_blocks_and_partition
));
4237 initialize_original_copy_tables ();
4239 cfg_layout_rtl_register_cfg_hooks ();
4241 record_effective_endpoints ();
4243 /* Make sure that the targets of non local gotos are marked. */
4244 for (x
= nonlocal_goto_handler_labels
; x
; x
= x
->next ())
4246 bb
= BLOCK_FOR_INSN (x
->insn ());
4247 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
4250 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
4253 /* Splits superblocks. */
4255 break_superblocks (void)
4257 sbitmap superblocks
;
4261 superblocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
4262 bitmap_clear (superblocks
);
4264 FOR_EACH_BB_FN (bb
, cfun
)
4265 if (bb
->flags
& BB_SUPERBLOCK
)
4267 bb
->flags
&= ~BB_SUPERBLOCK
;
4268 bitmap_set_bit (superblocks
, bb
->index
);
4274 rebuild_jump_labels (get_insns ());
4275 find_many_sub_basic_blocks (superblocks
);
4281 /* Finalize the changes: reorder insn list according to the sequence specified
4282 by aux pointers, enter compensation code, rebuild scope forest. */
4285 cfg_layout_finalize (void)
4287 #ifdef ENABLE_CHECKING
4288 verify_flow_info ();
4290 force_one_exit_fallthru ();
4291 rtl_register_cfg_hooks ();
4292 if (reload_completed
4293 #ifdef HAVE_epilogue
4297 fixup_fallthru_exit_predecessor ();
4298 fixup_reorder_chain ();
4300 rebuild_jump_labels (get_insns ());
4301 delete_dead_jumptables ();
4303 #ifdef ENABLE_CHECKING
4304 verify_insn_chain ();
4305 verify_flow_info ();
4310 /* Same as split_block but update cfg_layout structures. */
4313 cfg_layout_split_block (basic_block bb
, void *insnp
)
4315 rtx insn
= (rtx
) insnp
;
4316 basic_block new_bb
= rtl_split_block (bb
, insn
);
4318 BB_FOOTER (new_bb
) = BB_FOOTER (bb
);
4319 BB_FOOTER (bb
) = NULL
;
4324 /* Redirect Edge to DEST. */
4326 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
4328 basic_block src
= e
->src
;
4331 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4334 if (e
->dest
== dest
)
4337 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4338 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
4340 df_set_bb_dirty (src
);
4344 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4345 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
4348 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
4349 e
->src
->index
, dest
->index
);
4351 df_set_bb_dirty (e
->src
);
4352 redirect_edge_succ (e
, dest
);
4356 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4357 in the case the basic block appears to be in sequence. Avoid this
4360 if (e
->flags
& EDGE_FALLTHRU
)
4362 /* Redirect any branch edges unified with the fallthru one. */
4363 if (JUMP_P (BB_END (src
))
4364 && label_is_jump_target_p (BB_HEAD (e
->dest
),
4370 fprintf (dump_file
, "Fallthru edge unified with branch "
4371 "%i->%i redirected to %i\n",
4372 e
->src
->index
, e
->dest
->index
, dest
->index
);
4373 e
->flags
&= ~EDGE_FALLTHRU
;
4374 redirected
= redirect_branch_edge (e
, dest
);
4375 gcc_assert (redirected
);
4376 redirected
->flags
|= EDGE_FALLTHRU
;
4377 df_set_bb_dirty (redirected
->src
);
4380 /* In case we are redirecting fallthru edge to the branch edge
4381 of conditional jump, remove it. */
4382 if (EDGE_COUNT (src
->succs
) == 2)
4384 /* Find the edge that is different from E. */
4385 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
4388 && any_condjump_p (BB_END (src
))
4389 && onlyjump_p (BB_END (src
)))
4390 delete_insn (BB_END (src
));
4393 fprintf (dump_file
, "Redirecting fallthru edge %i->%i to %i\n",
4394 e
->src
->index
, e
->dest
->index
, dest
->index
);
4395 ret
= redirect_edge_succ_nodup (e
, dest
);
4398 ret
= redirect_branch_edge (e
, dest
);
4400 /* We don't want simplejumps in the insn stream during cfglayout. */
4401 gcc_assert (!simplejump_p (BB_END (src
)));
4403 df_set_bb_dirty (src
);
4407 /* Simple wrapper as we always can redirect fallthru edges. */
4409 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
4411 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
4413 gcc_assert (redirected
);
4417 /* Same as delete_basic_block but update cfg_layout structures. */
4420 cfg_layout_delete_block (basic_block bb
)
4422 rtx_insn
*insn
, *next
, *prev
= PREV_INSN (BB_HEAD (bb
)), *remaints
;
4427 next
= BB_HEAD (bb
);
4429 SET_NEXT_INSN (prev
) = BB_HEADER (bb
);
4431 set_first_insn (BB_HEADER (bb
));
4432 SET_PREV_INSN (BB_HEADER (bb
)) = prev
;
4433 insn
= BB_HEADER (bb
);
4434 while (NEXT_INSN (insn
))
4435 insn
= NEXT_INSN (insn
);
4436 SET_NEXT_INSN (insn
) = next
;
4437 SET_PREV_INSN (next
) = insn
;
4439 next
= NEXT_INSN (BB_END (bb
));
4442 insn
= BB_FOOTER (bb
);
4445 if (BARRIER_P (insn
))
4447 if (PREV_INSN (insn
))
4448 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
4450 BB_FOOTER (bb
) = NEXT_INSN (insn
);
4451 if (NEXT_INSN (insn
))
4452 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
4456 insn
= NEXT_INSN (insn
);
4461 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
4462 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
4463 while (NEXT_INSN (insn
))
4464 insn
= NEXT_INSN (insn
);
4465 SET_NEXT_INSN (insn
) = next
;
4467 SET_PREV_INSN (next
) = insn
;
4469 set_last_insn (insn
);
4472 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
4473 to
= &BB_HEADER (bb
->next_bb
);
4475 to
= &cfg_layout_function_footer
;
4477 rtl_delete_block (bb
);
4480 prev
= NEXT_INSN (prev
);
4482 prev
= get_insns ();
4484 next
= PREV_INSN (next
);
4486 next
= get_last_insn ();
4488 if (next
&& NEXT_INSN (next
) != prev
)
4490 remaints
= unlink_insn_chain (prev
, next
);
4492 while (NEXT_INSN (insn
))
4493 insn
= NEXT_INSN (insn
);
4494 SET_NEXT_INSN (insn
) = *to
;
4496 SET_PREV_INSN (*to
) = insn
;
4501 /* Return true when blocks A and B can be safely merged. */
4504 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
4506 /* If we are partitioning hot/cold basic blocks, we don't want to
4507 mess up unconditional or indirect jumps that cross between hot
4510 Basic block partitioning may result in some jumps that appear to
4511 be optimizable (or blocks that appear to be mergeable), but which really
4512 must be left untouched (they are required to make it safely across
4513 partition boundaries). See the comments at the top of
4514 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4516 if (BB_PARTITION (a
) != BB_PARTITION (b
))
4519 /* Protect the loop latches. */
4520 if (current_loops
&& b
->loop_father
->latch
== b
)
4523 /* If we would end up moving B's instructions, make sure it doesn't fall
4524 through into the exit block, since we cannot recover from a fallthrough
4525 edge into the exit block occurring in the middle of a function. */
4526 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4528 edge e
= find_fallthru_edge (b
->succs
);
4529 if (e
&& e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4533 /* There must be exactly one edge in between the blocks. */
4534 return (single_succ_p (a
)
4535 && single_succ (a
) == b
4536 && single_pred_p (b
) == 1
4538 /* Must be simple edge. */
4539 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
4540 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4541 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
4542 /* If the jump insn has side effects, we can't kill the edge.
4543 When not optimizing, try_redirect_by_replacing_jump will
4544 not allow us to redirect an edge by replacing a table jump. */
4545 && (!JUMP_P (BB_END (a
))
4546 || ((!optimize
|| reload_completed
)
4547 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
4550 /* Merge block A and B. The blocks must be mergeable. */
4553 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
4555 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
4558 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a
, b
));
4561 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
4564 /* If there was a CODE_LABEL beginning B, delete it. */
4565 if (LABEL_P (BB_HEAD (b
)))
4567 delete_insn (BB_HEAD (b
));
4570 /* We should have fallthru edge in a, or we can do dummy redirection to get
4572 if (JUMP_P (BB_END (a
)))
4573 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
4574 gcc_assert (!JUMP_P (BB_END (a
)));
4576 /* When not optimizing and the edge is the only place in RTL which holds
4577 some unique locus, emit a nop with that locus in between. */
4579 emit_nop_for_unique_locus_between (a
, b
);
4581 /* Move things from b->footer after a->footer. */
4585 BB_FOOTER (a
) = BB_FOOTER (b
);
4588 rtx_insn
*last
= BB_FOOTER (a
);
4590 while (NEXT_INSN (last
))
4591 last
= NEXT_INSN (last
);
4592 SET_NEXT_INSN (last
) = BB_FOOTER (b
);
4593 SET_PREV_INSN (BB_FOOTER (b
)) = last
;
4595 BB_FOOTER (b
) = NULL
;
4598 /* Move things from b->header before a->footer.
4599 Note that this may include dead tablejump data, but we don't clean
4600 those up until we go out of cfglayout mode. */
4603 if (! BB_FOOTER (a
))
4604 BB_FOOTER (a
) = BB_HEADER (b
);
4607 rtx_insn
*last
= BB_HEADER (b
);
4609 while (NEXT_INSN (last
))
4610 last
= NEXT_INSN (last
);
4611 SET_NEXT_INSN (last
) = BB_FOOTER (a
);
4612 SET_PREV_INSN (BB_FOOTER (a
)) = last
;
4613 BB_FOOTER (a
) = BB_HEADER (b
);
4615 BB_HEADER (b
) = NULL
;
4618 /* In the case basic blocks are not adjacent, move them around. */
4619 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4621 insn
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
4623 emit_insn_after_noloc (insn
, BB_END (a
), a
);
4625 /* Otherwise just re-associate the instructions. */
4629 BB_END (a
) = BB_END (b
);
4632 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4633 We need to explicitly call. */
4634 update_bb_for_insn_chain (insn
, BB_END (b
), a
);
4636 /* Skip possible DELETED_LABEL insn. */
4637 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
4638 insn
= NEXT_INSN (insn
);
4639 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4640 BB_HEAD (b
) = BB_END (b
) = NULL
;
4643 df_bb_delete (b
->index
);
4645 /* If B was a forwarder block, propagate the locus on the edge. */
4647 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
4648 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
4651 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
4657 cfg_layout_split_edge (edge e
)
4659 basic_block new_bb
=
4660 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4661 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
4664 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4665 BB_COPY_PARTITION (new_bb
, e
->src
);
4667 BB_COPY_PARTITION (new_bb
, e
->dest
);
4668 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
4669 redirect_edge_and_branch_force (e
, new_bb
);
4674 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4677 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
4681 /* Return true if BB contains only labels or non-executable
4685 rtl_block_empty_p (basic_block bb
)
4689 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4690 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4693 FOR_BB_INSNS (bb
, insn
)
4694 if (NONDEBUG_INSN_P (insn
) && !any_uncondjump_p (insn
))
4700 /* Split a basic block if it ends with a conditional branch and if
4701 the other part of the block is not empty. */
4704 rtl_split_block_before_cond_jump (basic_block bb
)
4707 rtx_insn
*split_point
= NULL
;
4708 rtx_insn
*last
= NULL
;
4709 bool found_code
= false;
4711 FOR_BB_INSNS (bb
, insn
)
4713 if (any_condjump_p (insn
))
4715 else if (NONDEBUG_INSN_P (insn
))
4720 /* Did not find everything. */
4721 if (found_code
&& split_point
)
4722 return split_block (bb
, split_point
)->dest
;
4727 /* Return 1 if BB ends with a call, possibly followed by some
4728 instructions that must stay with the call, 0 otherwise. */
4731 rtl_block_ends_with_call_p (basic_block bb
)
4733 rtx_insn
*insn
= BB_END (bb
);
4735 while (!CALL_P (insn
)
4736 && insn
!= BB_HEAD (bb
)
4737 && (keep_with_call_p (insn
)
4739 || DEBUG_INSN_P (insn
)))
4740 insn
= PREV_INSN (insn
);
4741 return (CALL_P (insn
));
4744 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4747 rtl_block_ends_with_condjump_p (const_basic_block bb
)
4749 return any_condjump_p (BB_END (bb
));
4752 /* Return true if we need to add fake edge to exit.
4753 Helper function for rtl_flow_call_edges_add. */
4756 need_fake_edge_p (const rtx_insn
*insn
)
4762 && !SIBLING_CALL_P (insn
)
4763 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
4764 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
4767 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
4768 && MEM_VOLATILE_P (PATTERN (insn
)))
4769 || (GET_CODE (PATTERN (insn
)) == PARALLEL
4770 && asm_noperands (insn
) != -1
4771 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
4772 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
4775 /* Add fake edges to the function exit for any non constant and non noreturn
4776 calls, volatile inline assembly in the bitmap of blocks specified by
4777 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4780 The goal is to expose cases in which entering a basic block does not imply
4781 that all subsequent instructions must be executed. */
4784 rtl_flow_call_edges_add (sbitmap blocks
)
4787 int blocks_split
= 0;
4788 int last_bb
= last_basic_block_for_fn (cfun
);
4789 bool check_last_block
= false;
4791 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
4795 check_last_block
= true;
4797 check_last_block
= bitmap_bit_p (blocks
,
4798 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
->index
);
4800 /* In the last basic block, before epilogue generation, there will be
4801 a fallthru edge to EXIT. Special care is required if the last insn
4802 of the last basic block is a call because make_edge folds duplicate
4803 edges, which would result in the fallthru edge also being marked
4804 fake, which would result in the fallthru edge being removed by
4805 remove_fake_edges, which would result in an invalid CFG.
4807 Moreover, we can't elide the outgoing fake edge, since the block
4808 profiler needs to take this into account in order to solve the minimal
4809 spanning tree in the case that the call doesn't return.
4811 Handle this by adding a dummy instruction in a new last basic block. */
4812 if (check_last_block
)
4814 basic_block bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
4815 rtx_insn
*insn
= BB_END (bb
);
4817 /* Back up past insns that must be kept in the same block as a call. */
4818 while (insn
!= BB_HEAD (bb
)
4819 && keep_with_call_p (insn
))
4820 insn
= PREV_INSN (insn
);
4822 if (need_fake_edge_p (insn
))
4826 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4829 insert_insn_on_edge (gen_use (const0_rtx
), e
);
4830 commit_edge_insertions ();
4835 /* Now add fake edges to the function exit for any non constant
4836 calls since there is no way that we can determine if they will
4839 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
4841 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
4843 rtx_insn
*prev_insn
;
4848 if (blocks
&& !bitmap_bit_p (blocks
, i
))
4851 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
4853 prev_insn
= PREV_INSN (insn
);
4854 if (need_fake_edge_p (insn
))
4857 rtx_insn
*split_at_insn
= insn
;
4859 /* Don't split the block between a call and an insn that should
4860 remain in the same block as the call. */
4862 while (split_at_insn
!= BB_END (bb
)
4863 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
4864 split_at_insn
= NEXT_INSN (split_at_insn
);
4866 /* The handling above of the final block before the epilogue
4867 should be enough to verify that there is no edge to the exit
4868 block in CFG already. Calling make_edge in such case would
4869 cause us to mark that edge as fake and remove it later. */
4871 #ifdef ENABLE_CHECKING
4872 if (split_at_insn
== BB_END (bb
))
4874 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4875 gcc_assert (e
== NULL
);
4879 /* Note that the following may create a new basic block
4880 and renumber the existing basic blocks. */
4881 if (split_at_insn
!= BB_END (bb
))
4883 e
= split_block (bb
, split_at_insn
);
4888 make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
4891 if (insn
== BB_HEAD (bb
))
4897 verify_flow_info ();
4899 return blocks_split
;
4902 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4903 the conditional branch target, SECOND_HEAD should be the fall-thru
4904 there is no need to handle this here the loop versioning code handles
4905 this. the reason for SECON_HEAD is that it is needed for condition
4906 in trees, and this should be of the same type since it is a hook. */
4908 rtl_lv_add_condition_to_bb (basic_block first_head
,
4909 basic_block second_head ATTRIBUTE_UNUSED
,
4910 basic_block cond_bb
, void *comp_rtx
)
4913 rtx_insn
*seq
, *jump
;
4914 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
4915 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
4916 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
4917 enum machine_mode mode
;
4920 label
= block_label (first_head
);
4921 mode
= GET_MODE (op0
);
4922 if (mode
== VOIDmode
)
4923 mode
= GET_MODE (op1
);
4926 op0
= force_operand (op0
, NULL_RTX
);
4927 op1
= force_operand (op1
, NULL_RTX
);
4928 do_compare_rtx_and_jump (op0
, op1
, comp
, 0,
4929 mode
, NULL_RTX
, NULL_RTX
, label
, -1);
4930 jump
= get_last_insn ();
4931 JUMP_LABEL (jump
) = label
;
4932 LABEL_NUSES (label
)++;
4936 /* Add the new cond, in the new head. */
4937 emit_insn_after (seq
, BB_END (cond_bb
));
4941 /* Given a block B with unconditional branch at its end, get the
4942 store the return the branch edge and the fall-thru edge in
4943 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4945 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
4946 edge
*fallthru_edge
)
4948 edge e
= EDGE_SUCC (b
, 0);
4950 if (e
->flags
& EDGE_FALLTHRU
)
4953 *branch_edge
= EDGE_SUCC (b
, 1);
4958 *fallthru_edge
= EDGE_SUCC (b
, 1);
4963 init_rtl_bb_info (basic_block bb
)
4965 gcc_assert (!bb
->il
.x
.rtl
);
4966 bb
->il
.x
.head_
= NULL
;
4967 bb
->il
.x
.rtl
= ggc_cleared_alloc
<rtl_bb_info
> ();
4970 /* Returns true if it is possible to remove edge E by redirecting
4971 it to the destination of the other edge from E->src. */
4974 rtl_can_remove_branch_p (const_edge e
)
4976 const_basic_block src
= e
->src
;
4977 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
4978 const rtx_insn
*insn
= BB_END (src
);
4981 /* The conditions are taken from try_redirect_by_replacing_jump. */
4982 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4985 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4988 if (BB_PARTITION (src
) != BB_PARTITION (target
))
4991 if (!onlyjump_p (insn
)
4992 || tablejump_p (insn
, NULL
, NULL
))
4995 set
= single_set (insn
);
4996 if (!set
|| side_effects_p (set
))
5003 rtl_duplicate_bb (basic_block bb
)
5005 bb
= cfg_layout_duplicate_bb (bb
);
5010 /* Do book-keeping of basic block BB for the profile consistency checker.
5011 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
5012 then do post-pass accounting. Store the counting in RECORD. */
5014 rtl_account_profile_record (basic_block bb
, int after_pass
,
5015 struct profile_record
*record
)
5018 FOR_BB_INSNS (bb
, insn
)
5021 record
->size
[after_pass
]
5022 += insn_rtx_cost (PATTERN (insn
), false);
5023 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
5024 record
->time
[after_pass
]
5025 += insn_rtx_cost (PATTERN (insn
), true) * bb
->count
;
5026 else if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
5027 record
->time
[after_pass
]
5028 += insn_rtx_cost (PATTERN (insn
), true) * bb
->frequency
;
5032 /* Implementation of CFG manipulation for linearized RTL. */
5033 struct cfg_hooks rtl_cfg_hooks
= {
5035 rtl_verify_flow_info
,
5037 rtl_dump_bb_for_graph
,
5038 rtl_create_basic_block
,
5039 rtl_redirect_edge_and_branch
,
5040 rtl_redirect_edge_and_branch_force
,
5041 rtl_can_remove_branch_p
,
5044 rtl_move_block_after
,
5045 rtl_can_merge_blocks
, /* can_merge_blocks_p */
5049 cfg_layout_can_duplicate_bb_p
,
5052 rtl_make_forwarder_block
,
5053 rtl_tidy_fallthru_edge
,
5054 rtl_force_nonfallthru
,
5055 rtl_block_ends_with_call_p
,
5056 rtl_block_ends_with_condjump_p
,
5057 rtl_flow_call_edges_add
,
5058 NULL
, /* execute_on_growing_pred */
5059 NULL
, /* execute_on_shrinking_pred */
5060 NULL
, /* duplicate loop for trees */
5061 NULL
, /* lv_add_condition_to_bb */
5062 NULL
, /* lv_adjust_loop_header_phi*/
5063 NULL
, /* extract_cond_bb_edges */
5064 NULL
, /* flush_pending_stmts */
5065 rtl_block_empty_p
, /* block_empty_p */
5066 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5067 rtl_account_profile_record
,
5070 /* Implementation of CFG manipulation for cfg layout RTL, where
5071 basic block connected via fallthru edges does not have to be adjacent.
5072 This representation will hopefully become the default one in future
5073 version of the compiler. */
5075 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
5077 rtl_verify_flow_info_1
,
5079 rtl_dump_bb_for_graph
,
5080 cfg_layout_create_basic_block
,
5081 cfg_layout_redirect_edge_and_branch
,
5082 cfg_layout_redirect_edge_and_branch_force
,
5083 rtl_can_remove_branch_p
,
5084 cfg_layout_delete_block
,
5085 cfg_layout_split_block
,
5086 rtl_move_block_after
,
5087 cfg_layout_can_merge_blocks_p
,
5088 cfg_layout_merge_blocks
,
5091 cfg_layout_can_duplicate_bb_p
,
5092 cfg_layout_duplicate_bb
,
5093 cfg_layout_split_edge
,
5094 rtl_make_forwarder_block
,
5095 NULL
, /* tidy_fallthru_edge */
5096 rtl_force_nonfallthru
,
5097 rtl_block_ends_with_call_p
,
5098 rtl_block_ends_with_condjump_p
,
5099 rtl_flow_call_edges_add
,
5100 NULL
, /* execute_on_growing_pred */
5101 NULL
, /* execute_on_shrinking_pred */
5102 duplicate_loop_to_header_edge
, /* duplicate loop for trees */
5103 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
5104 NULL
, /* lv_adjust_loop_header_phi*/
5105 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
5106 NULL
, /* flush_pending_stmts */
5107 rtl_block_empty_p
, /* block_empty_p */
5108 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5109 rtl_account_profile_record
,
5112 #include "gt-cfgrtl.h"