1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2019 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 use or 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 Similarly, keep a USE of the function return value, otherwise
561 the USE is dropped and we could fail to thread jump if USE
562 appears on some paths and not on others, see PR90257. */
563 if ((GET_CODE (PATTERN (insn
)) == CLOBBER
564 || GET_CODE (PATTERN (insn
)) == USE
)
565 && REG_P (XEXP (PATTERN (insn
), 0))
566 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn
), 0)))
572 /* Return true if the block has no effect and only forwards control flow to
573 its single destination. */
576 contains_no_active_insn_p (const_basic_block bb
)
580 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
581 || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
582 || !single_succ_p (bb
)
583 || (single_succ_edge (bb
)->flags
& EDGE_FAKE
) != 0)
586 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
587 if (INSN_P (insn
) && flow_active_insn_p (insn
))
590 return (!INSN_P (insn
)
591 || (JUMP_P (insn
) && simplejump_p (insn
))
592 || !flow_active_insn_p (insn
));
595 /* Likewise, but protect loop latches, headers and preheaders. */
596 /* FIXME: Make this a cfg hook. */
599 forwarder_block_p (const_basic_block bb
)
601 if (!contains_no_active_insn_p (bb
))
604 /* Protect loop latches, headers and preheaders. */
608 if (bb
->loop_father
->header
== bb
)
610 dest
= EDGE_SUCC (bb
, 0)->dest
;
611 if (dest
->loop_father
->header
== dest
)
618 /* Return nonzero if we can reach target from src by falling through. */
619 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
622 can_fallthru (basic_block src
, basic_block target
)
624 rtx_insn
*insn
= BB_END (src
);
629 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
631 if (src
->next_bb
!= target
)
634 /* ??? Later we may add code to move jump tables offline. */
635 if (tablejump_p (insn
, NULL
, NULL
))
638 FOR_EACH_EDGE (e
, ei
, src
->succs
)
639 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
640 && e
->flags
& EDGE_FALLTHRU
)
643 insn2
= BB_HEAD (target
);
644 if (!active_insn_p (insn2
))
645 insn2
= next_active_insn (insn2
);
647 return next_active_insn (insn
) == insn2
;
650 /* Return nonzero if we could reach target from src by falling through,
651 if the target was made adjacent. If we already have a fall-through
652 edge to the exit block, we can't do that. */
654 could_fall_through (basic_block src
, basic_block target
)
659 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
661 FOR_EACH_EDGE (e
, ei
, src
->succs
)
662 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
663 && e
->flags
& EDGE_FALLTHRU
)
668 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
670 bb_note (basic_block bb
)
676 note
= NEXT_INSN (note
);
678 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
679 return as_a
<rtx_note
*> (note
);
682 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
683 note associated with the BLOCK. */
686 first_insn_after_basic_block_note (basic_block block
)
690 /* Get the first instruction in the block. */
691 insn
= BB_HEAD (block
);
693 if (insn
== NULL_RTX
)
696 insn
= NEXT_INSN (insn
);
697 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
699 return NEXT_INSN (insn
);
702 /* Creates a new basic block just after basic block BB by splitting
703 everything after specified instruction INSNP. */
706 rtl_split_block (basic_block bb
, void *insnp
)
709 rtx_insn
*insn
= (rtx_insn
*) insnp
;
715 insn
= first_insn_after_basic_block_note (bb
);
719 rtx_insn
*next
= insn
;
721 insn
= PREV_INSN (insn
);
723 /* If the block contains only debug insns, insn would have
724 been NULL in a non-debug compilation, and then we'd end
725 up emitting a DELETED note. For -fcompare-debug
726 stability, emit the note too. */
727 if (insn
!= BB_END (bb
)
728 && DEBUG_INSN_P (next
)
729 && DEBUG_INSN_P (BB_END (bb
)))
731 while (next
!= BB_END (bb
) && DEBUG_INSN_P (next
))
732 next
= NEXT_INSN (next
);
734 if (next
== BB_END (bb
))
735 emit_note_after (NOTE_INSN_DELETED
, next
);
739 insn
= get_last_insn ();
742 /* We probably should check type of the insn so that we do not create
743 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
745 if (insn
== BB_END (bb
))
746 emit_note_after (NOTE_INSN_DELETED
, insn
);
748 /* Create the new basic block. */
749 new_bb
= create_basic_block (NEXT_INSN (insn
), BB_END (bb
), bb
);
750 BB_COPY_PARTITION (new_bb
, bb
);
753 /* Redirect the outgoing edges. */
754 new_bb
->succs
= bb
->succs
;
756 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
759 /* The new block starts off being dirty. */
760 df_set_bb_dirty (bb
);
764 /* Return true if the single edge between blocks A and B is the only place
765 in RTL which holds some unique locus. */
768 unique_locus_on_edge_between_p (basic_block a
, basic_block b
)
770 const location_t goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
771 rtx_insn
*insn
, *end
;
773 if (LOCATION_LOCUS (goto_locus
) == UNKNOWN_LOCATION
)
776 /* First scan block A backward. */
778 end
= PREV_INSN (BB_HEAD (a
));
779 while (insn
!= end
&& (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
780 insn
= PREV_INSN (insn
);
782 if (insn
!= end
&& INSN_LOCATION (insn
) == goto_locus
)
785 /* Then scan block B forward. */
789 end
= NEXT_INSN (BB_END (b
));
790 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
791 insn
= NEXT_INSN (insn
);
793 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
794 && INSN_LOCATION (insn
) == goto_locus
)
801 /* If the single edge between blocks A and B is the only place in RTL which
802 holds some unique locus, emit a nop with that locus between the blocks. */
805 emit_nop_for_unique_locus_between (basic_block a
, basic_block b
)
807 if (!unique_locus_on_edge_between_p (a
, b
))
810 BB_END (a
) = emit_insn_after_noloc (gen_nop (), BB_END (a
), a
);
811 INSN_LOCATION (BB_END (a
)) = EDGE_SUCC (a
, 0)->goto_locus
;
814 /* Blocks A and B are to be merged into a single block A. The insns
815 are already contiguous. */
818 rtl_merge_blocks (basic_block a
, basic_block b
)
820 /* If B is a forwarder block whose outgoing edge has no location, we'll
821 propagate the locus of the edge between A and B onto it. */
822 const bool forward_edge_locus
823 = (b
->flags
& BB_FORWARDER_BLOCK
) != 0
824 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
;
825 rtx_insn
*b_head
= BB_HEAD (b
), *b_end
= BB_END (b
), *a_end
= BB_END (a
);
826 rtx_insn
*del_first
= NULL
, *del_last
= NULL
;
827 rtx_insn
*b_debug_start
= b_end
, *b_debug_end
= b_end
;
831 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
834 while (DEBUG_INSN_P (b_end
))
835 b_end
= PREV_INSN (b_debug_start
= b_end
);
837 /* If there was a CODE_LABEL beginning B, delete it. */
838 if (LABEL_P (b_head
))
840 /* Detect basic blocks with nothing but a label. This can happen
841 in particular at the end of a function. */
845 del_first
= del_last
= b_head
;
846 b_head
= NEXT_INSN (b_head
);
849 /* Delete the basic block note and handle blocks containing just that
851 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
859 b_head
= NEXT_INSN (b_head
);
862 /* If there was a jump out of A, delete it. */
867 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
869 || NOTE_INSN_BASIC_BLOCK_P (prev
)
870 || prev
== BB_HEAD (a
))
875 /* If this was a conditional jump, we need to also delete
876 the insn that set cc0. */
877 if (HAVE_cc0
&& only_sets_cc0_p (prev
))
879 rtx_insn
*tmp
= prev
;
881 prev
= prev_nonnote_insn (prev
);
887 a_end
= PREV_INSN (del_first
);
889 else if (BARRIER_P (NEXT_INSN (a_end
)))
890 del_first
= NEXT_INSN (a_end
);
892 /* Delete everything marked above as well as crap that might be
893 hanging out between the two blocks. */
895 BB_HEAD (b
) = b_empty
? NULL
: b_head
;
896 delete_insn_chain (del_first
, del_last
, true);
898 /* If not optimizing, preserve the locus of the single edge between
899 blocks A and B if necessary by emitting a nop. */
901 && !forward_edge_locus
902 && !DECL_IGNORED_P (current_function_decl
))
904 emit_nop_for_unique_locus_between (a
, b
);
908 /* Reassociate the insns of B with A. */
911 update_bb_for_insn_chain (a_end
, b_debug_end
, a
);
913 BB_END (a
) = b_debug_end
;
916 else if (b_end
!= b_debug_end
)
918 /* Move any deleted labels and other notes between the end of A
919 and the debug insns that make up B after the debug insns,
920 bringing the debug insns into A while keeping the notes after
922 if (NEXT_INSN (a_end
) != b_debug_start
)
923 reorder_insns_nobb (NEXT_INSN (a_end
), PREV_INSN (b_debug_start
),
925 update_bb_for_insn_chain (b_debug_start
, b_debug_end
, a
);
926 BB_END (a
) = b_debug_end
;
929 df_bb_delete (b
->index
);
931 if (forward_edge_locus
)
932 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
935 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
939 /* Return true when block A and B can be merged. */
942 rtl_can_merge_blocks (basic_block a
, basic_block b
)
944 /* If we are partitioning hot/cold basic blocks, we don't want to
945 mess up unconditional or indirect jumps that cross between hot
948 Basic block partitioning may result in some jumps that appear to
949 be optimizable (or blocks that appear to be mergeable), but which really
950 must be left untouched (they are required to make it safely across
951 partition boundaries). See the comments at the top of
952 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
954 if (BB_PARTITION (a
) != BB_PARTITION (b
))
957 /* Protect the loop latches. */
958 if (current_loops
&& b
->loop_father
->latch
== b
)
961 /* There must be exactly one edge in between the blocks. */
962 return (single_succ_p (a
)
963 && single_succ (a
) == b
966 /* Must be simple edge. */
967 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
969 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
970 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
971 /* If the jump insn has side effects,
972 we can't kill the edge. */
973 && (!JUMP_P (BB_END (a
))
975 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
978 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
982 block_label (basic_block block
)
984 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
987 if (!LABEL_P (BB_HEAD (block
)))
989 BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
992 return as_a
<rtx_code_label
*> (BB_HEAD (block
));
995 /* Remove all barriers from BB_FOOTER of a BB. */
998 remove_barriers_from_footer (basic_block bb
)
1000 rtx_insn
*insn
= BB_FOOTER (bb
);
1002 /* Remove barriers but keep jumptables. */
1005 if (BARRIER_P (insn
))
1007 if (PREV_INSN (insn
))
1008 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1010 BB_FOOTER (bb
) = NEXT_INSN (insn
);
1011 if (NEXT_INSN (insn
))
1012 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1016 insn
= NEXT_INSN (insn
);
1020 /* Attempt to perform edge redirection by replacing possibly complex jump
1021 instruction by unconditional jump or removing jump completely. This can
1022 apply only if all edges now point to the same block. The parameters and
1023 return values are equivalent to redirect_edge_and_branch. */
1026 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
1028 basic_block src
= e
->src
;
1029 rtx_insn
*insn
= BB_END (src
), *kill_from
;
1033 /* If we are partitioning hot/cold basic blocks, we don't want to
1034 mess up unconditional or indirect jumps that cross between hot
1037 Basic block partitioning may result in some jumps that appear to
1038 be optimizable (or blocks that appear to be mergeable), but which really
1039 must be left untouched (they are required to make it safely across
1040 partition boundaries). See the comments at the top of
1041 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1043 if (BB_PARTITION (src
) != BB_PARTITION (target
))
1046 /* We can replace or remove a complex jump only when we have exactly
1047 two edges. Also, if we have exactly one outgoing edge, we can
1049 if (EDGE_COUNT (src
->succs
) >= 3
1050 /* Verify that all targets will be TARGET. Specifically, the
1051 edge that is not E must also go to TARGET. */
1052 || (EDGE_COUNT (src
->succs
) == 2
1053 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
1056 if (!onlyjump_p (insn
))
1058 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
1061 /* Avoid removing branch with side effects. */
1062 set
= single_set (insn
);
1063 if (!set
|| side_effects_p (set
))
1066 /* In case we zap a conditional jump, we'll need to kill
1067 the cc0 setter too. */
1069 if (HAVE_cc0
&& reg_mentioned_p (cc0_rtx
, PATTERN (insn
))
1070 && only_sets_cc0_p (PREV_INSN (insn
)))
1071 kill_from
= PREV_INSN (insn
);
1073 /* See if we can create the fallthru edge. */
1074 if (in_cfglayout
|| can_fallthru (src
, target
))
1077 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
1080 /* Selectively unlink whole insn chain. */
1083 delete_insn_chain (kill_from
, BB_END (src
), false);
1084 remove_barriers_from_footer (src
);
1087 delete_insn_chain (kill_from
, PREV_INSN (BB_HEAD (target
)),
1091 /* If this already is simplejump, redirect it. */
1092 else if (simplejump_p (insn
))
1094 if (e
->dest
== target
)
1097 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
1098 INSN_UID (insn
), e
->dest
->index
, target
->index
);
1099 if (!redirect_jump (as_a
<rtx_jump_insn
*> (insn
),
1100 block_label (target
), 0))
1102 gcc_assert (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1107 /* Cannot do anything for target exit block. */
1108 else if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1111 /* Or replace possibly complicated jump insn by simple jump insn. */
1114 rtx_code_label
*target_label
= block_label (target
);
1117 rtx_jump_table_data
*table
;
1119 emit_jump_insn_after_noloc (targetm
.gen_jump (target_label
), insn
);
1120 JUMP_LABEL (BB_END (src
)) = target_label
;
1121 LABEL_NUSES (target_label
)++;
1123 fprintf (dump_file
, "Replacing insn %i by jump %i\n",
1124 INSN_UID (insn
), INSN_UID (BB_END (src
)));
1127 delete_insn_chain (kill_from
, insn
, false);
1129 /* Recognize a tablejump that we are converting to a
1130 simple jump and remove its associated CODE_LABEL
1131 and ADDR_VEC or ADDR_DIFF_VEC. */
1132 if (tablejump_p (insn
, &label
, &table
))
1133 delete_insn_chain (label
, table
, false);
1135 barrier
= next_nonnote_nondebug_insn (BB_END (src
));
1136 if (!barrier
|| !BARRIER_P (barrier
))
1137 emit_barrier_after (BB_END (src
));
1140 if (barrier
!= NEXT_INSN (BB_END (src
)))
1142 /* Move the jump before barrier so that the notes
1143 which originally were or were created before jump table are
1144 inside the basic block. */
1145 rtx_insn
*new_insn
= BB_END (src
);
1147 update_bb_for_insn_chain (NEXT_INSN (BB_END (src
)),
1148 PREV_INSN (barrier
), src
);
1150 SET_NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
1151 SET_PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
1153 SET_NEXT_INSN (new_insn
) = barrier
;
1154 SET_NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
1156 SET_PREV_INSN (new_insn
) = PREV_INSN (barrier
);
1157 SET_PREV_INSN (barrier
) = new_insn
;
1162 /* Keep only one edge out and set proper flags. */
1163 if (!single_succ_p (src
))
1165 gcc_assert (single_succ_p (src
));
1167 e
= single_succ_edge (src
);
1169 e
->flags
= EDGE_FALLTHRU
;
1173 e
->probability
= profile_probability::always ();
1175 if (e
->dest
!= target
)
1176 redirect_edge_succ (e
, target
);
1180 /* Subroutine of redirect_branch_edge that tries to patch the jump
1181 instruction INSN so that it reaches block NEW. Do this
1182 only when it originally reached block OLD. Return true if this
1183 worked or the original target wasn't OLD, return false if redirection
1187 patch_jump_insn (rtx_insn
*insn
, rtx_insn
*old_label
, basic_block new_bb
)
1189 rtx_jump_table_data
*table
;
1191 /* Recognize a tablejump and adjust all matching cases. */
1192 if (tablejump_p (insn
, NULL
, &table
))
1196 rtx_code_label
*new_label
= block_label (new_bb
);
1198 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1200 vec
= table
->get_labels ();
1202 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
1203 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
1205 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
1206 --LABEL_NUSES (old_label
);
1207 ++LABEL_NUSES (new_label
);
1210 /* Handle casesi dispatch insns. */
1211 if ((tmp
= single_set (insn
)) != NULL
1212 && SET_DEST (tmp
) == pc_rtx
1213 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
1214 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
1215 && label_ref_label (XEXP (SET_SRC (tmp
), 2)) == old_label
)
1217 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
1219 --LABEL_NUSES (old_label
);
1220 ++LABEL_NUSES (new_label
);
1223 else if ((tmp
= extract_asm_operands (PATTERN (insn
))) != NULL
)
1225 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (tmp
);
1228 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1230 rtx_code_label
*new_label
= block_label (new_bb
);
1232 for (i
= 0; i
< n
; ++i
)
1234 rtx old_ref
= ASM_OPERANDS_LABEL (tmp
, i
);
1235 gcc_assert (GET_CODE (old_ref
) == LABEL_REF
);
1236 if (XEXP (old_ref
, 0) == old_label
)
1238 ASM_OPERANDS_LABEL (tmp
, i
)
1239 = gen_rtx_LABEL_REF (Pmode
, new_label
);
1240 --LABEL_NUSES (old_label
);
1241 ++LABEL_NUSES (new_label
);
1245 if (JUMP_LABEL (insn
) == old_label
)
1247 JUMP_LABEL (insn
) = new_label
;
1248 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1250 remove_note (insn
, note
);
1254 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1256 remove_note (insn
, note
);
1257 if (JUMP_LABEL (insn
) != new_label
1258 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1259 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1261 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1263 XEXP (note
, 0) = new_label
;
1267 /* ?? We may play the games with moving the named labels from
1268 one basic block to the other in case only one computed_jump is
1270 if (computed_jump_p (insn
)
1271 /* A return instruction can't be redirected. */
1272 || returnjump_p (insn
))
1275 if (!currently_expanding_to_rtl
|| JUMP_LABEL (insn
) == old_label
)
1277 /* If the insn doesn't go where we think, we're confused. */
1278 gcc_assert (JUMP_LABEL (insn
) == old_label
);
1280 /* If the substitution doesn't succeed, die. This can happen
1281 if the back end emitted unrecognizable instructions or if
1282 target is exit block on some arches. Or for crossing
1284 if (!redirect_jump (as_a
<rtx_jump_insn
*> (insn
),
1285 block_label (new_bb
), 0))
1287 gcc_assert (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
1288 || CROSSING_JUMP_P (insn
));
1297 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1300 redirect_branch_edge (edge e
, basic_block target
)
1302 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1303 basic_block src
= e
->src
;
1304 rtx_insn
*insn
= BB_END (src
);
1306 /* We can only redirect non-fallthru edges of jump insn. */
1307 if (e
->flags
& EDGE_FALLTHRU
)
1309 else if (!JUMP_P (insn
) && !currently_expanding_to_rtl
)
1312 if (!currently_expanding_to_rtl
)
1314 if (!patch_jump_insn (as_a
<rtx_jump_insn
*> (insn
), old_label
, target
))
1318 /* When expanding this BB might actually contain multiple
1319 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1320 Redirect all of those that match our label. */
1321 FOR_BB_INSNS (src
, insn
)
1322 if (JUMP_P (insn
) && !patch_jump_insn (as_a
<rtx_jump_insn
*> (insn
),
1327 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
1328 e
->src
->index
, e
->dest
->index
, target
->index
);
1330 if (e
->dest
!= target
)
1331 e
= redirect_edge_succ_nodup (e
, target
);
1336 /* Called when edge E has been redirected to a new destination,
1337 in order to update the region crossing flag on the edge and
1341 fixup_partition_crossing (edge e
)
1343 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || e
->dest
1344 == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1346 /* If we redirected an existing edge, it may already be marked
1347 crossing, even though the new src is missing a reg crossing note.
1348 But make sure reg crossing note doesn't already exist before
1350 if (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1352 e
->flags
|= EDGE_CROSSING
;
1353 if (JUMP_P (BB_END (e
->src
)))
1354 CROSSING_JUMP_P (BB_END (e
->src
)) = 1;
1356 else if (BB_PARTITION (e
->src
) == BB_PARTITION (e
->dest
))
1358 e
->flags
&= ~EDGE_CROSSING
;
1359 /* Remove the section crossing note from jump at end of
1360 src if it exists, and if no other successors are
1362 if (JUMP_P (BB_END (e
->src
)) && CROSSING_JUMP_P (BB_END (e
->src
)))
1364 bool has_crossing_succ
= false;
1367 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
1369 has_crossing_succ
|= (e2
->flags
& EDGE_CROSSING
);
1370 if (has_crossing_succ
)
1373 if (!has_crossing_succ
)
1374 CROSSING_JUMP_P (BB_END (e
->src
)) = 0;
1379 /* Called when block BB has been reassigned to the cold partition,
1380 because it is now dominated by another cold block,
1381 to ensure that the region crossing attributes are updated. */
1384 fixup_new_cold_bb (basic_block bb
)
1389 /* This is called when a hot bb is found to now be dominated
1390 by a cold bb and therefore needs to become cold. Therefore,
1391 its preds will no longer be region crossing. Any non-dominating
1392 preds that were previously hot would also have become cold
1393 in the caller for the same region. Any preds that were previously
1394 region-crossing will be adjusted in fixup_partition_crossing. */
1395 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1397 fixup_partition_crossing (e
);
1400 /* Possibly need to make bb's successor edges region crossing,
1401 or remove stale region crossing. */
1402 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1404 /* We can't have fall-through edges across partition boundaries.
1405 Note that force_nonfallthru will do any necessary partition
1406 boundary fixup by calling fixup_partition_crossing itself. */
1407 if ((e
->flags
& EDGE_FALLTHRU
)
1408 && BB_PARTITION (bb
) != BB_PARTITION (e
->dest
)
1409 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1410 force_nonfallthru (e
);
1412 fixup_partition_crossing (e
);
1416 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1417 expense of adding new instructions or reordering basic blocks.
1419 Function can be also called with edge destination equivalent to the TARGET.
1420 Then it should try the simplifications and do nothing if none is possible.
1422 Return edge representing the branch if transformation succeeded. Return NULL
1424 We still return NULL in case E already destinated TARGET and we didn't
1425 managed to simplify instruction stream. */
1428 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
1431 basic_block src
= e
->src
;
1432 basic_block dest
= e
->dest
;
1434 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1440 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
1442 df_set_bb_dirty (src
);
1443 fixup_partition_crossing (ret
);
1447 ret
= redirect_branch_edge (e
, target
);
1451 df_set_bb_dirty (src
);
1452 fixup_partition_crossing (ret
);
1456 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1459 emit_barrier_after_bb (basic_block bb
)
1461 rtx_barrier
*barrier
= emit_barrier_after (BB_END (bb
));
1462 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1463 || current_ir_type () == IR_RTL_CFGLAYOUT
);
1464 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
1466 rtx_insn
*insn
= unlink_insn_chain (barrier
, barrier
);
1470 rtx_insn
*footer_tail
= BB_FOOTER (bb
);
1472 while (NEXT_INSN (footer_tail
))
1473 footer_tail
= NEXT_INSN (footer_tail
);
1474 if (!BARRIER_P (footer_tail
))
1476 SET_NEXT_INSN (footer_tail
) = insn
;
1477 SET_PREV_INSN (insn
) = footer_tail
;
1481 BB_FOOTER (bb
) = insn
;
1485 /* Like force_nonfallthru below, but additionally performs redirection
1486 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1487 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1488 simple_return_rtx, indicating which kind of returnjump to create.
1489 It should be NULL otherwise. */
1492 force_nonfallthru_and_redirect (edge e
, basic_block target
, rtx jump_label
)
1494 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
1497 int abnormal_edge_flags
= 0;
1498 bool asm_goto_edge
= false;
1501 /* In the case the last instruction is conditional jump to the next
1502 instruction, first redirect the jump itself and then continue
1503 by creating a basic block afterwards to redirect fallthru edge. */
1504 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1505 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1506 && any_condjump_p (BB_END (e
->src
))
1507 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1510 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1513 redirected
= redirect_jump (as_a
<rtx_jump_insn
*> (BB_END (e
->src
)),
1514 block_label (target
), 0);
1515 gcc_assert (redirected
);
1517 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1520 int prob
= XINT (note
, 0);
1522 b
->probability
= profile_probability::from_reg_br_prob_note (prob
);
1523 e
->probability
-= e
->probability
;
1527 if (e
->flags
& EDGE_ABNORMAL
)
1529 /* Irritating special case - fallthru edge to the same block as abnormal
1531 We can't redirect abnormal edge, but we still can split the fallthru
1532 one and create separate abnormal edge to original destination.
1533 This allows bb-reorder to make such edge non-fallthru. */
1534 gcc_assert (e
->dest
== target
);
1535 abnormal_edge_flags
= e
->flags
& ~EDGE_FALLTHRU
;
1536 e
->flags
&= EDGE_FALLTHRU
;
1540 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1541 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1543 /* We can't redirect the entry block. Create an empty block
1544 at the start of the function which we use to add the new
1550 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
,
1551 ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1552 bb
->count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
;
1554 /* Make sure new block ends up in correct hot/cold section. */
1555 BB_COPY_PARTITION (bb
, e
->dest
);
1557 /* Change the existing edge's source to be the new block, and add
1558 a new edge from the entry block to the new block. */
1560 for (ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
1561 (tmp
= ei_safe_edge (ei
)); )
1565 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
->unordered_remove (ei
.index
);
1575 vec_safe_push (bb
->succs
, e
);
1576 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
,
1581 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1582 don't point to the target or fallthru label. */
1583 if (JUMP_P (BB_END (e
->src
))
1584 && target
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1585 && (e
->flags
& EDGE_FALLTHRU
)
1586 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
1588 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
1589 bool adjust_jump_target
= false;
1591 for (i
= 0; i
< n
; ++i
)
1593 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (e
->dest
))
1595 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))--;
1596 XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) = block_label (target
);
1597 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))++;
1598 adjust_jump_target
= true;
1600 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (target
))
1601 asm_goto_edge
= true;
1603 if (adjust_jump_target
)
1605 rtx_insn
*insn
= BB_END (e
->src
);
1607 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1608 rtx_insn
*new_label
= BB_HEAD (target
);
1610 if (JUMP_LABEL (insn
) == old_label
)
1612 JUMP_LABEL (insn
) = new_label
;
1613 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1615 remove_note (insn
, note
);
1619 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1621 remove_note (insn
, note
);
1622 if (JUMP_LABEL (insn
) != new_label
1623 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1624 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1626 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1628 XEXP (note
, 0) = new_label
;
1632 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
|| asm_goto_edge
)
1635 profile_count count
= e
->count ();
1636 profile_probability probability
= e
->probability
;
1637 /* Create the new structures. */
1639 /* If the old block ended with a tablejump, skip its table
1640 by searching forward from there. Otherwise start searching
1641 forward from the last instruction of the old block. */
1642 rtx_jump_table_data
*table
;
1643 if (tablejump_p (BB_END (e
->src
), NULL
, &table
))
1646 new_head
= BB_END (e
->src
);
1647 new_head
= NEXT_INSN (new_head
);
1649 jump_block
= create_basic_block (new_head
, NULL
, e
->src
);
1650 jump_block
->count
= count
;
1652 /* Make sure new block ends up in correct hot/cold section. */
1654 BB_COPY_PARTITION (jump_block
, e
->src
);
1657 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1658 new_edge
->probability
= probability
;
1660 /* Redirect old edge. */
1661 redirect_edge_pred (e
, jump_block
);
1662 e
->probability
= profile_probability::always ();
1664 /* If e->src was previously region crossing, it no longer is
1665 and the reg crossing note should be removed. */
1666 fixup_partition_crossing (new_edge
);
1668 /* If asm goto has any label refs to target's label,
1669 add also edge from asm goto bb to target. */
1672 new_edge
->probability
= new_edge
->probability
.apply_scale (1, 2);
1673 jump_block
->count
= jump_block
->count
.apply_scale (1, 2);
1674 edge new_edge2
= make_edge (new_edge
->src
, target
,
1675 e
->flags
& ~EDGE_FALLTHRU
);
1676 new_edge2
->probability
= probability
- new_edge
->probability
;
1679 new_bb
= jump_block
;
1682 jump_block
= e
->src
;
1684 loc
= e
->goto_locus
;
1685 e
->flags
&= ~EDGE_FALLTHRU
;
1686 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1688 if (jump_label
== ret_rtx
)
1689 emit_jump_insn_after_setloc (targetm
.gen_return (),
1690 BB_END (jump_block
), loc
);
1693 gcc_assert (jump_label
== simple_return_rtx
);
1694 emit_jump_insn_after_setloc (targetm
.gen_simple_return (),
1695 BB_END (jump_block
), loc
);
1697 set_return_jump_label (BB_END (jump_block
));
1701 rtx_code_label
*label
= block_label (target
);
1702 emit_jump_insn_after_setloc (targetm
.gen_jump (label
),
1703 BB_END (jump_block
), loc
);
1704 JUMP_LABEL (BB_END (jump_block
)) = label
;
1705 LABEL_NUSES (label
)++;
1708 /* We might be in cfg layout mode, and if so, the following routine will
1709 insert the barrier correctly. */
1710 emit_barrier_after_bb (jump_block
);
1711 redirect_edge_succ_nodup (e
, target
);
1713 if (abnormal_edge_flags
)
1714 make_edge (src
, target
, abnormal_edge_flags
);
1716 df_mark_solutions_dirty ();
1717 fixup_partition_crossing (e
);
1721 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1722 (and possibly create new basic block) to make edge non-fallthru.
1723 Return newly created BB or NULL if none. */
1726 rtl_force_nonfallthru (edge e
)
1728 return force_nonfallthru_and_redirect (e
, e
->dest
, NULL_RTX
);
1731 /* Redirect edge even at the expense of creating new jump insn or
1732 basic block. Return new basic block if created, NULL otherwise.
1733 Conversion must be possible. */
1736 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1738 if (redirect_edge_and_branch (e
, target
)
1739 || e
->dest
== target
)
1742 /* In case the edge redirection failed, try to force it to be non-fallthru
1743 and redirect newly created simplejump. */
1744 df_set_bb_dirty (e
->src
);
1745 return force_nonfallthru_and_redirect (e
, target
, NULL_RTX
);
1748 /* The given edge should potentially be a fallthru edge. If that is in
1749 fact true, delete the jump and barriers that are in the way. */
1752 rtl_tidy_fallthru_edge (edge e
)
1755 basic_block b
= e
->src
, c
= b
->next_bb
;
1757 /* ??? In a late-running flow pass, other folks may have deleted basic
1758 blocks by nopping out blocks, leaving multiple BARRIERs between here
1759 and the target label. They ought to be chastised and fixed.
1761 We can also wind up with a sequence of undeletable labels between
1762 one block and the next.
1764 So search through a sequence of barriers, labels, and notes for
1765 the head of block C and assert that we really do fall through. */
1767 for (q
= NEXT_INSN (BB_END (b
)); q
!= BB_HEAD (c
); q
= NEXT_INSN (q
))
1768 if (NONDEBUG_INSN_P (q
))
1771 /* Remove what will soon cease being the jump insn from the source block.
1772 If block B consisted only of this single jump, turn it into a deleted
1777 && (any_uncondjump_p (q
)
1778 || single_succ_p (b
)))
1781 rtx_jump_table_data
*table
;
1783 if (tablejump_p (q
, &label
, &table
))
1785 /* The label is likely mentioned in some instruction before
1786 the tablejump and might not be DCEd, so turn it into
1787 a note instead and move before the tablejump that is going to
1789 const char *name
= LABEL_NAME (label
);
1790 PUT_CODE (label
, NOTE
);
1791 NOTE_KIND (label
) = NOTE_INSN_DELETED_LABEL
;
1792 NOTE_DELETED_LABEL_NAME (label
) = name
;
1793 reorder_insns (label
, label
, PREV_INSN (q
));
1794 delete_insn (table
);
1797 /* If this was a conditional jump, we need to also delete
1798 the insn that set cc0. */
1799 if (HAVE_cc0
&& any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1804 /* Unconditional jumps with side-effects (i.e. which we can't just delete
1805 together with the barrier) should never have a fallthru edge. */
1806 else if (JUMP_P (q
) && any_uncondjump_p (q
))
1809 /* Selectively unlink the sequence. */
1810 if (q
!= PREV_INSN (BB_HEAD (c
)))
1811 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1813 e
->flags
|= EDGE_FALLTHRU
;
1816 /* Should move basic block BB after basic block AFTER. NIY. */
1819 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1820 basic_block after ATTRIBUTE_UNUSED
)
1825 /* Locate the last bb in the same partition as START_BB. */
1828 last_bb_in_partition (basic_block start_bb
)
1831 FOR_BB_BETWEEN (bb
, start_bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1833 if (BB_PARTITION (start_bb
) != BB_PARTITION (bb
->next_bb
))
1836 /* Return bb before the exit block. */
1840 /* Split a (typically critical) edge. Return the new block.
1841 The edge must not be abnormal.
1843 ??? The code generally expects to be called on critical edges.
1844 The case of a block ending in an unconditional jump to a
1845 block with multiple predecessors is not handled optimally. */
1848 rtl_split_edge (edge edge_in
)
1850 basic_block bb
, new_bb
;
1853 /* Abnormal edges cannot be split. */
1854 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1856 /* We are going to place the new block in front of edge destination.
1857 Avoid existence of fallthru predecessors. */
1858 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1860 edge e
= find_fallthru_edge (edge_in
->dest
->preds
);
1863 force_nonfallthru (e
);
1866 /* Create the basic block note. */
1867 if (edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1868 before
= BB_HEAD (edge_in
->dest
);
1872 /* If this is a fall through edge to the exit block, the blocks might be
1873 not adjacent, and the right place is after the source. */
1874 if ((edge_in
->flags
& EDGE_FALLTHRU
)
1875 && edge_in
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1877 before
= NEXT_INSN (BB_END (edge_in
->src
));
1878 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1879 BB_COPY_PARTITION (bb
, edge_in
->src
);
1883 if (edge_in
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1885 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1886 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1890 basic_block after
= edge_in
->dest
->prev_bb
;
1891 /* If this is post-bb reordering, and the edge crosses a partition
1892 boundary, the new block needs to be inserted in the bb chain
1893 at the end of the src partition (since we put the new bb into
1894 that partition, see below). Otherwise we may end up creating
1895 an extra partition crossing in the chain, which is illegal.
1896 It can't go after the src, because src may have a fall-through
1897 to a different block. */
1898 if (crtl
->bb_reorder_complete
1899 && (edge_in
->flags
& EDGE_CROSSING
))
1901 after
= last_bb_in_partition (edge_in
->src
);
1902 before
= get_last_bb_insn (after
);
1903 /* The instruction following the last bb in partition should
1904 be a barrier, since it cannot end in a fall-through. */
1905 gcc_checking_assert (BARRIER_P (before
));
1906 before
= NEXT_INSN (before
);
1908 bb
= create_basic_block (before
, NULL
, after
);
1909 /* Put the split bb into the src partition, to avoid creating
1910 a situation where a cold bb dominates a hot bb, in the case
1911 where src is cold and dest is hot. The src will dominate
1912 the new bb (whereas it might not have dominated dest). */
1913 BB_COPY_PARTITION (bb
, edge_in
->src
);
1917 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1919 /* Can't allow a region crossing edge to be fallthrough. */
1920 if (BB_PARTITION (bb
) != BB_PARTITION (edge_in
->dest
)
1921 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1923 new_bb
= force_nonfallthru (single_succ_edge (bb
));
1924 gcc_assert (!new_bb
);
1927 /* For non-fallthru edges, we must adjust the predecessor's
1928 jump instruction to target our new block. */
1929 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1931 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1932 gcc_assert (redirected
);
1936 if (edge_in
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1938 /* For asm goto even splitting of fallthru edge might
1939 need insn patching, as other labels might point to the
1941 rtx_insn
*last
= BB_END (edge_in
->src
);
1944 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1945 && (extract_asm_operands (PATTERN (last
))
1946 || JUMP_LABEL (last
) == before
)
1947 && patch_jump_insn (last
, before
, bb
))
1948 df_set_bb_dirty (edge_in
->src
);
1950 redirect_edge_succ (edge_in
, bb
);
1956 /* Queue instructions for insertion on an edge between two basic blocks.
1957 The new instructions and basic blocks (if any) will not appear in the
1958 CFG until commit_edge_insertions is called. */
1961 insert_insn_on_edge (rtx pattern
, edge e
)
1963 /* We cannot insert instructions on an abnormal critical edge.
1964 It will be easier to find the culprit if we die now. */
1965 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1967 if (e
->insns
.r
== NULL_RTX
)
1970 push_to_sequence (e
->insns
.r
);
1972 emit_insn (pattern
);
1974 e
->insns
.r
= get_insns ();
1978 /* Update the CFG for the instructions queued on edge E. */
1981 commit_one_edge_insertion (edge e
)
1983 rtx_insn
*before
= NULL
, *after
= NULL
, *insns
, *tmp
, *last
;
1986 /* Pull the insns off the edge now since the edge might go away. */
1990 /* Figure out where to put these insns. If the destination has
1991 one predecessor, insert there. Except for the exit block. */
1992 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1996 /* Get the location correct wrt a code label, and "nice" wrt
1997 a basic block note, and before everything else. */
2000 tmp
= NEXT_INSN (tmp
);
2001 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
2002 tmp
= NEXT_INSN (tmp
);
2003 if (tmp
== BB_HEAD (bb
))
2006 after
= PREV_INSN (tmp
);
2008 after
= get_last_insn ();
2011 /* If the source has one successor and the edge is not abnormal,
2012 insert there. Except for the entry block.
2013 Don't do this if the predecessor ends in a jump other than
2014 unconditional simple jump. E.g. for asm goto that points all
2015 its labels at the fallthru basic block, we can't insert instructions
2016 before the asm goto, as the asm goto can have various of side effects,
2017 and can't emit instructions after the asm goto, as it must end
2019 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
2020 && single_succ_p (e
->src
)
2021 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2022 && (!JUMP_P (BB_END (e
->src
))
2023 || simplejump_p (BB_END (e
->src
))))
2027 /* It is possible to have a non-simple jump here. Consider a target
2028 where some forms of unconditional jumps clobber a register. This
2029 happens on the fr30 for example.
2031 We know this block has a single successor, so we can just emit
2032 the queued insns before the jump. */
2033 if (JUMP_P (BB_END (bb
)))
2034 before
= BB_END (bb
);
2037 /* We'd better be fallthru, or we've lost track of what's what. */
2038 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
2040 after
= BB_END (bb
);
2044 /* Otherwise we must split the edge. */
2047 bb
= split_edge (e
);
2049 /* If E crossed a partition boundary, we needed to make bb end in
2050 a region-crossing jump, even though it was originally fallthru. */
2051 if (JUMP_P (BB_END (bb
)))
2052 before
= BB_END (bb
);
2054 after
= BB_END (bb
);
2057 /* Now that we've found the spot, do the insertion. */
2060 emit_insn_before_noloc (insns
, before
, bb
);
2061 last
= prev_nonnote_insn (before
);
2064 last
= emit_insn_after_noloc (insns
, after
, bb
);
2066 if (returnjump_p (last
))
2068 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2069 This is not currently a problem because this only happens
2070 for the (single) epilogue, which already has a fallthru edge
2073 e
= single_succ_edge (bb
);
2074 gcc_assert (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2075 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
2077 e
->flags
&= ~EDGE_FALLTHRU
;
2078 emit_barrier_after (last
);
2081 delete_insn (before
);
2084 gcc_assert (!JUMP_P (last
));
2087 /* Update the CFG for all queued instructions. */
2090 commit_edge_insertions (void)
2094 /* Optimization passes that invoke this routine can cause hot blocks
2095 previously reached by both hot and cold blocks to become dominated only
2096 by cold blocks. This will cause the verification below to fail,
2097 and lead to now cold code in the hot section. In some cases this
2098 may only be visible after newly unreachable blocks are deleted,
2099 which will be done by fixup_partitions. */
2100 fixup_partitions ();
2102 checking_verify_flow_info ();
2104 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
2105 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
2110 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2112 commit_one_edge_insertion (e
);
2117 /* Print out RTL-specific basic block information (live information
2118 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2119 documented in dumpfile.h. */
2122 rtl_dump_bb (FILE *outf
, basic_block bb
, int indent
, dump_flags_t flags
)
2126 s_indent
= (char *) alloca ((size_t) indent
+ 1);
2127 memset (s_indent
, ' ', (size_t) indent
);
2128 s_indent
[indent
] = '\0';
2130 if (df
&& (flags
& TDF_DETAILS
))
2132 df_dump_top (bb
, outf
);
2136 if (bb
->index
!= ENTRY_BLOCK
&& bb
->index
!= EXIT_BLOCK
)
2138 rtx_insn
*last
= BB_END (bb
);
2140 last
= NEXT_INSN (last
);
2141 for (rtx_insn
*insn
= BB_HEAD (bb
); insn
!= last
; insn
= NEXT_INSN (insn
))
2143 if (flags
& TDF_DETAILS
)
2144 df_dump_insn_top (insn
, outf
);
2145 if (! (flags
& TDF_SLIM
))
2146 print_rtl_single (outf
, insn
);
2148 dump_insn_slim (outf
, insn
);
2149 if (flags
& TDF_DETAILS
)
2150 df_dump_insn_bottom (insn
, outf
);
2154 if (df
&& (flags
& TDF_DETAILS
))
2156 df_dump_bottom (bb
, outf
);
2162 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2163 for the start of each basic block. FLAGS are the TDF_* masks documented
2167 print_rtl_with_bb (FILE *outf
, const rtx_insn
*rtx_first
, dump_flags_t flags
)
2169 const rtx_insn
*tmp_rtx
;
2171 fprintf (outf
, "(nil)\n");
2174 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
2175 int max_uid
= get_max_uid ();
2176 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
2177 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
2178 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
2181 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2182 insns, but the CFG is not maintained so the basic block info
2183 is not reliable. Therefore it's omitted from the dumps. */
2184 if (! (cfun
->curr_properties
& PROP_cfg
))
2185 flags
&= ~TDF_BLOCKS
;
2188 df_dump_start (outf
);
2190 if (flags
& TDF_BLOCKS
)
2192 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2196 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
2197 end
[INSN_UID (BB_END (bb
))] = bb
;
2198 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
2200 enum bb_state state
= IN_MULTIPLE_BB
;
2202 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
2204 in_bb_p
[INSN_UID (x
)] = state
;
2206 if (x
== BB_END (bb
))
2212 for (tmp_rtx
= rtx_first
; tmp_rtx
!= NULL
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
2214 if (flags
& TDF_BLOCKS
)
2216 bb
= start
[INSN_UID (tmp_rtx
)];
2219 dump_bb_info (outf
, bb
, 0, dump_flags
, true, false);
2220 if (df
&& (flags
& TDF_DETAILS
))
2221 df_dump_top (bb
, outf
);
2224 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
2225 && !NOTE_P (tmp_rtx
)
2226 && !BARRIER_P (tmp_rtx
))
2227 fprintf (outf
, ";; Insn is not within a basic block\n");
2228 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
2229 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
2232 if (flags
& TDF_DETAILS
)
2233 df_dump_insn_top (tmp_rtx
, outf
);
2234 if (! (flags
& TDF_SLIM
))
2235 print_rtl_single (outf
, tmp_rtx
);
2237 dump_insn_slim (outf
, tmp_rtx
);
2238 if (flags
& TDF_DETAILS
)
2239 df_dump_insn_bottom (tmp_rtx
, outf
);
2241 if (flags
& TDF_BLOCKS
)
2243 bb
= end
[INSN_UID (tmp_rtx
)];
2246 dump_bb_info (outf
, bb
, 0, dump_flags
, false, true);
2247 if (df
&& (flags
& TDF_DETAILS
))
2248 df_dump_bottom (bb
, outf
);
2260 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2263 update_br_prob_note (basic_block bb
)
2266 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
2267 if (!JUMP_P (BB_END (bb
)) || !BRANCH_EDGE (bb
)->probability
.initialized_p ())
2271 rtx
*note_link
, this_rtx
;
2273 note_link
= ®_NOTES (BB_END (bb
));
2274 for (this_rtx
= *note_link
; this_rtx
; this_rtx
= XEXP (this_rtx
, 1))
2275 if (this_rtx
== note
)
2277 *note_link
= XEXP (this_rtx
, 1);
2284 || XINT (note
, 0) == BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ())
2286 XINT (note
, 0) = BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ();
2289 /* Get the last insn associated with block BB (that includes barriers and
2290 tablejumps after BB). */
2292 get_last_bb_insn (basic_block bb
)
2294 rtx_jump_table_data
*table
;
2296 rtx_insn
*end
= BB_END (bb
);
2298 /* Include any jump table following the basic block. */
2299 if (tablejump_p (end
, NULL
, &table
))
2302 /* Include any barriers that may follow the basic block. */
2303 tmp
= next_nonnote_nondebug_insn_bb (end
);
2304 while (tmp
&& BARRIER_P (tmp
))
2307 tmp
= next_nonnote_nondebug_insn_bb (end
);
2313 /* Add all BBs reachable from entry via hot paths into the SET. */
2316 find_bbs_reachable_by_hot_paths (hash_set
<basic_block
> *set
)
2318 auto_vec
<basic_block
, 64> worklist
;
2320 set
->add (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
2321 worklist
.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
2323 while (worklist
.length () > 0)
2325 basic_block bb
= worklist
.pop ();
2329 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2330 if (BB_PARTITION (e
->dest
) != BB_COLD_PARTITION
2331 && !set
->add (e
->dest
))
2332 worklist
.safe_push (e
->dest
);
2336 /* Sanity check partition hotness to ensure that basic blocks in
2337 Â the cold partition don't dominate basic blocks in the hot partition.
2338 If FLAG_ONLY is true, report violations as errors. Otherwise
2339 re-mark the dominated blocks as cold, since this is run after
2340 cfg optimizations that may make hot blocks previously reached
2341 by both hot and cold blocks now only reachable along cold paths. */
2343 static vec
<basic_block
>
2344 find_partition_fixes (bool flag_only
)
2347 vec
<basic_block
> bbs_in_cold_partition
= vNULL
;
2348 vec
<basic_block
> bbs_to_fix
= vNULL
;
2349 hash_set
<basic_block
> set
;
2351 /* Callers check this. */
2352 gcc_checking_assert (crtl
->has_bb_partition
);
2354 find_bbs_reachable_by_hot_paths (&set
);
2356 FOR_EACH_BB_FN (bb
, cfun
)
2357 if (!set
.contains (bb
)
2358 && BB_PARTITION (bb
) != BB_COLD_PARTITION
)
2361 error ("non-cold basic block %d reachable only "
2362 "by paths crossing the cold partition", bb
->index
);
2364 BB_SET_PARTITION (bb
, BB_COLD_PARTITION
);
2365 bbs_to_fix
.safe_push (bb
);
2366 bbs_in_cold_partition
.safe_push (bb
);
2372 /* Perform cleanup on the hot/cold bb partitioning after optimization
2373 passes that modify the cfg. */
2376 fixup_partitions (void)
2380 if (!crtl
->has_bb_partition
)
2383 /* Delete any blocks that became unreachable and weren't
2384 already cleaned up, for example during edge forwarding
2385 and convert_jumps_to_returns. This will expose more
2386 opportunities for fixing the partition boundaries here.
2387 Also, the calculation of the dominance graph during verification
2388 will assert if there are unreachable nodes. */
2389 delete_unreachable_blocks ();
2391 /* If there are partitions, do a sanity check on them: A basic block in
2392 Â a cold partition cannot dominate a basic block in a hot partition.
2393 Fixup any that now violate this requirement, as a result of edge
2394 forwarding and unreachable block deletion. Â */
2395 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (false);
2397 /* Do the partition fixup after all necessary blocks have been converted to
2398 cold, so that we only update the region crossings the minimum number of
2399 places, which can require forcing edges to be non fallthru. */
2400 while (! bbs_to_fix
.is_empty ())
2402 bb
= bbs_to_fix
.pop ();
2403 fixup_new_cold_bb (bb
);
2407 /* Verify, in the basic block chain, that there is at most one switch
2408 between hot/cold partitions. This condition will not be true until
2409 after reorder_basic_blocks is called. */
2412 verify_hot_cold_block_grouping (void)
2416 bool switched_sections
= false;
2417 int current_partition
= BB_UNPARTITIONED
;
2419 /* Even after bb reordering is complete, we go into cfglayout mode
2420 again (in compgoto). Ensure we don't call this before going back
2421 into linearized RTL when any layout fixes would have been committed. */
2422 if (!crtl
->bb_reorder_complete
2423 || current_ir_type () != IR_RTL_CFGRTL
)
2426 FOR_EACH_BB_FN (bb
, cfun
)
2428 if (current_partition
!= BB_UNPARTITIONED
2429 && BB_PARTITION (bb
) != current_partition
)
2431 if (switched_sections
)
2433 error ("multiple hot/cold transitions found (bb %i)",
2438 switched_sections
= true;
2440 if (!crtl
->has_bb_partition
)
2441 error ("partition found but function partition flag not set");
2443 current_partition
= BB_PARTITION (bb
);
2450 /* Perform several checks on the edges out of each block, such as
2451 the consistency of the branch probabilities, the correctness
2452 of hot/cold partition crossing edges, and the number of expected
2453 successor edges. Also verify that the dominance relationship
2454 between hot/cold blocks is sane. */
2457 rtl_verify_edges (void)
2462 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2464 int n_fallthru
= 0, n_branch
= 0, n_abnormal_call
= 0, n_sibcall
= 0;
2465 int n_eh
= 0, n_abnormal
= 0;
2466 edge e
, fallthru
= NULL
;
2469 bool has_crossing_edge
= false;
2471 if (JUMP_P (BB_END (bb
))
2472 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
2473 && EDGE_COUNT (bb
->succs
) >= 2
2474 && any_condjump_p (BB_END (bb
)))
2476 if (!BRANCH_EDGE (bb
)->probability
.initialized_p ())
2478 if (profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2480 error ("verify_flow_info: "
2481 "REG_BR_PROB is set but cfg probability is not");
2485 else if (XINT (note
, 0)
2486 != BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ()
2487 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2489 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2491 BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ());
2496 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2500 if (e
->flags
& EDGE_FALLTHRU
)
2501 n_fallthru
++, fallthru
= e
;
2503 is_crossing
= (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
2504 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2505 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
2506 has_crossing_edge
|= is_crossing
;
2507 if (e
->flags
& EDGE_CROSSING
)
2511 error ("EDGE_CROSSING incorrectly set across same section");
2514 if (e
->flags
& EDGE_FALLTHRU
)
2516 error ("fallthru edge crosses section boundary in bb %i",
2520 if (e
->flags
& EDGE_EH
)
2522 error ("EH edge crosses section boundary in bb %i",
2526 if (JUMP_P (BB_END (bb
)) && !CROSSING_JUMP_P (BB_END (bb
)))
2528 error ("No region crossing jump at section boundary in bb %i",
2533 else if (is_crossing
)
2535 error ("EDGE_CROSSING missing across section boundary");
2539 if ((e
->flags
& ~(EDGE_DFS_BACK
2541 | EDGE_IRREDUCIBLE_LOOP
2544 | EDGE_PRESERVE
)) == 0)
2547 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2550 if (e
->flags
& EDGE_SIBCALL
)
2553 if (e
->flags
& EDGE_EH
)
2556 if (e
->flags
& EDGE_ABNORMAL
)
2560 if (!has_crossing_edge
2561 && JUMP_P (BB_END (bb
))
2562 && CROSSING_JUMP_P (BB_END (bb
)))
2564 print_rtl_with_bb (stderr
, get_insns (), TDF_BLOCKS
| TDF_DETAILS
);
2565 error ("Region crossing jump across same section in bb %i",
2570 if (n_eh
&& !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
2572 error ("missing REG_EH_REGION note at the end of bb %i", bb
->index
);
2577 error ("too many exception handling edges in bb %i", bb
->index
);
2581 && (!JUMP_P (BB_END (bb
))
2582 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
2583 || any_condjump_p (BB_END (bb
))))))
2585 error ("too many outgoing branch edges from bb %i", bb
->index
);
2588 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
2590 error ("fallthru edge after unconditional jump in bb %i", bb
->index
);
2593 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
2595 error ("wrong number of branch edges after unconditional jump"
2596 " in bb %i", bb
->index
);
2599 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
2600 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
2602 error ("wrong amount of branch edges after conditional jump"
2603 " in bb %i", bb
->index
);
2606 if (n_abnormal_call
&& !CALL_P (BB_END (bb
)))
2608 error ("abnormal call edges for non-call insn in bb %i", bb
->index
);
2611 if (n_sibcall
&& !CALL_P (BB_END (bb
)))
2613 error ("sibcall edges for non-call insn in bb %i", bb
->index
);
2616 if (n_abnormal
> n_eh
2617 && !(CALL_P (BB_END (bb
))
2618 && n_abnormal
== n_abnormal_call
+ n_sibcall
)
2619 && (!JUMP_P (BB_END (bb
))
2620 || any_condjump_p (BB_END (bb
))
2621 || any_uncondjump_p (BB_END (bb
))))
2623 error ("abnormal edges for no purpose in bb %i", bb
->index
);
2628 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2631 has_eh
= (e
->flags
& EDGE_EH
);
2632 if ((e
->flags
& EDGE_EH
) == has_eh
)
2634 error ("EH incoming edge mixed with non-EH incoming edges "
2635 "in bb %i", bb
->index
);
2641 /* If there are partitions, do a sanity check on them: A basic block in
2642 Â a cold partition cannot dominate a basic block in a hot partition. Â */
2643 if (crtl
->has_bb_partition
&& !err
2644 && current_ir_type () == IR_RTL_CFGLAYOUT
)
2646 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (true);
2647 err
= !bbs_to_fix
.is_empty ();
2654 /* Checks on the instructions within blocks. Currently checks that each
2655 block starts with a basic block note, and that basic block notes and
2656 control flow jumps are not found in the middle of the block. */
2659 rtl_verify_bb_insns (void)
2665 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2667 /* Now check the header of basic
2668 block. It ought to contain optional CODE_LABEL followed
2669 by NOTE_BASIC_BLOCK. */
2673 if (BB_END (bb
) == x
)
2675 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2683 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2685 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2690 if (BB_END (bb
) == x
)
2691 /* Do checks for empty blocks here. */
2694 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2696 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2698 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2699 INSN_UID (x
), bb
->index
);
2703 if (x
== BB_END (bb
))
2706 if (control_flow_insn_p (x
))
2708 error ("in basic block %d:", bb
->index
);
2709 fatal_insn ("flow control insn inside a basic block", x
);
2718 /* Verify that block pointers for instructions in basic blocks, headers and
2719 footers are set appropriately. */
2722 rtl_verify_bb_pointers (void)
2727 /* Check the general integrity of the basic blocks. */
2728 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2732 if (!(bb
->flags
& BB_RTL
))
2734 error ("BB_RTL flag not set for block %d", bb
->index
);
2738 FOR_BB_INSNS (bb
, insn
)
2739 if (BLOCK_FOR_INSN (insn
) != bb
)
2741 error ("insn %d basic block pointer is %d, should be %d",
2743 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
2748 for (insn
= BB_HEADER (bb
); insn
; insn
= NEXT_INSN (insn
))
2749 if (!BARRIER_P (insn
)
2750 && BLOCK_FOR_INSN (insn
) != NULL
)
2752 error ("insn %d in header of bb %d has non-NULL basic block",
2753 INSN_UID (insn
), bb
->index
);
2756 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
2757 if (!BARRIER_P (insn
)
2758 && BLOCK_FOR_INSN (insn
) != NULL
)
2760 error ("insn %d in footer of bb %d has non-NULL basic block",
2761 INSN_UID (insn
), bb
->index
);
2770 /* Verify the CFG and RTL consistency common for both underlying RTL and
2773 Currently it does following checks:
2775 - overlapping of basic blocks
2776 - insns with wrong BLOCK_FOR_INSN pointers
2777 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2778 - tails of basic blocks (ensure that boundary is necessary)
2779 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2780 and NOTE_INSN_BASIC_BLOCK
2781 - verify that no fall_thru edge crosses hot/cold partition boundaries
2782 - verify that there are no pending RTL branch predictions
2783 - verify that hot blocks are not dominated by cold blocks
2785 In future it can be extended check a lot of other stuff as well
2786 (reachability of basic blocks, life information, etc. etc.). */
2789 rtl_verify_flow_info_1 (void)
2793 err
|= rtl_verify_bb_pointers ();
2795 err
|= rtl_verify_bb_insns ();
2797 err
|= rtl_verify_edges ();
2802 /* Walk the instruction chain and verify that bb head/end pointers
2803 are correct, and that instructions are in exactly one bb and have
2804 correct block pointers. */
2807 rtl_verify_bb_insn_chain (void)
2812 rtx_insn
*last_head
= get_last_insn ();
2813 basic_block
*bb_info
;
2814 const int max_uid
= get_max_uid ();
2816 bb_info
= XCNEWVEC (basic_block
, max_uid
);
2818 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2820 rtx_insn
*head
= BB_HEAD (bb
);
2821 rtx_insn
*end
= BB_END (bb
);
2823 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2825 /* Verify the end of the basic block is in the INSN chain. */
2829 /* And that the code outside of basic blocks has NULL bb field. */
2831 && BLOCK_FOR_INSN (x
) != NULL
)
2833 error ("insn %d outside of basic blocks has non-NULL bb field",
2841 error ("end insn %d for block %d not found in the insn stream",
2842 INSN_UID (end
), bb
->index
);
2846 /* Work backwards from the end to the head of the basic block
2847 to verify the head is in the RTL chain. */
2848 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2850 /* While walking over the insn chain, verify insns appear
2851 in only one basic block. */
2852 if (bb_info
[INSN_UID (x
)] != NULL
)
2854 error ("insn %d is in multiple basic blocks (%d and %d)",
2855 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2859 bb_info
[INSN_UID (x
)] = bb
;
2866 error ("head insn %d for block %d not found in the insn stream",
2867 INSN_UID (head
), bb
->index
);
2871 last_head
= PREV_INSN (x
);
2874 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2876 /* Check that the code before the first basic block has NULL
2879 && BLOCK_FOR_INSN (x
) != NULL
)
2881 error ("insn %d outside of basic blocks has non-NULL bb field",
2891 /* Verify that fallthru edges point to adjacent blocks in layout order and
2892 that barriers exist after non-fallthru blocks. */
2895 rtl_verify_fallthru (void)
2900 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2904 e
= find_fallthru_edge (bb
->succs
);
2909 /* Ensure existence of barrier in BB with no fallthru edges. */
2910 for (insn
= NEXT_INSN (BB_END (bb
)); ; insn
= NEXT_INSN (insn
))
2912 if (!insn
|| NOTE_INSN_BASIC_BLOCK_P (insn
))
2914 error ("missing barrier after block %i", bb
->index
);
2918 if (BARRIER_P (insn
))
2922 else if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2923 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2927 if (e
->src
->next_bb
!= e
->dest
)
2930 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2931 e
->src
->index
, e
->dest
->index
);
2935 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
2936 insn
= NEXT_INSN (insn
))
2937 if (BARRIER_P (insn
) || NONDEBUG_INSN_P (insn
))
2939 error ("verify_flow_info: Incorrect fallthru %i->%i",
2940 e
->src
->index
, e
->dest
->index
);
2941 fatal_insn ("wrong insn in the fallthru edge", insn
);
2950 /* Verify that blocks are laid out in consecutive order. While walking the
2951 instructions, verify that all expected instructions are inside the basic
2952 blocks, and that all returns are followed by barriers. */
2955 rtl_verify_bb_layout (void)
2961 rtx_insn
* const rtx_first
= get_insns ();
2962 basic_block last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
), curr_bb
= NULL
;
2965 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
2967 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2969 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2971 bb
= NOTE_BASIC_BLOCK (x
);
2974 if (bb
!= last_bb_seen
->next_bb
)
2975 internal_error ("basic blocks not laid down consecutively");
2977 curr_bb
= last_bb_seen
= bb
;
2982 switch (GET_CODE (x
))
2989 /* An ADDR_VEC is placed outside any basic block. */
2991 && JUMP_TABLE_DATA_P (NEXT_INSN (x
)))
2994 /* But in any case, non-deletable labels can appear anywhere. */
2998 fatal_insn ("insn outside basic block", x
);
3003 && returnjump_p (x
) && ! condjump_p (x
)
3004 && ! ((y
= next_nonnote_nondebug_insn (x
))
3006 fatal_insn ("return not followed by barrier", x
);
3008 if (curr_bb
&& x
== BB_END (curr_bb
))
3012 if (num_bb_notes
!= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
)
3014 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
3015 num_bb_notes
, n_basic_blocks_for_fn (cfun
));
3020 /* Verify the CFG and RTL consistency common for both underlying RTL and
3021 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
3023 Currently it does following checks:
3024 - all checks of rtl_verify_flow_info_1
3025 - test head/end pointers
3026 - check that blocks are laid out in consecutive order
3027 - check that all insns are in the basic blocks
3028 (except the switch handling code, barriers and notes)
3029 - check that all returns are followed by barriers
3030 - check that all fallthru edge points to the adjacent blocks
3031 - verify that there is a single hot/cold partition boundary after bbro */
3034 rtl_verify_flow_info (void)
3038 err
|= rtl_verify_flow_info_1 ();
3040 err
|= rtl_verify_bb_insn_chain ();
3042 err
|= rtl_verify_fallthru ();
3044 err
|= rtl_verify_bb_layout ();
3046 err
|= verify_hot_cold_block_grouping ();
3051 /* Assume that the preceding pass has possibly eliminated jump instructions
3052 or converted the unconditional jumps. Eliminate the edges from CFG.
3053 Return true if any edges are eliminated. */
3056 purge_dead_edges (basic_block bb
)
3059 rtx_insn
*insn
= BB_END (bb
);
3061 bool purged
= false;
3065 if (DEBUG_INSN_P (insn
) && insn
!= BB_HEAD (bb
))
3067 insn
= PREV_INSN (insn
);
3068 while ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
));
3070 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3071 if (NONJUMP_INSN_P (insn
)
3072 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
3076 if (! may_trap_p (PATTERN (insn
))
3077 || ((eqnote
= find_reg_equal_equiv_note (insn
))
3078 && ! may_trap_p (XEXP (eqnote
, 0))))
3079 remove_note (insn
, note
);
3082 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3083 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3085 bool remove
= false;
3087 /* There are three types of edges we need to handle correctly here: EH
3088 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3089 latter can appear when nonlocal gotos are used. */
3090 if (e
->flags
& EDGE_ABNORMAL_CALL
)
3094 else if (can_nonlocal_goto (insn
))
3096 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3098 else if (flag_tm
&& find_reg_note (insn
, REG_TM
, NULL
))
3103 else if (e
->flags
& EDGE_EH
)
3104 remove
= !can_throw_internal (insn
);
3109 df_set_bb_dirty (bb
);
3122 /* We do care only about conditional jumps and simplejumps. */
3123 if (!any_condjump_p (insn
)
3124 && !returnjump_p (insn
)
3125 && !simplejump_p (insn
))
3128 /* Branch probability/prediction notes are defined only for
3129 condjumps. We've possibly turned condjump into simplejump. */
3130 if (simplejump_p (insn
))
3132 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3134 remove_note (insn
, note
);
3135 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
3136 remove_note (insn
, note
);
3139 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3141 /* Avoid abnormal flags to leak from computed jumps turned
3142 into simplejumps. */
3144 e
->flags
&= ~EDGE_ABNORMAL
;
3146 /* See if this edge is one we should keep. */
3147 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
3148 /* A conditional jump can fall through into the next
3149 block, so we should keep the edge. */
3154 else if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3155 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
3156 /* If the destination block is the target of the jump,
3162 else if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
3163 && returnjump_p (insn
))
3164 /* If the destination block is the exit block, and this
3165 instruction is a return, then keep the edge. */
3170 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3171 /* Keep the edges that correspond to exceptions thrown by
3172 this instruction and rematerialize the EDGE_ABNORMAL
3173 flag we just cleared above. */
3175 e
->flags
|= EDGE_ABNORMAL
;
3180 /* We do not need this edge. */
3181 df_set_bb_dirty (bb
);
3186 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
3190 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
3195 /* Redistribute probabilities. */
3196 if (single_succ_p (bb
))
3198 single_succ_edge (bb
)->probability
= profile_probability::always ();
3202 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3206 b
= BRANCH_EDGE (bb
);
3207 f
= FALLTHRU_EDGE (bb
);
3208 b
->probability
= profile_probability::from_reg_br_prob_note
3210 f
->probability
= b
->probability
.invert ();
3215 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
3217 /* First, there should not be any EH or ABCALL edges resulting
3218 from non-local gotos and the like. If there were, we shouldn't
3219 have created the sibcall in the first place. Second, there
3220 should of course never have been a fallthru edge. */
3221 gcc_assert (single_succ_p (bb
));
3222 gcc_assert (single_succ_edge (bb
)->flags
3223 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
3228 /* If we don't see a jump insn, we don't know exactly why the block would
3229 have been broken at this point. Look for a simple, non-fallthru edge,
3230 as these are only created by conditional branches. If we find such an
3231 edge we know that there used to be a jump here and can then safely
3232 remove all non-fallthru edges. */
3234 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3235 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
3244 /* Remove all but the fake and fallthru edges. The fake edge may be
3245 the only successor for this block in the case of noreturn
3247 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3249 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
3251 df_set_bb_dirty (bb
);
3259 gcc_assert (single_succ_p (bb
));
3261 single_succ_edge (bb
)->probability
= profile_probability::always ();
3264 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
3269 /* Search all basic blocks for potentially dead edges and purge them. Return
3270 true if some edge has been eliminated. */
3273 purge_all_dead_edges (void)
3278 FOR_EACH_BB_FN (bb
, cfun
)
3280 bool purged_here
= purge_dead_edges (bb
);
3282 purged
|= purged_here
;
3288 /* This is used by a few passes that emit some instructions after abnormal
3289 calls, moving the basic block's end, while they in fact do want to emit
3290 them on the fallthru edge. Look for abnormal call edges, find backward
3291 the call in the block and insert the instructions on the edge instead.
3293 Similarly, handle instructions throwing exceptions internally.
3295 Return true when instructions have been found and inserted on edges. */
3298 fixup_abnormal_edges (void)
3300 bool inserted
= false;
3303 FOR_EACH_BB_FN (bb
, cfun
)
3308 /* Look for cases we are interested in - calls or instructions causing
3310 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3311 if ((e
->flags
& EDGE_ABNORMAL_CALL
)
3312 || ((e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
3313 == (EDGE_ABNORMAL
| EDGE_EH
)))
3316 if (e
&& !CALL_P (BB_END (bb
)) && !can_throw_internal (BB_END (bb
)))
3320 /* Get past the new insns generated. Allow notes, as the insns
3321 may be already deleted. */
3323 while ((NONJUMP_INSN_P (insn
) || NOTE_P (insn
))
3324 && !can_throw_internal (insn
)
3325 && insn
!= BB_HEAD (bb
))
3326 insn
= PREV_INSN (insn
);
3328 if (CALL_P (insn
) || can_throw_internal (insn
))
3330 rtx_insn
*stop
, *next
;
3332 e
= find_fallthru_edge (bb
->succs
);
3334 stop
= NEXT_INSN (BB_END (bb
));
3337 for (insn
= NEXT_INSN (insn
); insn
!= stop
; insn
= next
)
3339 next
= NEXT_INSN (insn
);
3344 /* Sometimes there's still the return value USE.
3345 If it's placed after a trapping call (i.e. that
3346 call is the last insn anyway), we have no fallthru
3347 edge. Simply delete this use and don't try to insert
3348 on the non-existent edge.
3349 Similarly, sometimes a call that can throw is
3350 followed in the source with __builtin_unreachable (),
3351 meaning that there is UB if the call returns rather
3352 than throws. If there weren't any instructions
3353 following such calls before, supposedly even the ones
3354 we've deleted aren't significant and can be
3358 /* We're not deleting it, we're moving it. */
3359 insn
->set_undeleted ();
3360 SET_PREV_INSN (insn
) = NULL_RTX
;
3361 SET_NEXT_INSN (insn
) = NULL_RTX
;
3363 insert_insn_on_edge (insn
, e
);
3367 else if (!BARRIER_P (insn
))
3368 set_block_for_insn (insn
, NULL
);
3372 /* It may be that we don't find any trapping insn. In this
3373 case we discovered quite late that the insn that had been
3374 marked as can_throw_internal in fact couldn't trap at all.
3375 So we should in fact delete the EH edges out of the block. */
3377 purge_dead_edges (bb
);
3384 /* Cut the insns from FIRST to LAST out of the insns stream. */
3387 unlink_insn_chain (rtx_insn
*first
, rtx_insn
*last
)
3389 rtx_insn
*prevfirst
= PREV_INSN (first
);
3390 rtx_insn
*nextlast
= NEXT_INSN (last
);
3392 SET_PREV_INSN (first
) = NULL
;
3393 SET_NEXT_INSN (last
) = NULL
;
3395 SET_NEXT_INSN (prevfirst
) = nextlast
;
3397 SET_PREV_INSN (nextlast
) = prevfirst
;
3399 set_last_insn (prevfirst
);
3401 set_first_insn (nextlast
);
3405 /* Skip over inter-block insns occurring after BB which are typically
3406 associated with BB (e.g., barriers). If there are any such insns,
3407 we return the last one. Otherwise, we return the end of BB. */
3410 skip_insns_after_block (basic_block bb
)
3412 rtx_insn
*insn
, *last_insn
, *next_head
, *prev
;
3415 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3416 next_head
= BB_HEAD (bb
->next_bb
);
3418 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
3420 if (insn
== next_head
)
3423 switch (GET_CODE (insn
))
3430 switch (NOTE_KIND (insn
))
3432 case NOTE_INSN_BLOCK_END
:
3442 if (NEXT_INSN (insn
)
3443 && JUMP_TABLE_DATA_P (NEXT_INSN (insn
)))
3445 insn
= NEXT_INSN (insn
);
3458 /* It is possible to hit contradictory sequence. For instance:
3464 Where barrier belongs to jump_insn, but the note does not. This can be
3465 created by removing the basic block originally following
3466 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3468 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
3470 prev
= PREV_INSN (insn
);
3472 switch (NOTE_KIND (insn
))
3474 case NOTE_INSN_BLOCK_END
:
3477 case NOTE_INSN_DELETED
:
3478 case NOTE_INSN_DELETED_LABEL
:
3479 case NOTE_INSN_DELETED_DEBUG_LABEL
:
3482 reorder_insns (insn
, insn
, last_insn
);
3489 /* Locate or create a label for a given basic block. */
3492 label_for_bb (basic_block bb
)
3494 rtx_insn
*label
= BB_HEAD (bb
);
3496 if (!LABEL_P (label
))
3499 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
3501 label
= block_label (bb
);
3507 /* Locate the effective beginning and end of the insn chain for each
3508 block, as defined by skip_insns_after_block above. */
3511 record_effective_endpoints (void)
3513 rtx_insn
*next_insn
;
3517 for (insn
= get_insns ();
3520 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
;
3521 insn
= NEXT_INSN (insn
))
3523 /* No basic blocks at all? */
3526 if (PREV_INSN (insn
))
3527 cfg_layout_function_header
=
3528 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
3530 cfg_layout_function_header
= NULL
;
3532 next_insn
= get_insns ();
3533 FOR_EACH_BB_FN (bb
, cfun
)
3537 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
3538 BB_HEADER (bb
) = unlink_insn_chain (next_insn
,
3539 PREV_INSN (BB_HEAD (bb
)));
3540 end
= skip_insns_after_block (bb
);
3541 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
3542 BB_FOOTER (bb
) = unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
3543 next_insn
= NEXT_INSN (BB_END (bb
));
3546 cfg_layout_function_footer
= next_insn
;
3547 if (cfg_layout_function_footer
)
3548 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
3553 const pass_data pass_data_into_cfg_layout_mode
=
3555 RTL_PASS
, /* type */
3556 "into_cfglayout", /* name */
3557 OPTGROUP_NONE
, /* optinfo_flags */
3559 0, /* properties_required */
3560 PROP_cfglayout
, /* properties_provided */
3561 0, /* properties_destroyed */
3562 0, /* todo_flags_start */
3563 0, /* todo_flags_finish */
3566 class pass_into_cfg_layout_mode
: public rtl_opt_pass
3569 pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3570 : rtl_opt_pass (pass_data_into_cfg_layout_mode
, ctxt
)
3573 /* opt_pass methods: */
3574 virtual unsigned int execute (function
*)
3576 cfg_layout_initialize (0);
3580 }; // class pass_into_cfg_layout_mode
3585 make_pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3587 return new pass_into_cfg_layout_mode (ctxt
);
3592 const pass_data pass_data_outof_cfg_layout_mode
=
3594 RTL_PASS
, /* type */
3595 "outof_cfglayout", /* name */
3596 OPTGROUP_NONE
, /* optinfo_flags */
3598 0, /* properties_required */
3599 0, /* properties_provided */
3600 PROP_cfglayout
, /* properties_destroyed */
3601 0, /* todo_flags_start */
3602 0, /* todo_flags_finish */
3605 class pass_outof_cfg_layout_mode
: public rtl_opt_pass
3608 pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3609 : rtl_opt_pass (pass_data_outof_cfg_layout_mode
, ctxt
)
3612 /* opt_pass methods: */
3613 virtual unsigned int execute (function
*);
3615 }; // class pass_outof_cfg_layout_mode
3618 pass_outof_cfg_layout_mode::execute (function
*fun
)
3622 FOR_EACH_BB_FN (bb
, fun
)
3623 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3624 bb
->aux
= bb
->next_bb
;
3626 cfg_layout_finalize ();
3634 make_pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3636 return new pass_outof_cfg_layout_mode (ctxt
);
3640 /* Link the basic blocks in the correct order, compacting the basic
3641 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3642 function also clears the basic block header and footer fields.
3644 This function is usually called after a pass (e.g. tracer) finishes
3645 some transformations while in cfglayout mode. The required sequence
3646 of the basic blocks is in a linked list along the bb->aux field.
3647 This functions re-links the basic block prev_bb and next_bb pointers
3648 accordingly, and it compacts and renumbers the blocks.
3650 FIXME: This currently works only for RTL, but the only RTL-specific
3651 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3652 to GIMPLE a long time ago, but it doesn't relink the basic block
3653 chain. It could do that (to give better initial RTL) if this function
3654 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3657 relink_block_chain (bool stay_in_cfglayout_mode
)
3659 basic_block bb
, prev_bb
;
3662 /* Maybe dump the re-ordered sequence. */
3665 fprintf (dump_file
, "Reordered sequence:\n");
3666 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, index
=
3669 bb
= (basic_block
) bb
->aux
, index
++)
3671 fprintf (dump_file
, " %i ", index
);
3672 if (get_bb_original (bb
))
3673 fprintf (dump_file
, "duplicate of %i ",
3674 get_bb_original (bb
)->index
);
3675 else if (forwarder_block_p (bb
)
3676 && !LABEL_P (BB_HEAD (bb
)))
3677 fprintf (dump_file
, "compensation ");
3679 fprintf (dump_file
, "bb %i ", bb
->index
);
3683 /* Now reorder the blocks. */
3684 prev_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
3685 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
3686 for (; bb
; prev_bb
= bb
, bb
= (basic_block
) bb
->aux
)
3688 bb
->prev_bb
= prev_bb
;
3689 prev_bb
->next_bb
= bb
;
3691 prev_bb
->next_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
3692 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
= prev_bb
;
3694 /* Then, clean up the aux fields. */
3695 FOR_ALL_BB_FN (bb
, cfun
)
3698 if (!stay_in_cfglayout_mode
)
3699 BB_HEADER (bb
) = BB_FOOTER (bb
) = NULL
;
3702 /* Maybe reset the original copy tables, they are not valid anymore
3703 when we renumber the basic blocks in compact_blocks. If we are
3704 are going out of cfglayout mode, don't re-allocate the tables. */
3705 if (original_copy_tables_initialized_p ())
3706 free_original_copy_tables ();
3707 if (stay_in_cfglayout_mode
)
3708 initialize_original_copy_tables ();
3710 /* Finally, put basic_block_info in the new order. */
3715 /* Given a reorder chain, rearrange the code to match. */
3718 fixup_reorder_chain (void)
3721 rtx_insn
*insn
= NULL
;
3723 if (cfg_layout_function_header
)
3725 set_first_insn (cfg_layout_function_header
);
3726 insn
= cfg_layout_function_header
;
3727 while (NEXT_INSN (insn
))
3728 insn
= NEXT_INSN (insn
);
3731 /* First do the bulk reordering -- rechain the blocks without regard to
3732 the needed changes to jumps and labels. */
3734 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3740 SET_NEXT_INSN (insn
) = BB_HEADER (bb
);
3742 set_first_insn (BB_HEADER (bb
));
3743 SET_PREV_INSN (BB_HEADER (bb
)) = insn
;
3744 insn
= BB_HEADER (bb
);
3745 while (NEXT_INSN (insn
))
3746 insn
= NEXT_INSN (insn
);
3749 SET_NEXT_INSN (insn
) = BB_HEAD (bb
);
3751 set_first_insn (BB_HEAD (bb
));
3752 SET_PREV_INSN (BB_HEAD (bb
)) = insn
;
3756 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
3757 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
3758 while (NEXT_INSN (insn
))
3759 insn
= NEXT_INSN (insn
);
3763 SET_NEXT_INSN (insn
) = cfg_layout_function_footer
;
3764 if (cfg_layout_function_footer
)
3765 SET_PREV_INSN (cfg_layout_function_footer
) = insn
;
3767 while (NEXT_INSN (insn
))
3768 insn
= NEXT_INSN (insn
);
3770 set_last_insn (insn
);
3772 verify_insn_chain ();
3774 /* Now add jumps and labels as needed to match the blocks new
3777 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3780 edge e_fall
, e_taken
, e
;
3781 rtx_insn
*bb_end_insn
;
3782 rtx ret_label
= NULL_RTX
;
3786 if (EDGE_COUNT (bb
->succs
) == 0)
3789 /* Find the old fallthru edge, and another non-EH edge for
3791 e_taken
= e_fall
= NULL
;
3793 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3794 if (e
->flags
& EDGE_FALLTHRU
)
3796 else if (! (e
->flags
& EDGE_EH
))
3799 bb_end_insn
= BB_END (bb
);
3800 if (rtx_jump_insn
*bb_end_jump
= dyn_cast
<rtx_jump_insn
*> (bb_end_insn
))
3802 ret_label
= JUMP_LABEL (bb_end_jump
);
3803 if (any_condjump_p (bb_end_jump
))
3805 /* This might happen if the conditional jump has side
3806 effects and could therefore not be optimized away.
3807 Make the basic block to end with a barrier in order
3808 to prevent rtl_verify_flow_info from complaining. */
3811 gcc_assert (!onlyjump_p (bb_end_jump
)
3812 || returnjump_p (bb_end_jump
)
3813 || (e_taken
->flags
& EDGE_CROSSING
));
3814 emit_barrier_after (bb_end_jump
);
3818 /* If the old fallthru is still next, nothing to do. */
3819 if (bb
->aux
== e_fall
->dest
3820 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3823 /* The degenerated case of conditional jump jumping to the next
3824 instruction can happen for jumps with side effects. We need
3825 to construct a forwarder block and this will be done just
3826 fine by force_nonfallthru below. */
3830 /* There is another special case: if *neither* block is next,
3831 such as happens at the very end of a function, then we'll
3832 need to add a new unconditional jump. Choose the taken
3833 edge based on known or assumed probability. */
3834 else if (bb
->aux
!= e_taken
->dest
)
3836 rtx note
= find_reg_note (bb_end_jump
, REG_BR_PROB
, 0);
3839 && profile_probability::from_reg_br_prob_note
3840 (XINT (note
, 0)) < profile_probability::even ()
3841 && invert_jump (bb_end_jump
,
3843 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3845 : label_for_bb (e_fall
->dest
)), 0))
3847 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3848 gcc_checking_assert (could_fall_through
3849 (e_taken
->src
, e_taken
->dest
));
3850 e_taken
->flags
|= EDGE_FALLTHRU
;
3851 update_br_prob_note (bb
);
3852 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
3856 /* If the "jumping" edge is a crossing edge, and the fall
3857 through edge is non-crossing, leave things as they are. */
3858 else if ((e_taken
->flags
& EDGE_CROSSING
)
3859 && !(e_fall
->flags
& EDGE_CROSSING
))
3862 /* Otherwise we can try to invert the jump. This will
3863 basically never fail, however, keep up the pretense. */
3864 else if (invert_jump (bb_end_jump
,
3866 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3868 : label_for_bb (e_fall
->dest
)), 0))
3870 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3871 gcc_checking_assert (could_fall_through
3872 (e_taken
->src
, e_taken
->dest
));
3873 e_taken
->flags
|= EDGE_FALLTHRU
;
3874 update_br_prob_note (bb
);
3875 if (LABEL_NUSES (ret_label
) == 0
3876 && single_pred_p (e_taken
->dest
))
3877 delete_insn (as_a
<rtx_insn
*> (ret_label
));
3881 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
3883 /* If the old fallthru is still next or if
3884 asm goto doesn't have a fallthru (e.g. when followed by
3885 __builtin_unreachable ()), nothing to do. */
3887 || bb
->aux
== e_fall
->dest
3888 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3891 /* Otherwise we'll have to use the fallthru fixup below. */
3895 /* Otherwise we have some return, switch or computed
3896 jump. In the 99% case, there should not have been a
3898 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
3904 /* No fallthru implies a noreturn function with EH edges, or
3905 something similarly bizarre. In any case, we don't need to
3910 /* If the fallthru block is still next, nothing to do. */
3911 if (bb
->aux
== e_fall
->dest
)
3914 /* A fallthru to exit block. */
3915 if (e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3919 /* We got here if we need to add a new jump insn.
3920 Note force_nonfallthru can delete E_FALL and thus we have to
3921 save E_FALL->src prior to the call to force_nonfallthru. */
3922 nb
= force_nonfallthru_and_redirect (e_fall
, e_fall
->dest
, ret_label
);
3927 /* Don't process this new block. */
3932 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3934 /* Annoying special case - jump around dead jumptables left in the code. */
3935 FOR_EACH_BB_FN (bb
, cfun
)
3937 edge e
= find_fallthru_edge (bb
->succs
);
3939 if (e
&& !can_fallthru (e
->src
, e
->dest
))
3940 force_nonfallthru (e
);
3943 /* Ensure goto_locus from edges has some instructions with that locus in RTL
3944 when not optimizing. */
3945 if (!optimize
&& !DECL_IGNORED_P (current_function_decl
))
3946 FOR_EACH_BB_FN (bb
, cfun
)
3951 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3952 if (LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
3953 && !(e
->flags
& EDGE_ABNORMAL
))
3957 basic_block dest
, nb
;
3960 insn
= BB_END (e
->src
);
3961 end
= PREV_INSN (BB_HEAD (e
->src
));
3963 && (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
3964 insn
= PREV_INSN (insn
);
3966 && INSN_LOCATION (insn
) == e
->goto_locus
)
3968 if (simplejump_p (BB_END (e
->src
))
3969 && !INSN_HAS_LOCATION (BB_END (e
->src
)))
3971 INSN_LOCATION (BB_END (e
->src
)) = e
->goto_locus
;
3975 if (dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3977 /* Non-fallthru edges to the exit block cannot be split. */
3978 if (!(e
->flags
& EDGE_FALLTHRU
))
3983 insn
= BB_HEAD (dest
);
3984 end
= NEXT_INSN (BB_END (dest
));
3985 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
3986 insn
= NEXT_INSN (insn
);
3987 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
3988 && INSN_LOCATION (insn
) == e
->goto_locus
)
3991 nb
= split_edge (e
);
3992 if (!INSN_P (BB_END (nb
)))
3993 BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
3995 INSN_LOCATION (BB_END (nb
)) = e
->goto_locus
;
3997 /* If there are other incoming edges to the destination block
3998 with the same goto locus, redirect them to the new block as
3999 well, this can prevent other such blocks from being created
4000 in subsequent iterations of the loop. */
4001 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
4002 if (LOCATION_LOCUS (e2
->goto_locus
) != UNKNOWN_LOCATION
4003 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
4004 && e
->goto_locus
== e2
->goto_locus
)
4005 redirect_edge_and_branch (e2
, nb
);
4012 /* Perform sanity checks on the insn chain.
4013 1. Check that next/prev pointers are consistent in both the forward and
4015 2. Count insns in chain, going both directions, and check if equal.
4016 3. Check that get_last_insn () returns the actual end of chain. */
4019 verify_insn_chain (void)
4021 rtx_insn
*x
, *prevx
, *nextx
;
4022 int insn_cnt1
, insn_cnt2
;
4024 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
4026 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
4027 gcc_assert (PREV_INSN (x
) == prevx
);
4029 gcc_assert (prevx
== get_last_insn ());
4031 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
4033 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
4034 gcc_assert (NEXT_INSN (x
) == nextx
);
4036 gcc_assert (insn_cnt1
== insn_cnt2
);
4039 /* If we have assembler epilogues, the block falling through to exit must
4040 be the last one in the reordered chain when we reach final. Ensure
4041 that this condition is met. */
4043 fixup_fallthru_exit_predecessor (void)
4046 basic_block bb
= NULL
;
4048 /* This transformation is not valid before reload, because we might
4049 separate a call from the instruction that copies the return
4051 gcc_assert (reload_completed
);
4053 e
= find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4059 basic_block c
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
4061 /* If the very first block is the one with the fall-through exit
4062 edge, we have to split that block. */
4065 bb
= split_block_after_labels (bb
)->dest
;
4068 BB_FOOTER (bb
) = BB_FOOTER (c
);
4069 BB_FOOTER (c
) = NULL
;
4072 while (c
->aux
!= bb
)
4073 c
= (basic_block
) c
->aux
;
4077 c
= (basic_block
) c
->aux
;
4084 /* In case there are more than one fallthru predecessors of exit, force that
4085 there is only one. */
4088 force_one_exit_fallthru (void)
4090 edge e
, predecessor
= NULL
;
4093 basic_block forwarder
, bb
;
4095 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
4096 if (e
->flags
& EDGE_FALLTHRU
)
4098 if (predecessor
== NULL
)
4110 /* Exit has several fallthru predecessors. Create a forwarder block for
4112 forwarder
= split_edge (predecessor
);
4113 for (ei
= ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4114 (e
= ei_safe_edge (ei
)); )
4116 if (e
->src
== forwarder
4117 || !(e
->flags
& EDGE_FALLTHRU
))
4120 redirect_edge_and_branch_force (e
, forwarder
);
4123 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4125 FOR_EACH_BB_FN (bb
, cfun
)
4127 if (bb
->aux
== NULL
&& bb
!= forwarder
)
4129 bb
->aux
= forwarder
;
4135 /* Return true in case it is possible to duplicate the basic block BB. */
4138 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
4140 /* Do not attempt to duplicate tablejumps, as we need to unshare
4141 the dispatch table. This is difficult to do, as the instructions
4142 computing jump destination may be hoisted outside the basic block. */
4143 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
4146 /* Do not duplicate blocks containing insns that can't be copied. */
4147 if (targetm
.cannot_copy_insn_p
)
4149 rtx_insn
*insn
= BB_HEAD (bb
);
4152 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
4154 if (insn
== BB_END (bb
))
4156 insn
= NEXT_INSN (insn
);
4164 duplicate_insn_chain (rtx_insn
*from
, rtx_insn
*to
)
4166 rtx_insn
*insn
, *next
, *copy
;
4169 /* Avoid updating of boundaries of previous basic block. The
4170 note will get removed from insn stream in fixup. */
4171 last
= emit_note (NOTE_INSN_DELETED
);
4173 /* Create copy at the end of INSN chain. The chain will
4174 be reordered later. */
4175 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
4177 switch (GET_CODE (insn
))
4180 /* Don't duplicate label debug insns. */
4181 if (DEBUG_BIND_INSN_P (insn
)
4182 && TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
)
4188 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
4189 if (JUMP_P (insn
) && JUMP_LABEL (insn
) != NULL_RTX
4190 && ANY_RETURN_P (JUMP_LABEL (insn
)))
4191 JUMP_LABEL (copy
) = JUMP_LABEL (insn
);
4192 maybe_copy_prologue_epilogue_insn (insn
, copy
);
4195 case JUMP_TABLE_DATA
:
4196 /* Avoid copying of dispatch tables. We never duplicate
4197 tablejumps, so this can hit only in case the table got
4198 moved far from original jump.
4199 Avoid copying following barrier as well if any
4200 (and debug insns in between). */
4201 for (next
= NEXT_INSN (insn
);
4202 next
!= NEXT_INSN (to
);
4203 next
= NEXT_INSN (next
))
4204 if (!DEBUG_INSN_P (next
))
4206 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
4218 switch (NOTE_KIND (insn
))
4220 /* In case prologue is empty and function contain label
4221 in first BB, we may want to copy the block. */
4222 case NOTE_INSN_PROLOGUE_END
:
4224 case NOTE_INSN_DELETED
:
4225 case NOTE_INSN_DELETED_LABEL
:
4226 case NOTE_INSN_DELETED_DEBUG_LABEL
:
4227 /* No problem to strip these. */
4228 case NOTE_INSN_FUNCTION_BEG
:
4229 /* There is always just single entry to function. */
4230 case NOTE_INSN_BASIC_BLOCK
:
4231 /* We should only switch text sections once. */
4232 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
4235 case NOTE_INSN_EPILOGUE_BEG
:
4236 case NOTE_INSN_UPDATE_SJLJ_CONTEXT
:
4237 emit_note_copy (as_a
<rtx_note
*> (insn
));
4241 /* All other notes should have already been eliminated. */
4249 insn
= NEXT_INSN (last
);
4254 /* Create a duplicate of the basic block BB. */
4257 cfg_layout_duplicate_bb (basic_block bb
, copy_bb_data
*)
4262 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
4263 new_bb
= create_basic_block (insn
,
4264 insn
? get_last_insn () : NULL
,
4265 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
);
4267 BB_COPY_PARTITION (new_bb
, bb
);
4270 insn
= BB_HEADER (bb
);
4271 while (NEXT_INSN (insn
))
4272 insn
= NEXT_INSN (insn
);
4273 insn
= duplicate_insn_chain (BB_HEADER (bb
), insn
);
4275 BB_HEADER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4280 insn
= BB_FOOTER (bb
);
4281 while (NEXT_INSN (insn
))
4282 insn
= NEXT_INSN (insn
);
4283 insn
= duplicate_insn_chain (BB_FOOTER (bb
), insn
);
4285 BB_FOOTER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4292 /* Main entry point to this module - initialize the datastructures for
4293 CFG layout changes. It keeps LOOPS up-to-date if not null.
4295 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4298 cfg_layout_initialize (int flags
)
4303 /* Once bb partitioning is complete, cfg layout mode should not be
4304 re-entered. Entering cfg layout mode may require fixups. As an
4305 example, if edge forwarding performed when optimizing the cfg
4306 layout required moving a block from the hot to the cold
4307 section. This would create an illegal partitioning unless some
4308 manual fixup was performed. */
4309 gcc_assert (!crtl
->bb_reorder_complete
|| !crtl
->has_bb_partition
);
4311 initialize_original_copy_tables ();
4313 cfg_layout_rtl_register_cfg_hooks ();
4315 record_effective_endpoints ();
4317 /* Make sure that the targets of non local gotos are marked. */
4318 for (x
= nonlocal_goto_handler_labels
; x
; x
= x
->next ())
4320 bb
= BLOCK_FOR_INSN (x
->insn ());
4321 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
4324 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
4327 /* Splits superblocks. */
4329 break_superblocks (void)
4334 auto_sbitmap
superblocks (last_basic_block_for_fn (cfun
));
4335 bitmap_clear (superblocks
);
4337 FOR_EACH_BB_FN (bb
, cfun
)
4338 if (bb
->flags
& BB_SUPERBLOCK
)
4340 bb
->flags
&= ~BB_SUPERBLOCK
;
4341 bitmap_set_bit (superblocks
, bb
->index
);
4347 rebuild_jump_labels (get_insns ());
4348 find_many_sub_basic_blocks (superblocks
);
4352 /* Finalize the changes: reorder insn list according to the sequence specified
4353 by aux pointers, enter compensation code, rebuild scope forest. */
4356 cfg_layout_finalize (void)
4358 free_dominance_info (CDI_DOMINATORS
);
4359 force_one_exit_fallthru ();
4360 rtl_register_cfg_hooks ();
4361 if (reload_completed
&& !targetm
.have_epilogue ())
4362 fixup_fallthru_exit_predecessor ();
4363 fixup_reorder_chain ();
4365 rebuild_jump_labels (get_insns ());
4366 delete_dead_jumptables ();
4369 verify_insn_chain ();
4370 checking_verify_flow_info ();
4374 /* Same as split_block but update cfg_layout structures. */
4377 cfg_layout_split_block (basic_block bb
, void *insnp
)
4379 rtx insn
= (rtx
) insnp
;
4380 basic_block new_bb
= rtl_split_block (bb
, insn
);
4382 BB_FOOTER (new_bb
) = BB_FOOTER (bb
);
4383 BB_FOOTER (bb
) = NULL
;
4388 /* Redirect Edge to DEST. */
4390 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
4392 basic_block src
= e
->src
;
4395 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4398 if (e
->dest
== dest
)
4401 if (e
->flags
& EDGE_CROSSING
4402 && BB_PARTITION (e
->src
) == BB_PARTITION (dest
)
4403 && simplejump_p (BB_END (src
)))
4407 "Removing crossing jump while redirecting edge form %i to %i\n",
4408 e
->src
->index
, dest
->index
);
4409 delete_insn (BB_END (src
));
4410 remove_barriers_from_footer (src
);
4411 e
->flags
|= EDGE_FALLTHRU
;
4414 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4415 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
4417 df_set_bb_dirty (src
);
4421 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4422 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
4425 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
4426 e
->src
->index
, dest
->index
);
4428 df_set_bb_dirty (e
->src
);
4429 redirect_edge_succ (e
, dest
);
4433 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4434 in the case the basic block appears to be in sequence. Avoid this
4437 if (e
->flags
& EDGE_FALLTHRU
)
4439 /* Redirect any branch edges unified with the fallthru one. */
4440 if (JUMP_P (BB_END (src
))
4441 && label_is_jump_target_p (BB_HEAD (e
->dest
),
4447 fprintf (dump_file
, "Fallthru edge unified with branch "
4448 "%i->%i redirected to %i\n",
4449 e
->src
->index
, e
->dest
->index
, dest
->index
);
4450 e
->flags
&= ~EDGE_FALLTHRU
;
4451 redirected
= redirect_branch_edge (e
, dest
);
4452 gcc_assert (redirected
);
4453 redirected
->flags
|= EDGE_FALLTHRU
;
4454 df_set_bb_dirty (redirected
->src
);
4457 /* In case we are redirecting fallthru edge to the branch edge
4458 of conditional jump, remove it. */
4459 if (EDGE_COUNT (src
->succs
) == 2)
4461 /* Find the edge that is different from E. */
4462 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
4465 && any_condjump_p (BB_END (src
))
4466 && onlyjump_p (BB_END (src
)))
4467 delete_insn (BB_END (src
));
4470 fprintf (dump_file
, "Redirecting fallthru edge %i->%i to %i\n",
4471 e
->src
->index
, e
->dest
->index
, dest
->index
);
4472 ret
= redirect_edge_succ_nodup (e
, dest
);
4475 ret
= redirect_branch_edge (e
, dest
);
4480 fixup_partition_crossing (ret
);
4481 /* We don't want simplejumps in the insn stream during cfglayout. */
4482 gcc_assert (!simplejump_p (BB_END (src
)) || CROSSING_JUMP_P (BB_END (src
)));
4484 df_set_bb_dirty (src
);
4488 /* Simple wrapper as we always can redirect fallthru edges. */
4490 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
4492 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
4494 gcc_assert (redirected
);
4498 /* Same as delete_basic_block but update cfg_layout structures. */
4501 cfg_layout_delete_block (basic_block bb
)
4503 rtx_insn
*insn
, *next
, *prev
= PREV_INSN (BB_HEAD (bb
)), *remaints
;
4508 next
= BB_HEAD (bb
);
4510 SET_NEXT_INSN (prev
) = BB_HEADER (bb
);
4512 set_first_insn (BB_HEADER (bb
));
4513 SET_PREV_INSN (BB_HEADER (bb
)) = prev
;
4514 insn
= BB_HEADER (bb
);
4515 while (NEXT_INSN (insn
))
4516 insn
= NEXT_INSN (insn
);
4517 SET_NEXT_INSN (insn
) = next
;
4518 SET_PREV_INSN (next
) = insn
;
4520 next
= NEXT_INSN (BB_END (bb
));
4523 insn
= BB_FOOTER (bb
);
4526 if (BARRIER_P (insn
))
4528 if (PREV_INSN (insn
))
4529 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
4531 BB_FOOTER (bb
) = NEXT_INSN (insn
);
4532 if (NEXT_INSN (insn
))
4533 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
4537 insn
= NEXT_INSN (insn
);
4542 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
4543 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
4544 while (NEXT_INSN (insn
))
4545 insn
= NEXT_INSN (insn
);
4546 SET_NEXT_INSN (insn
) = next
;
4548 SET_PREV_INSN (next
) = insn
;
4550 set_last_insn (insn
);
4553 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
4554 to
= &BB_HEADER (bb
->next_bb
);
4556 to
= &cfg_layout_function_footer
;
4558 rtl_delete_block (bb
);
4561 prev
= NEXT_INSN (prev
);
4563 prev
= get_insns ();
4565 next
= PREV_INSN (next
);
4567 next
= get_last_insn ();
4569 if (next
&& NEXT_INSN (next
) != prev
)
4571 remaints
= unlink_insn_chain (prev
, next
);
4573 while (NEXT_INSN (insn
))
4574 insn
= NEXT_INSN (insn
);
4575 SET_NEXT_INSN (insn
) = *to
;
4577 SET_PREV_INSN (*to
) = insn
;
4582 /* Return true when blocks A and B can be safely merged. */
4585 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
4587 /* If we are partitioning hot/cold basic blocks, we don't want to
4588 mess up unconditional or indirect jumps that cross between hot
4591 Basic block partitioning may result in some jumps that appear to
4592 be optimizable (or blocks that appear to be mergeable), but which really
4593 must be left untouched (they are required to make it safely across
4594 partition boundaries). See the comments at the top of
4595 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4597 if (BB_PARTITION (a
) != BB_PARTITION (b
))
4600 /* Protect the loop latches. */
4601 if (current_loops
&& b
->loop_father
->latch
== b
)
4604 /* If we would end up moving B's instructions, make sure it doesn't fall
4605 through into the exit block, since we cannot recover from a fallthrough
4606 edge into the exit block occurring in the middle of a function. */
4607 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4609 edge e
= find_fallthru_edge (b
->succs
);
4610 if (e
&& e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4614 /* There must be exactly one edge in between the blocks. */
4615 return (single_succ_p (a
)
4616 && single_succ (a
) == b
4617 && single_pred_p (b
) == 1
4619 /* Must be simple edge. */
4620 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
4621 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4622 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
4623 /* If the jump insn has side effects, we can't kill the edge.
4624 When not optimizing, try_redirect_by_replacing_jump will
4625 not allow us to redirect an edge by replacing a table jump. */
4626 && (!JUMP_P (BB_END (a
))
4627 || ((!optimize
|| reload_completed
)
4628 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
4631 /* Merge block A and B. The blocks must be mergeable. */
4634 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
4636 /* If B is a forwarder block whose outgoing edge has no location, we'll
4637 propagate the locus of the edge between A and B onto it. */
4638 const bool forward_edge_locus
4639 = (b
->flags
& BB_FORWARDER_BLOCK
) != 0
4640 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
;
4643 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a
, b
));
4646 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
4649 /* If there was a CODE_LABEL beginning B, delete it. */
4650 if (LABEL_P (BB_HEAD (b
)))
4652 delete_insn (BB_HEAD (b
));
4655 /* We should have fallthru edge in a, or we can do dummy redirection to get
4657 if (JUMP_P (BB_END (a
)))
4658 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
4659 gcc_assert (!JUMP_P (BB_END (a
)));
4661 /* If not optimizing, preserve the locus of the single edge between
4662 blocks A and B if necessary by emitting a nop. */
4664 && !forward_edge_locus
4665 && !DECL_IGNORED_P (current_function_decl
))
4666 emit_nop_for_unique_locus_between (a
, b
);
4668 /* Move things from b->footer after a->footer. */
4672 BB_FOOTER (a
) = BB_FOOTER (b
);
4675 rtx_insn
*last
= BB_FOOTER (a
);
4677 while (NEXT_INSN (last
))
4678 last
= NEXT_INSN (last
);
4679 SET_NEXT_INSN (last
) = BB_FOOTER (b
);
4680 SET_PREV_INSN (BB_FOOTER (b
)) = last
;
4682 BB_FOOTER (b
) = NULL
;
4685 /* Move things from b->header before a->footer.
4686 Note that this may include dead tablejump data, but we don't clean
4687 those up until we go out of cfglayout mode. */
4690 if (! BB_FOOTER (a
))
4691 BB_FOOTER (a
) = BB_HEADER (b
);
4694 rtx_insn
*last
= BB_HEADER (b
);
4696 while (NEXT_INSN (last
))
4697 last
= NEXT_INSN (last
);
4698 SET_NEXT_INSN (last
) = BB_FOOTER (a
);
4699 SET_PREV_INSN (BB_FOOTER (a
)) = last
;
4700 BB_FOOTER (a
) = BB_HEADER (b
);
4702 BB_HEADER (b
) = NULL
;
4705 /* In the case basic blocks are not adjacent, move them around. */
4706 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4708 insn
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
4710 emit_insn_after_noloc (insn
, BB_END (a
), a
);
4712 /* Otherwise just re-associate the instructions. */
4716 BB_END (a
) = BB_END (b
);
4719 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4720 We need to explicitly call. */
4721 update_bb_for_insn_chain (insn
, BB_END (b
), a
);
4723 /* Skip possible DELETED_LABEL insn. */
4724 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
4725 insn
= NEXT_INSN (insn
);
4726 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4727 BB_HEAD (b
) = BB_END (b
) = NULL
;
4730 df_bb_delete (b
->index
);
4732 if (forward_edge_locus
)
4733 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
4736 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
4742 cfg_layout_split_edge (edge e
)
4744 basic_block new_bb
=
4745 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4746 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
4749 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4750 BB_COPY_PARTITION (new_bb
, e
->src
);
4752 BB_COPY_PARTITION (new_bb
, e
->dest
);
4753 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
4754 redirect_edge_and_branch_force (e
, new_bb
);
4759 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4762 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
4766 /* Return true if BB contains only labels or non-executable
4770 rtl_block_empty_p (basic_block bb
)
4774 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4775 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4778 FOR_BB_INSNS (bb
, insn
)
4779 if (NONDEBUG_INSN_P (insn
) && !any_uncondjump_p (insn
))
4785 /* Split a basic block if it ends with a conditional branch and if
4786 the other part of the block is not empty. */
4789 rtl_split_block_before_cond_jump (basic_block bb
)
4792 rtx_insn
*split_point
= NULL
;
4793 rtx_insn
*last
= NULL
;
4794 bool found_code
= false;
4796 FOR_BB_INSNS (bb
, insn
)
4798 if (any_condjump_p (insn
))
4800 else if (NONDEBUG_INSN_P (insn
))
4805 /* Did not find everything. */
4806 if (found_code
&& split_point
)
4807 return split_block (bb
, split_point
)->dest
;
4812 /* Return 1 if BB ends with a call, possibly followed by some
4813 instructions that must stay with the call, 0 otherwise. */
4816 rtl_block_ends_with_call_p (basic_block bb
)
4818 rtx_insn
*insn
= BB_END (bb
);
4820 while (!CALL_P (insn
)
4821 && insn
!= BB_HEAD (bb
)
4822 && (keep_with_call_p (insn
)
4824 || DEBUG_INSN_P (insn
)))
4825 insn
= PREV_INSN (insn
);
4826 return (CALL_P (insn
));
4829 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4832 rtl_block_ends_with_condjump_p (const_basic_block bb
)
4834 return any_condjump_p (BB_END (bb
));
4837 /* Return true if we need to add fake edge to exit.
4838 Helper function for rtl_flow_call_edges_add. */
4841 need_fake_edge_p (const rtx_insn
*insn
)
4847 && !SIBLING_CALL_P (insn
)
4848 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
4849 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
4852 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
4853 && MEM_VOLATILE_P (PATTERN (insn
)))
4854 || (GET_CODE (PATTERN (insn
)) == PARALLEL
4855 && asm_noperands (insn
) != -1
4856 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
4857 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
4860 /* Add fake edges to the function exit for any non constant and non noreturn
4861 calls, volatile inline assembly in the bitmap of blocks specified by
4862 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4865 The goal is to expose cases in which entering a basic block does not imply
4866 that all subsequent instructions must be executed. */
4869 rtl_flow_call_edges_add (sbitmap blocks
)
4872 int blocks_split
= 0;
4873 int last_bb
= last_basic_block_for_fn (cfun
);
4874 bool check_last_block
= false;
4876 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
4880 check_last_block
= true;
4882 check_last_block
= bitmap_bit_p (blocks
,
4883 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
->index
);
4885 /* In the last basic block, before epilogue generation, there will be
4886 a fallthru edge to EXIT. Special care is required if the last insn
4887 of the last basic block is a call because make_edge folds duplicate
4888 edges, which would result in the fallthru edge also being marked
4889 fake, which would result in the fallthru edge being removed by
4890 remove_fake_edges, which would result in an invalid CFG.
4892 Moreover, we can't elide the outgoing fake edge, since the block
4893 profiler needs to take this into account in order to solve the minimal
4894 spanning tree in the case that the call doesn't return.
4896 Handle this by adding a dummy instruction in a new last basic block. */
4897 if (check_last_block
)
4899 basic_block bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
4900 rtx_insn
*insn
= BB_END (bb
);
4902 /* Back up past insns that must be kept in the same block as a call. */
4903 while (insn
!= BB_HEAD (bb
)
4904 && keep_with_call_p (insn
))
4905 insn
= PREV_INSN (insn
);
4907 if (need_fake_edge_p (insn
))
4911 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4914 insert_insn_on_edge (gen_use (const0_rtx
), e
);
4915 commit_edge_insertions ();
4920 /* Now add fake edges to the function exit for any non constant
4921 calls since there is no way that we can determine if they will
4924 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
4926 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
4928 rtx_insn
*prev_insn
;
4933 if (blocks
&& !bitmap_bit_p (blocks
, i
))
4936 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
4938 prev_insn
= PREV_INSN (insn
);
4939 if (need_fake_edge_p (insn
))
4942 rtx_insn
*split_at_insn
= insn
;
4944 /* Don't split the block between a call and an insn that should
4945 remain in the same block as the call. */
4947 while (split_at_insn
!= BB_END (bb
)
4948 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
4949 split_at_insn
= NEXT_INSN (split_at_insn
);
4951 /* The handling above of the final block before the epilogue
4952 should be enough to verify that there is no edge to the exit
4953 block in CFG already. Calling make_edge in such case would
4954 cause us to mark that edge as fake and remove it later. */
4956 if (flag_checking
&& split_at_insn
== BB_END (bb
))
4958 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4959 gcc_assert (e
== NULL
);
4962 /* Note that the following may create a new basic block
4963 and renumber the existing basic blocks. */
4964 if (split_at_insn
!= BB_END (bb
))
4966 e
= split_block (bb
, split_at_insn
);
4971 edge ne
= make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
4972 ne
->probability
= profile_probability::guessed_never ();
4975 if (insn
== BB_HEAD (bb
))
4981 verify_flow_info ();
4983 return blocks_split
;
4986 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4987 the conditional branch target, SECOND_HEAD should be the fall-thru
4988 there is no need to handle this here the loop versioning code handles
4989 this. the reason for SECON_HEAD is that it is needed for condition
4990 in trees, and this should be of the same type since it is a hook. */
4992 rtl_lv_add_condition_to_bb (basic_block first_head
,
4993 basic_block second_head ATTRIBUTE_UNUSED
,
4994 basic_block cond_bb
, void *comp_rtx
)
4996 rtx_code_label
*label
;
4997 rtx_insn
*seq
, *jump
;
4998 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
4999 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
5000 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
5004 label
= block_label (first_head
);
5005 mode
= GET_MODE (op0
);
5006 if (mode
== VOIDmode
)
5007 mode
= GET_MODE (op1
);
5010 op0
= force_operand (op0
, NULL_RTX
);
5011 op1
= force_operand (op1
, NULL_RTX
);
5012 do_compare_rtx_and_jump (op0
, op1
, comp
, 0, mode
, NULL_RTX
, NULL
, label
,
5013 profile_probability::uninitialized ());
5014 jump
= get_last_insn ();
5015 JUMP_LABEL (jump
) = label
;
5016 LABEL_NUSES (label
)++;
5020 /* Add the new cond, in the new head. */
5021 emit_insn_after (seq
, BB_END (cond_bb
));
5025 /* Given a block B with unconditional branch at its end, get the
5026 store the return the branch edge and the fall-thru edge in
5027 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
5029 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
5030 edge
*fallthru_edge
)
5032 edge e
= EDGE_SUCC (b
, 0);
5034 if (e
->flags
& EDGE_FALLTHRU
)
5037 *branch_edge
= EDGE_SUCC (b
, 1);
5042 *fallthru_edge
= EDGE_SUCC (b
, 1);
5047 init_rtl_bb_info (basic_block bb
)
5049 gcc_assert (!bb
->il
.x
.rtl
);
5050 bb
->il
.x
.head_
= NULL
;
5051 bb
->il
.x
.rtl
= ggc_cleared_alloc
<rtl_bb_info
> ();
5054 /* Returns true if it is possible to remove edge E by redirecting
5055 it to the destination of the other edge from E->src. */
5058 rtl_can_remove_branch_p (const_edge e
)
5060 const_basic_block src
= e
->src
;
5061 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
5062 const rtx_insn
*insn
= BB_END (src
);
5065 /* The conditions are taken from try_redirect_by_replacing_jump. */
5066 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
5069 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
5072 if (BB_PARTITION (src
) != BB_PARTITION (target
))
5075 if (!onlyjump_p (insn
)
5076 || tablejump_p (insn
, NULL
, NULL
))
5079 set
= single_set (insn
);
5080 if (!set
|| side_effects_p (set
))
5087 rtl_duplicate_bb (basic_block bb
, copy_bb_data
*id
)
5089 bb
= cfg_layout_duplicate_bb (bb
, id
);
5094 /* Do book-keeping of basic block BB for the profile consistency checker.
5095 Store the counting in RECORD. */
5097 rtl_account_profile_record (basic_block bb
, struct profile_record
*record
)
5100 FOR_BB_INSNS (bb
, insn
)
5103 record
->size
+= insn_cost (insn
, false);
5104 if (bb
->count
.initialized_p ())
5106 += insn_cost (insn
, true) * bb
->count
.to_gcov_type ();
5107 else if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
5109 += insn_cost (insn
, true) * bb
->count
.to_frequency (cfun
);
5113 /* Implementation of CFG manipulation for linearized RTL. */
5114 struct cfg_hooks rtl_cfg_hooks
= {
5116 rtl_verify_flow_info
,
5118 rtl_dump_bb_for_graph
,
5119 rtl_create_basic_block
,
5120 rtl_redirect_edge_and_branch
,
5121 rtl_redirect_edge_and_branch_force
,
5122 rtl_can_remove_branch_p
,
5125 rtl_move_block_after
,
5126 rtl_can_merge_blocks
, /* can_merge_blocks_p */
5130 cfg_layout_can_duplicate_bb_p
,
5133 rtl_make_forwarder_block
,
5134 rtl_tidy_fallthru_edge
,
5135 rtl_force_nonfallthru
,
5136 rtl_block_ends_with_call_p
,
5137 rtl_block_ends_with_condjump_p
,
5138 rtl_flow_call_edges_add
,
5139 NULL
, /* execute_on_growing_pred */
5140 NULL
, /* execute_on_shrinking_pred */
5141 NULL
, /* duplicate loop for trees */
5142 NULL
, /* lv_add_condition_to_bb */
5143 NULL
, /* lv_adjust_loop_header_phi*/
5144 NULL
, /* extract_cond_bb_edges */
5145 NULL
, /* flush_pending_stmts */
5146 rtl_block_empty_p
, /* block_empty_p */
5147 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5148 rtl_account_profile_record
,
5151 /* Implementation of CFG manipulation for cfg layout RTL, where
5152 basic block connected via fallthru edges does not have to be adjacent.
5153 This representation will hopefully become the default one in future
5154 version of the compiler. */
5156 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
5158 rtl_verify_flow_info_1
,
5160 rtl_dump_bb_for_graph
,
5161 cfg_layout_create_basic_block
,
5162 cfg_layout_redirect_edge_and_branch
,
5163 cfg_layout_redirect_edge_and_branch_force
,
5164 rtl_can_remove_branch_p
,
5165 cfg_layout_delete_block
,
5166 cfg_layout_split_block
,
5167 rtl_move_block_after
,
5168 cfg_layout_can_merge_blocks_p
,
5169 cfg_layout_merge_blocks
,
5172 cfg_layout_can_duplicate_bb_p
,
5173 cfg_layout_duplicate_bb
,
5174 cfg_layout_split_edge
,
5175 rtl_make_forwarder_block
,
5176 NULL
, /* tidy_fallthru_edge */
5177 rtl_force_nonfallthru
,
5178 rtl_block_ends_with_call_p
,
5179 rtl_block_ends_with_condjump_p
,
5180 rtl_flow_call_edges_add
,
5181 NULL
, /* execute_on_growing_pred */
5182 NULL
, /* execute_on_shrinking_pred */
5183 duplicate_loop_to_header_edge
, /* duplicate loop for trees */
5184 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
5185 NULL
, /* lv_adjust_loop_header_phi*/
5186 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
5187 NULL
, /* flush_pending_stmts */
5188 rtl_block_empty_p
, /* block_empty_p */
5189 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5190 rtl_account_profile_record
,
5193 #include "gt-cfgrtl.h"