1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2016 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"
49 #include "insn-config.h"
55 #include "cfgcleanup.h"
56 #include "bb-reorder.h"
57 #include "rtl-error.h"
58 #include "insn-attr.h"
62 #include "tree-pass.h"
63 #include "print-rtl.h"
65 /* Holds the interesting leading and trailing notes for the function.
66 Only applicable if the CFG is in cfglayout mode. */
67 static GTY(()) rtx_insn
*cfg_layout_function_footer
;
68 static GTY(()) rtx_insn
*cfg_layout_function_header
;
70 static rtx_insn
*skip_insns_after_block (basic_block
);
71 static void record_effective_endpoints (void);
72 static void fixup_reorder_chain (void);
74 void verify_insn_chain (void);
75 static void fixup_fallthru_exit_predecessor (void);
76 static int can_delete_note_p (const rtx_note
*);
77 static int can_delete_label_p (const rtx_code_label
*);
78 static basic_block
rtl_split_edge (edge
);
79 static bool rtl_move_block_after (basic_block
, basic_block
);
80 static int rtl_verify_flow_info (void);
81 static basic_block
cfg_layout_split_block (basic_block
, void *);
82 static edge
cfg_layout_redirect_edge_and_branch (edge
, basic_block
);
83 static basic_block
cfg_layout_redirect_edge_and_branch_force (edge
, basic_block
);
84 static void cfg_layout_delete_block (basic_block
);
85 static void rtl_delete_block (basic_block
);
86 static basic_block
rtl_redirect_edge_and_branch_force (edge
, basic_block
);
87 static edge
rtl_redirect_edge_and_branch (edge
, basic_block
);
88 static basic_block
rtl_split_block (basic_block
, void *);
89 static void rtl_dump_bb (FILE *, basic_block
, int, int);
90 static int rtl_verify_flow_info_1 (void);
91 static void rtl_make_forwarder_block (edge
);
93 /* Return true if NOTE is not one of the ones that must be kept paired,
94 so that we may simply delete it. */
97 can_delete_note_p (const rtx_note
*note
)
99 switch (NOTE_KIND (note
))
101 case NOTE_INSN_DELETED
:
102 case NOTE_INSN_BASIC_BLOCK
:
103 case NOTE_INSN_EPILOGUE_BEG
:
111 /* True if a given label can be deleted. */
114 can_delete_label_p (const rtx_code_label
*label
)
116 return (!LABEL_PRESERVE_P (label
)
117 /* User declared labels must be preserved. */
118 && LABEL_NAME (label
) == 0
119 && !vec_safe_contains
<rtx_insn
*> (forced_labels
,
120 const_cast<rtx_code_label
*> (label
)));
123 /* Delete INSN by patching it out. */
126 delete_insn (rtx uncast_insn
)
128 rtx_insn
*insn
= as_a
<rtx_insn
*> (uncast_insn
);
130 bool really_delete
= true;
134 /* Some labels can't be directly removed from the INSN chain, as they
135 might be references via variables, constant pool etc.
136 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
137 if (! can_delete_label_p (as_a
<rtx_code_label
*> (insn
)))
139 const char *name
= LABEL_NAME (insn
);
140 basic_block bb
= BLOCK_FOR_INSN (insn
);
141 rtx_insn
*bb_note
= NEXT_INSN (insn
);
143 really_delete
= false;
144 PUT_CODE (insn
, NOTE
);
145 NOTE_KIND (insn
) = NOTE_INSN_DELETED_LABEL
;
146 NOTE_DELETED_LABEL_NAME (insn
) = name
;
148 /* If the note following the label starts a basic block, and the
149 label is a member of the same basic block, interchange the two. */
150 if (bb_note
!= NULL_RTX
151 && NOTE_INSN_BASIC_BLOCK_P (bb_note
)
153 && bb
== BLOCK_FOR_INSN (bb_note
))
155 reorder_insns_nobb (insn
, insn
, bb_note
);
156 BB_HEAD (bb
) = bb_note
;
157 if (BB_END (bb
) == bb_note
)
162 remove_node_from_insn_list (insn
, &nonlocal_goto_handler_labels
);
167 /* If this insn has already been deleted, something is very wrong. */
168 gcc_assert (!insn
->deleted ());
170 df_insn_delete (insn
);
172 insn
->set_deleted ();
175 /* If deleting a jump, decrement the use count of the label. Deleting
176 the label itself should happen in the normal course of block merging. */
179 if (JUMP_LABEL (insn
)
180 && LABEL_P (JUMP_LABEL (insn
)))
181 LABEL_NUSES (JUMP_LABEL (insn
))--;
183 /* If there are more targets, remove them too. */
185 = find_reg_note (insn
, REG_LABEL_TARGET
, NULL_RTX
)) != NULL_RTX
186 && LABEL_P (XEXP (note
, 0)))
188 LABEL_NUSES (XEXP (note
, 0))--;
189 remove_note (insn
, note
);
193 /* Also if deleting any insn that references a label as an operand. */
194 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, NULL_RTX
)) != NULL_RTX
195 && LABEL_P (XEXP (note
, 0)))
197 LABEL_NUSES (XEXP (note
, 0))--;
198 remove_note (insn
, note
);
201 if (rtx_jump_table_data
*table
= dyn_cast
<rtx_jump_table_data
*> (insn
))
203 rtvec vec
= table
->get_labels ();
204 int len
= GET_NUM_ELEM (vec
);
207 for (i
= 0; i
< len
; i
++)
209 rtx label
= XEXP (RTVEC_ELT (vec
, i
), 0);
211 /* When deleting code in bulk (e.g. removing many unreachable
212 blocks) we can delete a label that's a target of the vector
213 before deleting the vector itself. */
215 LABEL_NUSES (label
)--;
220 /* Like delete_insn but also purge dead edges from BB.
221 Return true if any edges are eliminated. */
224 delete_insn_and_edges (rtx_insn
*insn
)
229 && BLOCK_FOR_INSN (insn
)
230 && BB_END (BLOCK_FOR_INSN (insn
)) == insn
)
234 return purge_dead_edges (BLOCK_FOR_INSN (insn
));
238 /* Unlink a chain of insns between START and FINISH, leaving notes
239 that must be paired. If CLEAR_BB is true, we set bb field for
240 insns that cannot be removed to NULL. */
243 delete_insn_chain (rtx start
, rtx_insn
*finish
, bool clear_bb
)
245 /* Unchain the insns one by one. It would be quicker to delete all of these
246 with a single unchaining, rather than one at a time, but we need to keep
248 rtx_insn
*current
= finish
;
251 rtx_insn
*prev
= PREV_INSN (current
);
252 if (NOTE_P (current
) && !can_delete_note_p (as_a
<rtx_note
*> (current
)))
255 delete_insn (current
);
257 if (clear_bb
&& !current
->deleted ())
258 set_block_for_insn (current
, NULL
);
260 if (current
== start
)
266 /* Create a new basic block consisting of the instructions between HEAD and END
267 inclusive. This function is designed to allow fast BB construction - reuses
268 the note and basic block struct in BB_NOTE, if any and do not grow
269 BASIC_BLOCK chain and should be used directly only by CFG construction code.
270 END can be NULL in to create new empty basic block before HEAD. Both END
271 and HEAD can be NULL to create basic block at the end of INSN chain.
272 AFTER is the basic block we should be put after. */
275 create_basic_block_structure (rtx_insn
*head
, rtx_insn
*end
, rtx_note
*bb_note
,
281 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
284 /* If we found an existing note, thread it back onto the chain. */
292 after
= PREV_INSN (head
);
296 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
297 reorder_insns_nobb (bb_note
, bb_note
, after
);
301 /* Otherwise we must create a note and a basic block structure. */
305 init_rtl_bb_info (bb
);
308 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
309 else if (LABEL_P (head
) && end
)
311 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
317 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
323 NOTE_BASIC_BLOCK (bb_note
) = bb
;
326 /* Always include the bb note in the block. */
327 if (NEXT_INSN (end
) == bb_note
)
332 bb
->index
= last_basic_block_for_fn (cfun
)++;
333 bb
->flags
= BB_NEW
| BB_RTL
;
334 link_block (bb
, after
);
335 SET_BASIC_BLOCK_FOR_FN (cfun
, bb
->index
, bb
);
336 df_bb_refs_record (bb
->index
, false);
337 update_bb_for_insn (bb
);
338 BB_SET_PARTITION (bb
, BB_UNPARTITIONED
);
340 /* Tag the block so that we know it has been used when considering
341 other basic block notes. */
347 /* Create new basic block consisting of instructions in between HEAD and END
348 and place it to the BB chain after block AFTER. END can be NULL to
349 create a new empty basic block before HEAD. Both END and HEAD can be
350 NULL to create basic block at the end of INSN chain. */
353 rtl_create_basic_block (void *headp
, void *endp
, basic_block after
)
355 rtx_insn
*head
= (rtx_insn
*) headp
;
356 rtx_insn
*end
= (rtx_insn
*) endp
;
359 /* Grow the basic block array if needed. */
360 if ((size_t) last_basic_block_for_fn (cfun
)
361 >= basic_block_info_for_fn (cfun
)->length ())
364 (last_basic_block_for_fn (cfun
)
365 + (last_basic_block_for_fn (cfun
) + 3) / 4);
366 vec_safe_grow_cleared (basic_block_info_for_fn (cfun
), new_size
);
369 n_basic_blocks_for_fn (cfun
)++;
371 bb
= create_basic_block_structure (head
, end
, NULL
, after
);
377 cfg_layout_create_basic_block (void *head
, void *end
, basic_block after
)
379 basic_block newbb
= rtl_create_basic_block (head
, end
, after
);
384 /* Delete the insns in a (non-live) block. We physically delete every
385 non-deleted-note insn, and update the flow graph appropriately.
387 Return nonzero if we deleted an exception handler. */
389 /* ??? Preserving all such notes strikes me as wrong. It would be nice
390 to post-process the stream to remove empty blocks, loops, ranges, etc. */
393 rtl_delete_block (basic_block b
)
395 rtx_insn
*insn
, *end
;
397 /* If the head of this block is a CODE_LABEL, then it might be the
398 label for an exception handler which can't be reached. We need
399 to remove the label from the exception_handler_label list. */
402 end
= get_last_bb_insn (b
);
404 /* Selectively delete the entire chain. */
406 delete_insn_chain (insn
, end
, true);
410 fprintf (dump_file
, "deleting block %d\n", b
->index
);
411 df_bb_delete (b
->index
);
414 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
417 compute_bb_for_insn (void)
421 FOR_EACH_BB_FN (bb
, cfun
)
423 rtx_insn
*end
= BB_END (bb
);
426 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
428 BLOCK_FOR_INSN (insn
) = bb
;
435 /* Release the basic_block_for_insn array. */
438 free_bb_for_insn (void)
441 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
442 if (!BARRIER_P (insn
))
443 BLOCK_FOR_INSN (insn
) = NULL
;
449 const pass_data pass_data_free_cfg
=
452 "*free_cfg", /* name */
453 OPTGROUP_NONE
, /* optinfo_flags */
455 0, /* properties_required */
456 0, /* properties_provided */
457 PROP_cfg
, /* properties_destroyed */
458 0, /* todo_flags_start */
459 0, /* todo_flags_finish */
462 class pass_free_cfg
: public rtl_opt_pass
465 pass_free_cfg (gcc::context
*ctxt
)
466 : rtl_opt_pass (pass_data_free_cfg
, ctxt
)
469 /* opt_pass methods: */
470 virtual unsigned int execute (function
*);
472 }; // class pass_free_cfg
475 pass_free_cfg::execute (function
*)
477 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
478 valid at that point so it would be too late to call df_analyze. */
479 if (DELAY_SLOTS
&& optimize
> 0 && flag_delayed_branch
)
481 df_note_add_problem ();
485 if (crtl
->has_bb_partition
)
486 insert_section_boundary_note ();
495 make_pass_free_cfg (gcc::context
*ctxt
)
497 return new pass_free_cfg (ctxt
);
500 /* Return RTX to emit after when we want to emit code on the entry of function. */
502 entry_of_function (void)
504 return (n_basic_blocks_for_fn (cfun
) > NUM_FIXED_BLOCKS
?
505 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
) : get_insns ());
508 /* Emit INSN at the entry point of the function, ensuring that it is only
509 executed once per function. */
511 emit_insn_at_entry (rtx insn
)
513 edge_iterator ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
514 edge e
= ei_safe_edge (ei
);
515 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
517 insert_insn_on_edge (insn
, e
);
518 commit_edge_insertions ();
521 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
522 (or BARRIER if found) and notify df of the bb change.
523 The insn chain range is inclusive
524 (i.e. both BEGIN and END will be updated. */
527 update_bb_for_insn_chain (rtx_insn
*begin
, rtx_insn
*end
, basic_block bb
)
531 end
= NEXT_INSN (end
);
532 for (insn
= begin
; insn
!= end
; insn
= NEXT_INSN (insn
))
533 if (!BARRIER_P (insn
))
534 df_insn_change_bb (insn
, bb
);
537 /* Update BLOCK_FOR_INSN of insns in BB to BB,
538 and notify df of the change. */
541 update_bb_for_insn (basic_block bb
)
543 update_bb_for_insn_chain (BB_HEAD (bb
), BB_END (bb
), bb
);
547 /* Like active_insn_p, except keep the return value clobber around
548 even after reload. */
551 flow_active_insn_p (const rtx_insn
*insn
)
553 if (active_insn_p (insn
))
556 /* A clobber of the function return value exists for buggy
557 programs that fail to return a value. Its effect is to
558 keep the return value from being live across the entire
559 function. If we allow it to be skipped, we introduce the
560 possibility for register lifetime confusion. */
561 if (GET_CODE (PATTERN (insn
)) == CLOBBER
562 && REG_P (XEXP (PATTERN (insn
), 0))
563 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn
), 0)))
569 /* Return true if the block has no effect and only forwards control flow to
570 its single destination. */
573 contains_no_active_insn_p (const_basic_block bb
)
577 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
578 || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
579 || !single_succ_p (bb
)
580 || (single_succ_edge (bb
)->flags
& EDGE_FAKE
) != 0)
583 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
584 if (INSN_P (insn
) && flow_active_insn_p (insn
))
587 return (!INSN_P (insn
)
588 || (JUMP_P (insn
) && simplejump_p (insn
))
589 || !flow_active_insn_p (insn
));
592 /* Likewise, but protect loop latches, headers and preheaders. */
593 /* FIXME: Make this a cfg hook. */
596 forwarder_block_p (const_basic_block bb
)
598 if (!contains_no_active_insn_p (bb
))
601 /* Protect loop latches, headers and preheaders. */
605 if (bb
->loop_father
->header
== bb
)
607 dest
= EDGE_SUCC (bb
, 0)->dest
;
608 if (dest
->loop_father
->header
== dest
)
615 /* Return nonzero if we can reach target from src by falling through. */
616 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
619 can_fallthru (basic_block src
, basic_block target
)
621 rtx_insn
*insn
= BB_END (src
);
626 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
628 if (src
->next_bb
!= target
)
631 /* ??? Later we may add code to move jump tables offline. */
632 if (tablejump_p (insn
, NULL
, NULL
))
635 FOR_EACH_EDGE (e
, ei
, src
->succs
)
636 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
637 && e
->flags
& EDGE_FALLTHRU
)
640 insn2
= BB_HEAD (target
);
641 if (!active_insn_p (insn2
))
642 insn2
= next_active_insn (insn2
);
644 return next_active_insn (insn
) == insn2
;
647 /* Return nonzero if we could reach target from src by falling through,
648 if the target was made adjacent. If we already have a fall-through
649 edge to the exit block, we can't do that. */
651 could_fall_through (basic_block src
, basic_block target
)
656 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
658 FOR_EACH_EDGE (e
, ei
, src
->succs
)
659 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
660 && e
->flags
& EDGE_FALLTHRU
)
665 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
667 bb_note (basic_block bb
)
673 note
= NEXT_INSN (note
);
675 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
676 return as_a
<rtx_note
*> (note
);
679 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
680 note associated with the BLOCK. */
683 first_insn_after_basic_block_note (basic_block block
)
687 /* Get the first instruction in the block. */
688 insn
= BB_HEAD (block
);
690 if (insn
== NULL_RTX
)
693 insn
= NEXT_INSN (insn
);
694 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
696 return NEXT_INSN (insn
);
699 /* Creates a new basic block just after basic block BB by splitting
700 everything after specified instruction INSNP. */
703 rtl_split_block (basic_block bb
, void *insnp
)
706 rtx_insn
*insn
= (rtx_insn
*) insnp
;
712 insn
= first_insn_after_basic_block_note (bb
);
716 rtx_insn
*next
= insn
;
718 insn
= PREV_INSN (insn
);
720 /* If the block contains only debug insns, insn would have
721 been NULL in a non-debug compilation, and then we'd end
722 up emitting a DELETED note. For -fcompare-debug
723 stability, emit the note too. */
724 if (insn
!= BB_END (bb
)
725 && DEBUG_INSN_P (next
)
726 && DEBUG_INSN_P (BB_END (bb
)))
728 while (next
!= BB_END (bb
) && DEBUG_INSN_P (next
))
729 next
= NEXT_INSN (next
);
731 if (next
== BB_END (bb
))
732 emit_note_after (NOTE_INSN_DELETED
, next
);
736 insn
= get_last_insn ();
739 /* We probably should check type of the insn so that we do not create
740 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
742 if (insn
== BB_END (bb
))
743 emit_note_after (NOTE_INSN_DELETED
, insn
);
745 /* Create the new basic block. */
746 new_bb
= create_basic_block (NEXT_INSN (insn
), BB_END (bb
), bb
);
747 BB_COPY_PARTITION (new_bb
, bb
);
750 /* Redirect the outgoing edges. */
751 new_bb
->succs
= bb
->succs
;
753 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
756 /* The new block starts off being dirty. */
757 df_set_bb_dirty (bb
);
761 /* Return true if the single edge between blocks A and B is the only place
762 in RTL which holds some unique locus. */
765 unique_locus_on_edge_between_p (basic_block a
, basic_block b
)
767 const location_t goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
768 rtx_insn
*insn
, *end
;
770 if (LOCATION_LOCUS (goto_locus
) == UNKNOWN_LOCATION
)
773 /* First scan block A backward. */
775 end
= PREV_INSN (BB_HEAD (a
));
776 while (insn
!= end
&& (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
777 insn
= PREV_INSN (insn
);
779 if (insn
!= end
&& INSN_LOCATION (insn
) == goto_locus
)
782 /* Then scan block B forward. */
786 end
= NEXT_INSN (BB_END (b
));
787 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
788 insn
= NEXT_INSN (insn
);
790 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
791 && INSN_LOCATION (insn
) == goto_locus
)
798 /* If the single edge between blocks A and B is the only place in RTL which
799 holds some unique locus, emit a nop with that locus between the blocks. */
802 emit_nop_for_unique_locus_between (basic_block a
, basic_block b
)
804 if (!unique_locus_on_edge_between_p (a
, b
))
807 BB_END (a
) = emit_insn_after_noloc (gen_nop (), BB_END (a
), a
);
808 INSN_LOCATION (BB_END (a
)) = EDGE_SUCC (a
, 0)->goto_locus
;
811 /* Blocks A and B are to be merged into a single block A. The insns
812 are already contiguous. */
815 rtl_merge_blocks (basic_block a
, basic_block b
)
817 rtx_insn
*b_head
= BB_HEAD (b
), *b_end
= BB_END (b
), *a_end
= BB_END (a
);
818 rtx_insn
*del_first
= NULL
, *del_last
= NULL
;
819 rtx_insn
*b_debug_start
= b_end
, *b_debug_end
= b_end
;
820 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
824 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
827 while (DEBUG_INSN_P (b_end
))
828 b_end
= PREV_INSN (b_debug_start
= b_end
);
830 /* If there was a CODE_LABEL beginning B, delete it. */
831 if (LABEL_P (b_head
))
833 /* Detect basic blocks with nothing but a label. This can happen
834 in particular at the end of a function. */
838 del_first
= del_last
= b_head
;
839 b_head
= NEXT_INSN (b_head
);
842 /* Delete the basic block note and handle blocks containing just that
844 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
852 b_head
= NEXT_INSN (b_head
);
855 /* If there was a jump out of A, delete it. */
860 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
862 || NOTE_INSN_BASIC_BLOCK_P (prev
)
863 || prev
== BB_HEAD (a
))
868 /* If this was a conditional jump, we need to also delete
869 the insn that set cc0. */
870 if (HAVE_cc0
&& only_sets_cc0_p (prev
))
872 rtx_insn
*tmp
= prev
;
874 prev
= prev_nonnote_insn (prev
);
880 a_end
= PREV_INSN (del_first
);
882 else if (BARRIER_P (NEXT_INSN (a_end
)))
883 del_first
= NEXT_INSN (a_end
);
885 /* Delete everything marked above as well as crap that might be
886 hanging out between the two blocks. */
888 BB_HEAD (b
) = b_empty
? NULL
: b_head
;
889 delete_insn_chain (del_first
, del_last
, true);
891 /* When not optimizing and the edge is the only place in RTL which holds
892 some unique locus, emit a nop with that locus in between. */
895 emit_nop_for_unique_locus_between (a
, b
);
899 /* Reassociate the insns of B with A. */
902 update_bb_for_insn_chain (a_end
, b_debug_end
, a
);
904 BB_END (a
) = b_debug_end
;
907 else if (b_end
!= b_debug_end
)
909 /* Move any deleted labels and other notes between the end of A
910 and the debug insns that make up B after the debug insns,
911 bringing the debug insns into A while keeping the notes after
913 if (NEXT_INSN (a_end
) != b_debug_start
)
914 reorder_insns_nobb (NEXT_INSN (a_end
), PREV_INSN (b_debug_start
),
916 update_bb_for_insn_chain (b_debug_start
, b_debug_end
, a
);
917 BB_END (a
) = b_debug_end
;
920 df_bb_delete (b
->index
);
922 /* If B was a forwarder block, propagate the locus on the edge. */
924 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
925 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
928 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
932 /* Return true when block A and B can be merged. */
935 rtl_can_merge_blocks (basic_block a
, basic_block b
)
937 /* If we are partitioning hot/cold basic blocks, we don't want to
938 mess up unconditional or indirect jumps that cross between hot
941 Basic block partitioning may result in some jumps that appear to
942 be optimizable (or blocks that appear to be mergeable), but which really
943 must be left untouched (they are required to make it safely across
944 partition boundaries). See the comments at the top of
945 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
947 if (BB_PARTITION (a
) != BB_PARTITION (b
))
950 /* Protect the loop latches. */
951 if (current_loops
&& b
->loop_father
->latch
== b
)
954 /* There must be exactly one edge in between the blocks. */
955 return (single_succ_p (a
)
956 && single_succ (a
) == b
959 /* Must be simple edge. */
960 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
962 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
963 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
964 /* If the jump insn has side effects,
965 we can't kill the edge. */
966 && (!JUMP_P (BB_END (a
))
968 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
971 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
975 block_label (basic_block block
)
977 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
980 if (!LABEL_P (BB_HEAD (block
)))
982 BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
985 return as_a
<rtx_code_label
*> (BB_HEAD (block
));
988 /* Attempt to perform edge redirection by replacing possibly complex jump
989 instruction by unconditional jump or removing jump completely. This can
990 apply only if all edges now point to the same block. The parameters and
991 return values are equivalent to redirect_edge_and_branch. */
994 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
996 basic_block src
= e
->src
;
997 rtx_insn
*insn
= BB_END (src
), *kill_from
;
1001 /* If we are partitioning hot/cold basic blocks, we don't want to
1002 mess up unconditional or indirect jumps that cross between hot
1005 Basic block partitioning may result in some jumps that appear to
1006 be optimizable (or blocks that appear to be mergeable), but which really
1007 must be left untouched (they are required to make it safely across
1008 partition boundaries). See the comments at the top of
1009 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1011 if (BB_PARTITION (src
) != BB_PARTITION (target
))
1014 /* We can replace or remove a complex jump only when we have exactly
1015 two edges. Also, if we have exactly one outgoing edge, we can
1017 if (EDGE_COUNT (src
->succs
) >= 3
1018 /* Verify that all targets will be TARGET. Specifically, the
1019 edge that is not E must also go to TARGET. */
1020 || (EDGE_COUNT (src
->succs
) == 2
1021 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
1024 if (!onlyjump_p (insn
))
1026 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
1029 /* Avoid removing branch with side effects. */
1030 set
= single_set (insn
);
1031 if (!set
|| side_effects_p (set
))
1034 /* In case we zap a conditional jump, we'll need to kill
1035 the cc0 setter too. */
1037 if (HAVE_cc0
&& reg_mentioned_p (cc0_rtx
, PATTERN (insn
))
1038 && only_sets_cc0_p (PREV_INSN (insn
)))
1039 kill_from
= PREV_INSN (insn
);
1041 /* See if we can create the fallthru edge. */
1042 if (in_cfglayout
|| can_fallthru (src
, target
))
1045 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
1048 /* Selectively unlink whole insn chain. */
1051 rtx_insn
*insn
= BB_FOOTER (src
);
1053 delete_insn_chain (kill_from
, BB_END (src
), false);
1055 /* Remove barriers but keep jumptables. */
1058 if (BARRIER_P (insn
))
1060 if (PREV_INSN (insn
))
1061 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1063 BB_FOOTER (src
) = NEXT_INSN (insn
);
1064 if (NEXT_INSN (insn
))
1065 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1069 insn
= NEXT_INSN (insn
);
1073 delete_insn_chain (kill_from
, PREV_INSN (BB_HEAD (target
)),
1077 /* If this already is simplejump, redirect it. */
1078 else if (simplejump_p (insn
))
1080 if (e
->dest
== target
)
1083 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
1084 INSN_UID (insn
), e
->dest
->index
, target
->index
);
1085 if (!redirect_jump (as_a
<rtx_jump_insn
*> (insn
),
1086 block_label (target
), 0))
1088 gcc_assert (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1093 /* Cannot do anything for target exit block. */
1094 else if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1097 /* Or replace possibly complicated jump insn by simple jump insn. */
1100 rtx_code_label
*target_label
= block_label (target
);
1103 rtx_jump_table_data
*table
;
1105 emit_jump_insn_after_noloc (targetm
.gen_jump (target_label
), insn
);
1106 JUMP_LABEL (BB_END (src
)) = target_label
;
1107 LABEL_NUSES (target_label
)++;
1109 fprintf (dump_file
, "Replacing insn %i by jump %i\n",
1110 INSN_UID (insn
), INSN_UID (BB_END (src
)));
1113 delete_insn_chain (kill_from
, insn
, false);
1115 /* Recognize a tablejump that we are converting to a
1116 simple jump and remove its associated CODE_LABEL
1117 and ADDR_VEC or ADDR_DIFF_VEC. */
1118 if (tablejump_p (insn
, &label
, &table
))
1119 delete_insn_chain (label
, table
, false);
1121 barrier
= next_nonnote_insn (BB_END (src
));
1122 if (!barrier
|| !BARRIER_P (barrier
))
1123 emit_barrier_after (BB_END (src
));
1126 if (barrier
!= NEXT_INSN (BB_END (src
)))
1128 /* Move the jump before barrier so that the notes
1129 which originally were or were created before jump table are
1130 inside the basic block. */
1131 rtx_insn
*new_insn
= BB_END (src
);
1133 update_bb_for_insn_chain (NEXT_INSN (BB_END (src
)),
1134 PREV_INSN (barrier
), src
);
1136 SET_NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
1137 SET_PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
1139 SET_NEXT_INSN (new_insn
) = barrier
;
1140 SET_NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
1142 SET_PREV_INSN (new_insn
) = PREV_INSN (barrier
);
1143 SET_PREV_INSN (barrier
) = new_insn
;
1148 /* Keep only one edge out and set proper flags. */
1149 if (!single_succ_p (src
))
1151 gcc_assert (single_succ_p (src
));
1153 e
= single_succ_edge (src
);
1155 e
->flags
= EDGE_FALLTHRU
;
1159 e
->probability
= REG_BR_PROB_BASE
;
1160 e
->count
= src
->count
;
1162 if (e
->dest
!= target
)
1163 redirect_edge_succ (e
, target
);
1167 /* Subroutine of redirect_branch_edge that tries to patch the jump
1168 instruction INSN so that it reaches block NEW. Do this
1169 only when it originally reached block OLD. Return true if this
1170 worked or the original target wasn't OLD, return false if redirection
1174 patch_jump_insn (rtx_insn
*insn
, rtx_insn
*old_label
, basic_block new_bb
)
1176 rtx_jump_table_data
*table
;
1178 /* Recognize a tablejump and adjust all matching cases. */
1179 if (tablejump_p (insn
, NULL
, &table
))
1183 rtx_code_label
*new_label
= block_label (new_bb
);
1185 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1187 vec
= table
->get_labels ();
1189 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
1190 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
1192 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
1193 --LABEL_NUSES (old_label
);
1194 ++LABEL_NUSES (new_label
);
1197 /* Handle casesi dispatch insns. */
1198 if ((tmp
= single_set (insn
)) != NULL
1199 && SET_DEST (tmp
) == pc_rtx
1200 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
1201 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
1202 && label_ref_label (XEXP (SET_SRC (tmp
), 2)) == old_label
)
1204 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
1206 --LABEL_NUSES (old_label
);
1207 ++LABEL_NUSES (new_label
);
1210 else if ((tmp
= extract_asm_operands (PATTERN (insn
))) != NULL
)
1212 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (tmp
);
1215 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1217 rtx_code_label
*new_label
= block_label (new_bb
);
1219 for (i
= 0; i
< n
; ++i
)
1221 rtx old_ref
= ASM_OPERANDS_LABEL (tmp
, i
);
1222 gcc_assert (GET_CODE (old_ref
) == LABEL_REF
);
1223 if (XEXP (old_ref
, 0) == old_label
)
1225 ASM_OPERANDS_LABEL (tmp
, i
)
1226 = gen_rtx_LABEL_REF (Pmode
, new_label
);
1227 --LABEL_NUSES (old_label
);
1228 ++LABEL_NUSES (new_label
);
1232 if (JUMP_LABEL (insn
) == old_label
)
1234 JUMP_LABEL (insn
) = new_label
;
1235 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1237 remove_note (insn
, note
);
1241 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1243 remove_note (insn
, note
);
1244 if (JUMP_LABEL (insn
) != new_label
1245 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1246 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1248 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1250 XEXP (note
, 0) = new_label
;
1254 /* ?? We may play the games with moving the named labels from
1255 one basic block to the other in case only one computed_jump is
1257 if (computed_jump_p (insn
)
1258 /* A return instruction can't be redirected. */
1259 || returnjump_p (insn
))
1262 if (!currently_expanding_to_rtl
|| JUMP_LABEL (insn
) == old_label
)
1264 /* If the insn doesn't go where we think, we're confused. */
1265 gcc_assert (JUMP_LABEL (insn
) == old_label
);
1267 /* If the substitution doesn't succeed, die. This can happen
1268 if the back end emitted unrecognizable instructions or if
1269 target is exit block on some arches. */
1270 if (!redirect_jump (as_a
<rtx_jump_insn
*> (insn
),
1271 block_label (new_bb
), 0))
1273 gcc_assert (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1282 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1285 redirect_branch_edge (edge e
, basic_block target
)
1287 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1288 basic_block src
= e
->src
;
1289 rtx_insn
*insn
= BB_END (src
);
1291 /* We can only redirect non-fallthru edges of jump insn. */
1292 if (e
->flags
& EDGE_FALLTHRU
)
1294 else if (!JUMP_P (insn
) && !currently_expanding_to_rtl
)
1297 if (!currently_expanding_to_rtl
)
1299 if (!patch_jump_insn (as_a
<rtx_jump_insn
*> (insn
), old_label
, target
))
1303 /* When expanding this BB might actually contain multiple
1304 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1305 Redirect all of those that match our label. */
1306 FOR_BB_INSNS (src
, insn
)
1307 if (JUMP_P (insn
) && !patch_jump_insn (as_a
<rtx_jump_insn
*> (insn
),
1312 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
1313 e
->src
->index
, e
->dest
->index
, target
->index
);
1315 if (e
->dest
!= target
)
1316 e
= redirect_edge_succ_nodup (e
, target
);
1321 /* Called when edge E has been redirected to a new destination,
1322 in order to update the region crossing flag on the edge and
1326 fixup_partition_crossing (edge e
)
1328 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || e
->dest
1329 == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1331 /* If we redirected an existing edge, it may already be marked
1332 crossing, even though the new src is missing a reg crossing note.
1333 But make sure reg crossing note doesn't already exist before
1335 if (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1337 e
->flags
|= EDGE_CROSSING
;
1338 if (JUMP_P (BB_END (e
->src
))
1339 && !CROSSING_JUMP_P (BB_END (e
->src
)))
1340 CROSSING_JUMP_P (BB_END (e
->src
)) = 1;
1342 else if (BB_PARTITION (e
->src
) == BB_PARTITION (e
->dest
))
1344 e
->flags
&= ~EDGE_CROSSING
;
1345 /* Remove the section crossing note from jump at end of
1346 src if it exists, and if no other successors are
1348 if (JUMP_P (BB_END (e
->src
)) && CROSSING_JUMP_P (BB_END (e
->src
)))
1350 bool has_crossing_succ
= false;
1353 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
1355 has_crossing_succ
|= (e2
->flags
& EDGE_CROSSING
);
1356 if (has_crossing_succ
)
1359 if (!has_crossing_succ
)
1360 CROSSING_JUMP_P (BB_END (e
->src
)) = 0;
1365 /* Called when block BB has been reassigned to the cold partition,
1366 because it is now dominated by another cold block,
1367 to ensure that the region crossing attributes are updated. */
1370 fixup_new_cold_bb (basic_block bb
)
1375 /* This is called when a hot bb is found to now be dominated
1376 by a cold bb and therefore needs to become cold. Therefore,
1377 its preds will no longer be region crossing. Any non-dominating
1378 preds that were previously hot would also have become cold
1379 in the caller for the same region. Any preds that were previously
1380 region-crossing will be adjusted in fixup_partition_crossing. */
1381 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1383 fixup_partition_crossing (e
);
1386 /* Possibly need to make bb's successor edges region crossing,
1387 or remove stale region crossing. */
1388 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1390 /* We can't have fall-through edges across partition boundaries.
1391 Note that force_nonfallthru will do any necessary partition
1392 boundary fixup by calling fixup_partition_crossing itself. */
1393 if ((e
->flags
& EDGE_FALLTHRU
)
1394 && BB_PARTITION (bb
) != BB_PARTITION (e
->dest
)
1395 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1396 force_nonfallthru (e
);
1398 fixup_partition_crossing (e
);
1402 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1403 expense of adding new instructions or reordering basic blocks.
1405 Function can be also called with edge destination equivalent to the TARGET.
1406 Then it should try the simplifications and do nothing if none is possible.
1408 Return edge representing the branch if transformation succeeded. Return NULL
1410 We still return NULL in case E already destinated TARGET and we didn't
1411 managed to simplify instruction stream. */
1414 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
1417 basic_block src
= e
->src
;
1418 basic_block dest
= e
->dest
;
1420 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1426 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
1428 df_set_bb_dirty (src
);
1429 fixup_partition_crossing (ret
);
1433 ret
= redirect_branch_edge (e
, target
);
1437 df_set_bb_dirty (src
);
1438 fixup_partition_crossing (ret
);
1442 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1445 emit_barrier_after_bb (basic_block bb
)
1447 rtx_barrier
*barrier
= emit_barrier_after (BB_END (bb
));
1448 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1449 || current_ir_type () == IR_RTL_CFGLAYOUT
);
1450 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
1452 rtx_insn
*insn
= unlink_insn_chain (barrier
, barrier
);
1456 rtx_insn
*footer_tail
= BB_FOOTER (bb
);
1458 while (NEXT_INSN (footer_tail
))
1459 footer_tail
= NEXT_INSN (footer_tail
);
1460 if (!BARRIER_P (footer_tail
))
1462 SET_NEXT_INSN (footer_tail
) = insn
;
1463 SET_PREV_INSN (insn
) = footer_tail
;
1467 BB_FOOTER (bb
) = insn
;
1471 /* Like force_nonfallthru below, but additionally performs redirection
1472 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1473 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1474 simple_return_rtx, indicating which kind of returnjump to create.
1475 It should be NULL otherwise. */
1478 force_nonfallthru_and_redirect (edge e
, basic_block target
, rtx jump_label
)
1480 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
1483 int abnormal_edge_flags
= 0;
1484 bool asm_goto_edge
= false;
1487 /* In the case the last instruction is conditional jump to the next
1488 instruction, first redirect the jump itself and then continue
1489 by creating a basic block afterwards to redirect fallthru edge. */
1490 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1491 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1492 && any_condjump_p (BB_END (e
->src
))
1493 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1496 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1499 redirected
= redirect_jump (as_a
<rtx_jump_insn
*> (BB_END (e
->src
)),
1500 block_label (target
), 0);
1501 gcc_assert (redirected
);
1503 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1506 int prob
= XINT (note
, 0);
1508 b
->probability
= prob
;
1509 /* Update this to use GCOV_COMPUTE_SCALE. */
1510 b
->count
= e
->count
* prob
/ REG_BR_PROB_BASE
;
1511 e
->probability
-= e
->probability
;
1512 e
->count
-= b
->count
;
1513 if (e
->probability
< 0)
1520 if (e
->flags
& EDGE_ABNORMAL
)
1522 /* Irritating special case - fallthru edge to the same block as abnormal
1524 We can't redirect abnormal edge, but we still can split the fallthru
1525 one and create separate abnormal edge to original destination.
1526 This allows bb-reorder to make such edge non-fallthru. */
1527 gcc_assert (e
->dest
== target
);
1528 abnormal_edge_flags
= e
->flags
& ~EDGE_FALLTHRU
;
1529 e
->flags
&= EDGE_FALLTHRU
;
1533 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1534 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1536 /* We can't redirect the entry block. Create an empty block
1537 at the start of the function which we use to add the new
1543 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
,
1544 ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1546 /* Change the existing edge's source to be the new block, and add
1547 a new edge from the entry block to the new block. */
1549 for (ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
1550 (tmp
= ei_safe_edge (ei
)); )
1554 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
->unordered_remove (ei
.index
);
1564 vec_safe_push (bb
->succs
, e
);
1565 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
,
1570 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1571 don't point to the target or fallthru label. */
1572 if (JUMP_P (BB_END (e
->src
))
1573 && target
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1574 && (e
->flags
& EDGE_FALLTHRU
)
1575 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
1577 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
1578 bool adjust_jump_target
= false;
1580 for (i
= 0; i
< n
; ++i
)
1582 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (e
->dest
))
1584 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))--;
1585 XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) = block_label (target
);
1586 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))++;
1587 adjust_jump_target
= true;
1589 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (target
))
1590 asm_goto_edge
= true;
1592 if (adjust_jump_target
)
1594 rtx_insn
*insn
= BB_END (e
->src
);
1596 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1597 rtx_insn
*new_label
= BB_HEAD (target
);
1599 if (JUMP_LABEL (insn
) == old_label
)
1601 JUMP_LABEL (insn
) = new_label
;
1602 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1604 remove_note (insn
, note
);
1608 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1610 remove_note (insn
, note
);
1611 if (JUMP_LABEL (insn
) != new_label
1612 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1613 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1615 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1617 XEXP (note
, 0) = new_label
;
1621 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
|| asm_goto_edge
)
1624 gcov_type count
= e
->count
;
1625 int probability
= e
->probability
;
1626 /* Create the new structures. */
1628 /* If the old block ended with a tablejump, skip its table
1629 by searching forward from there. Otherwise start searching
1630 forward from the last instruction of the old block. */
1631 rtx_jump_table_data
*table
;
1632 if (tablejump_p (BB_END (e
->src
), NULL
, &table
))
1635 new_head
= BB_END (e
->src
);
1636 new_head
= NEXT_INSN (new_head
);
1638 jump_block
= create_basic_block (new_head
, NULL
, e
->src
);
1639 jump_block
->count
= count
;
1640 jump_block
->frequency
= EDGE_FREQUENCY (e
);
1642 /* Make sure new block ends up in correct hot/cold section. */
1644 BB_COPY_PARTITION (jump_block
, e
->src
);
1647 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1648 new_edge
->probability
= probability
;
1649 new_edge
->count
= count
;
1651 /* Redirect old edge. */
1652 redirect_edge_pred (e
, jump_block
);
1653 e
->probability
= REG_BR_PROB_BASE
;
1655 /* If e->src was previously region crossing, it no longer is
1656 and the reg crossing note should be removed. */
1657 fixup_partition_crossing (new_edge
);
1659 /* If asm goto has any label refs to target's label,
1660 add also edge from asm goto bb to target. */
1663 new_edge
->probability
/= 2;
1664 new_edge
->count
/= 2;
1665 jump_block
->count
/= 2;
1666 jump_block
->frequency
/= 2;
1667 new_edge
= make_edge (new_edge
->src
, target
,
1668 e
->flags
& ~EDGE_FALLTHRU
);
1669 new_edge
->probability
= probability
- probability
/ 2;
1670 new_edge
->count
= count
- count
/ 2;
1673 new_bb
= jump_block
;
1676 jump_block
= e
->src
;
1678 loc
= e
->goto_locus
;
1679 e
->flags
&= ~EDGE_FALLTHRU
;
1680 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1682 if (jump_label
== ret_rtx
)
1683 emit_jump_insn_after_setloc (targetm
.gen_return (),
1684 BB_END (jump_block
), loc
);
1687 gcc_assert (jump_label
== simple_return_rtx
);
1688 emit_jump_insn_after_setloc (targetm
.gen_simple_return (),
1689 BB_END (jump_block
), loc
);
1691 set_return_jump_label (BB_END (jump_block
));
1695 rtx_code_label
*label
= block_label (target
);
1696 emit_jump_insn_after_setloc (targetm
.gen_jump (label
),
1697 BB_END (jump_block
), loc
);
1698 JUMP_LABEL (BB_END (jump_block
)) = label
;
1699 LABEL_NUSES (label
)++;
1702 /* We might be in cfg layout mode, and if so, the following routine will
1703 insert the barrier correctly. */
1704 emit_barrier_after_bb (jump_block
);
1705 redirect_edge_succ_nodup (e
, target
);
1707 if (abnormal_edge_flags
)
1708 make_edge (src
, target
, abnormal_edge_flags
);
1710 df_mark_solutions_dirty ();
1711 fixup_partition_crossing (e
);
1715 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1716 (and possibly create new basic block) to make edge non-fallthru.
1717 Return newly created BB or NULL if none. */
1720 rtl_force_nonfallthru (edge e
)
1722 return force_nonfallthru_and_redirect (e
, e
->dest
, NULL_RTX
);
1725 /* Redirect edge even at the expense of creating new jump insn or
1726 basic block. Return new basic block if created, NULL otherwise.
1727 Conversion must be possible. */
1730 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1732 if (redirect_edge_and_branch (e
, target
)
1733 || e
->dest
== target
)
1736 /* In case the edge redirection failed, try to force it to be non-fallthru
1737 and redirect newly created simplejump. */
1738 df_set_bb_dirty (e
->src
);
1739 return force_nonfallthru_and_redirect (e
, target
, NULL_RTX
);
1742 /* The given edge should potentially be a fallthru edge. If that is in
1743 fact true, delete the jump and barriers that are in the way. */
1746 rtl_tidy_fallthru_edge (edge e
)
1749 basic_block b
= e
->src
, c
= b
->next_bb
;
1751 /* ??? In a late-running flow pass, other folks may have deleted basic
1752 blocks by nopping out blocks, leaving multiple BARRIERs between here
1753 and the target label. They ought to be chastised and fixed.
1755 We can also wind up with a sequence of undeletable labels between
1756 one block and the next.
1758 So search through a sequence of barriers, labels, and notes for
1759 the head of block C and assert that we really do fall through. */
1761 for (q
= NEXT_INSN (BB_END (b
)); q
!= BB_HEAD (c
); q
= NEXT_INSN (q
))
1765 /* Remove what will soon cease being the jump insn from the source block.
1766 If block B consisted only of this single jump, turn it into a deleted
1771 && (any_uncondjump_p (q
)
1772 || single_succ_p (b
)))
1775 rtx_jump_table_data
*table
;
1777 if (tablejump_p (q
, &label
, &table
))
1779 /* The label is likely mentioned in some instruction before
1780 the tablejump and might not be DCEd, so turn it into
1781 a note instead and move before the tablejump that is going to
1783 const char *name
= LABEL_NAME (label
);
1784 PUT_CODE (label
, NOTE
);
1785 NOTE_KIND (label
) = NOTE_INSN_DELETED_LABEL
;
1786 NOTE_DELETED_LABEL_NAME (label
) = name
;
1787 reorder_insns (label
, label
, PREV_INSN (q
));
1788 delete_insn (table
);
1791 /* If this was a conditional jump, we need to also delete
1792 the insn that set cc0. */
1793 if (HAVE_cc0
&& any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1799 /* Selectively unlink the sequence. */
1800 if (q
!= PREV_INSN (BB_HEAD (c
)))
1801 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1803 e
->flags
|= EDGE_FALLTHRU
;
1806 /* Should move basic block BB after basic block AFTER. NIY. */
1809 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1810 basic_block after ATTRIBUTE_UNUSED
)
1815 /* Locate the last bb in the same partition as START_BB. */
1818 last_bb_in_partition (basic_block start_bb
)
1821 FOR_BB_BETWEEN (bb
, start_bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1823 if (BB_PARTITION (start_bb
) != BB_PARTITION (bb
->next_bb
))
1826 /* Return bb before the exit block. */
1830 /* Split a (typically critical) edge. Return the new block.
1831 The edge must not be abnormal.
1833 ??? The code generally expects to be called on critical edges.
1834 The case of a block ending in an unconditional jump to a
1835 block with multiple predecessors is not handled optimally. */
1838 rtl_split_edge (edge edge_in
)
1840 basic_block bb
, new_bb
;
1843 /* Abnormal edges cannot be split. */
1844 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1846 /* We are going to place the new block in front of edge destination.
1847 Avoid existence of fallthru predecessors. */
1848 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1850 edge e
= find_fallthru_edge (edge_in
->dest
->preds
);
1853 force_nonfallthru (e
);
1856 /* Create the basic block note. */
1857 if (edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1858 before
= BB_HEAD (edge_in
->dest
);
1862 /* If this is a fall through edge to the exit block, the blocks might be
1863 not adjacent, and the right place is after the source. */
1864 if ((edge_in
->flags
& EDGE_FALLTHRU
)
1865 && edge_in
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1867 before
= NEXT_INSN (BB_END (edge_in
->src
));
1868 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1869 BB_COPY_PARTITION (bb
, edge_in
->src
);
1873 if (edge_in
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1875 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1876 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1880 basic_block after
= edge_in
->dest
->prev_bb
;
1881 /* If this is post-bb reordering, and the edge crosses a partition
1882 boundary, the new block needs to be inserted in the bb chain
1883 at the end of the src partition (since we put the new bb into
1884 that partition, see below). Otherwise we may end up creating
1885 an extra partition crossing in the chain, which is illegal.
1886 It can't go after the src, because src may have a fall-through
1887 to a different block. */
1888 if (crtl
->bb_reorder_complete
1889 && (edge_in
->flags
& EDGE_CROSSING
))
1891 after
= last_bb_in_partition (edge_in
->src
);
1892 before
= get_last_bb_insn (after
);
1893 /* The instruction following the last bb in partition should
1894 be a barrier, since it cannot end in a fall-through. */
1895 gcc_checking_assert (BARRIER_P (before
));
1896 before
= NEXT_INSN (before
);
1898 bb
= create_basic_block (before
, NULL
, after
);
1899 /* Put the split bb into the src partition, to avoid creating
1900 a situation where a cold bb dominates a hot bb, in the case
1901 where src is cold and dest is hot. The src will dominate
1902 the new bb (whereas it might not have dominated dest). */
1903 BB_COPY_PARTITION (bb
, edge_in
->src
);
1907 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1909 /* Can't allow a region crossing edge to be fallthrough. */
1910 if (BB_PARTITION (bb
) != BB_PARTITION (edge_in
->dest
)
1911 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1913 new_bb
= force_nonfallthru (single_succ_edge (bb
));
1914 gcc_assert (!new_bb
);
1917 /* For non-fallthru edges, we must adjust the predecessor's
1918 jump instruction to target our new block. */
1919 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1921 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1922 gcc_assert (redirected
);
1926 if (edge_in
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1928 /* For asm goto even splitting of fallthru edge might
1929 need insn patching, as other labels might point to the
1931 rtx_insn
*last
= BB_END (edge_in
->src
);
1934 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1935 && extract_asm_operands (PATTERN (last
)) != NULL_RTX
1936 && patch_jump_insn (last
, before
, bb
))
1937 df_set_bb_dirty (edge_in
->src
);
1939 redirect_edge_succ (edge_in
, bb
);
1945 /* Queue instructions for insertion on an edge between two basic blocks.
1946 The new instructions and basic blocks (if any) will not appear in the
1947 CFG until commit_edge_insertions is called. */
1950 insert_insn_on_edge (rtx pattern
, edge e
)
1952 /* We cannot insert instructions on an abnormal critical edge.
1953 It will be easier to find the culprit if we die now. */
1954 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1956 if (e
->insns
.r
== NULL_RTX
)
1959 push_to_sequence (e
->insns
.r
);
1961 emit_insn (pattern
);
1963 e
->insns
.r
= get_insns ();
1967 /* Update the CFG for the instructions queued on edge E. */
1970 commit_one_edge_insertion (edge e
)
1972 rtx_insn
*before
= NULL
, *after
= NULL
, *insns
, *tmp
, *last
;
1975 /* Pull the insns off the edge now since the edge might go away. */
1979 /* Figure out where to put these insns. If the destination has
1980 one predecessor, insert there. Except for the exit block. */
1981 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1985 /* Get the location correct wrt a code label, and "nice" wrt
1986 a basic block note, and before everything else. */
1989 tmp
= NEXT_INSN (tmp
);
1990 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1991 tmp
= NEXT_INSN (tmp
);
1992 if (tmp
== BB_HEAD (bb
))
1995 after
= PREV_INSN (tmp
);
1997 after
= get_last_insn ();
2000 /* If the source has one successor and the edge is not abnormal,
2001 insert there. Except for the entry block.
2002 Don't do this if the predecessor ends in a jump other than
2003 unconditional simple jump. E.g. for asm goto that points all
2004 its labels at the fallthru basic block, we can't insert instructions
2005 before the asm goto, as the asm goto can have various of side effects,
2006 and can't emit instructions after the asm goto, as it must end
2008 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
2009 && single_succ_p (e
->src
)
2010 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2011 && (!JUMP_P (BB_END (e
->src
))
2012 || simplejump_p (BB_END (e
->src
))))
2016 /* It is possible to have a non-simple jump here. Consider a target
2017 where some forms of unconditional jumps clobber a register. This
2018 happens on the fr30 for example.
2020 We know this block has a single successor, so we can just emit
2021 the queued insns before the jump. */
2022 if (JUMP_P (BB_END (bb
)))
2023 before
= BB_END (bb
);
2026 /* We'd better be fallthru, or we've lost track of what's what. */
2027 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
2029 after
= BB_END (bb
);
2033 /* Otherwise we must split the edge. */
2036 bb
= split_edge (e
);
2038 /* If E crossed a partition boundary, we needed to make bb end in
2039 a region-crossing jump, even though it was originally fallthru. */
2040 if (JUMP_P (BB_END (bb
)))
2041 before
= BB_END (bb
);
2043 after
= BB_END (bb
);
2046 /* Now that we've found the spot, do the insertion. */
2049 emit_insn_before_noloc (insns
, before
, bb
);
2050 last
= prev_nonnote_insn (before
);
2053 last
= emit_insn_after_noloc (insns
, after
, bb
);
2055 if (returnjump_p (last
))
2057 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2058 This is not currently a problem because this only happens
2059 for the (single) epilogue, which already has a fallthru edge
2062 e
= single_succ_edge (bb
);
2063 gcc_assert (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2064 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
2066 e
->flags
&= ~EDGE_FALLTHRU
;
2067 emit_barrier_after (last
);
2070 delete_insn (before
);
2073 gcc_assert (!JUMP_P (last
));
2076 /* Update the CFG for all queued instructions. */
2079 commit_edge_insertions (void)
2083 /* Optimization passes that invoke this routine can cause hot blocks
2084 previously reached by both hot and cold blocks to become dominated only
2085 by cold blocks. This will cause the verification below to fail,
2086 and lead to now cold code in the hot section. In some cases this
2087 may only be visible after newly unreachable blocks are deleted,
2088 which will be done by fixup_partitions. */
2089 fixup_partitions ();
2091 checking_verify_flow_info ();
2093 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
2094 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
2099 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2101 commit_one_edge_insertion (e
);
2106 /* Print out RTL-specific basic block information (live information
2107 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2108 documented in dumpfile.h. */
2111 rtl_dump_bb (FILE *outf
, basic_block bb
, int indent
, int flags
)
2117 s_indent
= (char *) alloca ((size_t) indent
+ 1);
2118 memset (s_indent
, ' ', (size_t) indent
);
2119 s_indent
[indent
] = '\0';
2121 if (df
&& (flags
& TDF_DETAILS
))
2123 df_dump_top (bb
, outf
);
2127 if (bb
->index
!= ENTRY_BLOCK
&& bb
->index
!= EXIT_BLOCK
)
2128 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
)); insn
!= last
;
2129 insn
= NEXT_INSN (insn
))
2131 if (flags
& TDF_DETAILS
)
2132 df_dump_insn_top (insn
, outf
);
2133 if (! (flags
& TDF_SLIM
))
2134 print_rtl_single (outf
, insn
);
2136 dump_insn_slim (outf
, insn
);
2137 if (flags
& TDF_DETAILS
)
2138 df_dump_insn_bottom (insn
, outf
);
2141 if (df
&& (flags
& TDF_DETAILS
))
2143 df_dump_bottom (bb
, outf
);
2149 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2150 for the start of each basic block. FLAGS are the TDF_* masks documented
2154 print_rtl_with_bb (FILE *outf
, const rtx_insn
*rtx_first
, int flags
)
2156 const rtx_insn
*tmp_rtx
;
2158 fprintf (outf
, "(nil)\n");
2161 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
2162 int max_uid
= get_max_uid ();
2163 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
2164 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
2165 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
2168 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2169 insns, but the CFG is not maintained so the basic block info
2170 is not reliable. Therefore it's omitted from the dumps. */
2171 if (! (cfun
->curr_properties
& PROP_cfg
))
2172 flags
&= ~TDF_BLOCKS
;
2175 df_dump_start (outf
);
2177 if (flags
& TDF_BLOCKS
)
2179 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2183 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
2184 end
[INSN_UID (BB_END (bb
))] = bb
;
2185 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
2187 enum bb_state state
= IN_MULTIPLE_BB
;
2189 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
2191 in_bb_p
[INSN_UID (x
)] = state
;
2193 if (x
== BB_END (bb
))
2199 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
2201 if (flags
& TDF_BLOCKS
)
2203 bb
= start
[INSN_UID (tmp_rtx
)];
2206 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, true, false);
2207 if (df
&& (flags
& TDF_DETAILS
))
2208 df_dump_top (bb
, outf
);
2211 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
2212 && !NOTE_P (tmp_rtx
)
2213 && !BARRIER_P (tmp_rtx
))
2214 fprintf (outf
, ";; Insn is not within a basic block\n");
2215 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
2216 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
2219 if (flags
& TDF_DETAILS
)
2220 df_dump_insn_top (tmp_rtx
, outf
);
2221 if (! (flags
& TDF_SLIM
))
2222 print_rtl_single (outf
, tmp_rtx
);
2224 dump_insn_slim (outf
, tmp_rtx
);
2225 if (flags
& TDF_DETAILS
)
2226 df_dump_insn_bottom (tmp_rtx
, outf
);
2228 if (flags
& TDF_BLOCKS
)
2230 bb
= end
[INSN_UID (tmp_rtx
)];
2233 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, false, true);
2234 if (df
&& (flags
& TDF_DETAILS
))
2235 df_dump_bottom (bb
, outf
);
2247 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2250 update_br_prob_note (basic_block bb
)
2253 if (!JUMP_P (BB_END (bb
)))
2255 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
2256 if (!note
|| XINT (note
, 0) == BRANCH_EDGE (bb
)->probability
)
2258 XINT (note
, 0) = BRANCH_EDGE (bb
)->probability
;
2261 /* Get the last insn associated with block BB (that includes barriers and
2262 tablejumps after BB). */
2264 get_last_bb_insn (basic_block bb
)
2266 rtx_jump_table_data
*table
;
2268 rtx_insn
*end
= BB_END (bb
);
2270 /* Include any jump table following the basic block. */
2271 if (tablejump_p (end
, NULL
, &table
))
2274 /* Include any barriers that may follow the basic block. */
2275 tmp
= next_nonnote_insn_bb (end
);
2276 while (tmp
&& BARRIER_P (tmp
))
2279 tmp
= next_nonnote_insn_bb (end
);
2285 /* Sanity check partition hotness to ensure that basic blocks in
2286 Â the cold partition don't dominate basic blocks in the hot partition.
2287 If FLAG_ONLY is true, report violations as errors. Otherwise
2288 re-mark the dominated blocks as cold, since this is run after
2289 cfg optimizations that may make hot blocks previously reached
2290 by both hot and cold blocks now only reachable along cold paths. */
2292 static vec
<basic_block
>
2293 find_partition_fixes (bool flag_only
)
2296 vec
<basic_block
> bbs_in_cold_partition
= vNULL
;
2297 vec
<basic_block
> bbs_to_fix
= vNULL
;
2299 /* Callers check this. */
2300 gcc_checking_assert (crtl
->has_bb_partition
);
2302 FOR_EACH_BB_FN (bb
, cfun
)
2303 if ((BB_PARTITION (bb
) == BB_COLD_PARTITION
))
2304 bbs_in_cold_partition
.safe_push (bb
);
2306 if (bbs_in_cold_partition
.is_empty ())
2309 bool dom_calculated_here
= !dom_info_available_p (CDI_DOMINATORS
);
2311 if (dom_calculated_here
)
2312 calculate_dominance_info (CDI_DOMINATORS
);
2314 while (! bbs_in_cold_partition
.is_empty ())
2316 bb
= bbs_in_cold_partition
.pop ();
2317 /* Any blocks dominated by a block in the cold section
2318 must also be cold. */
2320 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2322 son
= next_dom_son (CDI_DOMINATORS
, son
))
2324 /* If son is not yet cold, then mark it cold here and
2325 enqueue it for further processing. */
2326 if ((BB_PARTITION (son
) != BB_COLD_PARTITION
))
2329 error ("non-cold basic block %d dominated "
2330 "by a block in the cold partition (%d)", son
->index
, bb
->index
);
2332 BB_SET_PARTITION (son
, BB_COLD_PARTITION
);
2333 bbs_to_fix
.safe_push (son
);
2334 bbs_in_cold_partition
.safe_push (son
);
2339 if (dom_calculated_here
)
2340 free_dominance_info (CDI_DOMINATORS
);
2345 /* Perform cleanup on the hot/cold bb partitioning after optimization
2346 passes that modify the cfg. */
2349 fixup_partitions (void)
2353 if (!crtl
->has_bb_partition
)
2356 /* Delete any blocks that became unreachable and weren't
2357 already cleaned up, for example during edge forwarding
2358 and convert_jumps_to_returns. This will expose more
2359 opportunities for fixing the partition boundaries here.
2360 Also, the calculation of the dominance graph during verification
2361 will assert if there are unreachable nodes. */
2362 delete_unreachable_blocks ();
2364 /* If there are partitions, do a sanity check on them: A basic block in
2365 Â a cold partition cannot dominate a basic block in a hot partition.
2366 Fixup any that now violate this requirement, as a result of edge
2367 forwarding and unreachable block deletion. Â */
2368 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (false);
2370 /* Do the partition fixup after all necessary blocks have been converted to
2371 cold, so that we only update the region crossings the minimum number of
2372 places, which can require forcing edges to be non fallthru. */
2373 while (! bbs_to_fix
.is_empty ())
2375 bb
= bbs_to_fix
.pop ();
2376 fixup_new_cold_bb (bb
);
2380 /* Verify, in the basic block chain, that there is at most one switch
2381 between hot/cold partitions. This condition will not be true until
2382 after reorder_basic_blocks is called. */
2385 verify_hot_cold_block_grouping (void)
2389 bool switched_sections
= false;
2390 int current_partition
= BB_UNPARTITIONED
;
2392 /* Even after bb reordering is complete, we go into cfglayout mode
2393 again (in compgoto). Ensure we don't call this before going back
2394 into linearized RTL when any layout fixes would have been committed. */
2395 if (!crtl
->bb_reorder_complete
2396 || current_ir_type () != IR_RTL_CFGRTL
)
2399 FOR_EACH_BB_FN (bb
, cfun
)
2401 if (current_partition
!= BB_UNPARTITIONED
2402 && BB_PARTITION (bb
) != current_partition
)
2404 if (switched_sections
)
2406 error ("multiple hot/cold transitions found (bb %i)",
2411 switched_sections
= true;
2413 if (!crtl
->has_bb_partition
)
2414 error ("partition found but function partition flag not set");
2416 current_partition
= BB_PARTITION (bb
);
2423 /* Perform several checks on the edges out of each block, such as
2424 the consistency of the branch probabilities, the correctness
2425 of hot/cold partition crossing edges, and the number of expected
2426 successor edges. Also verify that the dominance relationship
2427 between hot/cold blocks is sane. */
2430 rtl_verify_edges (void)
2435 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2437 int n_fallthru
= 0, n_branch
= 0, n_abnormal_call
= 0, n_sibcall
= 0;
2438 int n_eh
= 0, n_abnormal
= 0;
2439 edge e
, fallthru
= NULL
;
2442 bool has_crossing_edge
= false;
2444 if (JUMP_P (BB_END (bb
))
2445 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
2446 && EDGE_COUNT (bb
->succs
) >= 2
2447 && any_condjump_p (BB_END (bb
)))
2449 if (XINT (note
, 0) != BRANCH_EDGE (bb
)->probability
2450 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2452 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2453 XINT (note
, 0), BRANCH_EDGE (bb
)->probability
);
2458 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2462 if (e
->flags
& EDGE_FALLTHRU
)
2463 n_fallthru
++, fallthru
= e
;
2465 is_crossing
= (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
2466 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2467 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
2468 has_crossing_edge
|= is_crossing
;
2469 if (e
->flags
& EDGE_CROSSING
)
2473 error ("EDGE_CROSSING incorrectly set across same section");
2476 if (e
->flags
& EDGE_FALLTHRU
)
2478 error ("fallthru edge crosses section boundary in bb %i",
2482 if (e
->flags
& EDGE_EH
)
2484 error ("EH edge crosses section boundary in bb %i",
2488 if (JUMP_P (BB_END (bb
)) && !CROSSING_JUMP_P (BB_END (bb
)))
2490 error ("No region crossing jump at section boundary in bb %i",
2495 else if (is_crossing
)
2497 error ("EDGE_CROSSING missing across section boundary");
2501 if ((e
->flags
& ~(EDGE_DFS_BACK
2503 | EDGE_IRREDUCIBLE_LOOP
2506 | EDGE_PRESERVE
)) == 0)
2509 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2512 if (e
->flags
& EDGE_SIBCALL
)
2515 if (e
->flags
& EDGE_EH
)
2518 if (e
->flags
& EDGE_ABNORMAL
)
2522 if (!has_crossing_edge
2523 && JUMP_P (BB_END (bb
))
2524 && CROSSING_JUMP_P (BB_END (bb
)))
2526 print_rtl_with_bb (stderr
, get_insns (), TDF_RTL
| TDF_BLOCKS
| TDF_DETAILS
);
2527 error ("Region crossing jump across same section in bb %i",
2532 if (n_eh
&& !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
2534 error ("missing REG_EH_REGION note at the end of bb %i", bb
->index
);
2539 error ("too many exception handling edges in bb %i", bb
->index
);
2543 && (!JUMP_P (BB_END (bb
))
2544 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
2545 || any_condjump_p (BB_END (bb
))))))
2547 error ("too many outgoing branch edges from bb %i", bb
->index
);
2550 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
2552 error ("fallthru edge after unconditional jump in bb %i", bb
->index
);
2555 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
2557 error ("wrong number of branch edges after unconditional jump"
2558 " in bb %i", bb
->index
);
2561 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
2562 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
2564 error ("wrong amount of branch edges after conditional jump"
2565 " in bb %i", bb
->index
);
2568 if (n_abnormal_call
&& !CALL_P (BB_END (bb
)))
2570 error ("abnormal call edges for non-call insn in bb %i", bb
->index
);
2573 if (n_sibcall
&& !CALL_P (BB_END (bb
)))
2575 error ("sibcall edges for non-call insn in bb %i", bb
->index
);
2578 if (n_abnormal
> n_eh
2579 && !(CALL_P (BB_END (bb
))
2580 && n_abnormal
== n_abnormal_call
+ n_sibcall
)
2581 && (!JUMP_P (BB_END (bb
))
2582 || any_condjump_p (BB_END (bb
))
2583 || any_uncondjump_p (BB_END (bb
))))
2585 error ("abnormal edges for no purpose in bb %i", bb
->index
);
2590 /* If there are partitions, do a sanity check on them: A basic block in
2591 Â a cold partition cannot dominate a basic block in a hot partition. Â */
2592 if (crtl
->has_bb_partition
&& !err
)
2594 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (true);
2595 err
= !bbs_to_fix
.is_empty ();
2602 /* Checks on the instructions within blocks. Currently checks that each
2603 block starts with a basic block note, and that basic block notes and
2604 control flow jumps are not found in the middle of the block. */
2607 rtl_verify_bb_insns (void)
2613 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2615 /* Now check the header of basic
2616 block. It ought to contain optional CODE_LABEL followed
2617 by NOTE_BASIC_BLOCK. */
2621 if (BB_END (bb
) == x
)
2623 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2631 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2633 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2638 if (BB_END (bb
) == x
)
2639 /* Do checks for empty blocks here. */
2642 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2644 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2646 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2647 INSN_UID (x
), bb
->index
);
2651 if (x
== BB_END (bb
))
2654 if (control_flow_insn_p (x
))
2656 error ("in basic block %d:", bb
->index
);
2657 fatal_insn ("flow control insn inside a basic block", x
);
2666 /* Verify that block pointers for instructions in basic blocks, headers and
2667 footers are set appropriately. */
2670 rtl_verify_bb_pointers (void)
2675 /* Check the general integrity of the basic blocks. */
2676 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2680 if (!(bb
->flags
& BB_RTL
))
2682 error ("BB_RTL flag not set for block %d", bb
->index
);
2686 FOR_BB_INSNS (bb
, insn
)
2687 if (BLOCK_FOR_INSN (insn
) != bb
)
2689 error ("insn %d basic block pointer is %d, should be %d",
2691 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
2696 for (insn
= BB_HEADER (bb
); insn
; insn
= NEXT_INSN (insn
))
2697 if (!BARRIER_P (insn
)
2698 && BLOCK_FOR_INSN (insn
) != NULL
)
2700 error ("insn %d in header of bb %d has non-NULL basic block",
2701 INSN_UID (insn
), bb
->index
);
2704 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
2705 if (!BARRIER_P (insn
)
2706 && BLOCK_FOR_INSN (insn
) != NULL
)
2708 error ("insn %d in footer of bb %d has non-NULL basic block",
2709 INSN_UID (insn
), bb
->index
);
2718 /* Verify the CFG and RTL consistency common for both underlying RTL and
2721 Currently it does following checks:
2723 - overlapping of basic blocks
2724 - insns with wrong BLOCK_FOR_INSN pointers
2725 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2726 - tails of basic blocks (ensure that boundary is necessary)
2727 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2728 and NOTE_INSN_BASIC_BLOCK
2729 - verify that no fall_thru edge crosses hot/cold partition boundaries
2730 - verify that there are no pending RTL branch predictions
2731 - verify that hot blocks are not dominated by cold blocks
2733 In future it can be extended check a lot of other stuff as well
2734 (reachability of basic blocks, life information, etc. etc.). */
2737 rtl_verify_flow_info_1 (void)
2741 err
|= rtl_verify_bb_pointers ();
2743 err
|= rtl_verify_bb_insns ();
2745 err
|= rtl_verify_edges ();
2750 /* Walk the instruction chain and verify that bb head/end pointers
2751 are correct, and that instructions are in exactly one bb and have
2752 correct block pointers. */
2755 rtl_verify_bb_insn_chain (void)
2760 rtx_insn
*last_head
= get_last_insn ();
2761 basic_block
*bb_info
;
2762 const int max_uid
= get_max_uid ();
2764 bb_info
= XCNEWVEC (basic_block
, max_uid
);
2766 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2768 rtx_insn
*head
= BB_HEAD (bb
);
2769 rtx_insn
*end
= BB_END (bb
);
2771 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2773 /* Verify the end of the basic block is in the INSN chain. */
2777 /* And that the code outside of basic blocks has NULL bb field. */
2779 && BLOCK_FOR_INSN (x
) != NULL
)
2781 error ("insn %d outside of basic blocks has non-NULL bb field",
2789 error ("end insn %d for block %d not found in the insn stream",
2790 INSN_UID (end
), bb
->index
);
2794 /* Work backwards from the end to the head of the basic block
2795 to verify the head is in the RTL chain. */
2796 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2798 /* While walking over the insn chain, verify insns appear
2799 in only one basic block. */
2800 if (bb_info
[INSN_UID (x
)] != NULL
)
2802 error ("insn %d is in multiple basic blocks (%d and %d)",
2803 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2807 bb_info
[INSN_UID (x
)] = bb
;
2814 error ("head insn %d for block %d not found in the insn stream",
2815 INSN_UID (head
), bb
->index
);
2819 last_head
= PREV_INSN (x
);
2822 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2824 /* Check that the code before the first basic block has NULL
2827 && BLOCK_FOR_INSN (x
) != NULL
)
2829 error ("insn %d outside of basic blocks has non-NULL bb field",
2839 /* Verify that fallthru edges point to adjacent blocks in layout order and
2840 that barriers exist after non-fallthru blocks. */
2843 rtl_verify_fallthru (void)
2848 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2852 e
= find_fallthru_edge (bb
->succs
);
2857 /* Ensure existence of barrier in BB with no fallthru edges. */
2858 for (insn
= NEXT_INSN (BB_END (bb
)); ; insn
= NEXT_INSN (insn
))
2860 if (!insn
|| NOTE_INSN_BASIC_BLOCK_P (insn
))
2862 error ("missing barrier after block %i", bb
->index
);
2866 if (BARRIER_P (insn
))
2870 else if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2871 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2875 if (e
->src
->next_bb
!= e
->dest
)
2878 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2879 e
->src
->index
, e
->dest
->index
);
2883 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
2884 insn
= NEXT_INSN (insn
))
2885 if (BARRIER_P (insn
) || INSN_P (insn
))
2887 error ("verify_flow_info: Incorrect fallthru %i->%i",
2888 e
->src
->index
, e
->dest
->index
);
2889 fatal_insn ("wrong insn in the fallthru edge", insn
);
2898 /* Verify that blocks are laid out in consecutive order. While walking the
2899 instructions, verify that all expected instructions are inside the basic
2900 blocks, and that all returns are followed by barriers. */
2903 rtl_verify_bb_layout (void)
2909 rtx_insn
* const rtx_first
= get_insns ();
2910 basic_block last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
), curr_bb
= NULL
;
2913 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
2915 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2917 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2919 bb
= NOTE_BASIC_BLOCK (x
);
2922 if (bb
!= last_bb_seen
->next_bb
)
2923 internal_error ("basic blocks not laid down consecutively");
2925 curr_bb
= last_bb_seen
= bb
;
2930 switch (GET_CODE (x
))
2937 /* An ADDR_VEC is placed outside any basic block. */
2939 && JUMP_TABLE_DATA_P (NEXT_INSN (x
)))
2942 /* But in any case, non-deletable labels can appear anywhere. */
2946 fatal_insn ("insn outside basic block", x
);
2951 && returnjump_p (x
) && ! condjump_p (x
)
2952 && ! (next_nonnote_insn (x
) && BARRIER_P (next_nonnote_insn (x
))))
2953 fatal_insn ("return not followed by barrier", x
);
2955 if (curr_bb
&& x
== BB_END (curr_bb
))
2959 if (num_bb_notes
!= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
)
2961 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2962 num_bb_notes
, n_basic_blocks_for_fn (cfun
));
2967 /* Verify the CFG and RTL consistency common for both underlying RTL and
2968 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
2970 Currently it does following checks:
2971 - all checks of rtl_verify_flow_info_1
2972 - test head/end pointers
2973 - check that blocks are laid out in consecutive order
2974 - check that all insns are in the basic blocks
2975 (except the switch handling code, barriers and notes)
2976 - check that all returns are followed by barriers
2977 - check that all fallthru edge points to the adjacent blocks
2978 - verify that there is a single hot/cold partition boundary after bbro */
2981 rtl_verify_flow_info (void)
2985 err
|= rtl_verify_flow_info_1 ();
2987 err
|= rtl_verify_bb_insn_chain ();
2989 err
|= rtl_verify_fallthru ();
2991 err
|= rtl_verify_bb_layout ();
2993 err
|= verify_hot_cold_block_grouping ();
2998 /* Assume that the preceding pass has possibly eliminated jump instructions
2999 or converted the unconditional jumps. Eliminate the edges from CFG.
3000 Return true if any edges are eliminated. */
3003 purge_dead_edges (basic_block bb
)
3006 rtx_insn
*insn
= BB_END (bb
);
3008 bool purged
= false;
3012 if (DEBUG_INSN_P (insn
) && insn
!= BB_HEAD (bb
))
3014 insn
= PREV_INSN (insn
);
3015 while ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
));
3017 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3018 if (NONJUMP_INSN_P (insn
)
3019 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
3023 if (! may_trap_p (PATTERN (insn
))
3024 || ((eqnote
= find_reg_equal_equiv_note (insn
))
3025 && ! may_trap_p (XEXP (eqnote
, 0))))
3026 remove_note (insn
, note
);
3029 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3030 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3032 bool remove
= false;
3034 /* There are three types of edges we need to handle correctly here: EH
3035 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3036 latter can appear when nonlocal gotos are used. */
3037 if (e
->flags
& EDGE_ABNORMAL_CALL
)
3041 else if (can_nonlocal_goto (insn
))
3043 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3045 else if (flag_tm
&& find_reg_note (insn
, REG_TM
, NULL
))
3050 else if (e
->flags
& EDGE_EH
)
3051 remove
= !can_throw_internal (insn
);
3056 df_set_bb_dirty (bb
);
3069 /* We do care only about conditional jumps and simplejumps. */
3070 if (!any_condjump_p (insn
)
3071 && !returnjump_p (insn
)
3072 && !simplejump_p (insn
))
3075 /* Branch probability/prediction notes are defined only for
3076 condjumps. We've possibly turned condjump into simplejump. */
3077 if (simplejump_p (insn
))
3079 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3081 remove_note (insn
, note
);
3082 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
3083 remove_note (insn
, note
);
3086 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3088 /* Avoid abnormal flags to leak from computed jumps turned
3089 into simplejumps. */
3091 e
->flags
&= ~EDGE_ABNORMAL
;
3093 /* See if this edge is one we should keep. */
3094 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
3095 /* A conditional jump can fall through into the next
3096 block, so we should keep the edge. */
3101 else if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3102 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
3103 /* If the destination block is the target of the jump,
3109 else if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
3110 && returnjump_p (insn
))
3111 /* If the destination block is the exit block, and this
3112 instruction is a return, then keep the edge. */
3117 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3118 /* Keep the edges that correspond to exceptions thrown by
3119 this instruction and rematerialize the EDGE_ABNORMAL
3120 flag we just cleared above. */
3122 e
->flags
|= EDGE_ABNORMAL
;
3127 /* We do not need this edge. */
3128 df_set_bb_dirty (bb
);
3133 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
3137 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
3142 /* Redistribute probabilities. */
3143 if (single_succ_p (bb
))
3145 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3146 single_succ_edge (bb
)->count
= bb
->count
;
3150 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3154 b
= BRANCH_EDGE (bb
);
3155 f
= FALLTHRU_EDGE (bb
);
3156 b
->probability
= XINT (note
, 0);
3157 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
3158 /* Update these to use GCOV_COMPUTE_SCALE. */
3159 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
3160 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
3165 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
3167 /* First, there should not be any EH or ABCALL edges resulting
3168 from non-local gotos and the like. If there were, we shouldn't
3169 have created the sibcall in the first place. Second, there
3170 should of course never have been a fallthru edge. */
3171 gcc_assert (single_succ_p (bb
));
3172 gcc_assert (single_succ_edge (bb
)->flags
3173 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
3178 /* If we don't see a jump insn, we don't know exactly why the block would
3179 have been broken at this point. Look for a simple, non-fallthru edge,
3180 as these are only created by conditional branches. If we find such an
3181 edge we know that there used to be a jump here and can then safely
3182 remove all non-fallthru edges. */
3184 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3185 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
3194 /* Remove all but the fake and fallthru edges. The fake edge may be
3195 the only successor for this block in the case of noreturn
3197 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3199 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
3201 df_set_bb_dirty (bb
);
3209 gcc_assert (single_succ_p (bb
));
3211 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3212 single_succ_edge (bb
)->count
= bb
->count
;
3215 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
3220 /* Search all basic blocks for potentially dead edges and purge them. Return
3221 true if some edge has been eliminated. */
3224 purge_all_dead_edges (void)
3229 FOR_EACH_BB_FN (bb
, cfun
)
3231 bool purged_here
= purge_dead_edges (bb
);
3233 purged
|= purged_here
;
3239 /* This is used by a few passes that emit some instructions after abnormal
3240 calls, moving the basic block's end, while they in fact do want to emit
3241 them on the fallthru edge. Look for abnormal call edges, find backward
3242 the call in the block and insert the instructions on the edge instead.
3244 Similarly, handle instructions throwing exceptions internally.
3246 Return true when instructions have been found and inserted on edges. */
3249 fixup_abnormal_edges (void)
3251 bool inserted
= false;
3254 FOR_EACH_BB_FN (bb
, cfun
)
3259 /* Look for cases we are interested in - calls or instructions causing
3261 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3262 if ((e
->flags
& EDGE_ABNORMAL_CALL
)
3263 || ((e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
3264 == (EDGE_ABNORMAL
| EDGE_EH
)))
3267 if (e
&& !CALL_P (BB_END (bb
)) && !can_throw_internal (BB_END (bb
)))
3271 /* Get past the new insns generated. Allow notes, as the insns
3272 may be already deleted. */
3274 while ((NONJUMP_INSN_P (insn
) || NOTE_P (insn
))
3275 && !can_throw_internal (insn
)
3276 && insn
!= BB_HEAD (bb
))
3277 insn
= PREV_INSN (insn
);
3279 if (CALL_P (insn
) || can_throw_internal (insn
))
3281 rtx_insn
*stop
, *next
;
3283 e
= find_fallthru_edge (bb
->succs
);
3285 stop
= NEXT_INSN (BB_END (bb
));
3288 for (insn
= NEXT_INSN (insn
); insn
!= stop
; insn
= next
)
3290 next
= NEXT_INSN (insn
);
3295 /* Sometimes there's still the return value USE.
3296 If it's placed after a trapping call (i.e. that
3297 call is the last insn anyway), we have no fallthru
3298 edge. Simply delete this use and don't try to insert
3299 on the non-existent edge. */
3300 if (GET_CODE (PATTERN (insn
)) != USE
)
3302 /* We're not deleting it, we're moving it. */
3303 insn
->set_undeleted ();
3304 SET_PREV_INSN (insn
) = NULL_RTX
;
3305 SET_NEXT_INSN (insn
) = NULL_RTX
;
3307 insert_insn_on_edge (insn
, e
);
3311 else if (!BARRIER_P (insn
))
3312 set_block_for_insn (insn
, NULL
);
3316 /* It may be that we don't find any trapping insn. In this
3317 case we discovered quite late that the insn that had been
3318 marked as can_throw_internal in fact couldn't trap at all.
3319 So we should in fact delete the EH edges out of the block. */
3321 purge_dead_edges (bb
);
3328 /* Cut the insns from FIRST to LAST out of the insns stream. */
3331 unlink_insn_chain (rtx_insn
*first
, rtx_insn
*last
)
3333 rtx_insn
*prevfirst
= PREV_INSN (first
);
3334 rtx_insn
*nextlast
= NEXT_INSN (last
);
3336 SET_PREV_INSN (first
) = NULL
;
3337 SET_NEXT_INSN (last
) = NULL
;
3339 SET_NEXT_INSN (prevfirst
) = nextlast
;
3341 SET_PREV_INSN (nextlast
) = prevfirst
;
3343 set_last_insn (prevfirst
);
3345 set_first_insn (nextlast
);
3349 /* Skip over inter-block insns occurring after BB which are typically
3350 associated with BB (e.g., barriers). If there are any such insns,
3351 we return the last one. Otherwise, we return the end of BB. */
3354 skip_insns_after_block (basic_block bb
)
3356 rtx_insn
*insn
, *last_insn
, *next_head
, *prev
;
3359 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3360 next_head
= BB_HEAD (bb
->next_bb
);
3362 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
3364 if (insn
== next_head
)
3367 switch (GET_CODE (insn
))
3374 switch (NOTE_KIND (insn
))
3376 case NOTE_INSN_BLOCK_END
:
3386 if (NEXT_INSN (insn
)
3387 && JUMP_TABLE_DATA_P (NEXT_INSN (insn
)))
3389 insn
= NEXT_INSN (insn
);
3402 /* It is possible to hit contradictory sequence. For instance:
3408 Where barrier belongs to jump_insn, but the note does not. This can be
3409 created by removing the basic block originally following
3410 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3412 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
3414 prev
= PREV_INSN (insn
);
3416 switch (NOTE_KIND (insn
))
3418 case NOTE_INSN_BLOCK_END
:
3421 case NOTE_INSN_DELETED
:
3422 case NOTE_INSN_DELETED_LABEL
:
3423 case NOTE_INSN_DELETED_DEBUG_LABEL
:
3426 reorder_insns (insn
, insn
, last_insn
);
3433 /* Locate or create a label for a given basic block. */
3436 label_for_bb (basic_block bb
)
3438 rtx_insn
*label
= BB_HEAD (bb
);
3440 if (!LABEL_P (label
))
3443 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
3445 label
= block_label (bb
);
3451 /* Locate the effective beginning and end of the insn chain for each
3452 block, as defined by skip_insns_after_block above. */
3455 record_effective_endpoints (void)
3457 rtx_insn
*next_insn
;
3461 for (insn
= get_insns ();
3464 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
;
3465 insn
= NEXT_INSN (insn
))
3467 /* No basic blocks at all? */
3470 if (PREV_INSN (insn
))
3471 cfg_layout_function_header
=
3472 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
3474 cfg_layout_function_header
= NULL
;
3476 next_insn
= get_insns ();
3477 FOR_EACH_BB_FN (bb
, cfun
)
3481 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
3482 BB_HEADER (bb
) = unlink_insn_chain (next_insn
,
3483 PREV_INSN (BB_HEAD (bb
)));
3484 end
= skip_insns_after_block (bb
);
3485 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
3486 BB_FOOTER (bb
) = unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
3487 next_insn
= NEXT_INSN (BB_END (bb
));
3490 cfg_layout_function_footer
= next_insn
;
3491 if (cfg_layout_function_footer
)
3492 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
3497 const pass_data pass_data_into_cfg_layout_mode
=
3499 RTL_PASS
, /* type */
3500 "into_cfglayout", /* name */
3501 OPTGROUP_NONE
, /* optinfo_flags */
3503 0, /* properties_required */
3504 PROP_cfglayout
, /* properties_provided */
3505 0, /* properties_destroyed */
3506 0, /* todo_flags_start */
3507 0, /* todo_flags_finish */
3510 class pass_into_cfg_layout_mode
: public rtl_opt_pass
3513 pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3514 : rtl_opt_pass (pass_data_into_cfg_layout_mode
, ctxt
)
3517 /* opt_pass methods: */
3518 virtual unsigned int execute (function
*)
3520 cfg_layout_initialize (0);
3524 }; // class pass_into_cfg_layout_mode
3529 make_pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3531 return new pass_into_cfg_layout_mode (ctxt
);
3536 const pass_data pass_data_outof_cfg_layout_mode
=
3538 RTL_PASS
, /* type */
3539 "outof_cfglayout", /* name */
3540 OPTGROUP_NONE
, /* optinfo_flags */
3542 0, /* properties_required */
3543 0, /* properties_provided */
3544 PROP_cfglayout
, /* properties_destroyed */
3545 0, /* todo_flags_start */
3546 0, /* todo_flags_finish */
3549 class pass_outof_cfg_layout_mode
: public rtl_opt_pass
3552 pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3553 : rtl_opt_pass (pass_data_outof_cfg_layout_mode
, ctxt
)
3556 /* opt_pass methods: */
3557 virtual unsigned int execute (function
*);
3559 }; // class pass_outof_cfg_layout_mode
3562 pass_outof_cfg_layout_mode::execute (function
*fun
)
3566 FOR_EACH_BB_FN (bb
, fun
)
3567 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3568 bb
->aux
= bb
->next_bb
;
3570 cfg_layout_finalize ();
3578 make_pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3580 return new pass_outof_cfg_layout_mode (ctxt
);
3584 /* Link the basic blocks in the correct order, compacting the basic
3585 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3586 function also clears the basic block header and footer fields.
3588 This function is usually called after a pass (e.g. tracer) finishes
3589 some transformations while in cfglayout mode. The required sequence
3590 of the basic blocks is in a linked list along the bb->aux field.
3591 This functions re-links the basic block prev_bb and next_bb pointers
3592 accordingly, and it compacts and renumbers the blocks.
3594 FIXME: This currently works only for RTL, but the only RTL-specific
3595 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3596 to GIMPLE a long time ago, but it doesn't relink the basic block
3597 chain. It could do that (to give better initial RTL) if this function
3598 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3601 relink_block_chain (bool stay_in_cfglayout_mode
)
3603 basic_block bb
, prev_bb
;
3606 /* Maybe dump the re-ordered sequence. */
3609 fprintf (dump_file
, "Reordered sequence:\n");
3610 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, index
=
3613 bb
= (basic_block
) bb
->aux
, index
++)
3615 fprintf (dump_file
, " %i ", index
);
3616 if (get_bb_original (bb
))
3617 fprintf (dump_file
, "duplicate of %i ",
3618 get_bb_original (bb
)->index
);
3619 else if (forwarder_block_p (bb
)
3620 && !LABEL_P (BB_HEAD (bb
)))
3621 fprintf (dump_file
, "compensation ");
3623 fprintf (dump_file
, "bb %i ", bb
->index
);
3624 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
3628 /* Now reorder the blocks. */
3629 prev_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
3630 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
3631 for (; bb
; prev_bb
= bb
, bb
= (basic_block
) bb
->aux
)
3633 bb
->prev_bb
= prev_bb
;
3634 prev_bb
->next_bb
= bb
;
3636 prev_bb
->next_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
3637 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
= prev_bb
;
3639 /* Then, clean up the aux fields. */
3640 FOR_ALL_BB_FN (bb
, cfun
)
3643 if (!stay_in_cfglayout_mode
)
3644 BB_HEADER (bb
) = BB_FOOTER (bb
) = NULL
;
3647 /* Maybe reset the original copy tables, they are not valid anymore
3648 when we renumber the basic blocks in compact_blocks. If we are
3649 are going out of cfglayout mode, don't re-allocate the tables. */
3650 free_original_copy_tables ();
3651 if (stay_in_cfglayout_mode
)
3652 initialize_original_copy_tables ();
3654 /* Finally, put basic_block_info in the new order. */
3659 /* Given a reorder chain, rearrange the code to match. */
3662 fixup_reorder_chain (void)
3665 rtx_insn
*insn
= NULL
;
3667 if (cfg_layout_function_header
)
3669 set_first_insn (cfg_layout_function_header
);
3670 insn
= cfg_layout_function_header
;
3671 while (NEXT_INSN (insn
))
3672 insn
= NEXT_INSN (insn
);
3675 /* First do the bulk reordering -- rechain the blocks without regard to
3676 the needed changes to jumps and labels. */
3678 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3684 SET_NEXT_INSN (insn
) = BB_HEADER (bb
);
3686 set_first_insn (BB_HEADER (bb
));
3687 SET_PREV_INSN (BB_HEADER (bb
)) = insn
;
3688 insn
= BB_HEADER (bb
);
3689 while (NEXT_INSN (insn
))
3690 insn
= NEXT_INSN (insn
);
3693 SET_NEXT_INSN (insn
) = BB_HEAD (bb
);
3695 set_first_insn (BB_HEAD (bb
));
3696 SET_PREV_INSN (BB_HEAD (bb
)) = insn
;
3700 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
3701 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
3702 while (NEXT_INSN (insn
))
3703 insn
= NEXT_INSN (insn
);
3707 SET_NEXT_INSN (insn
) = cfg_layout_function_footer
;
3708 if (cfg_layout_function_footer
)
3709 SET_PREV_INSN (cfg_layout_function_footer
) = insn
;
3711 while (NEXT_INSN (insn
))
3712 insn
= NEXT_INSN (insn
);
3714 set_last_insn (insn
);
3716 verify_insn_chain ();
3718 /* Now add jumps and labels as needed to match the blocks new
3721 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3724 edge e_fall
, e_taken
, e
;
3725 rtx_insn
*bb_end_insn
;
3726 rtx ret_label
= NULL_RTX
;
3730 if (EDGE_COUNT (bb
->succs
) == 0)
3733 /* Find the old fallthru edge, and another non-EH edge for
3735 e_taken
= e_fall
= NULL
;
3737 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3738 if (e
->flags
& EDGE_FALLTHRU
)
3740 else if (! (e
->flags
& EDGE_EH
))
3743 bb_end_insn
= BB_END (bb
);
3744 if (rtx_jump_insn
*bb_end_jump
= dyn_cast
<rtx_jump_insn
*> (bb_end_insn
))
3746 ret_label
= JUMP_LABEL (bb_end_jump
);
3747 if (any_condjump_p (bb_end_jump
))
3749 /* This might happen if the conditional jump has side
3750 effects and could therefore not be optimized away.
3751 Make the basic block to end with a barrier in order
3752 to prevent rtl_verify_flow_info from complaining. */
3755 gcc_assert (!onlyjump_p (bb_end_jump
)
3756 || returnjump_p (bb_end_jump
)
3757 || (e_taken
->flags
& EDGE_CROSSING
));
3758 emit_barrier_after (bb_end_jump
);
3762 /* If the old fallthru is still next, nothing to do. */
3763 if (bb
->aux
== e_fall
->dest
3764 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3767 /* The degenerated case of conditional jump jumping to the next
3768 instruction can happen for jumps with side effects. We need
3769 to construct a forwarder block and this will be done just
3770 fine by force_nonfallthru below. */
3774 /* There is another special case: if *neither* block is next,
3775 such as happens at the very end of a function, then we'll
3776 need to add a new unconditional jump. Choose the taken
3777 edge based on known or assumed probability. */
3778 else if (bb
->aux
!= e_taken
->dest
)
3780 rtx note
= find_reg_note (bb_end_jump
, REG_BR_PROB
, 0);
3783 && XINT (note
, 0) < REG_BR_PROB_BASE
/ 2
3784 && invert_jump (bb_end_jump
,
3786 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3788 : label_for_bb (e_fall
->dest
)), 0))
3790 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3791 gcc_checking_assert (could_fall_through
3792 (e_taken
->src
, e_taken
->dest
));
3793 e_taken
->flags
|= EDGE_FALLTHRU
;
3794 update_br_prob_note (bb
);
3795 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
3799 /* If the "jumping" edge is a crossing edge, and the fall
3800 through edge is non-crossing, leave things as they are. */
3801 else if ((e_taken
->flags
& EDGE_CROSSING
)
3802 && !(e_fall
->flags
& EDGE_CROSSING
))
3805 /* Otherwise we can try to invert the jump. This will
3806 basically never fail, however, keep up the pretense. */
3807 else if (invert_jump (bb_end_jump
,
3809 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3811 : label_for_bb (e_fall
->dest
)), 0))
3813 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3814 gcc_checking_assert (could_fall_through
3815 (e_taken
->src
, e_taken
->dest
));
3816 e_taken
->flags
|= EDGE_FALLTHRU
;
3817 update_br_prob_note (bb
);
3818 if (LABEL_NUSES (ret_label
) == 0
3819 && single_pred_p (e_taken
->dest
))
3820 delete_insn (ret_label
);
3824 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
3826 /* If the old fallthru is still next or if
3827 asm goto doesn't have a fallthru (e.g. when followed by
3828 __builtin_unreachable ()), nothing to do. */
3830 || bb
->aux
== e_fall
->dest
3831 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3834 /* Otherwise we'll have to use the fallthru fixup below. */
3838 /* Otherwise we have some return, switch or computed
3839 jump. In the 99% case, there should not have been a
3841 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
3847 /* No fallthru implies a noreturn function with EH edges, or
3848 something similarly bizarre. In any case, we don't need to
3853 /* If the fallthru block is still next, nothing to do. */
3854 if (bb
->aux
== e_fall
->dest
)
3857 /* A fallthru to exit block. */
3858 if (e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3862 /* We got here if we need to add a new jump insn.
3863 Note force_nonfallthru can delete E_FALL and thus we have to
3864 save E_FALL->src prior to the call to force_nonfallthru. */
3865 nb
= force_nonfallthru_and_redirect (e_fall
, e_fall
->dest
, ret_label
);
3870 /* Don't process this new block. */
3875 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3877 /* Annoying special case - jump around dead jumptables left in the code. */
3878 FOR_EACH_BB_FN (bb
, cfun
)
3880 edge e
= find_fallthru_edge (bb
->succs
);
3882 if (e
&& !can_fallthru (e
->src
, e
->dest
))
3883 force_nonfallthru (e
);
3886 /* Ensure goto_locus from edges has some instructions with that locus
3889 FOR_EACH_BB_FN (bb
, cfun
)
3894 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3895 if (LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
3896 && !(e
->flags
& EDGE_ABNORMAL
))
3900 basic_block dest
, nb
;
3903 insn
= BB_END (e
->src
);
3904 end
= PREV_INSN (BB_HEAD (e
->src
));
3906 && (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
3907 insn
= PREV_INSN (insn
);
3909 && INSN_LOCATION (insn
) == e
->goto_locus
)
3911 if (simplejump_p (BB_END (e
->src
))
3912 && !INSN_HAS_LOCATION (BB_END (e
->src
)))
3914 INSN_LOCATION (BB_END (e
->src
)) = e
->goto_locus
;
3918 if (dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3920 /* Non-fallthru edges to the exit block cannot be split. */
3921 if (!(e
->flags
& EDGE_FALLTHRU
))
3926 insn
= BB_HEAD (dest
);
3927 end
= NEXT_INSN (BB_END (dest
));
3928 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
3929 insn
= NEXT_INSN (insn
);
3930 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
3931 && INSN_LOCATION (insn
) == e
->goto_locus
)
3934 nb
= split_edge (e
);
3935 if (!INSN_P (BB_END (nb
)))
3936 BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
3938 INSN_LOCATION (BB_END (nb
)) = e
->goto_locus
;
3940 /* If there are other incoming edges to the destination block
3941 with the same goto locus, redirect them to the new block as
3942 well, this can prevent other such blocks from being created
3943 in subsequent iterations of the loop. */
3944 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
3945 if (LOCATION_LOCUS (e2
->goto_locus
) != UNKNOWN_LOCATION
3946 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
3947 && e
->goto_locus
== e2
->goto_locus
)
3948 redirect_edge_and_branch (e2
, nb
);
3955 /* Perform sanity checks on the insn chain.
3956 1. Check that next/prev pointers are consistent in both the forward and
3958 2. Count insns in chain, going both directions, and check if equal.
3959 3. Check that get_last_insn () returns the actual end of chain. */
3962 verify_insn_chain (void)
3964 rtx_insn
*x
, *prevx
, *nextx
;
3965 int insn_cnt1
, insn_cnt2
;
3967 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
3969 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
3970 gcc_assert (PREV_INSN (x
) == prevx
);
3972 gcc_assert (prevx
== get_last_insn ());
3974 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
3976 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
3977 gcc_assert (NEXT_INSN (x
) == nextx
);
3979 gcc_assert (insn_cnt1
== insn_cnt2
);
3982 /* If we have assembler epilogues, the block falling through to exit must
3983 be the last one in the reordered chain when we reach final. Ensure
3984 that this condition is met. */
3986 fixup_fallthru_exit_predecessor (void)
3989 basic_block bb
= NULL
;
3991 /* This transformation is not valid before reload, because we might
3992 separate a call from the instruction that copies the return
3994 gcc_assert (reload_completed
);
3996 e
= find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4002 basic_block c
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
4004 /* If the very first block is the one with the fall-through exit
4005 edge, we have to split that block. */
4008 bb
= split_block_after_labels (bb
)->dest
;
4011 BB_FOOTER (bb
) = BB_FOOTER (c
);
4012 BB_FOOTER (c
) = NULL
;
4015 while (c
->aux
!= bb
)
4016 c
= (basic_block
) c
->aux
;
4020 c
= (basic_block
) c
->aux
;
4027 /* In case there are more than one fallthru predecessors of exit, force that
4028 there is only one. */
4031 force_one_exit_fallthru (void)
4033 edge e
, predecessor
= NULL
;
4036 basic_block forwarder
, bb
;
4038 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
4039 if (e
->flags
& EDGE_FALLTHRU
)
4041 if (predecessor
== NULL
)
4053 /* Exit has several fallthru predecessors. Create a forwarder block for
4055 forwarder
= split_edge (predecessor
);
4056 for (ei
= ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4057 (e
= ei_safe_edge (ei
)); )
4059 if (e
->src
== forwarder
4060 || !(e
->flags
& EDGE_FALLTHRU
))
4063 redirect_edge_and_branch_force (e
, forwarder
);
4066 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4068 FOR_EACH_BB_FN (bb
, cfun
)
4070 if (bb
->aux
== NULL
&& bb
!= forwarder
)
4072 bb
->aux
= forwarder
;
4078 /* Return true in case it is possible to duplicate the basic block BB. */
4081 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
4083 /* Do not attempt to duplicate tablejumps, as we need to unshare
4084 the dispatch table. This is difficult to do, as the instructions
4085 computing jump destination may be hoisted outside the basic block. */
4086 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
4089 /* Do not duplicate blocks containing insns that can't be copied. */
4090 if (targetm
.cannot_copy_insn_p
)
4092 rtx_insn
*insn
= BB_HEAD (bb
);
4095 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
4097 if (insn
== BB_END (bb
))
4099 insn
= NEXT_INSN (insn
);
4107 duplicate_insn_chain (rtx_insn
*from
, rtx_insn
*to
)
4109 rtx_insn
*insn
, *next
, *copy
;
4112 /* Avoid updating of boundaries of previous basic block. The
4113 note will get removed from insn stream in fixup. */
4114 last
= emit_note (NOTE_INSN_DELETED
);
4116 /* Create copy at the end of INSN chain. The chain will
4117 be reordered later. */
4118 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
4120 switch (GET_CODE (insn
))
4123 /* Don't duplicate label debug insns. */
4124 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
)
4130 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
4131 if (JUMP_P (insn
) && JUMP_LABEL (insn
) != NULL_RTX
4132 && ANY_RETURN_P (JUMP_LABEL (insn
)))
4133 JUMP_LABEL (copy
) = JUMP_LABEL (insn
);
4134 maybe_copy_prologue_epilogue_insn (insn
, copy
);
4137 case JUMP_TABLE_DATA
:
4138 /* Avoid copying of dispatch tables. We never duplicate
4139 tablejumps, so this can hit only in case the table got
4140 moved far from original jump.
4141 Avoid copying following barrier as well if any
4142 (and debug insns in between). */
4143 for (next
= NEXT_INSN (insn
);
4144 next
!= NEXT_INSN (to
);
4145 next
= NEXT_INSN (next
))
4146 if (!DEBUG_INSN_P (next
))
4148 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
4160 switch (NOTE_KIND (insn
))
4162 /* In case prologue is empty and function contain label
4163 in first BB, we may want to copy the block. */
4164 case NOTE_INSN_PROLOGUE_END
:
4166 case NOTE_INSN_DELETED
:
4167 case NOTE_INSN_DELETED_LABEL
:
4168 case NOTE_INSN_DELETED_DEBUG_LABEL
:
4169 /* No problem to strip these. */
4170 case NOTE_INSN_FUNCTION_BEG
:
4171 /* There is always just single entry to function. */
4172 case NOTE_INSN_BASIC_BLOCK
:
4173 /* We should only switch text sections once. */
4174 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
4177 case NOTE_INSN_EPILOGUE_BEG
:
4178 case NOTE_INSN_UPDATE_SJLJ_CONTEXT
:
4179 emit_note_copy (as_a
<rtx_note
*> (insn
));
4183 /* All other notes should have already been eliminated. */
4191 insn
= NEXT_INSN (last
);
4196 /* Create a duplicate of the basic block BB. */
4199 cfg_layout_duplicate_bb (basic_block bb
)
4204 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
4205 new_bb
= create_basic_block (insn
,
4206 insn
? get_last_insn () : NULL
,
4207 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
);
4209 BB_COPY_PARTITION (new_bb
, bb
);
4212 insn
= BB_HEADER (bb
);
4213 while (NEXT_INSN (insn
))
4214 insn
= NEXT_INSN (insn
);
4215 insn
= duplicate_insn_chain (BB_HEADER (bb
), insn
);
4217 BB_HEADER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4222 insn
= BB_FOOTER (bb
);
4223 while (NEXT_INSN (insn
))
4224 insn
= NEXT_INSN (insn
);
4225 insn
= duplicate_insn_chain (BB_FOOTER (bb
), insn
);
4227 BB_FOOTER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4234 /* Main entry point to this module - initialize the datastructures for
4235 CFG layout changes. It keeps LOOPS up-to-date if not null.
4237 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4240 cfg_layout_initialize (unsigned int flags
)
4245 /* Once bb partitioning is complete, cfg layout mode should not be
4246 re-entered. Entering cfg layout mode may require fixups. As an
4247 example, if edge forwarding performed when optimizing the cfg
4248 layout required moving a block from the hot to the cold
4249 section. This would create an illegal partitioning unless some
4250 manual fixup was performed. */
4251 gcc_assert (!(crtl
->bb_reorder_complete
4252 && flag_reorder_blocks_and_partition
));
4254 initialize_original_copy_tables ();
4256 cfg_layout_rtl_register_cfg_hooks ();
4258 record_effective_endpoints ();
4260 /* Make sure that the targets of non local gotos are marked. */
4261 for (x
= nonlocal_goto_handler_labels
; x
; x
= x
->next ())
4263 bb
= BLOCK_FOR_INSN (x
->insn ());
4264 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
4267 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
4270 /* Splits superblocks. */
4272 break_superblocks (void)
4277 auto_sbitmap
superblocks (last_basic_block_for_fn (cfun
));
4278 bitmap_clear (superblocks
);
4280 FOR_EACH_BB_FN (bb
, cfun
)
4281 if (bb
->flags
& BB_SUPERBLOCK
)
4283 bb
->flags
&= ~BB_SUPERBLOCK
;
4284 bitmap_set_bit (superblocks
, bb
->index
);
4290 rebuild_jump_labels (get_insns ());
4291 find_many_sub_basic_blocks (superblocks
);
4295 /* Finalize the changes: reorder insn list according to the sequence specified
4296 by aux pointers, enter compensation code, rebuild scope forest. */
4299 cfg_layout_finalize (void)
4301 checking_verify_flow_info ();
4302 free_dominance_info (CDI_DOMINATORS
);
4303 force_one_exit_fallthru ();
4304 rtl_register_cfg_hooks ();
4305 if (reload_completed
&& !targetm
.have_epilogue ())
4306 fixup_fallthru_exit_predecessor ();
4307 fixup_reorder_chain ();
4309 rebuild_jump_labels (get_insns ());
4310 delete_dead_jumptables ();
4313 verify_insn_chain ();
4314 checking_verify_flow_info ();
4318 /* Same as split_block but update cfg_layout structures. */
4321 cfg_layout_split_block (basic_block bb
, void *insnp
)
4323 rtx insn
= (rtx
) insnp
;
4324 basic_block new_bb
= rtl_split_block (bb
, insn
);
4326 BB_FOOTER (new_bb
) = BB_FOOTER (bb
);
4327 BB_FOOTER (bb
) = NULL
;
4332 /* Redirect Edge to DEST. */
4334 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
4336 basic_block src
= e
->src
;
4339 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4342 if (e
->dest
== dest
)
4345 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4346 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
4348 df_set_bb_dirty (src
);
4352 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4353 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
4356 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
4357 e
->src
->index
, dest
->index
);
4359 df_set_bb_dirty (e
->src
);
4360 redirect_edge_succ (e
, dest
);
4364 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4365 in the case the basic block appears to be in sequence. Avoid this
4368 if (e
->flags
& EDGE_FALLTHRU
)
4370 /* Redirect any branch edges unified with the fallthru one. */
4371 if (JUMP_P (BB_END (src
))
4372 && label_is_jump_target_p (BB_HEAD (e
->dest
),
4378 fprintf (dump_file
, "Fallthru edge unified with branch "
4379 "%i->%i redirected to %i\n",
4380 e
->src
->index
, e
->dest
->index
, dest
->index
);
4381 e
->flags
&= ~EDGE_FALLTHRU
;
4382 redirected
= redirect_branch_edge (e
, dest
);
4383 gcc_assert (redirected
);
4384 redirected
->flags
|= EDGE_FALLTHRU
;
4385 df_set_bb_dirty (redirected
->src
);
4388 /* In case we are redirecting fallthru edge to the branch edge
4389 of conditional jump, remove it. */
4390 if (EDGE_COUNT (src
->succs
) == 2)
4392 /* Find the edge that is different from E. */
4393 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
4396 && any_condjump_p (BB_END (src
))
4397 && onlyjump_p (BB_END (src
)))
4398 delete_insn (BB_END (src
));
4401 fprintf (dump_file
, "Redirecting fallthru edge %i->%i to %i\n",
4402 e
->src
->index
, e
->dest
->index
, dest
->index
);
4403 ret
= redirect_edge_succ_nodup (e
, dest
);
4406 ret
= redirect_branch_edge (e
, dest
);
4408 /* We don't want simplejumps in the insn stream during cfglayout. */
4409 gcc_assert (!simplejump_p (BB_END (src
)));
4411 df_set_bb_dirty (src
);
4415 /* Simple wrapper as we always can redirect fallthru edges. */
4417 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
4419 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
4421 gcc_assert (redirected
);
4425 /* Same as delete_basic_block but update cfg_layout structures. */
4428 cfg_layout_delete_block (basic_block bb
)
4430 rtx_insn
*insn
, *next
, *prev
= PREV_INSN (BB_HEAD (bb
)), *remaints
;
4435 next
= BB_HEAD (bb
);
4437 SET_NEXT_INSN (prev
) = BB_HEADER (bb
);
4439 set_first_insn (BB_HEADER (bb
));
4440 SET_PREV_INSN (BB_HEADER (bb
)) = prev
;
4441 insn
= BB_HEADER (bb
);
4442 while (NEXT_INSN (insn
))
4443 insn
= NEXT_INSN (insn
);
4444 SET_NEXT_INSN (insn
) = next
;
4445 SET_PREV_INSN (next
) = insn
;
4447 next
= NEXT_INSN (BB_END (bb
));
4450 insn
= BB_FOOTER (bb
);
4453 if (BARRIER_P (insn
))
4455 if (PREV_INSN (insn
))
4456 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
4458 BB_FOOTER (bb
) = NEXT_INSN (insn
);
4459 if (NEXT_INSN (insn
))
4460 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
4464 insn
= NEXT_INSN (insn
);
4469 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
4470 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
4471 while (NEXT_INSN (insn
))
4472 insn
= NEXT_INSN (insn
);
4473 SET_NEXT_INSN (insn
) = next
;
4475 SET_PREV_INSN (next
) = insn
;
4477 set_last_insn (insn
);
4480 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
4481 to
= &BB_HEADER (bb
->next_bb
);
4483 to
= &cfg_layout_function_footer
;
4485 rtl_delete_block (bb
);
4488 prev
= NEXT_INSN (prev
);
4490 prev
= get_insns ();
4492 next
= PREV_INSN (next
);
4494 next
= get_last_insn ();
4496 if (next
&& NEXT_INSN (next
) != prev
)
4498 remaints
= unlink_insn_chain (prev
, next
);
4500 while (NEXT_INSN (insn
))
4501 insn
= NEXT_INSN (insn
);
4502 SET_NEXT_INSN (insn
) = *to
;
4504 SET_PREV_INSN (*to
) = insn
;
4509 /* Return true when blocks A and B can be safely merged. */
4512 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
4514 /* If we are partitioning hot/cold basic blocks, we don't want to
4515 mess up unconditional or indirect jumps that cross between hot
4518 Basic block partitioning may result in some jumps that appear to
4519 be optimizable (or blocks that appear to be mergeable), but which really
4520 must be left untouched (they are required to make it safely across
4521 partition boundaries). See the comments at the top of
4522 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4524 if (BB_PARTITION (a
) != BB_PARTITION (b
))
4527 /* Protect the loop latches. */
4528 if (current_loops
&& b
->loop_father
->latch
== b
)
4531 /* If we would end up moving B's instructions, make sure it doesn't fall
4532 through into the exit block, since we cannot recover from a fallthrough
4533 edge into the exit block occurring in the middle of a function. */
4534 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4536 edge e
= find_fallthru_edge (b
->succs
);
4537 if (e
&& e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4541 /* There must be exactly one edge in between the blocks. */
4542 return (single_succ_p (a
)
4543 && single_succ (a
) == b
4544 && single_pred_p (b
) == 1
4546 /* Must be simple edge. */
4547 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
4548 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4549 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
4550 /* If the jump insn has side effects, we can't kill the edge.
4551 When not optimizing, try_redirect_by_replacing_jump will
4552 not allow us to redirect an edge by replacing a table jump. */
4553 && (!JUMP_P (BB_END (a
))
4554 || ((!optimize
|| reload_completed
)
4555 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
4558 /* Merge block A and B. The blocks must be mergeable. */
4561 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
4563 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
4566 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a
, b
));
4569 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
4572 /* If there was a CODE_LABEL beginning B, delete it. */
4573 if (LABEL_P (BB_HEAD (b
)))
4575 delete_insn (BB_HEAD (b
));
4578 /* We should have fallthru edge in a, or we can do dummy redirection to get
4580 if (JUMP_P (BB_END (a
)))
4581 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
4582 gcc_assert (!JUMP_P (BB_END (a
)));
4584 /* When not optimizing and the edge is the only place in RTL which holds
4585 some unique locus, emit a nop with that locus in between. */
4587 emit_nop_for_unique_locus_between (a
, b
);
4589 /* Move things from b->footer after a->footer. */
4593 BB_FOOTER (a
) = BB_FOOTER (b
);
4596 rtx_insn
*last
= BB_FOOTER (a
);
4598 while (NEXT_INSN (last
))
4599 last
= NEXT_INSN (last
);
4600 SET_NEXT_INSN (last
) = BB_FOOTER (b
);
4601 SET_PREV_INSN (BB_FOOTER (b
)) = last
;
4603 BB_FOOTER (b
) = NULL
;
4606 /* Move things from b->header before a->footer.
4607 Note that this may include dead tablejump data, but we don't clean
4608 those up until we go out of cfglayout mode. */
4611 if (! BB_FOOTER (a
))
4612 BB_FOOTER (a
) = BB_HEADER (b
);
4615 rtx_insn
*last
= BB_HEADER (b
);
4617 while (NEXT_INSN (last
))
4618 last
= NEXT_INSN (last
);
4619 SET_NEXT_INSN (last
) = BB_FOOTER (a
);
4620 SET_PREV_INSN (BB_FOOTER (a
)) = last
;
4621 BB_FOOTER (a
) = BB_HEADER (b
);
4623 BB_HEADER (b
) = NULL
;
4626 /* In the case basic blocks are not adjacent, move them around. */
4627 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4629 insn
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
4631 emit_insn_after_noloc (insn
, BB_END (a
), a
);
4633 /* Otherwise just re-associate the instructions. */
4637 BB_END (a
) = BB_END (b
);
4640 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4641 We need to explicitly call. */
4642 update_bb_for_insn_chain (insn
, BB_END (b
), a
);
4644 /* Skip possible DELETED_LABEL insn. */
4645 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
4646 insn
= NEXT_INSN (insn
);
4647 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4648 BB_HEAD (b
) = BB_END (b
) = NULL
;
4651 df_bb_delete (b
->index
);
4653 /* If B was a forwarder block, propagate the locus on the edge. */
4655 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
4656 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
4659 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
4665 cfg_layout_split_edge (edge e
)
4667 basic_block new_bb
=
4668 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4669 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
4672 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4673 BB_COPY_PARTITION (new_bb
, e
->src
);
4675 BB_COPY_PARTITION (new_bb
, e
->dest
);
4676 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
4677 redirect_edge_and_branch_force (e
, new_bb
);
4682 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4685 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
4689 /* Return true if BB contains only labels or non-executable
4693 rtl_block_empty_p (basic_block bb
)
4697 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4698 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4701 FOR_BB_INSNS (bb
, insn
)
4702 if (NONDEBUG_INSN_P (insn
) && !any_uncondjump_p (insn
))
4708 /* Split a basic block if it ends with a conditional branch and if
4709 the other part of the block is not empty. */
4712 rtl_split_block_before_cond_jump (basic_block bb
)
4715 rtx_insn
*split_point
= NULL
;
4716 rtx_insn
*last
= NULL
;
4717 bool found_code
= false;
4719 FOR_BB_INSNS (bb
, insn
)
4721 if (any_condjump_p (insn
))
4723 else if (NONDEBUG_INSN_P (insn
))
4728 /* Did not find everything. */
4729 if (found_code
&& split_point
)
4730 return split_block (bb
, split_point
)->dest
;
4735 /* Return 1 if BB ends with a call, possibly followed by some
4736 instructions that must stay with the call, 0 otherwise. */
4739 rtl_block_ends_with_call_p (basic_block bb
)
4741 rtx_insn
*insn
= BB_END (bb
);
4743 while (!CALL_P (insn
)
4744 && insn
!= BB_HEAD (bb
)
4745 && (keep_with_call_p (insn
)
4747 || DEBUG_INSN_P (insn
)))
4748 insn
= PREV_INSN (insn
);
4749 return (CALL_P (insn
));
4752 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4755 rtl_block_ends_with_condjump_p (const_basic_block bb
)
4757 return any_condjump_p (BB_END (bb
));
4760 /* Return true if we need to add fake edge to exit.
4761 Helper function for rtl_flow_call_edges_add. */
4764 need_fake_edge_p (const rtx_insn
*insn
)
4770 && !SIBLING_CALL_P (insn
)
4771 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
4772 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
4775 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
4776 && MEM_VOLATILE_P (PATTERN (insn
)))
4777 || (GET_CODE (PATTERN (insn
)) == PARALLEL
4778 && asm_noperands (insn
) != -1
4779 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
4780 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
4783 /* Add fake edges to the function exit for any non constant and non noreturn
4784 calls, volatile inline assembly in the bitmap of blocks specified by
4785 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4788 The goal is to expose cases in which entering a basic block does not imply
4789 that all subsequent instructions must be executed. */
4792 rtl_flow_call_edges_add (sbitmap blocks
)
4795 int blocks_split
= 0;
4796 int last_bb
= last_basic_block_for_fn (cfun
);
4797 bool check_last_block
= false;
4799 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
4803 check_last_block
= true;
4805 check_last_block
= bitmap_bit_p (blocks
,
4806 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
->index
);
4808 /* In the last basic block, before epilogue generation, there will be
4809 a fallthru edge to EXIT. Special care is required if the last insn
4810 of the last basic block is a call because make_edge folds duplicate
4811 edges, which would result in the fallthru edge also being marked
4812 fake, which would result in the fallthru edge being removed by
4813 remove_fake_edges, which would result in an invalid CFG.
4815 Moreover, we can't elide the outgoing fake edge, since the block
4816 profiler needs to take this into account in order to solve the minimal
4817 spanning tree in the case that the call doesn't return.
4819 Handle this by adding a dummy instruction in a new last basic block. */
4820 if (check_last_block
)
4822 basic_block bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
4823 rtx_insn
*insn
= BB_END (bb
);
4825 /* Back up past insns that must be kept in the same block as a call. */
4826 while (insn
!= BB_HEAD (bb
)
4827 && keep_with_call_p (insn
))
4828 insn
= PREV_INSN (insn
);
4830 if (need_fake_edge_p (insn
))
4834 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4837 insert_insn_on_edge (gen_use (const0_rtx
), e
);
4838 commit_edge_insertions ();
4843 /* Now add fake edges to the function exit for any non constant
4844 calls since there is no way that we can determine if they will
4847 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
4849 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
4851 rtx_insn
*prev_insn
;
4856 if (blocks
&& !bitmap_bit_p (blocks
, i
))
4859 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
4861 prev_insn
= PREV_INSN (insn
);
4862 if (need_fake_edge_p (insn
))
4865 rtx_insn
*split_at_insn
= insn
;
4867 /* Don't split the block between a call and an insn that should
4868 remain in the same block as the call. */
4870 while (split_at_insn
!= BB_END (bb
)
4871 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
4872 split_at_insn
= NEXT_INSN (split_at_insn
);
4874 /* The handling above of the final block before the epilogue
4875 should be enough to verify that there is no edge to the exit
4876 block in CFG already. Calling make_edge in such case would
4877 cause us to mark that edge as fake and remove it later. */
4879 if (flag_checking
&& split_at_insn
== BB_END (bb
))
4881 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4882 gcc_assert (e
== NULL
);
4885 /* Note that the following may create a new basic block
4886 and renumber the existing basic blocks. */
4887 if (split_at_insn
!= BB_END (bb
))
4889 e
= split_block (bb
, split_at_insn
);
4894 make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
4897 if (insn
== BB_HEAD (bb
))
4903 verify_flow_info ();
4905 return blocks_split
;
4908 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4909 the conditional branch target, SECOND_HEAD should be the fall-thru
4910 there is no need to handle this here the loop versioning code handles
4911 this. the reason for SECON_HEAD is that it is needed for condition
4912 in trees, and this should be of the same type since it is a hook. */
4914 rtl_lv_add_condition_to_bb (basic_block first_head
,
4915 basic_block second_head ATTRIBUTE_UNUSED
,
4916 basic_block cond_bb
, void *comp_rtx
)
4918 rtx_code_label
*label
;
4919 rtx_insn
*seq
, *jump
;
4920 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
4921 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
4922 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
4926 label
= block_label (first_head
);
4927 mode
= GET_MODE (op0
);
4928 if (mode
== VOIDmode
)
4929 mode
= GET_MODE (op1
);
4932 op0
= force_operand (op0
, NULL_RTX
);
4933 op1
= force_operand (op1
, NULL_RTX
);
4934 do_compare_rtx_and_jump (op0
, op1
, comp
, 0, mode
, NULL_RTX
, NULL
, label
, -1);
4935 jump
= get_last_insn ();
4936 JUMP_LABEL (jump
) = label
;
4937 LABEL_NUSES (label
)++;
4941 /* Add the new cond, in the new head. */
4942 emit_insn_after (seq
, BB_END (cond_bb
));
4946 /* Given a block B with unconditional branch at its end, get the
4947 store the return the branch edge and the fall-thru edge in
4948 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4950 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
4951 edge
*fallthru_edge
)
4953 edge e
= EDGE_SUCC (b
, 0);
4955 if (e
->flags
& EDGE_FALLTHRU
)
4958 *branch_edge
= EDGE_SUCC (b
, 1);
4963 *fallthru_edge
= EDGE_SUCC (b
, 1);
4968 init_rtl_bb_info (basic_block bb
)
4970 gcc_assert (!bb
->il
.x
.rtl
);
4971 bb
->il
.x
.head_
= NULL
;
4972 bb
->il
.x
.rtl
= ggc_cleared_alloc
<rtl_bb_info
> ();
4975 /* Returns true if it is possible to remove edge E by redirecting
4976 it to the destination of the other edge from E->src. */
4979 rtl_can_remove_branch_p (const_edge e
)
4981 const_basic_block src
= e
->src
;
4982 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
4983 const rtx_insn
*insn
= BB_END (src
);
4986 /* The conditions are taken from try_redirect_by_replacing_jump. */
4987 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4990 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4993 if (BB_PARTITION (src
) != BB_PARTITION (target
))
4996 if (!onlyjump_p (insn
)
4997 || tablejump_p (insn
, NULL
, NULL
))
5000 set
= single_set (insn
);
5001 if (!set
|| side_effects_p (set
))
5008 rtl_duplicate_bb (basic_block bb
)
5010 bb
= cfg_layout_duplicate_bb (bb
);
5015 /* Do book-keeping of basic block BB for the profile consistency checker.
5016 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
5017 then do post-pass accounting. Store the counting in RECORD. */
5019 rtl_account_profile_record (basic_block bb
, int after_pass
,
5020 struct profile_record
*record
)
5023 FOR_BB_INSNS (bb
, insn
)
5026 record
->size
[after_pass
]
5027 += insn_rtx_cost (PATTERN (insn
), false);
5028 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
5029 record
->time
[after_pass
]
5030 += insn_rtx_cost (PATTERN (insn
), true) * bb
->count
;
5031 else if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
5032 record
->time
[after_pass
]
5033 += insn_rtx_cost (PATTERN (insn
), true) * bb
->frequency
;
5037 /* Implementation of CFG manipulation for linearized RTL. */
5038 struct cfg_hooks rtl_cfg_hooks
= {
5040 rtl_verify_flow_info
,
5042 rtl_dump_bb_for_graph
,
5043 rtl_create_basic_block
,
5044 rtl_redirect_edge_and_branch
,
5045 rtl_redirect_edge_and_branch_force
,
5046 rtl_can_remove_branch_p
,
5049 rtl_move_block_after
,
5050 rtl_can_merge_blocks
, /* can_merge_blocks_p */
5054 cfg_layout_can_duplicate_bb_p
,
5057 rtl_make_forwarder_block
,
5058 rtl_tidy_fallthru_edge
,
5059 rtl_force_nonfallthru
,
5060 rtl_block_ends_with_call_p
,
5061 rtl_block_ends_with_condjump_p
,
5062 rtl_flow_call_edges_add
,
5063 NULL
, /* execute_on_growing_pred */
5064 NULL
, /* execute_on_shrinking_pred */
5065 NULL
, /* duplicate loop for trees */
5066 NULL
, /* lv_add_condition_to_bb */
5067 NULL
, /* lv_adjust_loop_header_phi*/
5068 NULL
, /* extract_cond_bb_edges */
5069 NULL
, /* flush_pending_stmts */
5070 rtl_block_empty_p
, /* block_empty_p */
5071 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5072 rtl_account_profile_record
,
5075 /* Implementation of CFG manipulation for cfg layout RTL, where
5076 basic block connected via fallthru edges does not have to be adjacent.
5077 This representation will hopefully become the default one in future
5078 version of the compiler. */
5080 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
5082 rtl_verify_flow_info_1
,
5084 rtl_dump_bb_for_graph
,
5085 cfg_layout_create_basic_block
,
5086 cfg_layout_redirect_edge_and_branch
,
5087 cfg_layout_redirect_edge_and_branch_force
,
5088 rtl_can_remove_branch_p
,
5089 cfg_layout_delete_block
,
5090 cfg_layout_split_block
,
5091 rtl_move_block_after
,
5092 cfg_layout_can_merge_blocks_p
,
5093 cfg_layout_merge_blocks
,
5096 cfg_layout_can_duplicate_bb_p
,
5097 cfg_layout_duplicate_bb
,
5098 cfg_layout_split_edge
,
5099 rtl_make_forwarder_block
,
5100 NULL
, /* tidy_fallthru_edge */
5101 rtl_force_nonfallthru
,
5102 rtl_block_ends_with_call_p
,
5103 rtl_block_ends_with_condjump_p
,
5104 rtl_flow_call_edges_add
,
5105 NULL
, /* execute_on_growing_pred */
5106 NULL
, /* execute_on_shrinking_pred */
5107 duplicate_loop_to_header_edge
, /* duplicate loop for trees */
5108 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
5109 NULL
, /* lv_adjust_loop_header_phi*/
5110 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
5111 NULL
, /* flush_pending_stmts */
5112 rtl_block_empty_p
, /* block_empty_p */
5113 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5114 rtl_account_profile_record
,
5117 #include "gt-cfgrtl.h"