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"
54 #include "cfgcleanup.h"
55 #include "bb-reorder.h"
56 #include "rtl-error.h"
57 #include "insn-attr.h"
61 #include "tree-pass.h"
62 #include "print-rtl.h"
64 /* Holds the interesting leading and trailing notes for the function.
65 Only applicable if the CFG is in cfglayout mode. */
66 static GTY(()) rtx_insn
*cfg_layout_function_footer
;
67 static GTY(()) rtx_insn
*cfg_layout_function_header
;
69 static rtx_insn
*skip_insns_after_block (basic_block
);
70 static void record_effective_endpoints (void);
71 static void fixup_reorder_chain (void);
73 void verify_insn_chain (void);
74 static void fixup_fallthru_exit_predecessor (void);
75 static int can_delete_note_p (const rtx_note
*);
76 static int can_delete_label_p (const rtx_code_label
*);
77 static basic_block
rtl_split_edge (edge
);
78 static bool rtl_move_block_after (basic_block
, basic_block
);
79 static int rtl_verify_flow_info (void);
80 static basic_block
cfg_layout_split_block (basic_block
, void *);
81 static edge
cfg_layout_redirect_edge_and_branch (edge
, basic_block
);
82 static basic_block
cfg_layout_redirect_edge_and_branch_force (edge
, basic_block
);
83 static void cfg_layout_delete_block (basic_block
);
84 static void rtl_delete_block (basic_block
);
85 static basic_block
rtl_redirect_edge_and_branch_force (edge
, basic_block
);
86 static edge
rtl_redirect_edge_and_branch (edge
, basic_block
);
87 static basic_block
rtl_split_block (basic_block
, void *);
88 static void rtl_dump_bb (FILE *, basic_block
, int, int);
89 static int rtl_verify_flow_info_1 (void);
90 static void rtl_make_forwarder_block (edge
);
92 /* Return true if NOTE is not one of the ones that must be kept paired,
93 so that we may simply delete it. */
96 can_delete_note_p (const rtx_note
*note
)
98 switch (NOTE_KIND (note
))
100 case NOTE_INSN_DELETED
:
101 case NOTE_INSN_BASIC_BLOCK
:
102 case NOTE_INSN_EPILOGUE_BEG
:
110 /* True if a given label can be deleted. */
113 can_delete_label_p (const rtx_code_label
*label
)
115 return (!LABEL_PRESERVE_P (label
)
116 /* User declared labels must be preserved. */
117 && LABEL_NAME (label
) == 0
118 && !in_insn_list_p (forced_labels
, label
));
121 /* Delete INSN by patching it out. */
124 delete_insn (rtx uncast_insn
)
126 rtx_insn
*insn
= as_a
<rtx_insn
*> (uncast_insn
);
128 bool really_delete
= true;
132 /* Some labels can't be directly removed from the INSN chain, as they
133 might be references via variables, constant pool etc.
134 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
135 if (! can_delete_label_p (as_a
<rtx_code_label
*> (insn
)))
137 const char *name
= LABEL_NAME (insn
);
138 basic_block bb
= BLOCK_FOR_INSN (insn
);
139 rtx_insn
*bb_note
= NEXT_INSN (insn
);
141 really_delete
= false;
142 PUT_CODE (insn
, NOTE
);
143 NOTE_KIND (insn
) = NOTE_INSN_DELETED_LABEL
;
144 NOTE_DELETED_LABEL_NAME (insn
) = name
;
146 /* If the note following the label starts a basic block, and the
147 label is a member of the same basic block, interchange the two. */
148 if (bb_note
!= NULL_RTX
149 && NOTE_INSN_BASIC_BLOCK_P (bb_note
)
151 && bb
== BLOCK_FOR_INSN (bb_note
))
153 reorder_insns_nobb (insn
, insn
, bb_note
);
154 BB_HEAD (bb
) = bb_note
;
155 if (BB_END (bb
) == bb_note
)
160 remove_node_from_insn_list (insn
, &nonlocal_goto_handler_labels
);
165 /* If this insn has already been deleted, something is very wrong. */
166 gcc_assert (!insn
->deleted ());
168 df_insn_delete (insn
);
170 insn
->set_deleted ();
173 /* If deleting a jump, decrement the use count of the label. Deleting
174 the label itself should happen in the normal course of block merging. */
177 if (JUMP_LABEL (insn
)
178 && LABEL_P (JUMP_LABEL (insn
)))
179 LABEL_NUSES (JUMP_LABEL (insn
))--;
181 /* If there are more targets, remove them too. */
183 = find_reg_note (insn
, REG_LABEL_TARGET
, NULL_RTX
)) != NULL_RTX
184 && LABEL_P (XEXP (note
, 0)))
186 LABEL_NUSES (XEXP (note
, 0))--;
187 remove_note (insn
, note
);
191 /* Also if deleting any insn that references a label as an operand. */
192 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, NULL_RTX
)) != NULL_RTX
193 && LABEL_P (XEXP (note
, 0)))
195 LABEL_NUSES (XEXP (note
, 0))--;
196 remove_note (insn
, note
);
199 if (rtx_jump_table_data
*table
= dyn_cast
<rtx_jump_table_data
*> (insn
))
201 rtvec vec
= table
->get_labels ();
202 int len
= GET_NUM_ELEM (vec
);
205 for (i
= 0; i
< len
; i
++)
207 rtx label
= XEXP (RTVEC_ELT (vec
, i
), 0);
209 /* When deleting code in bulk (e.g. removing many unreachable
210 blocks) we can delete a label that's a target of the vector
211 before deleting the vector itself. */
213 LABEL_NUSES (label
)--;
218 /* Like delete_insn but also purge dead edges from BB.
219 Return true if any edges are eliminated. */
222 delete_insn_and_edges (rtx_insn
*insn
)
227 && BLOCK_FOR_INSN (insn
)
228 && BB_END (BLOCK_FOR_INSN (insn
)) == insn
)
232 return purge_dead_edges (BLOCK_FOR_INSN (insn
));
236 /* Unlink a chain of insns between START and FINISH, leaving notes
237 that must be paired. If CLEAR_BB is true, we set bb field for
238 insns that cannot be removed to NULL. */
241 delete_insn_chain (rtx start
, rtx finish
, bool clear_bb
)
243 rtx_insn
*prev
, *current
;
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 current
= safe_as_a
<rtx_insn
*> (finish
);
251 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 rtx_insn
*lab
= safe_as_a
<rtx_insn
*> (label
);
1788 reorder_insns (lab
, lab
, PREV_INSN (q
));
1789 delete_insn (table
);
1792 /* If this was a conditional jump, we need to also delete
1793 the insn that set cc0. */
1794 if (HAVE_cc0
&& any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1800 /* Selectively unlink the sequence. */
1801 if (q
!= PREV_INSN (BB_HEAD (c
)))
1802 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1804 e
->flags
|= EDGE_FALLTHRU
;
1807 /* Should move basic block BB after basic block AFTER. NIY. */
1810 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1811 basic_block after ATTRIBUTE_UNUSED
)
1816 /* Locate the last bb in the same partition as START_BB. */
1819 last_bb_in_partition (basic_block start_bb
)
1822 FOR_BB_BETWEEN (bb
, start_bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1824 if (BB_PARTITION (start_bb
) != BB_PARTITION (bb
->next_bb
))
1827 /* Return bb before the exit block. */
1831 /* Split a (typically critical) edge. Return the new block.
1832 The edge must not be abnormal.
1834 ??? The code generally expects to be called on critical edges.
1835 The case of a block ending in an unconditional jump to a
1836 block with multiple predecessors is not handled optimally. */
1839 rtl_split_edge (edge edge_in
)
1841 basic_block bb
, new_bb
;
1844 /* Abnormal edges cannot be split. */
1845 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1847 /* We are going to place the new block in front of edge destination.
1848 Avoid existence of fallthru predecessors. */
1849 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1851 edge e
= find_fallthru_edge (edge_in
->dest
->preds
);
1854 force_nonfallthru (e
);
1857 /* Create the basic block note. */
1858 if (edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1859 before
= BB_HEAD (edge_in
->dest
);
1863 /* If this is a fall through edge to the exit block, the blocks might be
1864 not adjacent, and the right place is after the source. */
1865 if ((edge_in
->flags
& EDGE_FALLTHRU
)
1866 && edge_in
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1868 before
= NEXT_INSN (BB_END (edge_in
->src
));
1869 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1870 BB_COPY_PARTITION (bb
, edge_in
->src
);
1874 if (edge_in
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1876 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1877 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1881 basic_block after
= edge_in
->dest
->prev_bb
;
1882 /* If this is post-bb reordering, and the edge crosses a partition
1883 boundary, the new block needs to be inserted in the bb chain
1884 at the end of the src partition (since we put the new bb into
1885 that partition, see below). Otherwise we may end up creating
1886 an extra partition crossing in the chain, which is illegal.
1887 It can't go after the src, because src may have a fall-through
1888 to a different block. */
1889 if (crtl
->bb_reorder_complete
1890 && (edge_in
->flags
& EDGE_CROSSING
))
1892 after
= last_bb_in_partition (edge_in
->src
);
1893 before
= get_last_bb_insn (after
);
1894 /* The instruction following the last bb in partition should
1895 be a barrier, since it cannot end in a fall-through. */
1896 gcc_checking_assert (BARRIER_P (before
));
1897 before
= NEXT_INSN (before
);
1899 bb
= create_basic_block (before
, NULL
, after
);
1900 /* Put the split bb into the src partition, to avoid creating
1901 a situation where a cold bb dominates a hot bb, in the case
1902 where src is cold and dest is hot. The src will dominate
1903 the new bb (whereas it might not have dominated dest). */
1904 BB_COPY_PARTITION (bb
, edge_in
->src
);
1908 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1910 /* Can't allow a region crossing edge to be fallthrough. */
1911 if (BB_PARTITION (bb
) != BB_PARTITION (edge_in
->dest
)
1912 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1914 new_bb
= force_nonfallthru (single_succ_edge (bb
));
1915 gcc_assert (!new_bb
);
1918 /* For non-fallthru edges, we must adjust the predecessor's
1919 jump instruction to target our new block. */
1920 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1922 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1923 gcc_assert (redirected
);
1927 if (edge_in
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1929 /* For asm goto even splitting of fallthru edge might
1930 need insn patching, as other labels might point to the
1932 rtx_insn
*last
= BB_END (edge_in
->src
);
1935 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1936 && extract_asm_operands (PATTERN (last
)) != NULL_RTX
1937 && patch_jump_insn (last
, before
, bb
))
1938 df_set_bb_dirty (edge_in
->src
);
1940 redirect_edge_succ (edge_in
, bb
);
1946 /* Queue instructions for insertion on an edge between two basic blocks.
1947 The new instructions and basic blocks (if any) will not appear in the
1948 CFG until commit_edge_insertions is called. */
1951 insert_insn_on_edge (rtx pattern
, edge e
)
1953 /* We cannot insert instructions on an abnormal critical edge.
1954 It will be easier to find the culprit if we die now. */
1955 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1957 if (e
->insns
.r
== NULL_RTX
)
1960 push_to_sequence (e
->insns
.r
);
1962 emit_insn (pattern
);
1964 e
->insns
.r
= get_insns ();
1968 /* Update the CFG for the instructions queued on edge E. */
1971 commit_one_edge_insertion (edge e
)
1973 rtx_insn
*before
= NULL
, *after
= NULL
, *insns
, *tmp
, *last
;
1976 /* Pull the insns off the edge now since the edge might go away. */
1980 /* Figure out where to put these insns. If the destination has
1981 one predecessor, insert there. Except for the exit block. */
1982 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1986 /* Get the location correct wrt a code label, and "nice" wrt
1987 a basic block note, and before everything else. */
1990 tmp
= NEXT_INSN (tmp
);
1991 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1992 tmp
= NEXT_INSN (tmp
);
1993 if (tmp
== BB_HEAD (bb
))
1996 after
= PREV_INSN (tmp
);
1998 after
= get_last_insn ();
2001 /* If the source has one successor and the edge is not abnormal,
2002 insert there. Except for the entry block.
2003 Don't do this if the predecessor ends in a jump other than
2004 unconditional simple jump. E.g. for asm goto that points all
2005 its labels at the fallthru basic block, we can't insert instructions
2006 before the asm goto, as the asm goto can have various of side effects,
2007 and can't emit instructions after the asm goto, as it must end
2009 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
2010 && single_succ_p (e
->src
)
2011 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2012 && (!JUMP_P (BB_END (e
->src
))
2013 || simplejump_p (BB_END (e
->src
))))
2017 /* It is possible to have a non-simple jump here. Consider a target
2018 where some forms of unconditional jumps clobber a register. This
2019 happens on the fr30 for example.
2021 We know this block has a single successor, so we can just emit
2022 the queued insns before the jump. */
2023 if (JUMP_P (BB_END (bb
)))
2024 before
= BB_END (bb
);
2027 /* We'd better be fallthru, or we've lost track of what's what. */
2028 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
2030 after
= BB_END (bb
);
2034 /* Otherwise we must split the edge. */
2037 bb
= split_edge (e
);
2039 /* If E crossed a partition boundary, we needed to make bb end in
2040 a region-crossing jump, even though it was originally fallthru. */
2041 if (JUMP_P (BB_END (bb
)))
2042 before
= BB_END (bb
);
2044 after
= BB_END (bb
);
2047 /* Now that we've found the spot, do the insertion. */
2050 emit_insn_before_noloc (insns
, before
, bb
);
2051 last
= prev_nonnote_insn (before
);
2054 last
= emit_insn_after_noloc (insns
, after
, bb
);
2056 if (returnjump_p (last
))
2058 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2059 This is not currently a problem because this only happens
2060 for the (single) epilogue, which already has a fallthru edge
2063 e
= single_succ_edge (bb
);
2064 gcc_assert (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2065 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
2067 e
->flags
&= ~EDGE_FALLTHRU
;
2068 emit_barrier_after (last
);
2071 delete_insn (before
);
2074 gcc_assert (!JUMP_P (last
));
2077 /* Update the CFG for all queued instructions. */
2080 commit_edge_insertions (void)
2084 /* Optimization passes that invoke this routine can cause hot blocks
2085 previously reached by both hot and cold blocks to become dominated only
2086 by cold blocks. This will cause the verification below to fail,
2087 and lead to now cold code in the hot section. In some cases this
2088 may only be visible after newly unreachable blocks are deleted,
2089 which will be done by fixup_partitions. */
2090 fixup_partitions ();
2092 checking_verify_flow_info ();
2094 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
2095 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
2100 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2102 commit_one_edge_insertion (e
);
2107 /* Print out RTL-specific basic block information (live information
2108 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2109 documented in dumpfile.h. */
2112 rtl_dump_bb (FILE *outf
, basic_block bb
, int indent
, int flags
)
2118 s_indent
= (char *) alloca ((size_t) indent
+ 1);
2119 memset (s_indent
, ' ', (size_t) indent
);
2120 s_indent
[indent
] = '\0';
2122 if (df
&& (flags
& TDF_DETAILS
))
2124 df_dump_top (bb
, outf
);
2128 if (bb
->index
!= ENTRY_BLOCK
&& bb
->index
!= EXIT_BLOCK
)
2129 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
)); insn
!= last
;
2130 insn
= NEXT_INSN (insn
))
2132 if (flags
& TDF_DETAILS
)
2133 df_dump_insn_top (insn
, outf
);
2134 if (! (flags
& TDF_SLIM
))
2135 print_rtl_single (outf
, insn
);
2137 dump_insn_slim (outf
, insn
);
2138 if (flags
& TDF_DETAILS
)
2139 df_dump_insn_bottom (insn
, outf
);
2142 if (df
&& (flags
& TDF_DETAILS
))
2144 df_dump_bottom (bb
, outf
);
2150 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2151 for the start of each basic block. FLAGS are the TDF_* masks documented
2155 print_rtl_with_bb (FILE *outf
, const rtx_insn
*rtx_first
, int flags
)
2157 const rtx_insn
*tmp_rtx
;
2159 fprintf (outf
, "(nil)\n");
2162 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
2163 int max_uid
= get_max_uid ();
2164 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
2165 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
2166 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
2169 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2170 insns, but the CFG is not maintained so the basic block info
2171 is not reliable. Therefore it's omitted from the dumps. */
2172 if (! (cfun
->curr_properties
& PROP_cfg
))
2173 flags
&= ~TDF_BLOCKS
;
2176 df_dump_start (outf
);
2178 if (flags
& TDF_BLOCKS
)
2180 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2184 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
2185 end
[INSN_UID (BB_END (bb
))] = bb
;
2186 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
2188 enum bb_state state
= IN_MULTIPLE_BB
;
2190 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
2192 in_bb_p
[INSN_UID (x
)] = state
;
2194 if (x
== BB_END (bb
))
2200 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
2202 if (flags
& TDF_BLOCKS
)
2204 bb
= start
[INSN_UID (tmp_rtx
)];
2207 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, true, false);
2208 if (df
&& (flags
& TDF_DETAILS
))
2209 df_dump_top (bb
, outf
);
2212 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
2213 && !NOTE_P (tmp_rtx
)
2214 && !BARRIER_P (tmp_rtx
))
2215 fprintf (outf
, ";; Insn is not within a basic block\n");
2216 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
2217 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
2220 if (flags
& TDF_DETAILS
)
2221 df_dump_insn_top (tmp_rtx
, outf
);
2222 if (! (flags
& TDF_SLIM
))
2223 print_rtl_single (outf
, tmp_rtx
);
2225 dump_insn_slim (outf
, tmp_rtx
);
2226 if (flags
& TDF_DETAILS
)
2227 df_dump_insn_bottom (tmp_rtx
, outf
);
2229 if (flags
& TDF_BLOCKS
)
2231 bb
= end
[INSN_UID (tmp_rtx
)];
2234 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, false, true);
2235 if (df
&& (flags
& TDF_DETAILS
))
2236 df_dump_bottom (bb
, outf
);
2248 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2251 update_br_prob_note (basic_block bb
)
2254 if (!JUMP_P (BB_END (bb
)))
2256 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
2257 if (!note
|| XINT (note
, 0) == BRANCH_EDGE (bb
)->probability
)
2259 XINT (note
, 0) = BRANCH_EDGE (bb
)->probability
;
2262 /* Get the last insn associated with block BB (that includes barriers and
2263 tablejumps after BB). */
2265 get_last_bb_insn (basic_block bb
)
2267 rtx_jump_table_data
*table
;
2269 rtx_insn
*end
= BB_END (bb
);
2271 /* Include any jump table following the basic block. */
2272 if (tablejump_p (end
, NULL
, &table
))
2275 /* Include any barriers that may follow the basic block. */
2276 tmp
= next_nonnote_insn_bb (end
);
2277 while (tmp
&& BARRIER_P (tmp
))
2280 tmp
= next_nonnote_insn_bb (end
);
2286 /* Sanity check partition hotness to ensure that basic blocks in
2287 Â the cold partition don't dominate basic blocks in the hot partition.
2288 If FLAG_ONLY is true, report violations as errors. Otherwise
2289 re-mark the dominated blocks as cold, since this is run after
2290 cfg optimizations that may make hot blocks previously reached
2291 by both hot and cold blocks now only reachable along cold paths. */
2293 static vec
<basic_block
>
2294 find_partition_fixes (bool flag_only
)
2297 vec
<basic_block
> bbs_in_cold_partition
= vNULL
;
2298 vec
<basic_block
> bbs_to_fix
= vNULL
;
2300 /* Callers check this. */
2301 gcc_checking_assert (crtl
->has_bb_partition
);
2303 FOR_EACH_BB_FN (bb
, cfun
)
2304 if ((BB_PARTITION (bb
) == BB_COLD_PARTITION
))
2305 bbs_in_cold_partition
.safe_push (bb
);
2307 if (bbs_in_cold_partition
.is_empty ())
2310 bool dom_calculated_here
= !dom_info_available_p (CDI_DOMINATORS
);
2312 if (dom_calculated_here
)
2313 calculate_dominance_info (CDI_DOMINATORS
);
2315 while (! bbs_in_cold_partition
.is_empty ())
2317 bb
= bbs_in_cold_partition
.pop ();
2318 /* Any blocks dominated by a block in the cold section
2319 must also be cold. */
2321 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2323 son
= next_dom_son (CDI_DOMINATORS
, son
))
2325 /* If son is not yet cold, then mark it cold here and
2326 enqueue it for further processing. */
2327 if ((BB_PARTITION (son
) != BB_COLD_PARTITION
))
2330 error ("non-cold basic block %d dominated "
2331 "by a block in the cold partition (%d)", son
->index
, bb
->index
);
2333 BB_SET_PARTITION (son
, BB_COLD_PARTITION
);
2334 bbs_to_fix
.safe_push (son
);
2335 bbs_in_cold_partition
.safe_push (son
);
2340 if (dom_calculated_here
)
2341 free_dominance_info (CDI_DOMINATORS
);
2346 /* Perform cleanup on the hot/cold bb partitioning after optimization
2347 passes that modify the cfg. */
2350 fixup_partitions (void)
2354 if (!crtl
->has_bb_partition
)
2357 /* Delete any blocks that became unreachable and weren't
2358 already cleaned up, for example during edge forwarding
2359 and convert_jumps_to_returns. This will expose more
2360 opportunities for fixing the partition boundaries here.
2361 Also, the calculation of the dominance graph during verification
2362 will assert if there are unreachable nodes. */
2363 delete_unreachable_blocks ();
2365 /* If there are partitions, do a sanity check on them: A basic block in
2366 Â a cold partition cannot dominate a basic block in a hot partition.
2367 Fixup any that now violate this requirement, as a result of edge
2368 forwarding and unreachable block deletion. Â */
2369 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (false);
2371 /* Do the partition fixup after all necessary blocks have been converted to
2372 cold, so that we only update the region crossings the minimum number of
2373 places, which can require forcing edges to be non fallthru. */
2374 while (! bbs_to_fix
.is_empty ())
2376 bb
= bbs_to_fix
.pop ();
2377 fixup_new_cold_bb (bb
);
2381 /* Verify, in the basic block chain, that there is at most one switch
2382 between hot/cold partitions. This condition will not be true until
2383 after reorder_basic_blocks is called. */
2386 verify_hot_cold_block_grouping (void)
2390 bool switched_sections
= false;
2391 int current_partition
= BB_UNPARTITIONED
;
2393 /* Even after bb reordering is complete, we go into cfglayout mode
2394 again (in compgoto). Ensure we don't call this before going back
2395 into linearized RTL when any layout fixes would have been committed. */
2396 if (!crtl
->bb_reorder_complete
2397 || current_ir_type () != IR_RTL_CFGRTL
)
2400 FOR_EACH_BB_FN (bb
, cfun
)
2402 if (current_partition
!= BB_UNPARTITIONED
2403 && BB_PARTITION (bb
) != current_partition
)
2405 if (switched_sections
)
2407 error ("multiple hot/cold transitions found (bb %i)",
2412 switched_sections
= true;
2414 if (!crtl
->has_bb_partition
)
2415 error ("partition found but function partition flag not set");
2417 current_partition
= BB_PARTITION (bb
);
2424 /* Perform several checks on the edges out of each block, such as
2425 the consistency of the branch probabilities, the correctness
2426 of hot/cold partition crossing edges, and the number of expected
2427 successor edges. Also verify that the dominance relationship
2428 between hot/cold blocks is sane. */
2431 rtl_verify_edges (void)
2436 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2438 int n_fallthru
= 0, n_branch
= 0, n_abnormal_call
= 0, n_sibcall
= 0;
2439 int n_eh
= 0, n_abnormal
= 0;
2440 edge e
, fallthru
= NULL
;
2443 bool has_crossing_edge
= false;
2445 if (JUMP_P (BB_END (bb
))
2446 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
2447 && EDGE_COUNT (bb
->succs
) >= 2
2448 && any_condjump_p (BB_END (bb
)))
2450 if (XINT (note
, 0) != BRANCH_EDGE (bb
)->probability
2451 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2453 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2454 XINT (note
, 0), BRANCH_EDGE (bb
)->probability
);
2459 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2463 if (e
->flags
& EDGE_FALLTHRU
)
2464 n_fallthru
++, fallthru
= e
;
2466 is_crossing
= (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
2467 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2468 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
2469 has_crossing_edge
|= is_crossing
;
2470 if (e
->flags
& EDGE_CROSSING
)
2474 error ("EDGE_CROSSING incorrectly set across same section");
2477 if (e
->flags
& EDGE_FALLTHRU
)
2479 error ("fallthru edge crosses section boundary in bb %i",
2483 if (e
->flags
& EDGE_EH
)
2485 error ("EH edge crosses section boundary in bb %i",
2489 if (JUMP_P (BB_END (bb
)) && !CROSSING_JUMP_P (BB_END (bb
)))
2491 error ("No region crossing jump at section boundary in bb %i",
2496 else if (is_crossing
)
2498 error ("EDGE_CROSSING missing across section boundary");
2502 if ((e
->flags
& ~(EDGE_DFS_BACK
2504 | EDGE_IRREDUCIBLE_LOOP
2507 | EDGE_PRESERVE
)) == 0)
2510 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2513 if (e
->flags
& EDGE_SIBCALL
)
2516 if (e
->flags
& EDGE_EH
)
2519 if (e
->flags
& EDGE_ABNORMAL
)
2523 if (!has_crossing_edge
2524 && JUMP_P (BB_END (bb
))
2525 && CROSSING_JUMP_P (BB_END (bb
)))
2527 print_rtl_with_bb (stderr
, get_insns (), TDF_RTL
| TDF_BLOCKS
| TDF_DETAILS
);
2528 error ("Region crossing jump across same section in bb %i",
2533 if (n_eh
&& !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
2535 error ("missing REG_EH_REGION note at the end of bb %i", bb
->index
);
2540 error ("too many exception handling edges in bb %i", bb
->index
);
2544 && (!JUMP_P (BB_END (bb
))
2545 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
2546 || any_condjump_p (BB_END (bb
))))))
2548 error ("too many outgoing branch edges from bb %i", bb
->index
);
2551 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
2553 error ("fallthru edge after unconditional jump in bb %i", bb
->index
);
2556 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
2558 error ("wrong number of branch edges after unconditional jump"
2559 " in bb %i", bb
->index
);
2562 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
2563 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
2565 error ("wrong amount of branch edges after conditional jump"
2566 " in bb %i", bb
->index
);
2569 if (n_abnormal_call
&& !CALL_P (BB_END (bb
)))
2571 error ("abnormal call edges for non-call insn in bb %i", bb
->index
);
2574 if (n_sibcall
&& !CALL_P (BB_END (bb
)))
2576 error ("sibcall edges for non-call insn in bb %i", bb
->index
);
2579 if (n_abnormal
> n_eh
2580 && !(CALL_P (BB_END (bb
))
2581 && n_abnormal
== n_abnormal_call
+ n_sibcall
)
2582 && (!JUMP_P (BB_END (bb
))
2583 || any_condjump_p (BB_END (bb
))
2584 || any_uncondjump_p (BB_END (bb
))))
2586 error ("abnormal edges for no purpose in bb %i", bb
->index
);
2591 /* If there are partitions, do a sanity check on them: A basic block in
2592 Â a cold partition cannot dominate a basic block in a hot partition. Â */
2593 if (crtl
->has_bb_partition
&& !err
)
2595 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (true);
2596 err
= !bbs_to_fix
.is_empty ();
2603 /* Checks on the instructions within blocks. Currently checks that each
2604 block starts with a basic block note, and that basic block notes and
2605 control flow jumps are not found in the middle of the block. */
2608 rtl_verify_bb_insns (void)
2614 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2616 /* Now check the header of basic
2617 block. It ought to contain optional CODE_LABEL followed
2618 by NOTE_BASIC_BLOCK. */
2622 if (BB_END (bb
) == x
)
2624 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2632 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2634 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2639 if (BB_END (bb
) == x
)
2640 /* Do checks for empty blocks here. */
2643 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2645 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2647 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2648 INSN_UID (x
), bb
->index
);
2652 if (x
== BB_END (bb
))
2655 if (control_flow_insn_p (x
))
2657 error ("in basic block %d:", bb
->index
);
2658 fatal_insn ("flow control insn inside a basic block", x
);
2667 /* Verify that block pointers for instructions in basic blocks, headers and
2668 footers are set appropriately. */
2671 rtl_verify_bb_pointers (void)
2676 /* Check the general integrity of the basic blocks. */
2677 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2681 if (!(bb
->flags
& BB_RTL
))
2683 error ("BB_RTL flag not set for block %d", bb
->index
);
2687 FOR_BB_INSNS (bb
, insn
)
2688 if (BLOCK_FOR_INSN (insn
) != bb
)
2690 error ("insn %d basic block pointer is %d, should be %d",
2692 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
2697 for (insn
= BB_HEADER (bb
); insn
; insn
= NEXT_INSN (insn
))
2698 if (!BARRIER_P (insn
)
2699 && BLOCK_FOR_INSN (insn
) != NULL
)
2701 error ("insn %d in header of bb %d has non-NULL basic block",
2702 INSN_UID (insn
), bb
->index
);
2705 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
2706 if (!BARRIER_P (insn
)
2707 && BLOCK_FOR_INSN (insn
) != NULL
)
2709 error ("insn %d in footer of bb %d has non-NULL basic block",
2710 INSN_UID (insn
), bb
->index
);
2719 /* Verify the CFG and RTL consistency common for both underlying RTL and
2722 Currently it does following checks:
2724 - overlapping of basic blocks
2725 - insns with wrong BLOCK_FOR_INSN pointers
2726 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2727 - tails of basic blocks (ensure that boundary is necessary)
2728 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2729 and NOTE_INSN_BASIC_BLOCK
2730 - verify that no fall_thru edge crosses hot/cold partition boundaries
2731 - verify that there are no pending RTL branch predictions
2732 - verify that hot blocks are not dominated by cold blocks
2734 In future it can be extended check a lot of other stuff as well
2735 (reachability of basic blocks, life information, etc. etc.). */
2738 rtl_verify_flow_info_1 (void)
2742 err
|= rtl_verify_bb_pointers ();
2744 err
|= rtl_verify_bb_insns ();
2746 err
|= rtl_verify_edges ();
2751 /* Walk the instruction chain and verify that bb head/end pointers
2752 are correct, and that instructions are in exactly one bb and have
2753 correct block pointers. */
2756 rtl_verify_bb_insn_chain (void)
2761 rtx_insn
*last_head
= get_last_insn ();
2762 basic_block
*bb_info
;
2763 const int max_uid
= get_max_uid ();
2765 bb_info
= XCNEWVEC (basic_block
, max_uid
);
2767 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2769 rtx_insn
*head
= BB_HEAD (bb
);
2770 rtx_insn
*end
= BB_END (bb
);
2772 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2774 /* Verify the end of the basic block is in the INSN chain. */
2778 /* And that the code outside of basic blocks has NULL bb field. */
2780 && BLOCK_FOR_INSN (x
) != NULL
)
2782 error ("insn %d outside of basic blocks has non-NULL bb field",
2790 error ("end insn %d for block %d not found in the insn stream",
2791 INSN_UID (end
), bb
->index
);
2795 /* Work backwards from the end to the head of the basic block
2796 to verify the head is in the RTL chain. */
2797 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2799 /* While walking over the insn chain, verify insns appear
2800 in only one basic block. */
2801 if (bb_info
[INSN_UID (x
)] != NULL
)
2803 error ("insn %d is in multiple basic blocks (%d and %d)",
2804 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2808 bb_info
[INSN_UID (x
)] = bb
;
2815 error ("head insn %d for block %d not found in the insn stream",
2816 INSN_UID (head
), bb
->index
);
2820 last_head
= PREV_INSN (x
);
2823 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2825 /* Check that the code before the first basic block has NULL
2828 && BLOCK_FOR_INSN (x
) != NULL
)
2830 error ("insn %d outside of basic blocks has non-NULL bb field",
2840 /* Verify that fallthru edges point to adjacent blocks in layout order and
2841 that barriers exist after non-fallthru blocks. */
2844 rtl_verify_fallthru (void)
2849 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2853 e
= find_fallthru_edge (bb
->succs
);
2858 /* Ensure existence of barrier in BB with no fallthru edges. */
2859 for (insn
= NEXT_INSN (BB_END (bb
)); ; insn
= NEXT_INSN (insn
))
2861 if (!insn
|| NOTE_INSN_BASIC_BLOCK_P (insn
))
2863 error ("missing barrier after block %i", bb
->index
);
2867 if (BARRIER_P (insn
))
2871 else if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2872 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2876 if (e
->src
->next_bb
!= e
->dest
)
2879 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2880 e
->src
->index
, e
->dest
->index
);
2884 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
2885 insn
= NEXT_INSN (insn
))
2886 if (BARRIER_P (insn
) || INSN_P (insn
))
2888 error ("verify_flow_info: Incorrect fallthru %i->%i",
2889 e
->src
->index
, e
->dest
->index
);
2890 fatal_insn ("wrong insn in the fallthru edge", insn
);
2899 /* Verify that blocks are laid out in consecutive order. While walking the
2900 instructions, verify that all expected instructions are inside the basic
2901 blocks, and that all returns are followed by barriers. */
2904 rtl_verify_bb_layout (void)
2910 rtx_insn
* const rtx_first
= get_insns ();
2911 basic_block last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
), curr_bb
= NULL
;
2914 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
2916 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2918 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2920 bb
= NOTE_BASIC_BLOCK (x
);
2923 if (bb
!= last_bb_seen
->next_bb
)
2924 internal_error ("basic blocks not laid down consecutively");
2926 curr_bb
= last_bb_seen
= bb
;
2931 switch (GET_CODE (x
))
2938 /* An ADDR_VEC is placed outside any basic block. */
2940 && JUMP_TABLE_DATA_P (NEXT_INSN (x
)))
2943 /* But in any case, non-deletable labels can appear anywhere. */
2947 fatal_insn ("insn outside basic block", x
);
2952 && returnjump_p (x
) && ! condjump_p (x
)
2953 && ! (next_nonnote_insn (x
) && BARRIER_P (next_nonnote_insn (x
))))
2954 fatal_insn ("return not followed by barrier", x
);
2956 if (curr_bb
&& x
== BB_END (curr_bb
))
2960 if (num_bb_notes
!= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
)
2962 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2963 num_bb_notes
, n_basic_blocks_for_fn (cfun
));
2968 /* Verify the CFG and RTL consistency common for both underlying RTL and
2969 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
2971 Currently it does following checks:
2972 - all checks of rtl_verify_flow_info_1
2973 - test head/end pointers
2974 - check that blocks are laid out in consecutive order
2975 - check that all insns are in the basic blocks
2976 (except the switch handling code, barriers and notes)
2977 - check that all returns are followed by barriers
2978 - check that all fallthru edge points to the adjacent blocks
2979 - verify that there is a single hot/cold partition boundary after bbro */
2982 rtl_verify_flow_info (void)
2986 err
|= rtl_verify_flow_info_1 ();
2988 err
|= rtl_verify_bb_insn_chain ();
2990 err
|= rtl_verify_fallthru ();
2992 err
|= rtl_verify_bb_layout ();
2994 err
|= verify_hot_cold_block_grouping ();
2999 /* Assume that the preceding pass has possibly eliminated jump instructions
3000 or converted the unconditional jumps. Eliminate the edges from CFG.
3001 Return true if any edges are eliminated. */
3004 purge_dead_edges (basic_block bb
)
3007 rtx_insn
*insn
= BB_END (bb
);
3009 bool purged
= false;
3013 if (DEBUG_INSN_P (insn
) && insn
!= BB_HEAD (bb
))
3015 insn
= PREV_INSN (insn
);
3016 while ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
));
3018 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3019 if (NONJUMP_INSN_P (insn
)
3020 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
3024 if (! may_trap_p (PATTERN (insn
))
3025 || ((eqnote
= find_reg_equal_equiv_note (insn
))
3026 && ! may_trap_p (XEXP (eqnote
, 0))))
3027 remove_note (insn
, note
);
3030 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3031 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3033 bool remove
= false;
3035 /* There are three types of edges we need to handle correctly here: EH
3036 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3037 latter can appear when nonlocal gotos are used. */
3038 if (e
->flags
& EDGE_ABNORMAL_CALL
)
3042 else if (can_nonlocal_goto (insn
))
3044 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3046 else if (flag_tm
&& find_reg_note (insn
, REG_TM
, NULL
))
3051 else if (e
->flags
& EDGE_EH
)
3052 remove
= !can_throw_internal (insn
);
3057 df_set_bb_dirty (bb
);
3070 /* We do care only about conditional jumps and simplejumps. */
3071 if (!any_condjump_p (insn
)
3072 && !returnjump_p (insn
)
3073 && !simplejump_p (insn
))
3076 /* Branch probability/prediction notes are defined only for
3077 condjumps. We've possibly turned condjump into simplejump. */
3078 if (simplejump_p (insn
))
3080 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3082 remove_note (insn
, note
);
3083 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
3084 remove_note (insn
, note
);
3087 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3089 /* Avoid abnormal flags to leak from computed jumps turned
3090 into simplejumps. */
3092 e
->flags
&= ~EDGE_ABNORMAL
;
3094 /* See if this edge is one we should keep. */
3095 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
3096 /* A conditional jump can fall through into the next
3097 block, so we should keep the edge. */
3102 else if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3103 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
3104 /* If the destination block is the target of the jump,
3110 else if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
3111 && returnjump_p (insn
))
3112 /* If the destination block is the exit block, and this
3113 instruction is a return, then keep the edge. */
3118 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3119 /* Keep the edges that correspond to exceptions thrown by
3120 this instruction and rematerialize the EDGE_ABNORMAL
3121 flag we just cleared above. */
3123 e
->flags
|= EDGE_ABNORMAL
;
3128 /* We do not need this edge. */
3129 df_set_bb_dirty (bb
);
3134 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
3138 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
3143 /* Redistribute probabilities. */
3144 if (single_succ_p (bb
))
3146 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3147 single_succ_edge (bb
)->count
= bb
->count
;
3151 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3155 b
= BRANCH_EDGE (bb
);
3156 f
= FALLTHRU_EDGE (bb
);
3157 b
->probability
= XINT (note
, 0);
3158 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
3159 /* Update these to use GCOV_COMPUTE_SCALE. */
3160 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
3161 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
3166 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
3168 /* First, there should not be any EH or ABCALL edges resulting
3169 from non-local gotos and the like. If there were, we shouldn't
3170 have created the sibcall in the first place. Second, there
3171 should of course never have been a fallthru edge. */
3172 gcc_assert (single_succ_p (bb
));
3173 gcc_assert (single_succ_edge (bb
)->flags
3174 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
3179 /* If we don't see a jump insn, we don't know exactly why the block would
3180 have been broken at this point. Look for a simple, non-fallthru edge,
3181 as these are only created by conditional branches. If we find such an
3182 edge we know that there used to be a jump here and can then safely
3183 remove all non-fallthru edges. */
3185 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3186 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
3195 /* Remove all but the fake and fallthru edges. The fake edge may be
3196 the only successor for this block in the case of noreturn
3198 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3200 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
3202 df_set_bb_dirty (bb
);
3210 gcc_assert (single_succ_p (bb
));
3212 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3213 single_succ_edge (bb
)->count
= bb
->count
;
3216 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
3221 /* Search all basic blocks for potentially dead edges and purge them. Return
3222 true if some edge has been eliminated. */
3225 purge_all_dead_edges (void)
3230 FOR_EACH_BB_FN (bb
, cfun
)
3232 bool purged_here
= purge_dead_edges (bb
);
3234 purged
|= purged_here
;
3240 /* This is used by a few passes that emit some instructions after abnormal
3241 calls, moving the basic block's end, while they in fact do want to emit
3242 them on the fallthru edge. Look for abnormal call edges, find backward
3243 the call in the block and insert the instructions on the edge instead.
3245 Similarly, handle instructions throwing exceptions internally.
3247 Return true when instructions have been found and inserted on edges. */
3250 fixup_abnormal_edges (void)
3252 bool inserted
= false;
3255 FOR_EACH_BB_FN (bb
, cfun
)
3260 /* Look for cases we are interested in - calls or instructions causing
3262 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3263 if ((e
->flags
& EDGE_ABNORMAL_CALL
)
3264 || ((e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
3265 == (EDGE_ABNORMAL
| EDGE_EH
)))
3268 if (e
&& !CALL_P (BB_END (bb
)) && !can_throw_internal (BB_END (bb
)))
3272 /* Get past the new insns generated. Allow notes, as the insns
3273 may be already deleted. */
3275 while ((NONJUMP_INSN_P (insn
) || NOTE_P (insn
))
3276 && !can_throw_internal (insn
)
3277 && insn
!= BB_HEAD (bb
))
3278 insn
= PREV_INSN (insn
);
3280 if (CALL_P (insn
) || can_throw_internal (insn
))
3282 rtx_insn
*stop
, *next
;
3284 e
= find_fallthru_edge (bb
->succs
);
3286 stop
= NEXT_INSN (BB_END (bb
));
3289 for (insn
= NEXT_INSN (insn
); insn
!= stop
; insn
= next
)
3291 next
= NEXT_INSN (insn
);
3296 /* Sometimes there's still the return value USE.
3297 If it's placed after a trapping call (i.e. that
3298 call is the last insn anyway), we have no fallthru
3299 edge. Simply delete this use and don't try to insert
3300 on the non-existent edge. */
3301 if (GET_CODE (PATTERN (insn
)) != USE
)
3303 /* We're not deleting it, we're moving it. */
3304 insn
->set_undeleted ();
3305 SET_PREV_INSN (insn
) = NULL_RTX
;
3306 SET_NEXT_INSN (insn
) = NULL_RTX
;
3308 insert_insn_on_edge (insn
, e
);
3312 else if (!BARRIER_P (insn
))
3313 set_block_for_insn (insn
, NULL
);
3317 /* It may be that we don't find any trapping insn. In this
3318 case we discovered quite late that the insn that had been
3319 marked as can_throw_internal in fact couldn't trap at all.
3320 So we should in fact delete the EH edges out of the block. */
3322 purge_dead_edges (bb
);
3329 /* Cut the insns from FIRST to LAST out of the insns stream. */
3332 unlink_insn_chain (rtx_insn
*first
, rtx_insn
*last
)
3334 rtx_insn
*prevfirst
= PREV_INSN (first
);
3335 rtx_insn
*nextlast
= NEXT_INSN (last
);
3337 SET_PREV_INSN (first
) = NULL
;
3338 SET_NEXT_INSN (last
) = NULL
;
3340 SET_NEXT_INSN (prevfirst
) = nextlast
;
3342 SET_PREV_INSN (nextlast
) = prevfirst
;
3344 set_last_insn (prevfirst
);
3346 set_first_insn (nextlast
);
3350 /* Skip over inter-block insns occurring after BB which are typically
3351 associated with BB (e.g., barriers). If there are any such insns,
3352 we return the last one. Otherwise, we return the end of BB. */
3355 skip_insns_after_block (basic_block bb
)
3357 rtx_insn
*insn
, *last_insn
, *next_head
, *prev
;
3360 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3361 next_head
= BB_HEAD (bb
->next_bb
);
3363 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
3365 if (insn
== next_head
)
3368 switch (GET_CODE (insn
))
3375 switch (NOTE_KIND (insn
))
3377 case NOTE_INSN_BLOCK_END
:
3387 if (NEXT_INSN (insn
)
3388 && JUMP_TABLE_DATA_P (NEXT_INSN (insn
)))
3390 insn
= NEXT_INSN (insn
);
3403 /* It is possible to hit contradictory sequence. For instance:
3409 Where barrier belongs to jump_insn, but the note does not. This can be
3410 created by removing the basic block originally following
3411 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3413 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
3415 prev
= PREV_INSN (insn
);
3417 switch (NOTE_KIND (insn
))
3419 case NOTE_INSN_BLOCK_END
:
3422 case NOTE_INSN_DELETED
:
3423 case NOTE_INSN_DELETED_LABEL
:
3424 case NOTE_INSN_DELETED_DEBUG_LABEL
:
3427 reorder_insns (insn
, insn
, last_insn
);
3434 /* Locate or create a label for a given basic block. */
3437 label_for_bb (basic_block bb
)
3439 rtx_insn
*label
= BB_HEAD (bb
);
3441 if (!LABEL_P (label
))
3444 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
3446 label
= block_label (bb
);
3452 /* Locate the effective beginning and end of the insn chain for each
3453 block, as defined by skip_insns_after_block above. */
3456 record_effective_endpoints (void)
3458 rtx_insn
*next_insn
;
3462 for (insn
= get_insns ();
3465 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
;
3466 insn
= NEXT_INSN (insn
))
3468 /* No basic blocks at all? */
3471 if (PREV_INSN (insn
))
3472 cfg_layout_function_header
=
3473 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
3475 cfg_layout_function_header
= NULL
;
3477 next_insn
= get_insns ();
3478 FOR_EACH_BB_FN (bb
, cfun
)
3482 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
3483 BB_HEADER (bb
) = unlink_insn_chain (next_insn
,
3484 PREV_INSN (BB_HEAD (bb
)));
3485 end
= skip_insns_after_block (bb
);
3486 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
3487 BB_FOOTER (bb
) = unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
3488 next_insn
= NEXT_INSN (BB_END (bb
));
3491 cfg_layout_function_footer
= next_insn
;
3492 if (cfg_layout_function_footer
)
3493 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
3498 const pass_data pass_data_into_cfg_layout_mode
=
3500 RTL_PASS
, /* type */
3501 "into_cfglayout", /* name */
3502 OPTGROUP_NONE
, /* optinfo_flags */
3504 0, /* properties_required */
3505 PROP_cfglayout
, /* properties_provided */
3506 0, /* properties_destroyed */
3507 0, /* todo_flags_start */
3508 0, /* todo_flags_finish */
3511 class pass_into_cfg_layout_mode
: public rtl_opt_pass
3514 pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3515 : rtl_opt_pass (pass_data_into_cfg_layout_mode
, ctxt
)
3518 /* opt_pass methods: */
3519 virtual unsigned int execute (function
*)
3521 cfg_layout_initialize (0);
3525 }; // class pass_into_cfg_layout_mode
3530 make_pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3532 return new pass_into_cfg_layout_mode (ctxt
);
3537 const pass_data pass_data_outof_cfg_layout_mode
=
3539 RTL_PASS
, /* type */
3540 "outof_cfglayout", /* name */
3541 OPTGROUP_NONE
, /* optinfo_flags */
3543 0, /* properties_required */
3544 0, /* properties_provided */
3545 PROP_cfglayout
, /* properties_destroyed */
3546 0, /* todo_flags_start */
3547 0, /* todo_flags_finish */
3550 class pass_outof_cfg_layout_mode
: public rtl_opt_pass
3553 pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3554 : rtl_opt_pass (pass_data_outof_cfg_layout_mode
, ctxt
)
3557 /* opt_pass methods: */
3558 virtual unsigned int execute (function
*);
3560 }; // class pass_outof_cfg_layout_mode
3563 pass_outof_cfg_layout_mode::execute (function
*fun
)
3567 FOR_EACH_BB_FN (bb
, fun
)
3568 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3569 bb
->aux
= bb
->next_bb
;
3571 cfg_layout_finalize ();
3579 make_pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3581 return new pass_outof_cfg_layout_mode (ctxt
);
3585 /* Link the basic blocks in the correct order, compacting the basic
3586 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3587 function also clears the basic block header and footer fields.
3589 This function is usually called after a pass (e.g. tracer) finishes
3590 some transformations while in cfglayout mode. The required sequence
3591 of the basic blocks is in a linked list along the bb->aux field.
3592 This functions re-links the basic block prev_bb and next_bb pointers
3593 accordingly, and it compacts and renumbers the blocks.
3595 FIXME: This currently works only for RTL, but the only RTL-specific
3596 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3597 to GIMPLE a long time ago, but it doesn't relink the basic block
3598 chain. It could do that (to give better initial RTL) if this function
3599 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3602 relink_block_chain (bool stay_in_cfglayout_mode
)
3604 basic_block bb
, prev_bb
;
3607 /* Maybe dump the re-ordered sequence. */
3610 fprintf (dump_file
, "Reordered sequence:\n");
3611 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, index
=
3614 bb
= (basic_block
) bb
->aux
, index
++)
3616 fprintf (dump_file
, " %i ", index
);
3617 if (get_bb_original (bb
))
3618 fprintf (dump_file
, "duplicate of %i ",
3619 get_bb_original (bb
)->index
);
3620 else if (forwarder_block_p (bb
)
3621 && !LABEL_P (BB_HEAD (bb
)))
3622 fprintf (dump_file
, "compensation ");
3624 fprintf (dump_file
, "bb %i ", bb
->index
);
3625 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
3629 /* Now reorder the blocks. */
3630 prev_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
3631 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
3632 for (; bb
; prev_bb
= bb
, bb
= (basic_block
) bb
->aux
)
3634 bb
->prev_bb
= prev_bb
;
3635 prev_bb
->next_bb
= bb
;
3637 prev_bb
->next_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
3638 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
= prev_bb
;
3640 /* Then, clean up the aux fields. */
3641 FOR_ALL_BB_FN (bb
, cfun
)
3644 if (!stay_in_cfglayout_mode
)
3645 BB_HEADER (bb
) = BB_FOOTER (bb
) = NULL
;
3648 /* Maybe reset the original copy tables, they are not valid anymore
3649 when we renumber the basic blocks in compact_blocks. If we are
3650 are going out of cfglayout mode, don't re-allocate the tables. */
3651 free_original_copy_tables ();
3652 if (stay_in_cfglayout_mode
)
3653 initialize_original_copy_tables ();
3655 /* Finally, put basic_block_info in the new order. */
3660 /* Given a reorder chain, rearrange the code to match. */
3663 fixup_reorder_chain (void)
3666 rtx_insn
*insn
= NULL
;
3668 if (cfg_layout_function_header
)
3670 set_first_insn (cfg_layout_function_header
);
3671 insn
= cfg_layout_function_header
;
3672 while (NEXT_INSN (insn
))
3673 insn
= NEXT_INSN (insn
);
3676 /* First do the bulk reordering -- rechain the blocks without regard to
3677 the needed changes to jumps and labels. */
3679 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3685 SET_NEXT_INSN (insn
) = BB_HEADER (bb
);
3687 set_first_insn (BB_HEADER (bb
));
3688 SET_PREV_INSN (BB_HEADER (bb
)) = insn
;
3689 insn
= BB_HEADER (bb
);
3690 while (NEXT_INSN (insn
))
3691 insn
= NEXT_INSN (insn
);
3694 SET_NEXT_INSN (insn
) = BB_HEAD (bb
);
3696 set_first_insn (BB_HEAD (bb
));
3697 SET_PREV_INSN (BB_HEAD (bb
)) = insn
;
3701 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
3702 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
3703 while (NEXT_INSN (insn
))
3704 insn
= NEXT_INSN (insn
);
3708 SET_NEXT_INSN (insn
) = cfg_layout_function_footer
;
3709 if (cfg_layout_function_footer
)
3710 SET_PREV_INSN (cfg_layout_function_footer
) = insn
;
3712 while (NEXT_INSN (insn
))
3713 insn
= NEXT_INSN (insn
);
3715 set_last_insn (insn
);
3717 verify_insn_chain ();
3719 /* Now add jumps and labels as needed to match the blocks new
3722 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3725 edge e_fall
, e_taken
, e
;
3726 rtx_insn
*bb_end_insn
;
3727 rtx ret_label
= NULL_RTX
;
3731 if (EDGE_COUNT (bb
->succs
) == 0)
3734 /* Find the old fallthru edge, and another non-EH edge for
3736 e_taken
= e_fall
= NULL
;
3738 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3739 if (e
->flags
& EDGE_FALLTHRU
)
3741 else if (! (e
->flags
& EDGE_EH
))
3744 bb_end_insn
= BB_END (bb
);
3745 if (rtx_jump_insn
*bb_end_jump
= dyn_cast
<rtx_jump_insn
*> (bb_end_insn
))
3747 ret_label
= JUMP_LABEL (bb_end_jump
);
3748 if (any_condjump_p (bb_end_jump
))
3750 /* This might happen if the conditional jump has side
3751 effects and could therefore not be optimized away.
3752 Make the basic block to end with a barrier in order
3753 to prevent rtl_verify_flow_info from complaining. */
3756 gcc_assert (!onlyjump_p (bb_end_jump
)
3757 || returnjump_p (bb_end_jump
)
3758 || (e_taken
->flags
& EDGE_CROSSING
));
3759 emit_barrier_after (bb_end_jump
);
3763 /* If the old fallthru is still next, nothing to do. */
3764 if (bb
->aux
== e_fall
->dest
3765 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3768 /* The degenerated case of conditional jump jumping to the next
3769 instruction can happen for jumps with side effects. We need
3770 to construct a forwarder block and this will be done just
3771 fine by force_nonfallthru below. */
3775 /* There is another special case: if *neither* block is next,
3776 such as happens at the very end of a function, then we'll
3777 need to add a new unconditional jump. Choose the taken
3778 edge based on known or assumed probability. */
3779 else if (bb
->aux
!= e_taken
->dest
)
3781 rtx note
= find_reg_note (bb_end_jump
, REG_BR_PROB
, 0);
3784 && XINT (note
, 0) < REG_BR_PROB_BASE
/ 2
3785 && invert_jump (bb_end_jump
,
3787 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3789 : label_for_bb (e_fall
->dest
)), 0))
3791 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3792 gcc_checking_assert (could_fall_through
3793 (e_taken
->src
, e_taken
->dest
));
3794 e_taken
->flags
|= EDGE_FALLTHRU
;
3795 update_br_prob_note (bb
);
3796 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
3800 /* If the "jumping" edge is a crossing edge, and the fall
3801 through edge is non-crossing, leave things as they are. */
3802 else if ((e_taken
->flags
& EDGE_CROSSING
)
3803 && !(e_fall
->flags
& EDGE_CROSSING
))
3806 /* Otherwise we can try to invert the jump. This will
3807 basically never fail, however, keep up the pretense. */
3808 else if (invert_jump (bb_end_jump
,
3810 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3812 : label_for_bb (e_fall
->dest
)), 0))
3814 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3815 gcc_checking_assert (could_fall_through
3816 (e_taken
->src
, e_taken
->dest
));
3817 e_taken
->flags
|= EDGE_FALLTHRU
;
3818 update_br_prob_note (bb
);
3819 if (LABEL_NUSES (ret_label
) == 0
3820 && single_pred_p (e_taken
->dest
))
3821 delete_insn (ret_label
);
3825 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
3827 /* If the old fallthru is still next or if
3828 asm goto doesn't have a fallthru (e.g. when followed by
3829 __builtin_unreachable ()), nothing to do. */
3831 || bb
->aux
== e_fall
->dest
3832 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3835 /* Otherwise we'll have to use the fallthru fixup below. */
3839 /* Otherwise we have some return, switch or computed
3840 jump. In the 99% case, there should not have been a
3842 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
3848 /* No fallthru implies a noreturn function with EH edges, or
3849 something similarly bizarre. In any case, we don't need to
3854 /* If the fallthru block is still next, nothing to do. */
3855 if (bb
->aux
== e_fall
->dest
)
3858 /* A fallthru to exit block. */
3859 if (e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3863 /* We got here if we need to add a new jump insn.
3864 Note force_nonfallthru can delete E_FALL and thus we have to
3865 save E_FALL->src prior to the call to force_nonfallthru. */
3866 nb
= force_nonfallthru_and_redirect (e_fall
, e_fall
->dest
, ret_label
);
3871 /* Don't process this new block. */
3876 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3878 /* Annoying special case - jump around dead jumptables left in the code. */
3879 FOR_EACH_BB_FN (bb
, cfun
)
3881 edge e
= find_fallthru_edge (bb
->succs
);
3883 if (e
&& !can_fallthru (e
->src
, e
->dest
))
3884 force_nonfallthru (e
);
3887 /* Ensure goto_locus from edges has some instructions with that locus
3890 FOR_EACH_BB_FN (bb
, cfun
)
3895 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3896 if (LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
3897 && !(e
->flags
& EDGE_ABNORMAL
))
3901 basic_block dest
, nb
;
3904 insn
= BB_END (e
->src
);
3905 end
= PREV_INSN (BB_HEAD (e
->src
));
3907 && (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
3908 insn
= PREV_INSN (insn
);
3910 && INSN_LOCATION (insn
) == e
->goto_locus
)
3912 if (simplejump_p (BB_END (e
->src
))
3913 && !INSN_HAS_LOCATION (BB_END (e
->src
)))
3915 INSN_LOCATION (BB_END (e
->src
)) = e
->goto_locus
;
3919 if (dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3921 /* Non-fallthru edges to the exit block cannot be split. */
3922 if (!(e
->flags
& EDGE_FALLTHRU
))
3927 insn
= BB_HEAD (dest
);
3928 end
= NEXT_INSN (BB_END (dest
));
3929 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
3930 insn
= NEXT_INSN (insn
);
3931 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
3932 && INSN_LOCATION (insn
) == e
->goto_locus
)
3935 nb
= split_edge (e
);
3936 if (!INSN_P (BB_END (nb
)))
3937 BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
3939 INSN_LOCATION (BB_END (nb
)) = e
->goto_locus
;
3941 /* If there are other incoming edges to the destination block
3942 with the same goto locus, redirect them to the new block as
3943 well, this can prevent other such blocks from being created
3944 in subsequent iterations of the loop. */
3945 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
3946 if (LOCATION_LOCUS (e2
->goto_locus
) != UNKNOWN_LOCATION
3947 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
3948 && e
->goto_locus
== e2
->goto_locus
)
3949 redirect_edge_and_branch (e2
, nb
);
3956 /* Perform sanity checks on the insn chain.
3957 1. Check that next/prev pointers are consistent in both the forward and
3959 2. Count insns in chain, going both directions, and check if equal.
3960 3. Check that get_last_insn () returns the actual end of chain. */
3963 verify_insn_chain (void)
3965 rtx_insn
*x
, *prevx
, *nextx
;
3966 int insn_cnt1
, insn_cnt2
;
3968 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
3970 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
3971 gcc_assert (PREV_INSN (x
) == prevx
);
3973 gcc_assert (prevx
== get_last_insn ());
3975 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
3977 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
3978 gcc_assert (NEXT_INSN (x
) == nextx
);
3980 gcc_assert (insn_cnt1
== insn_cnt2
);
3983 /* If we have assembler epilogues, the block falling through to exit must
3984 be the last one in the reordered chain when we reach final. Ensure
3985 that this condition is met. */
3987 fixup_fallthru_exit_predecessor (void)
3990 basic_block bb
= NULL
;
3992 /* This transformation is not valid before reload, because we might
3993 separate a call from the instruction that copies the return
3995 gcc_assert (reload_completed
);
3997 e
= find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4003 basic_block c
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
4005 /* If the very first block is the one with the fall-through exit
4006 edge, we have to split that block. */
4009 bb
= split_block_after_labels (bb
)->dest
;
4012 BB_FOOTER (bb
) = BB_FOOTER (c
);
4013 BB_FOOTER (c
) = NULL
;
4016 while (c
->aux
!= bb
)
4017 c
= (basic_block
) c
->aux
;
4021 c
= (basic_block
) c
->aux
;
4028 /* In case there are more than one fallthru predecessors of exit, force that
4029 there is only one. */
4032 force_one_exit_fallthru (void)
4034 edge e
, predecessor
= NULL
;
4037 basic_block forwarder
, bb
;
4039 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
4040 if (e
->flags
& EDGE_FALLTHRU
)
4042 if (predecessor
== NULL
)
4054 /* Exit has several fallthru predecessors. Create a forwarder block for
4056 forwarder
= split_edge (predecessor
);
4057 for (ei
= ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4058 (e
= ei_safe_edge (ei
)); )
4060 if (e
->src
== forwarder
4061 || !(e
->flags
& EDGE_FALLTHRU
))
4064 redirect_edge_and_branch_force (e
, forwarder
);
4067 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4069 FOR_EACH_BB_FN (bb
, cfun
)
4071 if (bb
->aux
== NULL
&& bb
!= forwarder
)
4073 bb
->aux
= forwarder
;
4079 /* Return true in case it is possible to duplicate the basic block BB. */
4082 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
4084 /* Do not attempt to duplicate tablejumps, as we need to unshare
4085 the dispatch table. This is difficult to do, as the instructions
4086 computing jump destination may be hoisted outside the basic block. */
4087 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
4090 /* Do not duplicate blocks containing insns that can't be copied. */
4091 if (targetm
.cannot_copy_insn_p
)
4093 rtx_insn
*insn
= BB_HEAD (bb
);
4096 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
4098 if (insn
== BB_END (bb
))
4100 insn
= NEXT_INSN (insn
);
4108 duplicate_insn_chain (rtx_insn
*from
, rtx_insn
*to
)
4110 rtx_insn
*insn
, *next
, *copy
;
4113 /* Avoid updating of boundaries of previous basic block. The
4114 note will get removed from insn stream in fixup. */
4115 last
= emit_note (NOTE_INSN_DELETED
);
4117 /* Create copy at the end of INSN chain. The chain will
4118 be reordered later. */
4119 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
4121 switch (GET_CODE (insn
))
4124 /* Don't duplicate label debug insns. */
4125 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
)
4131 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
4132 if (JUMP_P (insn
) && JUMP_LABEL (insn
) != NULL_RTX
4133 && ANY_RETURN_P (JUMP_LABEL (insn
)))
4134 JUMP_LABEL (copy
) = JUMP_LABEL (insn
);
4135 maybe_copy_prologue_epilogue_insn (insn
, copy
);
4138 case JUMP_TABLE_DATA
:
4139 /* Avoid copying of dispatch tables. We never duplicate
4140 tablejumps, so this can hit only in case the table got
4141 moved far from original jump.
4142 Avoid copying following barrier as well if any
4143 (and debug insns in between). */
4144 for (next
= NEXT_INSN (insn
);
4145 next
!= NEXT_INSN (to
);
4146 next
= NEXT_INSN (next
))
4147 if (!DEBUG_INSN_P (next
))
4149 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
4161 switch (NOTE_KIND (insn
))
4163 /* In case prologue is empty and function contain label
4164 in first BB, we may want to copy the block. */
4165 case NOTE_INSN_PROLOGUE_END
:
4167 case NOTE_INSN_DELETED
:
4168 case NOTE_INSN_DELETED_LABEL
:
4169 case NOTE_INSN_DELETED_DEBUG_LABEL
:
4170 /* No problem to strip these. */
4171 case NOTE_INSN_FUNCTION_BEG
:
4172 /* There is always just single entry to function. */
4173 case NOTE_INSN_BASIC_BLOCK
:
4174 /* We should only switch text sections once. */
4175 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
4178 case NOTE_INSN_EPILOGUE_BEG
:
4179 case NOTE_INSN_UPDATE_SJLJ_CONTEXT
:
4180 emit_note_copy (as_a
<rtx_note
*> (insn
));
4184 /* All other notes should have already been eliminated. */
4192 insn
= NEXT_INSN (last
);
4197 /* Create a duplicate of the basic block BB. */
4200 cfg_layout_duplicate_bb (basic_block bb
)
4205 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
4206 new_bb
= create_basic_block (insn
,
4207 insn
? get_last_insn () : NULL
,
4208 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
);
4210 BB_COPY_PARTITION (new_bb
, bb
);
4213 insn
= BB_HEADER (bb
);
4214 while (NEXT_INSN (insn
))
4215 insn
= NEXT_INSN (insn
);
4216 insn
= duplicate_insn_chain (BB_HEADER (bb
), insn
);
4218 BB_HEADER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4223 insn
= BB_FOOTER (bb
);
4224 while (NEXT_INSN (insn
))
4225 insn
= NEXT_INSN (insn
);
4226 insn
= duplicate_insn_chain (BB_FOOTER (bb
), insn
);
4228 BB_FOOTER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4235 /* Main entry point to this module - initialize the datastructures for
4236 CFG layout changes. It keeps LOOPS up-to-date if not null.
4238 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4241 cfg_layout_initialize (unsigned int flags
)
4246 /* Once bb partitioning is complete, cfg layout mode should not be
4247 re-entered. Entering cfg layout mode may require fixups. As an
4248 example, if edge forwarding performed when optimizing the cfg
4249 layout required moving a block from the hot to the cold
4250 section. This would create an illegal partitioning unless some
4251 manual fixup was performed. */
4252 gcc_assert (!(crtl
->bb_reorder_complete
4253 && flag_reorder_blocks_and_partition
));
4255 initialize_original_copy_tables ();
4257 cfg_layout_rtl_register_cfg_hooks ();
4259 record_effective_endpoints ();
4261 /* Make sure that the targets of non local gotos are marked. */
4262 for (x
= nonlocal_goto_handler_labels
; x
; x
= x
->next ())
4264 bb
= BLOCK_FOR_INSN (x
->insn ());
4265 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
4268 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
4271 /* Splits superblocks. */
4273 break_superblocks (void)
4275 sbitmap superblocks
;
4279 superblocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
4280 bitmap_clear (superblocks
);
4282 FOR_EACH_BB_FN (bb
, cfun
)
4283 if (bb
->flags
& BB_SUPERBLOCK
)
4285 bb
->flags
&= ~BB_SUPERBLOCK
;
4286 bitmap_set_bit (superblocks
, bb
->index
);
4292 rebuild_jump_labels (get_insns ());
4293 find_many_sub_basic_blocks (superblocks
);
4299 /* Finalize the changes: reorder insn list according to the sequence specified
4300 by aux pointers, enter compensation code, rebuild scope forest. */
4303 cfg_layout_finalize (void)
4305 checking_verify_flow_info ();
4306 free_dominance_info (CDI_DOMINATORS
);
4307 force_one_exit_fallthru ();
4308 rtl_register_cfg_hooks ();
4309 if (reload_completed
&& !targetm
.have_epilogue ())
4310 fixup_fallthru_exit_predecessor ();
4311 fixup_reorder_chain ();
4313 rebuild_jump_labels (get_insns ());
4314 delete_dead_jumptables ();
4317 verify_insn_chain ();
4318 checking_verify_flow_info ();
4322 /* Same as split_block but update cfg_layout structures. */
4325 cfg_layout_split_block (basic_block bb
, void *insnp
)
4327 rtx insn
= (rtx
) insnp
;
4328 basic_block new_bb
= rtl_split_block (bb
, insn
);
4330 BB_FOOTER (new_bb
) = BB_FOOTER (bb
);
4331 BB_FOOTER (bb
) = NULL
;
4336 /* Redirect Edge to DEST. */
4338 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
4340 basic_block src
= e
->src
;
4343 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4346 if (e
->dest
== dest
)
4349 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4350 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
4352 df_set_bb_dirty (src
);
4356 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4357 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
4360 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
4361 e
->src
->index
, dest
->index
);
4363 df_set_bb_dirty (e
->src
);
4364 redirect_edge_succ (e
, dest
);
4368 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4369 in the case the basic block appears to be in sequence. Avoid this
4372 if (e
->flags
& EDGE_FALLTHRU
)
4374 /* Redirect any branch edges unified with the fallthru one. */
4375 if (JUMP_P (BB_END (src
))
4376 && label_is_jump_target_p (BB_HEAD (e
->dest
),
4382 fprintf (dump_file
, "Fallthru edge unified with branch "
4383 "%i->%i redirected to %i\n",
4384 e
->src
->index
, e
->dest
->index
, dest
->index
);
4385 e
->flags
&= ~EDGE_FALLTHRU
;
4386 redirected
= redirect_branch_edge (e
, dest
);
4387 gcc_assert (redirected
);
4388 redirected
->flags
|= EDGE_FALLTHRU
;
4389 df_set_bb_dirty (redirected
->src
);
4392 /* In case we are redirecting fallthru edge to the branch edge
4393 of conditional jump, remove it. */
4394 if (EDGE_COUNT (src
->succs
) == 2)
4396 /* Find the edge that is different from E. */
4397 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
4400 && any_condjump_p (BB_END (src
))
4401 && onlyjump_p (BB_END (src
)))
4402 delete_insn (BB_END (src
));
4405 fprintf (dump_file
, "Redirecting fallthru edge %i->%i to %i\n",
4406 e
->src
->index
, e
->dest
->index
, dest
->index
);
4407 ret
= redirect_edge_succ_nodup (e
, dest
);
4410 ret
= redirect_branch_edge (e
, dest
);
4412 /* We don't want simplejumps in the insn stream during cfglayout. */
4413 gcc_assert (!simplejump_p (BB_END (src
)));
4415 df_set_bb_dirty (src
);
4419 /* Simple wrapper as we always can redirect fallthru edges. */
4421 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
4423 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
4425 gcc_assert (redirected
);
4429 /* Same as delete_basic_block but update cfg_layout structures. */
4432 cfg_layout_delete_block (basic_block bb
)
4434 rtx_insn
*insn
, *next
, *prev
= PREV_INSN (BB_HEAD (bb
)), *remaints
;
4439 next
= BB_HEAD (bb
);
4441 SET_NEXT_INSN (prev
) = BB_HEADER (bb
);
4443 set_first_insn (BB_HEADER (bb
));
4444 SET_PREV_INSN (BB_HEADER (bb
)) = prev
;
4445 insn
= BB_HEADER (bb
);
4446 while (NEXT_INSN (insn
))
4447 insn
= NEXT_INSN (insn
);
4448 SET_NEXT_INSN (insn
) = next
;
4449 SET_PREV_INSN (next
) = insn
;
4451 next
= NEXT_INSN (BB_END (bb
));
4454 insn
= BB_FOOTER (bb
);
4457 if (BARRIER_P (insn
))
4459 if (PREV_INSN (insn
))
4460 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
4462 BB_FOOTER (bb
) = NEXT_INSN (insn
);
4463 if (NEXT_INSN (insn
))
4464 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
4468 insn
= NEXT_INSN (insn
);
4473 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
4474 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
4475 while (NEXT_INSN (insn
))
4476 insn
= NEXT_INSN (insn
);
4477 SET_NEXT_INSN (insn
) = next
;
4479 SET_PREV_INSN (next
) = insn
;
4481 set_last_insn (insn
);
4484 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
4485 to
= &BB_HEADER (bb
->next_bb
);
4487 to
= &cfg_layout_function_footer
;
4489 rtl_delete_block (bb
);
4492 prev
= NEXT_INSN (prev
);
4494 prev
= get_insns ();
4496 next
= PREV_INSN (next
);
4498 next
= get_last_insn ();
4500 if (next
&& NEXT_INSN (next
) != prev
)
4502 remaints
= unlink_insn_chain (prev
, next
);
4504 while (NEXT_INSN (insn
))
4505 insn
= NEXT_INSN (insn
);
4506 SET_NEXT_INSN (insn
) = *to
;
4508 SET_PREV_INSN (*to
) = insn
;
4513 /* Return true when blocks A and B can be safely merged. */
4516 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
4518 /* If we are partitioning hot/cold basic blocks, we don't want to
4519 mess up unconditional or indirect jumps that cross between hot
4522 Basic block partitioning may result in some jumps that appear to
4523 be optimizable (or blocks that appear to be mergeable), but which really
4524 must be left untouched (they are required to make it safely across
4525 partition boundaries). See the comments at the top of
4526 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4528 if (BB_PARTITION (a
) != BB_PARTITION (b
))
4531 /* Protect the loop latches. */
4532 if (current_loops
&& b
->loop_father
->latch
== b
)
4535 /* If we would end up moving B's instructions, make sure it doesn't fall
4536 through into the exit block, since we cannot recover from a fallthrough
4537 edge into the exit block occurring in the middle of a function. */
4538 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4540 edge e
= find_fallthru_edge (b
->succs
);
4541 if (e
&& e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4545 /* There must be exactly one edge in between the blocks. */
4546 return (single_succ_p (a
)
4547 && single_succ (a
) == b
4548 && single_pred_p (b
) == 1
4550 /* Must be simple edge. */
4551 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
4552 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4553 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
4554 /* If the jump insn has side effects, we can't kill the edge.
4555 When not optimizing, try_redirect_by_replacing_jump will
4556 not allow us to redirect an edge by replacing a table jump. */
4557 && (!JUMP_P (BB_END (a
))
4558 || ((!optimize
|| reload_completed
)
4559 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
4562 /* Merge block A and B. The blocks must be mergeable. */
4565 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
4567 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
4570 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a
, b
));
4573 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
4576 /* If there was a CODE_LABEL beginning B, delete it. */
4577 if (LABEL_P (BB_HEAD (b
)))
4579 delete_insn (BB_HEAD (b
));
4582 /* We should have fallthru edge in a, or we can do dummy redirection to get
4584 if (JUMP_P (BB_END (a
)))
4585 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
4586 gcc_assert (!JUMP_P (BB_END (a
)));
4588 /* When not optimizing and the edge is the only place in RTL which holds
4589 some unique locus, emit a nop with that locus in between. */
4591 emit_nop_for_unique_locus_between (a
, b
);
4593 /* Move things from b->footer after a->footer. */
4597 BB_FOOTER (a
) = BB_FOOTER (b
);
4600 rtx_insn
*last
= BB_FOOTER (a
);
4602 while (NEXT_INSN (last
))
4603 last
= NEXT_INSN (last
);
4604 SET_NEXT_INSN (last
) = BB_FOOTER (b
);
4605 SET_PREV_INSN (BB_FOOTER (b
)) = last
;
4607 BB_FOOTER (b
) = NULL
;
4610 /* Move things from b->header before a->footer.
4611 Note that this may include dead tablejump data, but we don't clean
4612 those up until we go out of cfglayout mode. */
4615 if (! BB_FOOTER (a
))
4616 BB_FOOTER (a
) = BB_HEADER (b
);
4619 rtx_insn
*last
= BB_HEADER (b
);
4621 while (NEXT_INSN (last
))
4622 last
= NEXT_INSN (last
);
4623 SET_NEXT_INSN (last
) = BB_FOOTER (a
);
4624 SET_PREV_INSN (BB_FOOTER (a
)) = last
;
4625 BB_FOOTER (a
) = BB_HEADER (b
);
4627 BB_HEADER (b
) = NULL
;
4630 /* In the case basic blocks are not adjacent, move them around. */
4631 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4633 insn
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
4635 emit_insn_after_noloc (insn
, BB_END (a
), a
);
4637 /* Otherwise just re-associate the instructions. */
4641 BB_END (a
) = BB_END (b
);
4644 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4645 We need to explicitly call. */
4646 update_bb_for_insn_chain (insn
, BB_END (b
), a
);
4648 /* Skip possible DELETED_LABEL insn. */
4649 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
4650 insn
= NEXT_INSN (insn
);
4651 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4652 BB_HEAD (b
) = BB_END (b
) = NULL
;
4655 df_bb_delete (b
->index
);
4657 /* If B was a forwarder block, propagate the locus on the edge. */
4659 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
4660 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
4663 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
4669 cfg_layout_split_edge (edge e
)
4671 basic_block new_bb
=
4672 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4673 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
4676 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4677 BB_COPY_PARTITION (new_bb
, e
->src
);
4679 BB_COPY_PARTITION (new_bb
, e
->dest
);
4680 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
4681 redirect_edge_and_branch_force (e
, new_bb
);
4686 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4689 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
4693 /* Return true if BB contains only labels or non-executable
4697 rtl_block_empty_p (basic_block bb
)
4701 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4702 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4705 FOR_BB_INSNS (bb
, insn
)
4706 if (NONDEBUG_INSN_P (insn
) && !any_uncondjump_p (insn
))
4712 /* Split a basic block if it ends with a conditional branch and if
4713 the other part of the block is not empty. */
4716 rtl_split_block_before_cond_jump (basic_block bb
)
4719 rtx_insn
*split_point
= NULL
;
4720 rtx_insn
*last
= NULL
;
4721 bool found_code
= false;
4723 FOR_BB_INSNS (bb
, insn
)
4725 if (any_condjump_p (insn
))
4727 else if (NONDEBUG_INSN_P (insn
))
4732 /* Did not find everything. */
4733 if (found_code
&& split_point
)
4734 return split_block (bb
, split_point
)->dest
;
4739 /* Return 1 if BB ends with a call, possibly followed by some
4740 instructions that must stay with the call, 0 otherwise. */
4743 rtl_block_ends_with_call_p (basic_block bb
)
4745 rtx_insn
*insn
= BB_END (bb
);
4747 while (!CALL_P (insn
)
4748 && insn
!= BB_HEAD (bb
)
4749 && (keep_with_call_p (insn
)
4751 || DEBUG_INSN_P (insn
)))
4752 insn
= PREV_INSN (insn
);
4753 return (CALL_P (insn
));
4756 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4759 rtl_block_ends_with_condjump_p (const_basic_block bb
)
4761 return any_condjump_p (BB_END (bb
));
4764 /* Return true if we need to add fake edge to exit.
4765 Helper function for rtl_flow_call_edges_add. */
4768 need_fake_edge_p (const rtx_insn
*insn
)
4774 && !SIBLING_CALL_P (insn
)
4775 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
4776 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
4779 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
4780 && MEM_VOLATILE_P (PATTERN (insn
)))
4781 || (GET_CODE (PATTERN (insn
)) == PARALLEL
4782 && asm_noperands (insn
) != -1
4783 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
4784 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
4787 /* Add fake edges to the function exit for any non constant and non noreturn
4788 calls, volatile inline assembly in the bitmap of blocks specified by
4789 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4792 The goal is to expose cases in which entering a basic block does not imply
4793 that all subsequent instructions must be executed. */
4796 rtl_flow_call_edges_add (sbitmap blocks
)
4799 int blocks_split
= 0;
4800 int last_bb
= last_basic_block_for_fn (cfun
);
4801 bool check_last_block
= false;
4803 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
4807 check_last_block
= true;
4809 check_last_block
= bitmap_bit_p (blocks
,
4810 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
->index
);
4812 /* In the last basic block, before epilogue generation, there will be
4813 a fallthru edge to EXIT. Special care is required if the last insn
4814 of the last basic block is a call because make_edge folds duplicate
4815 edges, which would result in the fallthru edge also being marked
4816 fake, which would result in the fallthru edge being removed by
4817 remove_fake_edges, which would result in an invalid CFG.
4819 Moreover, we can't elide the outgoing fake edge, since the block
4820 profiler needs to take this into account in order to solve the minimal
4821 spanning tree in the case that the call doesn't return.
4823 Handle this by adding a dummy instruction in a new last basic block. */
4824 if (check_last_block
)
4826 basic_block bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
4827 rtx_insn
*insn
= BB_END (bb
);
4829 /* Back up past insns that must be kept in the same block as a call. */
4830 while (insn
!= BB_HEAD (bb
)
4831 && keep_with_call_p (insn
))
4832 insn
= PREV_INSN (insn
);
4834 if (need_fake_edge_p (insn
))
4838 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4841 insert_insn_on_edge (gen_use (const0_rtx
), e
);
4842 commit_edge_insertions ();
4847 /* Now add fake edges to the function exit for any non constant
4848 calls since there is no way that we can determine if they will
4851 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
4853 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
4855 rtx_insn
*prev_insn
;
4860 if (blocks
&& !bitmap_bit_p (blocks
, i
))
4863 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
4865 prev_insn
= PREV_INSN (insn
);
4866 if (need_fake_edge_p (insn
))
4869 rtx_insn
*split_at_insn
= insn
;
4871 /* Don't split the block between a call and an insn that should
4872 remain in the same block as the call. */
4874 while (split_at_insn
!= BB_END (bb
)
4875 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
4876 split_at_insn
= NEXT_INSN (split_at_insn
);
4878 /* The handling above of the final block before the epilogue
4879 should be enough to verify that there is no edge to the exit
4880 block in CFG already. Calling make_edge in such case would
4881 cause us to mark that edge as fake and remove it later. */
4883 if (flag_checking
&& split_at_insn
== BB_END (bb
))
4885 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4886 gcc_assert (e
== NULL
);
4889 /* Note that the following may create a new basic block
4890 and renumber the existing basic blocks. */
4891 if (split_at_insn
!= BB_END (bb
))
4893 e
= split_block (bb
, split_at_insn
);
4898 make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
4901 if (insn
== BB_HEAD (bb
))
4907 verify_flow_info ();
4909 return blocks_split
;
4912 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4913 the conditional branch target, SECOND_HEAD should be the fall-thru
4914 there is no need to handle this here the loop versioning code handles
4915 this. the reason for SECON_HEAD is that it is needed for condition
4916 in trees, and this should be of the same type since it is a hook. */
4918 rtl_lv_add_condition_to_bb (basic_block first_head
,
4919 basic_block second_head ATTRIBUTE_UNUSED
,
4920 basic_block cond_bb
, void *comp_rtx
)
4922 rtx_code_label
*label
;
4923 rtx_insn
*seq
, *jump
;
4924 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
4925 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
4926 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
4930 label
= block_label (first_head
);
4931 mode
= GET_MODE (op0
);
4932 if (mode
== VOIDmode
)
4933 mode
= GET_MODE (op1
);
4936 op0
= force_operand (op0
, NULL_RTX
);
4937 op1
= force_operand (op1
, NULL_RTX
);
4938 do_compare_rtx_and_jump (op0
, op1
, comp
, 0, mode
, NULL_RTX
, NULL
, label
, -1);
4939 jump
= get_last_insn ();
4940 JUMP_LABEL (jump
) = label
;
4941 LABEL_NUSES (label
)++;
4945 /* Add the new cond, in the new head. */
4946 emit_insn_after (seq
, BB_END (cond_bb
));
4950 /* Given a block B with unconditional branch at its end, get the
4951 store the return the branch edge and the fall-thru edge in
4952 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4954 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
4955 edge
*fallthru_edge
)
4957 edge e
= EDGE_SUCC (b
, 0);
4959 if (e
->flags
& EDGE_FALLTHRU
)
4962 *branch_edge
= EDGE_SUCC (b
, 1);
4967 *fallthru_edge
= EDGE_SUCC (b
, 1);
4972 init_rtl_bb_info (basic_block bb
)
4974 gcc_assert (!bb
->il
.x
.rtl
);
4975 bb
->il
.x
.head_
= NULL
;
4976 bb
->il
.x
.rtl
= ggc_cleared_alloc
<rtl_bb_info
> ();
4979 /* Returns true if it is possible to remove edge E by redirecting
4980 it to the destination of the other edge from E->src. */
4983 rtl_can_remove_branch_p (const_edge e
)
4985 const_basic_block src
= e
->src
;
4986 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
4987 const rtx_insn
*insn
= BB_END (src
);
4990 /* The conditions are taken from try_redirect_by_replacing_jump. */
4991 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4994 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4997 if (BB_PARTITION (src
) != BB_PARTITION (target
))
5000 if (!onlyjump_p (insn
)
5001 || tablejump_p (insn
, NULL
, NULL
))
5004 set
= single_set (insn
);
5005 if (!set
|| side_effects_p (set
))
5012 rtl_duplicate_bb (basic_block bb
)
5014 bb
= cfg_layout_duplicate_bb (bb
);
5019 /* Do book-keeping of basic block BB for the profile consistency checker.
5020 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
5021 then do post-pass accounting. Store the counting in RECORD. */
5023 rtl_account_profile_record (basic_block bb
, int after_pass
,
5024 struct profile_record
*record
)
5027 FOR_BB_INSNS (bb
, insn
)
5030 record
->size
[after_pass
]
5031 += insn_rtx_cost (PATTERN (insn
), false);
5032 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
5033 record
->time
[after_pass
]
5034 += insn_rtx_cost (PATTERN (insn
), true) * bb
->count
;
5035 else if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
5036 record
->time
[after_pass
]
5037 += insn_rtx_cost (PATTERN (insn
), true) * bb
->frequency
;
5041 /* Implementation of CFG manipulation for linearized RTL. */
5042 struct cfg_hooks rtl_cfg_hooks
= {
5044 rtl_verify_flow_info
,
5046 rtl_dump_bb_for_graph
,
5047 rtl_create_basic_block
,
5048 rtl_redirect_edge_and_branch
,
5049 rtl_redirect_edge_and_branch_force
,
5050 rtl_can_remove_branch_p
,
5053 rtl_move_block_after
,
5054 rtl_can_merge_blocks
, /* can_merge_blocks_p */
5058 cfg_layout_can_duplicate_bb_p
,
5061 rtl_make_forwarder_block
,
5062 rtl_tidy_fallthru_edge
,
5063 rtl_force_nonfallthru
,
5064 rtl_block_ends_with_call_p
,
5065 rtl_block_ends_with_condjump_p
,
5066 rtl_flow_call_edges_add
,
5067 NULL
, /* execute_on_growing_pred */
5068 NULL
, /* execute_on_shrinking_pred */
5069 NULL
, /* duplicate loop for trees */
5070 NULL
, /* lv_add_condition_to_bb */
5071 NULL
, /* lv_adjust_loop_header_phi*/
5072 NULL
, /* extract_cond_bb_edges */
5073 NULL
, /* flush_pending_stmts */
5074 rtl_block_empty_p
, /* block_empty_p */
5075 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5076 rtl_account_profile_record
,
5079 /* Implementation of CFG manipulation for cfg layout RTL, where
5080 basic block connected via fallthru edges does not have to be adjacent.
5081 This representation will hopefully become the default one in future
5082 version of the compiler. */
5084 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
5086 rtl_verify_flow_info_1
,
5088 rtl_dump_bb_for_graph
,
5089 cfg_layout_create_basic_block
,
5090 cfg_layout_redirect_edge_and_branch
,
5091 cfg_layout_redirect_edge_and_branch_force
,
5092 rtl_can_remove_branch_p
,
5093 cfg_layout_delete_block
,
5094 cfg_layout_split_block
,
5095 rtl_move_block_after
,
5096 cfg_layout_can_merge_blocks_p
,
5097 cfg_layout_merge_blocks
,
5100 cfg_layout_can_duplicate_bb_p
,
5101 cfg_layout_duplicate_bb
,
5102 cfg_layout_split_edge
,
5103 rtl_make_forwarder_block
,
5104 NULL
, /* tidy_fallthru_edge */
5105 rtl_force_nonfallthru
,
5106 rtl_block_ends_with_call_p
,
5107 rtl_block_ends_with_condjump_p
,
5108 rtl_flow_call_edges_add
,
5109 NULL
, /* execute_on_growing_pred */
5110 NULL
, /* execute_on_shrinking_pred */
5111 duplicate_loop_to_header_edge
, /* duplicate loop for trees */
5112 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
5113 NULL
, /* lv_adjust_loop_header_phi*/
5114 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
5115 NULL
, /* flush_pending_stmts */
5116 rtl_block_empty_p
, /* block_empty_p */
5117 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5118 rtl_account_profile_record
,
5121 #include "gt-cfgrtl.h"