1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This file contains low level functions to manipulate the CFG and analyze it
21 that are aware of the RTL intermediate language.
23 Available functionality:
24 - Basic CFG/RTL manipulation API documented in cfghooks.h
25 - CFG-aware instruction chain manipulation
26 delete_insn, delete_insn_chain
27 - Edge splitting and committing to edges
28 insert_insn_on_edge, commit_edge_insertions
29 - CFG updating after insn simplification
30 purge_dead_edges, purge_all_dead_edges
31 - CFG fixing after coarse manipulation
34 Functions not supposed for generic use:
35 - Infrastructure to determine quickly basic block for insn
36 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
37 - Edge redirection with updating and optimizing of insn chain
38 block_label, tidy_fallthru_edge, force_nonfallthru */
42 #include "coretypes.h"
49 #include "insn-config.h"
55 #include "cfgcleanup.h"
56 #include "bb-reorder.h"
57 #include "rtl-error.h"
58 #include "insn-attr.h"
62 #include "tree-pass.h"
63 #include "print-rtl.h"
65 /* Holds the interesting leading and trailing notes for the function.
66 Only applicable if the CFG is in cfglayout mode. */
67 static GTY(()) rtx_insn
*cfg_layout_function_footer
;
68 static GTY(()) rtx_insn
*cfg_layout_function_header
;
70 static rtx_insn
*skip_insns_after_block (basic_block
);
71 static void record_effective_endpoints (void);
72 static void fixup_reorder_chain (void);
74 void verify_insn_chain (void);
75 static void fixup_fallthru_exit_predecessor (void);
76 static int can_delete_note_p (const rtx_note
*);
77 static int can_delete_label_p (const rtx_code_label
*);
78 static basic_block
rtl_split_edge (edge
);
79 static bool rtl_move_block_after (basic_block
, basic_block
);
80 static int rtl_verify_flow_info (void);
81 static basic_block
cfg_layout_split_block (basic_block
, void *);
82 static edge
cfg_layout_redirect_edge_and_branch (edge
, basic_block
);
83 static basic_block
cfg_layout_redirect_edge_and_branch_force (edge
, basic_block
);
84 static void cfg_layout_delete_block (basic_block
);
85 static void rtl_delete_block (basic_block
);
86 static basic_block
rtl_redirect_edge_and_branch_force (edge
, basic_block
);
87 static edge
rtl_redirect_edge_and_branch (edge
, basic_block
);
88 static basic_block
rtl_split_block (basic_block
, void *);
89 static void rtl_dump_bb (FILE *, basic_block
, int, dump_flags_t
);
90 static int rtl_verify_flow_info_1 (void);
91 static void rtl_make_forwarder_block (edge
);
93 /* Return true if NOTE is not one of the ones that must be kept paired,
94 so that we may simply delete it. */
97 can_delete_note_p (const rtx_note
*note
)
99 switch (NOTE_KIND (note
))
101 case NOTE_INSN_DELETED
:
102 case NOTE_INSN_BASIC_BLOCK
:
103 case NOTE_INSN_EPILOGUE_BEG
:
111 /* True if a given label can be deleted. */
114 can_delete_label_p (const rtx_code_label
*label
)
116 return (!LABEL_PRESERVE_P (label
)
117 /* User declared labels must be preserved. */
118 && LABEL_NAME (label
) == 0
119 && !vec_safe_contains
<rtx_insn
*> (forced_labels
,
120 const_cast<rtx_code_label
*> (label
)));
123 /* Delete INSN by patching it out. */
126 delete_insn (rtx_insn
*insn
)
129 bool really_delete
= true;
133 /* Some labels can't be directly removed from the INSN chain, as they
134 might be references via variables, constant pool etc.
135 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
136 if (! can_delete_label_p (as_a
<rtx_code_label
*> (insn
)))
138 const char *name
= LABEL_NAME (insn
);
139 basic_block bb
= BLOCK_FOR_INSN (insn
);
140 rtx_insn
*bb_note
= NEXT_INSN (insn
);
142 really_delete
= false;
143 PUT_CODE (insn
, NOTE
);
144 NOTE_KIND (insn
) = NOTE_INSN_DELETED_LABEL
;
145 NOTE_DELETED_LABEL_NAME (insn
) = name
;
147 /* If the note following the label starts a basic block, and the
148 label is a member of the same basic block, interchange the two. */
149 if (bb_note
!= NULL_RTX
150 && NOTE_INSN_BASIC_BLOCK_P (bb_note
)
152 && bb
== BLOCK_FOR_INSN (bb_note
))
154 reorder_insns_nobb (insn
, insn
, bb_note
);
155 BB_HEAD (bb
) = bb_note
;
156 if (BB_END (bb
) == bb_note
)
161 remove_node_from_insn_list (insn
, &nonlocal_goto_handler_labels
);
166 /* If this insn has already been deleted, something is very wrong. */
167 gcc_assert (!insn
->deleted ());
169 df_insn_delete (insn
);
171 insn
->set_deleted ();
174 /* If deleting a jump, decrement the use count of the label. Deleting
175 the label itself should happen in the normal course of block merging. */
178 if (JUMP_LABEL (insn
)
179 && LABEL_P (JUMP_LABEL (insn
)))
180 LABEL_NUSES (JUMP_LABEL (insn
))--;
182 /* If there are more targets, remove them too. */
184 = find_reg_note (insn
, REG_LABEL_TARGET
, NULL_RTX
)) != NULL_RTX
185 && LABEL_P (XEXP (note
, 0)))
187 LABEL_NUSES (XEXP (note
, 0))--;
188 remove_note (insn
, note
);
192 /* Also if deleting any insn that references a label as an operand. */
193 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, NULL_RTX
)) != NULL_RTX
194 && LABEL_P (XEXP (note
, 0)))
196 LABEL_NUSES (XEXP (note
, 0))--;
197 remove_note (insn
, note
);
200 if (rtx_jump_table_data
*table
= dyn_cast
<rtx_jump_table_data
*> (insn
))
202 rtvec vec
= table
->get_labels ();
203 int len
= GET_NUM_ELEM (vec
);
206 for (i
= 0; i
< len
; i
++)
208 rtx label
= XEXP (RTVEC_ELT (vec
, i
), 0);
210 /* When deleting code in bulk (e.g. removing many unreachable
211 blocks) we can delete a label that's a target of the vector
212 before deleting the vector itself. */
214 LABEL_NUSES (label
)--;
219 /* Like delete_insn but also purge dead edges from BB.
220 Return true if any edges are eliminated. */
223 delete_insn_and_edges (rtx_insn
*insn
)
228 && BLOCK_FOR_INSN (insn
)
229 && BB_END (BLOCK_FOR_INSN (insn
)) == insn
)
233 return purge_dead_edges (BLOCK_FOR_INSN (insn
));
237 /* Unlink a chain of insns between START and FINISH, leaving notes
238 that must be paired. If CLEAR_BB is true, we set bb field for
239 insns that cannot be removed to NULL. */
242 delete_insn_chain (rtx start
, rtx_insn
*finish
, bool clear_bb
)
244 /* Unchain the insns one by one. It would be quicker to delete all of these
245 with a single unchaining, rather than one at a time, but we need to keep
247 rtx_insn
*current
= finish
;
250 rtx_insn
*prev
= PREV_INSN (current
);
251 if (NOTE_P (current
) && !can_delete_note_p (as_a
<rtx_note
*> (current
)))
254 delete_insn (current
);
256 if (clear_bb
&& !current
->deleted ())
257 set_block_for_insn (current
, NULL
);
259 if (current
== start
)
265 /* Create a new basic block consisting of the instructions between HEAD and END
266 inclusive. This function is designed to allow fast BB construction - reuses
267 the note and basic block struct in BB_NOTE, if any and do not grow
268 BASIC_BLOCK chain and should be used directly only by CFG construction code.
269 END can be NULL in to create new empty basic block before HEAD. Both END
270 and HEAD can be NULL to create basic block at the end of INSN chain.
271 AFTER is the basic block we should be put after. */
274 create_basic_block_structure (rtx_insn
*head
, rtx_insn
*end
, rtx_note
*bb_note
,
280 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
283 /* If we found an existing note, thread it back onto the chain. */
291 after
= PREV_INSN (head
);
295 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
296 reorder_insns_nobb (bb_note
, bb_note
, after
);
300 /* Otherwise we must create a note and a basic block structure. */
304 init_rtl_bb_info (bb
);
307 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
308 else if (LABEL_P (head
) && end
)
310 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
316 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
322 NOTE_BASIC_BLOCK (bb_note
) = bb
;
325 /* Always include the bb note in the block. */
326 if (NEXT_INSN (end
) == bb_note
)
331 bb
->index
= last_basic_block_for_fn (cfun
)++;
332 bb
->flags
= BB_NEW
| BB_RTL
;
333 link_block (bb
, after
);
334 SET_BASIC_BLOCK_FOR_FN (cfun
, bb
->index
, bb
);
335 df_bb_refs_record (bb
->index
, false);
336 update_bb_for_insn (bb
);
337 BB_SET_PARTITION (bb
, BB_UNPARTITIONED
);
339 /* Tag the block so that we know it has been used when considering
340 other basic block notes. */
346 /* Create new basic block consisting of instructions in between HEAD and END
347 and place it to the BB chain after block AFTER. END can be NULL to
348 create a new empty basic block before HEAD. Both END and HEAD can be
349 NULL to create basic block at the end of INSN chain. */
352 rtl_create_basic_block (void *headp
, void *endp
, basic_block after
)
354 rtx_insn
*head
= (rtx_insn
*) headp
;
355 rtx_insn
*end
= (rtx_insn
*) endp
;
358 /* Grow the basic block array if needed. */
359 if ((size_t) last_basic_block_for_fn (cfun
)
360 >= basic_block_info_for_fn (cfun
)->length ())
363 (last_basic_block_for_fn (cfun
)
364 + (last_basic_block_for_fn (cfun
) + 3) / 4);
365 vec_safe_grow_cleared (basic_block_info_for_fn (cfun
), new_size
);
368 n_basic_blocks_for_fn (cfun
)++;
370 bb
= create_basic_block_structure (head
, end
, NULL
, after
);
376 cfg_layout_create_basic_block (void *head
, void *end
, basic_block after
)
378 basic_block newbb
= rtl_create_basic_block (head
, end
, after
);
383 /* Delete the insns in a (non-live) block. We physically delete every
384 non-deleted-note insn, and update the flow graph appropriately.
386 Return nonzero if we deleted an exception handler. */
388 /* ??? Preserving all such notes strikes me as wrong. It would be nice
389 to post-process the stream to remove empty blocks, loops, ranges, etc. */
392 rtl_delete_block (basic_block b
)
394 rtx_insn
*insn
, *end
;
396 /* If the head of this block is a CODE_LABEL, then it might be the
397 label for an exception handler which can't be reached. We need
398 to remove the label from the exception_handler_label list. */
401 end
= get_last_bb_insn (b
);
403 /* Selectively delete the entire chain. */
405 delete_insn_chain (insn
, end
, true);
409 fprintf (dump_file
, "deleting block %d\n", b
->index
);
410 df_bb_delete (b
->index
);
413 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
416 compute_bb_for_insn (void)
420 FOR_EACH_BB_FN (bb
, cfun
)
422 rtx_insn
*end
= BB_END (bb
);
425 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
427 BLOCK_FOR_INSN (insn
) = bb
;
434 /* Release the basic_block_for_insn array. */
437 free_bb_for_insn (void)
440 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
441 if (!BARRIER_P (insn
))
442 BLOCK_FOR_INSN (insn
) = NULL
;
448 const pass_data pass_data_free_cfg
=
451 "*free_cfg", /* name */
452 OPTGROUP_NONE
, /* optinfo_flags */
454 0, /* properties_required */
455 0, /* properties_provided */
456 PROP_cfg
, /* properties_destroyed */
457 0, /* todo_flags_start */
458 0, /* todo_flags_finish */
461 class pass_free_cfg
: public rtl_opt_pass
464 pass_free_cfg (gcc::context
*ctxt
)
465 : rtl_opt_pass (pass_data_free_cfg
, ctxt
)
468 /* opt_pass methods: */
469 virtual unsigned int execute (function
*);
471 }; // class pass_free_cfg
474 pass_free_cfg::execute (function
*)
476 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
477 valid at that point so it would be too late to call df_analyze. */
478 if (DELAY_SLOTS
&& optimize
> 0 && flag_delayed_branch
)
480 df_note_add_problem ();
484 if (crtl
->has_bb_partition
)
485 insert_section_boundary_note ();
494 make_pass_free_cfg (gcc::context
*ctxt
)
496 return new pass_free_cfg (ctxt
);
499 /* Return RTX to emit after when we want to emit code on the entry of function. */
501 entry_of_function (void)
503 return (n_basic_blocks_for_fn (cfun
) > NUM_FIXED_BLOCKS
?
504 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
) : get_insns ());
507 /* Emit INSN at the entry point of the function, ensuring that it is only
508 executed once per function. */
510 emit_insn_at_entry (rtx insn
)
512 edge_iterator ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
513 edge e
= ei_safe_edge (ei
);
514 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
516 insert_insn_on_edge (insn
, e
);
517 commit_edge_insertions ();
520 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
521 (or BARRIER if found) and notify df of the bb change.
522 The insn chain range is inclusive
523 (i.e. both BEGIN and END will be updated. */
526 update_bb_for_insn_chain (rtx_insn
*begin
, rtx_insn
*end
, basic_block bb
)
530 end
= NEXT_INSN (end
);
531 for (insn
= begin
; insn
!= end
; insn
= NEXT_INSN (insn
))
532 if (!BARRIER_P (insn
))
533 df_insn_change_bb (insn
, bb
);
536 /* Update BLOCK_FOR_INSN of insns in BB to BB,
537 and notify df of the change. */
540 update_bb_for_insn (basic_block bb
)
542 update_bb_for_insn_chain (BB_HEAD (bb
), BB_END (bb
), bb
);
546 /* Like active_insn_p, except keep the return value clobber around
547 even after reload. */
550 flow_active_insn_p (const rtx_insn
*insn
)
552 if (active_insn_p (insn
))
555 /* A clobber of the function return value exists for buggy
556 programs that fail to return a value. Its effect is to
557 keep the return value from being live across the entire
558 function. If we allow it to be skipped, we introduce the
559 possibility for register lifetime confusion. */
560 if (GET_CODE (PATTERN (insn
)) == CLOBBER
561 && REG_P (XEXP (PATTERN (insn
), 0))
562 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn
), 0)))
568 /* Return true if the block has no effect and only forwards control flow to
569 its single destination. */
572 contains_no_active_insn_p (const_basic_block bb
)
576 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
577 || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
578 || !single_succ_p (bb
)
579 || (single_succ_edge (bb
)->flags
& EDGE_FAKE
) != 0)
582 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
583 if (INSN_P (insn
) && flow_active_insn_p (insn
))
586 return (!INSN_P (insn
)
587 || (JUMP_P (insn
) && simplejump_p (insn
))
588 || !flow_active_insn_p (insn
));
591 /* Likewise, but protect loop latches, headers and preheaders. */
592 /* FIXME: Make this a cfg hook. */
595 forwarder_block_p (const_basic_block bb
)
597 if (!contains_no_active_insn_p (bb
))
600 /* Protect loop latches, headers and preheaders. */
604 if (bb
->loop_father
->header
== bb
)
606 dest
= EDGE_SUCC (bb
, 0)->dest
;
607 if (dest
->loop_father
->header
== dest
)
614 /* Return nonzero if we can reach target from src by falling through. */
615 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
618 can_fallthru (basic_block src
, basic_block target
)
620 rtx_insn
*insn
= BB_END (src
);
625 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
627 if (src
->next_bb
!= target
)
630 /* ??? Later we may add code to move jump tables offline. */
631 if (tablejump_p (insn
, NULL
, NULL
))
634 FOR_EACH_EDGE (e
, ei
, src
->succs
)
635 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
636 && e
->flags
& EDGE_FALLTHRU
)
639 insn2
= BB_HEAD (target
);
640 if (!active_insn_p (insn2
))
641 insn2
= next_active_insn (insn2
);
643 return next_active_insn (insn
) == insn2
;
646 /* Return nonzero if we could reach target from src by falling through,
647 if the target was made adjacent. If we already have a fall-through
648 edge to the exit block, we can't do that. */
650 could_fall_through (basic_block src
, basic_block target
)
655 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
657 FOR_EACH_EDGE (e
, ei
, src
->succs
)
658 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
659 && e
->flags
& EDGE_FALLTHRU
)
664 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
666 bb_note (basic_block bb
)
672 note
= NEXT_INSN (note
);
674 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
675 return as_a
<rtx_note
*> (note
);
678 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
679 note associated with the BLOCK. */
682 first_insn_after_basic_block_note (basic_block block
)
686 /* Get the first instruction in the block. */
687 insn
= BB_HEAD (block
);
689 if (insn
== NULL_RTX
)
692 insn
= NEXT_INSN (insn
);
693 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
695 return NEXT_INSN (insn
);
698 /* Creates a new basic block just after basic block BB by splitting
699 everything after specified instruction INSNP. */
702 rtl_split_block (basic_block bb
, void *insnp
)
705 rtx_insn
*insn
= (rtx_insn
*) insnp
;
711 insn
= first_insn_after_basic_block_note (bb
);
715 rtx_insn
*next
= insn
;
717 insn
= PREV_INSN (insn
);
719 /* If the block contains only debug insns, insn would have
720 been NULL in a non-debug compilation, and then we'd end
721 up emitting a DELETED note. For -fcompare-debug
722 stability, emit the note too. */
723 if (insn
!= BB_END (bb
)
724 && DEBUG_INSN_P (next
)
725 && DEBUG_INSN_P (BB_END (bb
)))
727 while (next
!= BB_END (bb
) && DEBUG_INSN_P (next
))
728 next
= NEXT_INSN (next
);
730 if (next
== BB_END (bb
))
731 emit_note_after (NOTE_INSN_DELETED
, next
);
735 insn
= get_last_insn ();
738 /* We probably should check type of the insn so that we do not create
739 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
741 if (insn
== BB_END (bb
))
742 emit_note_after (NOTE_INSN_DELETED
, insn
);
744 /* Create the new basic block. */
745 new_bb
= create_basic_block (NEXT_INSN (insn
), BB_END (bb
), bb
);
746 BB_COPY_PARTITION (new_bb
, bb
);
749 /* Redirect the outgoing edges. */
750 new_bb
->succs
= bb
->succs
;
752 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
755 /* The new block starts off being dirty. */
756 df_set_bb_dirty (bb
);
760 /* Return true if the single edge between blocks A and B is the only place
761 in RTL which holds some unique locus. */
764 unique_locus_on_edge_between_p (basic_block a
, basic_block b
)
766 const location_t goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
767 rtx_insn
*insn
, *end
;
769 if (LOCATION_LOCUS (goto_locus
) == UNKNOWN_LOCATION
)
772 /* First scan block A backward. */
774 end
= PREV_INSN (BB_HEAD (a
));
775 while (insn
!= end
&& (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
776 insn
= PREV_INSN (insn
);
778 if (insn
!= end
&& INSN_LOCATION (insn
) == goto_locus
)
781 /* Then scan block B forward. */
785 end
= NEXT_INSN (BB_END (b
));
786 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
787 insn
= NEXT_INSN (insn
);
789 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
790 && INSN_LOCATION (insn
) == goto_locus
)
797 /* If the single edge between blocks A and B is the only place in RTL which
798 holds some unique locus, emit a nop with that locus between the blocks. */
801 emit_nop_for_unique_locus_between (basic_block a
, basic_block b
)
803 if (!unique_locus_on_edge_between_p (a
, b
))
806 BB_END (a
) = emit_insn_after_noloc (gen_nop (), BB_END (a
), a
);
807 INSN_LOCATION (BB_END (a
)) = EDGE_SUCC (a
, 0)->goto_locus
;
810 /* Blocks A and B are to be merged into a single block A. The insns
811 are already contiguous. */
814 rtl_merge_blocks (basic_block a
, basic_block b
)
816 rtx_insn
*b_head
= BB_HEAD (b
), *b_end
= BB_END (b
), *a_end
= BB_END (a
);
817 rtx_insn
*del_first
= NULL
, *del_last
= NULL
;
818 rtx_insn
*b_debug_start
= b_end
, *b_debug_end
= b_end
;
819 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
823 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
826 while (DEBUG_INSN_P (b_end
))
827 b_end
= PREV_INSN (b_debug_start
= b_end
);
829 /* If there was a CODE_LABEL beginning B, delete it. */
830 if (LABEL_P (b_head
))
832 /* Detect basic blocks with nothing but a label. This can happen
833 in particular at the end of a function. */
837 del_first
= del_last
= b_head
;
838 b_head
= NEXT_INSN (b_head
);
841 /* Delete the basic block note and handle blocks containing just that
843 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
851 b_head
= NEXT_INSN (b_head
);
854 /* If there was a jump out of A, delete it. */
859 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
861 || NOTE_INSN_BASIC_BLOCK_P (prev
)
862 || prev
== BB_HEAD (a
))
867 /* If this was a conditional jump, we need to also delete
868 the insn that set cc0. */
869 if (HAVE_cc0
&& only_sets_cc0_p (prev
))
871 rtx_insn
*tmp
= prev
;
873 prev
= prev_nonnote_insn (prev
);
879 a_end
= PREV_INSN (del_first
);
881 else if (BARRIER_P (NEXT_INSN (a_end
)))
882 del_first
= NEXT_INSN (a_end
);
884 /* Delete everything marked above as well as crap that might be
885 hanging out between the two blocks. */
887 BB_HEAD (b
) = b_empty
? NULL
: b_head
;
888 delete_insn_chain (del_first
, del_last
, true);
890 /* When not optimizing and the edge is the only place in RTL which holds
891 some unique locus, emit a nop with that locus in between. */
894 emit_nop_for_unique_locus_between (a
, b
);
898 /* Reassociate the insns of B with A. */
901 update_bb_for_insn_chain (a_end
, b_debug_end
, a
);
903 BB_END (a
) = b_debug_end
;
906 else if (b_end
!= b_debug_end
)
908 /* Move any deleted labels and other notes between the end of A
909 and the debug insns that make up B after the debug insns,
910 bringing the debug insns into A while keeping the notes after
912 if (NEXT_INSN (a_end
) != b_debug_start
)
913 reorder_insns_nobb (NEXT_INSN (a_end
), PREV_INSN (b_debug_start
),
915 update_bb_for_insn_chain (b_debug_start
, b_debug_end
, a
);
916 BB_END (a
) = b_debug_end
;
919 df_bb_delete (b
->index
);
921 /* If B was a forwarder block, propagate the locus on the edge. */
923 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
924 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
927 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
931 /* Return true when block A and B can be merged. */
934 rtl_can_merge_blocks (basic_block a
, basic_block b
)
936 /* If we are partitioning hot/cold basic blocks, we don't want to
937 mess up unconditional or indirect jumps that cross between hot
940 Basic block partitioning may result in some jumps that appear to
941 be optimizable (or blocks that appear to be mergeable), but which really
942 must be left untouched (they are required to make it safely across
943 partition boundaries). See the comments at the top of
944 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
946 if (BB_PARTITION (a
) != BB_PARTITION (b
))
949 /* Protect the loop latches. */
950 if (current_loops
&& b
->loop_father
->latch
== b
)
953 /* There must be exactly one edge in between the blocks. */
954 return (single_succ_p (a
)
955 && single_succ (a
) == b
958 /* Must be simple edge. */
959 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
961 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
962 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
963 /* If the jump insn has side effects,
964 we can't kill the edge. */
965 && (!JUMP_P (BB_END (a
))
967 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
970 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
974 block_label (basic_block block
)
976 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
979 if (!LABEL_P (BB_HEAD (block
)))
981 BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
984 return as_a
<rtx_code_label
*> (BB_HEAD (block
));
987 /* Attempt to perform edge redirection by replacing possibly complex jump
988 instruction by unconditional jump or removing jump completely. This can
989 apply only if all edges now point to the same block. The parameters and
990 return values are equivalent to redirect_edge_and_branch. */
993 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
995 basic_block src
= e
->src
;
996 rtx_insn
*insn
= BB_END (src
), *kill_from
;
1000 /* If we are partitioning hot/cold basic blocks, we don't want to
1001 mess up unconditional or indirect jumps that cross between hot
1004 Basic block partitioning may result in some jumps that appear to
1005 be optimizable (or blocks that appear to be mergeable), but which really
1006 must be left untouched (they are required to make it safely across
1007 partition boundaries). See the comments at the top of
1008 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1010 if (BB_PARTITION (src
) != BB_PARTITION (target
))
1013 /* We can replace or remove a complex jump only when we have exactly
1014 two edges. Also, if we have exactly one outgoing edge, we can
1016 if (EDGE_COUNT (src
->succs
) >= 3
1017 /* Verify that all targets will be TARGET. Specifically, the
1018 edge that is not E must also go to TARGET. */
1019 || (EDGE_COUNT (src
->succs
) == 2
1020 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
1023 if (!onlyjump_p (insn
))
1025 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
1028 /* Avoid removing branch with side effects. */
1029 set
= single_set (insn
);
1030 if (!set
|| side_effects_p (set
))
1033 /* In case we zap a conditional jump, we'll need to kill
1034 the cc0 setter too. */
1036 if (HAVE_cc0
&& reg_mentioned_p (cc0_rtx
, PATTERN (insn
))
1037 && only_sets_cc0_p (PREV_INSN (insn
)))
1038 kill_from
= PREV_INSN (insn
);
1040 /* See if we can create the fallthru edge. */
1041 if (in_cfglayout
|| can_fallthru (src
, target
))
1044 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
1047 /* Selectively unlink whole insn chain. */
1050 rtx_insn
*insn
= BB_FOOTER (src
);
1052 delete_insn_chain (kill_from
, BB_END (src
), false);
1054 /* Remove barriers but keep jumptables. */
1057 if (BARRIER_P (insn
))
1059 if (PREV_INSN (insn
))
1060 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1062 BB_FOOTER (src
) = NEXT_INSN (insn
);
1063 if (NEXT_INSN (insn
))
1064 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1068 insn
= NEXT_INSN (insn
);
1072 delete_insn_chain (kill_from
, PREV_INSN (BB_HEAD (target
)),
1076 /* If this already is simplejump, redirect it. */
1077 else if (simplejump_p (insn
))
1079 if (e
->dest
== target
)
1082 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
1083 INSN_UID (insn
), e
->dest
->index
, target
->index
);
1084 if (!redirect_jump (as_a
<rtx_jump_insn
*> (insn
),
1085 block_label (target
), 0))
1087 gcc_assert (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1092 /* Cannot do anything for target exit block. */
1093 else if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1096 /* Or replace possibly complicated jump insn by simple jump insn. */
1099 rtx_code_label
*target_label
= block_label (target
);
1102 rtx_jump_table_data
*table
;
1104 emit_jump_insn_after_noloc (targetm
.gen_jump (target_label
), insn
);
1105 JUMP_LABEL (BB_END (src
)) = target_label
;
1106 LABEL_NUSES (target_label
)++;
1108 fprintf (dump_file
, "Replacing insn %i by jump %i\n",
1109 INSN_UID (insn
), INSN_UID (BB_END (src
)));
1112 delete_insn_chain (kill_from
, insn
, false);
1114 /* Recognize a tablejump that we are converting to a
1115 simple jump and remove its associated CODE_LABEL
1116 and ADDR_VEC or ADDR_DIFF_VEC. */
1117 if (tablejump_p (insn
, &label
, &table
))
1118 delete_insn_chain (label
, table
, false);
1120 barrier
= next_nonnote_insn (BB_END (src
));
1121 if (!barrier
|| !BARRIER_P (barrier
))
1122 emit_barrier_after (BB_END (src
));
1125 if (barrier
!= NEXT_INSN (BB_END (src
)))
1127 /* Move the jump before barrier so that the notes
1128 which originally were or were created before jump table are
1129 inside the basic block. */
1130 rtx_insn
*new_insn
= BB_END (src
);
1132 update_bb_for_insn_chain (NEXT_INSN (BB_END (src
)),
1133 PREV_INSN (barrier
), src
);
1135 SET_NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
1136 SET_PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
1138 SET_NEXT_INSN (new_insn
) = barrier
;
1139 SET_NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
1141 SET_PREV_INSN (new_insn
) = PREV_INSN (barrier
);
1142 SET_PREV_INSN (barrier
) = new_insn
;
1147 /* Keep only one edge out and set proper flags. */
1148 if (!single_succ_p (src
))
1150 gcc_assert (single_succ_p (src
));
1152 e
= single_succ_edge (src
);
1154 e
->flags
= EDGE_FALLTHRU
;
1158 e
->probability
= profile_probability::always ();
1160 if (e
->dest
!= target
)
1161 redirect_edge_succ (e
, target
);
1165 /* Subroutine of redirect_branch_edge that tries to patch the jump
1166 instruction INSN so that it reaches block NEW. Do this
1167 only when it originally reached block OLD. Return true if this
1168 worked or the original target wasn't OLD, return false if redirection
1172 patch_jump_insn (rtx_insn
*insn
, rtx_insn
*old_label
, basic_block new_bb
)
1174 rtx_jump_table_data
*table
;
1176 /* Recognize a tablejump and adjust all matching cases. */
1177 if (tablejump_p (insn
, NULL
, &table
))
1181 rtx_code_label
*new_label
= block_label (new_bb
);
1183 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1185 vec
= table
->get_labels ();
1187 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
1188 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
1190 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
1191 --LABEL_NUSES (old_label
);
1192 ++LABEL_NUSES (new_label
);
1195 /* Handle casesi dispatch insns. */
1196 if ((tmp
= single_set (insn
)) != NULL
1197 && SET_DEST (tmp
) == pc_rtx
1198 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
1199 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
1200 && label_ref_label (XEXP (SET_SRC (tmp
), 2)) == old_label
)
1202 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
1204 --LABEL_NUSES (old_label
);
1205 ++LABEL_NUSES (new_label
);
1208 else if ((tmp
= extract_asm_operands (PATTERN (insn
))) != NULL
)
1210 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (tmp
);
1213 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1215 rtx_code_label
*new_label
= block_label (new_bb
);
1217 for (i
= 0; i
< n
; ++i
)
1219 rtx old_ref
= ASM_OPERANDS_LABEL (tmp
, i
);
1220 gcc_assert (GET_CODE (old_ref
) == LABEL_REF
);
1221 if (XEXP (old_ref
, 0) == old_label
)
1223 ASM_OPERANDS_LABEL (tmp
, i
)
1224 = gen_rtx_LABEL_REF (Pmode
, new_label
);
1225 --LABEL_NUSES (old_label
);
1226 ++LABEL_NUSES (new_label
);
1230 if (JUMP_LABEL (insn
) == old_label
)
1232 JUMP_LABEL (insn
) = new_label
;
1233 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1235 remove_note (insn
, note
);
1239 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1241 remove_note (insn
, note
);
1242 if (JUMP_LABEL (insn
) != new_label
1243 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1244 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1246 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1248 XEXP (note
, 0) = new_label
;
1252 /* ?? We may play the games with moving the named labels from
1253 one basic block to the other in case only one computed_jump is
1255 if (computed_jump_p (insn
)
1256 /* A return instruction can't be redirected. */
1257 || returnjump_p (insn
))
1260 if (!currently_expanding_to_rtl
|| JUMP_LABEL (insn
) == old_label
)
1262 /* If the insn doesn't go where we think, we're confused. */
1263 gcc_assert (JUMP_LABEL (insn
) == old_label
);
1265 /* If the substitution doesn't succeed, die. This can happen
1266 if the back end emitted unrecognizable instructions or if
1267 target is exit block on some arches. */
1268 if (!redirect_jump (as_a
<rtx_jump_insn
*> (insn
),
1269 block_label (new_bb
), 0))
1271 gcc_assert (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1280 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1283 redirect_branch_edge (edge e
, basic_block target
)
1285 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1286 basic_block src
= e
->src
;
1287 rtx_insn
*insn
= BB_END (src
);
1289 /* We can only redirect non-fallthru edges of jump insn. */
1290 if (e
->flags
& EDGE_FALLTHRU
)
1292 else if (!JUMP_P (insn
) && !currently_expanding_to_rtl
)
1295 if (!currently_expanding_to_rtl
)
1297 if (!patch_jump_insn (as_a
<rtx_jump_insn
*> (insn
), old_label
, target
))
1301 /* When expanding this BB might actually contain multiple
1302 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1303 Redirect all of those that match our label. */
1304 FOR_BB_INSNS (src
, insn
)
1305 if (JUMP_P (insn
) && !patch_jump_insn (as_a
<rtx_jump_insn
*> (insn
),
1310 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
1311 e
->src
->index
, e
->dest
->index
, target
->index
);
1313 if (e
->dest
!= target
)
1314 e
= redirect_edge_succ_nodup (e
, target
);
1319 /* Called when edge E has been redirected to a new destination,
1320 in order to update the region crossing flag on the edge and
1324 fixup_partition_crossing (edge e
)
1326 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || e
->dest
1327 == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1329 /* If we redirected an existing edge, it may already be marked
1330 crossing, even though the new src is missing a reg crossing note.
1331 But make sure reg crossing note doesn't already exist before
1333 if (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1335 e
->flags
|= EDGE_CROSSING
;
1336 if (JUMP_P (BB_END (e
->src
))
1337 && !CROSSING_JUMP_P (BB_END (e
->src
)))
1338 CROSSING_JUMP_P (BB_END (e
->src
)) = 1;
1340 else if (BB_PARTITION (e
->src
) == BB_PARTITION (e
->dest
))
1342 e
->flags
&= ~EDGE_CROSSING
;
1343 /* Remove the section crossing note from jump at end of
1344 src if it exists, and if no other successors are
1346 if (JUMP_P (BB_END (e
->src
)) && CROSSING_JUMP_P (BB_END (e
->src
)))
1348 bool has_crossing_succ
= false;
1351 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
1353 has_crossing_succ
|= (e2
->flags
& EDGE_CROSSING
);
1354 if (has_crossing_succ
)
1357 if (!has_crossing_succ
)
1358 CROSSING_JUMP_P (BB_END (e
->src
)) = 0;
1363 /* Called when block BB has been reassigned to the cold partition,
1364 because it is now dominated by another cold block,
1365 to ensure that the region crossing attributes are updated. */
1368 fixup_new_cold_bb (basic_block bb
)
1373 /* This is called when a hot bb is found to now be dominated
1374 by a cold bb and therefore needs to become cold. Therefore,
1375 its preds will no longer be region crossing. Any non-dominating
1376 preds that were previously hot would also have become cold
1377 in the caller for the same region. Any preds that were previously
1378 region-crossing will be adjusted in fixup_partition_crossing. */
1379 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1381 fixup_partition_crossing (e
);
1384 /* Possibly need to make bb's successor edges region crossing,
1385 or remove stale region crossing. */
1386 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1388 /* We can't have fall-through edges across partition boundaries.
1389 Note that force_nonfallthru will do any necessary partition
1390 boundary fixup by calling fixup_partition_crossing itself. */
1391 if ((e
->flags
& EDGE_FALLTHRU
)
1392 && BB_PARTITION (bb
) != BB_PARTITION (e
->dest
)
1393 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1394 force_nonfallthru (e
);
1396 fixup_partition_crossing (e
);
1400 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1401 expense of adding new instructions or reordering basic blocks.
1403 Function can be also called with edge destination equivalent to the TARGET.
1404 Then it should try the simplifications and do nothing if none is possible.
1406 Return edge representing the branch if transformation succeeded. Return NULL
1408 We still return NULL in case E already destinated TARGET and we didn't
1409 managed to simplify instruction stream. */
1412 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
1415 basic_block src
= e
->src
;
1416 basic_block dest
= e
->dest
;
1418 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1424 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
1426 df_set_bb_dirty (src
);
1427 fixup_partition_crossing (ret
);
1431 ret
= redirect_branch_edge (e
, target
);
1435 df_set_bb_dirty (src
);
1436 fixup_partition_crossing (ret
);
1440 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1443 emit_barrier_after_bb (basic_block bb
)
1445 rtx_barrier
*barrier
= emit_barrier_after (BB_END (bb
));
1446 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1447 || current_ir_type () == IR_RTL_CFGLAYOUT
);
1448 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
1450 rtx_insn
*insn
= unlink_insn_chain (barrier
, barrier
);
1454 rtx_insn
*footer_tail
= BB_FOOTER (bb
);
1456 while (NEXT_INSN (footer_tail
))
1457 footer_tail
= NEXT_INSN (footer_tail
);
1458 if (!BARRIER_P (footer_tail
))
1460 SET_NEXT_INSN (footer_tail
) = insn
;
1461 SET_PREV_INSN (insn
) = footer_tail
;
1465 BB_FOOTER (bb
) = insn
;
1469 /* Like force_nonfallthru below, but additionally performs redirection
1470 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1471 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1472 simple_return_rtx, indicating which kind of returnjump to create.
1473 It should be NULL otherwise. */
1476 force_nonfallthru_and_redirect (edge e
, basic_block target
, rtx jump_label
)
1478 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
1481 int abnormal_edge_flags
= 0;
1482 bool asm_goto_edge
= false;
1485 /* In the case the last instruction is conditional jump to the next
1486 instruction, first redirect the jump itself and then continue
1487 by creating a basic block afterwards to redirect fallthru edge. */
1488 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1489 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1490 && any_condjump_p (BB_END (e
->src
))
1491 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1494 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1497 redirected
= redirect_jump (as_a
<rtx_jump_insn
*> (BB_END (e
->src
)),
1498 block_label (target
), 0);
1499 gcc_assert (redirected
);
1501 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1504 int prob
= XINT (note
, 0);
1506 b
->probability
= profile_probability::from_reg_br_prob_note (prob
);
1507 e
->probability
-= e
->probability
;
1511 if (e
->flags
& EDGE_ABNORMAL
)
1513 /* Irritating special case - fallthru edge to the same block as abnormal
1515 We can't redirect abnormal edge, but we still can split the fallthru
1516 one and create separate abnormal edge to original destination.
1517 This allows bb-reorder to make such edge non-fallthru. */
1518 gcc_assert (e
->dest
== target
);
1519 abnormal_edge_flags
= e
->flags
& ~EDGE_FALLTHRU
;
1520 e
->flags
&= EDGE_FALLTHRU
;
1524 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1525 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1527 /* We can't redirect the entry block. Create an empty block
1528 at the start of the function which we use to add the new
1534 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
,
1535 ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1536 bb
->count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
;
1538 /* Change the existing edge's source to be the new block, and add
1539 a new edge from the entry block to the new block. */
1541 for (ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
1542 (tmp
= ei_safe_edge (ei
)); )
1546 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
->unordered_remove (ei
.index
);
1556 vec_safe_push (bb
->succs
, e
);
1557 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
,
1562 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1563 don't point to the target or fallthru label. */
1564 if (JUMP_P (BB_END (e
->src
))
1565 && target
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1566 && (e
->flags
& EDGE_FALLTHRU
)
1567 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
1569 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
1570 bool adjust_jump_target
= false;
1572 for (i
= 0; i
< n
; ++i
)
1574 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (e
->dest
))
1576 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))--;
1577 XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) = block_label (target
);
1578 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))++;
1579 adjust_jump_target
= true;
1581 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (target
))
1582 asm_goto_edge
= true;
1584 if (adjust_jump_target
)
1586 rtx_insn
*insn
= BB_END (e
->src
);
1588 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1589 rtx_insn
*new_label
= BB_HEAD (target
);
1591 if (JUMP_LABEL (insn
) == old_label
)
1593 JUMP_LABEL (insn
) = new_label
;
1594 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1596 remove_note (insn
, note
);
1600 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1602 remove_note (insn
, note
);
1603 if (JUMP_LABEL (insn
) != new_label
1604 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1605 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1607 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1609 XEXP (note
, 0) = new_label
;
1613 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
|| asm_goto_edge
)
1616 profile_count count
= e
->count ();
1617 profile_probability probability
= e
->probability
;
1618 /* Create the new structures. */
1620 /* If the old block ended with a tablejump, skip its table
1621 by searching forward from there. Otherwise start searching
1622 forward from the last instruction of the old block. */
1623 rtx_jump_table_data
*table
;
1624 if (tablejump_p (BB_END (e
->src
), NULL
, &table
))
1627 new_head
= BB_END (e
->src
);
1628 new_head
= NEXT_INSN (new_head
);
1629 /* Make sure we don't split a call and its corresponding
1630 CALL_ARG_LOCATION note. */
1631 if (new_head
&& NOTE_P (new_head
)
1632 && NOTE_KIND (new_head
) == NOTE_INSN_CALL_ARG_LOCATION
)
1633 new_head
= NEXT_INSN (new_head
);
1635 jump_block
= create_basic_block (new_head
, NULL
, e
->src
);
1636 jump_block
->count
= count
;
1638 /* Make sure new block ends up in correct hot/cold section. */
1640 BB_COPY_PARTITION (jump_block
, e
->src
);
1643 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1644 new_edge
->probability
= probability
;
1646 /* Redirect old edge. */
1647 redirect_edge_pred (e
, jump_block
);
1648 e
->probability
= profile_probability::always ();
1650 /* If e->src was previously region crossing, it no longer is
1651 and the reg crossing note should be removed. */
1652 fixup_partition_crossing (new_edge
);
1654 /* If asm goto has any label refs to target's label,
1655 add also edge from asm goto bb to target. */
1658 new_edge
->probability
= new_edge
->probability
.apply_scale (1, 2);
1659 jump_block
->count
= jump_block
->count
.apply_scale (1, 2);
1660 edge new_edge2
= make_edge (new_edge
->src
, target
,
1661 e
->flags
& ~EDGE_FALLTHRU
);
1662 new_edge2
->probability
= probability
- new_edge
->probability
;
1665 new_bb
= jump_block
;
1668 jump_block
= e
->src
;
1670 loc
= e
->goto_locus
;
1671 e
->flags
&= ~EDGE_FALLTHRU
;
1672 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1674 if (jump_label
== ret_rtx
)
1675 emit_jump_insn_after_setloc (targetm
.gen_return (),
1676 BB_END (jump_block
), loc
);
1679 gcc_assert (jump_label
== simple_return_rtx
);
1680 emit_jump_insn_after_setloc (targetm
.gen_simple_return (),
1681 BB_END (jump_block
), loc
);
1683 set_return_jump_label (BB_END (jump_block
));
1687 rtx_code_label
*label
= block_label (target
);
1688 emit_jump_insn_after_setloc (targetm
.gen_jump (label
),
1689 BB_END (jump_block
), loc
);
1690 JUMP_LABEL (BB_END (jump_block
)) = label
;
1691 LABEL_NUSES (label
)++;
1694 /* We might be in cfg layout mode, and if so, the following routine will
1695 insert the barrier correctly. */
1696 emit_barrier_after_bb (jump_block
);
1697 redirect_edge_succ_nodup (e
, target
);
1699 if (abnormal_edge_flags
)
1700 make_edge (src
, target
, abnormal_edge_flags
);
1702 df_mark_solutions_dirty ();
1703 fixup_partition_crossing (e
);
1707 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1708 (and possibly create new basic block) to make edge non-fallthru.
1709 Return newly created BB or NULL if none. */
1712 rtl_force_nonfallthru (edge e
)
1714 return force_nonfallthru_and_redirect (e
, e
->dest
, NULL_RTX
);
1717 /* Redirect edge even at the expense of creating new jump insn or
1718 basic block. Return new basic block if created, NULL otherwise.
1719 Conversion must be possible. */
1722 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1724 if (redirect_edge_and_branch (e
, target
)
1725 || e
->dest
== target
)
1728 /* In case the edge redirection failed, try to force it to be non-fallthru
1729 and redirect newly created simplejump. */
1730 df_set_bb_dirty (e
->src
);
1731 return force_nonfallthru_and_redirect (e
, target
, NULL_RTX
);
1734 /* The given edge should potentially be a fallthru edge. If that is in
1735 fact true, delete the jump and barriers that are in the way. */
1738 rtl_tidy_fallthru_edge (edge e
)
1741 basic_block b
= e
->src
, c
= b
->next_bb
;
1743 /* ??? In a late-running flow pass, other folks may have deleted basic
1744 blocks by nopping out blocks, leaving multiple BARRIERs between here
1745 and the target label. They ought to be chastised and fixed.
1747 We can also wind up with a sequence of undeletable labels between
1748 one block and the next.
1750 So search through a sequence of barriers, labels, and notes for
1751 the head of block C and assert that we really do fall through. */
1753 for (q
= NEXT_INSN (BB_END (b
)); q
!= BB_HEAD (c
); q
= NEXT_INSN (q
))
1757 /* Remove what will soon cease being the jump insn from the source block.
1758 If block B consisted only of this single jump, turn it into a deleted
1763 && (any_uncondjump_p (q
)
1764 || single_succ_p (b
)))
1767 rtx_jump_table_data
*table
;
1769 if (tablejump_p (q
, &label
, &table
))
1771 /* The label is likely mentioned in some instruction before
1772 the tablejump and might not be DCEd, so turn it into
1773 a note instead and move before the tablejump that is going to
1775 const char *name
= LABEL_NAME (label
);
1776 PUT_CODE (label
, NOTE
);
1777 NOTE_KIND (label
) = NOTE_INSN_DELETED_LABEL
;
1778 NOTE_DELETED_LABEL_NAME (label
) = name
;
1779 reorder_insns (label
, label
, PREV_INSN (q
));
1780 delete_insn (table
);
1783 /* If this was a conditional jump, we need to also delete
1784 the insn that set cc0. */
1785 if (HAVE_cc0
&& any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1790 /* Unconditional jumps with side-effects (i.e. which we can't just delete
1791 together with the barrier) should never have a fallthru edge. */
1792 else if (JUMP_P (q
) && any_uncondjump_p (q
))
1795 /* Selectively unlink the sequence. */
1796 if (q
!= PREV_INSN (BB_HEAD (c
)))
1797 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1799 e
->flags
|= EDGE_FALLTHRU
;
1802 /* Should move basic block BB after basic block AFTER. NIY. */
1805 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1806 basic_block after ATTRIBUTE_UNUSED
)
1811 /* Locate the last bb in the same partition as START_BB. */
1814 last_bb_in_partition (basic_block start_bb
)
1817 FOR_BB_BETWEEN (bb
, start_bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1819 if (BB_PARTITION (start_bb
) != BB_PARTITION (bb
->next_bb
))
1822 /* Return bb before the exit block. */
1826 /* Split a (typically critical) edge. Return the new block.
1827 The edge must not be abnormal.
1829 ??? The code generally expects to be called on critical edges.
1830 The case of a block ending in an unconditional jump to a
1831 block with multiple predecessors is not handled optimally. */
1834 rtl_split_edge (edge edge_in
)
1836 basic_block bb
, new_bb
;
1839 /* Abnormal edges cannot be split. */
1840 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1842 /* We are going to place the new block in front of edge destination.
1843 Avoid existence of fallthru predecessors. */
1844 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1846 edge e
= find_fallthru_edge (edge_in
->dest
->preds
);
1849 force_nonfallthru (e
);
1852 /* Create the basic block note. */
1853 if (edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1854 before
= BB_HEAD (edge_in
->dest
);
1858 /* If this is a fall through edge to the exit block, the blocks might be
1859 not adjacent, and the right place is after the source. */
1860 if ((edge_in
->flags
& EDGE_FALLTHRU
)
1861 && edge_in
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1863 before
= NEXT_INSN (BB_END (edge_in
->src
));
1864 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1865 BB_COPY_PARTITION (bb
, edge_in
->src
);
1869 if (edge_in
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1871 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1872 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1876 basic_block after
= edge_in
->dest
->prev_bb
;
1877 /* If this is post-bb reordering, and the edge crosses a partition
1878 boundary, the new block needs to be inserted in the bb chain
1879 at the end of the src partition (since we put the new bb into
1880 that partition, see below). Otherwise we may end up creating
1881 an extra partition crossing in the chain, which is illegal.
1882 It can't go after the src, because src may have a fall-through
1883 to a different block. */
1884 if (crtl
->bb_reorder_complete
1885 && (edge_in
->flags
& EDGE_CROSSING
))
1887 after
= last_bb_in_partition (edge_in
->src
);
1888 before
= get_last_bb_insn (after
);
1889 /* The instruction following the last bb in partition should
1890 be a barrier, since it cannot end in a fall-through. */
1891 gcc_checking_assert (BARRIER_P (before
));
1892 before
= NEXT_INSN (before
);
1894 bb
= create_basic_block (before
, NULL
, after
);
1895 /* Put the split bb into the src partition, to avoid creating
1896 a situation where a cold bb dominates a hot bb, in the case
1897 where src is cold and dest is hot. The src will dominate
1898 the new bb (whereas it might not have dominated dest). */
1899 BB_COPY_PARTITION (bb
, edge_in
->src
);
1903 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1905 /* Can't allow a region crossing edge to be fallthrough. */
1906 if (BB_PARTITION (bb
) != BB_PARTITION (edge_in
->dest
)
1907 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1909 new_bb
= force_nonfallthru (single_succ_edge (bb
));
1910 gcc_assert (!new_bb
);
1913 /* For non-fallthru edges, we must adjust the predecessor's
1914 jump instruction to target our new block. */
1915 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1917 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1918 gcc_assert (redirected
);
1922 if (edge_in
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1924 /* For asm goto even splitting of fallthru edge might
1925 need insn patching, as other labels might point to the
1927 rtx_insn
*last
= BB_END (edge_in
->src
);
1930 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1931 && (extract_asm_operands (PATTERN (last
))
1932 || JUMP_LABEL (last
) == before
)
1933 && patch_jump_insn (last
, before
, bb
))
1934 df_set_bb_dirty (edge_in
->src
);
1936 redirect_edge_succ (edge_in
, bb
);
1942 /* Queue instructions for insertion on an edge between two basic blocks.
1943 The new instructions and basic blocks (if any) will not appear in the
1944 CFG until commit_edge_insertions is called. */
1947 insert_insn_on_edge (rtx pattern
, edge e
)
1949 /* We cannot insert instructions on an abnormal critical edge.
1950 It will be easier to find the culprit if we die now. */
1951 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1953 if (e
->insns
.r
== NULL_RTX
)
1956 push_to_sequence (e
->insns
.r
);
1958 emit_insn (pattern
);
1960 e
->insns
.r
= get_insns ();
1964 /* Update the CFG for the instructions queued on edge E. */
1967 commit_one_edge_insertion (edge e
)
1969 rtx_insn
*before
= NULL
, *after
= NULL
, *insns
, *tmp
, *last
;
1972 /* Pull the insns off the edge now since the edge might go away. */
1976 /* Figure out where to put these insns. If the destination has
1977 one predecessor, insert there. Except for the exit block. */
1978 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1982 /* Get the location correct wrt a code label, and "nice" wrt
1983 a basic block note, and before everything else. */
1986 tmp
= NEXT_INSN (tmp
);
1987 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1988 tmp
= NEXT_INSN (tmp
);
1989 if (tmp
== BB_HEAD (bb
))
1992 after
= PREV_INSN (tmp
);
1994 after
= get_last_insn ();
1997 /* If the source has one successor and the edge is not abnormal,
1998 insert there. Except for the entry block.
1999 Don't do this if the predecessor ends in a jump other than
2000 unconditional simple jump. E.g. for asm goto that points all
2001 its labels at the fallthru basic block, we can't insert instructions
2002 before the asm goto, as the asm goto can have various of side effects,
2003 and can't emit instructions after the asm goto, as it must end
2005 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
2006 && single_succ_p (e
->src
)
2007 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2008 && (!JUMP_P (BB_END (e
->src
))
2009 || simplejump_p (BB_END (e
->src
))))
2013 /* It is possible to have a non-simple jump here. Consider a target
2014 where some forms of unconditional jumps clobber a register. This
2015 happens on the fr30 for example.
2017 We know this block has a single successor, so we can just emit
2018 the queued insns before the jump. */
2019 if (JUMP_P (BB_END (bb
)))
2020 before
= BB_END (bb
);
2023 /* We'd better be fallthru, or we've lost track of what's what. */
2024 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
2026 after
= BB_END (bb
);
2030 /* Otherwise we must split the edge. */
2033 bb
= split_edge (e
);
2035 /* If E crossed a partition boundary, we needed to make bb end in
2036 a region-crossing jump, even though it was originally fallthru. */
2037 if (JUMP_P (BB_END (bb
)))
2038 before
= BB_END (bb
);
2040 after
= BB_END (bb
);
2043 /* Now that we've found the spot, do the insertion. */
2046 emit_insn_before_noloc (insns
, before
, bb
);
2047 last
= prev_nonnote_insn (before
);
2050 last
= emit_insn_after_noloc (insns
, after
, bb
);
2052 if (returnjump_p (last
))
2054 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2055 This is not currently a problem because this only happens
2056 for the (single) epilogue, which already has a fallthru edge
2059 e
= single_succ_edge (bb
);
2060 gcc_assert (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2061 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
2063 e
->flags
&= ~EDGE_FALLTHRU
;
2064 emit_barrier_after (last
);
2067 delete_insn (before
);
2070 gcc_assert (!JUMP_P (last
));
2073 /* Update the CFG for all queued instructions. */
2076 commit_edge_insertions (void)
2080 /* Optimization passes that invoke this routine can cause hot blocks
2081 previously reached by both hot and cold blocks to become dominated only
2082 by cold blocks. This will cause the verification below to fail,
2083 and lead to now cold code in the hot section. In some cases this
2084 may only be visible after newly unreachable blocks are deleted,
2085 which will be done by fixup_partitions. */
2086 fixup_partitions ();
2088 checking_verify_flow_info ();
2090 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
2091 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
2096 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2098 commit_one_edge_insertion (e
);
2103 /* Print out RTL-specific basic block information (live information
2104 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2105 documented in dumpfile.h. */
2108 rtl_dump_bb (FILE *outf
, basic_block bb
, int indent
, dump_flags_t flags
)
2112 s_indent
= (char *) alloca ((size_t) indent
+ 1);
2113 memset (s_indent
, ' ', (size_t) indent
);
2114 s_indent
[indent
] = '\0';
2116 if (df
&& (flags
& TDF_DETAILS
))
2118 df_dump_top (bb
, outf
);
2122 if (bb
->index
!= ENTRY_BLOCK
&& bb
->index
!= EXIT_BLOCK
)
2124 rtx_insn
*last
= BB_END (bb
);
2126 last
= NEXT_INSN (last
);
2127 for (rtx_insn
*insn
= BB_HEAD (bb
); insn
!= last
; insn
= NEXT_INSN (insn
))
2129 if (flags
& TDF_DETAILS
)
2130 df_dump_insn_top (insn
, outf
);
2131 if (! (flags
& TDF_SLIM
))
2132 print_rtl_single (outf
, insn
);
2134 dump_insn_slim (outf
, insn
);
2135 if (flags
& TDF_DETAILS
)
2136 df_dump_insn_bottom (insn
, outf
);
2140 if (df
&& (flags
& TDF_DETAILS
))
2142 df_dump_bottom (bb
, outf
);
2148 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2149 for the start of each basic block. FLAGS are the TDF_* masks documented
2153 print_rtl_with_bb (FILE *outf
, const rtx_insn
*rtx_first
, dump_flags_t flags
)
2155 const rtx_insn
*tmp_rtx
;
2157 fprintf (outf
, "(nil)\n");
2160 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
2161 int max_uid
= get_max_uid ();
2162 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
2163 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
2164 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
2167 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2168 insns, but the CFG is not maintained so the basic block info
2169 is not reliable. Therefore it's omitted from the dumps. */
2170 if (! (cfun
->curr_properties
& PROP_cfg
))
2171 flags
&= ~TDF_BLOCKS
;
2174 df_dump_start (outf
);
2176 if (flags
& TDF_BLOCKS
)
2178 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2182 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
2183 end
[INSN_UID (BB_END (bb
))] = bb
;
2184 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
2186 enum bb_state state
= IN_MULTIPLE_BB
;
2188 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
2190 in_bb_p
[INSN_UID (x
)] = state
;
2192 if (x
== BB_END (bb
))
2198 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
2200 if (flags
& TDF_BLOCKS
)
2202 bb
= start
[INSN_UID (tmp_rtx
)];
2205 dump_bb_info (outf
, bb
, 0, dump_flags
, true, false);
2206 if (df
&& (flags
& TDF_DETAILS
))
2207 df_dump_top (bb
, outf
);
2210 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
2211 && !NOTE_P (tmp_rtx
)
2212 && !BARRIER_P (tmp_rtx
))
2213 fprintf (outf
, ";; Insn is not within a basic block\n");
2214 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
2215 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
2218 if (flags
& TDF_DETAILS
)
2219 df_dump_insn_top (tmp_rtx
, outf
);
2220 if (! (flags
& TDF_SLIM
))
2221 print_rtl_single (outf
, tmp_rtx
);
2223 dump_insn_slim (outf
, tmp_rtx
);
2224 if (flags
& TDF_DETAILS
)
2225 df_dump_insn_bottom (tmp_rtx
, outf
);
2227 if (flags
& TDF_BLOCKS
)
2229 bb
= end
[INSN_UID (tmp_rtx
)];
2232 dump_bb_info (outf
, bb
, 0, dump_flags
, false, true);
2233 if (df
&& (flags
& TDF_DETAILS
))
2234 df_dump_bottom (bb
, outf
);
2246 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2249 update_br_prob_note (basic_block bb
)
2252 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
2253 if (!JUMP_P (BB_END (bb
)) || !BRANCH_EDGE (bb
)->probability
.initialized_p ())
2257 rtx
*note_link
, this_rtx
;
2259 note_link
= ®_NOTES (BB_END (bb
));
2260 for (this_rtx
= *note_link
; this_rtx
; this_rtx
= XEXP (this_rtx
, 1))
2261 if (this_rtx
== note
)
2263 *note_link
= XEXP (this_rtx
, 1);
2270 || XINT (note
, 0) == BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ())
2272 XINT (note
, 0) = BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ();
2275 /* Get the last insn associated with block BB (that includes barriers and
2276 tablejumps after BB). */
2278 get_last_bb_insn (basic_block bb
)
2280 rtx_jump_table_data
*table
;
2282 rtx_insn
*end
= BB_END (bb
);
2284 /* Include any jump table following the basic block. */
2285 if (tablejump_p (end
, NULL
, &table
))
2288 /* Include any barriers that may follow the basic block. */
2289 tmp
= next_nonnote_insn_bb (end
);
2290 while (tmp
&& BARRIER_P (tmp
))
2293 tmp
= next_nonnote_insn_bb (end
);
2299 /* Add all BBs reachable from entry via hot paths into the SET. */
2302 find_bbs_reachable_by_hot_paths (hash_set
<basic_block
> *set
)
2304 auto_vec
<basic_block
, 64> worklist
;
2306 set
->add (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
2307 worklist
.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
2309 while (worklist
.length () > 0)
2311 basic_block bb
= worklist
.pop ();
2315 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2316 if (BB_PARTITION (e
->dest
) != BB_COLD_PARTITION
2317 && !set
->add (e
->dest
))
2318 worklist
.safe_push (e
->dest
);
2322 /* Sanity check partition hotness to ensure that basic blocks in
2323 Â the cold partition don't dominate basic blocks in the hot partition.
2324 If FLAG_ONLY is true, report violations as errors. Otherwise
2325 re-mark the dominated blocks as cold, since this is run after
2326 cfg optimizations that may make hot blocks previously reached
2327 by both hot and cold blocks now only reachable along cold paths. */
2329 static vec
<basic_block
>
2330 find_partition_fixes (bool flag_only
)
2333 vec
<basic_block
> bbs_in_cold_partition
= vNULL
;
2334 vec
<basic_block
> bbs_to_fix
= vNULL
;
2335 hash_set
<basic_block
> set
;
2337 /* Callers check this. */
2338 gcc_checking_assert (crtl
->has_bb_partition
);
2340 find_bbs_reachable_by_hot_paths (&set
);
2342 FOR_EACH_BB_FN (bb
, cfun
)
2343 if (!set
.contains (bb
)
2344 && BB_PARTITION (bb
) != BB_COLD_PARTITION
)
2347 error ("non-cold basic block %d reachable only "
2348 "by paths crossing the cold partition", bb
->index
);
2350 BB_SET_PARTITION (bb
, BB_COLD_PARTITION
);
2351 bbs_to_fix
.safe_push (bb
);
2352 bbs_in_cold_partition
.safe_push (bb
);
2358 /* Perform cleanup on the hot/cold bb partitioning after optimization
2359 passes that modify the cfg. */
2362 fixup_partitions (void)
2366 if (!crtl
->has_bb_partition
)
2369 /* Delete any blocks that became unreachable and weren't
2370 already cleaned up, for example during edge forwarding
2371 and convert_jumps_to_returns. This will expose more
2372 opportunities for fixing the partition boundaries here.
2373 Also, the calculation of the dominance graph during verification
2374 will assert if there are unreachable nodes. */
2375 delete_unreachable_blocks ();
2377 /* If there are partitions, do a sanity check on them: A basic block in
2378 Â a cold partition cannot dominate a basic block in a hot partition.
2379 Fixup any that now violate this requirement, as a result of edge
2380 forwarding and unreachable block deletion. Â */
2381 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (false);
2383 /* Do the partition fixup after all necessary blocks have been converted to
2384 cold, so that we only update the region crossings the minimum number of
2385 places, which can require forcing edges to be non fallthru. */
2386 while (! bbs_to_fix
.is_empty ())
2388 bb
= bbs_to_fix
.pop ();
2389 fixup_new_cold_bb (bb
);
2393 /* Verify, in the basic block chain, that there is at most one switch
2394 between hot/cold partitions. This condition will not be true until
2395 after reorder_basic_blocks is called. */
2398 verify_hot_cold_block_grouping (void)
2402 bool switched_sections
= false;
2403 int current_partition
= BB_UNPARTITIONED
;
2405 /* Even after bb reordering is complete, we go into cfglayout mode
2406 again (in compgoto). Ensure we don't call this before going back
2407 into linearized RTL when any layout fixes would have been committed. */
2408 if (!crtl
->bb_reorder_complete
2409 || current_ir_type () != IR_RTL_CFGRTL
)
2412 FOR_EACH_BB_FN (bb
, cfun
)
2414 if (current_partition
!= BB_UNPARTITIONED
2415 && BB_PARTITION (bb
) != current_partition
)
2417 if (switched_sections
)
2419 error ("multiple hot/cold transitions found (bb %i)",
2424 switched_sections
= true;
2426 if (!crtl
->has_bb_partition
)
2427 error ("partition found but function partition flag not set");
2429 current_partition
= BB_PARTITION (bb
);
2436 /* Perform several checks on the edges out of each block, such as
2437 the consistency of the branch probabilities, the correctness
2438 of hot/cold partition crossing edges, and the number of expected
2439 successor edges. Also verify that the dominance relationship
2440 between hot/cold blocks is sane. */
2443 rtl_verify_edges (void)
2448 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2450 int n_fallthru
= 0, n_branch
= 0, n_abnormal_call
= 0, n_sibcall
= 0;
2451 int n_eh
= 0, n_abnormal
= 0;
2452 edge e
, fallthru
= NULL
;
2455 bool has_crossing_edge
= false;
2457 if (JUMP_P (BB_END (bb
))
2458 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
2459 && EDGE_COUNT (bb
->succs
) >= 2
2460 && any_condjump_p (BB_END (bb
)))
2462 if (!BRANCH_EDGE (bb
)->probability
.initialized_p ())
2464 if (profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2466 error ("verify_flow_info: "
2467 "REG_BR_PROB is set but cfg probability is not");
2471 else if (XINT (note
, 0)
2472 != BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ()
2473 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2475 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2477 BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ());
2482 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2486 if (e
->flags
& EDGE_FALLTHRU
)
2487 n_fallthru
++, fallthru
= e
;
2489 is_crossing
= (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
2490 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2491 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
2492 has_crossing_edge
|= is_crossing
;
2493 if (e
->flags
& EDGE_CROSSING
)
2497 error ("EDGE_CROSSING incorrectly set across same section");
2500 if (e
->flags
& EDGE_FALLTHRU
)
2502 error ("fallthru edge crosses section boundary in bb %i",
2506 if (e
->flags
& EDGE_EH
)
2508 error ("EH edge crosses section boundary in bb %i",
2512 if (JUMP_P (BB_END (bb
)) && !CROSSING_JUMP_P (BB_END (bb
)))
2514 error ("No region crossing jump at section boundary in bb %i",
2519 else if (is_crossing
)
2521 error ("EDGE_CROSSING missing across section boundary");
2525 if ((e
->flags
& ~(EDGE_DFS_BACK
2527 | EDGE_IRREDUCIBLE_LOOP
2530 | EDGE_PRESERVE
)) == 0)
2533 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2536 if (e
->flags
& EDGE_SIBCALL
)
2539 if (e
->flags
& EDGE_EH
)
2542 if (e
->flags
& EDGE_ABNORMAL
)
2546 if (!has_crossing_edge
2547 && JUMP_P (BB_END (bb
))
2548 && CROSSING_JUMP_P (BB_END (bb
)))
2550 print_rtl_with_bb (stderr
, get_insns (), TDF_BLOCKS
| TDF_DETAILS
);
2551 error ("Region crossing jump across same section in bb %i",
2556 if (n_eh
&& !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
2558 error ("missing REG_EH_REGION note at the end of bb %i", bb
->index
);
2563 error ("too many exception handling edges in bb %i", bb
->index
);
2567 && (!JUMP_P (BB_END (bb
))
2568 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
2569 || any_condjump_p (BB_END (bb
))))))
2571 error ("too many outgoing branch edges from bb %i", bb
->index
);
2574 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
2576 error ("fallthru edge after unconditional jump in bb %i", bb
->index
);
2579 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
2581 error ("wrong number of branch edges after unconditional jump"
2582 " in bb %i", bb
->index
);
2585 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
2586 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
2588 error ("wrong amount of branch edges after conditional jump"
2589 " in bb %i", bb
->index
);
2592 if (n_abnormal_call
&& !CALL_P (BB_END (bb
)))
2594 error ("abnormal call edges for non-call insn in bb %i", bb
->index
);
2597 if (n_sibcall
&& !CALL_P (BB_END (bb
)))
2599 error ("sibcall edges for non-call insn in bb %i", bb
->index
);
2602 if (n_abnormal
> n_eh
2603 && !(CALL_P (BB_END (bb
))
2604 && n_abnormal
== n_abnormal_call
+ n_sibcall
)
2605 && (!JUMP_P (BB_END (bb
))
2606 || any_condjump_p (BB_END (bb
))
2607 || any_uncondjump_p (BB_END (bb
))))
2609 error ("abnormal edges for no purpose in bb %i", bb
->index
);
2614 /* If there are partitions, do a sanity check on them: A basic block in
2615 Â a cold partition cannot dominate a basic block in a hot partition. Â */
2616 if (crtl
->has_bb_partition
&& !err
)
2618 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (true);
2619 err
= !bbs_to_fix
.is_empty ();
2626 /* Checks on the instructions within blocks. Currently checks that each
2627 block starts with a basic block note, and that basic block notes and
2628 control flow jumps are not found in the middle of the block. */
2631 rtl_verify_bb_insns (void)
2637 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2639 /* Now check the header of basic
2640 block. It ought to contain optional CODE_LABEL followed
2641 by NOTE_BASIC_BLOCK. */
2645 if (BB_END (bb
) == x
)
2647 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2655 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2657 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2662 if (BB_END (bb
) == x
)
2663 /* Do checks for empty blocks here. */
2666 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2668 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2670 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2671 INSN_UID (x
), bb
->index
);
2675 if (x
== BB_END (bb
))
2678 if (control_flow_insn_p (x
))
2680 error ("in basic block %d:", bb
->index
);
2681 fatal_insn ("flow control insn inside a basic block", x
);
2690 /* Verify that block pointers for instructions in basic blocks, headers and
2691 footers are set appropriately. */
2694 rtl_verify_bb_pointers (void)
2699 /* Check the general integrity of the basic blocks. */
2700 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2704 if (!(bb
->flags
& BB_RTL
))
2706 error ("BB_RTL flag not set for block %d", bb
->index
);
2710 FOR_BB_INSNS (bb
, insn
)
2711 if (BLOCK_FOR_INSN (insn
) != bb
)
2713 error ("insn %d basic block pointer is %d, should be %d",
2715 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
2720 for (insn
= BB_HEADER (bb
); insn
; insn
= NEXT_INSN (insn
))
2721 if (!BARRIER_P (insn
)
2722 && BLOCK_FOR_INSN (insn
) != NULL
)
2724 error ("insn %d in header of bb %d has non-NULL basic block",
2725 INSN_UID (insn
), bb
->index
);
2728 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
2729 if (!BARRIER_P (insn
)
2730 && BLOCK_FOR_INSN (insn
) != NULL
)
2732 error ("insn %d in footer of bb %d has non-NULL basic block",
2733 INSN_UID (insn
), bb
->index
);
2742 /* Verify the CFG and RTL consistency common for both underlying RTL and
2745 Currently it does following checks:
2747 - overlapping of basic blocks
2748 - insns with wrong BLOCK_FOR_INSN pointers
2749 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2750 - tails of basic blocks (ensure that boundary is necessary)
2751 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2752 and NOTE_INSN_BASIC_BLOCK
2753 - verify that no fall_thru edge crosses hot/cold partition boundaries
2754 - verify that there are no pending RTL branch predictions
2755 - verify that hot blocks are not dominated by cold blocks
2757 In future it can be extended check a lot of other stuff as well
2758 (reachability of basic blocks, life information, etc. etc.). */
2761 rtl_verify_flow_info_1 (void)
2765 err
|= rtl_verify_bb_pointers ();
2767 err
|= rtl_verify_bb_insns ();
2769 err
|= rtl_verify_edges ();
2774 /* Walk the instruction chain and verify that bb head/end pointers
2775 are correct, and that instructions are in exactly one bb and have
2776 correct block pointers. */
2779 rtl_verify_bb_insn_chain (void)
2784 rtx_insn
*last_head
= get_last_insn ();
2785 basic_block
*bb_info
;
2786 const int max_uid
= get_max_uid ();
2788 bb_info
= XCNEWVEC (basic_block
, max_uid
);
2790 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2792 rtx_insn
*head
= BB_HEAD (bb
);
2793 rtx_insn
*end
= BB_END (bb
);
2795 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2797 /* Verify the end of the basic block is in the INSN chain. */
2801 /* And that the code outside of basic blocks has NULL bb field. */
2803 && BLOCK_FOR_INSN (x
) != NULL
)
2805 error ("insn %d outside of basic blocks has non-NULL bb field",
2813 error ("end insn %d for block %d not found in the insn stream",
2814 INSN_UID (end
), bb
->index
);
2818 /* Work backwards from the end to the head of the basic block
2819 to verify the head is in the RTL chain. */
2820 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2822 /* While walking over the insn chain, verify insns appear
2823 in only one basic block. */
2824 if (bb_info
[INSN_UID (x
)] != NULL
)
2826 error ("insn %d is in multiple basic blocks (%d and %d)",
2827 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2831 bb_info
[INSN_UID (x
)] = bb
;
2838 error ("head insn %d for block %d not found in the insn stream",
2839 INSN_UID (head
), bb
->index
);
2843 last_head
= PREV_INSN (x
);
2846 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2848 /* Check that the code before the first basic block has NULL
2851 && BLOCK_FOR_INSN (x
) != NULL
)
2853 error ("insn %d outside of basic blocks has non-NULL bb field",
2863 /* Verify that fallthru edges point to adjacent blocks in layout order and
2864 that barriers exist after non-fallthru blocks. */
2867 rtl_verify_fallthru (void)
2872 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2876 e
= find_fallthru_edge (bb
->succs
);
2881 /* Ensure existence of barrier in BB with no fallthru edges. */
2882 for (insn
= NEXT_INSN (BB_END (bb
)); ; insn
= NEXT_INSN (insn
))
2884 if (!insn
|| NOTE_INSN_BASIC_BLOCK_P (insn
))
2886 error ("missing barrier after block %i", bb
->index
);
2890 if (BARRIER_P (insn
))
2894 else if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2895 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2899 if (e
->src
->next_bb
!= e
->dest
)
2902 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2903 e
->src
->index
, e
->dest
->index
);
2907 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
2908 insn
= NEXT_INSN (insn
))
2909 if (BARRIER_P (insn
) || INSN_P (insn
))
2911 error ("verify_flow_info: Incorrect fallthru %i->%i",
2912 e
->src
->index
, e
->dest
->index
);
2913 fatal_insn ("wrong insn in the fallthru edge", insn
);
2922 /* Verify that blocks are laid out in consecutive order. While walking the
2923 instructions, verify that all expected instructions are inside the basic
2924 blocks, and that all returns are followed by barriers. */
2927 rtl_verify_bb_layout (void)
2933 rtx_insn
* const rtx_first
= get_insns ();
2934 basic_block last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
), curr_bb
= NULL
;
2937 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
2939 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2941 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2943 bb
= NOTE_BASIC_BLOCK (x
);
2946 if (bb
!= last_bb_seen
->next_bb
)
2947 internal_error ("basic blocks not laid down consecutively");
2949 curr_bb
= last_bb_seen
= bb
;
2954 switch (GET_CODE (x
))
2961 /* An ADDR_VEC is placed outside any basic block. */
2963 && JUMP_TABLE_DATA_P (NEXT_INSN (x
)))
2966 /* But in any case, non-deletable labels can appear anywhere. */
2970 fatal_insn ("insn outside basic block", x
);
2975 && returnjump_p (x
) && ! condjump_p (x
)
2976 && ! (next_nonnote_insn (x
) && BARRIER_P (next_nonnote_insn (x
))))
2977 fatal_insn ("return not followed by barrier", x
);
2979 if (curr_bb
&& x
== BB_END (curr_bb
))
2983 if (num_bb_notes
!= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
)
2985 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2986 num_bb_notes
, n_basic_blocks_for_fn (cfun
));
2991 /* Verify the CFG and RTL consistency common for both underlying RTL and
2992 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
2994 Currently it does following checks:
2995 - all checks of rtl_verify_flow_info_1
2996 - test head/end pointers
2997 - check that blocks are laid out in consecutive order
2998 - check that all insns are in the basic blocks
2999 (except the switch handling code, barriers and notes)
3000 - check that all returns are followed by barriers
3001 - check that all fallthru edge points to the adjacent blocks
3002 - verify that there is a single hot/cold partition boundary after bbro */
3005 rtl_verify_flow_info (void)
3009 err
|= rtl_verify_flow_info_1 ();
3011 err
|= rtl_verify_bb_insn_chain ();
3013 err
|= rtl_verify_fallthru ();
3015 err
|= rtl_verify_bb_layout ();
3017 err
|= verify_hot_cold_block_grouping ();
3022 /* Assume that the preceding pass has possibly eliminated jump instructions
3023 or converted the unconditional jumps. Eliminate the edges from CFG.
3024 Return true if any edges are eliminated. */
3027 purge_dead_edges (basic_block bb
)
3030 rtx_insn
*insn
= BB_END (bb
);
3032 bool purged
= false;
3036 if (DEBUG_INSN_P (insn
) && insn
!= BB_HEAD (bb
))
3038 insn
= PREV_INSN (insn
);
3039 while ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
));
3041 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3042 if (NONJUMP_INSN_P (insn
)
3043 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
3047 if (! may_trap_p (PATTERN (insn
))
3048 || ((eqnote
= find_reg_equal_equiv_note (insn
))
3049 && ! may_trap_p (XEXP (eqnote
, 0))))
3050 remove_note (insn
, note
);
3053 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3054 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3056 bool remove
= false;
3058 /* There are three types of edges we need to handle correctly here: EH
3059 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3060 latter can appear when nonlocal gotos are used. */
3061 if (e
->flags
& EDGE_ABNORMAL_CALL
)
3065 else if (can_nonlocal_goto (insn
))
3067 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3069 else if (flag_tm
&& find_reg_note (insn
, REG_TM
, NULL
))
3074 else if (e
->flags
& EDGE_EH
)
3075 remove
= !can_throw_internal (insn
);
3080 df_set_bb_dirty (bb
);
3093 /* We do care only about conditional jumps and simplejumps. */
3094 if (!any_condjump_p (insn
)
3095 && !returnjump_p (insn
)
3096 && !simplejump_p (insn
))
3099 /* Branch probability/prediction notes are defined only for
3100 condjumps. We've possibly turned condjump into simplejump. */
3101 if (simplejump_p (insn
))
3103 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3105 remove_note (insn
, note
);
3106 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
3107 remove_note (insn
, note
);
3110 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3112 /* Avoid abnormal flags to leak from computed jumps turned
3113 into simplejumps. */
3115 e
->flags
&= ~EDGE_ABNORMAL
;
3117 /* See if this edge is one we should keep. */
3118 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
3119 /* A conditional jump can fall through into the next
3120 block, so we should keep the edge. */
3125 else if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3126 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
3127 /* If the destination block is the target of the jump,
3133 else if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
3134 && returnjump_p (insn
))
3135 /* If the destination block is the exit block, and this
3136 instruction is a return, then keep the edge. */
3141 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3142 /* Keep the edges that correspond to exceptions thrown by
3143 this instruction and rematerialize the EDGE_ABNORMAL
3144 flag we just cleared above. */
3146 e
->flags
|= EDGE_ABNORMAL
;
3151 /* We do not need this edge. */
3152 df_set_bb_dirty (bb
);
3157 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
3161 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
3166 /* Redistribute probabilities. */
3167 if (single_succ_p (bb
))
3169 single_succ_edge (bb
)->probability
= profile_probability::always ();
3173 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3177 b
= BRANCH_EDGE (bb
);
3178 f
= FALLTHRU_EDGE (bb
);
3179 b
->probability
= profile_probability::from_reg_br_prob_note
3181 f
->probability
= b
->probability
.invert ();
3186 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
3188 /* First, there should not be any EH or ABCALL edges resulting
3189 from non-local gotos and the like. If there were, we shouldn't
3190 have created the sibcall in the first place. Second, there
3191 should of course never have been a fallthru edge. */
3192 gcc_assert (single_succ_p (bb
));
3193 gcc_assert (single_succ_edge (bb
)->flags
3194 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
3199 /* If we don't see a jump insn, we don't know exactly why the block would
3200 have been broken at this point. Look for a simple, non-fallthru edge,
3201 as these are only created by conditional branches. If we find such an
3202 edge we know that there used to be a jump here and can then safely
3203 remove all non-fallthru edges. */
3205 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3206 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
3215 /* Remove all but the fake and fallthru edges. The fake edge may be
3216 the only successor for this block in the case of noreturn
3218 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3220 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
3222 df_set_bb_dirty (bb
);
3230 gcc_assert (single_succ_p (bb
));
3232 single_succ_edge (bb
)->probability
= profile_probability::always ();
3235 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
3240 /* Search all basic blocks for potentially dead edges and purge them. Return
3241 true if some edge has been eliminated. */
3244 purge_all_dead_edges (void)
3249 FOR_EACH_BB_FN (bb
, cfun
)
3251 bool purged_here
= purge_dead_edges (bb
);
3253 purged
|= purged_here
;
3259 /* This is used by a few passes that emit some instructions after abnormal
3260 calls, moving the basic block's end, while they in fact do want to emit
3261 them on the fallthru edge. Look for abnormal call edges, find backward
3262 the call in the block and insert the instructions on the edge instead.
3264 Similarly, handle instructions throwing exceptions internally.
3266 Return true when instructions have been found and inserted on edges. */
3269 fixup_abnormal_edges (void)
3271 bool inserted
= false;
3274 FOR_EACH_BB_FN (bb
, cfun
)
3279 /* Look for cases we are interested in - calls or instructions causing
3281 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3282 if ((e
->flags
& EDGE_ABNORMAL_CALL
)
3283 || ((e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
3284 == (EDGE_ABNORMAL
| EDGE_EH
)))
3287 if (e
&& !CALL_P (BB_END (bb
)) && !can_throw_internal (BB_END (bb
)))
3291 /* Get past the new insns generated. Allow notes, as the insns
3292 may be already deleted. */
3294 while ((NONJUMP_INSN_P (insn
) || NOTE_P (insn
))
3295 && !can_throw_internal (insn
)
3296 && insn
!= BB_HEAD (bb
))
3297 insn
= PREV_INSN (insn
);
3299 if (CALL_P (insn
) || can_throw_internal (insn
))
3301 rtx_insn
*stop
, *next
;
3303 e
= find_fallthru_edge (bb
->succs
);
3305 stop
= NEXT_INSN (BB_END (bb
));
3308 for (insn
= NEXT_INSN (insn
); insn
!= stop
; insn
= next
)
3310 next
= NEXT_INSN (insn
);
3315 /* Sometimes there's still the return value USE.
3316 If it's placed after a trapping call (i.e. that
3317 call is the last insn anyway), we have no fallthru
3318 edge. Simply delete this use and don't try to insert
3319 on the non-existent edge. */
3320 if (GET_CODE (PATTERN (insn
)) != USE
)
3322 /* We're not deleting it, we're moving it. */
3323 insn
->set_undeleted ();
3324 SET_PREV_INSN (insn
) = NULL_RTX
;
3325 SET_NEXT_INSN (insn
) = NULL_RTX
;
3327 insert_insn_on_edge (insn
, e
);
3331 else if (!BARRIER_P (insn
))
3332 set_block_for_insn (insn
, NULL
);
3336 /* It may be that we don't find any trapping insn. In this
3337 case we discovered quite late that the insn that had been
3338 marked as can_throw_internal in fact couldn't trap at all.
3339 So we should in fact delete the EH edges out of the block. */
3341 purge_dead_edges (bb
);
3348 /* Cut the insns from FIRST to LAST out of the insns stream. */
3351 unlink_insn_chain (rtx_insn
*first
, rtx_insn
*last
)
3353 rtx_insn
*prevfirst
= PREV_INSN (first
);
3354 rtx_insn
*nextlast
= NEXT_INSN (last
);
3356 SET_PREV_INSN (first
) = NULL
;
3357 SET_NEXT_INSN (last
) = NULL
;
3359 SET_NEXT_INSN (prevfirst
) = nextlast
;
3361 SET_PREV_INSN (nextlast
) = prevfirst
;
3363 set_last_insn (prevfirst
);
3365 set_first_insn (nextlast
);
3369 /* Skip over inter-block insns occurring after BB which are typically
3370 associated with BB (e.g., barriers). If there are any such insns,
3371 we return the last one. Otherwise, we return the end of BB. */
3374 skip_insns_after_block (basic_block bb
)
3376 rtx_insn
*insn
, *last_insn
, *next_head
, *prev
;
3379 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3380 next_head
= BB_HEAD (bb
->next_bb
);
3382 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
3384 if (insn
== next_head
)
3387 switch (GET_CODE (insn
))
3394 switch (NOTE_KIND (insn
))
3396 case NOTE_INSN_BLOCK_END
:
3406 if (NEXT_INSN (insn
)
3407 && JUMP_TABLE_DATA_P (NEXT_INSN (insn
)))
3409 insn
= NEXT_INSN (insn
);
3422 /* It is possible to hit contradictory sequence. For instance:
3428 Where barrier belongs to jump_insn, but the note does not. This can be
3429 created by removing the basic block originally following
3430 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3432 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
3434 prev
= PREV_INSN (insn
);
3436 switch (NOTE_KIND (insn
))
3438 case NOTE_INSN_BLOCK_END
:
3441 case NOTE_INSN_DELETED
:
3442 case NOTE_INSN_DELETED_LABEL
:
3443 case NOTE_INSN_DELETED_DEBUG_LABEL
:
3446 reorder_insns (insn
, insn
, last_insn
);
3453 /* Locate or create a label for a given basic block. */
3456 label_for_bb (basic_block bb
)
3458 rtx_insn
*label
= BB_HEAD (bb
);
3460 if (!LABEL_P (label
))
3463 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
3465 label
= block_label (bb
);
3471 /* Locate the effective beginning and end of the insn chain for each
3472 block, as defined by skip_insns_after_block above. */
3475 record_effective_endpoints (void)
3477 rtx_insn
*next_insn
;
3481 for (insn
= get_insns ();
3484 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
;
3485 insn
= NEXT_INSN (insn
))
3487 /* No basic blocks at all? */
3490 if (PREV_INSN (insn
))
3491 cfg_layout_function_header
=
3492 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
3494 cfg_layout_function_header
= NULL
;
3496 next_insn
= get_insns ();
3497 FOR_EACH_BB_FN (bb
, cfun
)
3501 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
3502 BB_HEADER (bb
) = unlink_insn_chain (next_insn
,
3503 PREV_INSN (BB_HEAD (bb
)));
3504 end
= skip_insns_after_block (bb
);
3505 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
3506 BB_FOOTER (bb
) = unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
3507 next_insn
= NEXT_INSN (BB_END (bb
));
3510 cfg_layout_function_footer
= next_insn
;
3511 if (cfg_layout_function_footer
)
3512 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
3517 const pass_data pass_data_into_cfg_layout_mode
=
3519 RTL_PASS
, /* type */
3520 "into_cfglayout", /* name */
3521 OPTGROUP_NONE
, /* optinfo_flags */
3523 0, /* properties_required */
3524 PROP_cfglayout
, /* properties_provided */
3525 0, /* properties_destroyed */
3526 0, /* todo_flags_start */
3527 0, /* todo_flags_finish */
3530 class pass_into_cfg_layout_mode
: public rtl_opt_pass
3533 pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3534 : rtl_opt_pass (pass_data_into_cfg_layout_mode
, ctxt
)
3537 /* opt_pass methods: */
3538 virtual unsigned int execute (function
*)
3540 cfg_layout_initialize (0);
3544 }; // class pass_into_cfg_layout_mode
3549 make_pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3551 return new pass_into_cfg_layout_mode (ctxt
);
3556 const pass_data pass_data_outof_cfg_layout_mode
=
3558 RTL_PASS
, /* type */
3559 "outof_cfglayout", /* name */
3560 OPTGROUP_NONE
, /* optinfo_flags */
3562 0, /* properties_required */
3563 0, /* properties_provided */
3564 PROP_cfglayout
, /* properties_destroyed */
3565 0, /* todo_flags_start */
3566 0, /* todo_flags_finish */
3569 class pass_outof_cfg_layout_mode
: public rtl_opt_pass
3572 pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3573 : rtl_opt_pass (pass_data_outof_cfg_layout_mode
, ctxt
)
3576 /* opt_pass methods: */
3577 virtual unsigned int execute (function
*);
3579 }; // class pass_outof_cfg_layout_mode
3582 pass_outof_cfg_layout_mode::execute (function
*fun
)
3586 FOR_EACH_BB_FN (bb
, fun
)
3587 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3588 bb
->aux
= bb
->next_bb
;
3590 cfg_layout_finalize ();
3598 make_pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3600 return new pass_outof_cfg_layout_mode (ctxt
);
3604 /* Link the basic blocks in the correct order, compacting the basic
3605 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3606 function also clears the basic block header and footer fields.
3608 This function is usually called after a pass (e.g. tracer) finishes
3609 some transformations while in cfglayout mode. The required sequence
3610 of the basic blocks is in a linked list along the bb->aux field.
3611 This functions re-links the basic block prev_bb and next_bb pointers
3612 accordingly, and it compacts and renumbers the blocks.
3614 FIXME: This currently works only for RTL, but the only RTL-specific
3615 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3616 to GIMPLE a long time ago, but it doesn't relink the basic block
3617 chain. It could do that (to give better initial RTL) if this function
3618 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3621 relink_block_chain (bool stay_in_cfglayout_mode
)
3623 basic_block bb
, prev_bb
;
3626 /* Maybe dump the re-ordered sequence. */
3629 fprintf (dump_file
, "Reordered sequence:\n");
3630 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, index
=
3633 bb
= (basic_block
) bb
->aux
, index
++)
3635 fprintf (dump_file
, " %i ", index
);
3636 if (get_bb_original (bb
))
3637 fprintf (dump_file
, "duplicate of %i ",
3638 get_bb_original (bb
)->index
);
3639 else if (forwarder_block_p (bb
)
3640 && !LABEL_P (BB_HEAD (bb
)))
3641 fprintf (dump_file
, "compensation ");
3643 fprintf (dump_file
, "bb %i ", bb
->index
);
3647 /* Now reorder the blocks. */
3648 prev_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
3649 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
3650 for (; bb
; prev_bb
= bb
, bb
= (basic_block
) bb
->aux
)
3652 bb
->prev_bb
= prev_bb
;
3653 prev_bb
->next_bb
= bb
;
3655 prev_bb
->next_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
3656 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
= prev_bb
;
3658 /* Then, clean up the aux fields. */
3659 FOR_ALL_BB_FN (bb
, cfun
)
3662 if (!stay_in_cfglayout_mode
)
3663 BB_HEADER (bb
) = BB_FOOTER (bb
) = NULL
;
3666 /* Maybe reset the original copy tables, they are not valid anymore
3667 when we renumber the basic blocks in compact_blocks. If we are
3668 are going out of cfglayout mode, don't re-allocate the tables. */
3669 if (original_copy_tables_initialized_p ())
3670 free_original_copy_tables ();
3671 if (stay_in_cfglayout_mode
)
3672 initialize_original_copy_tables ();
3674 /* Finally, put basic_block_info in the new order. */
3679 /* Given a reorder chain, rearrange the code to match. */
3682 fixup_reorder_chain (void)
3685 rtx_insn
*insn
= NULL
;
3687 if (cfg_layout_function_header
)
3689 set_first_insn (cfg_layout_function_header
);
3690 insn
= cfg_layout_function_header
;
3691 while (NEXT_INSN (insn
))
3692 insn
= NEXT_INSN (insn
);
3695 /* First do the bulk reordering -- rechain the blocks without regard to
3696 the needed changes to jumps and labels. */
3698 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3704 SET_NEXT_INSN (insn
) = BB_HEADER (bb
);
3706 set_first_insn (BB_HEADER (bb
));
3707 SET_PREV_INSN (BB_HEADER (bb
)) = insn
;
3708 insn
= BB_HEADER (bb
);
3709 while (NEXT_INSN (insn
))
3710 insn
= NEXT_INSN (insn
);
3713 SET_NEXT_INSN (insn
) = BB_HEAD (bb
);
3715 set_first_insn (BB_HEAD (bb
));
3716 SET_PREV_INSN (BB_HEAD (bb
)) = insn
;
3720 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
3721 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
3722 while (NEXT_INSN (insn
))
3723 insn
= NEXT_INSN (insn
);
3727 SET_NEXT_INSN (insn
) = cfg_layout_function_footer
;
3728 if (cfg_layout_function_footer
)
3729 SET_PREV_INSN (cfg_layout_function_footer
) = insn
;
3731 while (NEXT_INSN (insn
))
3732 insn
= NEXT_INSN (insn
);
3734 set_last_insn (insn
);
3736 verify_insn_chain ();
3738 /* Now add jumps and labels as needed to match the blocks new
3741 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3744 edge e_fall
, e_taken
, e
;
3745 rtx_insn
*bb_end_insn
;
3746 rtx ret_label
= NULL_RTX
;
3750 if (EDGE_COUNT (bb
->succs
) == 0)
3753 /* Find the old fallthru edge, and another non-EH edge for
3755 e_taken
= e_fall
= NULL
;
3757 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3758 if (e
->flags
& EDGE_FALLTHRU
)
3760 else if (! (e
->flags
& EDGE_EH
))
3763 bb_end_insn
= BB_END (bb
);
3764 if (rtx_jump_insn
*bb_end_jump
= dyn_cast
<rtx_jump_insn
*> (bb_end_insn
))
3766 ret_label
= JUMP_LABEL (bb_end_jump
);
3767 if (any_condjump_p (bb_end_jump
))
3769 /* This might happen if the conditional jump has side
3770 effects and could therefore not be optimized away.
3771 Make the basic block to end with a barrier in order
3772 to prevent rtl_verify_flow_info from complaining. */
3775 gcc_assert (!onlyjump_p (bb_end_jump
)
3776 || returnjump_p (bb_end_jump
)
3777 || (e_taken
->flags
& EDGE_CROSSING
));
3778 emit_barrier_after (bb_end_jump
);
3782 /* If the old fallthru is still next, nothing to do. */
3783 if (bb
->aux
== e_fall
->dest
3784 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3787 /* The degenerated case of conditional jump jumping to the next
3788 instruction can happen for jumps with side effects. We need
3789 to construct a forwarder block and this will be done just
3790 fine by force_nonfallthru below. */
3794 /* There is another special case: if *neither* block is next,
3795 such as happens at the very end of a function, then we'll
3796 need to add a new unconditional jump. Choose the taken
3797 edge based on known or assumed probability. */
3798 else if (bb
->aux
!= e_taken
->dest
)
3800 rtx note
= find_reg_note (bb_end_jump
, REG_BR_PROB
, 0);
3803 && profile_probability::from_reg_br_prob_note
3804 (XINT (note
, 0)) < profile_probability::even ()
3805 && invert_jump (bb_end_jump
,
3807 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3809 : label_for_bb (e_fall
->dest
)), 0))
3811 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3812 gcc_checking_assert (could_fall_through
3813 (e_taken
->src
, e_taken
->dest
));
3814 e_taken
->flags
|= EDGE_FALLTHRU
;
3815 update_br_prob_note (bb
);
3816 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
3820 /* If the "jumping" edge is a crossing edge, and the fall
3821 through edge is non-crossing, leave things as they are. */
3822 else if ((e_taken
->flags
& EDGE_CROSSING
)
3823 && !(e_fall
->flags
& EDGE_CROSSING
))
3826 /* Otherwise we can try to invert the jump. This will
3827 basically never fail, however, keep up the pretense. */
3828 else if (invert_jump (bb_end_jump
,
3830 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3832 : label_for_bb (e_fall
->dest
)), 0))
3834 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3835 gcc_checking_assert (could_fall_through
3836 (e_taken
->src
, e_taken
->dest
));
3837 e_taken
->flags
|= EDGE_FALLTHRU
;
3838 update_br_prob_note (bb
);
3839 if (LABEL_NUSES (ret_label
) == 0
3840 && single_pred_p (e_taken
->dest
))
3841 delete_insn (as_a
<rtx_insn
*> (ret_label
));
3845 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
3847 /* If the old fallthru is still next or if
3848 asm goto doesn't have a fallthru (e.g. when followed by
3849 __builtin_unreachable ()), nothing to do. */
3851 || bb
->aux
== e_fall
->dest
3852 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3855 /* Otherwise we'll have to use the fallthru fixup below. */
3859 /* Otherwise we have some return, switch or computed
3860 jump. In the 99% case, there should not have been a
3862 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
3868 /* No fallthru implies a noreturn function with EH edges, or
3869 something similarly bizarre. In any case, we don't need to
3874 /* If the fallthru block is still next, nothing to do. */
3875 if (bb
->aux
== e_fall
->dest
)
3878 /* A fallthru to exit block. */
3879 if (e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3883 /* We got here if we need to add a new jump insn.
3884 Note force_nonfallthru can delete E_FALL and thus we have to
3885 save E_FALL->src prior to the call to force_nonfallthru. */
3886 nb
= force_nonfallthru_and_redirect (e_fall
, e_fall
->dest
, ret_label
);
3891 /* Don't process this new block. */
3896 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3898 /* Annoying special case - jump around dead jumptables left in the code. */
3899 FOR_EACH_BB_FN (bb
, cfun
)
3901 edge e
= find_fallthru_edge (bb
->succs
);
3903 if (e
&& !can_fallthru (e
->src
, e
->dest
))
3904 force_nonfallthru (e
);
3907 /* Ensure goto_locus from edges has some instructions with that locus
3910 FOR_EACH_BB_FN (bb
, cfun
)
3915 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3916 if (LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
3917 && !(e
->flags
& EDGE_ABNORMAL
))
3921 basic_block dest
, nb
;
3924 insn
= BB_END (e
->src
);
3925 end
= PREV_INSN (BB_HEAD (e
->src
));
3927 && (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
3928 insn
= PREV_INSN (insn
);
3930 && INSN_LOCATION (insn
) == e
->goto_locus
)
3932 if (simplejump_p (BB_END (e
->src
))
3933 && !INSN_HAS_LOCATION (BB_END (e
->src
)))
3935 INSN_LOCATION (BB_END (e
->src
)) = e
->goto_locus
;
3939 if (dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3941 /* Non-fallthru edges to the exit block cannot be split. */
3942 if (!(e
->flags
& EDGE_FALLTHRU
))
3947 insn
= BB_HEAD (dest
);
3948 end
= NEXT_INSN (BB_END (dest
));
3949 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
3950 insn
= NEXT_INSN (insn
);
3951 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
3952 && INSN_LOCATION (insn
) == e
->goto_locus
)
3955 nb
= split_edge (e
);
3956 if (!INSN_P (BB_END (nb
)))
3957 BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
3959 INSN_LOCATION (BB_END (nb
)) = e
->goto_locus
;
3961 /* If there are other incoming edges to the destination block
3962 with the same goto locus, redirect them to the new block as
3963 well, this can prevent other such blocks from being created
3964 in subsequent iterations of the loop. */
3965 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
3966 if (LOCATION_LOCUS (e2
->goto_locus
) != UNKNOWN_LOCATION
3967 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
3968 && e
->goto_locus
== e2
->goto_locus
)
3969 redirect_edge_and_branch (e2
, nb
);
3976 /* Perform sanity checks on the insn chain.
3977 1. Check that next/prev pointers are consistent in both the forward and
3979 2. Count insns in chain, going both directions, and check if equal.
3980 3. Check that get_last_insn () returns the actual end of chain. */
3983 verify_insn_chain (void)
3985 rtx_insn
*x
, *prevx
, *nextx
;
3986 int insn_cnt1
, insn_cnt2
;
3988 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
3990 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
3991 gcc_assert (PREV_INSN (x
) == prevx
);
3993 gcc_assert (prevx
== get_last_insn ());
3995 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
3997 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
3998 gcc_assert (NEXT_INSN (x
) == nextx
);
4000 gcc_assert (insn_cnt1
== insn_cnt2
);
4003 /* If we have assembler epilogues, the block falling through to exit must
4004 be the last one in the reordered chain when we reach final. Ensure
4005 that this condition is met. */
4007 fixup_fallthru_exit_predecessor (void)
4010 basic_block bb
= NULL
;
4012 /* This transformation is not valid before reload, because we might
4013 separate a call from the instruction that copies the return
4015 gcc_assert (reload_completed
);
4017 e
= find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4023 basic_block c
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
4025 /* If the very first block is the one with the fall-through exit
4026 edge, we have to split that block. */
4029 bb
= split_block_after_labels (bb
)->dest
;
4032 BB_FOOTER (bb
) = BB_FOOTER (c
);
4033 BB_FOOTER (c
) = NULL
;
4036 while (c
->aux
!= bb
)
4037 c
= (basic_block
) c
->aux
;
4041 c
= (basic_block
) c
->aux
;
4048 /* In case there are more than one fallthru predecessors of exit, force that
4049 there is only one. */
4052 force_one_exit_fallthru (void)
4054 edge e
, predecessor
= NULL
;
4057 basic_block forwarder
, bb
;
4059 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
4060 if (e
->flags
& EDGE_FALLTHRU
)
4062 if (predecessor
== NULL
)
4074 /* Exit has several fallthru predecessors. Create a forwarder block for
4076 forwarder
= split_edge (predecessor
);
4077 for (ei
= ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4078 (e
= ei_safe_edge (ei
)); )
4080 if (e
->src
== forwarder
4081 || !(e
->flags
& EDGE_FALLTHRU
))
4084 redirect_edge_and_branch_force (e
, forwarder
);
4087 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4089 FOR_EACH_BB_FN (bb
, cfun
)
4091 if (bb
->aux
== NULL
&& bb
!= forwarder
)
4093 bb
->aux
= forwarder
;
4099 /* Return true in case it is possible to duplicate the basic block BB. */
4102 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
4104 /* Do not attempt to duplicate tablejumps, as we need to unshare
4105 the dispatch table. This is difficult to do, as the instructions
4106 computing jump destination may be hoisted outside the basic block. */
4107 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
4110 /* Do not duplicate blocks containing insns that can't be copied. */
4111 if (targetm
.cannot_copy_insn_p
)
4113 rtx_insn
*insn
= BB_HEAD (bb
);
4116 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
4118 if (insn
== BB_END (bb
))
4120 insn
= NEXT_INSN (insn
);
4128 duplicate_insn_chain (rtx_insn
*from
, rtx_insn
*to
)
4130 rtx_insn
*insn
, *next
, *copy
;
4133 /* Avoid updating of boundaries of previous basic block. The
4134 note will get removed from insn stream in fixup. */
4135 last
= emit_note (NOTE_INSN_DELETED
);
4137 /* Create copy at the end of INSN chain. The chain will
4138 be reordered later. */
4139 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
4141 switch (GET_CODE (insn
))
4144 /* Don't duplicate label debug insns. */
4145 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
)
4151 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
4152 if (JUMP_P (insn
) && JUMP_LABEL (insn
) != NULL_RTX
4153 && ANY_RETURN_P (JUMP_LABEL (insn
)))
4154 JUMP_LABEL (copy
) = JUMP_LABEL (insn
);
4155 maybe_copy_prologue_epilogue_insn (insn
, copy
);
4158 case JUMP_TABLE_DATA
:
4159 /* Avoid copying of dispatch tables. We never duplicate
4160 tablejumps, so this can hit only in case the table got
4161 moved far from original jump.
4162 Avoid copying following barrier as well if any
4163 (and debug insns in between). */
4164 for (next
= NEXT_INSN (insn
);
4165 next
!= NEXT_INSN (to
);
4166 next
= NEXT_INSN (next
))
4167 if (!DEBUG_INSN_P (next
))
4169 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
4181 switch (NOTE_KIND (insn
))
4183 /* In case prologue is empty and function contain label
4184 in first BB, we may want to copy the block. */
4185 case NOTE_INSN_PROLOGUE_END
:
4187 case NOTE_INSN_DELETED
:
4188 case NOTE_INSN_DELETED_LABEL
:
4189 case NOTE_INSN_DELETED_DEBUG_LABEL
:
4190 /* No problem to strip these. */
4191 case NOTE_INSN_FUNCTION_BEG
:
4192 /* There is always just single entry to function. */
4193 case NOTE_INSN_BASIC_BLOCK
:
4194 /* We should only switch text sections once. */
4195 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
4198 case NOTE_INSN_EPILOGUE_BEG
:
4199 case NOTE_INSN_UPDATE_SJLJ_CONTEXT
:
4200 emit_note_copy (as_a
<rtx_note
*> (insn
));
4204 /* All other notes should have already been eliminated. */
4212 insn
= NEXT_INSN (last
);
4217 /* Create a duplicate of the basic block BB. */
4220 cfg_layout_duplicate_bb (basic_block bb
)
4225 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
4226 new_bb
= create_basic_block (insn
,
4227 insn
? get_last_insn () : NULL
,
4228 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
);
4230 BB_COPY_PARTITION (new_bb
, bb
);
4233 insn
= BB_HEADER (bb
);
4234 while (NEXT_INSN (insn
))
4235 insn
= NEXT_INSN (insn
);
4236 insn
= duplicate_insn_chain (BB_HEADER (bb
), insn
);
4238 BB_HEADER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4243 insn
= BB_FOOTER (bb
);
4244 while (NEXT_INSN (insn
))
4245 insn
= NEXT_INSN (insn
);
4246 insn
= duplicate_insn_chain (BB_FOOTER (bb
), insn
);
4248 BB_FOOTER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4255 /* Main entry point to this module - initialize the datastructures for
4256 CFG layout changes. It keeps LOOPS up-to-date if not null.
4258 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4261 cfg_layout_initialize (int flags
)
4266 /* Once bb partitioning is complete, cfg layout mode should not be
4267 re-entered. Entering cfg layout mode may require fixups. As an
4268 example, if edge forwarding performed when optimizing the cfg
4269 layout required moving a block from the hot to the cold
4270 section. This would create an illegal partitioning unless some
4271 manual fixup was performed. */
4272 gcc_assert (!crtl
->bb_reorder_complete
|| !crtl
->has_bb_partition
);
4274 initialize_original_copy_tables ();
4276 cfg_layout_rtl_register_cfg_hooks ();
4278 record_effective_endpoints ();
4280 /* Make sure that the targets of non local gotos are marked. */
4281 for (x
= nonlocal_goto_handler_labels
; x
; x
= x
->next ())
4283 bb
= BLOCK_FOR_INSN (x
->insn ());
4284 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
4287 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
4290 /* Splits superblocks. */
4292 break_superblocks (void)
4297 auto_sbitmap
superblocks (last_basic_block_for_fn (cfun
));
4298 bitmap_clear (superblocks
);
4300 FOR_EACH_BB_FN (bb
, cfun
)
4301 if (bb
->flags
& BB_SUPERBLOCK
)
4303 bb
->flags
&= ~BB_SUPERBLOCK
;
4304 bitmap_set_bit (superblocks
, bb
->index
);
4310 rebuild_jump_labels (get_insns ());
4311 find_many_sub_basic_blocks (superblocks
);
4315 /* Finalize the changes: reorder insn list according to the sequence specified
4316 by aux pointers, enter compensation code, rebuild scope forest. */
4319 cfg_layout_finalize (void)
4321 checking_verify_flow_info ();
4322 free_dominance_info (CDI_DOMINATORS
);
4323 force_one_exit_fallthru ();
4324 rtl_register_cfg_hooks ();
4325 if (reload_completed
&& !targetm
.have_epilogue ())
4326 fixup_fallthru_exit_predecessor ();
4327 fixup_reorder_chain ();
4329 rebuild_jump_labels (get_insns ());
4330 delete_dead_jumptables ();
4333 verify_insn_chain ();
4334 checking_verify_flow_info ();
4338 /* Same as split_block but update cfg_layout structures. */
4341 cfg_layout_split_block (basic_block bb
, void *insnp
)
4343 rtx insn
= (rtx
) insnp
;
4344 basic_block new_bb
= rtl_split_block (bb
, insn
);
4346 BB_FOOTER (new_bb
) = BB_FOOTER (bb
);
4347 BB_FOOTER (bb
) = NULL
;
4352 /* Redirect Edge to DEST. */
4354 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
4356 basic_block src
= e
->src
;
4359 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4362 if (e
->dest
== dest
)
4365 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4366 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
4368 df_set_bb_dirty (src
);
4372 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4373 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
4376 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
4377 e
->src
->index
, dest
->index
);
4379 df_set_bb_dirty (e
->src
);
4380 redirect_edge_succ (e
, dest
);
4384 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4385 in the case the basic block appears to be in sequence. Avoid this
4388 if (e
->flags
& EDGE_FALLTHRU
)
4390 /* Redirect any branch edges unified with the fallthru one. */
4391 if (JUMP_P (BB_END (src
))
4392 && label_is_jump_target_p (BB_HEAD (e
->dest
),
4398 fprintf (dump_file
, "Fallthru edge unified with branch "
4399 "%i->%i redirected to %i\n",
4400 e
->src
->index
, e
->dest
->index
, dest
->index
);
4401 e
->flags
&= ~EDGE_FALLTHRU
;
4402 redirected
= redirect_branch_edge (e
, dest
);
4403 gcc_assert (redirected
);
4404 redirected
->flags
|= EDGE_FALLTHRU
;
4405 df_set_bb_dirty (redirected
->src
);
4408 /* In case we are redirecting fallthru edge to the branch edge
4409 of conditional jump, remove it. */
4410 if (EDGE_COUNT (src
->succs
) == 2)
4412 /* Find the edge that is different from E. */
4413 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
4416 && any_condjump_p (BB_END (src
))
4417 && onlyjump_p (BB_END (src
)))
4418 delete_insn (BB_END (src
));
4421 fprintf (dump_file
, "Redirecting fallthru edge %i->%i to %i\n",
4422 e
->src
->index
, e
->dest
->index
, dest
->index
);
4423 ret
= redirect_edge_succ_nodup (e
, dest
);
4426 ret
= redirect_branch_edge (e
, dest
);
4428 /* We don't want simplejumps in the insn stream during cfglayout. */
4429 gcc_assert (!simplejump_p (BB_END (src
)));
4431 df_set_bb_dirty (src
);
4435 /* Simple wrapper as we always can redirect fallthru edges. */
4437 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
4439 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
4441 gcc_assert (redirected
);
4445 /* Same as delete_basic_block but update cfg_layout structures. */
4448 cfg_layout_delete_block (basic_block bb
)
4450 rtx_insn
*insn
, *next
, *prev
= PREV_INSN (BB_HEAD (bb
)), *remaints
;
4455 next
= BB_HEAD (bb
);
4457 SET_NEXT_INSN (prev
) = BB_HEADER (bb
);
4459 set_first_insn (BB_HEADER (bb
));
4460 SET_PREV_INSN (BB_HEADER (bb
)) = prev
;
4461 insn
= BB_HEADER (bb
);
4462 while (NEXT_INSN (insn
))
4463 insn
= NEXT_INSN (insn
);
4464 SET_NEXT_INSN (insn
) = next
;
4465 SET_PREV_INSN (next
) = insn
;
4467 next
= NEXT_INSN (BB_END (bb
));
4470 insn
= BB_FOOTER (bb
);
4473 if (BARRIER_P (insn
))
4475 if (PREV_INSN (insn
))
4476 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
4478 BB_FOOTER (bb
) = NEXT_INSN (insn
);
4479 if (NEXT_INSN (insn
))
4480 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
4484 insn
= NEXT_INSN (insn
);
4489 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
4490 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
4491 while (NEXT_INSN (insn
))
4492 insn
= NEXT_INSN (insn
);
4493 SET_NEXT_INSN (insn
) = next
;
4495 SET_PREV_INSN (next
) = insn
;
4497 set_last_insn (insn
);
4500 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
4501 to
= &BB_HEADER (bb
->next_bb
);
4503 to
= &cfg_layout_function_footer
;
4505 rtl_delete_block (bb
);
4508 prev
= NEXT_INSN (prev
);
4510 prev
= get_insns ();
4512 next
= PREV_INSN (next
);
4514 next
= get_last_insn ();
4516 if (next
&& NEXT_INSN (next
) != prev
)
4518 remaints
= unlink_insn_chain (prev
, next
);
4520 while (NEXT_INSN (insn
))
4521 insn
= NEXT_INSN (insn
);
4522 SET_NEXT_INSN (insn
) = *to
;
4524 SET_PREV_INSN (*to
) = insn
;
4529 /* Return true when blocks A and B can be safely merged. */
4532 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
4534 /* If we are partitioning hot/cold basic blocks, we don't want to
4535 mess up unconditional or indirect jumps that cross between hot
4538 Basic block partitioning may result in some jumps that appear to
4539 be optimizable (or blocks that appear to be mergeable), but which really
4540 must be left untouched (they are required to make it safely across
4541 partition boundaries). See the comments at the top of
4542 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4544 if (BB_PARTITION (a
) != BB_PARTITION (b
))
4547 /* Protect the loop latches. */
4548 if (current_loops
&& b
->loop_father
->latch
== b
)
4551 /* If we would end up moving B's instructions, make sure it doesn't fall
4552 through into the exit block, since we cannot recover from a fallthrough
4553 edge into the exit block occurring in the middle of a function. */
4554 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4556 edge e
= find_fallthru_edge (b
->succs
);
4557 if (e
&& e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4561 /* There must be exactly one edge in between the blocks. */
4562 return (single_succ_p (a
)
4563 && single_succ (a
) == b
4564 && single_pred_p (b
) == 1
4566 /* Must be simple edge. */
4567 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
4568 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4569 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
4570 /* If the jump insn has side effects, we can't kill the edge.
4571 When not optimizing, try_redirect_by_replacing_jump will
4572 not allow us to redirect an edge by replacing a table jump. */
4573 && (!JUMP_P (BB_END (a
))
4574 || ((!optimize
|| reload_completed
)
4575 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
4578 /* Merge block A and B. The blocks must be mergeable. */
4581 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
4583 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
4586 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a
, b
));
4589 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
4592 /* If there was a CODE_LABEL beginning B, delete it. */
4593 if (LABEL_P (BB_HEAD (b
)))
4595 delete_insn (BB_HEAD (b
));
4598 /* We should have fallthru edge in a, or we can do dummy redirection to get
4600 if (JUMP_P (BB_END (a
)))
4601 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
4602 gcc_assert (!JUMP_P (BB_END (a
)));
4604 /* When not optimizing and the edge is the only place in RTL which holds
4605 some unique locus, emit a nop with that locus in between. */
4607 emit_nop_for_unique_locus_between (a
, b
);
4609 /* Move things from b->footer after a->footer. */
4613 BB_FOOTER (a
) = BB_FOOTER (b
);
4616 rtx_insn
*last
= BB_FOOTER (a
);
4618 while (NEXT_INSN (last
))
4619 last
= NEXT_INSN (last
);
4620 SET_NEXT_INSN (last
) = BB_FOOTER (b
);
4621 SET_PREV_INSN (BB_FOOTER (b
)) = last
;
4623 BB_FOOTER (b
) = NULL
;
4626 /* Move things from b->header before a->footer.
4627 Note that this may include dead tablejump data, but we don't clean
4628 those up until we go out of cfglayout mode. */
4631 if (! BB_FOOTER (a
))
4632 BB_FOOTER (a
) = BB_HEADER (b
);
4635 rtx_insn
*last
= BB_HEADER (b
);
4637 while (NEXT_INSN (last
))
4638 last
= NEXT_INSN (last
);
4639 SET_NEXT_INSN (last
) = BB_FOOTER (a
);
4640 SET_PREV_INSN (BB_FOOTER (a
)) = last
;
4641 BB_FOOTER (a
) = BB_HEADER (b
);
4643 BB_HEADER (b
) = NULL
;
4646 /* In the case basic blocks are not adjacent, move them around. */
4647 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4649 insn
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
4651 emit_insn_after_noloc (insn
, BB_END (a
), a
);
4653 /* Otherwise just re-associate the instructions. */
4657 BB_END (a
) = BB_END (b
);
4660 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4661 We need to explicitly call. */
4662 update_bb_for_insn_chain (insn
, BB_END (b
), a
);
4664 /* Skip possible DELETED_LABEL insn. */
4665 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
4666 insn
= NEXT_INSN (insn
);
4667 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4668 BB_HEAD (b
) = BB_END (b
) = NULL
;
4671 df_bb_delete (b
->index
);
4673 /* If B was a forwarder block, propagate the locus on the edge. */
4675 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
4676 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
4679 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
4685 cfg_layout_split_edge (edge e
)
4687 basic_block new_bb
=
4688 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4689 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
4692 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4693 BB_COPY_PARTITION (new_bb
, e
->src
);
4695 BB_COPY_PARTITION (new_bb
, e
->dest
);
4696 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
4697 redirect_edge_and_branch_force (e
, new_bb
);
4702 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4705 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
4709 /* Return true if BB contains only labels or non-executable
4713 rtl_block_empty_p (basic_block bb
)
4717 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4718 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4721 FOR_BB_INSNS (bb
, insn
)
4722 if (NONDEBUG_INSN_P (insn
) && !any_uncondjump_p (insn
))
4728 /* Split a basic block if it ends with a conditional branch and if
4729 the other part of the block is not empty. */
4732 rtl_split_block_before_cond_jump (basic_block bb
)
4735 rtx_insn
*split_point
= NULL
;
4736 rtx_insn
*last
= NULL
;
4737 bool found_code
= false;
4739 FOR_BB_INSNS (bb
, insn
)
4741 if (any_condjump_p (insn
))
4743 else if (NONDEBUG_INSN_P (insn
))
4748 /* Did not find everything. */
4749 if (found_code
&& split_point
)
4750 return split_block (bb
, split_point
)->dest
;
4755 /* Return 1 if BB ends with a call, possibly followed by some
4756 instructions that must stay with the call, 0 otherwise. */
4759 rtl_block_ends_with_call_p (basic_block bb
)
4761 rtx_insn
*insn
= BB_END (bb
);
4763 while (!CALL_P (insn
)
4764 && insn
!= BB_HEAD (bb
)
4765 && (keep_with_call_p (insn
)
4767 || DEBUG_INSN_P (insn
)))
4768 insn
= PREV_INSN (insn
);
4769 return (CALL_P (insn
));
4772 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4775 rtl_block_ends_with_condjump_p (const_basic_block bb
)
4777 return any_condjump_p (BB_END (bb
));
4780 /* Return true if we need to add fake edge to exit.
4781 Helper function for rtl_flow_call_edges_add. */
4784 need_fake_edge_p (const rtx_insn
*insn
)
4790 && !SIBLING_CALL_P (insn
)
4791 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
4792 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
4795 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
4796 && MEM_VOLATILE_P (PATTERN (insn
)))
4797 || (GET_CODE (PATTERN (insn
)) == PARALLEL
4798 && asm_noperands (insn
) != -1
4799 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
4800 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
4803 /* Add fake edges to the function exit for any non constant and non noreturn
4804 calls, volatile inline assembly in the bitmap of blocks specified by
4805 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4808 The goal is to expose cases in which entering a basic block does not imply
4809 that all subsequent instructions must be executed. */
4812 rtl_flow_call_edges_add (sbitmap blocks
)
4815 int blocks_split
= 0;
4816 int last_bb
= last_basic_block_for_fn (cfun
);
4817 bool check_last_block
= false;
4819 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
4823 check_last_block
= true;
4825 check_last_block
= bitmap_bit_p (blocks
,
4826 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
->index
);
4828 /* In the last basic block, before epilogue generation, there will be
4829 a fallthru edge to EXIT. Special care is required if the last insn
4830 of the last basic block is a call because make_edge folds duplicate
4831 edges, which would result in the fallthru edge also being marked
4832 fake, which would result in the fallthru edge being removed by
4833 remove_fake_edges, which would result in an invalid CFG.
4835 Moreover, we can't elide the outgoing fake edge, since the block
4836 profiler needs to take this into account in order to solve the minimal
4837 spanning tree in the case that the call doesn't return.
4839 Handle this by adding a dummy instruction in a new last basic block. */
4840 if (check_last_block
)
4842 basic_block bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
4843 rtx_insn
*insn
= BB_END (bb
);
4845 /* Back up past insns that must be kept in the same block as a call. */
4846 while (insn
!= BB_HEAD (bb
)
4847 && keep_with_call_p (insn
))
4848 insn
= PREV_INSN (insn
);
4850 if (need_fake_edge_p (insn
))
4854 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4857 insert_insn_on_edge (gen_use (const0_rtx
), e
);
4858 commit_edge_insertions ();
4863 /* Now add fake edges to the function exit for any non constant
4864 calls since there is no way that we can determine if they will
4867 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
4869 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
4871 rtx_insn
*prev_insn
;
4876 if (blocks
&& !bitmap_bit_p (blocks
, i
))
4879 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
4881 prev_insn
= PREV_INSN (insn
);
4882 if (need_fake_edge_p (insn
))
4885 rtx_insn
*split_at_insn
= insn
;
4887 /* Don't split the block between a call and an insn that should
4888 remain in the same block as the call. */
4890 while (split_at_insn
!= BB_END (bb
)
4891 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
4892 split_at_insn
= NEXT_INSN (split_at_insn
);
4894 /* The handling above of the final block before the epilogue
4895 should be enough to verify that there is no edge to the exit
4896 block in CFG already. Calling make_edge in such case would
4897 cause us to mark that edge as fake and remove it later. */
4899 if (flag_checking
&& split_at_insn
== BB_END (bb
))
4901 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4902 gcc_assert (e
== NULL
);
4905 /* Note that the following may create a new basic block
4906 and renumber the existing basic blocks. */
4907 if (split_at_insn
!= BB_END (bb
))
4909 e
= split_block (bb
, split_at_insn
);
4914 edge ne
= make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
4915 ne
->probability
= profile_probability::guessed_never ();
4918 if (insn
== BB_HEAD (bb
))
4924 verify_flow_info ();
4926 return blocks_split
;
4929 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4930 the conditional branch target, SECOND_HEAD should be the fall-thru
4931 there is no need to handle this here the loop versioning code handles
4932 this. the reason for SECON_HEAD is that it is needed for condition
4933 in trees, and this should be of the same type since it is a hook. */
4935 rtl_lv_add_condition_to_bb (basic_block first_head
,
4936 basic_block second_head ATTRIBUTE_UNUSED
,
4937 basic_block cond_bb
, void *comp_rtx
)
4939 rtx_code_label
*label
;
4940 rtx_insn
*seq
, *jump
;
4941 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
4942 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
4943 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
4947 label
= block_label (first_head
);
4948 mode
= GET_MODE (op0
);
4949 if (mode
== VOIDmode
)
4950 mode
= GET_MODE (op1
);
4953 op0
= force_operand (op0
, NULL_RTX
);
4954 op1
= force_operand (op1
, NULL_RTX
);
4955 do_compare_rtx_and_jump (op0
, op1
, comp
, 0, mode
, NULL_RTX
, NULL
, label
,
4956 profile_probability::uninitialized ());
4957 jump
= get_last_insn ();
4958 JUMP_LABEL (jump
) = label
;
4959 LABEL_NUSES (label
)++;
4963 /* Add the new cond, in the new head. */
4964 emit_insn_after (seq
, BB_END (cond_bb
));
4968 /* Given a block B with unconditional branch at its end, get the
4969 store the return the branch edge and the fall-thru edge in
4970 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4972 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
4973 edge
*fallthru_edge
)
4975 edge e
= EDGE_SUCC (b
, 0);
4977 if (e
->flags
& EDGE_FALLTHRU
)
4980 *branch_edge
= EDGE_SUCC (b
, 1);
4985 *fallthru_edge
= EDGE_SUCC (b
, 1);
4990 init_rtl_bb_info (basic_block bb
)
4992 gcc_assert (!bb
->il
.x
.rtl
);
4993 bb
->il
.x
.head_
= NULL
;
4994 bb
->il
.x
.rtl
= ggc_cleared_alloc
<rtl_bb_info
> ();
4997 /* Returns true if it is possible to remove edge E by redirecting
4998 it to the destination of the other edge from E->src. */
5001 rtl_can_remove_branch_p (const_edge e
)
5003 const_basic_block src
= e
->src
;
5004 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
5005 const rtx_insn
*insn
= BB_END (src
);
5008 /* The conditions are taken from try_redirect_by_replacing_jump. */
5009 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
5012 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
5015 if (BB_PARTITION (src
) != BB_PARTITION (target
))
5018 if (!onlyjump_p (insn
)
5019 || tablejump_p (insn
, NULL
, NULL
))
5022 set
= single_set (insn
);
5023 if (!set
|| side_effects_p (set
))
5030 rtl_duplicate_bb (basic_block bb
)
5032 bb
= cfg_layout_duplicate_bb (bb
);
5037 /* Do book-keeping of basic block BB for the profile consistency checker.
5038 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
5039 then do post-pass accounting. Store the counting in RECORD. */
5041 rtl_account_profile_record (basic_block bb
, int after_pass
,
5042 struct profile_record
*record
)
5045 FOR_BB_INSNS (bb
, insn
)
5048 record
->size
[after_pass
] += insn_cost (insn
, false);
5049 if (bb
->count
.initialized_p ())
5050 record
->time
[after_pass
]
5051 += insn_cost (insn
, true) * bb
->count
.to_gcov_type ();
5052 else if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
5053 record
->time
[after_pass
]
5054 += insn_cost (insn
, true) * bb
->count
.to_frequency (cfun
);
5058 /* Implementation of CFG manipulation for linearized RTL. */
5059 struct cfg_hooks rtl_cfg_hooks
= {
5061 rtl_verify_flow_info
,
5063 rtl_dump_bb_for_graph
,
5064 rtl_create_basic_block
,
5065 rtl_redirect_edge_and_branch
,
5066 rtl_redirect_edge_and_branch_force
,
5067 rtl_can_remove_branch_p
,
5070 rtl_move_block_after
,
5071 rtl_can_merge_blocks
, /* can_merge_blocks_p */
5075 cfg_layout_can_duplicate_bb_p
,
5078 rtl_make_forwarder_block
,
5079 rtl_tidy_fallthru_edge
,
5080 rtl_force_nonfallthru
,
5081 rtl_block_ends_with_call_p
,
5082 rtl_block_ends_with_condjump_p
,
5083 rtl_flow_call_edges_add
,
5084 NULL
, /* execute_on_growing_pred */
5085 NULL
, /* execute_on_shrinking_pred */
5086 NULL
, /* duplicate loop for trees */
5087 NULL
, /* lv_add_condition_to_bb */
5088 NULL
, /* lv_adjust_loop_header_phi*/
5089 NULL
, /* extract_cond_bb_edges */
5090 NULL
, /* flush_pending_stmts */
5091 rtl_block_empty_p
, /* block_empty_p */
5092 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5093 rtl_account_profile_record
,
5096 /* Implementation of CFG manipulation for cfg layout RTL, where
5097 basic block connected via fallthru edges does not have to be adjacent.
5098 This representation will hopefully become the default one in future
5099 version of the compiler. */
5101 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
5103 rtl_verify_flow_info_1
,
5105 rtl_dump_bb_for_graph
,
5106 cfg_layout_create_basic_block
,
5107 cfg_layout_redirect_edge_and_branch
,
5108 cfg_layout_redirect_edge_and_branch_force
,
5109 rtl_can_remove_branch_p
,
5110 cfg_layout_delete_block
,
5111 cfg_layout_split_block
,
5112 rtl_move_block_after
,
5113 cfg_layout_can_merge_blocks_p
,
5114 cfg_layout_merge_blocks
,
5117 cfg_layout_can_duplicate_bb_p
,
5118 cfg_layout_duplicate_bb
,
5119 cfg_layout_split_edge
,
5120 rtl_make_forwarder_block
,
5121 NULL
, /* tidy_fallthru_edge */
5122 rtl_force_nonfallthru
,
5123 rtl_block_ends_with_call_p
,
5124 rtl_block_ends_with_condjump_p
,
5125 rtl_flow_call_edges_add
,
5126 NULL
, /* execute_on_growing_pred */
5127 NULL
, /* execute_on_shrinking_pred */
5128 duplicate_loop_to_header_edge
, /* duplicate loop for trees */
5129 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
5130 NULL
, /* lv_adjust_loop_header_phi*/
5131 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
5132 NULL
, /* flush_pending_stmts */
5133 rtl_block_empty_p
, /* block_empty_p */
5134 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5135 rtl_account_profile_record
,
5138 #include "gt-cfgrtl.h"