1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2014 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"
45 #include "hard-reg-set.h"
46 #include "basic-block.h"
47 #include "bb-reorder.h"
52 #include "rtl-error.h"
55 #include "insn-attr.h"
56 #include "insn-config.h"
59 #include "common/common-target.h"
62 #include "tree-pass.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 cfg_layout_function_footer
;
68 static GTY(()) rtx cfg_layout_function_header
;
70 static rtx
skip_insns_after_block (basic_block
);
71 static void record_effective_endpoints (void);
72 static rtx
label_for_bb (basic_block
);
73 static void fixup_reorder_chain (void);
75 void verify_insn_chain (void);
76 static void fixup_fallthru_exit_predecessor (void);
77 static int can_delete_note_p (const_rtx
);
78 static int can_delete_label_p (const_rtx
);
79 static basic_block
rtl_split_edge (edge
);
80 static bool rtl_move_block_after (basic_block
, basic_block
);
81 static int rtl_verify_flow_info (void);
82 static basic_block
cfg_layout_split_block (basic_block
, void *);
83 static edge
cfg_layout_redirect_edge_and_branch (edge
, basic_block
);
84 static basic_block
cfg_layout_redirect_edge_and_branch_force (edge
, basic_block
);
85 static void cfg_layout_delete_block (basic_block
);
86 static void rtl_delete_block (basic_block
);
87 static basic_block
rtl_redirect_edge_and_branch_force (edge
, basic_block
);
88 static edge
rtl_redirect_edge_and_branch (edge
, basic_block
);
89 static basic_block
rtl_split_block (basic_block
, void *);
90 static void rtl_dump_bb (FILE *, basic_block
, int, int);
91 static int rtl_verify_flow_info_1 (void);
92 static void rtl_make_forwarder_block (edge
);
94 /* Return true if NOTE is not one of the ones that must be kept paired,
95 so that we may simply delete it. */
98 can_delete_note_p (const_rtx note
)
100 switch (NOTE_KIND (note
))
102 case NOTE_INSN_DELETED
:
103 case NOTE_INSN_BASIC_BLOCK
:
104 case NOTE_INSN_EPILOGUE_BEG
:
112 /* True if a given label can be deleted. */
115 can_delete_label_p (const_rtx label
)
117 return (!LABEL_PRESERVE_P (label
)
118 /* User declared labels must be preserved. */
119 && LABEL_NAME (label
) == 0
120 && !in_expr_list_p (forced_labels
, label
));
123 /* Delete INSN by patching it out. */
126 delete_insn (rtx 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 (insn
))
138 const char *name
= LABEL_NAME (insn
);
139 basic_block bb
= BLOCK_FOR_INSN (insn
);
140 rtx 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_expr_list (insn
, &nonlocal_goto_handler_labels
);
166 /* If this insn has already been deleted, something is very wrong. */
167 gcc_assert (!INSN_DELETED_P (insn
));
169 df_insn_delete (insn
);
171 INSN_DELETED_P (insn
) = 1;
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 (JUMP_TABLE_DATA_P (insn
))
202 rtx pat
= PATTERN (insn
);
203 int diff_vec_p
= GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
;
204 int len
= XVECLEN (pat
, diff_vec_p
);
207 for (i
= 0; i
< len
; i
++)
209 rtx label
= XEXP (XVECEXP (pat
, diff_vec_p
, i
), 0);
211 /* When deleting code in bulk (e.g. removing many unreachable
212 blocks) we can delete a label that's a target of the vector
213 before deleting the vector itself. */
215 LABEL_NUSES (label
)--;
220 /* Like delete_insn but also purge dead edges from BB. */
223 delete_insn_and_edges (rtx insn
)
228 && BLOCK_FOR_INSN (insn
)
229 && BB_END (BLOCK_FOR_INSN (insn
)) == insn
)
233 purge_dead_edges (BLOCK_FOR_INSN (insn
));
236 /* Unlink a chain of insns between START and FINISH, leaving notes
237 that must be paired. If CLEAR_BB is true, we set bb field for
238 insns that cannot be removed to NULL. */
241 delete_insn_chain (rtx start
, rtx finish
, bool clear_bb
)
245 /* Unchain the insns one by one. It would be quicker to delete all of these
246 with a single unchaining, rather than one at a time, but we need to keep
251 prev
= PREV_INSN (current
);
252 if (NOTE_P (current
) && !can_delete_note_p (current
))
255 delete_insn (current
);
257 if (clear_bb
&& !INSN_DELETED_P (current
))
258 set_block_for_insn (current
, NULL
);
260 if (current
== start
)
266 /* Create a new basic block consisting of the instructions between HEAD and END
267 inclusive. This function is designed to allow fast BB construction - reuses
268 the note and basic block struct in BB_NOTE, if any and do not grow
269 BASIC_BLOCK chain and should be used directly only by CFG construction code.
270 END can be NULL in to create new empty basic block before HEAD. Both END
271 and HEAD can be NULL to create basic block at the end of INSN chain.
272 AFTER is the basic block we should be put after. */
275 create_basic_block_structure (rtx head
, rtx end
, rtx bb_note
, basic_block after
)
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 head
= (rtx
) headp
, end
= (rtx
) endp
;
357 /* Grow the basic block array if needed. */
358 if ((size_t) last_basic_block_for_fn (cfun
)
359 >= basic_block_info_for_fn (cfun
)->length ())
362 (last_basic_block_for_fn (cfun
)
363 + (last_basic_block_for_fn (cfun
) + 3) / 4);
364 vec_safe_grow_cleared (basic_block_info_for_fn (cfun
), new_size
);
367 n_basic_blocks_for_fn (cfun
)++;
369 bb
= create_basic_block_structure (head
, end
, NULL
, after
);
375 cfg_layout_create_basic_block (void *head
, void *end
, basic_block after
)
377 basic_block newbb
= rtl_create_basic_block (head
, end
, after
);
382 /* Delete the insns in a (non-live) block. We physically delete every
383 non-deleted-note insn, and update the flow graph appropriately.
385 Return nonzero if we deleted an exception handler. */
387 /* ??? Preserving all such notes strikes me as wrong. It would be nice
388 to post-process the stream to remove empty blocks, loops, ranges, etc. */
391 rtl_delete_block (basic_block b
)
395 /* If the head of this block is a CODE_LABEL, then it might be the
396 label for an exception handler which can't be reached. We need
397 to remove the label from the exception_handler_label list. */
400 end
= get_last_bb_insn (b
);
402 /* Selectively delete the entire chain. */
404 delete_insn_chain (insn
, end
, true);
408 fprintf (dump_file
, "deleting block %d\n", b
->index
);
409 df_bb_delete (b
->index
);
412 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
415 compute_bb_for_insn (void)
419 FOR_EACH_BB_FN (bb
, cfun
)
421 rtx end
= BB_END (bb
);
424 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
426 BLOCK_FOR_INSN (insn
) = bb
;
433 /* Release the basic_block_for_insn array. */
436 free_bb_for_insn (void)
439 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
440 if (!BARRIER_P (insn
))
441 BLOCK_FOR_INSN (insn
) = NULL
;
446 rest_of_pass_free_cfg (void)
449 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
450 valid at that point so it would be too late to call df_analyze. */
451 if (optimize
> 0 && flag_delayed_branch
)
453 df_note_add_problem ();
458 if (crtl
->has_bb_partition
)
459 insert_section_boundary_note ();
467 const pass_data pass_data_free_cfg
=
470 "*free_cfg", /* name */
471 OPTGROUP_NONE
, /* optinfo_flags */
472 false, /* has_gate */
473 true, /* has_execute */
475 0, /* properties_required */
476 0, /* properties_provided */
477 PROP_cfg
, /* properties_destroyed */
478 0, /* todo_flags_start */
479 0, /* todo_flags_finish */
482 class pass_free_cfg
: public rtl_opt_pass
485 pass_free_cfg (gcc::context
*ctxt
)
486 : rtl_opt_pass (pass_data_free_cfg
, ctxt
)
489 /* opt_pass methods: */
490 unsigned int execute () { return rest_of_pass_free_cfg (); }
492 }; // class pass_free_cfg
497 make_pass_free_cfg (gcc::context
*ctxt
)
499 return new pass_free_cfg (ctxt
);
502 /* Return RTX to emit after when we want to emit code on the entry of function. */
504 entry_of_function (void)
506 return (n_basic_blocks_for_fn (cfun
) > NUM_FIXED_BLOCKS
?
507 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
) : get_insns ());
510 /* Emit INSN at the entry point of the function, ensuring that it is only
511 executed once per function. */
513 emit_insn_at_entry (rtx insn
)
515 edge_iterator ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
516 edge e
= ei_safe_edge (ei
);
517 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
519 insert_insn_on_edge (insn
, e
);
520 commit_edge_insertions ();
523 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
524 (or BARRIER if found) and notify df of the bb change.
525 The insn chain range is inclusive
526 (i.e. both BEGIN and END will be updated. */
529 update_bb_for_insn_chain (rtx begin
, rtx end
, basic_block bb
)
533 end
= NEXT_INSN (end
);
534 for (insn
= begin
; insn
!= end
; insn
= NEXT_INSN (insn
))
535 if (!BARRIER_P (insn
))
536 df_insn_change_bb (insn
, bb
);
539 /* Update BLOCK_FOR_INSN of insns in BB to BB,
540 and notify df of the change. */
543 update_bb_for_insn (basic_block bb
)
545 update_bb_for_insn_chain (BB_HEAD (bb
), BB_END (bb
), bb
);
549 /* Like active_insn_p, except keep the return value clobber around
550 even after reload. */
553 flow_active_insn_p (const_rtx insn
)
555 if (active_insn_p (insn
))
558 /* A clobber of the function return value exists for buggy
559 programs that fail to return a value. Its effect is to
560 keep the return value from being live across the entire
561 function. If we allow it to be skipped, we introduce the
562 possibility for register lifetime confusion. */
563 if (GET_CODE (PATTERN (insn
)) == CLOBBER
564 && REG_P (XEXP (PATTERN (insn
), 0))
565 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn
), 0)))
571 /* Return true if the block has no effect and only forwards control flow to
572 its single destination. */
575 contains_no_active_insn_p (const_basic_block bb
)
579 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
580 || !single_succ_p (bb
))
583 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
584 if (INSN_P (insn
) && flow_active_insn_p (insn
))
587 return (!INSN_P (insn
)
588 || (JUMP_P (insn
) && simplejump_p (insn
))
589 || !flow_active_insn_p (insn
));
592 /* Likewise, but protect loop latches, headers and preheaders. */
593 /* FIXME: Make this a cfg hook. */
596 forwarder_block_p (const_basic_block bb
)
598 if (!contains_no_active_insn_p (bb
))
601 /* Protect loop latches, headers and preheaders. */
605 if (bb
->loop_father
->header
== bb
)
607 dest
= EDGE_SUCC (bb
, 0)->dest
;
608 if (dest
->loop_father
->header
== dest
)
615 /* Return nonzero if we can reach target from src by falling through. */
616 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
619 can_fallthru (basic_block src
, basic_block target
)
621 rtx insn
= BB_END (src
);
626 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
628 if (src
->next_bb
!= target
)
631 /* ??? Later we may add code to move jump tables offline. */
632 if (tablejump_p (insn
, NULL
, NULL
))
635 FOR_EACH_EDGE (e
, ei
, src
->succs
)
636 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
637 && e
->flags
& EDGE_FALLTHRU
)
640 insn2
= BB_HEAD (target
);
641 if (!active_insn_p (insn2
))
642 insn2
= next_active_insn (insn2
);
644 return next_active_insn (insn
) == insn2
;
647 /* Return nonzero if we could reach target from src by falling through,
648 if the target was made adjacent. If we already have a fall-through
649 edge to the exit block, we can't do that. */
651 could_fall_through (basic_block src
, basic_block target
)
656 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
658 FOR_EACH_EDGE (e
, ei
, src
->succs
)
659 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
660 && e
->flags
& EDGE_FALLTHRU
)
665 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
667 bb_note (basic_block bb
)
673 note
= NEXT_INSN (note
);
675 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
679 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
680 note associated with the BLOCK. */
683 first_insn_after_basic_block_note (basic_block block
)
687 /* Get the first instruction in the block. */
688 insn
= BB_HEAD (block
);
690 if (insn
== NULL_RTX
)
693 insn
= NEXT_INSN (insn
);
694 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
696 return NEXT_INSN (insn
);
699 /* Creates a new basic block just after basic block B by splitting
700 everything after specified instruction I. */
703 rtl_split_block (basic_block bb
, void *insnp
)
706 rtx insn
= (rtx
) insnp
;
712 insn
= first_insn_after_basic_block_note (bb
);
718 insn
= PREV_INSN (insn
);
720 /* If the block contains only debug insns, insn would have
721 been NULL in a non-debug compilation, and then we'd end
722 up emitting a DELETED note. For -fcompare-debug
723 stability, emit the note too. */
724 if (insn
!= BB_END (bb
)
725 && DEBUG_INSN_P (next
)
726 && DEBUG_INSN_P (BB_END (bb
)))
728 while (next
!= BB_END (bb
) && DEBUG_INSN_P (next
))
729 next
= NEXT_INSN (next
);
731 if (next
== BB_END (bb
))
732 emit_note_after (NOTE_INSN_DELETED
, next
);
736 insn
= get_last_insn ();
739 /* We probably should check type of the insn so that we do not create
740 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
742 if (insn
== BB_END (bb
))
743 emit_note_after (NOTE_INSN_DELETED
, insn
);
745 /* Create the new basic block. */
746 new_bb
= create_basic_block (NEXT_INSN (insn
), BB_END (bb
), bb
);
747 BB_COPY_PARTITION (new_bb
, bb
);
750 /* Redirect the outgoing edges. */
751 new_bb
->succs
= bb
->succs
;
753 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
756 /* The new block starts off being dirty. */
757 df_set_bb_dirty (bb
);
761 /* Return true if the single edge between blocks A and B is the only place
762 in RTL which holds some unique locus. */
765 unique_locus_on_edge_between_p (basic_block a
, basic_block b
)
767 const location_t goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
770 if (LOCATION_LOCUS (goto_locus
) == UNKNOWN_LOCATION
)
773 /* First scan block A backward. */
775 end
= PREV_INSN (BB_HEAD (a
));
776 while (insn
!= end
&& (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
777 insn
= PREV_INSN (insn
);
779 if (insn
!= end
&& INSN_LOCATION (insn
) == goto_locus
)
782 /* Then scan block B forward. */
786 end
= NEXT_INSN (BB_END (b
));
787 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
788 insn
= NEXT_INSN (insn
);
790 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
791 && INSN_LOCATION (insn
) == goto_locus
)
798 /* If the single edge between blocks A and B is the only place in RTL which
799 holds some unique locus, emit a nop with that locus between the blocks. */
802 emit_nop_for_unique_locus_between (basic_block a
, basic_block b
)
804 if (!unique_locus_on_edge_between_p (a
, b
))
807 BB_END (a
) = emit_insn_after_noloc (gen_nop (), BB_END (a
), a
);
808 INSN_LOCATION (BB_END (a
)) = EDGE_SUCC (a
, 0)->goto_locus
;
811 /* Blocks A and B are to be merged into a single block A. The insns
812 are already contiguous. */
815 rtl_merge_blocks (basic_block a
, basic_block b
)
817 rtx b_head
= BB_HEAD (b
), b_end
= BB_END (b
), a_end
= BB_END (a
);
818 rtx del_first
= NULL_RTX
, del_last
= NULL_RTX
;
819 rtx b_debug_start
= b_end
, b_debug_end
= b_end
;
820 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
824 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
827 while (DEBUG_INSN_P (b_end
))
828 b_end
= PREV_INSN (b_debug_start
= b_end
);
830 /* If there was a CODE_LABEL beginning B, delete it. */
831 if (LABEL_P (b_head
))
833 /* Detect basic blocks with nothing but a label. This can happen
834 in particular at the end of a function. */
838 del_first
= del_last
= b_head
;
839 b_head
= NEXT_INSN (b_head
);
842 /* Delete the basic block note and handle blocks containing just that
844 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
852 b_head
= NEXT_INSN (b_head
);
855 /* If there was a jump out of A, delete it. */
860 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
862 || NOTE_INSN_BASIC_BLOCK_P (prev
)
863 || prev
== BB_HEAD (a
))
869 /* If this was a conditional jump, we need to also delete
870 the insn that set cc0. */
871 if (only_sets_cc0_p (prev
))
875 prev
= prev_nonnote_insn (prev
);
882 a_end
= PREV_INSN (del_first
);
884 else if (BARRIER_P (NEXT_INSN (a_end
)))
885 del_first
= NEXT_INSN (a_end
);
887 /* Delete everything marked above as well as crap that might be
888 hanging out between the two blocks. */
890 BB_HEAD (b
) = b_empty
? NULL_RTX
: b_head
;
891 delete_insn_chain (del_first
, del_last
, true);
893 /* When not optimizing CFG and the edge is the only place in RTL which holds
894 some unique locus, emit a nop with that locus in between. */
897 emit_nop_for_unique_locus_between (a
, b
);
901 /* Reassociate the insns of B with A. */
904 update_bb_for_insn_chain (a_end
, b_debug_end
, a
);
906 BB_END (a
) = b_debug_end
;
907 BB_HEAD (b
) = NULL_RTX
;
909 else if (b_end
!= b_debug_end
)
911 /* Move any deleted labels and other notes between the end of A
912 and the debug insns that make up B after the debug insns,
913 bringing the debug insns into A while keeping the notes after
915 if (NEXT_INSN (a_end
) != b_debug_start
)
916 reorder_insns_nobb (NEXT_INSN (a_end
), PREV_INSN (b_debug_start
),
918 update_bb_for_insn_chain (b_debug_start
, b_debug_end
, a
);
919 BB_END (a
) = b_debug_end
;
922 df_bb_delete (b
->index
);
924 /* If B was a forwarder block, propagate the locus on the edge. */
926 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
927 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
930 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
934 /* Return true when block A and B can be merged. */
937 rtl_can_merge_blocks (basic_block a
, basic_block b
)
939 /* If we are partitioning hot/cold basic blocks, we don't want to
940 mess up unconditional or indirect jumps that cross between hot
943 Basic block partitioning may result in some jumps that appear to
944 be optimizable (or blocks that appear to be mergeable), but which really
945 must be left untouched (they are required to make it safely across
946 partition boundaries). See the comments at the top of
947 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
949 if (BB_PARTITION (a
) != BB_PARTITION (b
))
952 /* Protect the loop latches. */
953 if (current_loops
&& b
->loop_father
->latch
== b
)
956 /* There must be exactly one edge in between the blocks. */
957 return (single_succ_p (a
)
958 && single_succ (a
) == b
961 /* Must be simple edge. */
962 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
964 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
965 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
966 /* If the jump insn has side effects,
967 we can't kill the edge. */
968 && (!JUMP_P (BB_END (a
))
970 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
973 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
977 block_label (basic_block block
)
979 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
982 if (!LABEL_P (BB_HEAD (block
)))
984 BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
987 return BB_HEAD (block
);
990 /* Attempt to perform edge redirection by replacing possibly complex jump
991 instruction by unconditional jump or removing jump completely. This can
992 apply only if all edges now point to the same block. The parameters and
993 return values are equivalent to redirect_edge_and_branch. */
996 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
998 basic_block src
= e
->src
;
999 rtx insn
= BB_END (src
), kill_from
;
1003 /* If we are partitioning hot/cold basic blocks, we don't want to
1004 mess up unconditional or indirect jumps that cross between hot
1007 Basic block partitioning may result in some jumps that appear to
1008 be optimizable (or blocks that appear to be mergeable), but which really
1009 must be left untouched (they are required to make it safely across
1010 partition boundaries). See the comments at the top of
1011 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1013 if (BB_PARTITION (src
) != BB_PARTITION (target
))
1016 /* We can replace or remove a complex jump only when we have exactly
1017 two edges. Also, if we have exactly one outgoing edge, we can
1019 if (EDGE_COUNT (src
->succs
) >= 3
1020 /* Verify that all targets will be TARGET. Specifically, the
1021 edge that is not E must also go to TARGET. */
1022 || (EDGE_COUNT (src
->succs
) == 2
1023 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
1026 if (!onlyjump_p (insn
))
1028 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
1031 /* Avoid removing branch with side effects. */
1032 set
= single_set (insn
);
1033 if (!set
|| side_effects_p (set
))
1036 /* In case we zap a conditional jump, we'll need to kill
1037 the cc0 setter too. */
1040 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
))
1041 && only_sets_cc0_p (PREV_INSN (insn
)))
1042 kill_from
= PREV_INSN (insn
);
1045 /* See if we can create the fallthru edge. */
1046 if (in_cfglayout
|| can_fallthru (src
, target
))
1049 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
1052 /* Selectively unlink whole insn chain. */
1055 rtx insn
= BB_FOOTER (src
);
1057 delete_insn_chain (kill_from
, BB_END (src
), false);
1059 /* Remove barriers but keep jumptables. */
1062 if (BARRIER_P (insn
))
1064 if (PREV_INSN (insn
))
1065 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1067 BB_FOOTER (src
) = NEXT_INSN (insn
);
1068 if (NEXT_INSN (insn
))
1069 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1073 insn
= NEXT_INSN (insn
);
1077 delete_insn_chain (kill_from
, PREV_INSN (BB_HEAD (target
)),
1081 /* If this already is simplejump, redirect it. */
1082 else if (simplejump_p (insn
))
1084 if (e
->dest
== target
)
1087 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
1088 INSN_UID (insn
), e
->dest
->index
, target
->index
);
1089 if (!redirect_jump (insn
, 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 target_label
= block_label (target
);
1104 rtx barrier
, label
, table
;
1106 emit_jump_insn_after_noloc (gen_jump (target_label
), insn
);
1107 JUMP_LABEL (BB_END (src
)) = target_label
;
1108 LABEL_NUSES (target_label
)++;
1110 fprintf (dump_file
, "Replacing insn %i by jump %i\n",
1111 INSN_UID (insn
), INSN_UID (BB_END (src
)));
1114 delete_insn_chain (kill_from
, insn
, false);
1116 /* Recognize a tablejump that we are converting to a
1117 simple jump and remove its associated CODE_LABEL
1118 and ADDR_VEC or ADDR_DIFF_VEC. */
1119 if (tablejump_p (insn
, &label
, &table
))
1120 delete_insn_chain (label
, table
, false);
1122 barrier
= next_nonnote_insn (BB_END (src
));
1123 if (!barrier
|| !BARRIER_P (barrier
))
1124 emit_barrier_after (BB_END (src
));
1127 if (barrier
!= NEXT_INSN (BB_END (src
)))
1129 /* Move the jump before barrier so that the notes
1130 which originally were or were created before jump table are
1131 inside the basic block. */
1132 rtx new_insn
= BB_END (src
);
1134 update_bb_for_insn_chain (NEXT_INSN (BB_END (src
)),
1135 PREV_INSN (barrier
), src
);
1137 NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
1138 PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
1140 NEXT_INSN (new_insn
) = barrier
;
1141 NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
1143 PREV_INSN (new_insn
) = PREV_INSN (barrier
);
1144 PREV_INSN (barrier
) = new_insn
;
1149 /* Keep only one edge out and set proper flags. */
1150 if (!single_succ_p (src
))
1152 gcc_assert (single_succ_p (src
));
1154 e
= single_succ_edge (src
);
1156 e
->flags
= EDGE_FALLTHRU
;
1160 e
->probability
= REG_BR_PROB_BASE
;
1161 e
->count
= src
->count
;
1163 if (e
->dest
!= target
)
1164 redirect_edge_succ (e
, target
);
1168 /* Subroutine of redirect_branch_edge that tries to patch the jump
1169 instruction INSN so that it reaches block NEW. Do this
1170 only when it originally reached block OLD. Return true if this
1171 worked or the original target wasn't OLD, return false if redirection
1175 patch_jump_insn (rtx insn
, rtx old_label
, basic_block new_bb
)
1178 /* Recognize a tablejump and adjust all matching cases. */
1179 if (tablejump_p (insn
, NULL
, &tmp
))
1183 rtx new_label
= block_label (new_bb
);
1185 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1187 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
1188 vec
= XVEC (PATTERN (tmp
), 0);
1190 vec
= XVEC (PATTERN (tmp
), 1);
1192 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
1193 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
1195 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
1196 --LABEL_NUSES (old_label
);
1197 ++LABEL_NUSES (new_label
);
1200 /* Handle casesi dispatch insns. */
1201 if ((tmp
= single_set (insn
)) != NULL
1202 && SET_DEST (tmp
) == pc_rtx
1203 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
1204 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
1205 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
1207 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
1209 --LABEL_NUSES (old_label
);
1210 ++LABEL_NUSES (new_label
);
1213 else if ((tmp
= extract_asm_operands (PATTERN (insn
))) != NULL
)
1215 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (tmp
);
1216 rtx new_label
, note
;
1218 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1220 new_label
= block_label (new_bb
);
1222 for (i
= 0; i
< n
; ++i
)
1224 rtx old_ref
= ASM_OPERANDS_LABEL (tmp
, i
);
1225 gcc_assert (GET_CODE (old_ref
) == LABEL_REF
);
1226 if (XEXP (old_ref
, 0) == old_label
)
1228 ASM_OPERANDS_LABEL (tmp
, i
)
1229 = gen_rtx_LABEL_REF (Pmode
, new_label
);
1230 --LABEL_NUSES (old_label
);
1231 ++LABEL_NUSES (new_label
);
1235 if (JUMP_LABEL (insn
) == old_label
)
1237 JUMP_LABEL (insn
) = new_label
;
1238 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1240 remove_note (insn
, note
);
1244 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1246 remove_note (insn
, note
);
1247 if (JUMP_LABEL (insn
) != new_label
1248 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1249 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1251 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1253 XEXP (note
, 0) = new_label
;
1257 /* ?? We may play the games with moving the named labels from
1258 one basic block to the other in case only one computed_jump is
1260 if (computed_jump_p (insn
)
1261 /* A return instruction can't be redirected. */
1262 || returnjump_p (insn
))
1265 if (!currently_expanding_to_rtl
|| JUMP_LABEL (insn
) == old_label
)
1267 /* If the insn doesn't go where we think, we're confused. */
1268 gcc_assert (JUMP_LABEL (insn
) == old_label
);
1270 /* If the substitution doesn't succeed, die. This can happen
1271 if the back end emitted unrecognizable instructions or if
1272 target is exit block on some arches. */
1273 if (!redirect_jump (insn
, block_label (new_bb
), 0))
1275 gcc_assert (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1284 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1287 redirect_branch_edge (edge e
, basic_block target
)
1289 rtx old_label
= BB_HEAD (e
->dest
);
1290 basic_block src
= e
->src
;
1291 rtx insn
= BB_END (src
);
1293 /* We can only redirect non-fallthru edges of jump insn. */
1294 if (e
->flags
& EDGE_FALLTHRU
)
1296 else if (!JUMP_P (insn
) && !currently_expanding_to_rtl
)
1299 if (!currently_expanding_to_rtl
)
1301 if (!patch_jump_insn (insn
, old_label
, target
))
1305 /* When expanding this BB might actually contain multiple
1306 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1307 Redirect all of those that match our label. */
1308 FOR_BB_INSNS (src
, insn
)
1309 if (JUMP_P (insn
) && !patch_jump_insn (insn
, old_label
, target
))
1313 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
1314 e
->src
->index
, e
->dest
->index
, target
->index
);
1316 if (e
->dest
!= target
)
1317 e
= redirect_edge_succ_nodup (e
, target
);
1322 /* Called when edge E has been redirected to a new destination,
1323 in order to update the region crossing flag on the edge and
1327 fixup_partition_crossing (edge e
)
1331 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || e
->dest
1332 == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1334 /* If we redirected an existing edge, it may already be marked
1335 crossing, even though the new src is missing a reg crossing note.
1336 But make sure reg crossing note doesn't already exist before
1338 if (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1340 e
->flags
|= EDGE_CROSSING
;
1341 note
= find_reg_note (BB_END (e
->src
), REG_CROSSING_JUMP
, NULL_RTX
);
1342 if (JUMP_P (BB_END (e
->src
))
1344 add_reg_note (BB_END (e
->src
), REG_CROSSING_JUMP
, NULL_RTX
);
1346 else if (BB_PARTITION (e
->src
) == BB_PARTITION (e
->dest
))
1348 e
->flags
&= ~EDGE_CROSSING
;
1349 /* Remove the section crossing note from jump at end of
1350 src if it exists, and if no other successors are
1352 note
= find_reg_note (BB_END (e
->src
), REG_CROSSING_JUMP
, NULL_RTX
);
1355 bool has_crossing_succ
= false;
1358 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
1360 has_crossing_succ
|= (e2
->flags
& EDGE_CROSSING
);
1361 if (has_crossing_succ
)
1364 if (!has_crossing_succ
)
1365 remove_note (BB_END (e
->src
), note
);
1370 /* Called when block BB has been reassigned to the cold partition,
1371 because it is now dominated by another cold block,
1372 to ensure that the region crossing attributes are updated. */
1375 fixup_new_cold_bb (basic_block bb
)
1380 /* This is called when a hot bb is found to now be dominated
1381 by a cold bb and therefore needs to become cold. Therefore,
1382 its preds will no longer be region crossing. Any non-dominating
1383 preds that were previously hot would also have become cold
1384 in the caller for the same region. Any preds that were previously
1385 region-crossing will be adjusted in fixup_partition_crossing. */
1386 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1388 fixup_partition_crossing (e
);
1391 /* Possibly need to make bb's successor edges region crossing,
1392 or remove stale region crossing. */
1393 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1395 /* We can't have fall-through edges across partition boundaries.
1396 Note that force_nonfallthru will do any necessary partition
1397 boundary fixup by calling fixup_partition_crossing itself. */
1398 if ((e
->flags
& EDGE_FALLTHRU
)
1399 && BB_PARTITION (bb
) != BB_PARTITION (e
->dest
)
1400 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1401 force_nonfallthru (e
);
1403 fixup_partition_crossing (e
);
1407 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1408 expense of adding new instructions or reordering basic blocks.
1410 Function can be also called with edge destination equivalent to the TARGET.
1411 Then it should try the simplifications and do nothing if none is possible.
1413 Return edge representing the branch if transformation succeeded. Return NULL
1415 We still return NULL in case E already destinated TARGET and we didn't
1416 managed to simplify instruction stream. */
1419 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
1422 basic_block src
= e
->src
;
1423 basic_block dest
= e
->dest
;
1425 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1431 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
1433 df_set_bb_dirty (src
);
1434 fixup_partition_crossing (ret
);
1438 ret
= redirect_branch_edge (e
, target
);
1442 df_set_bb_dirty (src
);
1443 fixup_partition_crossing (ret
);
1447 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1450 emit_barrier_after_bb (basic_block bb
)
1452 rtx barrier
= emit_barrier_after (BB_END (bb
));
1453 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1454 || current_ir_type () == IR_RTL_CFGLAYOUT
);
1455 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
1456 BB_FOOTER (bb
) = unlink_insn_chain (barrier
, barrier
);
1459 /* Like force_nonfallthru below, but additionally performs redirection
1460 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1461 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1462 simple_return_rtx, indicating which kind of returnjump to create.
1463 It should be NULL otherwise. */
1466 force_nonfallthru_and_redirect (edge e
, basic_block target
, rtx jump_label
)
1468 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
1471 int abnormal_edge_flags
= 0;
1472 bool asm_goto_edge
= false;
1475 /* In the case the last instruction is conditional jump to the next
1476 instruction, first redirect the jump itself and then continue
1477 by creating a basic block afterwards to redirect fallthru edge. */
1478 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1479 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1480 && any_condjump_p (BB_END (e
->src
))
1481 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1484 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1487 redirected
= redirect_jump (BB_END (e
->src
), block_label (target
), 0);
1488 gcc_assert (redirected
);
1490 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1493 int prob
= XINT (note
, 0);
1495 b
->probability
= prob
;
1496 /* Update this to use GCOV_COMPUTE_SCALE. */
1497 b
->count
= e
->count
* prob
/ REG_BR_PROB_BASE
;
1498 e
->probability
-= e
->probability
;
1499 e
->count
-= b
->count
;
1500 if (e
->probability
< 0)
1507 if (e
->flags
& EDGE_ABNORMAL
)
1509 /* Irritating special case - fallthru edge to the same block as abnormal
1511 We can't redirect abnormal edge, but we still can split the fallthru
1512 one and create separate abnormal edge to original destination.
1513 This allows bb-reorder to make such edge non-fallthru. */
1514 gcc_assert (e
->dest
== target
);
1515 abnormal_edge_flags
= e
->flags
& ~EDGE_FALLTHRU
;
1516 e
->flags
&= EDGE_FALLTHRU
;
1520 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1521 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1523 /* We can't redirect the entry block. Create an empty block
1524 at the start of the function which we use to add the new
1530 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
,
1531 ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1533 /* Change the existing edge's source to be the new block, and add
1534 a new edge from the entry block to the new block. */
1536 for (ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
1537 (tmp
= ei_safe_edge (ei
)); )
1541 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
->unordered_remove (ei
.index
);
1551 vec_safe_push (bb
->succs
, e
);
1552 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
,
1557 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1558 don't point to the target or fallthru label. */
1559 if (JUMP_P (BB_END (e
->src
))
1560 && target
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1561 && (e
->flags
& EDGE_FALLTHRU
)
1562 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
1564 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
1565 bool adjust_jump_target
= false;
1567 for (i
= 0; i
< n
; ++i
)
1569 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (e
->dest
))
1571 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))--;
1572 XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) = block_label (target
);
1573 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))++;
1574 adjust_jump_target
= true;
1576 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (target
))
1577 asm_goto_edge
= true;
1579 if (adjust_jump_target
)
1581 rtx insn
= BB_END (e
->src
), note
;
1582 rtx old_label
= BB_HEAD (e
->dest
);
1583 rtx new_label
= BB_HEAD (target
);
1585 if (JUMP_LABEL (insn
) == old_label
)
1587 JUMP_LABEL (insn
) = new_label
;
1588 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1590 remove_note (insn
, note
);
1594 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1596 remove_note (insn
, note
);
1597 if (JUMP_LABEL (insn
) != new_label
1598 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1599 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1601 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1603 XEXP (note
, 0) = new_label
;
1607 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
|| asm_goto_edge
)
1609 gcov_type count
= e
->count
;
1610 int probability
= e
->probability
;
1611 /* Create the new structures. */
1613 /* If the old block ended with a tablejump, skip its table
1614 by searching forward from there. Otherwise start searching
1615 forward from the last instruction of the old block. */
1616 if (!tablejump_p (BB_END (e
->src
), NULL
, ¬e
))
1617 note
= BB_END (e
->src
);
1618 note
= NEXT_INSN (note
);
1620 jump_block
= create_basic_block (note
, NULL
, e
->src
);
1621 jump_block
->count
= count
;
1622 jump_block
->frequency
= EDGE_FREQUENCY (e
);
1624 /* Make sure new block ends up in correct hot/cold section. */
1626 BB_COPY_PARTITION (jump_block
, e
->src
);
1629 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1630 new_edge
->probability
= probability
;
1631 new_edge
->count
= count
;
1633 /* Redirect old edge. */
1634 redirect_edge_pred (e
, jump_block
);
1635 e
->probability
= REG_BR_PROB_BASE
;
1637 /* If e->src was previously region crossing, it no longer is
1638 and the reg crossing note should be removed. */
1639 fixup_partition_crossing (new_edge
);
1641 /* If asm goto has any label refs to target's label,
1642 add also edge from asm goto bb to target. */
1645 new_edge
->probability
/= 2;
1646 new_edge
->count
/= 2;
1647 jump_block
->count
/= 2;
1648 jump_block
->frequency
/= 2;
1649 new_edge
= make_edge (new_edge
->src
, target
,
1650 e
->flags
& ~EDGE_FALLTHRU
);
1651 new_edge
->probability
= probability
- probability
/ 2;
1652 new_edge
->count
= count
- count
/ 2;
1655 new_bb
= jump_block
;
1658 jump_block
= e
->src
;
1660 loc
= e
->goto_locus
;
1661 e
->flags
&= ~EDGE_FALLTHRU
;
1662 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1664 if (jump_label
== ret_rtx
)
1667 emit_jump_insn_after_setloc (gen_return (), BB_END (jump_block
), loc
);
1674 gcc_assert (jump_label
== simple_return_rtx
);
1675 #ifdef HAVE_simple_return
1676 emit_jump_insn_after_setloc (gen_simple_return (),
1677 BB_END (jump_block
), loc
);
1682 set_return_jump_label (BB_END (jump_block
));
1686 rtx label
= block_label (target
);
1687 emit_jump_insn_after_setloc (gen_jump (label
), BB_END (jump_block
), loc
);
1688 JUMP_LABEL (BB_END (jump_block
)) = label
;
1689 LABEL_NUSES (label
)++;
1692 /* We might be in cfg layout mode, and if so, the following routine will
1693 insert the barrier correctly. */
1694 emit_barrier_after_bb (jump_block
);
1695 redirect_edge_succ_nodup (e
, target
);
1697 if (abnormal_edge_flags
)
1698 make_edge (src
, target
, abnormal_edge_flags
);
1700 df_mark_solutions_dirty ();
1701 fixup_partition_crossing (e
);
1705 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1706 (and possibly create new basic block) to make edge non-fallthru.
1707 Return newly created BB or NULL if none. */
1710 rtl_force_nonfallthru (edge e
)
1712 return force_nonfallthru_and_redirect (e
, e
->dest
, NULL_RTX
);
1715 /* Redirect edge even at the expense of creating new jump insn or
1716 basic block. Return new basic block if created, NULL otherwise.
1717 Conversion must be possible. */
1720 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1722 if (redirect_edge_and_branch (e
, target
)
1723 || e
->dest
== target
)
1726 /* In case the edge redirection failed, try to force it to be non-fallthru
1727 and redirect newly created simplejump. */
1728 df_set_bb_dirty (e
->src
);
1729 return force_nonfallthru_and_redirect (e
, target
, NULL_RTX
);
1732 /* The given edge should potentially be a fallthru edge. If that is in
1733 fact true, delete the jump and barriers that are in the way. */
1736 rtl_tidy_fallthru_edge (edge e
)
1739 basic_block b
= e
->src
, c
= b
->next_bb
;
1741 /* ??? In a late-running flow pass, other folks may have deleted basic
1742 blocks by nopping out blocks, leaving multiple BARRIERs between here
1743 and the target label. They ought to be chastised and fixed.
1745 We can also wind up with a sequence of undeletable labels between
1746 one block and the next.
1748 So search through a sequence of barriers, labels, and notes for
1749 the head of block C and assert that we really do fall through. */
1751 for (q
= NEXT_INSN (BB_END (b
)); q
!= BB_HEAD (c
); q
= NEXT_INSN (q
))
1755 /* Remove what will soon cease being the jump insn from the source block.
1756 If block B consisted only of this single jump, turn it into a deleted
1761 && (any_uncondjump_p (q
)
1762 || single_succ_p (b
)))
1766 if (tablejump_p (q
, &label
, &table
))
1768 /* The label is likely mentioned in some instruction before
1769 the tablejump and might not be DCEd, so turn it into
1770 a note instead and move before the tablejump that is going to
1772 const char *name
= LABEL_NAME (label
);
1773 PUT_CODE (label
, NOTE
);
1774 NOTE_KIND (label
) = NOTE_INSN_DELETED_LABEL
;
1775 NOTE_DELETED_LABEL_NAME (label
) = name
;
1776 reorder_insns (label
, label
, PREV_INSN (q
));
1777 delete_insn (table
);
1781 /* If this was a conditional jump, we need to also delete
1782 the insn that set cc0. */
1783 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1790 /* Selectively unlink the sequence. */
1791 if (q
!= PREV_INSN (BB_HEAD (c
)))
1792 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1794 e
->flags
|= EDGE_FALLTHRU
;
1797 /* Should move basic block BB after basic block AFTER. NIY. */
1800 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1801 basic_block after ATTRIBUTE_UNUSED
)
1806 /* Locate the last bb in the same partition as START_BB. */
1809 last_bb_in_partition (basic_block start_bb
)
1812 FOR_BB_BETWEEN (bb
, start_bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1814 if (BB_PARTITION (start_bb
) != BB_PARTITION (bb
->next_bb
))
1817 /* Return bb before the exit block. */
1821 /* Split a (typically critical) edge. Return the new block.
1822 The edge must not be abnormal.
1824 ??? The code generally expects to be called on critical edges.
1825 The case of a block ending in an unconditional jump to a
1826 block with multiple predecessors is not handled optimally. */
1829 rtl_split_edge (edge edge_in
)
1831 basic_block bb
, new_bb
;
1834 /* Abnormal edges cannot be split. */
1835 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1837 /* We are going to place the new block in front of edge destination.
1838 Avoid existence of fallthru predecessors. */
1839 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1841 edge e
= find_fallthru_edge (edge_in
->dest
->preds
);
1844 force_nonfallthru (e
);
1847 /* Create the basic block note. */
1848 if (edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1849 before
= BB_HEAD (edge_in
->dest
);
1853 /* If this is a fall through edge to the exit block, the blocks might be
1854 not adjacent, and the right place is after the source. */
1855 if ((edge_in
->flags
& EDGE_FALLTHRU
)
1856 && edge_in
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1858 before
= NEXT_INSN (BB_END (edge_in
->src
));
1859 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1860 BB_COPY_PARTITION (bb
, edge_in
->src
);
1864 if (edge_in
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1866 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1867 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1871 basic_block after
= edge_in
->dest
->prev_bb
;
1872 /* If this is post-bb reordering, and the edge crosses a partition
1873 boundary, the new block needs to be inserted in the bb chain
1874 at the end of the src partition (since we put the new bb into
1875 that partition, see below). Otherwise we may end up creating
1876 an extra partition crossing in the chain, which is illegal.
1877 It can't go after the src, because src may have a fall-through
1878 to a different block. */
1879 if (crtl
->bb_reorder_complete
1880 && (edge_in
->flags
& EDGE_CROSSING
))
1882 after
= last_bb_in_partition (edge_in
->src
);
1883 before
= NEXT_INSN (BB_END (after
));
1884 /* The instruction following the last bb in partition should
1885 be a barrier, since it cannot end in a fall-through. */
1886 gcc_checking_assert (BARRIER_P (before
));
1887 before
= NEXT_INSN (before
);
1889 bb
= create_basic_block (before
, NULL
, after
);
1890 /* Put the split bb into the src partition, to avoid creating
1891 a situation where a cold bb dominates a hot bb, in the case
1892 where src is cold and dest is hot. The src will dominate
1893 the new bb (whereas it might not have dominated dest). */
1894 BB_COPY_PARTITION (bb
, edge_in
->src
);
1898 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1900 /* Can't allow a region crossing edge to be fallthrough. */
1901 if (BB_PARTITION (bb
) != BB_PARTITION (edge_in
->dest
)
1902 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1904 new_bb
= force_nonfallthru (single_succ_edge (bb
));
1905 gcc_assert (!new_bb
);
1908 /* For non-fallthru edges, we must adjust the predecessor's
1909 jump instruction to target our new block. */
1910 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1912 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1913 gcc_assert (redirected
);
1917 if (edge_in
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1919 /* For asm goto even splitting of fallthru edge might
1920 need insn patching, as other labels might point to the
1922 rtx last
= BB_END (edge_in
->src
);
1925 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1926 && extract_asm_operands (PATTERN (last
)) != NULL_RTX
1927 && patch_jump_insn (last
, before
, bb
))
1928 df_set_bb_dirty (edge_in
->src
);
1930 redirect_edge_succ (edge_in
, bb
);
1936 /* Queue instructions for insertion on an edge between two basic blocks.
1937 The new instructions and basic blocks (if any) will not appear in the
1938 CFG until commit_edge_insertions is called. */
1941 insert_insn_on_edge (rtx pattern
, edge e
)
1943 /* We cannot insert instructions on an abnormal critical edge.
1944 It will be easier to find the culprit if we die now. */
1945 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1947 if (e
->insns
.r
== NULL_RTX
)
1950 push_to_sequence (e
->insns
.r
);
1952 emit_insn (pattern
);
1954 e
->insns
.r
= get_insns ();
1958 /* Update the CFG for the instructions queued on edge E. */
1961 commit_one_edge_insertion (edge e
)
1963 rtx before
= NULL_RTX
, after
= NULL_RTX
, insns
, tmp
, last
;
1966 /* Pull the insns off the edge now since the edge might go away. */
1968 e
->insns
.r
= NULL_RTX
;
1970 /* Figure out where to put these insns. If the destination has
1971 one predecessor, insert there. Except for the exit block. */
1972 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1976 /* Get the location correct wrt a code label, and "nice" wrt
1977 a basic block note, and before everything else. */
1980 tmp
= NEXT_INSN (tmp
);
1981 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1982 tmp
= NEXT_INSN (tmp
);
1983 if (tmp
== BB_HEAD (bb
))
1986 after
= PREV_INSN (tmp
);
1988 after
= get_last_insn ();
1991 /* If the source has one successor and the edge is not abnormal,
1992 insert there. Except for the entry block.
1993 Don't do this if the predecessor ends in a jump other than
1994 unconditional simple jump. E.g. for asm goto that points all
1995 its labels at the fallthru basic block, we can't insert instructions
1996 before the asm goto, as the asm goto can have various of side effects,
1997 and can't emit instructions after the asm goto, as it must end
1999 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
2000 && single_succ_p (e
->src
)
2001 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2002 && (!JUMP_P (BB_END (e
->src
))
2003 || simplejump_p (BB_END (e
->src
))))
2007 /* It is possible to have a non-simple jump here. Consider a target
2008 where some forms of unconditional jumps clobber a register. This
2009 happens on the fr30 for example.
2011 We know this block has a single successor, so we can just emit
2012 the queued insns before the jump. */
2013 if (JUMP_P (BB_END (bb
)))
2014 before
= BB_END (bb
);
2017 /* We'd better be fallthru, or we've lost track of what's what. */
2018 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
2020 after
= BB_END (bb
);
2024 /* Otherwise we must split the edge. */
2027 bb
= split_edge (e
);
2029 /* If E crossed a partition boundary, we needed to make bb end in
2030 a region-crossing jump, even though it was originally fallthru. */
2031 if (JUMP_P (BB_END (bb
)))
2032 before
= BB_END (bb
);
2034 after
= BB_END (bb
);
2037 /* Now that we've found the spot, do the insertion. */
2040 emit_insn_before_noloc (insns
, before
, bb
);
2041 last
= prev_nonnote_insn (before
);
2044 last
= emit_insn_after_noloc (insns
, after
, bb
);
2046 if (returnjump_p (last
))
2048 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2049 This is not currently a problem because this only happens
2050 for the (single) epilogue, which already has a fallthru edge
2053 e
= single_succ_edge (bb
);
2054 gcc_assert (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2055 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
2057 e
->flags
&= ~EDGE_FALLTHRU
;
2058 emit_barrier_after (last
);
2061 delete_insn (before
);
2064 gcc_assert (!JUMP_P (last
));
2067 /* Update the CFG for all queued instructions. */
2070 commit_edge_insertions (void)
2074 /* Optimization passes that invoke this routine can cause hot blocks
2075 previously reached by both hot and cold blocks to become dominated only
2076 by cold blocks. This will cause the verification below to fail,
2077 and lead to now cold code in the hot section. In some cases this
2078 may only be visible after newly unreachable blocks are deleted,
2079 which will be done by fixup_partitions. */
2080 fixup_partitions ();
2082 #ifdef ENABLE_CHECKING
2083 verify_flow_info ();
2086 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
2087 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
2092 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2094 commit_one_edge_insertion (e
);
2099 /* Print out RTL-specific basic block information (live information
2100 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2101 documented in dumpfile.h. */
2104 rtl_dump_bb (FILE *outf
, basic_block bb
, int indent
, int flags
)
2110 s_indent
= (char *) alloca ((size_t) indent
+ 1);
2111 memset (s_indent
, ' ', (size_t) indent
);
2112 s_indent
[indent
] = '\0';
2114 if (df
&& (flags
& TDF_DETAILS
))
2116 df_dump_top (bb
, outf
);
2120 if (bb
->index
!= ENTRY_BLOCK
&& bb
->index
!= EXIT_BLOCK
)
2121 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
)); insn
!= last
;
2122 insn
= NEXT_INSN (insn
))
2124 if (flags
& TDF_DETAILS
)
2125 df_dump_insn_top (insn
, outf
);
2126 if (! (flags
& TDF_SLIM
))
2127 print_rtl_single (outf
, insn
);
2129 dump_insn_slim (outf
, insn
);
2130 if (flags
& TDF_DETAILS
)
2131 df_dump_insn_bottom (insn
, outf
);
2134 if (df
&& (flags
& TDF_DETAILS
))
2136 df_dump_bottom (bb
, outf
);
2142 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2143 for the start of each basic block. FLAGS are the TDF_* masks documented
2147 print_rtl_with_bb (FILE *outf
, const_rtx rtx_first
, int flags
)
2151 fprintf (outf
, "(nil)\n");
2154 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
2155 int max_uid
= get_max_uid ();
2156 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
2157 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
2158 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
2161 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2162 insns, but the CFG is not maintained so the basic block info
2163 is not reliable. Therefore it's omitted from the dumps. */
2164 if (! (cfun
->curr_properties
& PROP_cfg
))
2165 flags
&= ~TDF_BLOCKS
;
2168 df_dump_start (outf
);
2170 if (flags
& TDF_BLOCKS
)
2172 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2176 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
2177 end
[INSN_UID (BB_END (bb
))] = bb
;
2178 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
2180 enum bb_state state
= IN_MULTIPLE_BB
;
2182 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
2184 in_bb_p
[INSN_UID (x
)] = state
;
2186 if (x
== BB_END (bb
))
2192 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
2194 if (flags
& TDF_BLOCKS
)
2196 bb
= start
[INSN_UID (tmp_rtx
)];
2199 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, true, false);
2200 if (df
&& (flags
& TDF_DETAILS
))
2201 df_dump_top (bb
, outf
);
2204 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
2205 && !NOTE_P (tmp_rtx
)
2206 && !BARRIER_P (tmp_rtx
))
2207 fprintf (outf
, ";; Insn is not within a basic block\n");
2208 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
2209 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
2212 if (flags
& TDF_DETAILS
)
2213 df_dump_insn_top (tmp_rtx
, outf
);
2214 if (! (flags
& TDF_SLIM
))
2215 print_rtl_single (outf
, tmp_rtx
);
2217 dump_insn_slim (outf
, tmp_rtx
);
2218 if (flags
& TDF_DETAILS
)
2219 df_dump_insn_bottom (tmp_rtx
, outf
);
2221 if (flags
& TDF_BLOCKS
)
2223 bb
= end
[INSN_UID (tmp_rtx
)];
2226 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, false, true);
2227 if (df
&& (flags
& TDF_DETAILS
))
2228 df_dump_bottom (bb
, outf
);
2240 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2243 update_br_prob_note (basic_block bb
)
2246 if (!JUMP_P (BB_END (bb
)))
2248 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
2249 if (!note
|| XINT (note
, 0) == BRANCH_EDGE (bb
)->probability
)
2251 XINT (note
, 0) = BRANCH_EDGE (bb
)->probability
;
2254 /* Get the last insn associated with block BB (that includes barriers and
2255 tablejumps after BB). */
2257 get_last_bb_insn (basic_block bb
)
2260 rtx end
= BB_END (bb
);
2262 /* Include any jump table following the basic block. */
2263 if (tablejump_p (end
, NULL
, &tmp
))
2266 /* Include any barriers that may follow the basic block. */
2267 tmp
= next_nonnote_insn_bb (end
);
2268 while (tmp
&& BARRIER_P (tmp
))
2271 tmp
= next_nonnote_insn_bb (end
);
2277 /* Sanity check partition hotness to ensure that basic blocks in
2278 Â the cold partition don't dominate basic blocks in the hot partition.
2279 If FLAG_ONLY is true, report violations as errors. Otherwise
2280 re-mark the dominated blocks as cold, since this is run after
2281 cfg optimizations that may make hot blocks previously reached
2282 by both hot and cold blocks now only reachable along cold paths. */
2284 static vec
<basic_block
>
2285 find_partition_fixes (bool flag_only
)
2288 vec
<basic_block
> bbs_in_cold_partition
= vNULL
;
2289 vec
<basic_block
> bbs_to_fix
= vNULL
;
2291 /* Callers check this. */
2292 gcc_checking_assert (crtl
->has_bb_partition
);
2294 FOR_EACH_BB_FN (bb
, cfun
)
2295 if ((BB_PARTITION (bb
) == BB_COLD_PARTITION
))
2296 bbs_in_cold_partition
.safe_push (bb
);
2298 if (bbs_in_cold_partition
.is_empty ())
2301 bool dom_calculated_here
= !dom_info_available_p (CDI_DOMINATORS
);
2303 if (dom_calculated_here
)
2304 calculate_dominance_info (CDI_DOMINATORS
);
2306 while (! bbs_in_cold_partition
.is_empty ())
2308 bb
= bbs_in_cold_partition
.pop ();
2309 /* Any blocks dominated by a block in the cold section
2310 must also be cold. */
2312 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2314 son
= next_dom_son (CDI_DOMINATORS
, son
))
2316 /* If son is not yet cold, then mark it cold here and
2317 enqueue it for further processing. */
2318 if ((BB_PARTITION (son
) != BB_COLD_PARTITION
))
2321 error ("non-cold basic block %d dominated "
2322 "by a block in the cold partition (%d)", son
->index
, bb
->index
);
2324 BB_SET_PARTITION (son
, BB_COLD_PARTITION
);
2325 bbs_to_fix
.safe_push (son
);
2326 bbs_in_cold_partition
.safe_push (son
);
2331 if (dom_calculated_here
)
2332 free_dominance_info (CDI_DOMINATORS
);
2337 /* Perform cleanup on the hot/cold bb partitioning after optimization
2338 passes that modify the cfg. */
2341 fixup_partitions (void)
2345 if (!crtl
->has_bb_partition
)
2348 /* Delete any blocks that became unreachable and weren't
2349 already cleaned up, for example during edge forwarding
2350 and convert_jumps_to_returns. This will expose more
2351 opportunities for fixing the partition boundaries here.
2352 Also, the calculation of the dominance graph during verification
2353 will assert if there are unreachable nodes. */
2354 delete_unreachable_blocks ();
2356 /* If there are partitions, do a sanity check on them: A basic block in
2357 Â a cold partition cannot dominate a basic block in a hot partition.
2358 Fixup any that now violate this requirement, as a result of edge
2359 forwarding and unreachable block deletion. Â */
2360 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (false);
2362 /* Do the partition fixup after all necessary blocks have been converted to
2363 cold, so that we only update the region crossings the minimum number of
2364 places, which can require forcing edges to be non fallthru. */
2365 while (! bbs_to_fix
.is_empty ())
2367 bb
= bbs_to_fix
.pop ();
2368 fixup_new_cold_bb (bb
);
2372 /* Verify, in the basic block chain, that there is at most one switch
2373 between hot/cold partitions. This condition will not be true until
2374 after reorder_basic_blocks is called. */
2377 verify_hot_cold_block_grouping (void)
2381 bool switched_sections
= false;
2382 int current_partition
= BB_UNPARTITIONED
;
2384 /* Even after bb reordering is complete, we go into cfglayout mode
2385 again (in compgoto). Ensure we don't call this before going back
2386 into linearized RTL when any layout fixes would have been committed. */
2387 if (!crtl
->bb_reorder_complete
2388 || current_ir_type () != IR_RTL_CFGRTL
)
2391 FOR_EACH_BB_FN (bb
, cfun
)
2393 if (current_partition
!= BB_UNPARTITIONED
2394 && BB_PARTITION (bb
) != current_partition
)
2396 if (switched_sections
)
2398 error ("multiple hot/cold transitions found (bb %i)",
2403 switched_sections
= true;
2405 if (!crtl
->has_bb_partition
)
2406 error ("partition found but function partition flag not set");
2408 current_partition
= BB_PARTITION (bb
);
2415 /* Perform several checks on the edges out of each block, such as
2416 the consistency of the branch probabilities, the correctness
2417 of hot/cold partition crossing edges, and the number of expected
2418 successor edges. Also verify that the dominance relationship
2419 between hot/cold blocks is sane. */
2422 rtl_verify_edges (void)
2427 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2429 int n_fallthru
= 0, n_branch
= 0, n_abnormal_call
= 0, n_sibcall
= 0;
2430 int n_eh
= 0, n_abnormal
= 0;
2431 edge e
, fallthru
= NULL
;
2434 bool has_crossing_edge
= false;
2436 if (JUMP_P (BB_END (bb
))
2437 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
2438 && EDGE_COUNT (bb
->succs
) >= 2
2439 && any_condjump_p (BB_END (bb
)))
2441 if (XINT (note
, 0) != BRANCH_EDGE (bb
)->probability
2442 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2444 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2445 XINT (note
, 0), BRANCH_EDGE (bb
)->probability
);
2450 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2454 if (e
->flags
& EDGE_FALLTHRU
)
2455 n_fallthru
++, fallthru
= e
;
2457 is_crossing
= (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
2458 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2459 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
2460 has_crossing_edge
|= is_crossing
;
2461 if (e
->flags
& EDGE_CROSSING
)
2465 error ("EDGE_CROSSING incorrectly set across same section");
2468 if (e
->flags
& EDGE_FALLTHRU
)
2470 error ("fallthru edge crosses section boundary in bb %i",
2474 if (e
->flags
& EDGE_EH
)
2476 error ("EH edge crosses section boundary in bb %i",
2480 if (JUMP_P (BB_END (bb
))
2481 && !find_reg_note (BB_END (bb
), REG_CROSSING_JUMP
, NULL_RTX
))
2483 error ("No region crossing jump at section boundary in bb %i",
2488 else if (is_crossing
)
2490 error ("EDGE_CROSSING missing across section boundary");
2494 if ((e
->flags
& ~(EDGE_DFS_BACK
2496 | EDGE_IRREDUCIBLE_LOOP
2499 | EDGE_PRESERVE
)) == 0)
2502 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2505 if (e
->flags
& EDGE_SIBCALL
)
2508 if (e
->flags
& EDGE_EH
)
2511 if (e
->flags
& EDGE_ABNORMAL
)
2515 if (!has_crossing_edge
2516 && find_reg_note (BB_END (bb
), REG_CROSSING_JUMP
, NULL_RTX
))
2518 print_rtl_with_bb (stderr
, get_insns (), TDF_RTL
| TDF_BLOCKS
| TDF_DETAILS
);
2519 error ("Region crossing jump across same section in bb %i",
2524 if (n_eh
&& !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
2526 error ("missing REG_EH_REGION note at the end of bb %i", bb
->index
);
2531 error ("too many exception handling edges in bb %i", bb
->index
);
2535 && (!JUMP_P (BB_END (bb
))
2536 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
2537 || any_condjump_p (BB_END (bb
))))))
2539 error ("too many outgoing branch edges from bb %i", bb
->index
);
2542 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
2544 error ("fallthru edge after unconditional jump in bb %i", bb
->index
);
2547 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
2549 error ("wrong number of branch edges after unconditional jump"
2550 " in bb %i", bb
->index
);
2553 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
2554 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
2556 error ("wrong amount of branch edges after conditional jump"
2557 " in bb %i", bb
->index
);
2560 if (n_abnormal_call
&& !CALL_P (BB_END (bb
)))
2562 error ("abnormal call edges for non-call insn in bb %i", bb
->index
);
2565 if (n_sibcall
&& !CALL_P (BB_END (bb
)))
2567 error ("sibcall edges for non-call insn in bb %i", bb
->index
);
2570 if (n_abnormal
> n_eh
2571 && !(CALL_P (BB_END (bb
))
2572 && n_abnormal
== n_abnormal_call
+ n_sibcall
)
2573 && (!JUMP_P (BB_END (bb
))
2574 || any_condjump_p (BB_END (bb
))
2575 || any_uncondjump_p (BB_END (bb
))))
2577 error ("abnormal edges for no purpose in bb %i", bb
->index
);
2582 /* If there are partitions, do a sanity check on them: A basic block in
2583 Â a cold partition cannot dominate a basic block in a hot partition. Â */
2584 if (crtl
->has_bb_partition
&& !err
)
2586 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (true);
2587 err
= !bbs_to_fix
.is_empty ();
2594 /* Checks on the instructions within blocks. Currently checks that each
2595 block starts with a basic block note, and that basic block notes and
2596 control flow jumps are not found in the middle of the block. */
2599 rtl_verify_bb_insns (void)
2605 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2607 /* Now check the header of basic
2608 block. It ought to contain optional CODE_LABEL followed
2609 by NOTE_BASIC_BLOCK. */
2613 if (BB_END (bb
) == x
)
2615 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2623 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2625 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2630 if (BB_END (bb
) == x
)
2631 /* Do checks for empty blocks here. */
2634 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2636 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2638 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2639 INSN_UID (x
), bb
->index
);
2643 if (x
== BB_END (bb
))
2646 if (control_flow_insn_p (x
))
2648 error ("in basic block %d:", bb
->index
);
2649 fatal_insn ("flow control insn inside a basic block", x
);
2658 /* Verify that block pointers for instructions in basic blocks, headers and
2659 footers are set appropriately. */
2662 rtl_verify_bb_pointers (void)
2667 /* Check the general integrity of the basic blocks. */
2668 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2672 if (!(bb
->flags
& BB_RTL
))
2674 error ("BB_RTL flag not set for block %d", bb
->index
);
2678 FOR_BB_INSNS (bb
, insn
)
2679 if (BLOCK_FOR_INSN (insn
) != bb
)
2681 error ("insn %d basic block pointer is %d, should be %d",
2683 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
2688 for (insn
= BB_HEADER (bb
); insn
; insn
= NEXT_INSN (insn
))
2689 if (!BARRIER_P (insn
)
2690 && BLOCK_FOR_INSN (insn
) != NULL
)
2692 error ("insn %d in header of bb %d has non-NULL basic block",
2693 INSN_UID (insn
), bb
->index
);
2696 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
2697 if (!BARRIER_P (insn
)
2698 && BLOCK_FOR_INSN (insn
) != NULL
)
2700 error ("insn %d in footer of bb %d has non-NULL basic block",
2701 INSN_UID (insn
), bb
->index
);
2710 /* Verify the CFG and RTL consistency common for both underlying RTL and
2713 Currently it does following checks:
2715 - overlapping of basic blocks
2716 - insns with wrong BLOCK_FOR_INSN pointers
2717 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2718 - tails of basic blocks (ensure that boundary is necessary)
2719 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2720 and NOTE_INSN_BASIC_BLOCK
2721 - verify that no fall_thru edge crosses hot/cold partition boundaries
2722 - verify that there are no pending RTL branch predictions
2723 - verify that hot blocks are not dominated by cold blocks
2725 In future it can be extended check a lot of other stuff as well
2726 (reachability of basic blocks, life information, etc. etc.). */
2729 rtl_verify_flow_info_1 (void)
2733 err
|= rtl_verify_bb_pointers ();
2735 err
|= rtl_verify_bb_insns ();
2737 err
|= rtl_verify_edges ();
2742 /* Walk the instruction chain and verify that bb head/end pointers
2743 are correct, and that instructions are in exactly one bb and have
2744 correct block pointers. */
2747 rtl_verify_bb_insn_chain (void)
2752 rtx last_head
= get_last_insn ();
2753 basic_block
*bb_info
;
2754 const int max_uid
= get_max_uid ();
2756 bb_info
= XCNEWVEC (basic_block
, max_uid
);
2758 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2760 rtx head
= BB_HEAD (bb
);
2761 rtx end
= BB_END (bb
);
2763 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2765 /* Verify the end of the basic block is in the INSN chain. */
2769 /* And that the code outside of basic blocks has NULL bb field. */
2771 && BLOCK_FOR_INSN (x
) != NULL
)
2773 error ("insn %d outside of basic blocks has non-NULL bb field",
2781 error ("end insn %d for block %d not found in the insn stream",
2782 INSN_UID (end
), bb
->index
);
2786 /* Work backwards from the end to the head of the basic block
2787 to verify the head is in the RTL chain. */
2788 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2790 /* While walking over the insn chain, verify insns appear
2791 in only one basic block. */
2792 if (bb_info
[INSN_UID (x
)] != NULL
)
2794 error ("insn %d is in multiple basic blocks (%d and %d)",
2795 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2799 bb_info
[INSN_UID (x
)] = bb
;
2806 error ("head insn %d for block %d not found in the insn stream",
2807 INSN_UID (head
), bb
->index
);
2811 last_head
= PREV_INSN (x
);
2814 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2816 /* Check that the code before the first basic block has NULL
2819 && BLOCK_FOR_INSN (x
) != NULL
)
2821 error ("insn %d outside of basic blocks has non-NULL bb field",
2831 /* Verify that fallthru edges point to adjacent blocks in layout order and
2832 that barriers exist after non-fallthru blocks. */
2835 rtl_verify_fallthru (void)
2840 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2844 e
= find_fallthru_edge (bb
->succs
);
2849 /* Ensure existence of barrier in BB with no fallthru edges. */
2850 for (insn
= NEXT_INSN (BB_END (bb
)); ; insn
= NEXT_INSN (insn
))
2852 if (!insn
|| NOTE_INSN_BASIC_BLOCK_P (insn
))
2854 error ("missing barrier after block %i", bb
->index
);
2858 if (BARRIER_P (insn
))
2862 else if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2863 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2867 if (e
->src
->next_bb
!= e
->dest
)
2870 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2871 e
->src
->index
, e
->dest
->index
);
2875 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
2876 insn
= NEXT_INSN (insn
))
2877 if (BARRIER_P (insn
) || INSN_P (insn
))
2879 error ("verify_flow_info: Incorrect fallthru %i->%i",
2880 e
->src
->index
, e
->dest
->index
);
2881 fatal_insn ("wrong insn in the fallthru edge", insn
);
2890 /* Verify that blocks are laid out in consecutive order. While walking the
2891 instructions, verify that all expected instructions are inside the basic
2892 blocks, and that all returns are followed by barriers. */
2895 rtl_verify_bb_layout (void)
2901 const rtx rtx_first
= get_insns ();
2902 basic_block last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
), curr_bb
= NULL
;
2905 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
2907 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2909 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2911 bb
= NOTE_BASIC_BLOCK (x
);
2914 if (bb
!= last_bb_seen
->next_bb
)
2915 internal_error ("basic blocks not laid down consecutively");
2917 curr_bb
= last_bb_seen
= bb
;
2922 switch (GET_CODE (x
))
2929 /* An ADDR_VEC is placed outside any basic block. */
2931 && JUMP_TABLE_DATA_P (NEXT_INSN (x
)))
2934 /* But in any case, non-deletable labels can appear anywhere. */
2938 fatal_insn ("insn outside basic block", x
);
2943 && returnjump_p (x
) && ! condjump_p (x
)
2944 && ! (next_nonnote_insn (x
) && BARRIER_P (next_nonnote_insn (x
))))
2945 fatal_insn ("return not followed by barrier", x
);
2947 if (curr_bb
&& x
== BB_END (curr_bb
))
2951 if (num_bb_notes
!= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
)
2953 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2954 num_bb_notes
, n_basic_blocks_for_fn (cfun
));
2959 /* Verify the CFG and RTL consistency common for both underlying RTL and
2960 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
2962 Currently it does following checks:
2963 - all checks of rtl_verify_flow_info_1
2964 - test head/end pointers
2965 - check that blocks are laid out in consecutive order
2966 - check that all insns are in the basic blocks
2967 (except the switch handling code, barriers and notes)
2968 - check that all returns are followed by barriers
2969 - check that all fallthru edge points to the adjacent blocks
2970 - verify that there is a single hot/cold partition boundary after bbro */
2973 rtl_verify_flow_info (void)
2977 err
|= rtl_verify_flow_info_1 ();
2979 err
|= rtl_verify_bb_insn_chain ();
2981 err
|= rtl_verify_fallthru ();
2983 err
|= rtl_verify_bb_layout ();
2985 err
|= verify_hot_cold_block_grouping ();
2990 /* Assume that the preceding pass has possibly eliminated jump instructions
2991 or converted the unconditional jumps. Eliminate the edges from CFG.
2992 Return true if any edges are eliminated. */
2995 purge_dead_edges (basic_block bb
)
2998 rtx insn
= BB_END (bb
), note
;
2999 bool purged
= false;
3003 if (DEBUG_INSN_P (insn
) && insn
!= BB_HEAD (bb
))
3005 insn
= PREV_INSN (insn
);
3006 while ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
));
3008 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3009 if (NONJUMP_INSN_P (insn
)
3010 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
3014 if (! may_trap_p (PATTERN (insn
))
3015 || ((eqnote
= find_reg_equal_equiv_note (insn
))
3016 && ! may_trap_p (XEXP (eqnote
, 0))))
3017 remove_note (insn
, note
);
3020 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3021 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3023 bool remove
= false;
3025 /* There are three types of edges we need to handle correctly here: EH
3026 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3027 latter can appear when nonlocal gotos are used. */
3028 if (e
->flags
& EDGE_ABNORMAL_CALL
)
3032 else if (can_nonlocal_goto (insn
))
3034 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3036 else if (flag_tm
&& find_reg_note (insn
, REG_TM
, NULL
))
3041 else if (e
->flags
& EDGE_EH
)
3042 remove
= !can_throw_internal (insn
);
3047 df_set_bb_dirty (bb
);
3060 /* We do care only about conditional jumps and simplejumps. */
3061 if (!any_condjump_p (insn
)
3062 && !returnjump_p (insn
)
3063 && !simplejump_p (insn
))
3066 /* Branch probability/prediction notes are defined only for
3067 condjumps. We've possibly turned condjump into simplejump. */
3068 if (simplejump_p (insn
))
3070 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3072 remove_note (insn
, note
);
3073 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
3074 remove_note (insn
, note
);
3077 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3079 /* Avoid abnormal flags to leak from computed jumps turned
3080 into simplejumps. */
3082 e
->flags
&= ~EDGE_ABNORMAL
;
3084 /* See if this edge is one we should keep. */
3085 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
3086 /* A conditional jump can fall through into the next
3087 block, so we should keep the edge. */
3092 else if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3093 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
3094 /* If the destination block is the target of the jump,
3100 else if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
3101 && returnjump_p (insn
))
3102 /* If the destination block is the exit block, and this
3103 instruction is a return, then keep the edge. */
3108 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3109 /* Keep the edges that correspond to exceptions thrown by
3110 this instruction and rematerialize the EDGE_ABNORMAL
3111 flag we just cleared above. */
3113 e
->flags
|= EDGE_ABNORMAL
;
3118 /* We do not need this edge. */
3119 df_set_bb_dirty (bb
);
3124 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
3128 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
3133 /* Redistribute probabilities. */
3134 if (single_succ_p (bb
))
3136 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3137 single_succ_edge (bb
)->count
= bb
->count
;
3141 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3145 b
= BRANCH_EDGE (bb
);
3146 f
= FALLTHRU_EDGE (bb
);
3147 b
->probability
= XINT (note
, 0);
3148 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
3149 /* Update these to use GCOV_COMPUTE_SCALE. */
3150 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
3151 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
3156 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
3158 /* First, there should not be any EH or ABCALL edges resulting
3159 from non-local gotos and the like. If there were, we shouldn't
3160 have created the sibcall in the first place. Second, there
3161 should of course never have been a fallthru edge. */
3162 gcc_assert (single_succ_p (bb
));
3163 gcc_assert (single_succ_edge (bb
)->flags
3164 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
3169 /* If we don't see a jump insn, we don't know exactly why the block would
3170 have been broken at this point. Look for a simple, non-fallthru edge,
3171 as these are only created by conditional branches. If we find such an
3172 edge we know that there used to be a jump here and can then safely
3173 remove all non-fallthru edges. */
3175 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3176 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
3185 /* Remove all but the fake and fallthru edges. The fake edge may be
3186 the only successor for this block in the case of noreturn
3188 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3190 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
3192 df_set_bb_dirty (bb
);
3200 gcc_assert (single_succ_p (bb
));
3202 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3203 single_succ_edge (bb
)->count
= bb
->count
;
3206 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
3211 /* Search all basic blocks for potentially dead edges and purge them. Return
3212 true if some edge has been eliminated. */
3215 purge_all_dead_edges (void)
3220 FOR_EACH_BB_FN (bb
, cfun
)
3222 bool purged_here
= purge_dead_edges (bb
);
3224 purged
|= purged_here
;
3230 /* This is used by a few passes that emit some instructions after abnormal
3231 calls, moving the basic block's end, while they in fact do want to emit
3232 them on the fallthru edge. Look for abnormal call edges, find backward
3233 the call in the block and insert the instructions on the edge instead.
3235 Similarly, handle instructions throwing exceptions internally.
3237 Return true when instructions have been found and inserted on edges. */
3240 fixup_abnormal_edges (void)
3242 bool inserted
= false;
3245 FOR_EACH_BB_FN (bb
, cfun
)
3250 /* Look for cases we are interested in - calls or instructions causing
3252 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3253 if ((e
->flags
& EDGE_ABNORMAL_CALL
)
3254 || ((e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
3255 == (EDGE_ABNORMAL
| EDGE_EH
)))
3258 if (e
&& !CALL_P (BB_END (bb
)) && !can_throw_internal (BB_END (bb
)))
3262 /* Get past the new insns generated. Allow notes, as the insns
3263 may be already deleted. */
3265 while ((NONJUMP_INSN_P (insn
) || NOTE_P (insn
))
3266 && !can_throw_internal (insn
)
3267 && insn
!= BB_HEAD (bb
))
3268 insn
= PREV_INSN (insn
);
3270 if (CALL_P (insn
) || can_throw_internal (insn
))
3274 e
= find_fallthru_edge (bb
->succs
);
3276 stop
= NEXT_INSN (BB_END (bb
));
3279 for (insn
= NEXT_INSN (insn
); insn
!= stop
; insn
= next
)
3281 next
= NEXT_INSN (insn
);
3286 /* Sometimes there's still the return value USE.
3287 If it's placed after a trapping call (i.e. that
3288 call is the last insn anyway), we have no fallthru
3289 edge. Simply delete this use and don't try to insert
3290 on the non-existent edge. */
3291 if (GET_CODE (PATTERN (insn
)) != USE
)
3293 /* We're not deleting it, we're moving it. */
3294 INSN_DELETED_P (insn
) = 0;
3295 PREV_INSN (insn
) = NULL_RTX
;
3296 NEXT_INSN (insn
) = NULL_RTX
;
3298 insert_insn_on_edge (insn
, e
);
3302 else if (!BARRIER_P (insn
))
3303 set_block_for_insn (insn
, NULL
);
3307 /* It may be that we don't find any trapping insn. In this
3308 case we discovered quite late that the insn that had been
3309 marked as can_throw_internal in fact couldn't trap at all.
3310 So we should in fact delete the EH edges out of the block. */
3312 purge_dead_edges (bb
);
3319 /* Cut the insns from FIRST to LAST out of the insns stream. */
3322 unlink_insn_chain (rtx first
, rtx last
)
3324 rtx prevfirst
= PREV_INSN (first
);
3325 rtx nextlast
= NEXT_INSN (last
);
3327 PREV_INSN (first
) = NULL
;
3328 NEXT_INSN (last
) = NULL
;
3330 NEXT_INSN (prevfirst
) = nextlast
;
3332 PREV_INSN (nextlast
) = prevfirst
;
3334 set_last_insn (prevfirst
);
3336 set_first_insn (nextlast
);
3340 /* Skip over inter-block insns occurring after BB which are typically
3341 associated with BB (e.g., barriers). If there are any such insns,
3342 we return the last one. Otherwise, we return the end of BB. */
3345 skip_insns_after_block (basic_block bb
)
3347 rtx insn
, last_insn
, next_head
, prev
;
3349 next_head
= NULL_RTX
;
3350 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3351 next_head
= BB_HEAD (bb
->next_bb
);
3353 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
3355 if (insn
== next_head
)
3358 switch (GET_CODE (insn
))
3365 switch (NOTE_KIND (insn
))
3367 case NOTE_INSN_BLOCK_END
:
3377 if (NEXT_INSN (insn
)
3378 && JUMP_TABLE_DATA_P (NEXT_INSN (insn
)))
3380 insn
= NEXT_INSN (insn
);
3393 /* It is possible to hit contradictory sequence. For instance:
3399 Where barrier belongs to jump_insn, but the note does not. This can be
3400 created by removing the basic block originally following
3401 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3403 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
3405 prev
= PREV_INSN (insn
);
3407 switch (NOTE_KIND (insn
))
3409 case NOTE_INSN_BLOCK_END
:
3412 case NOTE_INSN_DELETED
:
3413 case NOTE_INSN_DELETED_LABEL
:
3414 case NOTE_INSN_DELETED_DEBUG_LABEL
:
3417 reorder_insns (insn
, insn
, last_insn
);
3424 /* Locate or create a label for a given basic block. */
3427 label_for_bb (basic_block bb
)
3429 rtx label
= BB_HEAD (bb
);
3431 if (!LABEL_P (label
))
3434 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
3436 label
= block_label (bb
);
3442 /* Locate the effective beginning and end of the insn chain for each
3443 block, as defined by skip_insns_after_block above. */
3446 record_effective_endpoints (void)
3452 for (insn
= get_insns ();
3455 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
;
3456 insn
= NEXT_INSN (insn
))
3458 /* No basic blocks at all? */
3461 if (PREV_INSN (insn
))
3462 cfg_layout_function_header
=
3463 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
3465 cfg_layout_function_header
= NULL_RTX
;
3467 next_insn
= get_insns ();
3468 FOR_EACH_BB_FN (bb
, cfun
)
3472 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
3473 BB_HEADER (bb
) = unlink_insn_chain (next_insn
,
3474 PREV_INSN (BB_HEAD (bb
)));
3475 end
= skip_insns_after_block (bb
);
3476 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
3477 BB_FOOTER (bb
) = unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
3478 next_insn
= NEXT_INSN (BB_END (bb
));
3481 cfg_layout_function_footer
= next_insn
;
3482 if (cfg_layout_function_footer
)
3483 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
3487 into_cfg_layout_mode (void)
3489 cfg_layout_initialize (0);
3494 outof_cfg_layout_mode (void)
3498 FOR_EACH_BB_FN (bb
, cfun
)
3499 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3500 bb
->aux
= bb
->next_bb
;
3502 cfg_layout_finalize ();
3509 const pass_data pass_data_into_cfg_layout_mode
=
3511 RTL_PASS
, /* type */
3512 "into_cfglayout", /* name */
3513 OPTGROUP_NONE
, /* optinfo_flags */
3514 false, /* has_gate */
3515 true, /* has_execute */
3517 0, /* properties_required */
3518 PROP_cfglayout
, /* properties_provided */
3519 0, /* properties_destroyed */
3520 0, /* todo_flags_start */
3521 0, /* todo_flags_finish */
3524 class pass_into_cfg_layout_mode
: public rtl_opt_pass
3527 pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3528 : rtl_opt_pass (pass_data_into_cfg_layout_mode
, ctxt
)
3531 /* opt_pass methods: */
3532 unsigned int execute () { return into_cfg_layout_mode (); }
3534 }; // class pass_into_cfg_layout_mode
3539 make_pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3541 return new pass_into_cfg_layout_mode (ctxt
);
3546 const pass_data pass_data_outof_cfg_layout_mode
=
3548 RTL_PASS
, /* type */
3549 "outof_cfglayout", /* name */
3550 OPTGROUP_NONE
, /* optinfo_flags */
3551 false, /* has_gate */
3552 true, /* has_execute */
3554 0, /* properties_required */
3555 0, /* properties_provided */
3556 PROP_cfglayout
, /* properties_destroyed */
3557 0, /* todo_flags_start */
3558 0, /* todo_flags_finish */
3561 class pass_outof_cfg_layout_mode
: public rtl_opt_pass
3564 pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3565 : rtl_opt_pass (pass_data_outof_cfg_layout_mode
, ctxt
)
3568 /* opt_pass methods: */
3569 unsigned int execute () { return outof_cfg_layout_mode (); }
3571 }; // class pass_outof_cfg_layout_mode
3576 make_pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3578 return new pass_outof_cfg_layout_mode (ctxt
);
3582 /* Link the basic blocks in the correct order, compacting the basic
3583 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3584 function also clears the basic block header and footer fields.
3586 This function is usually called after a pass (e.g. tracer) finishes
3587 some transformations while in cfglayout mode. The required sequence
3588 of the basic blocks is in a linked list along the bb->aux field.
3589 This functions re-links the basic block prev_bb and next_bb pointers
3590 accordingly, and it compacts and renumbers the blocks.
3592 FIXME: This currently works only for RTL, but the only RTL-specific
3593 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3594 to GIMPLE a long time ago, but it doesn't relink the basic block
3595 chain. It could do that (to give better initial RTL) if this function
3596 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3599 relink_block_chain (bool stay_in_cfglayout_mode
)
3601 basic_block bb
, prev_bb
;
3604 /* Maybe dump the re-ordered sequence. */
3607 fprintf (dump_file
, "Reordered sequence:\n");
3608 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, index
=
3611 bb
= (basic_block
) bb
->aux
, index
++)
3613 fprintf (dump_file
, " %i ", index
);
3614 if (get_bb_original (bb
))
3615 fprintf (dump_file
, "duplicate of %i ",
3616 get_bb_original (bb
)->index
);
3617 else if (forwarder_block_p (bb
)
3618 && !LABEL_P (BB_HEAD (bb
)))
3619 fprintf (dump_file
, "compensation ");
3621 fprintf (dump_file
, "bb %i ", bb
->index
);
3622 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
3626 /* Now reorder the blocks. */
3627 prev_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
3628 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
3629 for (; bb
; prev_bb
= bb
, bb
= (basic_block
) bb
->aux
)
3631 bb
->prev_bb
= prev_bb
;
3632 prev_bb
->next_bb
= bb
;
3634 prev_bb
->next_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
3635 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
= prev_bb
;
3637 /* Then, clean up the aux fields. */
3638 FOR_ALL_BB_FN (bb
, cfun
)
3641 if (!stay_in_cfglayout_mode
)
3642 BB_HEADER (bb
) = BB_FOOTER (bb
) = NULL
;
3645 /* Maybe reset the original copy tables, they are not valid anymore
3646 when we renumber the basic blocks in compact_blocks. If we are
3647 are going out of cfglayout mode, don't re-allocate the tables. */
3648 free_original_copy_tables ();
3649 if (stay_in_cfglayout_mode
)
3650 initialize_original_copy_tables ();
3652 /* Finally, put basic_block_info in the new order. */
3657 /* Given a reorder chain, rearrange the code to match. */
3660 fixup_reorder_chain (void)
3665 if (cfg_layout_function_header
)
3667 set_first_insn (cfg_layout_function_header
);
3668 insn
= cfg_layout_function_header
;
3669 while (NEXT_INSN (insn
))
3670 insn
= NEXT_INSN (insn
);
3673 /* First do the bulk reordering -- rechain the blocks without regard to
3674 the needed changes to jumps and labels. */
3676 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3682 NEXT_INSN (insn
) = BB_HEADER (bb
);
3684 set_first_insn (BB_HEADER (bb
));
3685 PREV_INSN (BB_HEADER (bb
)) = insn
;
3686 insn
= BB_HEADER (bb
);
3687 while (NEXT_INSN (insn
))
3688 insn
= NEXT_INSN (insn
);
3691 NEXT_INSN (insn
) = BB_HEAD (bb
);
3693 set_first_insn (BB_HEAD (bb
));
3694 PREV_INSN (BB_HEAD (bb
)) = insn
;
3698 NEXT_INSN (insn
) = BB_FOOTER (bb
);
3699 PREV_INSN (BB_FOOTER (bb
)) = insn
;
3700 while (NEXT_INSN (insn
))
3701 insn
= NEXT_INSN (insn
);
3705 NEXT_INSN (insn
) = cfg_layout_function_footer
;
3706 if (cfg_layout_function_footer
)
3707 PREV_INSN (cfg_layout_function_footer
) = insn
;
3709 while (NEXT_INSN (insn
))
3710 insn
= NEXT_INSN (insn
);
3712 set_last_insn (insn
);
3713 #ifdef ENABLE_CHECKING
3714 verify_insn_chain ();
3717 /* Now add jumps and labels as needed to match the blocks new
3720 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3723 edge e_fall
, e_taken
, e
;
3725 rtx ret_label
= NULL_RTX
;
3729 if (EDGE_COUNT (bb
->succs
) == 0)
3732 /* Find the old fallthru edge, and another non-EH edge for
3734 e_taken
= e_fall
= NULL
;
3736 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3737 if (e
->flags
& EDGE_FALLTHRU
)
3739 else if (! (e
->flags
& EDGE_EH
))
3742 bb_end_insn
= BB_END (bb
);
3743 if (JUMP_P (bb_end_insn
))
3745 ret_label
= JUMP_LABEL (bb_end_insn
);
3746 if (any_condjump_p (bb_end_insn
))
3748 /* This might happen if the conditional jump has side
3749 effects and could therefore not be optimized away.
3750 Make the basic block to end with a barrier in order
3751 to prevent rtl_verify_flow_info from complaining. */
3754 gcc_assert (!onlyjump_p (bb_end_insn
)
3755 || returnjump_p (bb_end_insn
)
3756 || (e_taken
->flags
& EDGE_CROSSING
));
3757 emit_barrier_after (bb_end_insn
);
3761 /* If the old fallthru is still next, nothing to do. */
3762 if (bb
->aux
== e_fall
->dest
3763 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3766 /* The degenerated case of conditional jump jumping to the next
3767 instruction can happen for jumps with side effects. We need
3768 to construct a forwarder block and this will be done just
3769 fine by force_nonfallthru below. */
3773 /* There is another special case: if *neither* block is next,
3774 such as happens at the very end of a function, then we'll
3775 need to add a new unconditional jump. Choose the taken
3776 edge based on known or assumed probability. */
3777 else if (bb
->aux
!= e_taken
->dest
)
3779 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
3782 && XINT (note
, 0) < REG_BR_PROB_BASE
/ 2
3783 && invert_jump (bb_end_insn
,
3785 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3787 : label_for_bb (e_fall
->dest
)), 0))
3789 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3790 gcc_checking_assert (could_fall_through
3791 (e_taken
->src
, e_taken
->dest
));
3792 e_taken
->flags
|= EDGE_FALLTHRU
;
3793 update_br_prob_note (bb
);
3794 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
3798 /* If the "jumping" edge is a crossing edge, and the fall
3799 through edge is non-crossing, leave things as they are. */
3800 else if ((e_taken
->flags
& EDGE_CROSSING
)
3801 && !(e_fall
->flags
& EDGE_CROSSING
))
3804 /* Otherwise we can try to invert the jump. This will
3805 basically never fail, however, keep up the pretense. */
3806 else if (invert_jump (bb_end_insn
,
3808 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3810 : label_for_bb (e_fall
->dest
)), 0))
3812 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3813 gcc_checking_assert (could_fall_through
3814 (e_taken
->src
, e_taken
->dest
));
3815 e_taken
->flags
|= EDGE_FALLTHRU
;
3816 update_br_prob_note (bb
);
3817 if (LABEL_NUSES (ret_label
) == 0
3818 && single_pred_p (e_taken
->dest
))
3819 delete_insn (ret_label
);
3823 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
3825 /* If the old fallthru is still next or if
3826 asm goto doesn't have a fallthru (e.g. when followed by
3827 __builtin_unreachable ()), nothing to do. */
3829 || bb
->aux
== e_fall
->dest
3830 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3833 /* Otherwise we'll have to use the fallthru fixup below. */
3837 /* Otherwise we have some return, switch or computed
3838 jump. In the 99% case, there should not have been a
3840 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
3846 /* No fallthru implies a noreturn function with EH edges, or
3847 something similarly bizarre. In any case, we don't need to
3852 /* If the fallthru block is still next, nothing to do. */
3853 if (bb
->aux
== e_fall
->dest
)
3856 /* A fallthru to exit block. */
3857 if (e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3861 /* We got here if we need to add a new jump insn.
3862 Note force_nonfallthru can delete E_FALL and thus we have to
3863 save E_FALL->src prior to the call to force_nonfallthru. */
3864 nb
= force_nonfallthru_and_redirect (e_fall
, e_fall
->dest
, ret_label
);
3869 /* Don't process this new block. */
3874 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3876 /* Annoying special case - jump around dead jumptables left in the code. */
3877 FOR_EACH_BB_FN (bb
, cfun
)
3879 edge e
= find_fallthru_edge (bb
->succs
);
3881 if (e
&& !can_fallthru (e
->src
, e
->dest
))
3882 force_nonfallthru (e
);
3885 /* Ensure goto_locus from edges has some instructions with that locus
3888 FOR_EACH_BB_FN (bb
, cfun
)
3893 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3894 if (LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
3895 && !(e
->flags
& EDGE_ABNORMAL
))
3899 basic_block dest
, nb
;
3902 insn
= BB_END (e
->src
);
3903 end
= PREV_INSN (BB_HEAD (e
->src
));
3905 && (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
3906 insn
= PREV_INSN (insn
);
3908 && INSN_LOCATION (insn
) == e
->goto_locus
)
3910 if (simplejump_p (BB_END (e
->src
))
3911 && !INSN_HAS_LOCATION (BB_END (e
->src
)))
3913 INSN_LOCATION (BB_END (e
->src
)) = e
->goto_locus
;
3917 if (dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3919 /* Non-fallthru edges to the exit block cannot be split. */
3920 if (!(e
->flags
& EDGE_FALLTHRU
))
3925 insn
= BB_HEAD (dest
);
3926 end
= NEXT_INSN (BB_END (dest
));
3927 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
3928 insn
= NEXT_INSN (insn
);
3929 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
3930 && INSN_LOCATION (insn
) == e
->goto_locus
)
3933 nb
= split_edge (e
);
3934 if (!INSN_P (BB_END (nb
)))
3935 BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
3937 INSN_LOCATION (BB_END (nb
)) = e
->goto_locus
;
3939 /* If there are other incoming edges to the destination block
3940 with the same goto locus, redirect them to the new block as
3941 well, this can prevent other such blocks from being created
3942 in subsequent iterations of the loop. */
3943 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
3944 if (LOCATION_LOCUS (e2
->goto_locus
) != UNKNOWN_LOCATION
3945 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
3946 && e
->goto_locus
== e2
->goto_locus
)
3947 redirect_edge_and_branch (e2
, nb
);
3954 /* Perform sanity checks on the insn chain.
3955 1. Check that next/prev pointers are consistent in both the forward and
3957 2. Count insns in chain, going both directions, and check if equal.
3958 3. Check that get_last_insn () returns the actual end of chain. */
3961 verify_insn_chain (void)
3963 rtx x
, prevx
, nextx
;
3964 int insn_cnt1
, insn_cnt2
;
3966 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
3968 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
3969 gcc_assert (PREV_INSN (x
) == prevx
);
3971 gcc_assert (prevx
== get_last_insn ());
3973 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
3975 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
3976 gcc_assert (NEXT_INSN (x
) == nextx
);
3978 gcc_assert (insn_cnt1
== insn_cnt2
);
3981 /* If we have assembler epilogues, the block falling through to exit must
3982 be the last one in the reordered chain when we reach final. Ensure
3983 that this condition is met. */
3985 fixup_fallthru_exit_predecessor (void)
3988 basic_block bb
= NULL
;
3990 /* This transformation is not valid before reload, because we might
3991 separate a call from the instruction that copies the return
3993 gcc_assert (reload_completed
);
3995 e
= find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4001 basic_block c
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
4003 /* If the very first block is the one with the fall-through exit
4004 edge, we have to split that block. */
4007 bb
= split_block (bb
, NULL
)->dest
;
4010 BB_FOOTER (bb
) = BB_FOOTER (c
);
4011 BB_FOOTER (c
) = NULL
;
4014 while (c
->aux
!= bb
)
4015 c
= (basic_block
) c
->aux
;
4019 c
= (basic_block
) c
->aux
;
4026 /* In case there are more than one fallthru predecessors of exit, force that
4027 there is only one. */
4030 force_one_exit_fallthru (void)
4032 edge e
, predecessor
= NULL
;
4035 basic_block forwarder
, bb
;
4037 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
4038 if (e
->flags
& EDGE_FALLTHRU
)
4040 if (predecessor
== NULL
)
4052 /* Exit has several fallthru predecessors. Create a forwarder block for
4054 forwarder
= split_edge (predecessor
);
4055 for (ei
= ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4056 (e
= ei_safe_edge (ei
)); )
4058 if (e
->src
== forwarder
4059 || !(e
->flags
& EDGE_FALLTHRU
))
4062 redirect_edge_and_branch_force (e
, forwarder
);
4065 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4067 FOR_EACH_BB_FN (bb
, cfun
)
4069 if (bb
->aux
== NULL
&& bb
!= forwarder
)
4071 bb
->aux
= forwarder
;
4077 /* Return true in case it is possible to duplicate the basic block BB. */
4080 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
4082 /* Do not attempt to duplicate tablejumps, as we need to unshare
4083 the dispatch table. This is difficult to do, as the instructions
4084 computing jump destination may be hoisted outside the basic block. */
4085 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
4088 /* Do not duplicate blocks containing insns that can't be copied. */
4089 if (targetm
.cannot_copy_insn_p
)
4091 rtx insn
= BB_HEAD (bb
);
4094 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
4096 if (insn
== BB_END (bb
))
4098 insn
= NEXT_INSN (insn
);
4106 duplicate_insn_chain (rtx from
, rtx to
)
4108 rtx insn
, next
, last
, copy
;
4110 /* Avoid updating of boundaries of previous basic block. The
4111 note will get removed from insn stream in fixup. */
4112 last
= emit_note (NOTE_INSN_DELETED
);
4114 /* Create copy at the end of INSN chain. The chain will
4115 be reordered later. */
4116 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
4118 switch (GET_CODE (insn
))
4121 /* Don't duplicate label debug insns. */
4122 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
)
4128 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
4129 if (JUMP_P (insn
) && JUMP_LABEL (insn
) != NULL_RTX
4130 && ANY_RETURN_P (JUMP_LABEL (insn
)))
4131 JUMP_LABEL (copy
) = JUMP_LABEL (insn
);
4132 maybe_copy_prologue_epilogue_insn (insn
, copy
);
4135 case JUMP_TABLE_DATA
:
4136 /* Avoid copying of dispatch tables. We never duplicate
4137 tablejumps, so this can hit only in case the table got
4138 moved far from original jump.
4139 Avoid copying following barrier as well if any
4140 (and debug insns in between). */
4141 for (next
= NEXT_INSN (insn
);
4142 next
!= NEXT_INSN (to
);
4143 next
= NEXT_INSN (next
))
4144 if (!DEBUG_INSN_P (next
))
4146 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
4158 switch (NOTE_KIND (insn
))
4160 /* In case prologue is empty and function contain label
4161 in first BB, we may want to copy the block. */
4162 case NOTE_INSN_PROLOGUE_END
:
4164 case NOTE_INSN_DELETED
:
4165 case NOTE_INSN_DELETED_LABEL
:
4166 case NOTE_INSN_DELETED_DEBUG_LABEL
:
4167 /* No problem to strip these. */
4168 case NOTE_INSN_FUNCTION_BEG
:
4169 /* There is always just single entry to function. */
4170 case NOTE_INSN_BASIC_BLOCK
:
4171 /* We should only switch text sections once. */
4172 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
4175 case NOTE_INSN_EPILOGUE_BEG
:
4176 emit_note_copy (insn
);
4180 /* All other notes should have already been eliminated. */
4188 insn
= NEXT_INSN (last
);
4193 /* Create a duplicate of the basic block BB. */
4196 cfg_layout_duplicate_bb (basic_block bb
)
4201 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
4202 new_bb
= create_basic_block (insn
,
4203 insn
? get_last_insn () : NULL
,
4204 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
);
4206 BB_COPY_PARTITION (new_bb
, bb
);
4209 insn
= BB_HEADER (bb
);
4210 while (NEXT_INSN (insn
))
4211 insn
= NEXT_INSN (insn
);
4212 insn
= duplicate_insn_chain (BB_HEADER (bb
), insn
);
4214 BB_HEADER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4219 insn
= BB_FOOTER (bb
);
4220 while (NEXT_INSN (insn
))
4221 insn
= NEXT_INSN (insn
);
4222 insn
= duplicate_insn_chain (BB_FOOTER (bb
), insn
);
4224 BB_FOOTER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4231 /* Main entry point to this module - initialize the datastructures for
4232 CFG layout changes. It keeps LOOPS up-to-date if not null.
4234 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4237 cfg_layout_initialize (unsigned int flags
)
4242 /* Once bb reordering is complete, cfg layout mode should not be re-entered.
4243 Entering cfg layout mode will perform optimizations on the cfg that
4244 could affect the bb layout negatively or even require fixups. An
4245 example of the latter is if edge forwarding performed when optimizing
4246 the cfg layout required moving a block from the hot to the cold section
4247 under -freorder-blocks-and-partition. This would create an illegal
4248 partitioning unless some manual fixup was performed. */
4249 gcc_assert (!crtl
->bb_reorder_complete
);
4251 initialize_original_copy_tables ();
4253 cfg_layout_rtl_register_cfg_hooks ();
4255 record_effective_endpoints ();
4257 /* Make sure that the targets of non local gotos are marked. */
4258 for (x
= nonlocal_goto_handler_labels
; x
; x
= XEXP (x
, 1))
4260 bb
= BLOCK_FOR_INSN (XEXP (x
, 0));
4261 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
4264 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
4267 /* Splits superblocks. */
4269 break_superblocks (void)
4271 sbitmap superblocks
;
4275 superblocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
4276 bitmap_clear (superblocks
);
4278 FOR_EACH_BB_FN (bb
, cfun
)
4279 if (bb
->flags
& BB_SUPERBLOCK
)
4281 bb
->flags
&= ~BB_SUPERBLOCK
;
4282 bitmap_set_bit (superblocks
, bb
->index
);
4288 rebuild_jump_labels (get_insns ());
4289 find_many_sub_basic_blocks (superblocks
);
4295 /* Finalize the changes: reorder insn list according to the sequence specified
4296 by aux pointers, enter compensation code, rebuild scope forest. */
4299 cfg_layout_finalize (void)
4301 #ifdef ENABLE_CHECKING
4302 verify_flow_info ();
4304 force_one_exit_fallthru ();
4305 rtl_register_cfg_hooks ();
4306 if (reload_completed
4307 #ifdef HAVE_epilogue
4311 fixup_fallthru_exit_predecessor ();
4312 fixup_reorder_chain ();
4314 rebuild_jump_labels (get_insns ());
4315 delete_dead_jumptables ();
4317 #ifdef ENABLE_CHECKING
4318 verify_insn_chain ();
4319 verify_flow_info ();
4324 /* Same as split_block but update cfg_layout structures. */
4327 cfg_layout_split_block (basic_block bb
, void *insnp
)
4329 rtx insn
= (rtx
) insnp
;
4330 basic_block new_bb
= rtl_split_block (bb
, insn
);
4332 BB_FOOTER (new_bb
) = BB_FOOTER (bb
);
4333 BB_FOOTER (bb
) = NULL
;
4338 /* Redirect Edge to DEST. */
4340 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
4342 basic_block src
= e
->src
;
4345 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4348 if (e
->dest
== dest
)
4351 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4352 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
4354 df_set_bb_dirty (src
);
4358 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4359 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
4362 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
4363 e
->src
->index
, dest
->index
);
4365 df_set_bb_dirty (e
->src
);
4366 redirect_edge_succ (e
, dest
);
4370 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4371 in the case the basic block appears to be in sequence. Avoid this
4374 if (e
->flags
& EDGE_FALLTHRU
)
4376 /* Redirect any branch edges unified with the fallthru one. */
4377 if (JUMP_P (BB_END (src
))
4378 && label_is_jump_target_p (BB_HEAD (e
->dest
),
4384 fprintf (dump_file
, "Fallthru edge unified with branch "
4385 "%i->%i redirected to %i\n",
4386 e
->src
->index
, e
->dest
->index
, dest
->index
);
4387 e
->flags
&= ~EDGE_FALLTHRU
;
4388 redirected
= redirect_branch_edge (e
, dest
);
4389 gcc_assert (redirected
);
4390 redirected
->flags
|= EDGE_FALLTHRU
;
4391 df_set_bb_dirty (redirected
->src
);
4394 /* In case we are redirecting fallthru edge to the branch edge
4395 of conditional jump, remove it. */
4396 if (EDGE_COUNT (src
->succs
) == 2)
4398 /* Find the edge that is different from E. */
4399 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
4402 && any_condjump_p (BB_END (src
))
4403 && onlyjump_p (BB_END (src
)))
4404 delete_insn (BB_END (src
));
4407 fprintf (dump_file
, "Redirecting fallthru edge %i->%i to %i\n",
4408 e
->src
->index
, e
->dest
->index
, dest
->index
);
4409 ret
= redirect_edge_succ_nodup (e
, dest
);
4412 ret
= redirect_branch_edge (e
, dest
);
4414 /* We don't want simplejumps in the insn stream during cfglayout. */
4415 gcc_assert (!simplejump_p (BB_END (src
)));
4417 df_set_bb_dirty (src
);
4421 /* Simple wrapper as we always can redirect fallthru edges. */
4423 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
4425 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
4427 gcc_assert (redirected
);
4431 /* Same as delete_basic_block but update cfg_layout structures. */
4434 cfg_layout_delete_block (basic_block bb
)
4436 rtx insn
, next
, prev
= PREV_INSN (BB_HEAD (bb
)), *to
, remaints
;
4440 next
= BB_HEAD (bb
);
4442 NEXT_INSN (prev
) = BB_HEADER (bb
);
4444 set_first_insn (BB_HEADER (bb
));
4445 PREV_INSN (BB_HEADER (bb
)) = prev
;
4446 insn
= BB_HEADER (bb
);
4447 while (NEXT_INSN (insn
))
4448 insn
= NEXT_INSN (insn
);
4449 NEXT_INSN (insn
) = next
;
4450 PREV_INSN (next
) = insn
;
4452 next
= NEXT_INSN (BB_END (bb
));
4455 insn
= BB_FOOTER (bb
);
4458 if (BARRIER_P (insn
))
4460 if (PREV_INSN (insn
))
4461 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
4463 BB_FOOTER (bb
) = NEXT_INSN (insn
);
4464 if (NEXT_INSN (insn
))
4465 PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
4469 insn
= NEXT_INSN (insn
);
4474 NEXT_INSN (insn
) = BB_FOOTER (bb
);
4475 PREV_INSN (BB_FOOTER (bb
)) = insn
;
4476 while (NEXT_INSN (insn
))
4477 insn
= NEXT_INSN (insn
);
4478 NEXT_INSN (insn
) = next
;
4480 PREV_INSN (next
) = insn
;
4482 set_last_insn (insn
);
4485 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
4486 to
= &BB_HEADER (bb
->next_bb
);
4488 to
= &cfg_layout_function_footer
;
4490 rtl_delete_block (bb
);
4493 prev
= NEXT_INSN (prev
);
4495 prev
= get_insns ();
4497 next
= PREV_INSN (next
);
4499 next
= get_last_insn ();
4501 if (next
&& NEXT_INSN (next
) != prev
)
4503 remaints
= unlink_insn_chain (prev
, next
);
4505 while (NEXT_INSN (insn
))
4506 insn
= NEXT_INSN (insn
);
4507 NEXT_INSN (insn
) = *to
;
4509 PREV_INSN (*to
) = insn
;
4514 /* Return true when blocks A and B can be safely merged. */
4517 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
4519 /* If we are partitioning hot/cold basic blocks, we don't want to
4520 mess up unconditional or indirect jumps that cross between hot
4523 Basic block partitioning may result in some jumps that appear to
4524 be optimizable (or blocks that appear to be mergeable), but which really
4525 must be left untouched (they are required to make it safely across
4526 partition boundaries). See the comments at the top of
4527 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4529 if (BB_PARTITION (a
) != BB_PARTITION (b
))
4532 /* Protect the loop latches. */
4533 if (current_loops
&& b
->loop_father
->latch
== b
)
4536 /* If we would end up moving B's instructions, make sure it doesn't fall
4537 through into the exit block, since we cannot recover from a fallthrough
4538 edge into the exit block occurring in the middle of a function. */
4539 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4541 edge e
= find_fallthru_edge (b
->succs
);
4542 if (e
&& e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4546 /* There must be exactly one edge in between the blocks. */
4547 return (single_succ_p (a
)
4548 && single_succ (a
) == b
4549 && single_pred_p (b
) == 1
4551 /* Must be simple edge. */
4552 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
4553 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4554 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
4555 /* If the jump insn has side effects, we can't kill the edge.
4556 When not optimizing, try_redirect_by_replacing_jump will
4557 not allow us to redirect an edge by replacing a table jump. */
4558 && (!JUMP_P (BB_END (a
))
4559 || ((!optimize
|| reload_completed
)
4560 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
4563 /* Merge block A and B. The blocks must be mergeable. */
4566 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
4568 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
4571 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a
, b
));
4574 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
4577 /* If there was a CODE_LABEL beginning B, delete it. */
4578 if (LABEL_P (BB_HEAD (b
)))
4580 delete_insn (BB_HEAD (b
));
4583 /* We should have fallthru edge in a, or we can do dummy redirection to get
4585 if (JUMP_P (BB_END (a
)))
4586 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
4587 gcc_assert (!JUMP_P (BB_END (a
)));
4589 /* When not optimizing CFG and the edge is the only place in RTL which holds
4590 some unique locus, emit a nop with that locus in between. */
4592 emit_nop_for_unique_locus_between (a
, b
);
4594 /* Move things from b->footer after a->footer. */
4598 BB_FOOTER (a
) = BB_FOOTER (b
);
4601 rtx last
= BB_FOOTER (a
);
4603 while (NEXT_INSN (last
))
4604 last
= NEXT_INSN (last
);
4605 NEXT_INSN (last
) = BB_FOOTER (b
);
4606 PREV_INSN (BB_FOOTER (b
)) = last
;
4608 BB_FOOTER (b
) = NULL
;
4611 /* Move things from b->header before a->footer.
4612 Note that this may include dead tablejump data, but we don't clean
4613 those up until we go out of cfglayout mode. */
4616 if (! BB_FOOTER (a
))
4617 BB_FOOTER (a
) = BB_HEADER (b
);
4620 rtx last
= BB_HEADER (b
);
4622 while (NEXT_INSN (last
))
4623 last
= NEXT_INSN (last
);
4624 NEXT_INSN (last
) = BB_FOOTER (a
);
4625 PREV_INSN (BB_FOOTER (a
)) = last
;
4626 BB_FOOTER (a
) = BB_HEADER (b
);
4628 BB_HEADER (b
) = NULL
;
4631 /* In the case basic blocks are not adjacent, move them around. */
4632 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4634 insn
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
4636 emit_insn_after_noloc (insn
, BB_END (a
), a
);
4638 /* Otherwise just re-associate the instructions. */
4642 BB_END (a
) = BB_END (b
);
4645 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4646 We need to explicitly call. */
4647 update_bb_for_insn_chain (insn
, BB_END (b
), a
);
4649 /* Skip possible DELETED_LABEL insn. */
4650 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
4651 insn
= NEXT_INSN (insn
);
4652 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4653 BB_HEAD (b
) = BB_END (b
) = NULL
;
4656 df_bb_delete (b
->index
);
4658 /* If B was a forwarder block, propagate the locus on the edge. */
4660 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
4661 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
4664 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
4670 cfg_layout_split_edge (edge e
)
4672 basic_block new_bb
=
4673 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4674 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
4677 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4678 BB_COPY_PARTITION (new_bb
, e
->src
);
4680 BB_COPY_PARTITION (new_bb
, e
->dest
);
4681 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
4682 redirect_edge_and_branch_force (e
, new_bb
);
4687 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4690 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
4694 /* Return true if BB contains only labels or non-executable
4698 rtl_block_empty_p (basic_block bb
)
4702 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4703 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4706 FOR_BB_INSNS (bb
, insn
)
4707 if (NONDEBUG_INSN_P (insn
) && !any_uncondjump_p (insn
))
4713 /* Split a basic block if it ends with a conditional branch and if
4714 the other part of the block is not empty. */
4717 rtl_split_block_before_cond_jump (basic_block bb
)
4720 rtx split_point
= NULL
;
4722 bool found_code
= false;
4724 FOR_BB_INSNS (bb
, insn
)
4726 if (any_condjump_p (insn
))
4728 else if (NONDEBUG_INSN_P (insn
))
4733 /* Did not find everything. */
4734 if (found_code
&& split_point
)
4735 return split_block (bb
, split_point
)->dest
;
4740 /* Return 1 if BB ends with a call, possibly followed by some
4741 instructions that must stay with the call, 0 otherwise. */
4744 rtl_block_ends_with_call_p (basic_block bb
)
4746 rtx insn
= BB_END (bb
);
4748 while (!CALL_P (insn
)
4749 && insn
!= BB_HEAD (bb
)
4750 && (keep_with_call_p (insn
)
4752 || DEBUG_INSN_P (insn
)))
4753 insn
= PREV_INSN (insn
);
4754 return (CALL_P (insn
));
4757 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4760 rtl_block_ends_with_condjump_p (const_basic_block bb
)
4762 return any_condjump_p (BB_END (bb
));
4765 /* Return true if we need to add fake edge to exit.
4766 Helper function for rtl_flow_call_edges_add. */
4769 need_fake_edge_p (const_rtx insn
)
4775 && !SIBLING_CALL_P (insn
)
4776 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
4777 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
4780 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
4781 && MEM_VOLATILE_P (PATTERN (insn
)))
4782 || (GET_CODE (PATTERN (insn
)) == PARALLEL
4783 && asm_noperands (insn
) != -1
4784 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
4785 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
4788 /* Add fake edges to the function exit for any non constant and non noreturn
4789 calls, volatile inline assembly in the bitmap of blocks specified by
4790 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4793 The goal is to expose cases in which entering a basic block does not imply
4794 that all subsequent instructions must be executed. */
4797 rtl_flow_call_edges_add (sbitmap blocks
)
4800 int blocks_split
= 0;
4801 int last_bb
= last_basic_block_for_fn (cfun
);
4802 bool check_last_block
= false;
4804 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
4808 check_last_block
= true;
4810 check_last_block
= bitmap_bit_p (blocks
,
4811 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
->index
);
4813 /* In the last basic block, before epilogue generation, there will be
4814 a fallthru edge to EXIT. Special care is required if the last insn
4815 of the last basic block is a call because make_edge folds duplicate
4816 edges, which would result in the fallthru edge also being marked
4817 fake, which would result in the fallthru edge being removed by
4818 remove_fake_edges, which would result in an invalid CFG.
4820 Moreover, we can't elide the outgoing fake edge, since the block
4821 profiler needs to take this into account in order to solve the minimal
4822 spanning tree in the case that the call doesn't return.
4824 Handle this by adding a dummy instruction in a new last basic block. */
4825 if (check_last_block
)
4827 basic_block bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
4828 rtx insn
= BB_END (bb
);
4830 /* Back up past insns that must be kept in the same block as a call. */
4831 while (insn
!= BB_HEAD (bb
)
4832 && keep_with_call_p (insn
))
4833 insn
= PREV_INSN (insn
);
4835 if (need_fake_edge_p (insn
))
4839 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4842 insert_insn_on_edge (gen_use (const0_rtx
), e
);
4843 commit_edge_insertions ();
4848 /* Now add fake edges to the function exit for any non constant
4849 calls since there is no way that we can determine if they will
4852 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
4854 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
4861 if (blocks
&& !bitmap_bit_p (blocks
, i
))
4864 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
4866 prev_insn
= PREV_INSN (insn
);
4867 if (need_fake_edge_p (insn
))
4870 rtx split_at_insn
= insn
;
4872 /* Don't split the block between a call and an insn that should
4873 remain in the same block as the call. */
4875 while (split_at_insn
!= BB_END (bb
)
4876 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
4877 split_at_insn
= NEXT_INSN (split_at_insn
);
4879 /* The handling above of the final block before the epilogue
4880 should be enough to verify that there is no edge to the exit
4881 block in CFG already. Calling make_edge in such case would
4882 cause us to mark that edge as fake and remove it later. */
4884 #ifdef ENABLE_CHECKING
4885 if (split_at_insn
== BB_END (bb
))
4887 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4888 gcc_assert (e
== NULL
);
4892 /* Note that the following may create a new basic block
4893 and renumber the existing basic blocks. */
4894 if (split_at_insn
!= BB_END (bb
))
4896 e
= split_block (bb
, split_at_insn
);
4901 make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
4904 if (insn
== BB_HEAD (bb
))
4910 verify_flow_info ();
4912 return blocks_split
;
4915 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4916 the conditional branch target, SECOND_HEAD should be the fall-thru
4917 there is no need to handle this here the loop versioning code handles
4918 this. the reason for SECON_HEAD is that it is needed for condition
4919 in trees, and this should be of the same type since it is a hook. */
4921 rtl_lv_add_condition_to_bb (basic_block first_head
,
4922 basic_block second_head ATTRIBUTE_UNUSED
,
4923 basic_block cond_bb
, void *comp_rtx
)
4925 rtx label
, seq
, jump
;
4926 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
4927 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
4928 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
4929 enum machine_mode mode
;
4932 label
= block_label (first_head
);
4933 mode
= GET_MODE (op0
);
4934 if (mode
== VOIDmode
)
4935 mode
= GET_MODE (op1
);
4938 op0
= force_operand (op0
, NULL_RTX
);
4939 op1
= force_operand (op1
, NULL_RTX
);
4940 do_compare_rtx_and_jump (op0
, op1
, comp
, 0,
4941 mode
, NULL_RTX
, NULL_RTX
, label
, -1);
4942 jump
= get_last_insn ();
4943 JUMP_LABEL (jump
) = label
;
4944 LABEL_NUSES (label
)++;
4948 /* Add the new cond , in the new head. */
4949 emit_insn_after (seq
, BB_END (cond_bb
));
4953 /* Given a block B with unconditional branch at its end, get the
4954 store the return the branch edge and the fall-thru edge in
4955 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4957 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
4958 edge
*fallthru_edge
)
4960 edge e
= EDGE_SUCC (b
, 0);
4962 if (e
->flags
& EDGE_FALLTHRU
)
4965 *branch_edge
= EDGE_SUCC (b
, 1);
4970 *fallthru_edge
= EDGE_SUCC (b
, 1);
4975 init_rtl_bb_info (basic_block bb
)
4977 gcc_assert (!bb
->il
.x
.rtl
);
4978 bb
->il
.x
.head_
= NULL
;
4979 bb
->il
.x
.rtl
= ggc_alloc_cleared_rtl_bb_info ();
4982 /* Returns true if it is possible to remove edge E by redirecting
4983 it to the destination of the other edge from E->src. */
4986 rtl_can_remove_branch_p (const_edge e
)
4988 const_basic_block src
= e
->src
;
4989 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
4990 const_rtx insn
= BB_END (src
), set
;
4992 /* The conditions are taken from try_redirect_by_replacing_jump. */
4993 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4996 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4999 if (BB_PARTITION (src
) != BB_PARTITION (target
))
5002 if (!onlyjump_p (insn
)
5003 || tablejump_p (insn
, NULL
, NULL
))
5006 set
= single_set (insn
);
5007 if (!set
|| side_effects_p (set
))
5014 rtl_duplicate_bb (basic_block bb
)
5016 bb
= cfg_layout_duplicate_bb (bb
);
5021 /* Do book-keeping of basic block BB for the profile consistency checker.
5022 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
5023 then do post-pass accounting. Store the counting in RECORD. */
5025 rtl_account_profile_record (basic_block bb
, int after_pass
,
5026 struct profile_record
*record
)
5029 FOR_BB_INSNS (bb
, insn
)
5032 record
->size
[after_pass
]
5033 += insn_rtx_cost (PATTERN (insn
), false);
5034 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
5035 record
->time
[after_pass
]
5036 += insn_rtx_cost (PATTERN (insn
), true) * bb
->count
;
5037 else if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
5038 record
->time
[after_pass
]
5039 += insn_rtx_cost (PATTERN (insn
), true) * bb
->frequency
;
5043 /* Implementation of CFG manipulation for linearized RTL. */
5044 struct cfg_hooks rtl_cfg_hooks
= {
5046 rtl_verify_flow_info
,
5048 rtl_dump_bb_for_graph
,
5049 rtl_create_basic_block
,
5050 rtl_redirect_edge_and_branch
,
5051 rtl_redirect_edge_and_branch_force
,
5052 rtl_can_remove_branch_p
,
5055 rtl_move_block_after
,
5056 rtl_can_merge_blocks
, /* can_merge_blocks_p */
5060 cfg_layout_can_duplicate_bb_p
,
5063 rtl_make_forwarder_block
,
5064 rtl_tidy_fallthru_edge
,
5065 rtl_force_nonfallthru
,
5066 rtl_block_ends_with_call_p
,
5067 rtl_block_ends_with_condjump_p
,
5068 rtl_flow_call_edges_add
,
5069 NULL
, /* execute_on_growing_pred */
5070 NULL
, /* execute_on_shrinking_pred */
5071 NULL
, /* duplicate loop for trees */
5072 NULL
, /* lv_add_condition_to_bb */
5073 NULL
, /* lv_adjust_loop_header_phi*/
5074 NULL
, /* extract_cond_bb_edges */
5075 NULL
, /* flush_pending_stmts */
5076 rtl_block_empty_p
, /* block_empty_p */
5077 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5078 rtl_account_profile_record
,
5081 /* Implementation of CFG manipulation for cfg layout RTL, where
5082 basic block connected via fallthru edges does not have to be adjacent.
5083 This representation will hopefully become the default one in future
5084 version of the compiler. */
5086 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
5088 rtl_verify_flow_info_1
,
5090 rtl_dump_bb_for_graph
,
5091 cfg_layout_create_basic_block
,
5092 cfg_layout_redirect_edge_and_branch
,
5093 cfg_layout_redirect_edge_and_branch_force
,
5094 rtl_can_remove_branch_p
,
5095 cfg_layout_delete_block
,
5096 cfg_layout_split_block
,
5097 rtl_move_block_after
,
5098 cfg_layout_can_merge_blocks_p
,
5099 cfg_layout_merge_blocks
,
5102 cfg_layout_can_duplicate_bb_p
,
5103 cfg_layout_duplicate_bb
,
5104 cfg_layout_split_edge
,
5105 rtl_make_forwarder_block
,
5106 NULL
, /* tidy_fallthru_edge */
5107 rtl_force_nonfallthru
,
5108 rtl_block_ends_with_call_p
,
5109 rtl_block_ends_with_condjump_p
,
5110 rtl_flow_call_edges_add
,
5111 NULL
, /* execute_on_growing_pred */
5112 NULL
, /* execute_on_shrinking_pred */
5113 duplicate_loop_to_header_edge
, /* duplicate loop for trees */
5114 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
5115 NULL
, /* lv_adjust_loop_header_phi*/
5116 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
5117 NULL
, /* flush_pending_stmts */
5118 rtl_block_empty_p
, /* block_empty_p */
5119 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5120 rtl_account_profile_record
,
5123 #include "gt-cfgrtl.h"