1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2018 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This file contains low level functions to manipulate the CFG and analyze it
21 that are aware of the RTL intermediate language.
23 Available functionality:
24 - Basic CFG/RTL manipulation API documented in cfghooks.h
25 - CFG-aware instruction chain manipulation
26 delete_insn, delete_insn_chain
27 - Edge splitting and committing to edges
28 insert_insn_on_edge, commit_edge_insertions
29 - CFG updating after insn simplification
30 purge_dead_edges, purge_all_dead_edges
31 - CFG fixing after coarse manipulation
34 Functions not supposed for generic use:
35 - Infrastructure to determine quickly basic block for insn
36 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
37 - Edge redirection with updating and optimizing of insn chain
38 block_label, tidy_fallthru_edge, force_nonfallthru */
42 #include "coretypes.h"
49 #include "insn-config.h"
55 #include "cfgcleanup.h"
56 #include "bb-reorder.h"
57 #include "rtl-error.h"
58 #include "insn-attr.h"
62 #include "tree-pass.h"
63 #include "print-rtl.h"
65 /* Holds the interesting leading and trailing notes for the function.
66 Only applicable if the CFG is in cfglayout mode. */
67 static GTY(()) rtx_insn
*cfg_layout_function_footer
;
68 static GTY(()) rtx_insn
*cfg_layout_function_header
;
70 static rtx_insn
*skip_insns_after_block (basic_block
);
71 static void record_effective_endpoints (void);
72 static void fixup_reorder_chain (void);
74 void verify_insn_chain (void);
75 static void fixup_fallthru_exit_predecessor (void);
76 static int can_delete_note_p (const rtx_note
*);
77 static int can_delete_label_p (const rtx_code_label
*);
78 static basic_block
rtl_split_edge (edge
);
79 static bool rtl_move_block_after (basic_block
, basic_block
);
80 static int rtl_verify_flow_info (void);
81 static basic_block
cfg_layout_split_block (basic_block
, void *);
82 static edge
cfg_layout_redirect_edge_and_branch (edge
, basic_block
);
83 static basic_block
cfg_layout_redirect_edge_and_branch_force (edge
, basic_block
);
84 static void cfg_layout_delete_block (basic_block
);
85 static void rtl_delete_block (basic_block
);
86 static basic_block
rtl_redirect_edge_and_branch_force (edge
, basic_block
);
87 static edge
rtl_redirect_edge_and_branch (edge
, basic_block
);
88 static basic_block
rtl_split_block (basic_block
, void *);
89 static void rtl_dump_bb (FILE *, basic_block
, int, dump_flags_t
);
90 static int rtl_verify_flow_info_1 (void);
91 static void rtl_make_forwarder_block (edge
);
93 /* Return true if NOTE is not one of the ones that must be kept paired,
94 so that we may simply delete it. */
97 can_delete_note_p (const rtx_note
*note
)
99 switch (NOTE_KIND (note
))
101 case NOTE_INSN_DELETED
:
102 case NOTE_INSN_BASIC_BLOCK
:
103 case NOTE_INSN_EPILOGUE_BEG
:
111 /* True if a given label can be deleted. */
114 can_delete_label_p (const rtx_code_label
*label
)
116 return (!LABEL_PRESERVE_P (label
)
117 /* User declared labels must be preserved. */
118 && LABEL_NAME (label
) == 0
119 && !vec_safe_contains
<rtx_insn
*> (forced_labels
,
120 const_cast<rtx_code_label
*> (label
)));
123 /* Delete INSN by patching it out. */
126 delete_insn (rtx_insn
*insn
)
129 bool really_delete
= true;
133 /* Some labels can't be directly removed from the INSN chain, as they
134 might be references via variables, constant pool etc.
135 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
136 if (! can_delete_label_p (as_a
<rtx_code_label
*> (insn
)))
138 const char *name
= LABEL_NAME (insn
);
139 basic_block bb
= BLOCK_FOR_INSN (insn
);
140 rtx_insn
*bb_note
= NEXT_INSN (insn
);
142 really_delete
= false;
143 PUT_CODE (insn
, NOTE
);
144 NOTE_KIND (insn
) = NOTE_INSN_DELETED_LABEL
;
145 NOTE_DELETED_LABEL_NAME (insn
) = name
;
147 /* If the note following the label starts a basic block, and the
148 label is a member of the same basic block, interchange the two. */
149 if (bb_note
!= NULL_RTX
150 && NOTE_INSN_BASIC_BLOCK_P (bb_note
)
152 && bb
== BLOCK_FOR_INSN (bb_note
))
154 reorder_insns_nobb (insn
, insn
, bb_note
);
155 BB_HEAD (bb
) = bb_note
;
156 if (BB_END (bb
) == bb_note
)
161 remove_node_from_insn_list (insn
, &nonlocal_goto_handler_labels
);
166 /* If this insn has already been deleted, something is very wrong. */
167 gcc_assert (!insn
->deleted ());
169 df_insn_delete (insn
);
171 insn
->set_deleted ();
174 /* If deleting a jump, decrement the use count of the label. Deleting
175 the label itself should happen in the normal course of block merging. */
178 if (JUMP_LABEL (insn
)
179 && LABEL_P (JUMP_LABEL (insn
)))
180 LABEL_NUSES (JUMP_LABEL (insn
))--;
182 /* If there are more targets, remove them too. */
184 = find_reg_note (insn
, REG_LABEL_TARGET
, NULL_RTX
)) != NULL_RTX
185 && LABEL_P (XEXP (note
, 0)))
187 LABEL_NUSES (XEXP (note
, 0))--;
188 remove_note (insn
, note
);
192 /* Also if deleting any insn that references a label as an operand. */
193 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, NULL_RTX
)) != NULL_RTX
194 && LABEL_P (XEXP (note
, 0)))
196 LABEL_NUSES (XEXP (note
, 0))--;
197 remove_note (insn
, note
);
200 if (rtx_jump_table_data
*table
= dyn_cast
<rtx_jump_table_data
*> (insn
))
202 rtvec vec
= table
->get_labels ();
203 int len
= GET_NUM_ELEM (vec
);
206 for (i
= 0; i
< len
; i
++)
208 rtx label
= XEXP (RTVEC_ELT (vec
, i
), 0);
210 /* When deleting code in bulk (e.g. removing many unreachable
211 blocks) we can delete a label that's a target of the vector
212 before deleting the vector itself. */
214 LABEL_NUSES (label
)--;
219 /* Like delete_insn but also purge dead edges from BB.
220 Return true if any edges are eliminated. */
223 delete_insn_and_edges (rtx_insn
*insn
)
228 && BLOCK_FOR_INSN (insn
)
229 && BB_END (BLOCK_FOR_INSN (insn
)) == insn
)
233 return purge_dead_edges (BLOCK_FOR_INSN (insn
));
237 /* Unlink a chain of insns between START and FINISH, leaving notes
238 that must be paired. If CLEAR_BB is true, we set bb field for
239 insns that cannot be removed to NULL. */
242 delete_insn_chain (rtx start
, rtx_insn
*finish
, bool clear_bb
)
244 /* Unchain the insns one by one. It would be quicker to delete all of these
245 with a single unchaining, rather than one at a time, but we need to keep
247 rtx_insn
*current
= finish
;
250 rtx_insn
*prev
= PREV_INSN (current
);
251 if (NOTE_P (current
) && !can_delete_note_p (as_a
<rtx_note
*> (current
)))
254 delete_insn (current
);
256 if (clear_bb
&& !current
->deleted ())
257 set_block_for_insn (current
, NULL
);
259 if (current
== start
)
265 /* Create a new basic block consisting of the instructions between HEAD and END
266 inclusive. This function is designed to allow fast BB construction - reuses
267 the note and basic block struct in BB_NOTE, if any and do not grow
268 BASIC_BLOCK chain and should be used directly only by CFG construction code.
269 END can be NULL in to create new empty basic block before HEAD. Both END
270 and HEAD can be NULL to create basic block at the end of INSN chain.
271 AFTER is the basic block we should be put after. */
274 create_basic_block_structure (rtx_insn
*head
, rtx_insn
*end
, rtx_note
*bb_note
,
280 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
283 /* If we found an existing note, thread it back onto the chain. */
291 after
= PREV_INSN (head
);
295 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
296 reorder_insns_nobb (bb_note
, bb_note
, after
);
300 /* Otherwise we must create a note and a basic block structure. */
304 init_rtl_bb_info (bb
);
307 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
308 else if (LABEL_P (head
) && end
)
310 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
316 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
322 NOTE_BASIC_BLOCK (bb_note
) = bb
;
325 /* Always include the bb note in the block. */
326 if (NEXT_INSN (end
) == bb_note
)
331 bb
->index
= last_basic_block_for_fn (cfun
)++;
332 bb
->flags
= BB_NEW
| BB_RTL
;
333 link_block (bb
, after
);
334 SET_BASIC_BLOCK_FOR_FN (cfun
, bb
->index
, bb
);
335 df_bb_refs_record (bb
->index
, false);
336 update_bb_for_insn (bb
);
337 BB_SET_PARTITION (bb
, BB_UNPARTITIONED
);
339 /* Tag the block so that we know it has been used when considering
340 other basic block notes. */
346 /* Create new basic block consisting of instructions in between HEAD and END
347 and place it to the BB chain after block AFTER. END can be NULL to
348 create a new empty basic block before HEAD. Both END and HEAD can be
349 NULL to create basic block at the end of INSN chain. */
352 rtl_create_basic_block (void *headp
, void *endp
, basic_block after
)
354 rtx_insn
*head
= (rtx_insn
*) headp
;
355 rtx_insn
*end
= (rtx_insn
*) endp
;
358 /* Grow the basic block array if needed. */
359 if ((size_t) last_basic_block_for_fn (cfun
)
360 >= basic_block_info_for_fn (cfun
)->length ())
363 (last_basic_block_for_fn (cfun
)
364 + (last_basic_block_for_fn (cfun
) + 3) / 4);
365 vec_safe_grow_cleared (basic_block_info_for_fn (cfun
), new_size
);
368 n_basic_blocks_for_fn (cfun
)++;
370 bb
= create_basic_block_structure (head
, end
, NULL
, after
);
376 cfg_layout_create_basic_block (void *head
, void *end
, basic_block after
)
378 basic_block newbb
= rtl_create_basic_block (head
, end
, after
);
383 /* Delete the insns in a (non-live) block. We physically delete every
384 non-deleted-note insn, and update the flow graph appropriately.
386 Return nonzero if we deleted an exception handler. */
388 /* ??? Preserving all such notes strikes me as wrong. It would be nice
389 to post-process the stream to remove empty blocks, loops, ranges, etc. */
392 rtl_delete_block (basic_block b
)
394 rtx_insn
*insn
, *end
;
396 /* If the head of this block is a CODE_LABEL, then it might be the
397 label for an exception handler which can't be reached. We need
398 to remove the label from the exception_handler_label list. */
401 end
= get_last_bb_insn (b
);
403 /* Selectively delete the entire chain. */
405 delete_insn_chain (insn
, end
, true);
409 fprintf (dump_file
, "deleting block %d\n", b
->index
);
410 df_bb_delete (b
->index
);
413 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
416 compute_bb_for_insn (void)
420 FOR_EACH_BB_FN (bb
, cfun
)
422 rtx_insn
*end
= BB_END (bb
);
425 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
427 BLOCK_FOR_INSN (insn
) = bb
;
434 /* Release the basic_block_for_insn array. */
437 free_bb_for_insn (void)
440 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
441 if (!BARRIER_P (insn
))
442 BLOCK_FOR_INSN (insn
) = NULL
;
448 const pass_data pass_data_free_cfg
=
451 "*free_cfg", /* name */
452 OPTGROUP_NONE
, /* optinfo_flags */
454 0, /* properties_required */
455 0, /* properties_provided */
456 PROP_cfg
, /* properties_destroyed */
457 0, /* todo_flags_start */
458 0, /* todo_flags_finish */
461 class pass_free_cfg
: public rtl_opt_pass
464 pass_free_cfg (gcc::context
*ctxt
)
465 : rtl_opt_pass (pass_data_free_cfg
, ctxt
)
468 /* opt_pass methods: */
469 virtual unsigned int execute (function
*);
471 }; // class pass_free_cfg
474 pass_free_cfg::execute (function
*)
476 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
477 valid at that point so it would be too late to call df_analyze. */
478 if (DELAY_SLOTS
&& optimize
> 0 && flag_delayed_branch
)
480 df_note_add_problem ();
484 if (crtl
->has_bb_partition
)
485 insert_section_boundary_note ();
494 make_pass_free_cfg (gcc::context
*ctxt
)
496 return new pass_free_cfg (ctxt
);
499 /* Return RTX to emit after when we want to emit code on the entry of function. */
501 entry_of_function (void)
503 return (n_basic_blocks_for_fn (cfun
) > NUM_FIXED_BLOCKS
?
504 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
) : get_insns ());
507 /* Emit INSN at the entry point of the function, ensuring that it is only
508 executed once per function. */
510 emit_insn_at_entry (rtx insn
)
512 edge_iterator ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
513 edge e
= ei_safe_edge (ei
);
514 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
516 insert_insn_on_edge (insn
, e
);
517 commit_edge_insertions ();
520 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
521 (or BARRIER if found) and notify df of the bb change.
522 The insn chain range is inclusive
523 (i.e. both BEGIN and END will be updated. */
526 update_bb_for_insn_chain (rtx_insn
*begin
, rtx_insn
*end
, basic_block bb
)
530 end
= NEXT_INSN (end
);
531 for (insn
= begin
; insn
!= end
; insn
= NEXT_INSN (insn
))
532 if (!BARRIER_P (insn
))
533 df_insn_change_bb (insn
, bb
);
536 /* Update BLOCK_FOR_INSN of insns in BB to BB,
537 and notify df of the change. */
540 update_bb_for_insn (basic_block bb
)
542 update_bb_for_insn_chain (BB_HEAD (bb
), BB_END (bb
), bb
);
546 /* Like active_insn_p, except keep the return value clobber around
547 even after reload. */
550 flow_active_insn_p (const rtx_insn
*insn
)
552 if (active_insn_p (insn
))
555 /* A clobber of the function return value exists for buggy
556 programs that fail to return a value. Its effect is to
557 keep the return value from being live across the entire
558 function. If we allow it to be skipped, we introduce the
559 possibility for register lifetime confusion. */
560 if (GET_CODE (PATTERN (insn
)) == CLOBBER
561 && REG_P (XEXP (PATTERN (insn
), 0))
562 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn
), 0)))
568 /* Return true if the block has no effect and only forwards control flow to
569 its single destination. */
572 contains_no_active_insn_p (const_basic_block bb
)
576 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
577 || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
578 || !single_succ_p (bb
)
579 || (single_succ_edge (bb
)->flags
& EDGE_FAKE
) != 0)
582 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
583 if (INSN_P (insn
) && flow_active_insn_p (insn
))
586 return (!INSN_P (insn
)
587 || (JUMP_P (insn
) && simplejump_p (insn
))
588 || !flow_active_insn_p (insn
));
591 /* Likewise, but protect loop latches, headers and preheaders. */
592 /* FIXME: Make this a cfg hook. */
595 forwarder_block_p (const_basic_block bb
)
597 if (!contains_no_active_insn_p (bb
))
600 /* Protect loop latches, headers and preheaders. */
604 if (bb
->loop_father
->header
== bb
)
606 dest
= EDGE_SUCC (bb
, 0)->dest
;
607 if (dest
->loop_father
->header
== dest
)
614 /* Return nonzero if we can reach target from src by falling through. */
615 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
618 can_fallthru (basic_block src
, basic_block target
)
620 rtx_insn
*insn
= BB_END (src
);
625 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
627 if (src
->next_bb
!= target
)
630 /* ??? Later we may add code to move jump tables offline. */
631 if (tablejump_p (insn
, NULL
, NULL
))
634 FOR_EACH_EDGE (e
, ei
, src
->succs
)
635 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
636 && e
->flags
& EDGE_FALLTHRU
)
639 insn2
= BB_HEAD (target
);
640 if (!active_insn_p (insn2
))
641 insn2
= next_active_insn (insn2
);
643 return next_active_insn (insn
) == insn2
;
646 /* Return nonzero if we could reach target from src by falling through,
647 if the target was made adjacent. If we already have a fall-through
648 edge to the exit block, we can't do that. */
650 could_fall_through (basic_block src
, basic_block target
)
655 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
657 FOR_EACH_EDGE (e
, ei
, src
->succs
)
658 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
659 && e
->flags
& EDGE_FALLTHRU
)
664 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
666 bb_note (basic_block bb
)
672 note
= NEXT_INSN (note
);
674 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
675 return as_a
<rtx_note
*> (note
);
678 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
679 note associated with the BLOCK. */
682 first_insn_after_basic_block_note (basic_block block
)
686 /* Get the first instruction in the block. */
687 insn
= BB_HEAD (block
);
689 if (insn
== NULL_RTX
)
692 insn
= NEXT_INSN (insn
);
693 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
695 return NEXT_INSN (insn
);
698 /* Creates a new basic block just after basic block BB by splitting
699 everything after specified instruction INSNP. */
702 rtl_split_block (basic_block bb
, void *insnp
)
705 rtx_insn
*insn
= (rtx_insn
*) insnp
;
711 insn
= first_insn_after_basic_block_note (bb
);
715 rtx_insn
*next
= insn
;
717 insn
= PREV_INSN (insn
);
719 /* If the block contains only debug insns, insn would have
720 been NULL in a non-debug compilation, and then we'd end
721 up emitting a DELETED note. For -fcompare-debug
722 stability, emit the note too. */
723 if (insn
!= BB_END (bb
)
724 && DEBUG_INSN_P (next
)
725 && DEBUG_INSN_P (BB_END (bb
)))
727 while (next
!= BB_END (bb
) && DEBUG_INSN_P (next
))
728 next
= NEXT_INSN (next
);
730 if (next
== BB_END (bb
))
731 emit_note_after (NOTE_INSN_DELETED
, next
);
735 insn
= get_last_insn ();
738 /* We probably should check type of the insn so that we do not create
739 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
741 if (insn
== BB_END (bb
))
742 emit_note_after (NOTE_INSN_DELETED
, insn
);
744 /* Create the new basic block. */
745 new_bb
= create_basic_block (NEXT_INSN (insn
), BB_END (bb
), bb
);
746 BB_COPY_PARTITION (new_bb
, bb
);
749 /* Redirect the outgoing edges. */
750 new_bb
->succs
= bb
->succs
;
752 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
755 /* The new block starts off being dirty. */
756 df_set_bb_dirty (bb
);
760 /* Return true if the single edge between blocks A and B is the only place
761 in RTL which holds some unique locus. */
764 unique_locus_on_edge_between_p (basic_block a
, basic_block b
)
766 const location_t goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
767 rtx_insn
*insn
, *end
;
769 if (LOCATION_LOCUS (goto_locus
) == UNKNOWN_LOCATION
)
772 /* First scan block A backward. */
774 end
= PREV_INSN (BB_HEAD (a
));
775 while (insn
!= end
&& (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
776 insn
= PREV_INSN (insn
);
778 if (insn
!= end
&& INSN_LOCATION (insn
) == goto_locus
)
781 /* Then scan block B forward. */
785 end
= NEXT_INSN (BB_END (b
));
786 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
787 insn
= NEXT_INSN (insn
);
789 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
790 && INSN_LOCATION (insn
) == goto_locus
)
797 /* If the single edge between blocks A and B is the only place in RTL which
798 holds some unique locus, emit a nop with that locus between the blocks. */
801 emit_nop_for_unique_locus_between (basic_block a
, basic_block b
)
803 if (!unique_locus_on_edge_between_p (a
, b
))
806 BB_END (a
) = emit_insn_after_noloc (gen_nop (), BB_END (a
), a
);
807 INSN_LOCATION (BB_END (a
)) = EDGE_SUCC (a
, 0)->goto_locus
;
810 /* Blocks A and B are to be merged into a single block A. The insns
811 are already contiguous. */
814 rtl_merge_blocks (basic_block a
, basic_block b
)
816 /* If B is a forwarder block whose outgoing edge has no location, we'll
817 propagate the locus of the edge between A and B onto it. */
818 const bool forward_edge_locus
819 = (b
->flags
& BB_FORWARDER_BLOCK
) != 0
820 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
;
821 rtx_insn
*b_head
= BB_HEAD (b
), *b_end
= BB_END (b
), *a_end
= BB_END (a
);
822 rtx_insn
*del_first
= NULL
, *del_last
= NULL
;
823 rtx_insn
*b_debug_start
= b_end
, *b_debug_end
= b_end
;
827 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
830 while (DEBUG_INSN_P (b_end
))
831 b_end
= PREV_INSN (b_debug_start
= b_end
);
833 /* If there was a CODE_LABEL beginning B, delete it. */
834 if (LABEL_P (b_head
))
836 /* Detect basic blocks with nothing but a label. This can happen
837 in particular at the end of a function. */
841 del_first
= del_last
= b_head
;
842 b_head
= NEXT_INSN (b_head
);
845 /* Delete the basic block note and handle blocks containing just that
847 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
855 b_head
= NEXT_INSN (b_head
);
858 /* If there was a jump out of A, delete it. */
863 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
865 || NOTE_INSN_BASIC_BLOCK_P (prev
)
866 || prev
== BB_HEAD (a
))
871 /* If this was a conditional jump, we need to also delete
872 the insn that set cc0. */
873 if (HAVE_cc0
&& only_sets_cc0_p (prev
))
875 rtx_insn
*tmp
= prev
;
877 prev
= prev_nonnote_insn (prev
);
883 a_end
= PREV_INSN (del_first
);
885 else if (BARRIER_P (NEXT_INSN (a_end
)))
886 del_first
= NEXT_INSN (a_end
);
888 /* Delete everything marked above as well as crap that might be
889 hanging out between the two blocks. */
891 BB_HEAD (b
) = b_empty
? NULL
: b_head
;
892 delete_insn_chain (del_first
, del_last
, true);
894 /* If not optimizing, preserve the locus of the single edge between
895 blocks A and B if necessary by emitting a nop. */
897 && !forward_edge_locus
898 && !DECL_IGNORED_P (current_function_decl
))
900 emit_nop_for_unique_locus_between (a
, b
);
904 /* Reassociate the insns of B with A. */
907 update_bb_for_insn_chain (a_end
, b_debug_end
, a
);
909 BB_END (a
) = b_debug_end
;
912 else if (b_end
!= b_debug_end
)
914 /* Move any deleted labels and other notes between the end of A
915 and the debug insns that make up B after the debug insns,
916 bringing the debug insns into A while keeping the notes after
918 if (NEXT_INSN (a_end
) != b_debug_start
)
919 reorder_insns_nobb (NEXT_INSN (a_end
), PREV_INSN (b_debug_start
),
921 update_bb_for_insn_chain (b_debug_start
, b_debug_end
, a
);
922 BB_END (a
) = b_debug_end
;
925 df_bb_delete (b
->index
);
927 if (forward_edge_locus
)
928 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
931 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
935 /* Return true when block A and B can be merged. */
938 rtl_can_merge_blocks (basic_block a
, basic_block b
)
940 /* If we are partitioning hot/cold basic blocks, we don't want to
941 mess up unconditional or indirect jumps that cross between hot
944 Basic block partitioning may result in some jumps that appear to
945 be optimizable (or blocks that appear to be mergeable), but which really
946 must be left untouched (they are required to make it safely across
947 partition boundaries). See the comments at the top of
948 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
950 if (BB_PARTITION (a
) != BB_PARTITION (b
))
953 /* Protect the loop latches. */
954 if (current_loops
&& b
->loop_father
->latch
== b
)
957 /* There must be exactly one edge in between the blocks. */
958 return (single_succ_p (a
)
959 && single_succ (a
) == b
962 /* Must be simple edge. */
963 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
965 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
966 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
967 /* If the jump insn has side effects,
968 we can't kill the edge. */
969 && (!JUMP_P (BB_END (a
))
971 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
974 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
978 block_label (basic_block block
)
980 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
983 if (!LABEL_P (BB_HEAD (block
)))
985 BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
988 return as_a
<rtx_code_label
*> (BB_HEAD (block
));
991 /* Attempt to perform edge redirection by replacing possibly complex jump
992 instruction by unconditional jump or removing jump completely. This can
993 apply only if all edges now point to the same block. The parameters and
994 return values are equivalent to redirect_edge_and_branch. */
997 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
999 basic_block src
= e
->src
;
1000 rtx_insn
*insn
= BB_END (src
), *kill_from
;
1004 /* If we are partitioning hot/cold basic blocks, we don't want to
1005 mess up unconditional or indirect jumps that cross between hot
1008 Basic block partitioning may result in some jumps that appear to
1009 be optimizable (or blocks that appear to be mergeable), but which really
1010 must be left untouched (they are required to make it safely across
1011 partition boundaries). See the comments at the top of
1012 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1014 if (BB_PARTITION (src
) != BB_PARTITION (target
))
1017 /* We can replace or remove a complex jump only when we have exactly
1018 two edges. Also, if we have exactly one outgoing edge, we can
1020 if (EDGE_COUNT (src
->succs
) >= 3
1021 /* Verify that all targets will be TARGET. Specifically, the
1022 edge that is not E must also go to TARGET. */
1023 || (EDGE_COUNT (src
->succs
) == 2
1024 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
1027 if (!onlyjump_p (insn
))
1029 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
1032 /* Avoid removing branch with side effects. */
1033 set
= single_set (insn
);
1034 if (!set
|| side_effects_p (set
))
1037 /* In case we zap a conditional jump, we'll need to kill
1038 the cc0 setter too. */
1040 if (HAVE_cc0
&& reg_mentioned_p (cc0_rtx
, PATTERN (insn
))
1041 && only_sets_cc0_p (PREV_INSN (insn
)))
1042 kill_from
= PREV_INSN (insn
);
1044 /* See if we can create the fallthru edge. */
1045 if (in_cfglayout
|| can_fallthru (src
, target
))
1048 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
1051 /* Selectively unlink whole insn chain. */
1054 rtx_insn
*insn
= BB_FOOTER (src
);
1056 delete_insn_chain (kill_from
, BB_END (src
), false);
1058 /* Remove barriers but keep jumptables. */
1061 if (BARRIER_P (insn
))
1063 if (PREV_INSN (insn
))
1064 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1066 BB_FOOTER (src
) = NEXT_INSN (insn
);
1067 if (NEXT_INSN (insn
))
1068 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1072 insn
= NEXT_INSN (insn
);
1076 delete_insn_chain (kill_from
, PREV_INSN (BB_HEAD (target
)),
1080 /* If this already is simplejump, redirect it. */
1081 else if (simplejump_p (insn
))
1083 if (e
->dest
== target
)
1086 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
1087 INSN_UID (insn
), e
->dest
->index
, target
->index
);
1088 if (!redirect_jump (as_a
<rtx_jump_insn
*> (insn
),
1089 block_label (target
), 0))
1091 gcc_assert (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1096 /* Cannot do anything for target exit block. */
1097 else if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1100 /* Or replace possibly complicated jump insn by simple jump insn. */
1103 rtx_code_label
*target_label
= block_label (target
);
1106 rtx_jump_table_data
*table
;
1108 emit_jump_insn_after_noloc (targetm
.gen_jump (target_label
), insn
);
1109 JUMP_LABEL (BB_END (src
)) = target_label
;
1110 LABEL_NUSES (target_label
)++;
1112 fprintf (dump_file
, "Replacing insn %i by jump %i\n",
1113 INSN_UID (insn
), INSN_UID (BB_END (src
)));
1116 delete_insn_chain (kill_from
, insn
, false);
1118 /* Recognize a tablejump that we are converting to a
1119 simple jump and remove its associated CODE_LABEL
1120 and ADDR_VEC or ADDR_DIFF_VEC. */
1121 if (tablejump_p (insn
, &label
, &table
))
1122 delete_insn_chain (label
, table
, false);
1124 barrier
= next_nonnote_nondebug_insn (BB_END (src
));
1125 if (!barrier
|| !BARRIER_P (barrier
))
1126 emit_barrier_after (BB_END (src
));
1129 if (barrier
!= NEXT_INSN (BB_END (src
)))
1131 /* Move the jump before barrier so that the notes
1132 which originally were or were created before jump table are
1133 inside the basic block. */
1134 rtx_insn
*new_insn
= BB_END (src
);
1136 update_bb_for_insn_chain (NEXT_INSN (BB_END (src
)),
1137 PREV_INSN (barrier
), src
);
1139 SET_NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
1140 SET_PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
1142 SET_NEXT_INSN (new_insn
) = barrier
;
1143 SET_NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
1145 SET_PREV_INSN (new_insn
) = PREV_INSN (barrier
);
1146 SET_PREV_INSN (barrier
) = new_insn
;
1151 /* Keep only one edge out and set proper flags. */
1152 if (!single_succ_p (src
))
1154 gcc_assert (single_succ_p (src
));
1156 e
= single_succ_edge (src
);
1158 e
->flags
= EDGE_FALLTHRU
;
1162 e
->probability
= profile_probability::always ();
1164 if (e
->dest
!= target
)
1165 redirect_edge_succ (e
, target
);
1169 /* Subroutine of redirect_branch_edge that tries to patch the jump
1170 instruction INSN so that it reaches block NEW. Do this
1171 only when it originally reached block OLD. Return true if this
1172 worked or the original target wasn't OLD, return false if redirection
1176 patch_jump_insn (rtx_insn
*insn
, rtx_insn
*old_label
, basic_block new_bb
)
1178 rtx_jump_table_data
*table
;
1180 /* Recognize a tablejump and adjust all matching cases. */
1181 if (tablejump_p (insn
, NULL
, &table
))
1185 rtx_code_label
*new_label
= block_label (new_bb
);
1187 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1189 vec
= table
->get_labels ();
1191 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
1192 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
1194 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
1195 --LABEL_NUSES (old_label
);
1196 ++LABEL_NUSES (new_label
);
1199 /* Handle casesi dispatch insns. */
1200 if ((tmp
= single_set (insn
)) != NULL
1201 && SET_DEST (tmp
) == pc_rtx
1202 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
1203 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
1204 && label_ref_label (XEXP (SET_SRC (tmp
), 2)) == old_label
)
1206 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
1208 --LABEL_NUSES (old_label
);
1209 ++LABEL_NUSES (new_label
);
1212 else if ((tmp
= extract_asm_operands (PATTERN (insn
))) != NULL
)
1214 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (tmp
);
1217 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1219 rtx_code_label
*new_label
= block_label (new_bb
);
1221 for (i
= 0; i
< n
; ++i
)
1223 rtx old_ref
= ASM_OPERANDS_LABEL (tmp
, i
);
1224 gcc_assert (GET_CODE (old_ref
) == LABEL_REF
);
1225 if (XEXP (old_ref
, 0) == old_label
)
1227 ASM_OPERANDS_LABEL (tmp
, i
)
1228 = gen_rtx_LABEL_REF (Pmode
, new_label
);
1229 --LABEL_NUSES (old_label
);
1230 ++LABEL_NUSES (new_label
);
1234 if (JUMP_LABEL (insn
) == old_label
)
1236 JUMP_LABEL (insn
) = new_label
;
1237 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1239 remove_note (insn
, note
);
1243 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1245 remove_note (insn
, note
);
1246 if (JUMP_LABEL (insn
) != new_label
1247 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1248 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1250 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1252 XEXP (note
, 0) = new_label
;
1256 /* ?? We may play the games with moving the named labels from
1257 one basic block to the other in case only one computed_jump is
1259 if (computed_jump_p (insn
)
1260 /* A return instruction can't be redirected. */
1261 || returnjump_p (insn
))
1264 if (!currently_expanding_to_rtl
|| JUMP_LABEL (insn
) == old_label
)
1266 /* If the insn doesn't go where we think, we're confused. */
1267 gcc_assert (JUMP_LABEL (insn
) == old_label
);
1269 /* If the substitution doesn't succeed, die. This can happen
1270 if the back end emitted unrecognizable instructions or if
1271 target is exit block on some arches. Or for crossing
1273 if (!redirect_jump (as_a
<rtx_jump_insn
*> (insn
),
1274 block_label (new_bb
), 0))
1276 gcc_assert (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
1277 || CROSSING_JUMP_P (insn
));
1286 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1289 redirect_branch_edge (edge e
, basic_block target
)
1291 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1292 basic_block src
= e
->src
;
1293 rtx_insn
*insn
= BB_END (src
);
1295 /* We can only redirect non-fallthru edges of jump insn. */
1296 if (e
->flags
& EDGE_FALLTHRU
)
1298 else if (!JUMP_P (insn
) && !currently_expanding_to_rtl
)
1301 if (!currently_expanding_to_rtl
)
1303 if (!patch_jump_insn (as_a
<rtx_jump_insn
*> (insn
), old_label
, target
))
1307 /* When expanding this BB might actually contain multiple
1308 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1309 Redirect all of those that match our label. */
1310 FOR_BB_INSNS (src
, insn
)
1311 if (JUMP_P (insn
) && !patch_jump_insn (as_a
<rtx_jump_insn
*> (insn
),
1316 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
1317 e
->src
->index
, e
->dest
->index
, target
->index
);
1319 if (e
->dest
!= target
)
1320 e
= redirect_edge_succ_nodup (e
, target
);
1325 /* Called when edge E has been redirected to a new destination,
1326 in order to update the region crossing flag on the edge and
1330 fixup_partition_crossing (edge e
)
1332 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || e
->dest
1333 == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1335 /* If we redirected an existing edge, it may already be marked
1336 crossing, even though the new src is missing a reg crossing note.
1337 But make sure reg crossing note doesn't already exist before
1339 if (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1341 e
->flags
|= EDGE_CROSSING
;
1342 if (JUMP_P (BB_END (e
->src
)))
1343 CROSSING_JUMP_P (BB_END (e
->src
)) = 1;
1345 else if (BB_PARTITION (e
->src
) == BB_PARTITION (e
->dest
))
1347 e
->flags
&= ~EDGE_CROSSING
;
1348 /* Remove the section crossing note from jump at end of
1349 src if it exists, and if no other successors are
1351 if (JUMP_P (BB_END (e
->src
)) && CROSSING_JUMP_P (BB_END (e
->src
)))
1353 bool has_crossing_succ
= false;
1356 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
1358 has_crossing_succ
|= (e2
->flags
& EDGE_CROSSING
);
1359 if (has_crossing_succ
)
1362 if (!has_crossing_succ
)
1363 CROSSING_JUMP_P (BB_END (e
->src
)) = 0;
1368 /* Called when block BB has been reassigned to the cold partition,
1369 because it is now dominated by another cold block,
1370 to ensure that the region crossing attributes are updated. */
1373 fixup_new_cold_bb (basic_block bb
)
1378 /* This is called when a hot bb is found to now be dominated
1379 by a cold bb and therefore needs to become cold. Therefore,
1380 its preds will no longer be region crossing. Any non-dominating
1381 preds that were previously hot would also have become cold
1382 in the caller for the same region. Any preds that were previously
1383 region-crossing will be adjusted in fixup_partition_crossing. */
1384 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1386 fixup_partition_crossing (e
);
1389 /* Possibly need to make bb's successor edges region crossing,
1390 or remove stale region crossing. */
1391 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1393 /* We can't have fall-through edges across partition boundaries.
1394 Note that force_nonfallthru will do any necessary partition
1395 boundary fixup by calling fixup_partition_crossing itself. */
1396 if ((e
->flags
& EDGE_FALLTHRU
)
1397 && BB_PARTITION (bb
) != BB_PARTITION (e
->dest
)
1398 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1399 force_nonfallthru (e
);
1401 fixup_partition_crossing (e
);
1405 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1406 expense of adding new instructions or reordering basic blocks.
1408 Function can be also called with edge destination equivalent to the TARGET.
1409 Then it should try the simplifications and do nothing if none is possible.
1411 Return edge representing the branch if transformation succeeded. Return NULL
1413 We still return NULL in case E already destinated TARGET and we didn't
1414 managed to simplify instruction stream. */
1417 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
1420 basic_block src
= e
->src
;
1421 basic_block dest
= e
->dest
;
1423 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1429 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
1431 df_set_bb_dirty (src
);
1432 fixup_partition_crossing (ret
);
1436 ret
= redirect_branch_edge (e
, target
);
1440 df_set_bb_dirty (src
);
1441 fixup_partition_crossing (ret
);
1445 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1448 emit_barrier_after_bb (basic_block bb
)
1450 rtx_barrier
*barrier
= emit_barrier_after (BB_END (bb
));
1451 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1452 || current_ir_type () == IR_RTL_CFGLAYOUT
);
1453 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
1455 rtx_insn
*insn
= unlink_insn_chain (barrier
, barrier
);
1459 rtx_insn
*footer_tail
= BB_FOOTER (bb
);
1461 while (NEXT_INSN (footer_tail
))
1462 footer_tail
= NEXT_INSN (footer_tail
);
1463 if (!BARRIER_P (footer_tail
))
1465 SET_NEXT_INSN (footer_tail
) = insn
;
1466 SET_PREV_INSN (insn
) = footer_tail
;
1470 BB_FOOTER (bb
) = insn
;
1474 /* Like force_nonfallthru below, but additionally performs redirection
1475 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1476 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1477 simple_return_rtx, indicating which kind of returnjump to create.
1478 It should be NULL otherwise. */
1481 force_nonfallthru_and_redirect (edge e
, basic_block target
, rtx jump_label
)
1483 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
1486 int abnormal_edge_flags
= 0;
1487 bool asm_goto_edge
= false;
1490 /* In the case the last instruction is conditional jump to the next
1491 instruction, first redirect the jump itself and then continue
1492 by creating a basic block afterwards to redirect fallthru edge. */
1493 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1494 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1495 && any_condjump_p (BB_END (e
->src
))
1496 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1499 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1502 redirected
= redirect_jump (as_a
<rtx_jump_insn
*> (BB_END (e
->src
)),
1503 block_label (target
), 0);
1504 gcc_assert (redirected
);
1506 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1509 int prob
= XINT (note
, 0);
1511 b
->probability
= profile_probability::from_reg_br_prob_note (prob
);
1512 e
->probability
-= e
->probability
;
1516 if (e
->flags
& EDGE_ABNORMAL
)
1518 /* Irritating special case - fallthru edge to the same block as abnormal
1520 We can't redirect abnormal edge, but we still can split the fallthru
1521 one and create separate abnormal edge to original destination.
1522 This allows bb-reorder to make such edge non-fallthru. */
1523 gcc_assert (e
->dest
== target
);
1524 abnormal_edge_flags
= e
->flags
& ~EDGE_FALLTHRU
;
1525 e
->flags
&= EDGE_FALLTHRU
;
1529 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1530 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1532 /* We can't redirect the entry block. Create an empty block
1533 at the start of the function which we use to add the new
1539 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
,
1540 ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1541 bb
->count
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->count
;
1543 /* Make sure new block ends up in correct hot/cold section. */
1544 BB_COPY_PARTITION (bb
, e
->dest
);
1546 /* Change the existing edge's source to be the new block, and add
1547 a new edge from the entry block to the new block. */
1549 for (ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
1550 (tmp
= ei_safe_edge (ei
)); )
1554 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
->unordered_remove (ei
.index
);
1564 vec_safe_push (bb
->succs
, e
);
1565 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
,
1570 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1571 don't point to the target or fallthru label. */
1572 if (JUMP_P (BB_END (e
->src
))
1573 && target
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1574 && (e
->flags
& EDGE_FALLTHRU
)
1575 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
1577 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
1578 bool adjust_jump_target
= false;
1580 for (i
= 0; i
< n
; ++i
)
1582 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (e
->dest
))
1584 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))--;
1585 XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) = block_label (target
);
1586 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))++;
1587 adjust_jump_target
= true;
1589 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (target
))
1590 asm_goto_edge
= true;
1592 if (adjust_jump_target
)
1594 rtx_insn
*insn
= BB_END (e
->src
);
1596 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1597 rtx_insn
*new_label
= BB_HEAD (target
);
1599 if (JUMP_LABEL (insn
) == old_label
)
1601 JUMP_LABEL (insn
) = new_label
;
1602 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1604 remove_note (insn
, note
);
1608 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1610 remove_note (insn
, note
);
1611 if (JUMP_LABEL (insn
) != new_label
1612 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1613 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1615 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1617 XEXP (note
, 0) = new_label
;
1621 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
|| asm_goto_edge
)
1624 profile_count count
= e
->count ();
1625 profile_probability probability
= e
->probability
;
1626 /* Create the new structures. */
1628 /* If the old block ended with a tablejump, skip its table
1629 by searching forward from there. Otherwise start searching
1630 forward from the last instruction of the old block. */
1631 rtx_jump_table_data
*table
;
1632 if (tablejump_p (BB_END (e
->src
), NULL
, &table
))
1635 new_head
= BB_END (e
->src
);
1636 new_head
= NEXT_INSN (new_head
);
1638 jump_block
= create_basic_block (new_head
, NULL
, e
->src
);
1639 jump_block
->count
= count
;
1641 /* Make sure new block ends up in correct hot/cold section. */
1643 BB_COPY_PARTITION (jump_block
, e
->src
);
1646 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1647 new_edge
->probability
= probability
;
1649 /* Redirect old edge. */
1650 redirect_edge_pred (e
, jump_block
);
1651 e
->probability
= profile_probability::always ();
1653 /* If e->src was previously region crossing, it no longer is
1654 and the reg crossing note should be removed. */
1655 fixup_partition_crossing (new_edge
);
1657 /* If asm goto has any label refs to target's label,
1658 add also edge from asm goto bb to target. */
1661 new_edge
->probability
= new_edge
->probability
.apply_scale (1, 2);
1662 jump_block
->count
= jump_block
->count
.apply_scale (1, 2);
1663 edge new_edge2
= make_edge (new_edge
->src
, target
,
1664 e
->flags
& ~EDGE_FALLTHRU
);
1665 new_edge2
->probability
= probability
- new_edge
->probability
;
1668 new_bb
= jump_block
;
1671 jump_block
= e
->src
;
1673 loc
= e
->goto_locus
;
1674 e
->flags
&= ~EDGE_FALLTHRU
;
1675 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1677 if (jump_label
== ret_rtx
)
1678 emit_jump_insn_after_setloc (targetm
.gen_return (),
1679 BB_END (jump_block
), loc
);
1682 gcc_assert (jump_label
== simple_return_rtx
);
1683 emit_jump_insn_after_setloc (targetm
.gen_simple_return (),
1684 BB_END (jump_block
), loc
);
1686 set_return_jump_label (BB_END (jump_block
));
1690 rtx_code_label
*label
= block_label (target
);
1691 emit_jump_insn_after_setloc (targetm
.gen_jump (label
),
1692 BB_END (jump_block
), loc
);
1693 JUMP_LABEL (BB_END (jump_block
)) = label
;
1694 LABEL_NUSES (label
)++;
1697 /* We might be in cfg layout mode, and if so, the following routine will
1698 insert the barrier correctly. */
1699 emit_barrier_after_bb (jump_block
);
1700 redirect_edge_succ_nodup (e
, target
);
1702 if (abnormal_edge_flags
)
1703 make_edge (src
, target
, abnormal_edge_flags
);
1705 df_mark_solutions_dirty ();
1706 fixup_partition_crossing (e
);
1710 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1711 (and possibly create new basic block) to make edge non-fallthru.
1712 Return newly created BB or NULL if none. */
1715 rtl_force_nonfallthru (edge e
)
1717 return force_nonfallthru_and_redirect (e
, e
->dest
, NULL_RTX
);
1720 /* Redirect edge even at the expense of creating new jump insn or
1721 basic block. Return new basic block if created, NULL otherwise.
1722 Conversion must be possible. */
1725 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1727 if (redirect_edge_and_branch (e
, target
)
1728 || e
->dest
== target
)
1731 /* In case the edge redirection failed, try to force it to be non-fallthru
1732 and redirect newly created simplejump. */
1733 df_set_bb_dirty (e
->src
);
1734 return force_nonfallthru_and_redirect (e
, target
, NULL_RTX
);
1737 /* The given edge should potentially be a fallthru edge. If that is in
1738 fact true, delete the jump and barriers that are in the way. */
1741 rtl_tidy_fallthru_edge (edge e
)
1744 basic_block b
= e
->src
, c
= b
->next_bb
;
1746 /* ??? In a late-running flow pass, other folks may have deleted basic
1747 blocks by nopping out blocks, leaving multiple BARRIERs between here
1748 and the target label. They ought to be chastised and fixed.
1750 We can also wind up with a sequence of undeletable labels between
1751 one block and the next.
1753 So search through a sequence of barriers, labels, and notes for
1754 the head of block C and assert that we really do fall through. */
1756 for (q
= NEXT_INSN (BB_END (b
)); q
!= BB_HEAD (c
); q
= NEXT_INSN (q
))
1757 if (NONDEBUG_INSN_P (q
))
1760 /* Remove what will soon cease being the jump insn from the source block.
1761 If block B consisted only of this single jump, turn it into a deleted
1766 && (any_uncondjump_p (q
)
1767 || single_succ_p (b
)))
1770 rtx_jump_table_data
*table
;
1772 if (tablejump_p (q
, &label
, &table
))
1774 /* The label is likely mentioned in some instruction before
1775 the tablejump and might not be DCEd, so turn it into
1776 a note instead and move before the tablejump that is going to
1778 const char *name
= LABEL_NAME (label
);
1779 PUT_CODE (label
, NOTE
);
1780 NOTE_KIND (label
) = NOTE_INSN_DELETED_LABEL
;
1781 NOTE_DELETED_LABEL_NAME (label
) = name
;
1782 reorder_insns (label
, label
, PREV_INSN (q
));
1783 delete_insn (table
);
1786 /* If this was a conditional jump, we need to also delete
1787 the insn that set cc0. */
1788 if (HAVE_cc0
&& any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1793 /* Unconditional jumps with side-effects (i.e. which we can't just delete
1794 together with the barrier) should never have a fallthru edge. */
1795 else if (JUMP_P (q
) && any_uncondjump_p (q
))
1798 /* Selectively unlink the sequence. */
1799 if (q
!= PREV_INSN (BB_HEAD (c
)))
1800 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1802 e
->flags
|= EDGE_FALLTHRU
;
1805 /* Should move basic block BB after basic block AFTER. NIY. */
1808 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1809 basic_block after ATTRIBUTE_UNUSED
)
1814 /* Locate the last bb in the same partition as START_BB. */
1817 last_bb_in_partition (basic_block start_bb
)
1820 FOR_BB_BETWEEN (bb
, start_bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1822 if (BB_PARTITION (start_bb
) != BB_PARTITION (bb
->next_bb
))
1825 /* Return bb before the exit block. */
1829 /* Split a (typically critical) edge. Return the new block.
1830 The edge must not be abnormal.
1832 ??? The code generally expects to be called on critical edges.
1833 The case of a block ending in an unconditional jump to a
1834 block with multiple predecessors is not handled optimally. */
1837 rtl_split_edge (edge edge_in
)
1839 basic_block bb
, new_bb
;
1842 /* Abnormal edges cannot be split. */
1843 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1845 /* We are going to place the new block in front of edge destination.
1846 Avoid existence of fallthru predecessors. */
1847 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1849 edge e
= find_fallthru_edge (edge_in
->dest
->preds
);
1852 force_nonfallthru (e
);
1855 /* Create the basic block note. */
1856 if (edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1857 before
= BB_HEAD (edge_in
->dest
);
1861 /* If this is a fall through edge to the exit block, the blocks might be
1862 not adjacent, and the right place is after the source. */
1863 if ((edge_in
->flags
& EDGE_FALLTHRU
)
1864 && edge_in
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1866 before
= NEXT_INSN (BB_END (edge_in
->src
));
1867 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1868 BB_COPY_PARTITION (bb
, edge_in
->src
);
1872 if (edge_in
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1874 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1875 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1879 basic_block after
= edge_in
->dest
->prev_bb
;
1880 /* If this is post-bb reordering, and the edge crosses a partition
1881 boundary, the new block needs to be inserted in the bb chain
1882 at the end of the src partition (since we put the new bb into
1883 that partition, see below). Otherwise we may end up creating
1884 an extra partition crossing in the chain, which is illegal.
1885 It can't go after the src, because src may have a fall-through
1886 to a different block. */
1887 if (crtl
->bb_reorder_complete
1888 && (edge_in
->flags
& EDGE_CROSSING
))
1890 after
= last_bb_in_partition (edge_in
->src
);
1891 before
= get_last_bb_insn (after
);
1892 /* The instruction following the last bb in partition should
1893 be a barrier, since it cannot end in a fall-through. */
1894 gcc_checking_assert (BARRIER_P (before
));
1895 before
= NEXT_INSN (before
);
1897 bb
= create_basic_block (before
, NULL
, after
);
1898 /* Put the split bb into the src partition, to avoid creating
1899 a situation where a cold bb dominates a hot bb, in the case
1900 where src is cold and dest is hot. The src will dominate
1901 the new bb (whereas it might not have dominated dest). */
1902 BB_COPY_PARTITION (bb
, edge_in
->src
);
1906 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1908 /* Can't allow a region crossing edge to be fallthrough. */
1909 if (BB_PARTITION (bb
) != BB_PARTITION (edge_in
->dest
)
1910 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1912 new_bb
= force_nonfallthru (single_succ_edge (bb
));
1913 gcc_assert (!new_bb
);
1916 /* For non-fallthru edges, we must adjust the predecessor's
1917 jump instruction to target our new block. */
1918 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1920 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1921 gcc_assert (redirected
);
1925 if (edge_in
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1927 /* For asm goto even splitting of fallthru edge might
1928 need insn patching, as other labels might point to the
1930 rtx_insn
*last
= BB_END (edge_in
->src
);
1933 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1934 && (extract_asm_operands (PATTERN (last
))
1935 || JUMP_LABEL (last
) == before
)
1936 && patch_jump_insn (last
, before
, bb
))
1937 df_set_bb_dirty (edge_in
->src
);
1939 redirect_edge_succ (edge_in
, bb
);
1945 /* Queue instructions for insertion on an edge between two basic blocks.
1946 The new instructions and basic blocks (if any) will not appear in the
1947 CFG until commit_edge_insertions is called. */
1950 insert_insn_on_edge (rtx pattern
, edge e
)
1952 /* We cannot insert instructions on an abnormal critical edge.
1953 It will be easier to find the culprit if we die now. */
1954 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1956 if (e
->insns
.r
== NULL_RTX
)
1959 push_to_sequence (e
->insns
.r
);
1961 emit_insn (pattern
);
1963 e
->insns
.r
= get_insns ();
1967 /* Update the CFG for the instructions queued on edge E. */
1970 commit_one_edge_insertion (edge e
)
1972 rtx_insn
*before
= NULL
, *after
= NULL
, *insns
, *tmp
, *last
;
1975 /* Pull the insns off the edge now since the edge might go away. */
1979 /* Figure out where to put these insns. If the destination has
1980 one predecessor, insert there. Except for the exit block. */
1981 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1985 /* Get the location correct wrt a code label, and "nice" wrt
1986 a basic block note, and before everything else. */
1989 tmp
= NEXT_INSN (tmp
);
1990 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1991 tmp
= NEXT_INSN (tmp
);
1992 if (tmp
== BB_HEAD (bb
))
1995 after
= PREV_INSN (tmp
);
1997 after
= get_last_insn ();
2000 /* If the source has one successor and the edge is not abnormal,
2001 insert there. Except for the entry block.
2002 Don't do this if the predecessor ends in a jump other than
2003 unconditional simple jump. E.g. for asm goto that points all
2004 its labels at the fallthru basic block, we can't insert instructions
2005 before the asm goto, as the asm goto can have various of side effects,
2006 and can't emit instructions after the asm goto, as it must end
2008 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
2009 && single_succ_p (e
->src
)
2010 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2011 && (!JUMP_P (BB_END (e
->src
))
2012 || simplejump_p (BB_END (e
->src
))))
2016 /* It is possible to have a non-simple jump here. Consider a target
2017 where some forms of unconditional jumps clobber a register. This
2018 happens on the fr30 for example.
2020 We know this block has a single successor, so we can just emit
2021 the queued insns before the jump. */
2022 if (JUMP_P (BB_END (bb
)))
2023 before
= BB_END (bb
);
2026 /* We'd better be fallthru, or we've lost track of what's what. */
2027 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
2029 after
= BB_END (bb
);
2033 /* Otherwise we must split the edge. */
2036 bb
= split_edge (e
);
2038 /* If E crossed a partition boundary, we needed to make bb end in
2039 a region-crossing jump, even though it was originally fallthru. */
2040 if (JUMP_P (BB_END (bb
)))
2041 before
= BB_END (bb
);
2043 after
= BB_END (bb
);
2046 /* Now that we've found the spot, do the insertion. */
2049 emit_insn_before_noloc (insns
, before
, bb
);
2050 last
= prev_nonnote_insn (before
);
2053 last
= emit_insn_after_noloc (insns
, after
, bb
);
2055 if (returnjump_p (last
))
2057 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2058 This is not currently a problem because this only happens
2059 for the (single) epilogue, which already has a fallthru edge
2062 e
= single_succ_edge (bb
);
2063 gcc_assert (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2064 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
2066 e
->flags
&= ~EDGE_FALLTHRU
;
2067 emit_barrier_after (last
);
2070 delete_insn (before
);
2073 gcc_assert (!JUMP_P (last
));
2076 /* Update the CFG for all queued instructions. */
2079 commit_edge_insertions (void)
2083 /* Optimization passes that invoke this routine can cause hot blocks
2084 previously reached by both hot and cold blocks to become dominated only
2085 by cold blocks. This will cause the verification below to fail,
2086 and lead to now cold code in the hot section. In some cases this
2087 may only be visible after newly unreachable blocks are deleted,
2088 which will be done by fixup_partitions. */
2089 fixup_partitions ();
2091 checking_verify_flow_info ();
2093 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
2094 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
2099 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2101 commit_one_edge_insertion (e
);
2106 /* Print out RTL-specific basic block information (live information
2107 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2108 documented in dumpfile.h. */
2111 rtl_dump_bb (FILE *outf
, basic_block bb
, int indent
, dump_flags_t flags
)
2115 s_indent
= (char *) alloca ((size_t) indent
+ 1);
2116 memset (s_indent
, ' ', (size_t) indent
);
2117 s_indent
[indent
] = '\0';
2119 if (df
&& (flags
& TDF_DETAILS
))
2121 df_dump_top (bb
, outf
);
2125 if (bb
->index
!= ENTRY_BLOCK
&& bb
->index
!= EXIT_BLOCK
)
2127 rtx_insn
*last
= BB_END (bb
);
2129 last
= NEXT_INSN (last
);
2130 for (rtx_insn
*insn
= BB_HEAD (bb
); insn
!= last
; insn
= NEXT_INSN (insn
))
2132 if (flags
& TDF_DETAILS
)
2133 df_dump_insn_top (insn
, outf
);
2134 if (! (flags
& TDF_SLIM
))
2135 print_rtl_single (outf
, insn
);
2137 dump_insn_slim (outf
, insn
);
2138 if (flags
& TDF_DETAILS
)
2139 df_dump_insn_bottom (insn
, outf
);
2143 if (df
&& (flags
& TDF_DETAILS
))
2145 df_dump_bottom (bb
, outf
);
2151 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2152 for the start of each basic block. FLAGS are the TDF_* masks documented
2156 print_rtl_with_bb (FILE *outf
, const rtx_insn
*rtx_first
, dump_flags_t flags
)
2158 const rtx_insn
*tmp_rtx
;
2160 fprintf (outf
, "(nil)\n");
2163 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
2164 int max_uid
= get_max_uid ();
2165 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
2166 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
2167 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
2170 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2171 insns, but the CFG is not maintained so the basic block info
2172 is not reliable. Therefore it's omitted from the dumps. */
2173 if (! (cfun
->curr_properties
& PROP_cfg
))
2174 flags
&= ~TDF_BLOCKS
;
2177 df_dump_start (outf
);
2179 if (flags
& TDF_BLOCKS
)
2181 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2185 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
2186 end
[INSN_UID (BB_END (bb
))] = bb
;
2187 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
2189 enum bb_state state
= IN_MULTIPLE_BB
;
2191 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
2193 in_bb_p
[INSN_UID (x
)] = state
;
2195 if (x
== BB_END (bb
))
2201 for (tmp_rtx
= rtx_first
; tmp_rtx
!= NULL
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
2203 if (flags
& TDF_BLOCKS
)
2205 bb
= start
[INSN_UID (tmp_rtx
)];
2208 dump_bb_info (outf
, bb
, 0, dump_flags
, true, false);
2209 if (df
&& (flags
& TDF_DETAILS
))
2210 df_dump_top (bb
, outf
);
2213 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
2214 && !NOTE_P (tmp_rtx
)
2215 && !BARRIER_P (tmp_rtx
))
2216 fprintf (outf
, ";; Insn is not within a basic block\n");
2217 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
2218 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
2221 if (flags
& TDF_DETAILS
)
2222 df_dump_insn_top (tmp_rtx
, outf
);
2223 if (! (flags
& TDF_SLIM
))
2224 print_rtl_single (outf
, tmp_rtx
);
2226 dump_insn_slim (outf
, tmp_rtx
);
2227 if (flags
& TDF_DETAILS
)
2228 df_dump_insn_bottom (tmp_rtx
, outf
);
2230 if (flags
& TDF_BLOCKS
)
2232 bb
= end
[INSN_UID (tmp_rtx
)];
2235 dump_bb_info (outf
, bb
, 0, dump_flags
, false, true);
2236 if (df
&& (flags
& TDF_DETAILS
))
2237 df_dump_bottom (bb
, outf
);
2249 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2252 update_br_prob_note (basic_block bb
)
2255 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
2256 if (!JUMP_P (BB_END (bb
)) || !BRANCH_EDGE (bb
)->probability
.initialized_p ())
2260 rtx
*note_link
, this_rtx
;
2262 note_link
= ®_NOTES (BB_END (bb
));
2263 for (this_rtx
= *note_link
; this_rtx
; this_rtx
= XEXP (this_rtx
, 1))
2264 if (this_rtx
== note
)
2266 *note_link
= XEXP (this_rtx
, 1);
2273 || XINT (note
, 0) == BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ())
2275 XINT (note
, 0) = BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ();
2278 /* Get the last insn associated with block BB (that includes barriers and
2279 tablejumps after BB). */
2281 get_last_bb_insn (basic_block bb
)
2283 rtx_jump_table_data
*table
;
2285 rtx_insn
*end
= BB_END (bb
);
2287 /* Include any jump table following the basic block. */
2288 if (tablejump_p (end
, NULL
, &table
))
2291 /* Include any barriers that may follow the basic block. */
2292 tmp
= next_nonnote_nondebug_insn_bb (end
);
2293 while (tmp
&& BARRIER_P (tmp
))
2296 tmp
= next_nonnote_nondebug_insn_bb (end
);
2302 /* Add all BBs reachable from entry via hot paths into the SET. */
2305 find_bbs_reachable_by_hot_paths (hash_set
<basic_block
> *set
)
2307 auto_vec
<basic_block
, 64> worklist
;
2309 set
->add (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
2310 worklist
.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
2312 while (worklist
.length () > 0)
2314 basic_block bb
= worklist
.pop ();
2318 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2319 if (BB_PARTITION (e
->dest
) != BB_COLD_PARTITION
2320 && !set
->add (e
->dest
))
2321 worklist
.safe_push (e
->dest
);
2325 /* Sanity check partition hotness to ensure that basic blocks in
2326 Â the cold partition don't dominate basic blocks in the hot partition.
2327 If FLAG_ONLY is true, report violations as errors. Otherwise
2328 re-mark the dominated blocks as cold, since this is run after
2329 cfg optimizations that may make hot blocks previously reached
2330 by both hot and cold blocks now only reachable along cold paths. */
2332 static vec
<basic_block
>
2333 find_partition_fixes (bool flag_only
)
2336 vec
<basic_block
> bbs_in_cold_partition
= vNULL
;
2337 vec
<basic_block
> bbs_to_fix
= vNULL
;
2338 hash_set
<basic_block
> set
;
2340 /* Callers check this. */
2341 gcc_checking_assert (crtl
->has_bb_partition
);
2343 find_bbs_reachable_by_hot_paths (&set
);
2345 FOR_EACH_BB_FN (bb
, cfun
)
2346 if (!set
.contains (bb
)
2347 && BB_PARTITION (bb
) != BB_COLD_PARTITION
)
2350 error ("non-cold basic block %d reachable only "
2351 "by paths crossing the cold partition", bb
->index
);
2353 BB_SET_PARTITION (bb
, BB_COLD_PARTITION
);
2354 bbs_to_fix
.safe_push (bb
);
2355 bbs_in_cold_partition
.safe_push (bb
);
2361 /* Perform cleanup on the hot/cold bb partitioning after optimization
2362 passes that modify the cfg. */
2365 fixup_partitions (void)
2369 if (!crtl
->has_bb_partition
)
2372 /* Delete any blocks that became unreachable and weren't
2373 already cleaned up, for example during edge forwarding
2374 and convert_jumps_to_returns. This will expose more
2375 opportunities for fixing the partition boundaries here.
2376 Also, the calculation of the dominance graph during verification
2377 will assert if there are unreachable nodes. */
2378 delete_unreachable_blocks ();
2380 /* If there are partitions, do a sanity check on them: A basic block in
2381 Â a cold partition cannot dominate a basic block in a hot partition.
2382 Fixup any that now violate this requirement, as a result of edge
2383 forwarding and unreachable block deletion. Â */
2384 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (false);
2386 /* Do the partition fixup after all necessary blocks have been converted to
2387 cold, so that we only update the region crossings the minimum number of
2388 places, which can require forcing edges to be non fallthru. */
2389 while (! bbs_to_fix
.is_empty ())
2391 bb
= bbs_to_fix
.pop ();
2392 fixup_new_cold_bb (bb
);
2396 /* Verify, in the basic block chain, that there is at most one switch
2397 between hot/cold partitions. This condition will not be true until
2398 after reorder_basic_blocks is called. */
2401 verify_hot_cold_block_grouping (void)
2405 bool switched_sections
= false;
2406 int current_partition
= BB_UNPARTITIONED
;
2408 /* Even after bb reordering is complete, we go into cfglayout mode
2409 again (in compgoto). Ensure we don't call this before going back
2410 into linearized RTL when any layout fixes would have been committed. */
2411 if (!crtl
->bb_reorder_complete
2412 || current_ir_type () != IR_RTL_CFGRTL
)
2415 FOR_EACH_BB_FN (bb
, cfun
)
2417 if (current_partition
!= BB_UNPARTITIONED
2418 && BB_PARTITION (bb
) != current_partition
)
2420 if (switched_sections
)
2422 error ("multiple hot/cold transitions found (bb %i)",
2427 switched_sections
= true;
2429 if (!crtl
->has_bb_partition
)
2430 error ("partition found but function partition flag not set");
2432 current_partition
= BB_PARTITION (bb
);
2439 /* Perform several checks on the edges out of each block, such as
2440 the consistency of the branch probabilities, the correctness
2441 of hot/cold partition crossing edges, and the number of expected
2442 successor edges. Also verify that the dominance relationship
2443 between hot/cold blocks is sane. */
2446 rtl_verify_edges (void)
2451 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2453 int n_fallthru
= 0, n_branch
= 0, n_abnormal_call
= 0, n_sibcall
= 0;
2454 int n_eh
= 0, n_abnormal
= 0;
2455 edge e
, fallthru
= NULL
;
2458 bool has_crossing_edge
= false;
2460 if (JUMP_P (BB_END (bb
))
2461 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
2462 && EDGE_COUNT (bb
->succs
) >= 2
2463 && any_condjump_p (BB_END (bb
)))
2465 if (!BRANCH_EDGE (bb
)->probability
.initialized_p ())
2467 if (profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2469 error ("verify_flow_info: "
2470 "REG_BR_PROB is set but cfg probability is not");
2474 else if (XINT (note
, 0)
2475 != BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ()
2476 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2478 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2480 BRANCH_EDGE (bb
)->probability
.to_reg_br_prob_note ());
2485 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2489 if (e
->flags
& EDGE_FALLTHRU
)
2490 n_fallthru
++, fallthru
= e
;
2492 is_crossing
= (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
2493 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2494 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
2495 has_crossing_edge
|= is_crossing
;
2496 if (e
->flags
& EDGE_CROSSING
)
2500 error ("EDGE_CROSSING incorrectly set across same section");
2503 if (e
->flags
& EDGE_FALLTHRU
)
2505 error ("fallthru edge crosses section boundary in bb %i",
2509 if (e
->flags
& EDGE_EH
)
2511 error ("EH edge crosses section boundary in bb %i",
2515 if (JUMP_P (BB_END (bb
)) && !CROSSING_JUMP_P (BB_END (bb
)))
2517 error ("No region crossing jump at section boundary in bb %i",
2522 else if (is_crossing
)
2524 error ("EDGE_CROSSING missing across section boundary");
2528 if ((e
->flags
& ~(EDGE_DFS_BACK
2530 | EDGE_IRREDUCIBLE_LOOP
2533 | EDGE_PRESERVE
)) == 0)
2536 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2539 if (e
->flags
& EDGE_SIBCALL
)
2542 if (e
->flags
& EDGE_EH
)
2545 if (e
->flags
& EDGE_ABNORMAL
)
2549 if (!has_crossing_edge
2550 && JUMP_P (BB_END (bb
))
2551 && CROSSING_JUMP_P (BB_END (bb
)))
2553 print_rtl_with_bb (stderr
, get_insns (), TDF_BLOCKS
| TDF_DETAILS
);
2554 error ("Region crossing jump across same section in bb %i",
2559 if (n_eh
&& !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
2561 error ("missing REG_EH_REGION note at the end of bb %i", bb
->index
);
2566 error ("too many exception handling edges in bb %i", bb
->index
);
2570 && (!JUMP_P (BB_END (bb
))
2571 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
2572 || any_condjump_p (BB_END (bb
))))))
2574 error ("too many outgoing branch edges from bb %i", bb
->index
);
2577 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
2579 error ("fallthru edge after unconditional jump in bb %i", bb
->index
);
2582 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
2584 error ("wrong number of branch edges after unconditional jump"
2585 " in bb %i", bb
->index
);
2588 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
2589 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
2591 error ("wrong amount of branch edges after conditional jump"
2592 " in bb %i", bb
->index
);
2595 if (n_abnormal_call
&& !CALL_P (BB_END (bb
)))
2597 error ("abnormal call edges for non-call insn in bb %i", bb
->index
);
2600 if (n_sibcall
&& !CALL_P (BB_END (bb
)))
2602 error ("sibcall edges for non-call insn in bb %i", bb
->index
);
2605 if (n_abnormal
> n_eh
2606 && !(CALL_P (BB_END (bb
))
2607 && n_abnormal
== n_abnormal_call
+ n_sibcall
)
2608 && (!JUMP_P (BB_END (bb
))
2609 || any_condjump_p (BB_END (bb
))
2610 || any_uncondjump_p (BB_END (bb
))))
2612 error ("abnormal edges for no purpose in bb %i", bb
->index
);
2617 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2620 has_eh
= (e
->flags
& EDGE_EH
);
2621 if ((e
->flags
& EDGE_EH
) == has_eh
)
2623 error ("EH incoming edge mixed with non-EH incoming edges "
2624 "in bb %i", bb
->index
);
2630 /* If there are partitions, do a sanity check on them: A basic block in
2631 Â a cold partition cannot dominate a basic block in a hot partition. Â */
2632 if (crtl
->has_bb_partition
&& !err
2633 && current_ir_type () == IR_RTL_CFGLAYOUT
)
2635 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (true);
2636 err
= !bbs_to_fix
.is_empty ();
2643 /* Checks on the instructions within blocks. Currently checks that each
2644 block starts with a basic block note, and that basic block notes and
2645 control flow jumps are not found in the middle of the block. */
2648 rtl_verify_bb_insns (void)
2654 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2656 /* Now check the header of basic
2657 block. It ought to contain optional CODE_LABEL followed
2658 by NOTE_BASIC_BLOCK. */
2662 if (BB_END (bb
) == x
)
2664 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2672 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2674 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2679 if (BB_END (bb
) == x
)
2680 /* Do checks for empty blocks here. */
2683 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2685 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2687 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2688 INSN_UID (x
), bb
->index
);
2692 if (x
== BB_END (bb
))
2695 if (control_flow_insn_p (x
))
2697 error ("in basic block %d:", bb
->index
);
2698 fatal_insn ("flow control insn inside a basic block", x
);
2707 /* Verify that block pointers for instructions in basic blocks, headers and
2708 footers are set appropriately. */
2711 rtl_verify_bb_pointers (void)
2716 /* Check the general integrity of the basic blocks. */
2717 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2721 if (!(bb
->flags
& BB_RTL
))
2723 error ("BB_RTL flag not set for block %d", bb
->index
);
2727 FOR_BB_INSNS (bb
, insn
)
2728 if (BLOCK_FOR_INSN (insn
) != bb
)
2730 error ("insn %d basic block pointer is %d, should be %d",
2732 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
2737 for (insn
= BB_HEADER (bb
); insn
; insn
= NEXT_INSN (insn
))
2738 if (!BARRIER_P (insn
)
2739 && BLOCK_FOR_INSN (insn
) != NULL
)
2741 error ("insn %d in header of bb %d has non-NULL basic block",
2742 INSN_UID (insn
), bb
->index
);
2745 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
2746 if (!BARRIER_P (insn
)
2747 && BLOCK_FOR_INSN (insn
) != NULL
)
2749 error ("insn %d in footer of bb %d has non-NULL basic block",
2750 INSN_UID (insn
), bb
->index
);
2759 /* Verify the CFG and RTL consistency common for both underlying RTL and
2762 Currently it does following checks:
2764 - overlapping of basic blocks
2765 - insns with wrong BLOCK_FOR_INSN pointers
2766 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2767 - tails of basic blocks (ensure that boundary is necessary)
2768 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2769 and NOTE_INSN_BASIC_BLOCK
2770 - verify that no fall_thru edge crosses hot/cold partition boundaries
2771 - verify that there are no pending RTL branch predictions
2772 - verify that hot blocks are not dominated by cold blocks
2774 In future it can be extended check a lot of other stuff as well
2775 (reachability of basic blocks, life information, etc. etc.). */
2778 rtl_verify_flow_info_1 (void)
2782 err
|= rtl_verify_bb_pointers ();
2784 err
|= rtl_verify_bb_insns ();
2786 err
|= rtl_verify_edges ();
2791 /* Walk the instruction chain and verify that bb head/end pointers
2792 are correct, and that instructions are in exactly one bb and have
2793 correct block pointers. */
2796 rtl_verify_bb_insn_chain (void)
2801 rtx_insn
*last_head
= get_last_insn ();
2802 basic_block
*bb_info
;
2803 const int max_uid
= get_max_uid ();
2805 bb_info
= XCNEWVEC (basic_block
, max_uid
);
2807 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2809 rtx_insn
*head
= BB_HEAD (bb
);
2810 rtx_insn
*end
= BB_END (bb
);
2812 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2814 /* Verify the end of the basic block is in the INSN chain. */
2818 /* And that the code outside of basic blocks has NULL bb field. */
2820 && BLOCK_FOR_INSN (x
) != NULL
)
2822 error ("insn %d outside of basic blocks has non-NULL bb field",
2830 error ("end insn %d for block %d not found in the insn stream",
2831 INSN_UID (end
), bb
->index
);
2835 /* Work backwards from the end to the head of the basic block
2836 to verify the head is in the RTL chain. */
2837 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2839 /* While walking over the insn chain, verify insns appear
2840 in only one basic block. */
2841 if (bb_info
[INSN_UID (x
)] != NULL
)
2843 error ("insn %d is in multiple basic blocks (%d and %d)",
2844 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2848 bb_info
[INSN_UID (x
)] = bb
;
2855 error ("head insn %d for block %d not found in the insn stream",
2856 INSN_UID (head
), bb
->index
);
2860 last_head
= PREV_INSN (x
);
2863 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2865 /* Check that the code before the first basic block has NULL
2868 && BLOCK_FOR_INSN (x
) != NULL
)
2870 error ("insn %d outside of basic blocks has non-NULL bb field",
2880 /* Verify that fallthru edges point to adjacent blocks in layout order and
2881 that barriers exist after non-fallthru blocks. */
2884 rtl_verify_fallthru (void)
2889 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2893 e
= find_fallthru_edge (bb
->succs
);
2898 /* Ensure existence of barrier in BB with no fallthru edges. */
2899 for (insn
= NEXT_INSN (BB_END (bb
)); ; insn
= NEXT_INSN (insn
))
2901 if (!insn
|| NOTE_INSN_BASIC_BLOCK_P (insn
))
2903 error ("missing barrier after block %i", bb
->index
);
2907 if (BARRIER_P (insn
))
2911 else if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2912 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2916 if (e
->src
->next_bb
!= e
->dest
)
2919 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2920 e
->src
->index
, e
->dest
->index
);
2924 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
2925 insn
= NEXT_INSN (insn
))
2926 if (BARRIER_P (insn
) || NONDEBUG_INSN_P (insn
))
2928 error ("verify_flow_info: Incorrect fallthru %i->%i",
2929 e
->src
->index
, e
->dest
->index
);
2930 fatal_insn ("wrong insn in the fallthru edge", insn
);
2939 /* Verify that blocks are laid out in consecutive order. While walking the
2940 instructions, verify that all expected instructions are inside the basic
2941 blocks, and that all returns are followed by barriers. */
2944 rtl_verify_bb_layout (void)
2950 rtx_insn
* const rtx_first
= get_insns ();
2951 basic_block last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
), curr_bb
= NULL
;
2954 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
2956 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2958 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2960 bb
= NOTE_BASIC_BLOCK (x
);
2963 if (bb
!= last_bb_seen
->next_bb
)
2964 internal_error ("basic blocks not laid down consecutively");
2966 curr_bb
= last_bb_seen
= bb
;
2971 switch (GET_CODE (x
))
2978 /* An ADDR_VEC is placed outside any basic block. */
2980 && JUMP_TABLE_DATA_P (NEXT_INSN (x
)))
2983 /* But in any case, non-deletable labels can appear anywhere. */
2987 fatal_insn ("insn outside basic block", x
);
2992 && returnjump_p (x
) && ! condjump_p (x
)
2993 && ! ((y
= next_nonnote_nondebug_insn (x
))
2995 fatal_insn ("return not followed by barrier", x
);
2997 if (curr_bb
&& x
== BB_END (curr_bb
))
3001 if (num_bb_notes
!= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
)
3003 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
3004 num_bb_notes
, n_basic_blocks_for_fn (cfun
));
3009 /* Verify the CFG and RTL consistency common for both underlying RTL and
3010 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
3012 Currently it does following checks:
3013 - all checks of rtl_verify_flow_info_1
3014 - test head/end pointers
3015 - check that blocks are laid out in consecutive order
3016 - check that all insns are in the basic blocks
3017 (except the switch handling code, barriers and notes)
3018 - check that all returns are followed by barriers
3019 - check that all fallthru edge points to the adjacent blocks
3020 - verify that there is a single hot/cold partition boundary after bbro */
3023 rtl_verify_flow_info (void)
3027 err
|= rtl_verify_flow_info_1 ();
3029 err
|= rtl_verify_bb_insn_chain ();
3031 err
|= rtl_verify_fallthru ();
3033 err
|= rtl_verify_bb_layout ();
3035 err
|= verify_hot_cold_block_grouping ();
3040 /* Assume that the preceding pass has possibly eliminated jump instructions
3041 or converted the unconditional jumps. Eliminate the edges from CFG.
3042 Return true if any edges are eliminated. */
3045 purge_dead_edges (basic_block bb
)
3048 rtx_insn
*insn
= BB_END (bb
);
3050 bool purged
= false;
3054 if (DEBUG_INSN_P (insn
) && insn
!= BB_HEAD (bb
))
3056 insn
= PREV_INSN (insn
);
3057 while ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
));
3059 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3060 if (NONJUMP_INSN_P (insn
)
3061 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
3065 if (! may_trap_p (PATTERN (insn
))
3066 || ((eqnote
= find_reg_equal_equiv_note (insn
))
3067 && ! may_trap_p (XEXP (eqnote
, 0))))
3068 remove_note (insn
, note
);
3071 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3072 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3074 bool remove
= false;
3076 /* There are three types of edges we need to handle correctly here: EH
3077 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3078 latter can appear when nonlocal gotos are used. */
3079 if (e
->flags
& EDGE_ABNORMAL_CALL
)
3083 else if (can_nonlocal_goto (insn
))
3085 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3087 else if (flag_tm
&& find_reg_note (insn
, REG_TM
, NULL
))
3092 else if (e
->flags
& EDGE_EH
)
3093 remove
= !can_throw_internal (insn
);
3098 df_set_bb_dirty (bb
);
3111 /* We do care only about conditional jumps and simplejumps. */
3112 if (!any_condjump_p (insn
)
3113 && !returnjump_p (insn
)
3114 && !simplejump_p (insn
))
3117 /* Branch probability/prediction notes are defined only for
3118 condjumps. We've possibly turned condjump into simplejump. */
3119 if (simplejump_p (insn
))
3121 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3123 remove_note (insn
, note
);
3124 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
3125 remove_note (insn
, note
);
3128 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3130 /* Avoid abnormal flags to leak from computed jumps turned
3131 into simplejumps. */
3133 e
->flags
&= ~EDGE_ABNORMAL
;
3135 /* See if this edge is one we should keep. */
3136 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
3137 /* A conditional jump can fall through into the next
3138 block, so we should keep the edge. */
3143 else if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3144 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
3145 /* If the destination block is the target of the jump,
3151 else if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
3152 && returnjump_p (insn
))
3153 /* If the destination block is the exit block, and this
3154 instruction is a return, then keep the edge. */
3159 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3160 /* Keep the edges that correspond to exceptions thrown by
3161 this instruction and rematerialize the EDGE_ABNORMAL
3162 flag we just cleared above. */
3164 e
->flags
|= EDGE_ABNORMAL
;
3169 /* We do not need this edge. */
3170 df_set_bb_dirty (bb
);
3175 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
3179 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
3184 /* Redistribute probabilities. */
3185 if (single_succ_p (bb
))
3187 single_succ_edge (bb
)->probability
= profile_probability::always ();
3191 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3195 b
= BRANCH_EDGE (bb
);
3196 f
= FALLTHRU_EDGE (bb
);
3197 b
->probability
= profile_probability::from_reg_br_prob_note
3199 f
->probability
= b
->probability
.invert ();
3204 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
3206 /* First, there should not be any EH or ABCALL edges resulting
3207 from non-local gotos and the like. If there were, we shouldn't
3208 have created the sibcall in the first place. Second, there
3209 should of course never have been a fallthru edge. */
3210 gcc_assert (single_succ_p (bb
));
3211 gcc_assert (single_succ_edge (bb
)->flags
3212 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
3217 /* If we don't see a jump insn, we don't know exactly why the block would
3218 have been broken at this point. Look for a simple, non-fallthru edge,
3219 as these are only created by conditional branches. If we find such an
3220 edge we know that there used to be a jump here and can then safely
3221 remove all non-fallthru edges. */
3223 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3224 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
3233 /* Remove all but the fake and fallthru edges. The fake edge may be
3234 the only successor for this block in the case of noreturn
3236 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3238 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
3240 df_set_bb_dirty (bb
);
3248 gcc_assert (single_succ_p (bb
));
3250 single_succ_edge (bb
)->probability
= profile_probability::always ();
3253 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
3258 /* Search all basic blocks for potentially dead edges and purge them. Return
3259 true if some edge has been eliminated. */
3262 purge_all_dead_edges (void)
3267 FOR_EACH_BB_FN (bb
, cfun
)
3269 bool purged_here
= purge_dead_edges (bb
);
3271 purged
|= purged_here
;
3277 /* This is used by a few passes that emit some instructions after abnormal
3278 calls, moving the basic block's end, while they in fact do want to emit
3279 them on the fallthru edge. Look for abnormal call edges, find backward
3280 the call in the block and insert the instructions on the edge instead.
3282 Similarly, handle instructions throwing exceptions internally.
3284 Return true when instructions have been found and inserted on edges. */
3287 fixup_abnormal_edges (void)
3289 bool inserted
= false;
3292 FOR_EACH_BB_FN (bb
, cfun
)
3297 /* Look for cases we are interested in - calls or instructions causing
3299 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3300 if ((e
->flags
& EDGE_ABNORMAL_CALL
)
3301 || ((e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
3302 == (EDGE_ABNORMAL
| EDGE_EH
)))
3305 if (e
&& !CALL_P (BB_END (bb
)) && !can_throw_internal (BB_END (bb
)))
3309 /* Get past the new insns generated. Allow notes, as the insns
3310 may be already deleted. */
3312 while ((NONJUMP_INSN_P (insn
) || NOTE_P (insn
))
3313 && !can_throw_internal (insn
)
3314 && insn
!= BB_HEAD (bb
))
3315 insn
= PREV_INSN (insn
);
3317 if (CALL_P (insn
) || can_throw_internal (insn
))
3319 rtx_insn
*stop
, *next
;
3321 e
= find_fallthru_edge (bb
->succs
);
3323 stop
= NEXT_INSN (BB_END (bb
));
3326 for (insn
= NEXT_INSN (insn
); insn
!= stop
; insn
= next
)
3328 next
= NEXT_INSN (insn
);
3333 /* Sometimes there's still the return value USE.
3334 If it's placed after a trapping call (i.e. that
3335 call is the last insn anyway), we have no fallthru
3336 edge. Simply delete this use and don't try to insert
3337 on the non-existent edge.
3338 Similarly, sometimes a call that can throw is
3339 followed in the source with __builtin_unreachable (),
3340 meaning that there is UB if the call returns rather
3341 than throws. If there weren't any instructions
3342 following such calls before, supposedly even the ones
3343 we've deleted aren't significant and can be
3347 /* We're not deleting it, we're moving it. */
3348 insn
->set_undeleted ();
3349 SET_PREV_INSN (insn
) = NULL_RTX
;
3350 SET_NEXT_INSN (insn
) = NULL_RTX
;
3352 insert_insn_on_edge (insn
, e
);
3356 else if (!BARRIER_P (insn
))
3357 set_block_for_insn (insn
, NULL
);
3361 /* It may be that we don't find any trapping insn. In this
3362 case we discovered quite late that the insn that had been
3363 marked as can_throw_internal in fact couldn't trap at all.
3364 So we should in fact delete the EH edges out of the block. */
3366 purge_dead_edges (bb
);
3373 /* Cut the insns from FIRST to LAST out of the insns stream. */
3376 unlink_insn_chain (rtx_insn
*first
, rtx_insn
*last
)
3378 rtx_insn
*prevfirst
= PREV_INSN (first
);
3379 rtx_insn
*nextlast
= NEXT_INSN (last
);
3381 SET_PREV_INSN (first
) = NULL
;
3382 SET_NEXT_INSN (last
) = NULL
;
3384 SET_NEXT_INSN (prevfirst
) = nextlast
;
3386 SET_PREV_INSN (nextlast
) = prevfirst
;
3388 set_last_insn (prevfirst
);
3390 set_first_insn (nextlast
);
3394 /* Skip over inter-block insns occurring after BB which are typically
3395 associated with BB (e.g., barriers). If there are any such insns,
3396 we return the last one. Otherwise, we return the end of BB. */
3399 skip_insns_after_block (basic_block bb
)
3401 rtx_insn
*insn
, *last_insn
, *next_head
, *prev
;
3404 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3405 next_head
= BB_HEAD (bb
->next_bb
);
3407 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
3409 if (insn
== next_head
)
3412 switch (GET_CODE (insn
))
3419 switch (NOTE_KIND (insn
))
3421 case NOTE_INSN_BLOCK_END
:
3431 if (NEXT_INSN (insn
)
3432 && JUMP_TABLE_DATA_P (NEXT_INSN (insn
)))
3434 insn
= NEXT_INSN (insn
);
3447 /* It is possible to hit contradictory sequence. For instance:
3453 Where barrier belongs to jump_insn, but the note does not. This can be
3454 created by removing the basic block originally following
3455 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3457 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
3459 prev
= PREV_INSN (insn
);
3461 switch (NOTE_KIND (insn
))
3463 case NOTE_INSN_BLOCK_END
:
3466 case NOTE_INSN_DELETED
:
3467 case NOTE_INSN_DELETED_LABEL
:
3468 case NOTE_INSN_DELETED_DEBUG_LABEL
:
3471 reorder_insns (insn
, insn
, last_insn
);
3478 /* Locate or create a label for a given basic block. */
3481 label_for_bb (basic_block bb
)
3483 rtx_insn
*label
= BB_HEAD (bb
);
3485 if (!LABEL_P (label
))
3488 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
3490 label
= block_label (bb
);
3496 /* Locate the effective beginning and end of the insn chain for each
3497 block, as defined by skip_insns_after_block above. */
3500 record_effective_endpoints (void)
3502 rtx_insn
*next_insn
;
3506 for (insn
= get_insns ();
3509 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
;
3510 insn
= NEXT_INSN (insn
))
3512 /* No basic blocks at all? */
3515 if (PREV_INSN (insn
))
3516 cfg_layout_function_header
=
3517 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
3519 cfg_layout_function_header
= NULL
;
3521 next_insn
= get_insns ();
3522 FOR_EACH_BB_FN (bb
, cfun
)
3526 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
3527 BB_HEADER (bb
) = unlink_insn_chain (next_insn
,
3528 PREV_INSN (BB_HEAD (bb
)));
3529 end
= skip_insns_after_block (bb
);
3530 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
3531 BB_FOOTER (bb
) = unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
3532 next_insn
= NEXT_INSN (BB_END (bb
));
3535 cfg_layout_function_footer
= next_insn
;
3536 if (cfg_layout_function_footer
)
3537 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
3542 const pass_data pass_data_into_cfg_layout_mode
=
3544 RTL_PASS
, /* type */
3545 "into_cfglayout", /* name */
3546 OPTGROUP_NONE
, /* optinfo_flags */
3548 0, /* properties_required */
3549 PROP_cfglayout
, /* properties_provided */
3550 0, /* properties_destroyed */
3551 0, /* todo_flags_start */
3552 0, /* todo_flags_finish */
3555 class pass_into_cfg_layout_mode
: public rtl_opt_pass
3558 pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3559 : rtl_opt_pass (pass_data_into_cfg_layout_mode
, ctxt
)
3562 /* opt_pass methods: */
3563 virtual unsigned int execute (function
*)
3565 cfg_layout_initialize (0);
3569 }; // class pass_into_cfg_layout_mode
3574 make_pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3576 return new pass_into_cfg_layout_mode (ctxt
);
3581 const pass_data pass_data_outof_cfg_layout_mode
=
3583 RTL_PASS
, /* type */
3584 "outof_cfglayout", /* name */
3585 OPTGROUP_NONE
, /* optinfo_flags */
3587 0, /* properties_required */
3588 0, /* properties_provided */
3589 PROP_cfglayout
, /* properties_destroyed */
3590 0, /* todo_flags_start */
3591 0, /* todo_flags_finish */
3594 class pass_outof_cfg_layout_mode
: public rtl_opt_pass
3597 pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3598 : rtl_opt_pass (pass_data_outof_cfg_layout_mode
, ctxt
)
3601 /* opt_pass methods: */
3602 virtual unsigned int execute (function
*);
3604 }; // class pass_outof_cfg_layout_mode
3607 pass_outof_cfg_layout_mode::execute (function
*fun
)
3611 FOR_EACH_BB_FN (bb
, fun
)
3612 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3613 bb
->aux
= bb
->next_bb
;
3615 cfg_layout_finalize ();
3623 make_pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3625 return new pass_outof_cfg_layout_mode (ctxt
);
3629 /* Link the basic blocks in the correct order, compacting the basic
3630 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3631 function also clears the basic block header and footer fields.
3633 This function is usually called after a pass (e.g. tracer) finishes
3634 some transformations while in cfglayout mode. The required sequence
3635 of the basic blocks is in a linked list along the bb->aux field.
3636 This functions re-links the basic block prev_bb and next_bb pointers
3637 accordingly, and it compacts and renumbers the blocks.
3639 FIXME: This currently works only for RTL, but the only RTL-specific
3640 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3641 to GIMPLE a long time ago, but it doesn't relink the basic block
3642 chain. It could do that (to give better initial RTL) if this function
3643 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3646 relink_block_chain (bool stay_in_cfglayout_mode
)
3648 basic_block bb
, prev_bb
;
3651 /* Maybe dump the re-ordered sequence. */
3654 fprintf (dump_file
, "Reordered sequence:\n");
3655 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, index
=
3658 bb
= (basic_block
) bb
->aux
, index
++)
3660 fprintf (dump_file
, " %i ", index
);
3661 if (get_bb_original (bb
))
3662 fprintf (dump_file
, "duplicate of %i ",
3663 get_bb_original (bb
)->index
);
3664 else if (forwarder_block_p (bb
)
3665 && !LABEL_P (BB_HEAD (bb
)))
3666 fprintf (dump_file
, "compensation ");
3668 fprintf (dump_file
, "bb %i ", bb
->index
);
3672 /* Now reorder the blocks. */
3673 prev_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
3674 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
3675 for (; bb
; prev_bb
= bb
, bb
= (basic_block
) bb
->aux
)
3677 bb
->prev_bb
= prev_bb
;
3678 prev_bb
->next_bb
= bb
;
3680 prev_bb
->next_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
3681 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
= prev_bb
;
3683 /* Then, clean up the aux fields. */
3684 FOR_ALL_BB_FN (bb
, cfun
)
3687 if (!stay_in_cfglayout_mode
)
3688 BB_HEADER (bb
) = BB_FOOTER (bb
) = NULL
;
3691 /* Maybe reset the original copy tables, they are not valid anymore
3692 when we renumber the basic blocks in compact_blocks. If we are
3693 are going out of cfglayout mode, don't re-allocate the tables. */
3694 if (original_copy_tables_initialized_p ())
3695 free_original_copy_tables ();
3696 if (stay_in_cfglayout_mode
)
3697 initialize_original_copy_tables ();
3699 /* Finally, put basic_block_info in the new order. */
3704 /* Given a reorder chain, rearrange the code to match. */
3707 fixup_reorder_chain (void)
3710 rtx_insn
*insn
= NULL
;
3712 if (cfg_layout_function_header
)
3714 set_first_insn (cfg_layout_function_header
);
3715 insn
= cfg_layout_function_header
;
3716 while (NEXT_INSN (insn
))
3717 insn
= NEXT_INSN (insn
);
3720 /* First do the bulk reordering -- rechain the blocks without regard to
3721 the needed changes to jumps and labels. */
3723 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3729 SET_NEXT_INSN (insn
) = BB_HEADER (bb
);
3731 set_first_insn (BB_HEADER (bb
));
3732 SET_PREV_INSN (BB_HEADER (bb
)) = insn
;
3733 insn
= BB_HEADER (bb
);
3734 while (NEXT_INSN (insn
))
3735 insn
= NEXT_INSN (insn
);
3738 SET_NEXT_INSN (insn
) = BB_HEAD (bb
);
3740 set_first_insn (BB_HEAD (bb
));
3741 SET_PREV_INSN (BB_HEAD (bb
)) = insn
;
3745 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
3746 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
3747 while (NEXT_INSN (insn
))
3748 insn
= NEXT_INSN (insn
);
3752 SET_NEXT_INSN (insn
) = cfg_layout_function_footer
;
3753 if (cfg_layout_function_footer
)
3754 SET_PREV_INSN (cfg_layout_function_footer
) = insn
;
3756 while (NEXT_INSN (insn
))
3757 insn
= NEXT_INSN (insn
);
3759 set_last_insn (insn
);
3761 verify_insn_chain ();
3763 /* Now add jumps and labels as needed to match the blocks new
3766 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3769 edge e_fall
, e_taken
, e
;
3770 rtx_insn
*bb_end_insn
;
3771 rtx ret_label
= NULL_RTX
;
3775 if (EDGE_COUNT (bb
->succs
) == 0)
3778 /* Find the old fallthru edge, and another non-EH edge for
3780 e_taken
= e_fall
= NULL
;
3782 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3783 if (e
->flags
& EDGE_FALLTHRU
)
3785 else if (! (e
->flags
& EDGE_EH
))
3788 bb_end_insn
= BB_END (bb
);
3789 if (rtx_jump_insn
*bb_end_jump
= dyn_cast
<rtx_jump_insn
*> (bb_end_insn
))
3791 ret_label
= JUMP_LABEL (bb_end_jump
);
3792 if (any_condjump_p (bb_end_jump
))
3794 /* This might happen if the conditional jump has side
3795 effects and could therefore not be optimized away.
3796 Make the basic block to end with a barrier in order
3797 to prevent rtl_verify_flow_info from complaining. */
3800 gcc_assert (!onlyjump_p (bb_end_jump
)
3801 || returnjump_p (bb_end_jump
)
3802 || (e_taken
->flags
& EDGE_CROSSING
));
3803 emit_barrier_after (bb_end_jump
);
3807 /* If the old fallthru is still next, nothing to do. */
3808 if (bb
->aux
== e_fall
->dest
3809 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3812 /* The degenerated case of conditional jump jumping to the next
3813 instruction can happen for jumps with side effects. We need
3814 to construct a forwarder block and this will be done just
3815 fine by force_nonfallthru below. */
3819 /* There is another special case: if *neither* block is next,
3820 such as happens at the very end of a function, then we'll
3821 need to add a new unconditional jump. Choose the taken
3822 edge based on known or assumed probability. */
3823 else if (bb
->aux
!= e_taken
->dest
)
3825 rtx note
= find_reg_note (bb_end_jump
, REG_BR_PROB
, 0);
3828 && profile_probability::from_reg_br_prob_note
3829 (XINT (note
, 0)) < profile_probability::even ()
3830 && invert_jump (bb_end_jump
,
3832 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3834 : label_for_bb (e_fall
->dest
)), 0))
3836 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3837 gcc_checking_assert (could_fall_through
3838 (e_taken
->src
, e_taken
->dest
));
3839 e_taken
->flags
|= EDGE_FALLTHRU
;
3840 update_br_prob_note (bb
);
3841 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
3845 /* If the "jumping" edge is a crossing edge, and the fall
3846 through edge is non-crossing, leave things as they are. */
3847 else if ((e_taken
->flags
& EDGE_CROSSING
)
3848 && !(e_fall
->flags
& EDGE_CROSSING
))
3851 /* Otherwise we can try to invert the jump. This will
3852 basically never fail, however, keep up the pretense. */
3853 else if (invert_jump (bb_end_jump
,
3855 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3857 : label_for_bb (e_fall
->dest
)), 0))
3859 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3860 gcc_checking_assert (could_fall_through
3861 (e_taken
->src
, e_taken
->dest
));
3862 e_taken
->flags
|= EDGE_FALLTHRU
;
3863 update_br_prob_note (bb
);
3864 if (LABEL_NUSES (ret_label
) == 0
3865 && single_pred_p (e_taken
->dest
))
3866 delete_insn (as_a
<rtx_insn
*> (ret_label
));
3870 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
3872 /* If the old fallthru is still next or if
3873 asm goto doesn't have a fallthru (e.g. when followed by
3874 __builtin_unreachable ()), nothing to do. */
3876 || bb
->aux
== e_fall
->dest
3877 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3880 /* Otherwise we'll have to use the fallthru fixup below. */
3884 /* Otherwise we have some return, switch or computed
3885 jump. In the 99% case, there should not have been a
3887 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
3893 /* No fallthru implies a noreturn function with EH edges, or
3894 something similarly bizarre. In any case, we don't need to
3899 /* If the fallthru block is still next, nothing to do. */
3900 if (bb
->aux
== e_fall
->dest
)
3903 /* A fallthru to exit block. */
3904 if (e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3908 /* We got here if we need to add a new jump insn.
3909 Note force_nonfallthru can delete E_FALL and thus we have to
3910 save E_FALL->src prior to the call to force_nonfallthru. */
3911 nb
= force_nonfallthru_and_redirect (e_fall
, e_fall
->dest
, ret_label
);
3916 /* Don't process this new block. */
3921 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3923 /* Annoying special case - jump around dead jumptables left in the code. */
3924 FOR_EACH_BB_FN (bb
, cfun
)
3926 edge e
= find_fallthru_edge (bb
->succs
);
3928 if (e
&& !can_fallthru (e
->src
, e
->dest
))
3929 force_nonfallthru (e
);
3932 /* Ensure goto_locus from edges has some instructions with that locus in RTL
3933 when not optimizing. */
3934 if (!optimize
&& !DECL_IGNORED_P (current_function_decl
))
3935 FOR_EACH_BB_FN (bb
, cfun
)
3940 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3941 if (LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
3942 && !(e
->flags
& EDGE_ABNORMAL
))
3946 basic_block dest
, nb
;
3949 insn
= BB_END (e
->src
);
3950 end
= PREV_INSN (BB_HEAD (e
->src
));
3952 && (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
3953 insn
= PREV_INSN (insn
);
3955 && INSN_LOCATION (insn
) == e
->goto_locus
)
3957 if (simplejump_p (BB_END (e
->src
))
3958 && !INSN_HAS_LOCATION (BB_END (e
->src
)))
3960 INSN_LOCATION (BB_END (e
->src
)) = e
->goto_locus
;
3964 if (dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3966 /* Non-fallthru edges to the exit block cannot be split. */
3967 if (!(e
->flags
& EDGE_FALLTHRU
))
3972 insn
= BB_HEAD (dest
);
3973 end
= NEXT_INSN (BB_END (dest
));
3974 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
3975 insn
= NEXT_INSN (insn
);
3976 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
3977 && INSN_LOCATION (insn
) == e
->goto_locus
)
3980 nb
= split_edge (e
);
3981 if (!INSN_P (BB_END (nb
)))
3982 BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
3984 INSN_LOCATION (BB_END (nb
)) = e
->goto_locus
;
3986 /* If there are other incoming edges to the destination block
3987 with the same goto locus, redirect them to the new block as
3988 well, this can prevent other such blocks from being created
3989 in subsequent iterations of the loop. */
3990 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
3991 if (LOCATION_LOCUS (e2
->goto_locus
) != UNKNOWN_LOCATION
3992 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
3993 && e
->goto_locus
== e2
->goto_locus
)
3994 redirect_edge_and_branch (e2
, nb
);
4001 /* Perform sanity checks on the insn chain.
4002 1. Check that next/prev pointers are consistent in both the forward and
4004 2. Count insns in chain, going both directions, and check if equal.
4005 3. Check that get_last_insn () returns the actual end of chain. */
4008 verify_insn_chain (void)
4010 rtx_insn
*x
, *prevx
, *nextx
;
4011 int insn_cnt1
, insn_cnt2
;
4013 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
4015 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
4016 gcc_assert (PREV_INSN (x
) == prevx
);
4018 gcc_assert (prevx
== get_last_insn ());
4020 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
4022 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
4023 gcc_assert (NEXT_INSN (x
) == nextx
);
4025 gcc_assert (insn_cnt1
== insn_cnt2
);
4028 /* If we have assembler epilogues, the block falling through to exit must
4029 be the last one in the reordered chain when we reach final. Ensure
4030 that this condition is met. */
4032 fixup_fallthru_exit_predecessor (void)
4035 basic_block bb
= NULL
;
4037 /* This transformation is not valid before reload, because we might
4038 separate a call from the instruction that copies the return
4040 gcc_assert (reload_completed
);
4042 e
= find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4048 basic_block c
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
4050 /* If the very first block is the one with the fall-through exit
4051 edge, we have to split that block. */
4054 bb
= split_block_after_labels (bb
)->dest
;
4057 BB_FOOTER (bb
) = BB_FOOTER (c
);
4058 BB_FOOTER (c
) = NULL
;
4061 while (c
->aux
!= bb
)
4062 c
= (basic_block
) c
->aux
;
4066 c
= (basic_block
) c
->aux
;
4073 /* In case there are more than one fallthru predecessors of exit, force that
4074 there is only one. */
4077 force_one_exit_fallthru (void)
4079 edge e
, predecessor
= NULL
;
4082 basic_block forwarder
, bb
;
4084 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
4085 if (e
->flags
& EDGE_FALLTHRU
)
4087 if (predecessor
== NULL
)
4099 /* Exit has several fallthru predecessors. Create a forwarder block for
4101 forwarder
= split_edge (predecessor
);
4102 for (ei
= ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4103 (e
= ei_safe_edge (ei
)); )
4105 if (e
->src
== forwarder
4106 || !(e
->flags
& EDGE_FALLTHRU
))
4109 redirect_edge_and_branch_force (e
, forwarder
);
4112 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4114 FOR_EACH_BB_FN (bb
, cfun
)
4116 if (bb
->aux
== NULL
&& bb
!= forwarder
)
4118 bb
->aux
= forwarder
;
4124 /* Return true in case it is possible to duplicate the basic block BB. */
4127 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
4129 /* Do not attempt to duplicate tablejumps, as we need to unshare
4130 the dispatch table. This is difficult to do, as the instructions
4131 computing jump destination may be hoisted outside the basic block. */
4132 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
4135 /* Do not duplicate blocks containing insns that can't be copied. */
4136 if (targetm
.cannot_copy_insn_p
)
4138 rtx_insn
*insn
= BB_HEAD (bb
);
4141 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
4143 if (insn
== BB_END (bb
))
4145 insn
= NEXT_INSN (insn
);
4153 duplicate_insn_chain (rtx_insn
*from
, rtx_insn
*to
)
4155 rtx_insn
*insn
, *next
, *copy
;
4158 /* Avoid updating of boundaries of previous basic block. The
4159 note will get removed from insn stream in fixup. */
4160 last
= emit_note (NOTE_INSN_DELETED
);
4162 /* Create copy at the end of INSN chain. The chain will
4163 be reordered later. */
4164 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
4166 switch (GET_CODE (insn
))
4169 /* Don't duplicate label debug insns. */
4170 if (DEBUG_BIND_INSN_P (insn
)
4171 && TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
)
4177 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
4178 if (JUMP_P (insn
) && JUMP_LABEL (insn
) != NULL_RTX
4179 && ANY_RETURN_P (JUMP_LABEL (insn
)))
4180 JUMP_LABEL (copy
) = JUMP_LABEL (insn
);
4181 maybe_copy_prologue_epilogue_insn (insn
, copy
);
4184 case JUMP_TABLE_DATA
:
4185 /* Avoid copying of dispatch tables. We never duplicate
4186 tablejumps, so this can hit only in case the table got
4187 moved far from original jump.
4188 Avoid copying following barrier as well if any
4189 (and debug insns in between). */
4190 for (next
= NEXT_INSN (insn
);
4191 next
!= NEXT_INSN (to
);
4192 next
= NEXT_INSN (next
))
4193 if (!DEBUG_INSN_P (next
))
4195 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
4207 switch (NOTE_KIND (insn
))
4209 /* In case prologue is empty and function contain label
4210 in first BB, we may want to copy the block. */
4211 case NOTE_INSN_PROLOGUE_END
:
4213 case NOTE_INSN_DELETED
:
4214 case NOTE_INSN_DELETED_LABEL
:
4215 case NOTE_INSN_DELETED_DEBUG_LABEL
:
4216 /* No problem to strip these. */
4217 case NOTE_INSN_FUNCTION_BEG
:
4218 /* There is always just single entry to function. */
4219 case NOTE_INSN_BASIC_BLOCK
:
4220 /* We should only switch text sections once. */
4221 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
4224 case NOTE_INSN_EPILOGUE_BEG
:
4225 case NOTE_INSN_UPDATE_SJLJ_CONTEXT
:
4226 emit_note_copy (as_a
<rtx_note
*> (insn
));
4230 /* All other notes should have already been eliminated. */
4238 insn
= NEXT_INSN (last
);
4243 /* Create a duplicate of the basic block BB. */
4246 cfg_layout_duplicate_bb (basic_block bb
)
4251 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
4252 new_bb
= create_basic_block (insn
,
4253 insn
? get_last_insn () : NULL
,
4254 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
);
4256 BB_COPY_PARTITION (new_bb
, bb
);
4259 insn
= BB_HEADER (bb
);
4260 while (NEXT_INSN (insn
))
4261 insn
= NEXT_INSN (insn
);
4262 insn
= duplicate_insn_chain (BB_HEADER (bb
), insn
);
4264 BB_HEADER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4269 insn
= BB_FOOTER (bb
);
4270 while (NEXT_INSN (insn
))
4271 insn
= NEXT_INSN (insn
);
4272 insn
= duplicate_insn_chain (BB_FOOTER (bb
), insn
);
4274 BB_FOOTER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4281 /* Main entry point to this module - initialize the datastructures for
4282 CFG layout changes. It keeps LOOPS up-to-date if not null.
4284 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4287 cfg_layout_initialize (int flags
)
4292 /* Once bb partitioning is complete, cfg layout mode should not be
4293 re-entered. Entering cfg layout mode may require fixups. As an
4294 example, if edge forwarding performed when optimizing the cfg
4295 layout required moving a block from the hot to the cold
4296 section. This would create an illegal partitioning unless some
4297 manual fixup was performed. */
4298 gcc_assert (!crtl
->bb_reorder_complete
|| !crtl
->has_bb_partition
);
4300 initialize_original_copy_tables ();
4302 cfg_layout_rtl_register_cfg_hooks ();
4304 record_effective_endpoints ();
4306 /* Make sure that the targets of non local gotos are marked. */
4307 for (x
= nonlocal_goto_handler_labels
; x
; x
= x
->next ())
4309 bb
= BLOCK_FOR_INSN (x
->insn ());
4310 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
4313 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
4316 /* Splits superblocks. */
4318 break_superblocks (void)
4323 auto_sbitmap
superblocks (last_basic_block_for_fn (cfun
));
4324 bitmap_clear (superblocks
);
4326 FOR_EACH_BB_FN (bb
, cfun
)
4327 if (bb
->flags
& BB_SUPERBLOCK
)
4329 bb
->flags
&= ~BB_SUPERBLOCK
;
4330 bitmap_set_bit (superblocks
, bb
->index
);
4336 rebuild_jump_labels (get_insns ());
4337 find_many_sub_basic_blocks (superblocks
);
4341 /* Finalize the changes: reorder insn list according to the sequence specified
4342 by aux pointers, enter compensation code, rebuild scope forest. */
4345 cfg_layout_finalize (void)
4347 free_dominance_info (CDI_DOMINATORS
);
4348 force_one_exit_fallthru ();
4349 rtl_register_cfg_hooks ();
4350 if (reload_completed
&& !targetm
.have_epilogue ())
4351 fixup_fallthru_exit_predecessor ();
4352 fixup_reorder_chain ();
4354 rebuild_jump_labels (get_insns ());
4355 delete_dead_jumptables ();
4358 verify_insn_chain ();
4359 checking_verify_flow_info ();
4363 /* Same as split_block but update cfg_layout structures. */
4366 cfg_layout_split_block (basic_block bb
, void *insnp
)
4368 rtx insn
= (rtx
) insnp
;
4369 basic_block new_bb
= rtl_split_block (bb
, insn
);
4371 BB_FOOTER (new_bb
) = BB_FOOTER (bb
);
4372 BB_FOOTER (bb
) = NULL
;
4377 /* Redirect Edge to DEST. */
4379 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
4381 basic_block src
= e
->src
;
4384 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4387 if (e
->dest
== dest
)
4390 if (e
->flags
& EDGE_CROSSING
4391 && BB_PARTITION (e
->src
) == BB_PARTITION (dest
)
4392 && simplejump_p (BB_END (src
)))
4396 "Removing crossing jump while redirecting edge form %i to %i\n",
4397 e
->src
->index
, dest
->index
);
4398 delete_insn (BB_END (src
));
4399 e
->flags
|= EDGE_FALLTHRU
;
4402 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4403 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
4405 df_set_bb_dirty (src
);
4409 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4410 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
4413 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
4414 e
->src
->index
, dest
->index
);
4416 df_set_bb_dirty (e
->src
);
4417 redirect_edge_succ (e
, dest
);
4421 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4422 in the case the basic block appears to be in sequence. Avoid this
4425 if (e
->flags
& EDGE_FALLTHRU
)
4427 /* Redirect any branch edges unified with the fallthru one. */
4428 if (JUMP_P (BB_END (src
))
4429 && label_is_jump_target_p (BB_HEAD (e
->dest
),
4435 fprintf (dump_file
, "Fallthru edge unified with branch "
4436 "%i->%i redirected to %i\n",
4437 e
->src
->index
, e
->dest
->index
, dest
->index
);
4438 e
->flags
&= ~EDGE_FALLTHRU
;
4439 redirected
= redirect_branch_edge (e
, dest
);
4440 gcc_assert (redirected
);
4441 redirected
->flags
|= EDGE_FALLTHRU
;
4442 df_set_bb_dirty (redirected
->src
);
4445 /* In case we are redirecting fallthru edge to the branch edge
4446 of conditional jump, remove it. */
4447 if (EDGE_COUNT (src
->succs
) == 2)
4449 /* Find the edge that is different from E. */
4450 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
4453 && any_condjump_p (BB_END (src
))
4454 && onlyjump_p (BB_END (src
)))
4455 delete_insn (BB_END (src
));
4458 fprintf (dump_file
, "Redirecting fallthru edge %i->%i to %i\n",
4459 e
->src
->index
, e
->dest
->index
, dest
->index
);
4460 ret
= redirect_edge_succ_nodup (e
, dest
);
4463 ret
= redirect_branch_edge (e
, dest
);
4468 fixup_partition_crossing (ret
);
4469 /* We don't want simplejumps in the insn stream during cfglayout. */
4470 gcc_assert (!simplejump_p (BB_END (src
)) || CROSSING_JUMP_P (BB_END (src
)));
4472 df_set_bb_dirty (src
);
4476 /* Simple wrapper as we always can redirect fallthru edges. */
4478 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
4480 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
4482 gcc_assert (redirected
);
4486 /* Same as delete_basic_block but update cfg_layout structures. */
4489 cfg_layout_delete_block (basic_block bb
)
4491 rtx_insn
*insn
, *next
, *prev
= PREV_INSN (BB_HEAD (bb
)), *remaints
;
4496 next
= BB_HEAD (bb
);
4498 SET_NEXT_INSN (prev
) = BB_HEADER (bb
);
4500 set_first_insn (BB_HEADER (bb
));
4501 SET_PREV_INSN (BB_HEADER (bb
)) = prev
;
4502 insn
= BB_HEADER (bb
);
4503 while (NEXT_INSN (insn
))
4504 insn
= NEXT_INSN (insn
);
4505 SET_NEXT_INSN (insn
) = next
;
4506 SET_PREV_INSN (next
) = insn
;
4508 next
= NEXT_INSN (BB_END (bb
));
4511 insn
= BB_FOOTER (bb
);
4514 if (BARRIER_P (insn
))
4516 if (PREV_INSN (insn
))
4517 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
4519 BB_FOOTER (bb
) = NEXT_INSN (insn
);
4520 if (NEXT_INSN (insn
))
4521 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
4525 insn
= NEXT_INSN (insn
);
4530 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
4531 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
4532 while (NEXT_INSN (insn
))
4533 insn
= NEXT_INSN (insn
);
4534 SET_NEXT_INSN (insn
) = next
;
4536 SET_PREV_INSN (next
) = insn
;
4538 set_last_insn (insn
);
4541 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
4542 to
= &BB_HEADER (bb
->next_bb
);
4544 to
= &cfg_layout_function_footer
;
4546 rtl_delete_block (bb
);
4549 prev
= NEXT_INSN (prev
);
4551 prev
= get_insns ();
4553 next
= PREV_INSN (next
);
4555 next
= get_last_insn ();
4557 if (next
&& NEXT_INSN (next
) != prev
)
4559 remaints
= unlink_insn_chain (prev
, next
);
4561 while (NEXT_INSN (insn
))
4562 insn
= NEXT_INSN (insn
);
4563 SET_NEXT_INSN (insn
) = *to
;
4565 SET_PREV_INSN (*to
) = insn
;
4570 /* Return true when blocks A and B can be safely merged. */
4573 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
4575 /* If we are partitioning hot/cold basic blocks, we don't want to
4576 mess up unconditional or indirect jumps that cross between hot
4579 Basic block partitioning may result in some jumps that appear to
4580 be optimizable (or blocks that appear to be mergeable), but which really
4581 must be left untouched (they are required to make it safely across
4582 partition boundaries). See the comments at the top of
4583 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4585 if (BB_PARTITION (a
) != BB_PARTITION (b
))
4588 /* Protect the loop latches. */
4589 if (current_loops
&& b
->loop_father
->latch
== b
)
4592 /* If we would end up moving B's instructions, make sure it doesn't fall
4593 through into the exit block, since we cannot recover from a fallthrough
4594 edge into the exit block occurring in the middle of a function. */
4595 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4597 edge e
= find_fallthru_edge (b
->succs
);
4598 if (e
&& e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4602 /* There must be exactly one edge in between the blocks. */
4603 return (single_succ_p (a
)
4604 && single_succ (a
) == b
4605 && single_pred_p (b
) == 1
4607 /* Must be simple edge. */
4608 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
4609 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4610 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
4611 /* If the jump insn has side effects, we can't kill the edge.
4612 When not optimizing, try_redirect_by_replacing_jump will
4613 not allow us to redirect an edge by replacing a table jump. */
4614 && (!JUMP_P (BB_END (a
))
4615 || ((!optimize
|| reload_completed
)
4616 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
4619 /* Merge block A and B. The blocks must be mergeable. */
4622 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
4624 /* If B is a forwarder block whose outgoing edge has no location, we'll
4625 propagate the locus of the edge between A and B onto it. */
4626 const bool forward_edge_locus
4627 = (b
->flags
& BB_FORWARDER_BLOCK
) != 0
4628 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
;
4631 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a
, b
));
4634 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
4637 /* If there was a CODE_LABEL beginning B, delete it. */
4638 if (LABEL_P (BB_HEAD (b
)))
4640 delete_insn (BB_HEAD (b
));
4643 /* We should have fallthru edge in a, or we can do dummy redirection to get
4645 if (JUMP_P (BB_END (a
)))
4646 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
4647 gcc_assert (!JUMP_P (BB_END (a
)));
4649 /* If not optimizing, preserve the locus of the single edge between
4650 blocks A and B if necessary by emitting a nop. */
4652 && !forward_edge_locus
4653 && !DECL_IGNORED_P (current_function_decl
))
4654 emit_nop_for_unique_locus_between (a
, b
);
4656 /* Move things from b->footer after a->footer. */
4660 BB_FOOTER (a
) = BB_FOOTER (b
);
4663 rtx_insn
*last
= BB_FOOTER (a
);
4665 while (NEXT_INSN (last
))
4666 last
= NEXT_INSN (last
);
4667 SET_NEXT_INSN (last
) = BB_FOOTER (b
);
4668 SET_PREV_INSN (BB_FOOTER (b
)) = last
;
4670 BB_FOOTER (b
) = NULL
;
4673 /* Move things from b->header before a->footer.
4674 Note that this may include dead tablejump data, but we don't clean
4675 those up until we go out of cfglayout mode. */
4678 if (! BB_FOOTER (a
))
4679 BB_FOOTER (a
) = BB_HEADER (b
);
4682 rtx_insn
*last
= BB_HEADER (b
);
4684 while (NEXT_INSN (last
))
4685 last
= NEXT_INSN (last
);
4686 SET_NEXT_INSN (last
) = BB_FOOTER (a
);
4687 SET_PREV_INSN (BB_FOOTER (a
)) = last
;
4688 BB_FOOTER (a
) = BB_HEADER (b
);
4690 BB_HEADER (b
) = NULL
;
4693 /* In the case basic blocks are not adjacent, move them around. */
4694 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4696 insn
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
4698 emit_insn_after_noloc (insn
, BB_END (a
), a
);
4700 /* Otherwise just re-associate the instructions. */
4704 BB_END (a
) = BB_END (b
);
4707 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4708 We need to explicitly call. */
4709 update_bb_for_insn_chain (insn
, BB_END (b
), a
);
4711 /* Skip possible DELETED_LABEL insn. */
4712 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
4713 insn
= NEXT_INSN (insn
);
4714 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4715 BB_HEAD (b
) = BB_END (b
) = NULL
;
4718 df_bb_delete (b
->index
);
4720 if (forward_edge_locus
)
4721 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
4724 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
4730 cfg_layout_split_edge (edge e
)
4732 basic_block new_bb
=
4733 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4734 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
4737 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4738 BB_COPY_PARTITION (new_bb
, e
->src
);
4740 BB_COPY_PARTITION (new_bb
, e
->dest
);
4741 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
4742 redirect_edge_and_branch_force (e
, new_bb
);
4747 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4750 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
4754 /* Return true if BB contains only labels or non-executable
4758 rtl_block_empty_p (basic_block bb
)
4762 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4763 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4766 FOR_BB_INSNS (bb
, insn
)
4767 if (NONDEBUG_INSN_P (insn
) && !any_uncondjump_p (insn
))
4773 /* Split a basic block if it ends with a conditional branch and if
4774 the other part of the block is not empty. */
4777 rtl_split_block_before_cond_jump (basic_block bb
)
4780 rtx_insn
*split_point
= NULL
;
4781 rtx_insn
*last
= NULL
;
4782 bool found_code
= false;
4784 FOR_BB_INSNS (bb
, insn
)
4786 if (any_condjump_p (insn
))
4788 else if (NONDEBUG_INSN_P (insn
))
4793 /* Did not find everything. */
4794 if (found_code
&& split_point
)
4795 return split_block (bb
, split_point
)->dest
;
4800 /* Return 1 if BB ends with a call, possibly followed by some
4801 instructions that must stay with the call, 0 otherwise. */
4804 rtl_block_ends_with_call_p (basic_block bb
)
4806 rtx_insn
*insn
= BB_END (bb
);
4808 while (!CALL_P (insn
)
4809 && insn
!= BB_HEAD (bb
)
4810 && (keep_with_call_p (insn
)
4812 || DEBUG_INSN_P (insn
)))
4813 insn
= PREV_INSN (insn
);
4814 return (CALL_P (insn
));
4817 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4820 rtl_block_ends_with_condjump_p (const_basic_block bb
)
4822 return any_condjump_p (BB_END (bb
));
4825 /* Return true if we need to add fake edge to exit.
4826 Helper function for rtl_flow_call_edges_add. */
4829 need_fake_edge_p (const rtx_insn
*insn
)
4835 && !SIBLING_CALL_P (insn
)
4836 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
4837 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
4840 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
4841 && MEM_VOLATILE_P (PATTERN (insn
)))
4842 || (GET_CODE (PATTERN (insn
)) == PARALLEL
4843 && asm_noperands (insn
) != -1
4844 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
4845 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
4848 /* Add fake edges to the function exit for any non constant and non noreturn
4849 calls, volatile inline assembly in the bitmap of blocks specified by
4850 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4853 The goal is to expose cases in which entering a basic block does not imply
4854 that all subsequent instructions must be executed. */
4857 rtl_flow_call_edges_add (sbitmap blocks
)
4860 int blocks_split
= 0;
4861 int last_bb
= last_basic_block_for_fn (cfun
);
4862 bool check_last_block
= false;
4864 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
4868 check_last_block
= true;
4870 check_last_block
= bitmap_bit_p (blocks
,
4871 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
->index
);
4873 /* In the last basic block, before epilogue generation, there will be
4874 a fallthru edge to EXIT. Special care is required if the last insn
4875 of the last basic block is a call because make_edge folds duplicate
4876 edges, which would result in the fallthru edge also being marked
4877 fake, which would result in the fallthru edge being removed by
4878 remove_fake_edges, which would result in an invalid CFG.
4880 Moreover, we can't elide the outgoing fake edge, since the block
4881 profiler needs to take this into account in order to solve the minimal
4882 spanning tree in the case that the call doesn't return.
4884 Handle this by adding a dummy instruction in a new last basic block. */
4885 if (check_last_block
)
4887 basic_block bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
4888 rtx_insn
*insn
= BB_END (bb
);
4890 /* Back up past insns that must be kept in the same block as a call. */
4891 while (insn
!= BB_HEAD (bb
)
4892 && keep_with_call_p (insn
))
4893 insn
= PREV_INSN (insn
);
4895 if (need_fake_edge_p (insn
))
4899 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4902 insert_insn_on_edge (gen_use (const0_rtx
), e
);
4903 commit_edge_insertions ();
4908 /* Now add fake edges to the function exit for any non constant
4909 calls since there is no way that we can determine if they will
4912 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
4914 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
4916 rtx_insn
*prev_insn
;
4921 if (blocks
&& !bitmap_bit_p (blocks
, i
))
4924 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
4926 prev_insn
= PREV_INSN (insn
);
4927 if (need_fake_edge_p (insn
))
4930 rtx_insn
*split_at_insn
= insn
;
4932 /* Don't split the block between a call and an insn that should
4933 remain in the same block as the call. */
4935 while (split_at_insn
!= BB_END (bb
)
4936 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
4937 split_at_insn
= NEXT_INSN (split_at_insn
);
4939 /* The handling above of the final block before the epilogue
4940 should be enough to verify that there is no edge to the exit
4941 block in CFG already. Calling make_edge in such case would
4942 cause us to mark that edge as fake and remove it later. */
4944 if (flag_checking
&& split_at_insn
== BB_END (bb
))
4946 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4947 gcc_assert (e
== NULL
);
4950 /* Note that the following may create a new basic block
4951 and renumber the existing basic blocks. */
4952 if (split_at_insn
!= BB_END (bb
))
4954 e
= split_block (bb
, split_at_insn
);
4959 edge ne
= make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
4960 ne
->probability
= profile_probability::guessed_never ();
4963 if (insn
== BB_HEAD (bb
))
4969 verify_flow_info ();
4971 return blocks_split
;
4974 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4975 the conditional branch target, SECOND_HEAD should be the fall-thru
4976 there is no need to handle this here the loop versioning code handles
4977 this. the reason for SECON_HEAD is that it is needed for condition
4978 in trees, and this should be of the same type since it is a hook. */
4980 rtl_lv_add_condition_to_bb (basic_block first_head
,
4981 basic_block second_head ATTRIBUTE_UNUSED
,
4982 basic_block cond_bb
, void *comp_rtx
)
4984 rtx_code_label
*label
;
4985 rtx_insn
*seq
, *jump
;
4986 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
4987 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
4988 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
4992 label
= block_label (first_head
);
4993 mode
= GET_MODE (op0
);
4994 if (mode
== VOIDmode
)
4995 mode
= GET_MODE (op1
);
4998 op0
= force_operand (op0
, NULL_RTX
);
4999 op1
= force_operand (op1
, NULL_RTX
);
5000 do_compare_rtx_and_jump (op0
, op1
, comp
, 0, mode
, NULL_RTX
, NULL
, label
,
5001 profile_probability::uninitialized ());
5002 jump
= get_last_insn ();
5003 JUMP_LABEL (jump
) = label
;
5004 LABEL_NUSES (label
)++;
5008 /* Add the new cond, in the new head. */
5009 emit_insn_after (seq
, BB_END (cond_bb
));
5013 /* Given a block B with unconditional branch at its end, get the
5014 store the return the branch edge and the fall-thru edge in
5015 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
5017 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
5018 edge
*fallthru_edge
)
5020 edge e
= EDGE_SUCC (b
, 0);
5022 if (e
->flags
& EDGE_FALLTHRU
)
5025 *branch_edge
= EDGE_SUCC (b
, 1);
5030 *fallthru_edge
= EDGE_SUCC (b
, 1);
5035 init_rtl_bb_info (basic_block bb
)
5037 gcc_assert (!bb
->il
.x
.rtl
);
5038 bb
->il
.x
.head_
= NULL
;
5039 bb
->il
.x
.rtl
= ggc_cleared_alloc
<rtl_bb_info
> ();
5042 /* Returns true if it is possible to remove edge E by redirecting
5043 it to the destination of the other edge from E->src. */
5046 rtl_can_remove_branch_p (const_edge e
)
5048 const_basic_block src
= e
->src
;
5049 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
5050 const rtx_insn
*insn
= BB_END (src
);
5053 /* The conditions are taken from try_redirect_by_replacing_jump. */
5054 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
5057 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
5060 if (BB_PARTITION (src
) != BB_PARTITION (target
))
5063 if (!onlyjump_p (insn
)
5064 || tablejump_p (insn
, NULL
, NULL
))
5067 set
= single_set (insn
);
5068 if (!set
|| side_effects_p (set
))
5075 rtl_duplicate_bb (basic_block bb
)
5077 bb
= cfg_layout_duplicate_bb (bb
);
5082 /* Do book-keeping of basic block BB for the profile consistency checker.
5083 Store the counting in RECORD. */
5085 rtl_account_profile_record (basic_block bb
, struct profile_record
*record
)
5088 FOR_BB_INSNS (bb
, insn
)
5091 record
->size
+= insn_cost (insn
, false);
5092 if (bb
->count
.initialized_p ())
5094 += insn_cost (insn
, true) * bb
->count
.to_gcov_type ();
5095 else if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
5097 += insn_cost (insn
, true) * bb
->count
.to_frequency (cfun
);
5101 /* Implementation of CFG manipulation for linearized RTL. */
5102 struct cfg_hooks rtl_cfg_hooks
= {
5104 rtl_verify_flow_info
,
5106 rtl_dump_bb_for_graph
,
5107 rtl_create_basic_block
,
5108 rtl_redirect_edge_and_branch
,
5109 rtl_redirect_edge_and_branch_force
,
5110 rtl_can_remove_branch_p
,
5113 rtl_move_block_after
,
5114 rtl_can_merge_blocks
, /* can_merge_blocks_p */
5118 cfg_layout_can_duplicate_bb_p
,
5121 rtl_make_forwarder_block
,
5122 rtl_tidy_fallthru_edge
,
5123 rtl_force_nonfallthru
,
5124 rtl_block_ends_with_call_p
,
5125 rtl_block_ends_with_condjump_p
,
5126 rtl_flow_call_edges_add
,
5127 NULL
, /* execute_on_growing_pred */
5128 NULL
, /* execute_on_shrinking_pred */
5129 NULL
, /* duplicate loop for trees */
5130 NULL
, /* lv_add_condition_to_bb */
5131 NULL
, /* lv_adjust_loop_header_phi*/
5132 NULL
, /* extract_cond_bb_edges */
5133 NULL
, /* flush_pending_stmts */
5134 rtl_block_empty_p
, /* block_empty_p */
5135 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5136 rtl_account_profile_record
,
5139 /* Implementation of CFG manipulation for cfg layout RTL, where
5140 basic block connected via fallthru edges does not have to be adjacent.
5141 This representation will hopefully become the default one in future
5142 version of the compiler. */
5144 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
5146 rtl_verify_flow_info_1
,
5148 rtl_dump_bb_for_graph
,
5149 cfg_layout_create_basic_block
,
5150 cfg_layout_redirect_edge_and_branch
,
5151 cfg_layout_redirect_edge_and_branch_force
,
5152 rtl_can_remove_branch_p
,
5153 cfg_layout_delete_block
,
5154 cfg_layout_split_block
,
5155 rtl_move_block_after
,
5156 cfg_layout_can_merge_blocks_p
,
5157 cfg_layout_merge_blocks
,
5160 cfg_layout_can_duplicate_bb_p
,
5161 cfg_layout_duplicate_bb
,
5162 cfg_layout_split_edge
,
5163 rtl_make_forwarder_block
,
5164 NULL
, /* tidy_fallthru_edge */
5165 rtl_force_nonfallthru
,
5166 rtl_block_ends_with_call_p
,
5167 rtl_block_ends_with_condjump_p
,
5168 rtl_flow_call_edges_add
,
5169 NULL
, /* execute_on_growing_pred */
5170 NULL
, /* execute_on_shrinking_pred */
5171 duplicate_loop_to_header_edge
, /* duplicate loop for trees */
5172 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
5173 NULL
, /* lv_adjust_loop_header_phi*/
5174 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
5175 NULL
, /* flush_pending_stmts */
5176 rtl_block_empty_p
, /* block_empty_p */
5177 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5178 rtl_account_profile_record
,
5181 #include "gt-cfgrtl.h"