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"
53 #include "dominance.h"
58 #include "cfgcleanup.h"
59 #include "basic-block.h"
60 #include "bb-reorder.h"
64 #include "rtl-error.h"
67 #include "insn-attr.h"
68 #include "insn-config.h"
71 #include "common/common-target.h"
74 #include "tree-pass.h"
77 /* Holds the interesting leading and trailing notes for the function.
78 Only applicable if the CFG is in cfglayout mode. */
79 static GTY(()) rtx_insn
*cfg_layout_function_footer
;
80 static GTY(()) rtx_insn
*cfg_layout_function_header
;
82 static rtx_insn
*skip_insns_after_block (basic_block
);
83 static void record_effective_endpoints (void);
84 static rtx
label_for_bb (basic_block
);
85 static void fixup_reorder_chain (void);
87 void verify_insn_chain (void);
88 static void fixup_fallthru_exit_predecessor (void);
89 static int can_delete_note_p (const rtx_note
*);
90 static int can_delete_label_p (const rtx_code_label
*);
91 static basic_block
rtl_split_edge (edge
);
92 static bool rtl_move_block_after (basic_block
, basic_block
);
93 static int rtl_verify_flow_info (void);
94 static basic_block
cfg_layout_split_block (basic_block
, void *);
95 static edge
cfg_layout_redirect_edge_and_branch (edge
, basic_block
);
96 static basic_block
cfg_layout_redirect_edge_and_branch_force (edge
, basic_block
);
97 static void cfg_layout_delete_block (basic_block
);
98 static void rtl_delete_block (basic_block
);
99 static basic_block
rtl_redirect_edge_and_branch_force (edge
, basic_block
);
100 static edge
rtl_redirect_edge_and_branch (edge
, basic_block
);
101 static basic_block
rtl_split_block (basic_block
, void *);
102 static void rtl_dump_bb (FILE *, basic_block
, int, int);
103 static int rtl_verify_flow_info_1 (void);
104 static void rtl_make_forwarder_block (edge
);
106 /* Return true if NOTE is not one of the ones that must be kept paired,
107 so that we may simply delete it. */
110 can_delete_note_p (const rtx_note
*note
)
112 switch (NOTE_KIND (note
))
114 case NOTE_INSN_DELETED
:
115 case NOTE_INSN_BASIC_BLOCK
:
116 case NOTE_INSN_EPILOGUE_BEG
:
124 /* True if a given label can be deleted. */
127 can_delete_label_p (const rtx_code_label
*label
)
129 return (!LABEL_PRESERVE_P (label
)
130 /* User declared labels must be preserved. */
131 && LABEL_NAME (label
) == 0
132 && !in_expr_list_p (forced_labels
, label
));
135 /* Delete INSN by patching it out. */
138 delete_insn (rtx uncast_insn
)
140 rtx_insn
*insn
= as_a
<rtx_insn
*> (uncast_insn
);
142 bool really_delete
= true;
146 /* Some labels can't be directly removed from the INSN chain, as they
147 might be references via variables, constant pool etc.
148 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
149 if (! can_delete_label_p (as_a
<rtx_code_label
*> (insn
)))
151 const char *name
= LABEL_NAME (insn
);
152 basic_block bb
= BLOCK_FOR_INSN (insn
);
153 rtx_insn
*bb_note
= NEXT_INSN (insn
);
155 really_delete
= false;
156 PUT_CODE (insn
, NOTE
);
157 NOTE_KIND (insn
) = NOTE_INSN_DELETED_LABEL
;
158 NOTE_DELETED_LABEL_NAME (insn
) = name
;
160 /* If the note following the label starts a basic block, and the
161 label is a member of the same basic block, interchange the two. */
162 if (bb_note
!= NULL_RTX
163 && NOTE_INSN_BASIC_BLOCK_P (bb_note
)
165 && bb
== BLOCK_FOR_INSN (bb_note
))
167 reorder_insns_nobb (insn
, insn
, bb_note
);
168 BB_HEAD (bb
) = bb_note
;
169 if (BB_END (bb
) == bb_note
)
174 remove_node_from_insn_list (insn
, &nonlocal_goto_handler_labels
);
179 /* If this insn has already been deleted, something is very wrong. */
180 gcc_assert (!insn
->deleted ());
182 df_insn_delete (insn
);
184 insn
->set_deleted ();
187 /* If deleting a jump, decrement the use count of the label. Deleting
188 the label itself should happen in the normal course of block merging. */
191 if (JUMP_LABEL (insn
)
192 && LABEL_P (JUMP_LABEL (insn
)))
193 LABEL_NUSES (JUMP_LABEL (insn
))--;
195 /* If there are more targets, remove them too. */
197 = find_reg_note (insn
, REG_LABEL_TARGET
, NULL_RTX
)) != NULL_RTX
198 && LABEL_P (XEXP (note
, 0)))
200 LABEL_NUSES (XEXP (note
, 0))--;
201 remove_note (insn
, note
);
205 /* Also if deleting any insn that references a label as an operand. */
206 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, NULL_RTX
)) != NULL_RTX
207 && LABEL_P (XEXP (note
, 0)))
209 LABEL_NUSES (XEXP (note
, 0))--;
210 remove_note (insn
, note
);
213 if (rtx_jump_table_data
*table
= dyn_cast
<rtx_jump_table_data
*> (insn
))
215 rtvec vec
= table
->get_labels ();
216 int len
= GET_NUM_ELEM (vec
);
219 for (i
= 0; i
< len
; i
++)
221 rtx label
= XEXP (RTVEC_ELT (vec
, i
), 0);
223 /* When deleting code in bulk (e.g. removing many unreachable
224 blocks) we can delete a label that's a target of the vector
225 before deleting the vector itself. */
227 LABEL_NUSES (label
)--;
232 /* Like delete_insn but also purge dead edges from BB. */
235 delete_insn_and_edges (rtx_insn
*insn
)
240 && BLOCK_FOR_INSN (insn
)
241 && BB_END (BLOCK_FOR_INSN (insn
)) == insn
)
245 purge_dead_edges (BLOCK_FOR_INSN (insn
));
248 /* Unlink a chain of insns between START and FINISH, leaving notes
249 that must be paired. If CLEAR_BB is true, we set bb field for
250 insns that cannot be removed to NULL. */
253 delete_insn_chain (rtx start
, rtx finish
, bool clear_bb
)
255 rtx_insn
*prev
, *current
;
257 /* Unchain the insns one by one. It would be quicker to delete all of these
258 with a single unchaining, rather than one at a time, but we need to keep
260 current
= safe_as_a
<rtx_insn
*> (finish
);
263 prev
= PREV_INSN (current
);
264 if (NOTE_P (current
) && !can_delete_note_p (as_a
<rtx_note
*> (current
)))
267 delete_insn (current
);
269 if (clear_bb
&& !current
->deleted ())
270 set_block_for_insn (current
, NULL
);
272 if (current
== start
)
278 /* Create a new basic block consisting of the instructions between HEAD and END
279 inclusive. This function is designed to allow fast BB construction - reuses
280 the note and basic block struct in BB_NOTE, if any and do not grow
281 BASIC_BLOCK chain and should be used directly only by CFG construction code.
282 END can be NULL in to create new empty basic block before HEAD. Both END
283 and HEAD can be NULL to create basic block at the end of INSN chain.
284 AFTER is the basic block we should be put after. */
287 create_basic_block_structure (rtx_insn
*head
, rtx_insn
*end
, rtx_note
*bb_note
,
293 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
296 /* If we found an existing note, thread it back onto the chain. */
304 after
= PREV_INSN (head
);
308 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
309 reorder_insns_nobb (bb_note
, bb_note
, after
);
313 /* Otherwise we must create a note and a basic block structure. */
317 init_rtl_bb_info (bb
);
320 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
321 else if (LABEL_P (head
) && end
)
323 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
329 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
335 NOTE_BASIC_BLOCK (bb_note
) = bb
;
338 /* Always include the bb note in the block. */
339 if (NEXT_INSN (end
) == bb_note
)
344 bb
->index
= last_basic_block_for_fn (cfun
)++;
345 bb
->flags
= BB_NEW
| BB_RTL
;
346 link_block (bb
, after
);
347 SET_BASIC_BLOCK_FOR_FN (cfun
, bb
->index
, bb
);
348 df_bb_refs_record (bb
->index
, false);
349 update_bb_for_insn (bb
);
350 BB_SET_PARTITION (bb
, BB_UNPARTITIONED
);
352 /* Tag the block so that we know it has been used when considering
353 other basic block notes. */
359 /* Create new basic block consisting of instructions in between HEAD and END
360 and place it to the BB chain after block AFTER. END can be NULL to
361 create a new empty basic block before HEAD. Both END and HEAD can be
362 NULL to create basic block at the end of INSN chain. */
365 rtl_create_basic_block (void *headp
, void *endp
, basic_block after
)
367 rtx_insn
*head
= (rtx_insn
*) headp
;
368 rtx_insn
*end
= (rtx_insn
*) endp
;
371 /* Grow the basic block array if needed. */
372 if ((size_t) last_basic_block_for_fn (cfun
)
373 >= basic_block_info_for_fn (cfun
)->length ())
376 (last_basic_block_for_fn (cfun
)
377 + (last_basic_block_for_fn (cfun
) + 3) / 4);
378 vec_safe_grow_cleared (basic_block_info_for_fn (cfun
), new_size
);
381 n_basic_blocks_for_fn (cfun
)++;
383 bb
= create_basic_block_structure (head
, end
, NULL
, after
);
389 cfg_layout_create_basic_block (void *head
, void *end
, basic_block after
)
391 basic_block newbb
= rtl_create_basic_block (head
, end
, after
);
396 /* Delete the insns in a (non-live) block. We physically delete every
397 non-deleted-note insn, and update the flow graph appropriately.
399 Return nonzero if we deleted an exception handler. */
401 /* ??? Preserving all such notes strikes me as wrong. It would be nice
402 to post-process the stream to remove empty blocks, loops, ranges, etc. */
405 rtl_delete_block (basic_block b
)
407 rtx_insn
*insn
, *end
;
409 /* If the head of this block is a CODE_LABEL, then it might be the
410 label for an exception handler which can't be reached. We need
411 to remove the label from the exception_handler_label list. */
414 end
= get_last_bb_insn (b
);
416 /* Selectively delete the entire chain. */
418 delete_insn_chain (insn
, end
, true);
422 fprintf (dump_file
, "deleting block %d\n", b
->index
);
423 df_bb_delete (b
->index
);
426 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
429 compute_bb_for_insn (void)
433 FOR_EACH_BB_FN (bb
, cfun
)
435 rtx_insn
*end
= BB_END (bb
);
438 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
440 BLOCK_FOR_INSN (insn
) = bb
;
447 /* Release the basic_block_for_insn array. */
450 free_bb_for_insn (void)
453 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
454 if (!BARRIER_P (insn
))
455 BLOCK_FOR_INSN (insn
) = NULL
;
461 const pass_data pass_data_free_cfg
=
464 "*free_cfg", /* name */
465 OPTGROUP_NONE
, /* optinfo_flags */
467 0, /* properties_required */
468 0, /* properties_provided */
469 PROP_cfg
, /* properties_destroyed */
470 0, /* todo_flags_start */
471 0, /* todo_flags_finish */
474 class pass_free_cfg
: public rtl_opt_pass
477 pass_free_cfg (gcc::context
*ctxt
)
478 : rtl_opt_pass (pass_data_free_cfg
, ctxt
)
481 /* opt_pass methods: */
482 virtual unsigned int execute (function
*);
484 }; // class pass_free_cfg
487 pass_free_cfg::execute (function
*)
490 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
491 valid at that point so it would be too late to call df_analyze. */
492 if (optimize
> 0 && flag_delayed_branch
)
494 df_note_add_problem ();
499 if (crtl
->has_bb_partition
)
500 insert_section_boundary_note ();
509 make_pass_free_cfg (gcc::context
*ctxt
)
511 return new pass_free_cfg (ctxt
);
514 /* Return RTX to emit after when we want to emit code on the entry of function. */
516 entry_of_function (void)
518 return (n_basic_blocks_for_fn (cfun
) > NUM_FIXED_BLOCKS
?
519 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
) : get_insns ());
522 /* Emit INSN at the entry point of the function, ensuring that it is only
523 executed once per function. */
525 emit_insn_at_entry (rtx insn
)
527 edge_iterator ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
528 edge e
= ei_safe_edge (ei
);
529 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
531 insert_insn_on_edge (insn
, e
);
532 commit_edge_insertions ();
535 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
536 (or BARRIER if found) and notify df of the bb change.
537 The insn chain range is inclusive
538 (i.e. both BEGIN and END will be updated. */
541 update_bb_for_insn_chain (rtx_insn
*begin
, rtx_insn
*end
, basic_block bb
)
545 end
= NEXT_INSN (end
);
546 for (insn
= begin
; insn
!= end
; insn
= NEXT_INSN (insn
))
547 if (!BARRIER_P (insn
))
548 df_insn_change_bb (insn
, bb
);
551 /* Update BLOCK_FOR_INSN of insns in BB to BB,
552 and notify df of the change. */
555 update_bb_for_insn (basic_block bb
)
557 update_bb_for_insn_chain (BB_HEAD (bb
), BB_END (bb
), bb
);
561 /* Like active_insn_p, except keep the return value clobber around
562 even after reload. */
565 flow_active_insn_p (const rtx_insn
*insn
)
567 if (active_insn_p (insn
))
570 /* A clobber of the function return value exists for buggy
571 programs that fail to return a value. Its effect is to
572 keep the return value from being live across the entire
573 function. If we allow it to be skipped, we introduce the
574 possibility for register lifetime confusion. */
575 if (GET_CODE (PATTERN (insn
)) == CLOBBER
576 && REG_P (XEXP (PATTERN (insn
), 0))
577 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn
), 0)))
583 /* Return true if the block has no effect and only forwards control flow to
584 its single destination. */
587 contains_no_active_insn_p (const_basic_block bb
)
591 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
592 || !single_succ_p (bb
))
595 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
596 if (INSN_P (insn
) && flow_active_insn_p (insn
))
599 return (!INSN_P (insn
)
600 || (JUMP_P (insn
) && simplejump_p (insn
))
601 || !flow_active_insn_p (insn
));
604 /* Likewise, but protect loop latches, headers and preheaders. */
605 /* FIXME: Make this a cfg hook. */
608 forwarder_block_p (const_basic_block bb
)
610 if (!contains_no_active_insn_p (bb
))
613 /* Protect loop latches, headers and preheaders. */
617 if (bb
->loop_father
->header
== bb
)
619 dest
= EDGE_SUCC (bb
, 0)->dest
;
620 if (dest
->loop_father
->header
== dest
)
627 /* Return nonzero if we can reach target from src by falling through. */
628 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
631 can_fallthru (basic_block src
, basic_block target
)
633 rtx_insn
*insn
= BB_END (src
);
638 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
640 if (src
->next_bb
!= target
)
643 /* ??? Later we may add code to move jump tables offline. */
644 if (tablejump_p (insn
, NULL
, NULL
))
647 FOR_EACH_EDGE (e
, ei
, src
->succs
)
648 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
649 && e
->flags
& EDGE_FALLTHRU
)
652 insn2
= BB_HEAD (target
);
653 if (!active_insn_p (insn2
))
654 insn2
= next_active_insn (insn2
);
656 return next_active_insn (insn
) == insn2
;
659 /* Return nonzero if we could reach target from src by falling through,
660 if the target was made adjacent. If we already have a fall-through
661 edge to the exit block, we can't do that. */
663 could_fall_through (basic_block src
, basic_block target
)
668 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
670 FOR_EACH_EDGE (e
, ei
, src
->succs
)
671 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
672 && e
->flags
& EDGE_FALLTHRU
)
677 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
679 bb_note (basic_block bb
)
685 note
= NEXT_INSN (note
);
687 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
688 return as_a
<rtx_note
*> (note
);
691 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
692 note associated with the BLOCK. */
695 first_insn_after_basic_block_note (basic_block block
)
699 /* Get the first instruction in the block. */
700 insn
= BB_HEAD (block
);
702 if (insn
== NULL_RTX
)
705 insn
= NEXT_INSN (insn
);
706 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
708 return NEXT_INSN (insn
);
711 /* Creates a new basic block just after basic block BB by splitting
712 everything after specified instruction INSNP. */
715 rtl_split_block (basic_block bb
, void *insnp
)
718 rtx_insn
*insn
= (rtx_insn
*) insnp
;
724 insn
= first_insn_after_basic_block_note (bb
);
728 rtx_insn
*next
= insn
;
730 insn
= PREV_INSN (insn
);
732 /* If the block contains only debug insns, insn would have
733 been NULL in a non-debug compilation, and then we'd end
734 up emitting a DELETED note. For -fcompare-debug
735 stability, emit the note too. */
736 if (insn
!= BB_END (bb
)
737 && DEBUG_INSN_P (next
)
738 && DEBUG_INSN_P (BB_END (bb
)))
740 while (next
!= BB_END (bb
) && DEBUG_INSN_P (next
))
741 next
= NEXT_INSN (next
);
743 if (next
== BB_END (bb
))
744 emit_note_after (NOTE_INSN_DELETED
, next
);
748 insn
= get_last_insn ();
751 /* We probably should check type of the insn so that we do not create
752 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
754 if (insn
== BB_END (bb
))
755 emit_note_after (NOTE_INSN_DELETED
, insn
);
757 /* Create the new basic block. */
758 new_bb
= create_basic_block (NEXT_INSN (insn
), BB_END (bb
), bb
);
759 BB_COPY_PARTITION (new_bb
, bb
);
762 /* Redirect the outgoing edges. */
763 new_bb
->succs
= bb
->succs
;
765 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
768 /* The new block starts off being dirty. */
769 df_set_bb_dirty (bb
);
773 /* Return true if the single edge between blocks A and B is the only place
774 in RTL which holds some unique locus. */
777 unique_locus_on_edge_between_p (basic_block a
, basic_block b
)
779 const location_t goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
780 rtx_insn
*insn
, *end
;
782 if (LOCATION_LOCUS (goto_locus
) == UNKNOWN_LOCATION
)
785 /* First scan block A backward. */
787 end
= PREV_INSN (BB_HEAD (a
));
788 while (insn
!= end
&& (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
789 insn
= PREV_INSN (insn
);
791 if (insn
!= end
&& INSN_LOCATION (insn
) == goto_locus
)
794 /* Then scan block B forward. */
798 end
= NEXT_INSN (BB_END (b
));
799 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
800 insn
= NEXT_INSN (insn
);
802 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
803 && INSN_LOCATION (insn
) == goto_locus
)
810 /* If the single edge between blocks A and B is the only place in RTL which
811 holds some unique locus, emit a nop with that locus between the blocks. */
814 emit_nop_for_unique_locus_between (basic_block a
, basic_block b
)
816 if (!unique_locus_on_edge_between_p (a
, b
))
819 BB_END (a
) = emit_insn_after_noloc (gen_nop (), BB_END (a
), a
);
820 INSN_LOCATION (BB_END (a
)) = EDGE_SUCC (a
, 0)->goto_locus
;
823 /* Blocks A and B are to be merged into a single block A. The insns
824 are already contiguous. */
827 rtl_merge_blocks (basic_block a
, basic_block b
)
829 rtx_insn
*b_head
= BB_HEAD (b
), *b_end
= BB_END (b
), *a_end
= BB_END (a
);
830 rtx_insn
*del_first
= NULL
, *del_last
= NULL
;
831 rtx_insn
*b_debug_start
= b_end
, *b_debug_end
= b_end
;
832 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
836 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
839 while (DEBUG_INSN_P (b_end
))
840 b_end
= PREV_INSN (b_debug_start
= b_end
);
842 /* If there was a CODE_LABEL beginning B, delete it. */
843 if (LABEL_P (b_head
))
845 /* Detect basic blocks with nothing but a label. This can happen
846 in particular at the end of a function. */
850 del_first
= del_last
= b_head
;
851 b_head
= NEXT_INSN (b_head
);
854 /* Delete the basic block note and handle blocks containing just that
856 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
864 b_head
= NEXT_INSN (b_head
);
867 /* If there was a jump out of A, delete it. */
872 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
874 || NOTE_INSN_BASIC_BLOCK_P (prev
)
875 || prev
== BB_HEAD (a
))
881 /* If this was a conditional jump, we need to also delete
882 the insn that set cc0. */
883 if (only_sets_cc0_p (prev
))
885 rtx_insn
*tmp
= prev
;
887 prev
= prev_nonnote_insn (prev
);
894 a_end
= PREV_INSN (del_first
);
896 else if (BARRIER_P (NEXT_INSN (a_end
)))
897 del_first
= NEXT_INSN (a_end
);
899 /* Delete everything marked above as well as crap that might be
900 hanging out between the two blocks. */
902 BB_HEAD (b
) = b_empty
? NULL
: b_head
;
903 delete_insn_chain (del_first
, del_last
, true);
905 /* When not optimizing and the edge is the only place in RTL which holds
906 some unique locus, emit a nop with that locus in between. */
909 emit_nop_for_unique_locus_between (a
, b
);
913 /* Reassociate the insns of B with A. */
916 update_bb_for_insn_chain (a_end
, b_debug_end
, a
);
918 BB_END (a
) = b_debug_end
;
921 else if (b_end
!= b_debug_end
)
923 /* Move any deleted labels and other notes between the end of A
924 and the debug insns that make up B after the debug insns,
925 bringing the debug insns into A while keeping the notes after
927 if (NEXT_INSN (a_end
) != b_debug_start
)
928 reorder_insns_nobb (NEXT_INSN (a_end
), PREV_INSN (b_debug_start
),
930 update_bb_for_insn_chain (b_debug_start
, b_debug_end
, a
);
931 BB_END (a
) = b_debug_end
;
934 df_bb_delete (b
->index
);
936 /* If B was a forwarder block, propagate the locus on the edge. */
938 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
939 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
942 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
946 /* Return true when block A and B can be merged. */
949 rtl_can_merge_blocks (basic_block a
, basic_block b
)
951 /* If we are partitioning hot/cold basic blocks, we don't want to
952 mess up unconditional or indirect jumps that cross between hot
955 Basic block partitioning may result in some jumps that appear to
956 be optimizable (or blocks that appear to be mergeable), but which really
957 must be left untouched (they are required to make it safely across
958 partition boundaries). See the comments at the top of
959 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
961 if (BB_PARTITION (a
) != BB_PARTITION (b
))
964 /* Protect the loop latches. */
965 if (current_loops
&& b
->loop_father
->latch
== b
)
968 /* There must be exactly one edge in between the blocks. */
969 return (single_succ_p (a
)
970 && single_succ (a
) == b
973 /* Must be simple edge. */
974 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
976 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
977 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
978 /* If the jump insn has side effects,
979 we can't kill the edge. */
980 && (!JUMP_P (BB_END (a
))
982 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
985 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
989 block_label (basic_block block
)
991 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
994 if (!LABEL_P (BB_HEAD (block
)))
996 BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
999 return BB_HEAD (block
);
1002 /* Attempt to perform edge redirection by replacing possibly complex jump
1003 instruction by unconditional jump or removing jump completely. This can
1004 apply only if all edges now point to the same block. The parameters and
1005 return values are equivalent to redirect_edge_and_branch. */
1008 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
1010 basic_block src
= e
->src
;
1011 rtx_insn
*insn
= BB_END (src
), *kill_from
;
1015 /* If we are partitioning hot/cold basic blocks, we don't want to
1016 mess up unconditional or indirect jumps that cross between hot
1019 Basic block partitioning may result in some jumps that appear to
1020 be optimizable (or blocks that appear to be mergeable), but which really
1021 must be left untouched (they are required to make it safely across
1022 partition boundaries). See the comments at the top of
1023 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1025 if (BB_PARTITION (src
) != BB_PARTITION (target
))
1028 /* We can replace or remove a complex jump only when we have exactly
1029 two edges. Also, if we have exactly one outgoing edge, we can
1031 if (EDGE_COUNT (src
->succs
) >= 3
1032 /* Verify that all targets will be TARGET. Specifically, the
1033 edge that is not E must also go to TARGET. */
1034 || (EDGE_COUNT (src
->succs
) == 2
1035 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
1038 if (!onlyjump_p (insn
))
1040 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
1043 /* Avoid removing branch with side effects. */
1044 set
= single_set (insn
);
1045 if (!set
|| side_effects_p (set
))
1048 /* In case we zap a conditional jump, we'll need to kill
1049 the cc0 setter too. */
1052 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
))
1053 && only_sets_cc0_p (PREV_INSN (insn
)))
1054 kill_from
= PREV_INSN (insn
);
1057 /* See if we can create the fallthru edge. */
1058 if (in_cfglayout
|| can_fallthru (src
, target
))
1061 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
1064 /* Selectively unlink whole insn chain. */
1067 rtx_insn
*insn
= BB_FOOTER (src
);
1069 delete_insn_chain (kill_from
, BB_END (src
), false);
1071 /* Remove barriers but keep jumptables. */
1074 if (BARRIER_P (insn
))
1076 if (PREV_INSN (insn
))
1077 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1079 BB_FOOTER (src
) = NEXT_INSN (insn
);
1080 if (NEXT_INSN (insn
))
1081 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1085 insn
= NEXT_INSN (insn
);
1089 delete_insn_chain (kill_from
, PREV_INSN (BB_HEAD (target
)),
1093 /* If this already is simplejump, redirect it. */
1094 else if (simplejump_p (insn
))
1096 if (e
->dest
== target
)
1099 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
1100 INSN_UID (insn
), e
->dest
->index
, target
->index
);
1101 if (!redirect_jump (insn
, block_label (target
), 0))
1103 gcc_assert (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1108 /* Cannot do anything for target exit block. */
1109 else if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1112 /* Or replace possibly complicated jump insn by simple jump insn. */
1115 rtx target_label
= block_label (target
);
1118 rtx_jump_table_data
*table
;
1120 emit_jump_insn_after_noloc (gen_jump (target_label
), insn
);
1121 JUMP_LABEL (BB_END (src
)) = target_label
;
1122 LABEL_NUSES (target_label
)++;
1124 fprintf (dump_file
, "Replacing insn %i by jump %i\n",
1125 INSN_UID (insn
), INSN_UID (BB_END (src
)));
1128 delete_insn_chain (kill_from
, insn
, false);
1130 /* Recognize a tablejump that we are converting to a
1131 simple jump and remove its associated CODE_LABEL
1132 and ADDR_VEC or ADDR_DIFF_VEC. */
1133 if (tablejump_p (insn
, &label
, &table
))
1134 delete_insn_chain (label
, table
, false);
1136 barrier
= next_nonnote_insn (BB_END (src
));
1137 if (!barrier
|| !BARRIER_P (barrier
))
1138 emit_barrier_after (BB_END (src
));
1141 if (barrier
!= NEXT_INSN (BB_END (src
)))
1143 /* Move the jump before barrier so that the notes
1144 which originally were or were created before jump table are
1145 inside the basic block. */
1146 rtx_insn
*new_insn
= BB_END (src
);
1148 update_bb_for_insn_chain (NEXT_INSN (BB_END (src
)),
1149 PREV_INSN (barrier
), src
);
1151 SET_NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
1152 SET_PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
1154 SET_NEXT_INSN (new_insn
) = barrier
;
1155 SET_NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
1157 SET_PREV_INSN (new_insn
) = PREV_INSN (barrier
);
1158 SET_PREV_INSN (barrier
) = new_insn
;
1163 /* Keep only one edge out and set proper flags. */
1164 if (!single_succ_p (src
))
1166 gcc_assert (single_succ_p (src
));
1168 e
= single_succ_edge (src
);
1170 e
->flags
= EDGE_FALLTHRU
;
1174 e
->probability
= REG_BR_PROB_BASE
;
1175 e
->count
= src
->count
;
1177 if (e
->dest
!= target
)
1178 redirect_edge_succ (e
, target
);
1182 /* Subroutine of redirect_branch_edge that tries to patch the jump
1183 instruction INSN so that it reaches block NEW. Do this
1184 only when it originally reached block OLD. Return true if this
1185 worked or the original target wasn't OLD, return false if redirection
1189 patch_jump_insn (rtx_insn
*insn
, rtx_insn
*old_label
, basic_block new_bb
)
1191 rtx_jump_table_data
*table
;
1193 /* Recognize a tablejump and adjust all matching cases. */
1194 if (tablejump_p (insn
, NULL
, &table
))
1198 rtx new_label
= block_label (new_bb
);
1200 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1202 vec
= table
->get_labels ();
1204 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
1205 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
1207 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
1208 --LABEL_NUSES (old_label
);
1209 ++LABEL_NUSES (new_label
);
1212 /* Handle casesi dispatch insns. */
1213 if ((tmp
= single_set (insn
)) != NULL
1214 && SET_DEST (tmp
) == pc_rtx
1215 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
1216 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
1217 && LABEL_REF_LABEL (XEXP (SET_SRC (tmp
), 2)) == old_label
)
1219 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
1221 --LABEL_NUSES (old_label
);
1222 ++LABEL_NUSES (new_label
);
1225 else if ((tmp
= extract_asm_operands (PATTERN (insn
))) != NULL
)
1227 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (tmp
);
1228 rtx new_label
, note
;
1230 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1232 new_label
= block_label (new_bb
);
1234 for (i
= 0; i
< n
; ++i
)
1236 rtx old_ref
= ASM_OPERANDS_LABEL (tmp
, i
);
1237 gcc_assert (GET_CODE (old_ref
) == LABEL_REF
);
1238 if (XEXP (old_ref
, 0) == old_label
)
1240 ASM_OPERANDS_LABEL (tmp
, i
)
1241 = gen_rtx_LABEL_REF (Pmode
, new_label
);
1242 --LABEL_NUSES (old_label
);
1243 ++LABEL_NUSES (new_label
);
1247 if (JUMP_LABEL (insn
) == old_label
)
1249 JUMP_LABEL (insn
) = new_label
;
1250 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1252 remove_note (insn
, note
);
1256 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1258 remove_note (insn
, note
);
1259 if (JUMP_LABEL (insn
) != new_label
1260 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1261 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1263 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1265 XEXP (note
, 0) = new_label
;
1269 /* ?? We may play the games with moving the named labels from
1270 one basic block to the other in case only one computed_jump is
1272 if (computed_jump_p (insn
)
1273 /* A return instruction can't be redirected. */
1274 || returnjump_p (insn
))
1277 if (!currently_expanding_to_rtl
|| JUMP_LABEL (insn
) == old_label
)
1279 /* If the insn doesn't go where we think, we're confused. */
1280 gcc_assert (JUMP_LABEL (insn
) == old_label
);
1282 /* If the substitution doesn't succeed, die. This can happen
1283 if the back end emitted unrecognizable instructions or if
1284 target is exit block on some arches. */
1285 if (!redirect_jump (insn
, block_label (new_bb
), 0))
1287 gcc_assert (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1296 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1299 redirect_branch_edge (edge e
, basic_block target
)
1301 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1302 basic_block src
= e
->src
;
1303 rtx_insn
*insn
= BB_END (src
);
1305 /* We can only redirect non-fallthru edges of jump insn. */
1306 if (e
->flags
& EDGE_FALLTHRU
)
1308 else if (!JUMP_P (insn
) && !currently_expanding_to_rtl
)
1311 if (!currently_expanding_to_rtl
)
1313 if (!patch_jump_insn (insn
, old_label
, target
))
1317 /* When expanding this BB might actually contain multiple
1318 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1319 Redirect all of those that match our label. */
1320 FOR_BB_INSNS (src
, insn
)
1321 if (JUMP_P (insn
) && !patch_jump_insn (insn
, old_label
, target
))
1325 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
1326 e
->src
->index
, e
->dest
->index
, target
->index
);
1328 if (e
->dest
!= target
)
1329 e
= redirect_edge_succ_nodup (e
, target
);
1334 /* Called when edge E has been redirected to a new destination,
1335 in order to update the region crossing flag on the edge and
1339 fixup_partition_crossing (edge e
)
1341 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || e
->dest
1342 == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1344 /* If we redirected an existing edge, it may already be marked
1345 crossing, even though the new src is missing a reg crossing note.
1346 But make sure reg crossing note doesn't already exist before
1348 if (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1350 e
->flags
|= EDGE_CROSSING
;
1351 if (JUMP_P (BB_END (e
->src
))
1352 && !CROSSING_JUMP_P (BB_END (e
->src
)))
1353 CROSSING_JUMP_P (BB_END (e
->src
)) = 1;
1355 else if (BB_PARTITION (e
->src
) == BB_PARTITION (e
->dest
))
1357 e
->flags
&= ~EDGE_CROSSING
;
1358 /* Remove the section crossing note from jump at end of
1359 src if it exists, and if no other successors are
1361 if (JUMP_P (BB_END (e
->src
)) && CROSSING_JUMP_P (BB_END (e
->src
)))
1363 bool has_crossing_succ
= false;
1366 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
1368 has_crossing_succ
|= (e2
->flags
& EDGE_CROSSING
);
1369 if (has_crossing_succ
)
1372 if (!has_crossing_succ
)
1373 CROSSING_JUMP_P (BB_END (e
->src
)) = 0;
1378 /* Called when block BB has been reassigned to the cold partition,
1379 because it is now dominated by another cold block,
1380 to ensure that the region crossing attributes are updated. */
1383 fixup_new_cold_bb (basic_block bb
)
1388 /* This is called when a hot bb is found to now be dominated
1389 by a cold bb and therefore needs to become cold. Therefore,
1390 its preds will no longer be region crossing. Any non-dominating
1391 preds that were previously hot would also have become cold
1392 in the caller for the same region. Any preds that were previously
1393 region-crossing will be adjusted in fixup_partition_crossing. */
1394 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1396 fixup_partition_crossing (e
);
1399 /* Possibly need to make bb's successor edges region crossing,
1400 or remove stale region crossing. */
1401 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1403 /* We can't have fall-through edges across partition boundaries.
1404 Note that force_nonfallthru will do any necessary partition
1405 boundary fixup by calling fixup_partition_crossing itself. */
1406 if ((e
->flags
& EDGE_FALLTHRU
)
1407 && BB_PARTITION (bb
) != BB_PARTITION (e
->dest
)
1408 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1409 force_nonfallthru (e
);
1411 fixup_partition_crossing (e
);
1415 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1416 expense of adding new instructions or reordering basic blocks.
1418 Function can be also called with edge destination equivalent to the TARGET.
1419 Then it should try the simplifications and do nothing if none is possible.
1421 Return edge representing the branch if transformation succeeded. Return NULL
1423 We still return NULL in case E already destinated TARGET and we didn't
1424 managed to simplify instruction stream. */
1427 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
1430 basic_block src
= e
->src
;
1431 basic_block dest
= e
->dest
;
1433 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1439 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
1441 df_set_bb_dirty (src
);
1442 fixup_partition_crossing (ret
);
1446 ret
= redirect_branch_edge (e
, target
);
1450 df_set_bb_dirty (src
);
1451 fixup_partition_crossing (ret
);
1455 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1458 emit_barrier_after_bb (basic_block bb
)
1460 rtx_barrier
*barrier
= emit_barrier_after (BB_END (bb
));
1461 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1462 || current_ir_type () == IR_RTL_CFGLAYOUT
);
1463 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
1464 BB_FOOTER (bb
) = unlink_insn_chain (barrier
, barrier
);
1467 /* Like force_nonfallthru below, but additionally performs redirection
1468 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1469 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1470 simple_return_rtx, indicating which kind of returnjump to create.
1471 It should be NULL otherwise. */
1474 force_nonfallthru_and_redirect (edge e
, basic_block target
, rtx jump_label
)
1476 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
1479 int abnormal_edge_flags
= 0;
1480 bool asm_goto_edge
= false;
1483 /* In the case the last instruction is conditional jump to the next
1484 instruction, first redirect the jump itself and then continue
1485 by creating a basic block afterwards to redirect fallthru edge. */
1486 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1487 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1488 && any_condjump_p (BB_END (e
->src
))
1489 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1492 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1495 redirected
= redirect_jump (BB_END (e
->src
), block_label (target
), 0);
1496 gcc_assert (redirected
);
1498 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1501 int prob
= XINT (note
, 0);
1503 b
->probability
= prob
;
1504 /* Update this to use GCOV_COMPUTE_SCALE. */
1505 b
->count
= e
->count
* prob
/ REG_BR_PROB_BASE
;
1506 e
->probability
-= e
->probability
;
1507 e
->count
-= b
->count
;
1508 if (e
->probability
< 0)
1515 if (e
->flags
& EDGE_ABNORMAL
)
1517 /* Irritating special case - fallthru edge to the same block as abnormal
1519 We can't redirect abnormal edge, but we still can split the fallthru
1520 one and create separate abnormal edge to original destination.
1521 This allows bb-reorder to make such edge non-fallthru. */
1522 gcc_assert (e
->dest
== target
);
1523 abnormal_edge_flags
= e
->flags
& ~EDGE_FALLTHRU
;
1524 e
->flags
&= EDGE_FALLTHRU
;
1528 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1529 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1531 /* We can't redirect the entry block. Create an empty block
1532 at the start of the function which we use to add the new
1538 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
,
1539 ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1541 /* Change the existing edge's source to be the new block, and add
1542 a new edge from the entry block to the new block. */
1544 for (ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
1545 (tmp
= ei_safe_edge (ei
)); )
1549 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
->unordered_remove (ei
.index
);
1559 vec_safe_push (bb
->succs
, e
);
1560 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
,
1565 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1566 don't point to the target or fallthru label. */
1567 if (JUMP_P (BB_END (e
->src
))
1568 && target
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1569 && (e
->flags
& EDGE_FALLTHRU
)
1570 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
1572 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
1573 bool adjust_jump_target
= false;
1575 for (i
= 0; i
< n
; ++i
)
1577 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (e
->dest
))
1579 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))--;
1580 XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) = block_label (target
);
1581 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))++;
1582 adjust_jump_target
= true;
1584 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (target
))
1585 asm_goto_edge
= true;
1587 if (adjust_jump_target
)
1589 rtx_insn
*insn
= BB_END (e
->src
);
1591 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1592 rtx_insn
*new_label
= BB_HEAD (target
);
1594 if (JUMP_LABEL (insn
) == old_label
)
1596 JUMP_LABEL (insn
) = new_label
;
1597 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1599 remove_note (insn
, note
);
1603 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1605 remove_note (insn
, note
);
1606 if (JUMP_LABEL (insn
) != new_label
1607 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1608 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1610 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1612 XEXP (note
, 0) = new_label
;
1616 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
|| asm_goto_edge
)
1619 gcov_type count
= e
->count
;
1620 int probability
= e
->probability
;
1621 /* Create the new structures. */
1623 /* If the old block ended with a tablejump, skip its table
1624 by searching forward from there. Otherwise start searching
1625 forward from the last instruction of the old block. */
1626 rtx_jump_table_data
*table
;
1627 if (tablejump_p (BB_END (e
->src
), NULL
, &table
))
1630 new_head
= BB_END (e
->src
);
1631 new_head
= NEXT_INSN (new_head
);
1633 jump_block
= create_basic_block (new_head
, NULL
, e
->src
);
1634 jump_block
->count
= count
;
1635 jump_block
->frequency
= EDGE_FREQUENCY (e
);
1637 /* Make sure new block ends up in correct hot/cold section. */
1639 BB_COPY_PARTITION (jump_block
, e
->src
);
1642 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1643 new_edge
->probability
= probability
;
1644 new_edge
->count
= count
;
1646 /* Redirect old edge. */
1647 redirect_edge_pred (e
, jump_block
);
1648 e
->probability
= REG_BR_PROB_BASE
;
1650 /* If e->src was previously region crossing, it no longer is
1651 and the reg crossing note should be removed. */
1652 fixup_partition_crossing (new_edge
);
1654 /* If asm goto has any label refs to target's label,
1655 add also edge from asm goto bb to target. */
1658 new_edge
->probability
/= 2;
1659 new_edge
->count
/= 2;
1660 jump_block
->count
/= 2;
1661 jump_block
->frequency
/= 2;
1662 new_edge
= make_edge (new_edge
->src
, target
,
1663 e
->flags
& ~EDGE_FALLTHRU
);
1664 new_edge
->probability
= probability
- probability
/ 2;
1665 new_edge
->count
= count
- count
/ 2;
1668 new_bb
= jump_block
;
1671 jump_block
= e
->src
;
1673 loc
= e
->goto_locus
;
1674 e
->flags
&= ~EDGE_FALLTHRU
;
1675 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1677 if (jump_label
== ret_rtx
)
1680 emit_jump_insn_after_setloc (gen_return (), BB_END (jump_block
), loc
);
1687 gcc_assert (jump_label
== simple_return_rtx
);
1688 #ifdef HAVE_simple_return
1689 emit_jump_insn_after_setloc (gen_simple_return (),
1690 BB_END (jump_block
), loc
);
1695 set_return_jump_label (BB_END (jump_block
));
1699 rtx label
= block_label (target
);
1700 emit_jump_insn_after_setloc (gen_jump (label
), BB_END (jump_block
), loc
);
1701 JUMP_LABEL (BB_END (jump_block
)) = label
;
1702 LABEL_NUSES (label
)++;
1705 /* We might be in cfg layout mode, and if so, the following routine will
1706 insert the barrier correctly. */
1707 emit_barrier_after_bb (jump_block
);
1708 redirect_edge_succ_nodup (e
, target
);
1710 if (abnormal_edge_flags
)
1711 make_edge (src
, target
, abnormal_edge_flags
);
1713 df_mark_solutions_dirty ();
1714 fixup_partition_crossing (e
);
1718 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1719 (and possibly create new basic block) to make edge non-fallthru.
1720 Return newly created BB or NULL if none. */
1723 rtl_force_nonfallthru (edge e
)
1725 return force_nonfallthru_and_redirect (e
, e
->dest
, NULL_RTX
);
1728 /* Redirect edge even at the expense of creating new jump insn or
1729 basic block. Return new basic block if created, NULL otherwise.
1730 Conversion must be possible. */
1733 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1735 if (redirect_edge_and_branch (e
, target
)
1736 || e
->dest
== target
)
1739 /* In case the edge redirection failed, try to force it to be non-fallthru
1740 and redirect newly created simplejump. */
1741 df_set_bb_dirty (e
->src
);
1742 return force_nonfallthru_and_redirect (e
, target
, NULL_RTX
);
1745 /* The given edge should potentially be a fallthru edge. If that is in
1746 fact true, delete the jump and barriers that are in the way. */
1749 rtl_tidy_fallthru_edge (edge e
)
1752 basic_block b
= e
->src
, c
= b
->next_bb
;
1754 /* ??? In a late-running flow pass, other folks may have deleted basic
1755 blocks by nopping out blocks, leaving multiple BARRIERs between here
1756 and the target label. They ought to be chastised and fixed.
1758 We can also wind up with a sequence of undeletable labels between
1759 one block and the next.
1761 So search through a sequence of barriers, labels, and notes for
1762 the head of block C and assert that we really do fall through. */
1764 for (q
= NEXT_INSN (BB_END (b
)); q
!= BB_HEAD (c
); q
= NEXT_INSN (q
))
1768 /* Remove what will soon cease being the jump insn from the source block.
1769 If block B consisted only of this single jump, turn it into a deleted
1774 && (any_uncondjump_p (q
)
1775 || single_succ_p (b
)))
1778 /* If this was a conditional jump, we need to also delete
1779 the insn that set cc0. */
1780 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1787 /* Selectively unlink the sequence. */
1788 if (q
!= PREV_INSN (BB_HEAD (c
)))
1789 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1791 e
->flags
|= EDGE_FALLTHRU
;
1794 /* Should move basic block BB after basic block AFTER. NIY. */
1797 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1798 basic_block after ATTRIBUTE_UNUSED
)
1803 /* Locate the last bb in the same partition as START_BB. */
1806 last_bb_in_partition (basic_block start_bb
)
1809 FOR_BB_BETWEEN (bb
, start_bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1811 if (BB_PARTITION (start_bb
) != BB_PARTITION (bb
->next_bb
))
1814 /* Return bb before the exit block. */
1818 /* Split a (typically critical) edge. Return the new block.
1819 The edge must not be abnormal.
1821 ??? The code generally expects to be called on critical edges.
1822 The case of a block ending in an unconditional jump to a
1823 block with multiple predecessors is not handled optimally. */
1826 rtl_split_edge (edge edge_in
)
1828 basic_block bb
, new_bb
;
1831 /* Abnormal edges cannot be split. */
1832 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1834 /* We are going to place the new block in front of edge destination.
1835 Avoid existence of fallthru predecessors. */
1836 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1838 edge e
= find_fallthru_edge (edge_in
->dest
->preds
);
1841 force_nonfallthru (e
);
1844 /* Create the basic block note. */
1845 if (edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1846 before
= BB_HEAD (edge_in
->dest
);
1850 /* If this is a fall through edge to the exit block, the blocks might be
1851 not adjacent, and the right place is after the source. */
1852 if ((edge_in
->flags
& EDGE_FALLTHRU
)
1853 && edge_in
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1855 before
= NEXT_INSN (BB_END (edge_in
->src
));
1856 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1857 BB_COPY_PARTITION (bb
, edge_in
->src
);
1861 if (edge_in
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1863 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1864 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1868 basic_block after
= edge_in
->dest
->prev_bb
;
1869 /* If this is post-bb reordering, and the edge crosses a partition
1870 boundary, the new block needs to be inserted in the bb chain
1871 at the end of the src partition (since we put the new bb into
1872 that partition, see below). Otherwise we may end up creating
1873 an extra partition crossing in the chain, which is illegal.
1874 It can't go after the src, because src may have a fall-through
1875 to a different block. */
1876 if (crtl
->bb_reorder_complete
1877 && (edge_in
->flags
& EDGE_CROSSING
))
1879 after
= last_bb_in_partition (edge_in
->src
);
1880 before
= NEXT_INSN (BB_END (after
));
1881 /* The instruction following the last bb in partition should
1882 be a barrier, since it cannot end in a fall-through. */
1883 gcc_checking_assert (BARRIER_P (before
));
1884 before
= NEXT_INSN (before
);
1886 bb
= create_basic_block (before
, NULL
, after
);
1887 /* Put the split bb into the src partition, to avoid creating
1888 a situation where a cold bb dominates a hot bb, in the case
1889 where src is cold and dest is hot. The src will dominate
1890 the new bb (whereas it might not have dominated dest). */
1891 BB_COPY_PARTITION (bb
, edge_in
->src
);
1895 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1897 /* Can't allow a region crossing edge to be fallthrough. */
1898 if (BB_PARTITION (bb
) != BB_PARTITION (edge_in
->dest
)
1899 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1901 new_bb
= force_nonfallthru (single_succ_edge (bb
));
1902 gcc_assert (!new_bb
);
1905 /* For non-fallthru edges, we must adjust the predecessor's
1906 jump instruction to target our new block. */
1907 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1909 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1910 gcc_assert (redirected
);
1914 if (edge_in
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1916 /* For asm goto even splitting of fallthru edge might
1917 need insn patching, as other labels might point to the
1919 rtx_insn
*last
= BB_END (edge_in
->src
);
1922 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1923 && extract_asm_operands (PATTERN (last
)) != NULL_RTX
1924 && patch_jump_insn (last
, before
, bb
))
1925 df_set_bb_dirty (edge_in
->src
);
1927 redirect_edge_succ (edge_in
, bb
);
1933 /* Queue instructions for insertion on an edge between two basic blocks.
1934 The new instructions and basic blocks (if any) will not appear in the
1935 CFG until commit_edge_insertions is called. */
1938 insert_insn_on_edge (rtx pattern
, edge e
)
1940 /* We cannot insert instructions on an abnormal critical edge.
1941 It will be easier to find the culprit if we die now. */
1942 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1944 if (e
->insns
.r
== NULL_RTX
)
1947 push_to_sequence (e
->insns
.r
);
1949 emit_insn (pattern
);
1951 e
->insns
.r
= get_insns ();
1955 /* Update the CFG for the instructions queued on edge E. */
1958 commit_one_edge_insertion (edge e
)
1960 rtx_insn
*before
= NULL
, *after
= NULL
, *insns
, *tmp
, *last
;
1963 /* Pull the insns off the edge now since the edge might go away. */
1967 /* Figure out where to put these insns. If the destination has
1968 one predecessor, insert there. Except for the exit block. */
1969 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1973 /* Get the location correct wrt a code label, and "nice" wrt
1974 a basic block note, and before everything else. */
1977 tmp
= NEXT_INSN (tmp
);
1978 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1979 tmp
= NEXT_INSN (tmp
);
1980 if (tmp
== BB_HEAD (bb
))
1983 after
= PREV_INSN (tmp
);
1985 after
= get_last_insn ();
1988 /* If the source has one successor and the edge is not abnormal,
1989 insert there. Except for the entry block.
1990 Don't do this if the predecessor ends in a jump other than
1991 unconditional simple jump. E.g. for asm goto that points all
1992 its labels at the fallthru basic block, we can't insert instructions
1993 before the asm goto, as the asm goto can have various of side effects,
1994 and can't emit instructions after the asm goto, as it must end
1996 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1997 && single_succ_p (e
->src
)
1998 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1999 && (!JUMP_P (BB_END (e
->src
))
2000 || simplejump_p (BB_END (e
->src
))))
2004 /* It is possible to have a non-simple jump here. Consider a target
2005 where some forms of unconditional jumps clobber a register. This
2006 happens on the fr30 for example.
2008 We know this block has a single successor, so we can just emit
2009 the queued insns before the jump. */
2010 if (JUMP_P (BB_END (bb
)))
2011 before
= BB_END (bb
);
2014 /* We'd better be fallthru, or we've lost track of what's what. */
2015 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
2017 after
= BB_END (bb
);
2021 /* Otherwise we must split the edge. */
2024 bb
= split_edge (e
);
2026 /* If E crossed a partition boundary, we needed to make bb end in
2027 a region-crossing jump, even though it was originally fallthru. */
2028 if (JUMP_P (BB_END (bb
)))
2029 before
= BB_END (bb
);
2031 after
= BB_END (bb
);
2034 /* Now that we've found the spot, do the insertion. */
2037 emit_insn_before_noloc (insns
, before
, bb
);
2038 last
= prev_nonnote_insn (before
);
2041 last
= emit_insn_after_noloc (insns
, after
, bb
);
2043 if (returnjump_p (last
))
2045 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2046 This is not currently a problem because this only happens
2047 for the (single) epilogue, which already has a fallthru edge
2050 e
= single_succ_edge (bb
);
2051 gcc_assert (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2052 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
2054 e
->flags
&= ~EDGE_FALLTHRU
;
2055 emit_barrier_after (last
);
2058 delete_insn (before
);
2061 gcc_assert (!JUMP_P (last
));
2064 /* Update the CFG for all queued instructions. */
2067 commit_edge_insertions (void)
2071 /* Optimization passes that invoke this routine can cause hot blocks
2072 previously reached by both hot and cold blocks to become dominated only
2073 by cold blocks. This will cause the verification below to fail,
2074 and lead to now cold code in the hot section. In some cases this
2075 may only be visible after newly unreachable blocks are deleted,
2076 which will be done by fixup_partitions. */
2077 fixup_partitions ();
2079 #ifdef ENABLE_CHECKING
2080 verify_flow_info ();
2083 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
2084 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
2089 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2091 commit_one_edge_insertion (e
);
2096 /* Print out RTL-specific basic block information (live information
2097 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2098 documented in dumpfile.h. */
2101 rtl_dump_bb (FILE *outf
, basic_block bb
, int indent
, int flags
)
2107 s_indent
= (char *) alloca ((size_t) indent
+ 1);
2108 memset (s_indent
, ' ', (size_t) indent
);
2109 s_indent
[indent
] = '\0';
2111 if (df
&& (flags
& TDF_DETAILS
))
2113 df_dump_top (bb
, outf
);
2117 if (bb
->index
!= ENTRY_BLOCK
&& bb
->index
!= EXIT_BLOCK
)
2118 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
)); insn
!= last
;
2119 insn
= NEXT_INSN (insn
))
2121 if (flags
& TDF_DETAILS
)
2122 df_dump_insn_top (insn
, outf
);
2123 if (! (flags
& TDF_SLIM
))
2124 print_rtl_single (outf
, insn
);
2126 dump_insn_slim (outf
, insn
);
2127 if (flags
& TDF_DETAILS
)
2128 df_dump_insn_bottom (insn
, outf
);
2131 if (df
&& (flags
& TDF_DETAILS
))
2133 df_dump_bottom (bb
, outf
);
2139 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2140 for the start of each basic block. FLAGS are the TDF_* masks documented
2144 print_rtl_with_bb (FILE *outf
, const rtx_insn
*rtx_first
, int flags
)
2146 const rtx_insn
*tmp_rtx
;
2148 fprintf (outf
, "(nil)\n");
2151 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
2152 int max_uid
= get_max_uid ();
2153 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
2154 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
2155 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
2158 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2159 insns, but the CFG is not maintained so the basic block info
2160 is not reliable. Therefore it's omitted from the dumps. */
2161 if (! (cfun
->curr_properties
& PROP_cfg
))
2162 flags
&= ~TDF_BLOCKS
;
2165 df_dump_start (outf
);
2167 if (flags
& TDF_BLOCKS
)
2169 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2173 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
2174 end
[INSN_UID (BB_END (bb
))] = bb
;
2175 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
2177 enum bb_state state
= IN_MULTIPLE_BB
;
2179 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
2181 in_bb_p
[INSN_UID (x
)] = state
;
2183 if (x
== BB_END (bb
))
2189 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
2191 if (flags
& TDF_BLOCKS
)
2193 bb
= start
[INSN_UID (tmp_rtx
)];
2196 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, true, false);
2197 if (df
&& (flags
& TDF_DETAILS
))
2198 df_dump_top (bb
, outf
);
2201 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
2202 && !NOTE_P (tmp_rtx
)
2203 && !BARRIER_P (tmp_rtx
))
2204 fprintf (outf
, ";; Insn is not within a basic block\n");
2205 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
2206 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
2209 if (flags
& TDF_DETAILS
)
2210 df_dump_insn_top (tmp_rtx
, outf
);
2211 if (! (flags
& TDF_SLIM
))
2212 print_rtl_single (outf
, tmp_rtx
);
2214 dump_insn_slim (outf
, tmp_rtx
);
2215 if (flags
& TDF_DETAILS
)
2216 df_dump_insn_bottom (tmp_rtx
, outf
);
2218 if (flags
& TDF_BLOCKS
)
2220 bb
= end
[INSN_UID (tmp_rtx
)];
2223 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, false, true);
2224 if (df
&& (flags
& TDF_DETAILS
))
2225 df_dump_bottom (bb
, outf
);
2237 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2240 update_br_prob_note (basic_block bb
)
2243 if (!JUMP_P (BB_END (bb
)))
2245 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
2246 if (!note
|| XINT (note
, 0) == BRANCH_EDGE (bb
)->probability
)
2248 XINT (note
, 0) = BRANCH_EDGE (bb
)->probability
;
2251 /* Get the last insn associated with block BB (that includes barriers and
2252 tablejumps after BB). */
2254 get_last_bb_insn (basic_block bb
)
2256 rtx_jump_table_data
*table
;
2258 rtx_insn
*end
= BB_END (bb
);
2260 /* Include any jump table following the basic block. */
2261 if (tablejump_p (end
, NULL
, &table
))
2264 /* Include any barriers that may follow the basic block. */
2265 tmp
= next_nonnote_insn_bb (end
);
2266 while (tmp
&& BARRIER_P (tmp
))
2269 tmp
= next_nonnote_insn_bb (end
);
2275 /* Sanity check partition hotness to ensure that basic blocks in
2276 Â the cold partition don't dominate basic blocks in the hot partition.
2277 If FLAG_ONLY is true, report violations as errors. Otherwise
2278 re-mark the dominated blocks as cold, since this is run after
2279 cfg optimizations that may make hot blocks previously reached
2280 by both hot and cold blocks now only reachable along cold paths. */
2282 static vec
<basic_block
>
2283 find_partition_fixes (bool flag_only
)
2286 vec
<basic_block
> bbs_in_cold_partition
= vNULL
;
2287 vec
<basic_block
> bbs_to_fix
= vNULL
;
2289 /* Callers check this. */
2290 gcc_checking_assert (crtl
->has_bb_partition
);
2292 FOR_EACH_BB_FN (bb
, cfun
)
2293 if ((BB_PARTITION (bb
) == BB_COLD_PARTITION
))
2294 bbs_in_cold_partition
.safe_push (bb
);
2296 if (bbs_in_cold_partition
.is_empty ())
2299 bool dom_calculated_here
= !dom_info_available_p (CDI_DOMINATORS
);
2301 if (dom_calculated_here
)
2302 calculate_dominance_info (CDI_DOMINATORS
);
2304 while (! bbs_in_cold_partition
.is_empty ())
2306 bb
= bbs_in_cold_partition
.pop ();
2307 /* Any blocks dominated by a block in the cold section
2308 must also be cold. */
2310 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2312 son
= next_dom_son (CDI_DOMINATORS
, son
))
2314 /* If son is not yet cold, then mark it cold here and
2315 enqueue it for further processing. */
2316 if ((BB_PARTITION (son
) != BB_COLD_PARTITION
))
2319 error ("non-cold basic block %d dominated "
2320 "by a block in the cold partition (%d)", son
->index
, bb
->index
);
2322 BB_SET_PARTITION (son
, BB_COLD_PARTITION
);
2323 bbs_to_fix
.safe_push (son
);
2324 bbs_in_cold_partition
.safe_push (son
);
2329 if (dom_calculated_here
)
2330 free_dominance_info (CDI_DOMINATORS
);
2335 /* Perform cleanup on the hot/cold bb partitioning after optimization
2336 passes that modify the cfg. */
2339 fixup_partitions (void)
2343 if (!crtl
->has_bb_partition
)
2346 /* Delete any blocks that became unreachable and weren't
2347 already cleaned up, for example during edge forwarding
2348 and convert_jumps_to_returns. This will expose more
2349 opportunities for fixing the partition boundaries here.
2350 Also, the calculation of the dominance graph during verification
2351 will assert if there are unreachable nodes. */
2352 delete_unreachable_blocks ();
2354 /* If there are partitions, do a sanity check on them: A basic block in
2355 Â a cold partition cannot dominate a basic block in a hot partition.
2356 Fixup any that now violate this requirement, as a result of edge
2357 forwarding and unreachable block deletion. Â */
2358 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (false);
2360 /* Do the partition fixup after all necessary blocks have been converted to
2361 cold, so that we only update the region crossings the minimum number of
2362 places, which can require forcing edges to be non fallthru. */
2363 while (! bbs_to_fix
.is_empty ())
2365 bb
= bbs_to_fix
.pop ();
2366 fixup_new_cold_bb (bb
);
2370 /* Verify, in the basic block chain, that there is at most one switch
2371 between hot/cold partitions. This condition will not be true until
2372 after reorder_basic_blocks is called. */
2375 verify_hot_cold_block_grouping (void)
2379 bool switched_sections
= false;
2380 int current_partition
= BB_UNPARTITIONED
;
2382 /* Even after bb reordering is complete, we go into cfglayout mode
2383 again (in compgoto). Ensure we don't call this before going back
2384 into linearized RTL when any layout fixes would have been committed. */
2385 if (!crtl
->bb_reorder_complete
2386 || current_ir_type () != IR_RTL_CFGRTL
)
2389 FOR_EACH_BB_FN (bb
, cfun
)
2391 if (current_partition
!= BB_UNPARTITIONED
2392 && BB_PARTITION (bb
) != current_partition
)
2394 if (switched_sections
)
2396 error ("multiple hot/cold transitions found (bb %i)",
2401 switched_sections
= true;
2403 if (!crtl
->has_bb_partition
)
2404 error ("partition found but function partition flag not set");
2406 current_partition
= BB_PARTITION (bb
);
2413 /* Perform several checks on the edges out of each block, such as
2414 the consistency of the branch probabilities, the correctness
2415 of hot/cold partition crossing edges, and the number of expected
2416 successor edges. Also verify that the dominance relationship
2417 between hot/cold blocks is sane. */
2420 rtl_verify_edges (void)
2425 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2427 int n_fallthru
= 0, n_branch
= 0, n_abnormal_call
= 0, n_sibcall
= 0;
2428 int n_eh
= 0, n_abnormal
= 0;
2429 edge e
, fallthru
= NULL
;
2432 bool has_crossing_edge
= false;
2434 if (JUMP_P (BB_END (bb
))
2435 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
2436 && EDGE_COUNT (bb
->succs
) >= 2
2437 && any_condjump_p (BB_END (bb
)))
2439 if (XINT (note
, 0) != BRANCH_EDGE (bb
)->probability
2440 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2442 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2443 XINT (note
, 0), BRANCH_EDGE (bb
)->probability
);
2448 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2452 if (e
->flags
& EDGE_FALLTHRU
)
2453 n_fallthru
++, fallthru
= e
;
2455 is_crossing
= (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
2456 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2457 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
2458 has_crossing_edge
|= is_crossing
;
2459 if (e
->flags
& EDGE_CROSSING
)
2463 error ("EDGE_CROSSING incorrectly set across same section");
2466 if (e
->flags
& EDGE_FALLTHRU
)
2468 error ("fallthru edge crosses section boundary in bb %i",
2472 if (e
->flags
& EDGE_EH
)
2474 error ("EH edge crosses section boundary in bb %i",
2478 if (JUMP_P (BB_END (bb
)) && !CROSSING_JUMP_P (BB_END (bb
)))
2480 error ("No region crossing jump at section boundary in bb %i",
2485 else if (is_crossing
)
2487 error ("EDGE_CROSSING missing across section boundary");
2491 if ((e
->flags
& ~(EDGE_DFS_BACK
2493 | EDGE_IRREDUCIBLE_LOOP
2496 | EDGE_PRESERVE
)) == 0)
2499 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2502 if (e
->flags
& EDGE_SIBCALL
)
2505 if (e
->flags
& EDGE_EH
)
2508 if (e
->flags
& EDGE_ABNORMAL
)
2512 if (!has_crossing_edge
2513 && JUMP_P (BB_END (bb
))
2514 && CROSSING_JUMP_P (BB_END (bb
)))
2516 print_rtl_with_bb (stderr
, get_insns (), TDF_RTL
| TDF_BLOCKS
| TDF_DETAILS
);
2517 error ("Region crossing jump across same section in bb %i",
2522 if (n_eh
&& !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
2524 error ("missing REG_EH_REGION note at the end of bb %i", bb
->index
);
2529 error ("too many exception handling edges in bb %i", bb
->index
);
2533 && (!JUMP_P (BB_END (bb
))
2534 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
2535 || any_condjump_p (BB_END (bb
))))))
2537 error ("too many outgoing branch edges from bb %i", bb
->index
);
2540 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
2542 error ("fallthru edge after unconditional jump in bb %i", bb
->index
);
2545 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
2547 error ("wrong number of branch edges after unconditional jump"
2548 " in bb %i", bb
->index
);
2551 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
2552 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
2554 error ("wrong amount of branch edges after conditional jump"
2555 " in bb %i", bb
->index
);
2558 if (n_abnormal_call
&& !CALL_P (BB_END (bb
)))
2560 error ("abnormal call edges for non-call insn in bb %i", bb
->index
);
2563 if (n_sibcall
&& !CALL_P (BB_END (bb
)))
2565 error ("sibcall edges for non-call insn in bb %i", bb
->index
);
2568 if (n_abnormal
> n_eh
2569 && !(CALL_P (BB_END (bb
))
2570 && n_abnormal
== n_abnormal_call
+ n_sibcall
)
2571 && (!JUMP_P (BB_END (bb
))
2572 || any_condjump_p (BB_END (bb
))
2573 || any_uncondjump_p (BB_END (bb
))))
2575 error ("abnormal edges for no purpose in bb %i", bb
->index
);
2580 /* If there are partitions, do a sanity check on them: A basic block in
2581 Â a cold partition cannot dominate a basic block in a hot partition. Â */
2582 if (crtl
->has_bb_partition
&& !err
)
2584 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (true);
2585 err
= !bbs_to_fix
.is_empty ();
2592 /* Checks on the instructions within blocks. Currently checks that each
2593 block starts with a basic block note, and that basic block notes and
2594 control flow jumps are not found in the middle of the block. */
2597 rtl_verify_bb_insns (void)
2603 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2605 /* Now check the header of basic
2606 block. It ought to contain optional CODE_LABEL followed
2607 by NOTE_BASIC_BLOCK. */
2611 if (BB_END (bb
) == x
)
2613 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2621 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2623 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2628 if (BB_END (bb
) == x
)
2629 /* Do checks for empty blocks here. */
2632 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2634 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2636 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2637 INSN_UID (x
), bb
->index
);
2641 if (x
== BB_END (bb
))
2644 if (control_flow_insn_p (x
))
2646 error ("in basic block %d:", bb
->index
);
2647 fatal_insn ("flow control insn inside a basic block", x
);
2656 /* Verify that block pointers for instructions in basic blocks, headers and
2657 footers are set appropriately. */
2660 rtl_verify_bb_pointers (void)
2665 /* Check the general integrity of the basic blocks. */
2666 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2670 if (!(bb
->flags
& BB_RTL
))
2672 error ("BB_RTL flag not set for block %d", bb
->index
);
2676 FOR_BB_INSNS (bb
, insn
)
2677 if (BLOCK_FOR_INSN (insn
) != bb
)
2679 error ("insn %d basic block pointer is %d, should be %d",
2681 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
2686 for (insn
= BB_HEADER (bb
); insn
; insn
= NEXT_INSN (insn
))
2687 if (!BARRIER_P (insn
)
2688 && BLOCK_FOR_INSN (insn
) != NULL
)
2690 error ("insn %d in header of bb %d has non-NULL basic block",
2691 INSN_UID (insn
), bb
->index
);
2694 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
2695 if (!BARRIER_P (insn
)
2696 && BLOCK_FOR_INSN (insn
) != NULL
)
2698 error ("insn %d in footer of bb %d has non-NULL basic block",
2699 INSN_UID (insn
), bb
->index
);
2708 /* Verify the CFG and RTL consistency common for both underlying RTL and
2711 Currently it does following checks:
2713 - overlapping of basic blocks
2714 - insns with wrong BLOCK_FOR_INSN pointers
2715 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2716 - tails of basic blocks (ensure that boundary is necessary)
2717 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2718 and NOTE_INSN_BASIC_BLOCK
2719 - verify that no fall_thru edge crosses hot/cold partition boundaries
2720 - verify that there are no pending RTL branch predictions
2721 - verify that hot blocks are not dominated by cold blocks
2723 In future it can be extended check a lot of other stuff as well
2724 (reachability of basic blocks, life information, etc. etc.). */
2727 rtl_verify_flow_info_1 (void)
2731 err
|= rtl_verify_bb_pointers ();
2733 err
|= rtl_verify_bb_insns ();
2735 err
|= rtl_verify_edges ();
2740 /* Walk the instruction chain and verify that bb head/end pointers
2741 are correct, and that instructions are in exactly one bb and have
2742 correct block pointers. */
2745 rtl_verify_bb_insn_chain (void)
2750 rtx_insn
*last_head
= get_last_insn ();
2751 basic_block
*bb_info
;
2752 const int max_uid
= get_max_uid ();
2754 bb_info
= XCNEWVEC (basic_block
, max_uid
);
2756 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2758 rtx_insn
*head
= BB_HEAD (bb
);
2759 rtx_insn
*end
= BB_END (bb
);
2761 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2763 /* Verify the end of the basic block is in the INSN chain. */
2767 /* And that the code outside of basic blocks has NULL bb field. */
2769 && BLOCK_FOR_INSN (x
) != NULL
)
2771 error ("insn %d outside of basic blocks has non-NULL bb field",
2779 error ("end insn %d for block %d not found in the insn stream",
2780 INSN_UID (end
), bb
->index
);
2784 /* Work backwards from the end to the head of the basic block
2785 to verify the head is in the RTL chain. */
2786 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2788 /* While walking over the insn chain, verify insns appear
2789 in only one basic block. */
2790 if (bb_info
[INSN_UID (x
)] != NULL
)
2792 error ("insn %d is in multiple basic blocks (%d and %d)",
2793 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2797 bb_info
[INSN_UID (x
)] = bb
;
2804 error ("head insn %d for block %d not found in the insn stream",
2805 INSN_UID (head
), bb
->index
);
2809 last_head
= PREV_INSN (x
);
2812 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2814 /* Check that the code before the first basic block has NULL
2817 && BLOCK_FOR_INSN (x
) != NULL
)
2819 error ("insn %d outside of basic blocks has non-NULL bb field",
2829 /* Verify that fallthru edges point to adjacent blocks in layout order and
2830 that barriers exist after non-fallthru blocks. */
2833 rtl_verify_fallthru (void)
2838 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2842 e
= find_fallthru_edge (bb
->succs
);
2847 /* Ensure existence of barrier in BB with no fallthru edges. */
2848 for (insn
= NEXT_INSN (BB_END (bb
)); ; insn
= NEXT_INSN (insn
))
2850 if (!insn
|| NOTE_INSN_BASIC_BLOCK_P (insn
))
2852 error ("missing barrier after block %i", bb
->index
);
2856 if (BARRIER_P (insn
))
2860 else if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2861 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2865 if (e
->src
->next_bb
!= e
->dest
)
2868 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2869 e
->src
->index
, e
->dest
->index
);
2873 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
2874 insn
= NEXT_INSN (insn
))
2875 if (BARRIER_P (insn
) || INSN_P (insn
))
2877 error ("verify_flow_info: Incorrect fallthru %i->%i",
2878 e
->src
->index
, e
->dest
->index
);
2879 fatal_insn ("wrong insn in the fallthru edge", insn
);
2888 /* Verify that blocks are laid out in consecutive order. While walking the
2889 instructions, verify that all expected instructions are inside the basic
2890 blocks, and that all returns are followed by barriers. */
2893 rtl_verify_bb_layout (void)
2899 rtx_insn
* const rtx_first
= get_insns ();
2900 basic_block last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
), curr_bb
= NULL
;
2903 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
2905 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2907 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2909 bb
= NOTE_BASIC_BLOCK (x
);
2912 if (bb
!= last_bb_seen
->next_bb
)
2913 internal_error ("basic blocks not laid down consecutively");
2915 curr_bb
= last_bb_seen
= bb
;
2920 switch (GET_CODE (x
))
2927 /* An ADDR_VEC is placed outside any basic block. */
2929 && JUMP_TABLE_DATA_P (NEXT_INSN (x
)))
2932 /* But in any case, non-deletable labels can appear anywhere. */
2936 fatal_insn ("insn outside basic block", x
);
2941 && returnjump_p (x
) && ! condjump_p (x
)
2942 && ! (next_nonnote_insn (x
) && BARRIER_P (next_nonnote_insn (x
))))
2943 fatal_insn ("return not followed by barrier", x
);
2945 if (curr_bb
&& x
== BB_END (curr_bb
))
2949 if (num_bb_notes
!= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
)
2951 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2952 num_bb_notes
, n_basic_blocks_for_fn (cfun
));
2957 /* Verify the CFG and RTL consistency common for both underlying RTL and
2958 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
2960 Currently it does following checks:
2961 - all checks of rtl_verify_flow_info_1
2962 - test head/end pointers
2963 - check that blocks are laid out in consecutive order
2964 - check that all insns are in the basic blocks
2965 (except the switch handling code, barriers and notes)
2966 - check that all returns are followed by barriers
2967 - check that all fallthru edge points to the adjacent blocks
2968 - verify that there is a single hot/cold partition boundary after bbro */
2971 rtl_verify_flow_info (void)
2975 err
|= rtl_verify_flow_info_1 ();
2977 err
|= rtl_verify_bb_insn_chain ();
2979 err
|= rtl_verify_fallthru ();
2981 err
|= rtl_verify_bb_layout ();
2983 err
|= verify_hot_cold_block_grouping ();
2988 /* Assume that the preceding pass has possibly eliminated jump instructions
2989 or converted the unconditional jumps. Eliminate the edges from CFG.
2990 Return true if any edges are eliminated. */
2993 purge_dead_edges (basic_block bb
)
2996 rtx_insn
*insn
= BB_END (bb
);
2998 bool purged
= false;
3002 if (DEBUG_INSN_P (insn
) && insn
!= BB_HEAD (bb
))
3004 insn
= PREV_INSN (insn
);
3005 while ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
));
3007 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3008 if (NONJUMP_INSN_P (insn
)
3009 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
3013 if (! may_trap_p (PATTERN (insn
))
3014 || ((eqnote
= find_reg_equal_equiv_note (insn
))
3015 && ! may_trap_p (XEXP (eqnote
, 0))))
3016 remove_note (insn
, note
);
3019 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3020 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3022 bool remove
= false;
3024 /* There are three types of edges we need to handle correctly here: EH
3025 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3026 latter can appear when nonlocal gotos are used. */
3027 if (e
->flags
& EDGE_ABNORMAL_CALL
)
3031 else if (can_nonlocal_goto (insn
))
3033 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3035 else if (flag_tm
&& find_reg_note (insn
, REG_TM
, NULL
))
3040 else if (e
->flags
& EDGE_EH
)
3041 remove
= !can_throw_internal (insn
);
3046 df_set_bb_dirty (bb
);
3059 /* We do care only about conditional jumps and simplejumps. */
3060 if (!any_condjump_p (insn
)
3061 && !returnjump_p (insn
)
3062 && !simplejump_p (insn
))
3065 /* Branch probability/prediction notes are defined only for
3066 condjumps. We've possibly turned condjump into simplejump. */
3067 if (simplejump_p (insn
))
3069 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3071 remove_note (insn
, note
);
3072 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
3073 remove_note (insn
, note
);
3076 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3078 /* Avoid abnormal flags to leak from computed jumps turned
3079 into simplejumps. */
3081 e
->flags
&= ~EDGE_ABNORMAL
;
3083 /* See if this edge is one we should keep. */
3084 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
3085 /* A conditional jump can fall through into the next
3086 block, so we should keep the edge. */
3091 else if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3092 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
3093 /* If the destination block is the target of the jump,
3099 else if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
3100 && returnjump_p (insn
))
3101 /* If the destination block is the exit block, and this
3102 instruction is a return, then keep the edge. */
3107 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3108 /* Keep the edges that correspond to exceptions thrown by
3109 this instruction and rematerialize the EDGE_ABNORMAL
3110 flag we just cleared above. */
3112 e
->flags
|= EDGE_ABNORMAL
;
3117 /* We do not need this edge. */
3118 df_set_bb_dirty (bb
);
3123 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
3127 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
3132 /* Redistribute probabilities. */
3133 if (single_succ_p (bb
))
3135 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3136 single_succ_edge (bb
)->count
= bb
->count
;
3140 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3144 b
= BRANCH_EDGE (bb
);
3145 f
= FALLTHRU_EDGE (bb
);
3146 b
->probability
= XINT (note
, 0);
3147 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
3148 /* Update these to use GCOV_COMPUTE_SCALE. */
3149 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
3150 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
3155 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
3157 /* First, there should not be any EH or ABCALL edges resulting
3158 from non-local gotos and the like. If there were, we shouldn't
3159 have created the sibcall in the first place. Second, there
3160 should of course never have been a fallthru edge. */
3161 gcc_assert (single_succ_p (bb
));
3162 gcc_assert (single_succ_edge (bb
)->flags
3163 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
3168 /* If we don't see a jump insn, we don't know exactly why the block would
3169 have been broken at this point. Look for a simple, non-fallthru edge,
3170 as these are only created by conditional branches. If we find such an
3171 edge we know that there used to be a jump here and can then safely
3172 remove all non-fallthru edges. */
3174 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3175 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
3184 /* Remove all but the fake and fallthru edges. The fake edge may be
3185 the only successor for this block in the case of noreturn
3187 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3189 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
3191 df_set_bb_dirty (bb
);
3199 gcc_assert (single_succ_p (bb
));
3201 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3202 single_succ_edge (bb
)->count
= bb
->count
;
3205 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
3210 /* Search all basic blocks for potentially dead edges and purge them. Return
3211 true if some edge has been eliminated. */
3214 purge_all_dead_edges (void)
3219 FOR_EACH_BB_FN (bb
, cfun
)
3221 bool purged_here
= purge_dead_edges (bb
);
3223 purged
|= purged_here
;
3229 /* This is used by a few passes that emit some instructions after abnormal
3230 calls, moving the basic block's end, while they in fact do want to emit
3231 them on the fallthru edge. Look for abnormal call edges, find backward
3232 the call in the block and insert the instructions on the edge instead.
3234 Similarly, handle instructions throwing exceptions internally.
3236 Return true when instructions have been found and inserted on edges. */
3239 fixup_abnormal_edges (void)
3241 bool inserted
= false;
3244 FOR_EACH_BB_FN (bb
, cfun
)
3249 /* Look for cases we are interested in - calls or instructions causing
3251 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3252 if ((e
->flags
& EDGE_ABNORMAL_CALL
)
3253 || ((e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
3254 == (EDGE_ABNORMAL
| EDGE_EH
)))
3257 if (e
&& !CALL_P (BB_END (bb
)) && !can_throw_internal (BB_END (bb
)))
3261 /* Get past the new insns generated. Allow notes, as the insns
3262 may be already deleted. */
3264 while ((NONJUMP_INSN_P (insn
) || NOTE_P (insn
))
3265 && !can_throw_internal (insn
)
3266 && insn
!= BB_HEAD (bb
))
3267 insn
= PREV_INSN (insn
);
3269 if (CALL_P (insn
) || can_throw_internal (insn
))
3271 rtx_insn
*stop
, *next
;
3273 e
= find_fallthru_edge (bb
->succs
);
3275 stop
= NEXT_INSN (BB_END (bb
));
3278 for (insn
= NEXT_INSN (insn
); insn
!= stop
; insn
= next
)
3280 next
= NEXT_INSN (insn
);
3285 /* Sometimes there's still the return value USE.
3286 If it's placed after a trapping call (i.e. that
3287 call is the last insn anyway), we have no fallthru
3288 edge. Simply delete this use and don't try to insert
3289 on the non-existent edge. */
3290 if (GET_CODE (PATTERN (insn
)) != USE
)
3292 /* We're not deleting it, we're moving it. */
3293 insn
->set_undeleted ();
3294 SET_PREV_INSN (insn
) = NULL_RTX
;
3295 SET_NEXT_INSN (insn
) = NULL_RTX
;
3297 insert_insn_on_edge (insn
, e
);
3301 else if (!BARRIER_P (insn
))
3302 set_block_for_insn (insn
, NULL
);
3306 /* It may be that we don't find any trapping insn. In this
3307 case we discovered quite late that the insn that had been
3308 marked as can_throw_internal in fact couldn't trap at all.
3309 So we should in fact delete the EH edges out of the block. */
3311 purge_dead_edges (bb
);
3318 /* Cut the insns from FIRST to LAST out of the insns stream. */
3321 unlink_insn_chain (rtx_insn
*first
, rtx_insn
*last
)
3323 rtx_insn
*prevfirst
= PREV_INSN (first
);
3324 rtx_insn
*nextlast
= NEXT_INSN (last
);
3326 SET_PREV_INSN (first
) = NULL
;
3327 SET_NEXT_INSN (last
) = NULL
;
3329 SET_NEXT_INSN (prevfirst
) = nextlast
;
3331 SET_PREV_INSN (nextlast
) = prevfirst
;
3333 set_last_insn (prevfirst
);
3335 set_first_insn (nextlast
);
3339 /* Skip over inter-block insns occurring after BB which are typically
3340 associated with BB (e.g., barriers). If there are any such insns,
3341 we return the last one. Otherwise, we return the end of BB. */
3344 skip_insns_after_block (basic_block bb
)
3346 rtx_insn
*insn
, *last_insn
, *next_head
, *prev
;
3349 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3350 next_head
= BB_HEAD (bb
->next_bb
);
3352 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
3354 if (insn
== next_head
)
3357 switch (GET_CODE (insn
))
3364 switch (NOTE_KIND (insn
))
3366 case NOTE_INSN_BLOCK_END
:
3376 if (NEXT_INSN (insn
)
3377 && JUMP_TABLE_DATA_P (NEXT_INSN (insn
)))
3379 insn
= NEXT_INSN (insn
);
3392 /* It is possible to hit contradictory sequence. For instance:
3398 Where barrier belongs to jump_insn, but the note does not. This can be
3399 created by removing the basic block originally following
3400 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3402 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
3404 prev
= PREV_INSN (insn
);
3406 switch (NOTE_KIND (insn
))
3408 case NOTE_INSN_BLOCK_END
:
3411 case NOTE_INSN_DELETED
:
3412 case NOTE_INSN_DELETED_LABEL
:
3413 case NOTE_INSN_DELETED_DEBUG_LABEL
:
3416 reorder_insns (insn
, insn
, last_insn
);
3423 /* Locate or create a label for a given basic block. */
3426 label_for_bb (basic_block bb
)
3428 rtx label
= BB_HEAD (bb
);
3430 if (!LABEL_P (label
))
3433 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
3435 label
= block_label (bb
);
3441 /* Locate the effective beginning and end of the insn chain for each
3442 block, as defined by skip_insns_after_block above. */
3445 record_effective_endpoints (void)
3447 rtx_insn
*next_insn
;
3451 for (insn
= get_insns ();
3454 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
;
3455 insn
= NEXT_INSN (insn
))
3457 /* No basic blocks at all? */
3460 if (PREV_INSN (insn
))
3461 cfg_layout_function_header
=
3462 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
3464 cfg_layout_function_header
= NULL
;
3466 next_insn
= get_insns ();
3467 FOR_EACH_BB_FN (bb
, cfun
)
3471 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
3472 BB_HEADER (bb
) = unlink_insn_chain (next_insn
,
3473 PREV_INSN (BB_HEAD (bb
)));
3474 end
= skip_insns_after_block (bb
);
3475 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
3476 BB_FOOTER (bb
) = unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
3477 next_insn
= NEXT_INSN (BB_END (bb
));
3480 cfg_layout_function_footer
= next_insn
;
3481 if (cfg_layout_function_footer
)
3482 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
3487 const pass_data pass_data_into_cfg_layout_mode
=
3489 RTL_PASS
, /* type */
3490 "into_cfglayout", /* name */
3491 OPTGROUP_NONE
, /* optinfo_flags */
3493 0, /* properties_required */
3494 PROP_cfglayout
, /* properties_provided */
3495 0, /* properties_destroyed */
3496 0, /* todo_flags_start */
3497 0, /* todo_flags_finish */
3500 class pass_into_cfg_layout_mode
: public rtl_opt_pass
3503 pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3504 : rtl_opt_pass (pass_data_into_cfg_layout_mode
, ctxt
)
3507 /* opt_pass methods: */
3508 virtual unsigned int execute (function
*)
3510 cfg_layout_initialize (0);
3514 }; // class pass_into_cfg_layout_mode
3519 make_pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3521 return new pass_into_cfg_layout_mode (ctxt
);
3526 const pass_data pass_data_outof_cfg_layout_mode
=
3528 RTL_PASS
, /* type */
3529 "outof_cfglayout", /* name */
3530 OPTGROUP_NONE
, /* optinfo_flags */
3532 0, /* properties_required */
3533 0, /* properties_provided */
3534 PROP_cfglayout
, /* properties_destroyed */
3535 0, /* todo_flags_start */
3536 0, /* todo_flags_finish */
3539 class pass_outof_cfg_layout_mode
: public rtl_opt_pass
3542 pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3543 : rtl_opt_pass (pass_data_outof_cfg_layout_mode
, ctxt
)
3546 /* opt_pass methods: */
3547 virtual unsigned int execute (function
*);
3549 }; // class pass_outof_cfg_layout_mode
3552 pass_outof_cfg_layout_mode::execute (function
*fun
)
3556 FOR_EACH_BB_FN (bb
, fun
)
3557 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3558 bb
->aux
= bb
->next_bb
;
3560 cfg_layout_finalize ();
3568 make_pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3570 return new pass_outof_cfg_layout_mode (ctxt
);
3574 /* Link the basic blocks in the correct order, compacting the basic
3575 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3576 function also clears the basic block header and footer fields.
3578 This function is usually called after a pass (e.g. tracer) finishes
3579 some transformations while in cfglayout mode. The required sequence
3580 of the basic blocks is in a linked list along the bb->aux field.
3581 This functions re-links the basic block prev_bb and next_bb pointers
3582 accordingly, and it compacts and renumbers the blocks.
3584 FIXME: This currently works only for RTL, but the only RTL-specific
3585 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3586 to GIMPLE a long time ago, but it doesn't relink the basic block
3587 chain. It could do that (to give better initial RTL) if this function
3588 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3591 relink_block_chain (bool stay_in_cfglayout_mode
)
3593 basic_block bb
, prev_bb
;
3596 /* Maybe dump the re-ordered sequence. */
3599 fprintf (dump_file
, "Reordered sequence:\n");
3600 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, index
=
3603 bb
= (basic_block
) bb
->aux
, index
++)
3605 fprintf (dump_file
, " %i ", index
);
3606 if (get_bb_original (bb
))
3607 fprintf (dump_file
, "duplicate of %i ",
3608 get_bb_original (bb
)->index
);
3609 else if (forwarder_block_p (bb
)
3610 && !LABEL_P (BB_HEAD (bb
)))
3611 fprintf (dump_file
, "compensation ");
3613 fprintf (dump_file
, "bb %i ", bb
->index
);
3614 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
3618 /* Now reorder the blocks. */
3619 prev_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
3620 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
3621 for (; bb
; prev_bb
= bb
, bb
= (basic_block
) bb
->aux
)
3623 bb
->prev_bb
= prev_bb
;
3624 prev_bb
->next_bb
= bb
;
3626 prev_bb
->next_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
3627 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
= prev_bb
;
3629 /* Then, clean up the aux fields. */
3630 FOR_ALL_BB_FN (bb
, cfun
)
3633 if (!stay_in_cfglayout_mode
)
3634 BB_HEADER (bb
) = BB_FOOTER (bb
) = NULL
;
3637 /* Maybe reset the original copy tables, they are not valid anymore
3638 when we renumber the basic blocks in compact_blocks. If we are
3639 are going out of cfglayout mode, don't re-allocate the tables. */
3640 free_original_copy_tables ();
3641 if (stay_in_cfglayout_mode
)
3642 initialize_original_copy_tables ();
3644 /* Finally, put basic_block_info in the new order. */
3649 /* Given a reorder chain, rearrange the code to match. */
3652 fixup_reorder_chain (void)
3655 rtx_insn
*insn
= NULL
;
3657 if (cfg_layout_function_header
)
3659 set_first_insn (cfg_layout_function_header
);
3660 insn
= cfg_layout_function_header
;
3661 while (NEXT_INSN (insn
))
3662 insn
= NEXT_INSN (insn
);
3665 /* First do the bulk reordering -- rechain the blocks without regard to
3666 the needed changes to jumps and labels. */
3668 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3674 SET_NEXT_INSN (insn
) = BB_HEADER (bb
);
3676 set_first_insn (BB_HEADER (bb
));
3677 SET_PREV_INSN (BB_HEADER (bb
)) = insn
;
3678 insn
= BB_HEADER (bb
);
3679 while (NEXT_INSN (insn
))
3680 insn
= NEXT_INSN (insn
);
3683 SET_NEXT_INSN (insn
) = BB_HEAD (bb
);
3685 set_first_insn (BB_HEAD (bb
));
3686 SET_PREV_INSN (BB_HEAD (bb
)) = insn
;
3690 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
3691 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
3692 while (NEXT_INSN (insn
))
3693 insn
= NEXT_INSN (insn
);
3697 SET_NEXT_INSN (insn
) = cfg_layout_function_footer
;
3698 if (cfg_layout_function_footer
)
3699 SET_PREV_INSN (cfg_layout_function_footer
) = insn
;
3701 while (NEXT_INSN (insn
))
3702 insn
= NEXT_INSN (insn
);
3704 set_last_insn (insn
);
3705 #ifdef ENABLE_CHECKING
3706 verify_insn_chain ();
3709 /* Now add jumps and labels as needed to match the blocks new
3712 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3715 edge e_fall
, e_taken
, e
;
3716 rtx_insn
*bb_end_insn
;
3717 rtx ret_label
= NULL_RTX
;
3721 if (EDGE_COUNT (bb
->succs
) == 0)
3724 /* Find the old fallthru edge, and another non-EH edge for
3726 e_taken
= e_fall
= NULL
;
3728 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3729 if (e
->flags
& EDGE_FALLTHRU
)
3731 else if (! (e
->flags
& EDGE_EH
))
3734 bb_end_insn
= BB_END (bb
);
3735 if (JUMP_P (bb_end_insn
))
3737 ret_label
= JUMP_LABEL (bb_end_insn
);
3738 if (any_condjump_p (bb_end_insn
))
3740 /* This might happen if the conditional jump has side
3741 effects and could therefore not be optimized away.
3742 Make the basic block to end with a barrier in order
3743 to prevent rtl_verify_flow_info from complaining. */
3746 gcc_assert (!onlyjump_p (bb_end_insn
)
3747 || returnjump_p (bb_end_insn
)
3748 || (e_taken
->flags
& EDGE_CROSSING
));
3749 emit_barrier_after (bb_end_insn
);
3753 /* If the old fallthru is still next, nothing to do. */
3754 if (bb
->aux
== e_fall
->dest
3755 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3758 /* The degenerated case of conditional jump jumping to the next
3759 instruction can happen for jumps with side effects. We need
3760 to construct a forwarder block and this will be done just
3761 fine by force_nonfallthru below. */
3765 /* There is another special case: if *neither* block is next,
3766 such as happens at the very end of a function, then we'll
3767 need to add a new unconditional jump. Choose the taken
3768 edge based on known or assumed probability. */
3769 else if (bb
->aux
!= e_taken
->dest
)
3771 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
3774 && XINT (note
, 0) < REG_BR_PROB_BASE
/ 2
3775 && invert_jump (bb_end_insn
,
3777 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3779 : label_for_bb (e_fall
->dest
)), 0))
3781 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3782 gcc_checking_assert (could_fall_through
3783 (e_taken
->src
, e_taken
->dest
));
3784 e_taken
->flags
|= EDGE_FALLTHRU
;
3785 update_br_prob_note (bb
);
3786 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
3790 /* If the "jumping" edge is a crossing edge, and the fall
3791 through edge is non-crossing, leave things as they are. */
3792 else if ((e_taken
->flags
& EDGE_CROSSING
)
3793 && !(e_fall
->flags
& EDGE_CROSSING
))
3796 /* Otherwise we can try to invert the jump. This will
3797 basically never fail, however, keep up the pretense. */
3798 else if (invert_jump (bb_end_insn
,
3800 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3802 : label_for_bb (e_fall
->dest
)), 0))
3804 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3805 gcc_checking_assert (could_fall_through
3806 (e_taken
->src
, e_taken
->dest
));
3807 e_taken
->flags
|= EDGE_FALLTHRU
;
3808 update_br_prob_note (bb
);
3809 if (LABEL_NUSES (ret_label
) == 0
3810 && single_pred_p (e_taken
->dest
))
3811 delete_insn (ret_label
);
3815 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
3817 /* If the old fallthru is still next or if
3818 asm goto doesn't have a fallthru (e.g. when followed by
3819 __builtin_unreachable ()), nothing to do. */
3821 || bb
->aux
== e_fall
->dest
3822 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3825 /* Otherwise we'll have to use the fallthru fixup below. */
3829 /* Otherwise we have some return, switch or computed
3830 jump. In the 99% case, there should not have been a
3832 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
3838 /* No fallthru implies a noreturn function with EH edges, or
3839 something similarly bizarre. In any case, we don't need to
3844 /* If the fallthru block is still next, nothing to do. */
3845 if (bb
->aux
== e_fall
->dest
)
3848 /* A fallthru to exit block. */
3849 if (e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3853 /* We got here if we need to add a new jump insn.
3854 Note force_nonfallthru can delete E_FALL and thus we have to
3855 save E_FALL->src prior to the call to force_nonfallthru. */
3856 nb
= force_nonfallthru_and_redirect (e_fall
, e_fall
->dest
, ret_label
);
3861 /* Don't process this new block. */
3866 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3868 /* Annoying special case - jump around dead jumptables left in the code. */
3869 FOR_EACH_BB_FN (bb
, cfun
)
3871 edge e
= find_fallthru_edge (bb
->succs
);
3873 if (e
&& !can_fallthru (e
->src
, e
->dest
))
3874 force_nonfallthru (e
);
3877 /* Ensure goto_locus from edges has some instructions with that locus
3880 FOR_EACH_BB_FN (bb
, cfun
)
3885 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3886 if (LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
3887 && !(e
->flags
& EDGE_ABNORMAL
))
3891 basic_block dest
, nb
;
3894 insn
= BB_END (e
->src
);
3895 end
= PREV_INSN (BB_HEAD (e
->src
));
3897 && (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
3898 insn
= PREV_INSN (insn
);
3900 && INSN_LOCATION (insn
) == e
->goto_locus
)
3902 if (simplejump_p (BB_END (e
->src
))
3903 && !INSN_HAS_LOCATION (BB_END (e
->src
)))
3905 INSN_LOCATION (BB_END (e
->src
)) = e
->goto_locus
;
3909 if (dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3911 /* Non-fallthru edges to the exit block cannot be split. */
3912 if (!(e
->flags
& EDGE_FALLTHRU
))
3917 insn
= BB_HEAD (dest
);
3918 end
= NEXT_INSN (BB_END (dest
));
3919 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
3920 insn
= NEXT_INSN (insn
);
3921 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
3922 && INSN_LOCATION (insn
) == e
->goto_locus
)
3925 nb
= split_edge (e
);
3926 if (!INSN_P (BB_END (nb
)))
3927 BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
3929 INSN_LOCATION (BB_END (nb
)) = e
->goto_locus
;
3931 /* If there are other incoming edges to the destination block
3932 with the same goto locus, redirect them to the new block as
3933 well, this can prevent other such blocks from being created
3934 in subsequent iterations of the loop. */
3935 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
3936 if (LOCATION_LOCUS (e2
->goto_locus
) != UNKNOWN_LOCATION
3937 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
3938 && e
->goto_locus
== e2
->goto_locus
)
3939 redirect_edge_and_branch (e2
, nb
);
3946 /* Perform sanity checks on the insn chain.
3947 1. Check that next/prev pointers are consistent in both the forward and
3949 2. Count insns in chain, going both directions, and check if equal.
3950 3. Check that get_last_insn () returns the actual end of chain. */
3953 verify_insn_chain (void)
3955 rtx_insn
*x
, *prevx
, *nextx
;
3956 int insn_cnt1
, insn_cnt2
;
3958 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
3960 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
3961 gcc_assert (PREV_INSN (x
) == prevx
);
3963 gcc_assert (prevx
== get_last_insn ());
3965 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
3967 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
3968 gcc_assert (NEXT_INSN (x
) == nextx
);
3970 gcc_assert (insn_cnt1
== insn_cnt2
);
3973 /* If we have assembler epilogues, the block falling through to exit must
3974 be the last one in the reordered chain when we reach final. Ensure
3975 that this condition is met. */
3977 fixup_fallthru_exit_predecessor (void)
3980 basic_block bb
= NULL
;
3982 /* This transformation is not valid before reload, because we might
3983 separate a call from the instruction that copies the return
3985 gcc_assert (reload_completed
);
3987 e
= find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
3993 basic_block c
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
3995 /* If the very first block is the one with the fall-through exit
3996 edge, we have to split that block. */
3999 bb
= split_block (bb
, NULL
)->dest
;
4002 BB_FOOTER (bb
) = BB_FOOTER (c
);
4003 BB_FOOTER (c
) = NULL
;
4006 while (c
->aux
!= bb
)
4007 c
= (basic_block
) c
->aux
;
4011 c
= (basic_block
) c
->aux
;
4018 /* In case there are more than one fallthru predecessors of exit, force that
4019 there is only one. */
4022 force_one_exit_fallthru (void)
4024 edge e
, predecessor
= NULL
;
4027 basic_block forwarder
, bb
;
4029 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
4030 if (e
->flags
& EDGE_FALLTHRU
)
4032 if (predecessor
== NULL
)
4044 /* Exit has several fallthru predecessors. Create a forwarder block for
4046 forwarder
= split_edge (predecessor
);
4047 for (ei
= ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4048 (e
= ei_safe_edge (ei
)); )
4050 if (e
->src
== forwarder
4051 || !(e
->flags
& EDGE_FALLTHRU
))
4054 redirect_edge_and_branch_force (e
, forwarder
);
4057 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4059 FOR_EACH_BB_FN (bb
, cfun
)
4061 if (bb
->aux
== NULL
&& bb
!= forwarder
)
4063 bb
->aux
= forwarder
;
4069 /* Return true in case it is possible to duplicate the basic block BB. */
4072 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
4074 /* Do not attempt to duplicate tablejumps, as we need to unshare
4075 the dispatch table. This is difficult to do, as the instructions
4076 computing jump destination may be hoisted outside the basic block. */
4077 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
4080 /* Do not duplicate blocks containing insns that can't be copied. */
4081 if (targetm
.cannot_copy_insn_p
)
4083 rtx_insn
*insn
= BB_HEAD (bb
);
4086 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
4088 if (insn
== BB_END (bb
))
4090 insn
= NEXT_INSN (insn
);
4098 duplicate_insn_chain (rtx_insn
*from
, rtx_insn
*to
)
4100 rtx_insn
*insn
, *next
, *copy
;
4103 /* Avoid updating of boundaries of previous basic block. The
4104 note will get removed from insn stream in fixup. */
4105 last
= emit_note (NOTE_INSN_DELETED
);
4107 /* Create copy at the end of INSN chain. The chain will
4108 be reordered later. */
4109 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
4111 switch (GET_CODE (insn
))
4114 /* Don't duplicate label debug insns. */
4115 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
)
4121 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
4122 if (JUMP_P (insn
) && JUMP_LABEL (insn
) != NULL_RTX
4123 && ANY_RETURN_P (JUMP_LABEL (insn
)))
4124 JUMP_LABEL (copy
) = JUMP_LABEL (insn
);
4125 maybe_copy_prologue_epilogue_insn (insn
, copy
);
4128 case JUMP_TABLE_DATA
:
4129 /* Avoid copying of dispatch tables. We never duplicate
4130 tablejumps, so this can hit only in case the table got
4131 moved far from original jump.
4132 Avoid copying following barrier as well if any
4133 (and debug insns in between). */
4134 for (next
= NEXT_INSN (insn
);
4135 next
!= NEXT_INSN (to
);
4136 next
= NEXT_INSN (next
))
4137 if (!DEBUG_INSN_P (next
))
4139 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
4151 switch (NOTE_KIND (insn
))
4153 /* In case prologue is empty and function contain label
4154 in first BB, we may want to copy the block. */
4155 case NOTE_INSN_PROLOGUE_END
:
4157 case NOTE_INSN_DELETED
:
4158 case NOTE_INSN_DELETED_LABEL
:
4159 case NOTE_INSN_DELETED_DEBUG_LABEL
:
4160 /* No problem to strip these. */
4161 case NOTE_INSN_FUNCTION_BEG
:
4162 /* There is always just single entry to function. */
4163 case NOTE_INSN_BASIC_BLOCK
:
4164 /* We should only switch text sections once. */
4165 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
4168 case NOTE_INSN_EPILOGUE_BEG
:
4169 emit_note_copy (as_a
<rtx_note
*> (insn
));
4173 /* All other notes should have already been eliminated. */
4181 insn
= NEXT_INSN (last
);
4186 /* Create a duplicate of the basic block BB. */
4189 cfg_layout_duplicate_bb (basic_block bb
)
4194 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
4195 new_bb
= create_basic_block (insn
,
4196 insn
? get_last_insn () : NULL
,
4197 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
);
4199 BB_COPY_PARTITION (new_bb
, bb
);
4202 insn
= BB_HEADER (bb
);
4203 while (NEXT_INSN (insn
))
4204 insn
= NEXT_INSN (insn
);
4205 insn
= duplicate_insn_chain (BB_HEADER (bb
), insn
);
4207 BB_HEADER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4212 insn
= BB_FOOTER (bb
);
4213 while (NEXT_INSN (insn
))
4214 insn
= NEXT_INSN (insn
);
4215 insn
= duplicate_insn_chain (BB_FOOTER (bb
), insn
);
4217 BB_FOOTER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4224 /* Main entry point to this module - initialize the datastructures for
4225 CFG layout changes. It keeps LOOPS up-to-date if not null.
4227 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4230 cfg_layout_initialize (unsigned int flags
)
4235 /* Once bb partitioning is complete, cfg layout mode should not be
4236 re-entered. Entering cfg layout mode may require fixups. As an
4237 example, if edge forwarding performed when optimizing the cfg
4238 layout required moving a block from the hot to the cold
4239 section. This would create an illegal partitioning unless some
4240 manual fixup was performed. */
4241 gcc_assert (!(crtl
->bb_reorder_complete
4242 && flag_reorder_blocks_and_partition
));
4244 initialize_original_copy_tables ();
4246 cfg_layout_rtl_register_cfg_hooks ();
4248 record_effective_endpoints ();
4250 /* Make sure that the targets of non local gotos are marked. */
4251 for (x
= nonlocal_goto_handler_labels
; x
; x
= x
->next ())
4253 bb
= BLOCK_FOR_INSN (x
->insn ());
4254 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
4257 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
4260 /* Splits superblocks. */
4262 break_superblocks (void)
4264 sbitmap superblocks
;
4268 superblocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
4269 bitmap_clear (superblocks
);
4271 FOR_EACH_BB_FN (bb
, cfun
)
4272 if (bb
->flags
& BB_SUPERBLOCK
)
4274 bb
->flags
&= ~BB_SUPERBLOCK
;
4275 bitmap_set_bit (superblocks
, bb
->index
);
4281 rebuild_jump_labels (get_insns ());
4282 find_many_sub_basic_blocks (superblocks
);
4288 /* Finalize the changes: reorder insn list according to the sequence specified
4289 by aux pointers, enter compensation code, rebuild scope forest. */
4292 cfg_layout_finalize (void)
4294 #ifdef ENABLE_CHECKING
4295 verify_flow_info ();
4297 force_one_exit_fallthru ();
4298 rtl_register_cfg_hooks ();
4299 if (reload_completed
4300 #ifdef HAVE_epilogue
4304 fixup_fallthru_exit_predecessor ();
4305 fixup_reorder_chain ();
4307 rebuild_jump_labels (get_insns ());
4308 delete_dead_jumptables ();
4310 #ifdef ENABLE_CHECKING
4311 verify_insn_chain ();
4312 verify_flow_info ();
4317 /* Same as split_block but update cfg_layout structures. */
4320 cfg_layout_split_block (basic_block bb
, void *insnp
)
4322 rtx insn
= (rtx
) insnp
;
4323 basic_block new_bb
= rtl_split_block (bb
, insn
);
4325 BB_FOOTER (new_bb
) = BB_FOOTER (bb
);
4326 BB_FOOTER (bb
) = NULL
;
4331 /* Redirect Edge to DEST. */
4333 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
4335 basic_block src
= e
->src
;
4338 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4341 if (e
->dest
== dest
)
4344 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4345 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
4347 df_set_bb_dirty (src
);
4351 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4352 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
4355 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
4356 e
->src
->index
, dest
->index
);
4358 df_set_bb_dirty (e
->src
);
4359 redirect_edge_succ (e
, dest
);
4363 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4364 in the case the basic block appears to be in sequence. Avoid this
4367 if (e
->flags
& EDGE_FALLTHRU
)
4369 /* Redirect any branch edges unified with the fallthru one. */
4370 if (JUMP_P (BB_END (src
))
4371 && label_is_jump_target_p (BB_HEAD (e
->dest
),
4377 fprintf (dump_file
, "Fallthru edge unified with branch "
4378 "%i->%i redirected to %i\n",
4379 e
->src
->index
, e
->dest
->index
, dest
->index
);
4380 e
->flags
&= ~EDGE_FALLTHRU
;
4381 redirected
= redirect_branch_edge (e
, dest
);
4382 gcc_assert (redirected
);
4383 redirected
->flags
|= EDGE_FALLTHRU
;
4384 df_set_bb_dirty (redirected
->src
);
4387 /* In case we are redirecting fallthru edge to the branch edge
4388 of conditional jump, remove it. */
4389 if (EDGE_COUNT (src
->succs
) == 2)
4391 /* Find the edge that is different from E. */
4392 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
4395 && any_condjump_p (BB_END (src
))
4396 && onlyjump_p (BB_END (src
)))
4397 delete_insn (BB_END (src
));
4400 fprintf (dump_file
, "Redirecting fallthru edge %i->%i to %i\n",
4401 e
->src
->index
, e
->dest
->index
, dest
->index
);
4402 ret
= redirect_edge_succ_nodup (e
, dest
);
4405 ret
= redirect_branch_edge (e
, dest
);
4407 /* We don't want simplejumps in the insn stream during cfglayout. */
4408 gcc_assert (!simplejump_p (BB_END (src
)));
4410 df_set_bb_dirty (src
);
4414 /* Simple wrapper as we always can redirect fallthru edges. */
4416 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
4418 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
4420 gcc_assert (redirected
);
4424 /* Same as delete_basic_block but update cfg_layout structures. */
4427 cfg_layout_delete_block (basic_block bb
)
4429 rtx_insn
*insn
, *next
, *prev
= PREV_INSN (BB_HEAD (bb
)), *remaints
;
4434 next
= BB_HEAD (bb
);
4436 SET_NEXT_INSN (prev
) = BB_HEADER (bb
);
4438 set_first_insn (BB_HEADER (bb
));
4439 SET_PREV_INSN (BB_HEADER (bb
)) = prev
;
4440 insn
= BB_HEADER (bb
);
4441 while (NEXT_INSN (insn
))
4442 insn
= NEXT_INSN (insn
);
4443 SET_NEXT_INSN (insn
) = next
;
4444 SET_PREV_INSN (next
) = insn
;
4446 next
= NEXT_INSN (BB_END (bb
));
4449 insn
= BB_FOOTER (bb
);
4452 if (BARRIER_P (insn
))
4454 if (PREV_INSN (insn
))
4455 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
4457 BB_FOOTER (bb
) = NEXT_INSN (insn
);
4458 if (NEXT_INSN (insn
))
4459 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
4463 insn
= NEXT_INSN (insn
);
4468 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
4469 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
4470 while (NEXT_INSN (insn
))
4471 insn
= NEXT_INSN (insn
);
4472 SET_NEXT_INSN (insn
) = next
;
4474 SET_PREV_INSN (next
) = insn
;
4476 set_last_insn (insn
);
4479 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
4480 to
= &BB_HEADER (bb
->next_bb
);
4482 to
= &cfg_layout_function_footer
;
4484 rtl_delete_block (bb
);
4487 prev
= NEXT_INSN (prev
);
4489 prev
= get_insns ();
4491 next
= PREV_INSN (next
);
4493 next
= get_last_insn ();
4495 if (next
&& NEXT_INSN (next
) != prev
)
4497 remaints
= unlink_insn_chain (prev
, next
);
4499 while (NEXT_INSN (insn
))
4500 insn
= NEXT_INSN (insn
);
4501 SET_NEXT_INSN (insn
) = *to
;
4503 SET_PREV_INSN (*to
) = insn
;
4508 /* Return true when blocks A and B can be safely merged. */
4511 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
4513 /* If we are partitioning hot/cold basic blocks, we don't want to
4514 mess up unconditional or indirect jumps that cross between hot
4517 Basic block partitioning may result in some jumps that appear to
4518 be optimizable (or blocks that appear to be mergeable), but which really
4519 must be left untouched (they are required to make it safely across
4520 partition boundaries). See the comments at the top of
4521 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4523 if (BB_PARTITION (a
) != BB_PARTITION (b
))
4526 /* Protect the loop latches. */
4527 if (current_loops
&& b
->loop_father
->latch
== b
)
4530 /* If we would end up moving B's instructions, make sure it doesn't fall
4531 through into the exit block, since we cannot recover from a fallthrough
4532 edge into the exit block occurring in the middle of a function. */
4533 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4535 edge e
= find_fallthru_edge (b
->succs
);
4536 if (e
&& e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4540 /* There must be exactly one edge in between the blocks. */
4541 return (single_succ_p (a
)
4542 && single_succ (a
) == b
4543 && single_pred_p (b
) == 1
4545 /* Must be simple edge. */
4546 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
4547 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4548 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
4549 /* If the jump insn has side effects, we can't kill the edge.
4550 When not optimizing, try_redirect_by_replacing_jump will
4551 not allow us to redirect an edge by replacing a table jump. */
4552 && (!JUMP_P (BB_END (a
))
4553 || ((!optimize
|| reload_completed
)
4554 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
4557 /* Merge block A and B. The blocks must be mergeable. */
4560 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
4562 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
4565 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a
, b
));
4568 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
4571 /* If there was a CODE_LABEL beginning B, delete it. */
4572 if (LABEL_P (BB_HEAD (b
)))
4574 delete_insn (BB_HEAD (b
));
4577 /* We should have fallthru edge in a, or we can do dummy redirection to get
4579 if (JUMP_P (BB_END (a
)))
4580 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
4581 gcc_assert (!JUMP_P (BB_END (a
)));
4583 /* When not optimizing and the edge is the only place in RTL which holds
4584 some unique locus, emit a nop with that locus in between. */
4586 emit_nop_for_unique_locus_between (a
, b
);
4588 /* Move things from b->footer after a->footer. */
4592 BB_FOOTER (a
) = BB_FOOTER (b
);
4595 rtx_insn
*last
= BB_FOOTER (a
);
4597 while (NEXT_INSN (last
))
4598 last
= NEXT_INSN (last
);
4599 SET_NEXT_INSN (last
) = BB_FOOTER (b
);
4600 SET_PREV_INSN (BB_FOOTER (b
)) = last
;
4602 BB_FOOTER (b
) = NULL
;
4605 /* Move things from b->header before a->footer.
4606 Note that this may include dead tablejump data, but we don't clean
4607 those up until we go out of cfglayout mode. */
4610 if (! BB_FOOTER (a
))
4611 BB_FOOTER (a
) = BB_HEADER (b
);
4614 rtx_insn
*last
= BB_HEADER (b
);
4616 while (NEXT_INSN (last
))
4617 last
= NEXT_INSN (last
);
4618 SET_NEXT_INSN (last
) = BB_FOOTER (a
);
4619 SET_PREV_INSN (BB_FOOTER (a
)) = last
;
4620 BB_FOOTER (a
) = BB_HEADER (b
);
4622 BB_HEADER (b
) = NULL
;
4625 /* In the case basic blocks are not adjacent, move them around. */
4626 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4628 insn
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
4630 emit_insn_after_noloc (insn
, BB_END (a
), a
);
4632 /* Otherwise just re-associate the instructions. */
4636 BB_END (a
) = BB_END (b
);
4639 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4640 We need to explicitly call. */
4641 update_bb_for_insn_chain (insn
, BB_END (b
), a
);
4643 /* Skip possible DELETED_LABEL insn. */
4644 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
4645 insn
= NEXT_INSN (insn
);
4646 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4647 BB_HEAD (b
) = BB_END (b
) = NULL
;
4650 df_bb_delete (b
->index
);
4652 /* If B was a forwarder block, propagate the locus on the edge. */
4654 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
4655 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
4658 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
4664 cfg_layout_split_edge (edge e
)
4666 basic_block new_bb
=
4667 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4668 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
4671 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4672 BB_COPY_PARTITION (new_bb
, e
->src
);
4674 BB_COPY_PARTITION (new_bb
, e
->dest
);
4675 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
4676 redirect_edge_and_branch_force (e
, new_bb
);
4681 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4684 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
4688 /* Return true if BB contains only labels or non-executable
4692 rtl_block_empty_p (basic_block bb
)
4696 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4697 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4700 FOR_BB_INSNS (bb
, insn
)
4701 if (NONDEBUG_INSN_P (insn
) && !any_uncondjump_p (insn
))
4707 /* Split a basic block if it ends with a conditional branch and if
4708 the other part of the block is not empty. */
4711 rtl_split_block_before_cond_jump (basic_block bb
)
4714 rtx_insn
*split_point
= NULL
;
4715 rtx_insn
*last
= NULL
;
4716 bool found_code
= false;
4718 FOR_BB_INSNS (bb
, insn
)
4720 if (any_condjump_p (insn
))
4722 else if (NONDEBUG_INSN_P (insn
))
4727 /* Did not find everything. */
4728 if (found_code
&& split_point
)
4729 return split_block (bb
, split_point
)->dest
;
4734 /* Return 1 if BB ends with a call, possibly followed by some
4735 instructions that must stay with the call, 0 otherwise. */
4738 rtl_block_ends_with_call_p (basic_block bb
)
4740 rtx_insn
*insn
= BB_END (bb
);
4742 while (!CALL_P (insn
)
4743 && insn
!= BB_HEAD (bb
)
4744 && (keep_with_call_p (insn
)
4746 || DEBUG_INSN_P (insn
)))
4747 insn
= PREV_INSN (insn
);
4748 return (CALL_P (insn
));
4751 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4754 rtl_block_ends_with_condjump_p (const_basic_block bb
)
4756 return any_condjump_p (BB_END (bb
));
4759 /* Return true if we need to add fake edge to exit.
4760 Helper function for rtl_flow_call_edges_add. */
4763 need_fake_edge_p (const rtx_insn
*insn
)
4769 && !SIBLING_CALL_P (insn
)
4770 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
4771 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
4774 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
4775 && MEM_VOLATILE_P (PATTERN (insn
)))
4776 || (GET_CODE (PATTERN (insn
)) == PARALLEL
4777 && asm_noperands (insn
) != -1
4778 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
4779 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
4782 /* Add fake edges to the function exit for any non constant and non noreturn
4783 calls, volatile inline assembly in the bitmap of blocks specified by
4784 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4787 The goal is to expose cases in which entering a basic block does not imply
4788 that all subsequent instructions must be executed. */
4791 rtl_flow_call_edges_add (sbitmap blocks
)
4794 int blocks_split
= 0;
4795 int last_bb
= last_basic_block_for_fn (cfun
);
4796 bool check_last_block
= false;
4798 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
4802 check_last_block
= true;
4804 check_last_block
= bitmap_bit_p (blocks
,
4805 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
->index
);
4807 /* In the last basic block, before epilogue generation, there will be
4808 a fallthru edge to EXIT. Special care is required if the last insn
4809 of the last basic block is a call because make_edge folds duplicate
4810 edges, which would result in the fallthru edge also being marked
4811 fake, which would result in the fallthru edge being removed by
4812 remove_fake_edges, which would result in an invalid CFG.
4814 Moreover, we can't elide the outgoing fake edge, since the block
4815 profiler needs to take this into account in order to solve the minimal
4816 spanning tree in the case that the call doesn't return.
4818 Handle this by adding a dummy instruction in a new last basic block. */
4819 if (check_last_block
)
4821 basic_block bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
4822 rtx_insn
*insn
= BB_END (bb
);
4824 /* Back up past insns that must be kept in the same block as a call. */
4825 while (insn
!= BB_HEAD (bb
)
4826 && keep_with_call_p (insn
))
4827 insn
= PREV_INSN (insn
);
4829 if (need_fake_edge_p (insn
))
4833 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4836 insert_insn_on_edge (gen_use (const0_rtx
), e
);
4837 commit_edge_insertions ();
4842 /* Now add fake edges to the function exit for any non constant
4843 calls since there is no way that we can determine if they will
4846 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
4848 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
4850 rtx_insn
*prev_insn
;
4855 if (blocks
&& !bitmap_bit_p (blocks
, i
))
4858 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
4860 prev_insn
= PREV_INSN (insn
);
4861 if (need_fake_edge_p (insn
))
4864 rtx_insn
*split_at_insn
= insn
;
4866 /* Don't split the block between a call and an insn that should
4867 remain in the same block as the call. */
4869 while (split_at_insn
!= BB_END (bb
)
4870 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
4871 split_at_insn
= NEXT_INSN (split_at_insn
);
4873 /* The handling above of the final block before the epilogue
4874 should be enough to verify that there is no edge to the exit
4875 block in CFG already. Calling make_edge in such case would
4876 cause us to mark that edge as fake and remove it later. */
4878 #ifdef ENABLE_CHECKING
4879 if (split_at_insn
== BB_END (bb
))
4881 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4882 gcc_assert (e
== NULL
);
4886 /* Note that the following may create a new basic block
4887 and renumber the existing basic blocks. */
4888 if (split_at_insn
!= BB_END (bb
))
4890 e
= split_block (bb
, split_at_insn
);
4895 make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
4898 if (insn
== BB_HEAD (bb
))
4904 verify_flow_info ();
4906 return blocks_split
;
4909 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4910 the conditional branch target, SECOND_HEAD should be the fall-thru
4911 there is no need to handle this here the loop versioning code handles
4912 this. the reason for SECON_HEAD is that it is needed for condition
4913 in trees, and this should be of the same type since it is a hook. */
4915 rtl_lv_add_condition_to_bb (basic_block first_head
,
4916 basic_block second_head ATTRIBUTE_UNUSED
,
4917 basic_block cond_bb
, void *comp_rtx
)
4920 rtx_insn
*seq
, *jump
;
4921 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
4922 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
4923 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
4927 label
= block_label (first_head
);
4928 mode
= GET_MODE (op0
);
4929 if (mode
== VOIDmode
)
4930 mode
= GET_MODE (op1
);
4933 op0
= force_operand (op0
, NULL_RTX
);
4934 op1
= force_operand (op1
, NULL_RTX
);
4935 do_compare_rtx_and_jump (op0
, op1
, comp
, 0,
4936 mode
, NULL_RTX
, NULL_RTX
, label
, -1);
4937 jump
= get_last_insn ();
4938 JUMP_LABEL (jump
) = label
;
4939 LABEL_NUSES (label
)++;
4943 /* Add the new cond, in the new head. */
4944 emit_insn_after (seq
, BB_END (cond_bb
));
4948 /* Given a block B with unconditional branch at its end, get the
4949 store the return the branch edge and the fall-thru edge in
4950 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4952 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
4953 edge
*fallthru_edge
)
4955 edge e
= EDGE_SUCC (b
, 0);
4957 if (e
->flags
& EDGE_FALLTHRU
)
4960 *branch_edge
= EDGE_SUCC (b
, 1);
4965 *fallthru_edge
= EDGE_SUCC (b
, 1);
4970 init_rtl_bb_info (basic_block bb
)
4972 gcc_assert (!bb
->il
.x
.rtl
);
4973 bb
->il
.x
.head_
= NULL
;
4974 bb
->il
.x
.rtl
= ggc_cleared_alloc
<rtl_bb_info
> ();
4977 /* Returns true if it is possible to remove edge E by redirecting
4978 it to the destination of the other edge from E->src. */
4981 rtl_can_remove_branch_p (const_edge e
)
4983 const_basic_block src
= e
->src
;
4984 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
4985 const rtx_insn
*insn
= BB_END (src
);
4988 /* The conditions are taken from try_redirect_by_replacing_jump. */
4989 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4992 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4995 if (BB_PARTITION (src
) != BB_PARTITION (target
))
4998 if (!onlyjump_p (insn
)
4999 || tablejump_p (insn
, NULL
, NULL
))
5002 set
= single_set (insn
);
5003 if (!set
|| side_effects_p (set
))
5010 rtl_duplicate_bb (basic_block bb
)
5012 bb
= cfg_layout_duplicate_bb (bb
);
5017 /* Do book-keeping of basic block BB for the profile consistency checker.
5018 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
5019 then do post-pass accounting. Store the counting in RECORD. */
5021 rtl_account_profile_record (basic_block bb
, int after_pass
,
5022 struct profile_record
*record
)
5025 FOR_BB_INSNS (bb
, insn
)
5028 record
->size
[after_pass
]
5029 += insn_rtx_cost (PATTERN (insn
), false);
5030 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
5031 record
->time
[after_pass
]
5032 += insn_rtx_cost (PATTERN (insn
), true) * bb
->count
;
5033 else if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
5034 record
->time
[after_pass
]
5035 += insn_rtx_cost (PATTERN (insn
), true) * bb
->frequency
;
5039 /* Implementation of CFG manipulation for linearized RTL. */
5040 struct cfg_hooks rtl_cfg_hooks
= {
5042 rtl_verify_flow_info
,
5044 rtl_dump_bb_for_graph
,
5045 rtl_create_basic_block
,
5046 rtl_redirect_edge_and_branch
,
5047 rtl_redirect_edge_and_branch_force
,
5048 rtl_can_remove_branch_p
,
5051 rtl_move_block_after
,
5052 rtl_can_merge_blocks
, /* can_merge_blocks_p */
5056 cfg_layout_can_duplicate_bb_p
,
5059 rtl_make_forwarder_block
,
5060 rtl_tidy_fallthru_edge
,
5061 rtl_force_nonfallthru
,
5062 rtl_block_ends_with_call_p
,
5063 rtl_block_ends_with_condjump_p
,
5064 rtl_flow_call_edges_add
,
5065 NULL
, /* execute_on_growing_pred */
5066 NULL
, /* execute_on_shrinking_pred */
5067 NULL
, /* duplicate loop for trees */
5068 NULL
, /* lv_add_condition_to_bb */
5069 NULL
, /* lv_adjust_loop_header_phi*/
5070 NULL
, /* extract_cond_bb_edges */
5071 NULL
, /* flush_pending_stmts */
5072 rtl_block_empty_p
, /* block_empty_p */
5073 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5074 rtl_account_profile_record
,
5077 /* Implementation of CFG manipulation for cfg layout RTL, where
5078 basic block connected via fallthru edges does not have to be adjacent.
5079 This representation will hopefully become the default one in future
5080 version of the compiler. */
5082 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
5084 rtl_verify_flow_info_1
,
5086 rtl_dump_bb_for_graph
,
5087 cfg_layout_create_basic_block
,
5088 cfg_layout_redirect_edge_and_branch
,
5089 cfg_layout_redirect_edge_and_branch_force
,
5090 rtl_can_remove_branch_p
,
5091 cfg_layout_delete_block
,
5092 cfg_layout_split_block
,
5093 rtl_move_block_after
,
5094 cfg_layout_can_merge_blocks_p
,
5095 cfg_layout_merge_blocks
,
5098 cfg_layout_can_duplicate_bb_p
,
5099 cfg_layout_duplicate_bb
,
5100 cfg_layout_split_edge
,
5101 rtl_make_forwarder_block
,
5102 NULL
, /* tidy_fallthru_edge */
5103 rtl_force_nonfallthru
,
5104 rtl_block_ends_with_call_p
,
5105 rtl_block_ends_with_condjump_p
,
5106 rtl_flow_call_edges_add
,
5107 NULL
, /* execute_on_growing_pred */
5108 NULL
, /* execute_on_shrinking_pred */
5109 duplicate_loop_to_header_edge
, /* duplicate loop for trees */
5110 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
5111 NULL
, /* lv_adjust_loop_header_phi*/
5112 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
5113 NULL
, /* flush_pending_stmts */
5114 rtl_block_empty_p
, /* block_empty_p */
5115 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5116 rtl_account_profile_record
,
5119 #include "gt-cfgrtl.h"