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 SET_BB_HEAD (bb
) = bb_note
;
156 if (BB_END (bb
) == bb_note
)
157 SET_BB_END (bb
) = insn
;
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_note
*bb_note
,
281 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
284 /* If we found an existing note, thread it back onto the chain. */
292 after
= PREV_INSN (head
);
296 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
297 reorder_insns_nobb (bb_note
, bb_note
, after
);
301 /* Otherwise we must create a note and a basic block structure. */
305 init_rtl_bb_info (bb
);
308 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
309 else if (LABEL_P (head
) && end
)
311 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
317 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
323 NOTE_BASIC_BLOCK (bb_note
) = bb
;
326 /* Always include the bb note in the block. */
327 if (NEXT_INSN (end
) == bb_note
)
330 SET_BB_HEAD (bb
) = head
;
331 SET_BB_END (bb
) = end
;
332 bb
->index
= last_basic_block_for_fn (cfun
)++;
333 bb
->flags
= BB_NEW
| BB_RTL
;
334 link_block (bb
, after
);
335 SET_BASIC_BLOCK_FOR_FN (cfun
, bb
->index
, bb
);
336 df_bb_refs_record (bb
->index
, false);
337 update_bb_for_insn (bb
);
338 BB_SET_PARTITION (bb
, BB_UNPARTITIONED
);
340 /* Tag the block so that we know it has been used when considering
341 other basic block notes. */
347 /* Create new basic block consisting of instructions in between HEAD and END
348 and place it to the BB chain after block AFTER. END can be NULL to
349 create a new empty basic block before HEAD. Both END and HEAD can be
350 NULL to create basic block at the end of INSN chain. */
353 rtl_create_basic_block (void *headp
, void *endp
, basic_block after
)
355 rtx head
= (rtx
) headp
, end
= (rtx
) endp
;
358 /* Grow the basic block array if needed. */
359 if ((size_t) last_basic_block_for_fn (cfun
)
360 >= basic_block_info_for_fn (cfun
)->length ())
363 (last_basic_block_for_fn (cfun
)
364 + (last_basic_block_for_fn (cfun
) + 3) / 4);
365 vec_safe_grow_cleared (basic_block_info_for_fn (cfun
), new_size
);
368 n_basic_blocks_for_fn (cfun
)++;
370 bb
= create_basic_block_structure (head
, end
, NULL
, after
);
376 cfg_layout_create_basic_block (void *head
, void *end
, basic_block after
)
378 basic_block newbb
= rtl_create_basic_block (head
, end
, after
);
383 /* Delete the insns in a (non-live) block. We physically delete every
384 non-deleted-note insn, and update the flow graph appropriately.
386 Return nonzero if we deleted an exception handler. */
388 /* ??? Preserving all such notes strikes me as wrong. It would be nice
389 to post-process the stream to remove empty blocks, loops, ranges, etc. */
392 rtl_delete_block (basic_block b
)
396 /* If the head of this block is a CODE_LABEL, then it might be the
397 label for an exception handler which can't be reached. We need
398 to remove the label from the exception_handler_label list. */
401 end
= get_last_bb_insn (b
);
403 /* Selectively delete the entire chain. */
404 SET_BB_HEAD (b
) = NULL
;
405 delete_insn_chain (insn
, end
, true);
409 fprintf (dump_file
, "deleting block %d\n", b
->index
);
410 df_bb_delete (b
->index
);
413 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
416 compute_bb_for_insn (void)
420 FOR_EACH_BB_FN (bb
, cfun
)
422 rtx end
= BB_END (bb
);
425 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
427 BLOCK_FOR_INSN (insn
) = bb
;
434 /* Release the basic_block_for_insn array. */
437 free_bb_for_insn (void)
440 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
441 if (!BARRIER_P (insn
))
442 BLOCK_FOR_INSN (insn
) = NULL
;
448 const pass_data pass_data_free_cfg
=
451 "*free_cfg", /* name */
452 OPTGROUP_NONE
, /* optinfo_flags */
454 0, /* properties_required */
455 0, /* properties_provided */
456 PROP_cfg
, /* properties_destroyed */
457 0, /* todo_flags_start */
458 0, /* todo_flags_finish */
461 class pass_free_cfg
: public rtl_opt_pass
464 pass_free_cfg (gcc::context
*ctxt
)
465 : rtl_opt_pass (pass_data_free_cfg
, ctxt
)
468 /* opt_pass methods: */
469 virtual unsigned int execute (function
*);
471 }; // class pass_free_cfg
474 pass_free_cfg::execute (function
*)
477 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
478 valid at that point so it would be too late to call df_analyze. */
479 if (optimize
> 0 && flag_delayed_branch
)
481 df_note_add_problem ();
486 if (crtl
->has_bb_partition
)
487 insert_section_boundary_note ();
496 make_pass_free_cfg (gcc::context
*ctxt
)
498 return new pass_free_cfg (ctxt
);
501 /* Return RTX to emit after when we want to emit code on the entry of function. */
503 entry_of_function (void)
505 return (n_basic_blocks_for_fn (cfun
) > NUM_FIXED_BLOCKS
?
506 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
) : get_insns ());
509 /* Emit INSN at the entry point of the function, ensuring that it is only
510 executed once per function. */
512 emit_insn_at_entry (rtx insn
)
514 edge_iterator ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
515 edge e
= ei_safe_edge (ei
);
516 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
518 insert_insn_on_edge (insn
, e
);
519 commit_edge_insertions ();
522 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
523 (or BARRIER if found) and notify df of the bb change.
524 The insn chain range is inclusive
525 (i.e. both BEGIN and END will be updated. */
528 update_bb_for_insn_chain (rtx begin
, rtx end
, basic_block bb
)
532 end
= NEXT_INSN (end
);
533 for (insn
= begin
; insn
!= end
; insn
= NEXT_INSN (insn
))
534 if (!BARRIER_P (insn
))
535 df_insn_change_bb (insn
, bb
);
538 /* Update BLOCK_FOR_INSN of insns in BB to BB,
539 and notify df of the change. */
542 update_bb_for_insn (basic_block bb
)
544 update_bb_for_insn_chain (BB_HEAD (bb
), BB_END (bb
), bb
);
548 /* Like active_insn_p, except keep the return value clobber around
549 even after reload. */
552 flow_active_insn_p (const_rtx insn
)
554 if (active_insn_p (insn
))
557 /* A clobber of the function return value exists for buggy
558 programs that fail to return a value. Its effect is to
559 keep the return value from being live across the entire
560 function. If we allow it to be skipped, we introduce the
561 possibility for register lifetime confusion. */
562 if (GET_CODE (PATTERN (insn
)) == CLOBBER
563 && REG_P (XEXP (PATTERN (insn
), 0))
564 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn
), 0)))
570 /* Return true if the block has no effect and only forwards control flow to
571 its single destination. */
574 contains_no_active_insn_p (const_basic_block bb
)
578 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
579 || !single_succ_p (bb
))
582 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
583 if (INSN_P (insn
) && flow_active_insn_p (insn
))
586 return (!INSN_P (insn
)
587 || (JUMP_P (insn
) && simplejump_p (insn
))
588 || !flow_active_insn_p (insn
));
591 /* Likewise, but protect loop latches, headers and preheaders. */
592 /* FIXME: Make this a cfg hook. */
595 forwarder_block_p (const_basic_block bb
)
597 if (!contains_no_active_insn_p (bb
))
600 /* Protect loop latches, headers and preheaders. */
604 if (bb
->loop_father
->header
== bb
)
606 dest
= EDGE_SUCC (bb
, 0)->dest
;
607 if (dest
->loop_father
->header
== dest
)
614 /* Return nonzero if we can reach target from src by falling through. */
615 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
618 can_fallthru (basic_block src
, basic_block target
)
620 rtx insn
= BB_END (src
);
625 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
627 if (src
->next_bb
!= target
)
630 /* ??? Later we may add code to move jump tables offline. */
631 if (tablejump_p (insn
, NULL
, NULL
))
634 FOR_EACH_EDGE (e
, ei
, src
->succs
)
635 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
636 && e
->flags
& EDGE_FALLTHRU
)
639 insn2
= BB_HEAD (target
);
640 if (!active_insn_p (insn2
))
641 insn2
= next_active_insn (insn2
);
643 return next_active_insn (insn
) == insn2
;
646 /* Return nonzero if we could reach target from src by falling through,
647 if the target was made adjacent. If we already have a fall-through
648 edge to the exit block, we can't do that. */
650 could_fall_through (basic_block src
, basic_block target
)
655 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
657 FOR_EACH_EDGE (e
, ei
, src
->succs
)
658 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
659 && e
->flags
& EDGE_FALLTHRU
)
664 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
666 bb_note (basic_block bb
)
672 note
= NEXT_INSN (note
);
674 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
675 return as_a
<rtx_note
*> (note
);
678 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
679 note associated with the BLOCK. */
682 first_insn_after_basic_block_note (basic_block block
)
686 /* Get the first instruction in the block. */
687 insn
= BB_HEAD (block
);
689 if (insn
== NULL_RTX
)
692 insn
= NEXT_INSN (insn
);
693 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
695 return NEXT_INSN (insn
);
698 /* Creates a new basic block just after basic block B by splitting
699 everything after specified instruction I. */
702 rtl_split_block (basic_block bb
, void *insnp
)
705 rtx insn
= (rtx
) insnp
;
711 insn
= first_insn_after_basic_block_note (bb
);
717 insn
= PREV_INSN (insn
);
719 /* If the block contains only debug insns, insn would have
720 been NULL in a non-debug compilation, and then we'd end
721 up emitting a DELETED note. For -fcompare-debug
722 stability, emit the note too. */
723 if (insn
!= BB_END (bb
)
724 && DEBUG_INSN_P (next
)
725 && DEBUG_INSN_P (BB_END (bb
)))
727 while (next
!= BB_END (bb
) && DEBUG_INSN_P (next
))
728 next
= NEXT_INSN (next
);
730 if (next
== BB_END (bb
))
731 emit_note_after (NOTE_INSN_DELETED
, next
);
735 insn
= get_last_insn ();
738 /* We probably should check type of the insn so that we do not create
739 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
741 if (insn
== BB_END (bb
))
742 emit_note_after (NOTE_INSN_DELETED
, insn
);
744 /* Create the new basic block. */
745 new_bb
= create_basic_block (NEXT_INSN (insn
), BB_END (bb
), bb
);
746 BB_COPY_PARTITION (new_bb
, bb
);
747 SET_BB_END (bb
) = insn
;
749 /* Redirect the outgoing edges. */
750 new_bb
->succs
= bb
->succs
;
752 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
755 /* The new block starts off being dirty. */
756 df_set_bb_dirty (bb
);
760 /* Return true if the single edge between blocks A and B is the only place
761 in RTL which holds some unique locus. */
764 unique_locus_on_edge_between_p (basic_block a
, basic_block b
)
766 const location_t goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
769 if (LOCATION_LOCUS (goto_locus
) == UNKNOWN_LOCATION
)
772 /* First scan block A backward. */
774 end
= PREV_INSN (BB_HEAD (a
));
775 while (insn
!= end
&& (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
776 insn
= PREV_INSN (insn
);
778 if (insn
!= end
&& INSN_LOCATION (insn
) == goto_locus
)
781 /* Then scan block B forward. */
785 end
= NEXT_INSN (BB_END (b
));
786 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
787 insn
= NEXT_INSN (insn
);
789 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
790 && INSN_LOCATION (insn
) == goto_locus
)
797 /* If the single edge between blocks A and B is the only place in RTL which
798 holds some unique locus, emit a nop with that locus between the blocks. */
801 emit_nop_for_unique_locus_between (basic_block a
, basic_block b
)
803 if (!unique_locus_on_edge_between_p (a
, b
))
806 SET_BB_END (a
) = emit_insn_after_noloc (gen_nop (), BB_END (a
), a
);
807 INSN_LOCATION (BB_END (a
)) = EDGE_SUCC (a
, 0)->goto_locus
;
810 /* Blocks A and B are to be merged into a single block A. The insns
811 are already contiguous. */
814 rtl_merge_blocks (basic_block a
, basic_block b
)
816 rtx b_head
= BB_HEAD (b
), b_end
= BB_END (b
), a_end
= BB_END (a
);
817 rtx del_first
= NULL_RTX
, del_last
= NULL_RTX
;
818 rtx b_debug_start
= b_end
, b_debug_end
= b_end
;
819 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
823 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
826 while (DEBUG_INSN_P (b_end
))
827 b_end
= PREV_INSN (b_debug_start
= b_end
);
829 /* If there was a CODE_LABEL beginning B, delete it. */
830 if (LABEL_P (b_head
))
832 /* Detect basic blocks with nothing but a label. This can happen
833 in particular at the end of a function. */
837 del_first
= del_last
= b_head
;
838 b_head
= NEXT_INSN (b_head
);
841 /* Delete the basic block note and handle blocks containing just that
843 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
851 b_head
= NEXT_INSN (b_head
);
854 /* If there was a jump out of A, delete it. */
859 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
861 || NOTE_INSN_BASIC_BLOCK_P (prev
)
862 || prev
== BB_HEAD (a
))
868 /* If this was a conditional jump, we need to also delete
869 the insn that set cc0. */
870 if (only_sets_cc0_p (prev
))
874 prev
= prev_nonnote_insn (prev
);
881 a_end
= PREV_INSN (del_first
);
883 else if (BARRIER_P (NEXT_INSN (a_end
)))
884 del_first
= NEXT_INSN (a_end
);
886 /* Delete everything marked above as well as crap that might be
887 hanging out between the two blocks. */
888 SET_BB_END (a
) = a_end
;
889 SET_BB_HEAD (b
) = b_empty
? NULL_RTX
: b_head
;
890 delete_insn_chain (del_first
, del_last
, true);
892 /* When not optimizing and the edge is the only place in RTL which holds
893 some unique locus, emit a nop with that locus in between. */
896 emit_nop_for_unique_locus_between (a
, b
);
900 /* Reassociate the insns of B with A. */
903 update_bb_for_insn_chain (a_end
, b_debug_end
, a
);
905 SET_BB_END (a
) = b_debug_end
;
906 SET_BB_HEAD (b
) = NULL_RTX
;
908 else if (b_end
!= b_debug_end
)
910 /* Move any deleted labels and other notes between the end of A
911 and the debug insns that make up B after the debug insns,
912 bringing the debug insns into A while keeping the notes after
914 if (NEXT_INSN (a_end
) != b_debug_start
)
915 reorder_insns_nobb (NEXT_INSN (a_end
), PREV_INSN (b_debug_start
),
917 update_bb_for_insn_chain (b_debug_start
, b_debug_end
, a
);
918 SET_BB_END (a
) = b_debug_end
;
921 df_bb_delete (b
->index
);
923 /* If B was a forwarder block, propagate the locus on the edge. */
925 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
926 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
929 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
933 /* Return true when block A and B can be merged. */
936 rtl_can_merge_blocks (basic_block a
, basic_block b
)
938 /* If we are partitioning hot/cold basic blocks, we don't want to
939 mess up unconditional or indirect jumps that cross between hot
942 Basic block partitioning may result in some jumps that appear to
943 be optimizable (or blocks that appear to be mergeable), but which really
944 must be left untouched (they are required to make it safely across
945 partition boundaries). See the comments at the top of
946 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
948 if (BB_PARTITION (a
) != BB_PARTITION (b
))
951 /* Protect the loop latches. */
952 if (current_loops
&& b
->loop_father
->latch
== b
)
955 /* There must be exactly one edge in between the blocks. */
956 return (single_succ_p (a
)
957 && single_succ (a
) == b
960 /* Must be simple edge. */
961 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
963 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
964 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
965 /* If the jump insn has side effects,
966 we can't kill the edge. */
967 && (!JUMP_P (BB_END (a
))
969 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
972 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
976 block_label (basic_block block
)
978 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
981 if (!LABEL_P (BB_HEAD (block
)))
983 SET_BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
986 return BB_HEAD (block
);
989 /* Attempt to perform edge redirection by replacing possibly complex jump
990 instruction by unconditional jump or removing jump completely. This can
991 apply only if all edges now point to the same block. The parameters and
992 return values are equivalent to redirect_edge_and_branch. */
995 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
997 basic_block src
= e
->src
;
998 rtx insn
= BB_END (src
), kill_from
;
1002 /* If we are partitioning hot/cold basic blocks, we don't want to
1003 mess up unconditional or indirect jumps that cross between hot
1006 Basic block partitioning may result in some jumps that appear to
1007 be optimizable (or blocks that appear to be mergeable), but which really
1008 must be left untouched (they are required to make it safely across
1009 partition boundaries). See the comments at the top of
1010 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1012 if (BB_PARTITION (src
) != BB_PARTITION (target
))
1015 /* We can replace or remove a complex jump only when we have exactly
1016 two edges. Also, if we have exactly one outgoing edge, we can
1018 if (EDGE_COUNT (src
->succs
) >= 3
1019 /* Verify that all targets will be TARGET. Specifically, the
1020 edge that is not E must also go to TARGET. */
1021 || (EDGE_COUNT (src
->succs
) == 2
1022 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
1025 if (!onlyjump_p (insn
))
1027 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
1030 /* Avoid removing branch with side effects. */
1031 set
= single_set (insn
);
1032 if (!set
|| side_effects_p (set
))
1035 /* In case we zap a conditional jump, we'll need to kill
1036 the cc0 setter too. */
1039 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
))
1040 && only_sets_cc0_p (PREV_INSN (insn
)))
1041 kill_from
= PREV_INSN (insn
);
1044 /* See if we can create the fallthru edge. */
1045 if (in_cfglayout
|| can_fallthru (src
, target
))
1048 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
1051 /* Selectively unlink whole insn chain. */
1054 rtx insn
= BB_FOOTER (src
);
1056 delete_insn_chain (kill_from
, BB_END (src
), false);
1058 /* Remove barriers but keep jumptables. */
1061 if (BARRIER_P (insn
))
1063 if (PREV_INSN (insn
))
1064 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1066 SET_BB_FOOTER (src
) = NEXT_INSN (insn
);
1067 if (NEXT_INSN (insn
))
1068 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1072 insn
= NEXT_INSN (insn
);
1076 delete_insn_chain (kill_from
, PREV_INSN (BB_HEAD (target
)),
1080 /* If this already is simplejump, redirect it. */
1081 else if (simplejump_p (insn
))
1083 if (e
->dest
== target
)
1086 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
1087 INSN_UID (insn
), e
->dest
->index
, target
->index
);
1088 if (!redirect_jump (insn
, block_label (target
), 0))
1090 gcc_assert (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1095 /* Cannot do anything for target exit block. */
1096 else if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1099 /* Or replace possibly complicated jump insn by simple jump insn. */
1102 rtx target_label
= block_label (target
);
1104 rtx_jump_table_data
*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 SET_NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
1138 SET_PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
1140 SET_NEXT_INSN (new_insn
) = barrier
;
1141 SET_NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
1143 SET_PREV_INSN (new_insn
) = PREV_INSN (barrier
);
1144 SET_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
)
1177 rtx_jump_table_data
*table
;
1179 /* Recognize a tablejump and adjust all matching cases. */
1180 if (tablejump_p (insn
, NULL
, &table
))
1184 rtx new_label
= block_label (new_bb
);
1186 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1188 if (GET_CODE (PATTERN (table
)) == ADDR_VEC
)
1189 vec
= XVEC (PATTERN (table
), 0);
1191 vec
= XVEC (PATTERN (table
), 1);
1193 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
1194 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
1196 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
1197 --LABEL_NUSES (old_label
);
1198 ++LABEL_NUSES (new_label
);
1201 /* Handle casesi dispatch insns. */
1202 if ((tmp
= single_set (insn
)) != NULL
1203 && SET_DEST (tmp
) == pc_rtx
1204 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
1205 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
1206 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
1208 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
1210 --LABEL_NUSES (old_label
);
1211 ++LABEL_NUSES (new_label
);
1214 else if ((tmp
= extract_asm_operands (PATTERN (insn
))) != NULL
)
1216 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (tmp
);
1217 rtx new_label
, note
;
1219 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1221 new_label
= block_label (new_bb
);
1223 for (i
= 0; i
< n
; ++i
)
1225 rtx old_ref
= ASM_OPERANDS_LABEL (tmp
, i
);
1226 gcc_assert (GET_CODE (old_ref
) == LABEL_REF
);
1227 if (XEXP (old_ref
, 0) == old_label
)
1229 ASM_OPERANDS_LABEL (tmp
, i
)
1230 = gen_rtx_LABEL_REF (Pmode
, new_label
);
1231 --LABEL_NUSES (old_label
);
1232 ++LABEL_NUSES (new_label
);
1236 if (JUMP_LABEL (insn
) == old_label
)
1238 JUMP_LABEL (insn
) = new_label
;
1239 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1241 remove_note (insn
, note
);
1245 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1247 remove_note (insn
, note
);
1248 if (JUMP_LABEL (insn
) != new_label
1249 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1250 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1252 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1254 XEXP (note
, 0) = new_label
;
1258 /* ?? We may play the games with moving the named labels from
1259 one basic block to the other in case only one computed_jump is
1261 if (computed_jump_p (insn
)
1262 /* A return instruction can't be redirected. */
1263 || returnjump_p (insn
))
1266 if (!currently_expanding_to_rtl
|| JUMP_LABEL (insn
) == old_label
)
1268 /* If the insn doesn't go where we think, we're confused. */
1269 gcc_assert (JUMP_LABEL (insn
) == old_label
);
1271 /* If the substitution doesn't succeed, die. This can happen
1272 if the back end emitted unrecognizable instructions or if
1273 target is exit block on some arches. */
1274 if (!redirect_jump (insn
, block_label (new_bb
), 0))
1276 gcc_assert (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1285 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1288 redirect_branch_edge (edge e
, basic_block target
)
1290 rtx old_label
= BB_HEAD (e
->dest
);
1291 basic_block src
= e
->src
;
1292 rtx insn
= BB_END (src
);
1294 /* We can only redirect non-fallthru edges of jump insn. */
1295 if (e
->flags
& EDGE_FALLTHRU
)
1297 else if (!JUMP_P (insn
) && !currently_expanding_to_rtl
)
1300 if (!currently_expanding_to_rtl
)
1302 if (!patch_jump_insn (insn
, old_label
, target
))
1306 /* When expanding this BB might actually contain multiple
1307 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1308 Redirect all of those that match our label. */
1309 FOR_BB_INSNS (src
, insn
)
1310 if (JUMP_P (insn
) && !patch_jump_insn (insn
, old_label
, target
))
1314 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
1315 e
->src
->index
, e
->dest
->index
, target
->index
);
1317 if (e
->dest
!= target
)
1318 e
= redirect_edge_succ_nodup (e
, target
);
1323 /* Called when edge E has been redirected to a new destination,
1324 in order to update the region crossing flag on the edge and
1328 fixup_partition_crossing (edge e
)
1330 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || e
->dest
1331 == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1333 /* If we redirected an existing edge, it may already be marked
1334 crossing, even though the new src is missing a reg crossing note.
1335 But make sure reg crossing note doesn't already exist before
1337 if (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1339 e
->flags
|= EDGE_CROSSING
;
1340 if (JUMP_P (BB_END (e
->src
))
1341 && !CROSSING_JUMP_P (BB_END (e
->src
)))
1342 CROSSING_JUMP_P (BB_END (e
->src
)) = 1;
1344 else if (BB_PARTITION (e
->src
) == BB_PARTITION (e
->dest
))
1346 e
->flags
&= ~EDGE_CROSSING
;
1347 /* Remove the section crossing note from jump at end of
1348 src if it exists, and if no other successors are
1350 if (JUMP_P (BB_END (e
->src
)) && CROSSING_JUMP_P (BB_END (e
->src
)))
1352 bool has_crossing_succ
= false;
1355 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
1357 has_crossing_succ
|= (e2
->flags
& EDGE_CROSSING
);
1358 if (has_crossing_succ
)
1361 if (!has_crossing_succ
)
1362 CROSSING_JUMP_P (BB_END (e
->src
)) = 0;
1367 /* Called when block BB has been reassigned to the cold partition,
1368 because it is now dominated by another cold block,
1369 to ensure that the region crossing attributes are updated. */
1372 fixup_new_cold_bb (basic_block bb
)
1377 /* This is called when a hot bb is found to now be dominated
1378 by a cold bb and therefore needs to become cold. Therefore,
1379 its preds will no longer be region crossing. Any non-dominating
1380 preds that were previously hot would also have become cold
1381 in the caller for the same region. Any preds that were previously
1382 region-crossing will be adjusted in fixup_partition_crossing. */
1383 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1385 fixup_partition_crossing (e
);
1388 /* Possibly need to make bb's successor edges region crossing,
1389 or remove stale region crossing. */
1390 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1392 /* We can't have fall-through edges across partition boundaries.
1393 Note that force_nonfallthru will do any necessary partition
1394 boundary fixup by calling fixup_partition_crossing itself. */
1395 if ((e
->flags
& EDGE_FALLTHRU
)
1396 && BB_PARTITION (bb
) != BB_PARTITION (e
->dest
)
1397 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1398 force_nonfallthru (e
);
1400 fixup_partition_crossing (e
);
1404 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1405 expense of adding new instructions or reordering basic blocks.
1407 Function can be also called with edge destination equivalent to the TARGET.
1408 Then it should try the simplifications and do nothing if none is possible.
1410 Return edge representing the branch if transformation succeeded. Return NULL
1412 We still return NULL in case E already destinated TARGET and we didn't
1413 managed to simplify instruction stream. */
1416 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
1419 basic_block src
= e
->src
;
1420 basic_block dest
= e
->dest
;
1422 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1428 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
1430 df_set_bb_dirty (src
);
1431 fixup_partition_crossing (ret
);
1435 ret
= redirect_branch_edge (e
, target
);
1439 df_set_bb_dirty (src
);
1440 fixup_partition_crossing (ret
);
1444 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1447 emit_barrier_after_bb (basic_block bb
)
1449 rtx_barrier
*barrier
= emit_barrier_after (BB_END (bb
));
1450 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1451 || current_ir_type () == IR_RTL_CFGLAYOUT
);
1452 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
1453 SET_BB_FOOTER (bb
) = unlink_insn_chain (barrier
, barrier
);
1456 /* Like force_nonfallthru below, but additionally performs redirection
1457 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1458 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1459 simple_return_rtx, indicating which kind of returnjump to create.
1460 It should be NULL otherwise. */
1463 force_nonfallthru_and_redirect (edge e
, basic_block target
, rtx jump_label
)
1465 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
1468 int abnormal_edge_flags
= 0;
1469 bool asm_goto_edge
= false;
1472 /* In the case the last instruction is conditional jump to the next
1473 instruction, first redirect the jump itself and then continue
1474 by creating a basic block afterwards to redirect fallthru edge. */
1475 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1476 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1477 && any_condjump_p (BB_END (e
->src
))
1478 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1481 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1484 redirected
= redirect_jump (BB_END (e
->src
), block_label (target
), 0);
1485 gcc_assert (redirected
);
1487 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1490 int prob
= XINT (note
, 0);
1492 b
->probability
= prob
;
1493 /* Update this to use GCOV_COMPUTE_SCALE. */
1494 b
->count
= e
->count
* prob
/ REG_BR_PROB_BASE
;
1495 e
->probability
-= e
->probability
;
1496 e
->count
-= b
->count
;
1497 if (e
->probability
< 0)
1504 if (e
->flags
& EDGE_ABNORMAL
)
1506 /* Irritating special case - fallthru edge to the same block as abnormal
1508 We can't redirect abnormal edge, but we still can split the fallthru
1509 one and create separate abnormal edge to original destination.
1510 This allows bb-reorder to make such edge non-fallthru. */
1511 gcc_assert (e
->dest
== target
);
1512 abnormal_edge_flags
= e
->flags
& ~EDGE_FALLTHRU
;
1513 e
->flags
&= EDGE_FALLTHRU
;
1517 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1518 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1520 /* We can't redirect the entry block. Create an empty block
1521 at the start of the function which we use to add the new
1527 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
,
1528 ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1530 /* Change the existing edge's source to be the new block, and add
1531 a new edge from the entry block to the new block. */
1533 for (ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
1534 (tmp
= ei_safe_edge (ei
)); )
1538 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
->unordered_remove (ei
.index
);
1548 vec_safe_push (bb
->succs
, e
);
1549 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
,
1554 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1555 don't point to the target or fallthru label. */
1556 if (JUMP_P (BB_END (e
->src
))
1557 && target
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1558 && (e
->flags
& EDGE_FALLTHRU
)
1559 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
1561 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
1562 bool adjust_jump_target
= false;
1564 for (i
= 0; i
< n
; ++i
)
1566 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (e
->dest
))
1568 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))--;
1569 XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) = block_label (target
);
1570 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))++;
1571 adjust_jump_target
= true;
1573 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (target
))
1574 asm_goto_edge
= true;
1576 if (adjust_jump_target
)
1578 rtx insn
= BB_END (e
->src
), note
;
1579 rtx old_label
= BB_HEAD (e
->dest
);
1580 rtx new_label
= BB_HEAD (target
);
1582 if (JUMP_LABEL (insn
) == old_label
)
1584 JUMP_LABEL (insn
) = new_label
;
1585 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1587 remove_note (insn
, note
);
1591 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1593 remove_note (insn
, note
);
1594 if (JUMP_LABEL (insn
) != new_label
1595 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1596 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1598 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1600 XEXP (note
, 0) = new_label
;
1604 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
|| asm_goto_edge
)
1606 gcov_type count
= e
->count
;
1607 int probability
= e
->probability
;
1608 /* Create the new structures. */
1610 /* If the old block ended with a tablejump, skip its table
1611 by searching forward from there. Otherwise start searching
1612 forward from the last instruction of the old block. */
1613 rtx_jump_table_data
*table
;
1614 if (tablejump_p (BB_END (e
->src
), NULL
, &table
))
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
)))
1765 /* If this was a conditional jump, we need to also delete
1766 the insn that set cc0. */
1767 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1774 /* Selectively unlink the sequence. */
1775 if (q
!= PREV_INSN (BB_HEAD (c
)))
1776 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1778 e
->flags
|= EDGE_FALLTHRU
;
1781 /* Should move basic block BB after basic block AFTER. NIY. */
1784 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1785 basic_block after ATTRIBUTE_UNUSED
)
1790 /* Locate the last bb in the same partition as START_BB. */
1793 last_bb_in_partition (basic_block start_bb
)
1796 FOR_BB_BETWEEN (bb
, start_bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1798 if (BB_PARTITION (start_bb
) != BB_PARTITION (bb
->next_bb
))
1801 /* Return bb before the exit block. */
1805 /* Split a (typically critical) edge. Return the new block.
1806 The edge must not be abnormal.
1808 ??? The code generally expects to be called on critical edges.
1809 The case of a block ending in an unconditional jump to a
1810 block with multiple predecessors is not handled optimally. */
1813 rtl_split_edge (edge edge_in
)
1815 basic_block bb
, new_bb
;
1818 /* Abnormal edges cannot be split. */
1819 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1821 /* We are going to place the new block in front of edge destination.
1822 Avoid existence of fallthru predecessors. */
1823 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1825 edge e
= find_fallthru_edge (edge_in
->dest
->preds
);
1828 force_nonfallthru (e
);
1831 /* Create the basic block note. */
1832 if (edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1833 before
= BB_HEAD (edge_in
->dest
);
1837 /* If this is a fall through edge to the exit block, the blocks might be
1838 not adjacent, and the right place is after the source. */
1839 if ((edge_in
->flags
& EDGE_FALLTHRU
)
1840 && edge_in
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1842 before
= NEXT_INSN (BB_END (edge_in
->src
));
1843 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1844 BB_COPY_PARTITION (bb
, edge_in
->src
);
1848 if (edge_in
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1850 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1851 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1855 basic_block after
= edge_in
->dest
->prev_bb
;
1856 /* If this is post-bb reordering, and the edge crosses a partition
1857 boundary, the new block needs to be inserted in the bb chain
1858 at the end of the src partition (since we put the new bb into
1859 that partition, see below). Otherwise we may end up creating
1860 an extra partition crossing in the chain, which is illegal.
1861 It can't go after the src, because src may have a fall-through
1862 to a different block. */
1863 if (crtl
->bb_reorder_complete
1864 && (edge_in
->flags
& EDGE_CROSSING
))
1866 after
= last_bb_in_partition (edge_in
->src
);
1867 before
= NEXT_INSN (BB_END (after
));
1868 /* The instruction following the last bb in partition should
1869 be a barrier, since it cannot end in a fall-through. */
1870 gcc_checking_assert (BARRIER_P (before
));
1871 before
= NEXT_INSN (before
);
1873 bb
= create_basic_block (before
, NULL
, after
);
1874 /* Put the split bb into the src partition, to avoid creating
1875 a situation where a cold bb dominates a hot bb, in the case
1876 where src is cold and dest is hot. The src will dominate
1877 the new bb (whereas it might not have dominated dest). */
1878 BB_COPY_PARTITION (bb
, edge_in
->src
);
1882 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1884 /* Can't allow a region crossing edge to be fallthrough. */
1885 if (BB_PARTITION (bb
) != BB_PARTITION (edge_in
->dest
)
1886 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1888 new_bb
= force_nonfallthru (single_succ_edge (bb
));
1889 gcc_assert (!new_bb
);
1892 /* For non-fallthru edges, we must adjust the predecessor's
1893 jump instruction to target our new block. */
1894 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1896 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1897 gcc_assert (redirected
);
1901 if (edge_in
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1903 /* For asm goto even splitting of fallthru edge might
1904 need insn patching, as other labels might point to the
1906 rtx last
= BB_END (edge_in
->src
);
1909 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1910 && extract_asm_operands (PATTERN (last
)) != NULL_RTX
1911 && patch_jump_insn (last
, before
, bb
))
1912 df_set_bb_dirty (edge_in
->src
);
1914 redirect_edge_succ (edge_in
, bb
);
1920 /* Queue instructions for insertion on an edge between two basic blocks.
1921 The new instructions and basic blocks (if any) will not appear in the
1922 CFG until commit_edge_insertions is called. */
1925 insert_insn_on_edge (rtx pattern
, edge e
)
1927 /* We cannot insert instructions on an abnormal critical edge.
1928 It will be easier to find the culprit if we die now. */
1929 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1931 if (e
->insns
.r
== NULL_RTX
)
1934 push_to_sequence (e
->insns
.r
);
1936 emit_insn (pattern
);
1938 e
->insns
.r
= get_insns ();
1942 /* Update the CFG for the instructions queued on edge E. */
1945 commit_one_edge_insertion (edge e
)
1947 rtx before
= NULL_RTX
, after
= NULL_RTX
, insns
, tmp
, last
;
1950 /* Pull the insns off the edge now since the edge might go away. */
1952 e
->insns
.r
= NULL_RTX
;
1954 /* Figure out where to put these insns. If the destination has
1955 one predecessor, insert there. Except for the exit block. */
1956 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1960 /* Get the location correct wrt a code label, and "nice" wrt
1961 a basic block note, and before everything else. */
1964 tmp
= NEXT_INSN (tmp
);
1965 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1966 tmp
= NEXT_INSN (tmp
);
1967 if (tmp
== BB_HEAD (bb
))
1970 after
= PREV_INSN (tmp
);
1972 after
= get_last_insn ();
1975 /* If the source has one successor and the edge is not abnormal,
1976 insert there. Except for the entry block.
1977 Don't do this if the predecessor ends in a jump other than
1978 unconditional simple jump. E.g. for asm goto that points all
1979 its labels at the fallthru basic block, we can't insert instructions
1980 before the asm goto, as the asm goto can have various of side effects,
1981 and can't emit instructions after the asm goto, as it must end
1983 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1984 && single_succ_p (e
->src
)
1985 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1986 && (!JUMP_P (BB_END (e
->src
))
1987 || simplejump_p (BB_END (e
->src
))))
1991 /* It is possible to have a non-simple jump here. Consider a target
1992 where some forms of unconditional jumps clobber a register. This
1993 happens on the fr30 for example.
1995 We know this block has a single successor, so we can just emit
1996 the queued insns before the jump. */
1997 if (JUMP_P (BB_END (bb
)))
1998 before
= BB_END (bb
);
2001 /* We'd better be fallthru, or we've lost track of what's what. */
2002 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
2004 after
= BB_END (bb
);
2008 /* Otherwise we must split the edge. */
2011 bb
= split_edge (e
);
2013 /* If E crossed a partition boundary, we needed to make bb end in
2014 a region-crossing jump, even though it was originally fallthru. */
2015 if (JUMP_P (BB_END (bb
)))
2016 before
= BB_END (bb
);
2018 after
= BB_END (bb
);
2021 /* Now that we've found the spot, do the insertion. */
2024 emit_insn_before_noloc (insns
, before
, bb
);
2025 last
= prev_nonnote_insn (before
);
2028 last
= emit_insn_after_noloc (insns
, after
, bb
);
2030 if (returnjump_p (last
))
2032 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2033 This is not currently a problem because this only happens
2034 for the (single) epilogue, which already has a fallthru edge
2037 e
= single_succ_edge (bb
);
2038 gcc_assert (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2039 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
2041 e
->flags
&= ~EDGE_FALLTHRU
;
2042 emit_barrier_after (last
);
2045 delete_insn (before
);
2048 gcc_assert (!JUMP_P (last
));
2051 /* Update the CFG for all queued instructions. */
2054 commit_edge_insertions (void)
2058 /* Optimization passes that invoke this routine can cause hot blocks
2059 previously reached by both hot and cold blocks to become dominated only
2060 by cold blocks. This will cause the verification below to fail,
2061 and lead to now cold code in the hot section. In some cases this
2062 may only be visible after newly unreachable blocks are deleted,
2063 which will be done by fixup_partitions. */
2064 fixup_partitions ();
2066 #ifdef ENABLE_CHECKING
2067 verify_flow_info ();
2070 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
2071 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
2076 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2078 commit_one_edge_insertion (e
);
2083 /* Print out RTL-specific basic block information (live information
2084 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2085 documented in dumpfile.h. */
2088 rtl_dump_bb (FILE *outf
, basic_block bb
, int indent
, int flags
)
2094 s_indent
= (char *) alloca ((size_t) indent
+ 1);
2095 memset (s_indent
, ' ', (size_t) indent
);
2096 s_indent
[indent
] = '\0';
2098 if (df
&& (flags
& TDF_DETAILS
))
2100 df_dump_top (bb
, outf
);
2104 if (bb
->index
!= ENTRY_BLOCK
&& bb
->index
!= EXIT_BLOCK
)
2105 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
)); insn
!= last
;
2106 insn
= NEXT_INSN (insn
))
2108 if (flags
& TDF_DETAILS
)
2109 df_dump_insn_top (insn
, outf
);
2110 if (! (flags
& TDF_SLIM
))
2111 print_rtl_single (outf
, insn
);
2113 dump_insn_slim (outf
, insn
);
2114 if (flags
& TDF_DETAILS
)
2115 df_dump_insn_bottom (insn
, outf
);
2118 if (df
&& (flags
& TDF_DETAILS
))
2120 df_dump_bottom (bb
, outf
);
2126 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2127 for the start of each basic block. FLAGS are the TDF_* masks documented
2131 print_rtl_with_bb (FILE *outf
, const_rtx rtx_first
, int flags
)
2135 fprintf (outf
, "(nil)\n");
2138 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
2139 int max_uid
= get_max_uid ();
2140 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
2141 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
2142 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
2145 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2146 insns, but the CFG is not maintained so the basic block info
2147 is not reliable. Therefore it's omitted from the dumps. */
2148 if (! (cfun
->curr_properties
& PROP_cfg
))
2149 flags
&= ~TDF_BLOCKS
;
2152 df_dump_start (outf
);
2154 if (flags
& TDF_BLOCKS
)
2156 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2160 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
2161 end
[INSN_UID (BB_END (bb
))] = bb
;
2162 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
2164 enum bb_state state
= IN_MULTIPLE_BB
;
2166 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
2168 in_bb_p
[INSN_UID (x
)] = state
;
2170 if (x
== BB_END (bb
))
2176 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
2178 if (flags
& TDF_BLOCKS
)
2180 bb
= start
[INSN_UID (tmp_rtx
)];
2183 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, true, false);
2184 if (df
&& (flags
& TDF_DETAILS
))
2185 df_dump_top (bb
, outf
);
2188 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
2189 && !NOTE_P (tmp_rtx
)
2190 && !BARRIER_P (tmp_rtx
))
2191 fprintf (outf
, ";; Insn is not within a basic block\n");
2192 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
2193 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
2196 if (flags
& TDF_DETAILS
)
2197 df_dump_insn_top (tmp_rtx
, outf
);
2198 if (! (flags
& TDF_SLIM
))
2199 print_rtl_single (outf
, tmp_rtx
);
2201 dump_insn_slim (outf
, tmp_rtx
);
2202 if (flags
& TDF_DETAILS
)
2203 df_dump_insn_bottom (tmp_rtx
, outf
);
2205 if (flags
& TDF_BLOCKS
)
2207 bb
= end
[INSN_UID (tmp_rtx
)];
2210 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, false, true);
2211 if (df
&& (flags
& TDF_DETAILS
))
2212 df_dump_bottom (bb
, outf
);
2224 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2227 update_br_prob_note (basic_block bb
)
2230 if (!JUMP_P (BB_END (bb
)))
2232 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
2233 if (!note
|| XINT (note
, 0) == BRANCH_EDGE (bb
)->probability
)
2235 XINT (note
, 0) = BRANCH_EDGE (bb
)->probability
;
2238 /* Get the last insn associated with block BB (that includes barriers and
2239 tablejumps after BB). */
2241 get_last_bb_insn (basic_block bb
)
2243 rtx_jump_table_data
*table
;
2245 rtx end
= BB_END (bb
);
2247 /* Include any jump table following the basic block. */
2248 if (tablejump_p (end
, NULL
, &table
))
2251 /* Include any barriers that may follow the basic block. */
2252 tmp
= next_nonnote_insn_bb (end
);
2253 while (tmp
&& BARRIER_P (tmp
))
2256 tmp
= next_nonnote_insn_bb (end
);
2262 /* Sanity check partition hotness to ensure that basic blocks in
2263 Â the cold partition don't dominate basic blocks in the hot partition.
2264 If FLAG_ONLY is true, report violations as errors. Otherwise
2265 re-mark the dominated blocks as cold, since this is run after
2266 cfg optimizations that may make hot blocks previously reached
2267 by both hot and cold blocks now only reachable along cold paths. */
2269 static vec
<basic_block
>
2270 find_partition_fixes (bool flag_only
)
2273 vec
<basic_block
> bbs_in_cold_partition
= vNULL
;
2274 vec
<basic_block
> bbs_to_fix
= vNULL
;
2276 /* Callers check this. */
2277 gcc_checking_assert (crtl
->has_bb_partition
);
2279 FOR_EACH_BB_FN (bb
, cfun
)
2280 if ((BB_PARTITION (bb
) == BB_COLD_PARTITION
))
2281 bbs_in_cold_partition
.safe_push (bb
);
2283 if (bbs_in_cold_partition
.is_empty ())
2286 bool dom_calculated_here
= !dom_info_available_p (CDI_DOMINATORS
);
2288 if (dom_calculated_here
)
2289 calculate_dominance_info (CDI_DOMINATORS
);
2291 while (! bbs_in_cold_partition
.is_empty ())
2293 bb
= bbs_in_cold_partition
.pop ();
2294 /* Any blocks dominated by a block in the cold section
2295 must also be cold. */
2297 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2299 son
= next_dom_son (CDI_DOMINATORS
, son
))
2301 /* If son is not yet cold, then mark it cold here and
2302 enqueue it for further processing. */
2303 if ((BB_PARTITION (son
) != BB_COLD_PARTITION
))
2306 error ("non-cold basic block %d dominated "
2307 "by a block in the cold partition (%d)", son
->index
, bb
->index
);
2309 BB_SET_PARTITION (son
, BB_COLD_PARTITION
);
2310 bbs_to_fix
.safe_push (son
);
2311 bbs_in_cold_partition
.safe_push (son
);
2316 if (dom_calculated_here
)
2317 free_dominance_info (CDI_DOMINATORS
);
2322 /* Perform cleanup on the hot/cold bb partitioning after optimization
2323 passes that modify the cfg. */
2326 fixup_partitions (void)
2330 if (!crtl
->has_bb_partition
)
2333 /* Delete any blocks that became unreachable and weren't
2334 already cleaned up, for example during edge forwarding
2335 and convert_jumps_to_returns. This will expose more
2336 opportunities for fixing the partition boundaries here.
2337 Also, the calculation of the dominance graph during verification
2338 will assert if there are unreachable nodes. */
2339 delete_unreachable_blocks ();
2341 /* If there are partitions, do a sanity check on them: A basic block in
2342 Â a cold partition cannot dominate a basic block in a hot partition.
2343 Fixup any that now violate this requirement, as a result of edge
2344 forwarding and unreachable block deletion. Â */
2345 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (false);
2347 /* Do the partition fixup after all necessary blocks have been converted to
2348 cold, so that we only update the region crossings the minimum number of
2349 places, which can require forcing edges to be non fallthru. */
2350 while (! bbs_to_fix
.is_empty ())
2352 bb
= bbs_to_fix
.pop ();
2353 fixup_new_cold_bb (bb
);
2357 /* Verify, in the basic block chain, that there is at most one switch
2358 between hot/cold partitions. This condition will not be true until
2359 after reorder_basic_blocks is called. */
2362 verify_hot_cold_block_grouping (void)
2366 bool switched_sections
= false;
2367 int current_partition
= BB_UNPARTITIONED
;
2369 /* Even after bb reordering is complete, we go into cfglayout mode
2370 again (in compgoto). Ensure we don't call this before going back
2371 into linearized RTL when any layout fixes would have been committed. */
2372 if (!crtl
->bb_reorder_complete
2373 || current_ir_type () != IR_RTL_CFGRTL
)
2376 FOR_EACH_BB_FN (bb
, cfun
)
2378 if (current_partition
!= BB_UNPARTITIONED
2379 && BB_PARTITION (bb
) != current_partition
)
2381 if (switched_sections
)
2383 error ("multiple hot/cold transitions found (bb %i)",
2388 switched_sections
= true;
2390 if (!crtl
->has_bb_partition
)
2391 error ("partition found but function partition flag not set");
2393 current_partition
= BB_PARTITION (bb
);
2400 /* Perform several checks on the edges out of each block, such as
2401 the consistency of the branch probabilities, the correctness
2402 of hot/cold partition crossing edges, and the number of expected
2403 successor edges. Also verify that the dominance relationship
2404 between hot/cold blocks is sane. */
2407 rtl_verify_edges (void)
2412 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2414 int n_fallthru
= 0, n_branch
= 0, n_abnormal_call
= 0, n_sibcall
= 0;
2415 int n_eh
= 0, n_abnormal
= 0;
2416 edge e
, fallthru
= NULL
;
2419 bool has_crossing_edge
= false;
2421 if (JUMP_P (BB_END (bb
))
2422 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
2423 && EDGE_COUNT (bb
->succs
) >= 2
2424 && any_condjump_p (BB_END (bb
)))
2426 if (XINT (note
, 0) != BRANCH_EDGE (bb
)->probability
2427 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2429 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2430 XINT (note
, 0), BRANCH_EDGE (bb
)->probability
);
2435 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2439 if (e
->flags
& EDGE_FALLTHRU
)
2440 n_fallthru
++, fallthru
= e
;
2442 is_crossing
= (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
2443 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2444 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
2445 has_crossing_edge
|= is_crossing
;
2446 if (e
->flags
& EDGE_CROSSING
)
2450 error ("EDGE_CROSSING incorrectly set across same section");
2453 if (e
->flags
& EDGE_FALLTHRU
)
2455 error ("fallthru edge crosses section boundary in bb %i",
2459 if (e
->flags
& EDGE_EH
)
2461 error ("EH edge crosses section boundary in bb %i",
2465 if (JUMP_P (BB_END (bb
)) && !CROSSING_JUMP_P (BB_END (bb
)))
2467 error ("No region crossing jump at section boundary in bb %i",
2472 else if (is_crossing
)
2474 error ("EDGE_CROSSING missing across section boundary");
2478 if ((e
->flags
& ~(EDGE_DFS_BACK
2480 | EDGE_IRREDUCIBLE_LOOP
2483 | EDGE_PRESERVE
)) == 0)
2486 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2489 if (e
->flags
& EDGE_SIBCALL
)
2492 if (e
->flags
& EDGE_EH
)
2495 if (e
->flags
& EDGE_ABNORMAL
)
2499 if (!has_crossing_edge
2500 && JUMP_P (BB_END (bb
))
2501 && CROSSING_JUMP_P (BB_END (bb
)))
2503 print_rtl_with_bb (stderr
, get_insns (), TDF_RTL
| TDF_BLOCKS
| TDF_DETAILS
);
2504 error ("Region crossing jump across same section in bb %i",
2509 if (n_eh
&& !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
2511 error ("missing REG_EH_REGION note at the end of bb %i", bb
->index
);
2516 error ("too many exception handling edges in bb %i", bb
->index
);
2520 && (!JUMP_P (BB_END (bb
))
2521 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
2522 || any_condjump_p (BB_END (bb
))))))
2524 error ("too many outgoing branch edges from bb %i", bb
->index
);
2527 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
2529 error ("fallthru edge after unconditional jump in bb %i", bb
->index
);
2532 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
2534 error ("wrong number of branch edges after unconditional jump"
2535 " in bb %i", bb
->index
);
2538 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
2539 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
2541 error ("wrong amount of branch edges after conditional jump"
2542 " in bb %i", bb
->index
);
2545 if (n_abnormal_call
&& !CALL_P (BB_END (bb
)))
2547 error ("abnormal call edges for non-call insn in bb %i", bb
->index
);
2550 if (n_sibcall
&& !CALL_P (BB_END (bb
)))
2552 error ("sibcall edges for non-call insn in bb %i", bb
->index
);
2555 if (n_abnormal
> n_eh
2556 && !(CALL_P (BB_END (bb
))
2557 && n_abnormal
== n_abnormal_call
+ n_sibcall
)
2558 && (!JUMP_P (BB_END (bb
))
2559 || any_condjump_p (BB_END (bb
))
2560 || any_uncondjump_p (BB_END (bb
))))
2562 error ("abnormal edges for no purpose in bb %i", bb
->index
);
2567 /* If there are partitions, do a sanity check on them: A basic block in
2568 Â a cold partition cannot dominate a basic block in a hot partition. Â */
2569 if (crtl
->has_bb_partition
&& !err
)
2571 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (true);
2572 err
= !bbs_to_fix
.is_empty ();
2579 /* Checks on the instructions within blocks. Currently checks that each
2580 block starts with a basic block note, and that basic block notes and
2581 control flow jumps are not found in the middle of the block. */
2584 rtl_verify_bb_insns (void)
2590 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2592 /* Now check the header of basic
2593 block. It ought to contain optional CODE_LABEL followed
2594 by NOTE_BASIC_BLOCK. */
2598 if (BB_END (bb
) == x
)
2600 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2608 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2610 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2615 if (BB_END (bb
) == x
)
2616 /* Do checks for empty blocks here. */
2619 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2621 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2623 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2624 INSN_UID (x
), bb
->index
);
2628 if (x
== BB_END (bb
))
2631 if (control_flow_insn_p (x
))
2633 error ("in basic block %d:", bb
->index
);
2634 fatal_insn ("flow control insn inside a basic block", x
);
2643 /* Verify that block pointers for instructions in basic blocks, headers and
2644 footers are set appropriately. */
2647 rtl_verify_bb_pointers (void)
2652 /* Check the general integrity of the basic blocks. */
2653 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2657 if (!(bb
->flags
& BB_RTL
))
2659 error ("BB_RTL flag not set for block %d", bb
->index
);
2663 FOR_BB_INSNS (bb
, insn
)
2664 if (BLOCK_FOR_INSN (insn
) != bb
)
2666 error ("insn %d basic block pointer is %d, should be %d",
2668 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
2673 for (insn
= BB_HEADER (bb
); insn
; insn
= NEXT_INSN (insn
))
2674 if (!BARRIER_P (insn
)
2675 && BLOCK_FOR_INSN (insn
) != NULL
)
2677 error ("insn %d in header of bb %d has non-NULL basic block",
2678 INSN_UID (insn
), bb
->index
);
2681 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
2682 if (!BARRIER_P (insn
)
2683 && BLOCK_FOR_INSN (insn
) != NULL
)
2685 error ("insn %d in footer of bb %d has non-NULL basic block",
2686 INSN_UID (insn
), bb
->index
);
2695 /* Verify the CFG and RTL consistency common for both underlying RTL and
2698 Currently it does following checks:
2700 - overlapping of basic blocks
2701 - insns with wrong BLOCK_FOR_INSN pointers
2702 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2703 - tails of basic blocks (ensure that boundary is necessary)
2704 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2705 and NOTE_INSN_BASIC_BLOCK
2706 - verify that no fall_thru edge crosses hot/cold partition boundaries
2707 - verify that there are no pending RTL branch predictions
2708 - verify that hot blocks are not dominated by cold blocks
2710 In future it can be extended check a lot of other stuff as well
2711 (reachability of basic blocks, life information, etc. etc.). */
2714 rtl_verify_flow_info_1 (void)
2718 err
|= rtl_verify_bb_pointers ();
2720 err
|= rtl_verify_bb_insns ();
2722 err
|= rtl_verify_edges ();
2727 /* Walk the instruction chain and verify that bb head/end pointers
2728 are correct, and that instructions are in exactly one bb and have
2729 correct block pointers. */
2732 rtl_verify_bb_insn_chain (void)
2737 rtx last_head
= get_last_insn ();
2738 basic_block
*bb_info
;
2739 const int max_uid
= get_max_uid ();
2741 bb_info
= XCNEWVEC (basic_block
, max_uid
);
2743 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2745 rtx head
= BB_HEAD (bb
);
2746 rtx end
= BB_END (bb
);
2748 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2750 /* Verify the end of the basic block is in the INSN chain. */
2754 /* And that the code outside of basic blocks has NULL bb field. */
2756 && BLOCK_FOR_INSN (x
) != NULL
)
2758 error ("insn %d outside of basic blocks has non-NULL bb field",
2766 error ("end insn %d for block %d not found in the insn stream",
2767 INSN_UID (end
), bb
->index
);
2771 /* Work backwards from the end to the head of the basic block
2772 to verify the head is in the RTL chain. */
2773 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2775 /* While walking over the insn chain, verify insns appear
2776 in only one basic block. */
2777 if (bb_info
[INSN_UID (x
)] != NULL
)
2779 error ("insn %d is in multiple basic blocks (%d and %d)",
2780 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2784 bb_info
[INSN_UID (x
)] = bb
;
2791 error ("head insn %d for block %d not found in the insn stream",
2792 INSN_UID (head
), bb
->index
);
2796 last_head
= PREV_INSN (x
);
2799 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2801 /* Check that the code before the first basic block has NULL
2804 && BLOCK_FOR_INSN (x
) != NULL
)
2806 error ("insn %d outside of basic blocks has non-NULL bb field",
2816 /* Verify that fallthru edges point to adjacent blocks in layout order and
2817 that barriers exist after non-fallthru blocks. */
2820 rtl_verify_fallthru (void)
2825 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2829 e
= find_fallthru_edge (bb
->succs
);
2834 /* Ensure existence of barrier in BB with no fallthru edges. */
2835 for (insn
= NEXT_INSN (BB_END (bb
)); ; insn
= NEXT_INSN (insn
))
2837 if (!insn
|| NOTE_INSN_BASIC_BLOCK_P (insn
))
2839 error ("missing barrier after block %i", bb
->index
);
2843 if (BARRIER_P (insn
))
2847 else if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2848 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2852 if (e
->src
->next_bb
!= e
->dest
)
2855 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2856 e
->src
->index
, e
->dest
->index
);
2860 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
2861 insn
= NEXT_INSN (insn
))
2862 if (BARRIER_P (insn
) || INSN_P (insn
))
2864 error ("verify_flow_info: Incorrect fallthru %i->%i",
2865 e
->src
->index
, e
->dest
->index
);
2866 fatal_insn ("wrong insn in the fallthru edge", insn
);
2875 /* Verify that blocks are laid out in consecutive order. While walking the
2876 instructions, verify that all expected instructions are inside the basic
2877 blocks, and that all returns are followed by barriers. */
2880 rtl_verify_bb_layout (void)
2886 const rtx rtx_first
= get_insns ();
2887 basic_block last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
), curr_bb
= NULL
;
2890 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
2892 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2894 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2896 bb
= NOTE_BASIC_BLOCK (x
);
2899 if (bb
!= last_bb_seen
->next_bb
)
2900 internal_error ("basic blocks not laid down consecutively");
2902 curr_bb
= last_bb_seen
= bb
;
2907 switch (GET_CODE (x
))
2914 /* An ADDR_VEC is placed outside any basic block. */
2916 && JUMP_TABLE_DATA_P (NEXT_INSN (x
)))
2919 /* But in any case, non-deletable labels can appear anywhere. */
2923 fatal_insn ("insn outside basic block", x
);
2928 && returnjump_p (x
) && ! condjump_p (x
)
2929 && ! (next_nonnote_insn (x
) && BARRIER_P (next_nonnote_insn (x
))))
2930 fatal_insn ("return not followed by barrier", x
);
2932 if (curr_bb
&& x
== BB_END (curr_bb
))
2936 if (num_bb_notes
!= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
)
2938 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2939 num_bb_notes
, n_basic_blocks_for_fn (cfun
));
2944 /* Verify the CFG and RTL consistency common for both underlying RTL and
2945 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
2947 Currently it does following checks:
2948 - all checks of rtl_verify_flow_info_1
2949 - test head/end pointers
2950 - check that blocks are laid out in consecutive order
2951 - check that all insns are in the basic blocks
2952 (except the switch handling code, barriers and notes)
2953 - check that all returns are followed by barriers
2954 - check that all fallthru edge points to the adjacent blocks
2955 - verify that there is a single hot/cold partition boundary after bbro */
2958 rtl_verify_flow_info (void)
2962 err
|= rtl_verify_flow_info_1 ();
2964 err
|= rtl_verify_bb_insn_chain ();
2966 err
|= rtl_verify_fallthru ();
2968 err
|= rtl_verify_bb_layout ();
2970 err
|= verify_hot_cold_block_grouping ();
2975 /* Assume that the preceding pass has possibly eliminated jump instructions
2976 or converted the unconditional jumps. Eliminate the edges from CFG.
2977 Return true if any edges are eliminated. */
2980 purge_dead_edges (basic_block bb
)
2983 rtx insn
= BB_END (bb
), note
;
2984 bool purged
= false;
2988 if (DEBUG_INSN_P (insn
) && insn
!= BB_HEAD (bb
))
2990 insn
= PREV_INSN (insn
);
2991 while ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
));
2993 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2994 if (NONJUMP_INSN_P (insn
)
2995 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
2999 if (! may_trap_p (PATTERN (insn
))
3000 || ((eqnote
= find_reg_equal_equiv_note (insn
))
3001 && ! may_trap_p (XEXP (eqnote
, 0))))
3002 remove_note (insn
, note
);
3005 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3006 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3008 bool remove
= false;
3010 /* There are three types of edges we need to handle correctly here: EH
3011 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3012 latter can appear when nonlocal gotos are used. */
3013 if (e
->flags
& EDGE_ABNORMAL_CALL
)
3017 else if (can_nonlocal_goto (insn
))
3019 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3021 else if (flag_tm
&& find_reg_note (insn
, REG_TM
, NULL
))
3026 else if (e
->flags
& EDGE_EH
)
3027 remove
= !can_throw_internal (insn
);
3032 df_set_bb_dirty (bb
);
3045 /* We do care only about conditional jumps and simplejumps. */
3046 if (!any_condjump_p (insn
)
3047 && !returnjump_p (insn
)
3048 && !simplejump_p (insn
))
3051 /* Branch probability/prediction notes are defined only for
3052 condjumps. We've possibly turned condjump into simplejump. */
3053 if (simplejump_p (insn
))
3055 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3057 remove_note (insn
, note
);
3058 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
3059 remove_note (insn
, note
);
3062 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3064 /* Avoid abnormal flags to leak from computed jumps turned
3065 into simplejumps. */
3067 e
->flags
&= ~EDGE_ABNORMAL
;
3069 /* See if this edge is one we should keep. */
3070 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
3071 /* A conditional jump can fall through into the next
3072 block, so we should keep the edge. */
3077 else if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3078 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
3079 /* If the destination block is the target of the jump,
3085 else if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
3086 && returnjump_p (insn
))
3087 /* If the destination block is the exit block, and this
3088 instruction is a return, then keep the edge. */
3093 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3094 /* Keep the edges that correspond to exceptions thrown by
3095 this instruction and rematerialize the EDGE_ABNORMAL
3096 flag we just cleared above. */
3098 e
->flags
|= EDGE_ABNORMAL
;
3103 /* We do not need this edge. */
3104 df_set_bb_dirty (bb
);
3109 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
3113 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
3118 /* Redistribute probabilities. */
3119 if (single_succ_p (bb
))
3121 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3122 single_succ_edge (bb
)->count
= bb
->count
;
3126 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3130 b
= BRANCH_EDGE (bb
);
3131 f
= FALLTHRU_EDGE (bb
);
3132 b
->probability
= XINT (note
, 0);
3133 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
3134 /* Update these to use GCOV_COMPUTE_SCALE. */
3135 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
3136 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
3141 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
3143 /* First, there should not be any EH or ABCALL edges resulting
3144 from non-local gotos and the like. If there were, we shouldn't
3145 have created the sibcall in the first place. Second, there
3146 should of course never have been a fallthru edge. */
3147 gcc_assert (single_succ_p (bb
));
3148 gcc_assert (single_succ_edge (bb
)->flags
3149 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
3154 /* If we don't see a jump insn, we don't know exactly why the block would
3155 have been broken at this point. Look for a simple, non-fallthru edge,
3156 as these are only created by conditional branches. If we find such an
3157 edge we know that there used to be a jump here and can then safely
3158 remove all non-fallthru edges. */
3160 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3161 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
3170 /* Remove all but the fake and fallthru edges. The fake edge may be
3171 the only successor for this block in the case of noreturn
3173 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3175 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
3177 df_set_bb_dirty (bb
);
3185 gcc_assert (single_succ_p (bb
));
3187 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3188 single_succ_edge (bb
)->count
= bb
->count
;
3191 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
3196 /* Search all basic blocks for potentially dead edges and purge them. Return
3197 true if some edge has been eliminated. */
3200 purge_all_dead_edges (void)
3205 FOR_EACH_BB_FN (bb
, cfun
)
3207 bool purged_here
= purge_dead_edges (bb
);
3209 purged
|= purged_here
;
3215 /* This is used by a few passes that emit some instructions after abnormal
3216 calls, moving the basic block's end, while they in fact do want to emit
3217 them on the fallthru edge. Look for abnormal call edges, find backward
3218 the call in the block and insert the instructions on the edge instead.
3220 Similarly, handle instructions throwing exceptions internally.
3222 Return true when instructions have been found and inserted on edges. */
3225 fixup_abnormal_edges (void)
3227 bool inserted
= false;
3230 FOR_EACH_BB_FN (bb
, cfun
)
3235 /* Look for cases we are interested in - calls or instructions causing
3237 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3238 if ((e
->flags
& EDGE_ABNORMAL_CALL
)
3239 || ((e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
3240 == (EDGE_ABNORMAL
| EDGE_EH
)))
3243 if (e
&& !CALL_P (BB_END (bb
)) && !can_throw_internal (BB_END (bb
)))
3247 /* Get past the new insns generated. Allow notes, as the insns
3248 may be already deleted. */
3250 while ((NONJUMP_INSN_P (insn
) || NOTE_P (insn
))
3251 && !can_throw_internal (insn
)
3252 && insn
!= BB_HEAD (bb
))
3253 insn
= PREV_INSN (insn
);
3255 if (CALL_P (insn
) || can_throw_internal (insn
))
3259 e
= find_fallthru_edge (bb
->succs
);
3261 stop
= NEXT_INSN (BB_END (bb
));
3262 SET_BB_END (bb
) = insn
;
3264 for (insn
= NEXT_INSN (insn
); insn
!= stop
; insn
= next
)
3266 next
= NEXT_INSN (insn
);
3271 /* Sometimes there's still the return value USE.
3272 If it's placed after a trapping call (i.e. that
3273 call is the last insn anyway), we have no fallthru
3274 edge. Simply delete this use and don't try to insert
3275 on the non-existent edge. */
3276 if (GET_CODE (PATTERN (insn
)) != USE
)
3278 /* We're not deleting it, we're moving it. */
3279 INSN_DELETED_P (insn
) = 0;
3280 SET_PREV_INSN (insn
) = NULL_RTX
;
3281 SET_NEXT_INSN (insn
) = NULL_RTX
;
3283 insert_insn_on_edge (insn
, e
);
3287 else if (!BARRIER_P (insn
))
3288 set_block_for_insn (insn
, NULL
);
3292 /* It may be that we don't find any trapping insn. In this
3293 case we discovered quite late that the insn that had been
3294 marked as can_throw_internal in fact couldn't trap at all.
3295 So we should in fact delete the EH edges out of the block. */
3297 purge_dead_edges (bb
);
3304 /* Cut the insns from FIRST to LAST out of the insns stream. */
3307 unlink_insn_chain (rtx first
, rtx last
)
3309 rtx_insn
*prevfirst
= PREV_INSN (first
);
3310 rtx_insn
*nextlast
= NEXT_INSN (last
);
3312 SET_PREV_INSN (first
) = NULL
;
3313 SET_NEXT_INSN (last
) = NULL
;
3315 SET_NEXT_INSN (prevfirst
) = nextlast
;
3317 SET_PREV_INSN (nextlast
) = prevfirst
;
3319 set_last_insn (prevfirst
);
3321 set_first_insn (nextlast
);
3322 return as_a
<rtx_insn
*> (first
);
3325 /* Skip over inter-block insns occurring after BB which are typically
3326 associated with BB (e.g., barriers). If there are any such insns,
3327 we return the last one. Otherwise, we return the end of BB. */
3330 skip_insns_after_block (basic_block bb
)
3332 rtx insn
, last_insn
, next_head
, prev
;
3334 next_head
= NULL_RTX
;
3335 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3336 next_head
= BB_HEAD (bb
->next_bb
);
3338 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
3340 if (insn
== next_head
)
3343 switch (GET_CODE (insn
))
3350 switch (NOTE_KIND (insn
))
3352 case NOTE_INSN_BLOCK_END
:
3362 if (NEXT_INSN (insn
)
3363 && JUMP_TABLE_DATA_P (NEXT_INSN (insn
)))
3365 insn
= NEXT_INSN (insn
);
3378 /* It is possible to hit contradictory sequence. For instance:
3384 Where barrier belongs to jump_insn, but the note does not. This can be
3385 created by removing the basic block originally following
3386 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3388 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
3390 prev
= PREV_INSN (insn
);
3392 switch (NOTE_KIND (insn
))
3394 case NOTE_INSN_BLOCK_END
:
3397 case NOTE_INSN_DELETED
:
3398 case NOTE_INSN_DELETED_LABEL
:
3399 case NOTE_INSN_DELETED_DEBUG_LABEL
:
3402 reorder_insns (insn
, insn
, last_insn
);
3409 /* Locate or create a label for a given basic block. */
3412 label_for_bb (basic_block bb
)
3414 rtx label
= BB_HEAD (bb
);
3416 if (!LABEL_P (label
))
3419 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
3421 label
= block_label (bb
);
3427 /* Locate the effective beginning and end of the insn chain for each
3428 block, as defined by skip_insns_after_block above. */
3431 record_effective_endpoints (void)
3437 for (insn
= get_insns ();
3440 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
;
3441 insn
= NEXT_INSN (insn
))
3443 /* No basic blocks at all? */
3446 if (PREV_INSN (insn
))
3447 cfg_layout_function_header
=
3448 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
3450 cfg_layout_function_header
= NULL_RTX
;
3452 next_insn
= get_insns ();
3453 FOR_EACH_BB_FN (bb
, cfun
)
3457 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
3458 SET_BB_HEADER (bb
) = unlink_insn_chain (next_insn
,
3459 PREV_INSN (BB_HEAD (bb
)));
3460 end
= skip_insns_after_block (bb
);
3461 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
3462 SET_BB_FOOTER (bb
) = unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
3463 next_insn
= NEXT_INSN (BB_END (bb
));
3466 cfg_layout_function_footer
= next_insn
;
3467 if (cfg_layout_function_footer
)
3468 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
3473 const pass_data pass_data_into_cfg_layout_mode
=
3475 RTL_PASS
, /* type */
3476 "into_cfglayout", /* name */
3477 OPTGROUP_NONE
, /* optinfo_flags */
3479 0, /* properties_required */
3480 PROP_cfglayout
, /* properties_provided */
3481 0, /* properties_destroyed */
3482 0, /* todo_flags_start */
3483 0, /* todo_flags_finish */
3486 class pass_into_cfg_layout_mode
: public rtl_opt_pass
3489 pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3490 : rtl_opt_pass (pass_data_into_cfg_layout_mode
, ctxt
)
3493 /* opt_pass methods: */
3494 virtual unsigned int execute (function
*)
3496 cfg_layout_initialize (0);
3500 }; // class pass_into_cfg_layout_mode
3505 make_pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3507 return new pass_into_cfg_layout_mode (ctxt
);
3512 const pass_data pass_data_outof_cfg_layout_mode
=
3514 RTL_PASS
, /* type */
3515 "outof_cfglayout", /* name */
3516 OPTGROUP_NONE
, /* optinfo_flags */
3518 0, /* properties_required */
3519 0, /* properties_provided */
3520 PROP_cfglayout
, /* properties_destroyed */
3521 0, /* todo_flags_start */
3522 0, /* todo_flags_finish */
3525 class pass_outof_cfg_layout_mode
: public rtl_opt_pass
3528 pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3529 : rtl_opt_pass (pass_data_outof_cfg_layout_mode
, ctxt
)
3532 /* opt_pass methods: */
3533 virtual unsigned int execute (function
*);
3535 }; // class pass_outof_cfg_layout_mode
3538 pass_outof_cfg_layout_mode::execute (function
*fun
)
3542 FOR_EACH_BB_FN (bb
, fun
)
3543 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3544 bb
->aux
= bb
->next_bb
;
3546 cfg_layout_finalize ();
3554 make_pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3556 return new pass_outof_cfg_layout_mode (ctxt
);
3560 /* Link the basic blocks in the correct order, compacting the basic
3561 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3562 function also clears the basic block header and footer fields.
3564 This function is usually called after a pass (e.g. tracer) finishes
3565 some transformations while in cfglayout mode. The required sequence
3566 of the basic blocks is in a linked list along the bb->aux field.
3567 This functions re-links the basic block prev_bb and next_bb pointers
3568 accordingly, and it compacts and renumbers the blocks.
3570 FIXME: This currently works only for RTL, but the only RTL-specific
3571 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3572 to GIMPLE a long time ago, but it doesn't relink the basic block
3573 chain. It could do that (to give better initial RTL) if this function
3574 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3577 relink_block_chain (bool stay_in_cfglayout_mode
)
3579 basic_block bb
, prev_bb
;
3582 /* Maybe dump the re-ordered sequence. */
3585 fprintf (dump_file
, "Reordered sequence:\n");
3586 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, index
=
3589 bb
= (basic_block
) bb
->aux
, index
++)
3591 fprintf (dump_file
, " %i ", index
);
3592 if (get_bb_original (bb
))
3593 fprintf (dump_file
, "duplicate of %i ",
3594 get_bb_original (bb
)->index
);
3595 else if (forwarder_block_p (bb
)
3596 && !LABEL_P (BB_HEAD (bb
)))
3597 fprintf (dump_file
, "compensation ");
3599 fprintf (dump_file
, "bb %i ", bb
->index
);
3600 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
3604 /* Now reorder the blocks. */
3605 prev_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
3606 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
3607 for (; bb
; prev_bb
= bb
, bb
= (basic_block
) bb
->aux
)
3609 bb
->prev_bb
= prev_bb
;
3610 prev_bb
->next_bb
= bb
;
3612 prev_bb
->next_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
3613 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
= prev_bb
;
3615 /* Then, clean up the aux fields. */
3616 FOR_ALL_BB_FN (bb
, cfun
)
3619 if (!stay_in_cfglayout_mode
)
3620 SET_BB_HEADER (bb
) = SET_BB_FOOTER (bb
) = NULL
;
3623 /* Maybe reset the original copy tables, they are not valid anymore
3624 when we renumber the basic blocks in compact_blocks. If we are
3625 are going out of cfglayout mode, don't re-allocate the tables. */
3626 free_original_copy_tables ();
3627 if (stay_in_cfglayout_mode
)
3628 initialize_original_copy_tables ();
3630 /* Finally, put basic_block_info in the new order. */
3635 /* Given a reorder chain, rearrange the code to match. */
3638 fixup_reorder_chain (void)
3643 if (cfg_layout_function_header
)
3645 set_first_insn (cfg_layout_function_header
);
3646 insn
= cfg_layout_function_header
;
3647 while (NEXT_INSN (insn
))
3648 insn
= NEXT_INSN (insn
);
3651 /* First do the bulk reordering -- rechain the blocks without regard to
3652 the needed changes to jumps and labels. */
3654 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3660 SET_NEXT_INSN (insn
) = BB_HEADER (bb
);
3662 set_first_insn (BB_HEADER (bb
));
3663 SET_PREV_INSN (BB_HEADER (bb
)) = insn
;
3664 insn
= BB_HEADER (bb
);
3665 while (NEXT_INSN (insn
))
3666 insn
= NEXT_INSN (insn
);
3669 SET_NEXT_INSN (insn
) = BB_HEAD (bb
);
3671 set_first_insn (BB_HEAD (bb
));
3672 SET_PREV_INSN (BB_HEAD (bb
)) = insn
;
3676 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
3677 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
3678 while (NEXT_INSN (insn
))
3679 insn
= NEXT_INSN (insn
);
3683 SET_NEXT_INSN (insn
) = cfg_layout_function_footer
;
3684 if (cfg_layout_function_footer
)
3685 SET_PREV_INSN (cfg_layout_function_footer
) = insn
;
3687 while (NEXT_INSN (insn
))
3688 insn
= NEXT_INSN (insn
);
3690 set_last_insn (insn
);
3691 #ifdef ENABLE_CHECKING
3692 verify_insn_chain ();
3695 /* Now add jumps and labels as needed to match the blocks new
3698 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3701 edge e_fall
, e_taken
, e
;
3703 rtx ret_label
= NULL_RTX
;
3707 if (EDGE_COUNT (bb
->succs
) == 0)
3710 /* Find the old fallthru edge, and another non-EH edge for
3712 e_taken
= e_fall
= NULL
;
3714 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3715 if (e
->flags
& EDGE_FALLTHRU
)
3717 else if (! (e
->flags
& EDGE_EH
))
3720 bb_end_insn
= BB_END (bb
);
3721 if (JUMP_P (bb_end_insn
))
3723 ret_label
= JUMP_LABEL (bb_end_insn
);
3724 if (any_condjump_p (bb_end_insn
))
3726 /* This might happen if the conditional jump has side
3727 effects and could therefore not be optimized away.
3728 Make the basic block to end with a barrier in order
3729 to prevent rtl_verify_flow_info from complaining. */
3732 gcc_assert (!onlyjump_p (bb_end_insn
)
3733 || returnjump_p (bb_end_insn
)
3734 || (e_taken
->flags
& EDGE_CROSSING
));
3735 emit_barrier_after (bb_end_insn
);
3739 /* If the old fallthru is still next, nothing to do. */
3740 if (bb
->aux
== e_fall
->dest
3741 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3744 /* The degenerated case of conditional jump jumping to the next
3745 instruction can happen for jumps with side effects. We need
3746 to construct a forwarder block and this will be done just
3747 fine by force_nonfallthru below. */
3751 /* There is another special case: if *neither* block is next,
3752 such as happens at the very end of a function, then we'll
3753 need to add a new unconditional jump. Choose the taken
3754 edge based on known or assumed probability. */
3755 else if (bb
->aux
!= e_taken
->dest
)
3757 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
3760 && XINT (note
, 0) < REG_BR_PROB_BASE
/ 2
3761 && invert_jump (bb_end_insn
,
3763 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3765 : label_for_bb (e_fall
->dest
)), 0))
3767 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3768 gcc_checking_assert (could_fall_through
3769 (e_taken
->src
, e_taken
->dest
));
3770 e_taken
->flags
|= EDGE_FALLTHRU
;
3771 update_br_prob_note (bb
);
3772 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
3776 /* If the "jumping" edge is a crossing edge, and the fall
3777 through edge is non-crossing, leave things as they are. */
3778 else if ((e_taken
->flags
& EDGE_CROSSING
)
3779 && !(e_fall
->flags
& EDGE_CROSSING
))
3782 /* Otherwise we can try to invert the jump. This will
3783 basically never fail, however, keep up the pretense. */
3784 else if (invert_jump (bb_end_insn
,
3786 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3788 : label_for_bb (e_fall
->dest
)), 0))
3790 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3791 gcc_checking_assert (could_fall_through
3792 (e_taken
->src
, e_taken
->dest
));
3793 e_taken
->flags
|= EDGE_FALLTHRU
;
3794 update_br_prob_note (bb
);
3795 if (LABEL_NUSES (ret_label
) == 0
3796 && single_pred_p (e_taken
->dest
))
3797 delete_insn (ret_label
);
3801 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
3803 /* If the old fallthru is still next or if
3804 asm goto doesn't have a fallthru (e.g. when followed by
3805 __builtin_unreachable ()), nothing to do. */
3807 || bb
->aux
== e_fall
->dest
3808 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3811 /* Otherwise we'll have to use the fallthru fixup below. */
3815 /* Otherwise we have some return, switch or computed
3816 jump. In the 99% case, there should not have been a
3818 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
3824 /* No fallthru implies a noreturn function with EH edges, or
3825 something similarly bizarre. In any case, we don't need to
3830 /* If the fallthru block is still next, nothing to do. */
3831 if (bb
->aux
== e_fall
->dest
)
3834 /* A fallthru to exit block. */
3835 if (e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3839 /* We got here if we need to add a new jump insn.
3840 Note force_nonfallthru can delete E_FALL and thus we have to
3841 save E_FALL->src prior to the call to force_nonfallthru. */
3842 nb
= force_nonfallthru_and_redirect (e_fall
, e_fall
->dest
, ret_label
);
3847 /* Don't process this new block. */
3852 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3854 /* Annoying special case - jump around dead jumptables left in the code. */
3855 FOR_EACH_BB_FN (bb
, cfun
)
3857 edge e
= find_fallthru_edge (bb
->succs
);
3859 if (e
&& !can_fallthru (e
->src
, e
->dest
))
3860 force_nonfallthru (e
);
3863 /* Ensure goto_locus from edges has some instructions with that locus
3866 FOR_EACH_BB_FN (bb
, cfun
)
3871 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3872 if (LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
3873 && !(e
->flags
& EDGE_ABNORMAL
))
3877 basic_block dest
, nb
;
3880 insn
= BB_END (e
->src
);
3881 end
= PREV_INSN (BB_HEAD (e
->src
));
3883 && (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
3884 insn
= PREV_INSN (insn
);
3886 && INSN_LOCATION (insn
) == e
->goto_locus
)
3888 if (simplejump_p (BB_END (e
->src
))
3889 && !INSN_HAS_LOCATION (BB_END (e
->src
)))
3891 INSN_LOCATION (BB_END (e
->src
)) = e
->goto_locus
;
3895 if (dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3897 /* Non-fallthru edges to the exit block cannot be split. */
3898 if (!(e
->flags
& EDGE_FALLTHRU
))
3903 insn
= BB_HEAD (dest
);
3904 end
= NEXT_INSN (BB_END (dest
));
3905 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
3906 insn
= NEXT_INSN (insn
);
3907 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
3908 && INSN_LOCATION (insn
) == e
->goto_locus
)
3911 nb
= split_edge (e
);
3912 if (!INSN_P (BB_END (nb
)))
3913 SET_BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
3915 INSN_LOCATION (BB_END (nb
)) = e
->goto_locus
;
3917 /* If there are other incoming edges to the destination block
3918 with the same goto locus, redirect them to the new block as
3919 well, this can prevent other such blocks from being created
3920 in subsequent iterations of the loop. */
3921 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
3922 if (LOCATION_LOCUS (e2
->goto_locus
) != UNKNOWN_LOCATION
3923 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
3924 && e
->goto_locus
== e2
->goto_locus
)
3925 redirect_edge_and_branch (e2
, nb
);
3932 /* Perform sanity checks on the insn chain.
3933 1. Check that next/prev pointers are consistent in both the forward and
3935 2. Count insns in chain, going both directions, and check if equal.
3936 3. Check that get_last_insn () returns the actual end of chain. */
3939 verify_insn_chain (void)
3941 rtx x
, prevx
, nextx
;
3942 int insn_cnt1
, insn_cnt2
;
3944 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
3946 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
3947 gcc_assert (PREV_INSN (x
) == prevx
);
3949 gcc_assert (prevx
== get_last_insn ());
3951 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
3953 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
3954 gcc_assert (NEXT_INSN (x
) == nextx
);
3956 gcc_assert (insn_cnt1
== insn_cnt2
);
3959 /* If we have assembler epilogues, the block falling through to exit must
3960 be the last one in the reordered chain when we reach final. Ensure
3961 that this condition is met. */
3963 fixup_fallthru_exit_predecessor (void)
3966 basic_block bb
= NULL
;
3968 /* This transformation is not valid before reload, because we might
3969 separate a call from the instruction that copies the return
3971 gcc_assert (reload_completed
);
3973 e
= find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
3979 basic_block c
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
3981 /* If the very first block is the one with the fall-through exit
3982 edge, we have to split that block. */
3985 bb
= split_block (bb
, NULL
)->dest
;
3988 SET_BB_FOOTER (bb
) = BB_FOOTER (c
);
3989 SET_BB_FOOTER (c
) = NULL
;
3992 while (c
->aux
!= bb
)
3993 c
= (basic_block
) c
->aux
;
3997 c
= (basic_block
) c
->aux
;
4004 /* In case there are more than one fallthru predecessors of exit, force that
4005 there is only one. */
4008 force_one_exit_fallthru (void)
4010 edge e
, predecessor
= NULL
;
4013 basic_block forwarder
, bb
;
4015 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
4016 if (e
->flags
& EDGE_FALLTHRU
)
4018 if (predecessor
== NULL
)
4030 /* Exit has several fallthru predecessors. Create a forwarder block for
4032 forwarder
= split_edge (predecessor
);
4033 for (ei
= ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4034 (e
= ei_safe_edge (ei
)); )
4036 if (e
->src
== forwarder
4037 || !(e
->flags
& EDGE_FALLTHRU
))
4040 redirect_edge_and_branch_force (e
, forwarder
);
4043 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4045 FOR_EACH_BB_FN (bb
, cfun
)
4047 if (bb
->aux
== NULL
&& bb
!= forwarder
)
4049 bb
->aux
= forwarder
;
4055 /* Return true in case it is possible to duplicate the basic block BB. */
4058 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
4060 /* Do not attempt to duplicate tablejumps, as we need to unshare
4061 the dispatch table. This is difficult to do, as the instructions
4062 computing jump destination may be hoisted outside the basic block. */
4063 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
4066 /* Do not duplicate blocks containing insns that can't be copied. */
4067 if (targetm
.cannot_copy_insn_p
)
4069 rtx insn
= BB_HEAD (bb
);
4072 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
4074 if (insn
== BB_END (bb
))
4076 insn
= NEXT_INSN (insn
);
4084 duplicate_insn_chain (rtx from
, rtx to
)
4086 rtx insn
, next
, copy
;
4089 /* Avoid updating of boundaries of previous basic block. The
4090 note will get removed from insn stream in fixup. */
4091 last
= emit_note (NOTE_INSN_DELETED
);
4093 /* Create copy at the end of INSN chain. The chain will
4094 be reordered later. */
4095 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
4097 switch (GET_CODE (insn
))
4100 /* Don't duplicate label debug insns. */
4101 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
)
4107 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
4108 if (JUMP_P (insn
) && JUMP_LABEL (insn
) != NULL_RTX
4109 && ANY_RETURN_P (JUMP_LABEL (insn
)))
4110 JUMP_LABEL (copy
) = JUMP_LABEL (insn
);
4111 maybe_copy_prologue_epilogue_insn (insn
, copy
);
4114 case JUMP_TABLE_DATA
:
4115 /* Avoid copying of dispatch tables. We never duplicate
4116 tablejumps, so this can hit only in case the table got
4117 moved far from original jump.
4118 Avoid copying following barrier as well if any
4119 (and debug insns in between). */
4120 for (next
= NEXT_INSN (insn
);
4121 next
!= NEXT_INSN (to
);
4122 next
= NEXT_INSN (next
))
4123 if (!DEBUG_INSN_P (next
))
4125 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
4137 switch (NOTE_KIND (insn
))
4139 /* In case prologue is empty and function contain label
4140 in first BB, we may want to copy the block. */
4141 case NOTE_INSN_PROLOGUE_END
:
4143 case NOTE_INSN_DELETED
:
4144 case NOTE_INSN_DELETED_LABEL
:
4145 case NOTE_INSN_DELETED_DEBUG_LABEL
:
4146 /* No problem to strip these. */
4147 case NOTE_INSN_FUNCTION_BEG
:
4148 /* There is always just single entry to function. */
4149 case NOTE_INSN_BASIC_BLOCK
:
4150 /* We should only switch text sections once. */
4151 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
4154 case NOTE_INSN_EPILOGUE_BEG
:
4155 emit_note_copy (as_a
<rtx_note
*> (insn
));
4159 /* All other notes should have already been eliminated. */
4167 insn
= NEXT_INSN (last
);
4169 return safe_as_a
<rtx_insn
*> (insn
);
4172 /* Create a duplicate of the basic block BB. */
4175 cfg_layout_duplicate_bb (basic_block bb
)
4180 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
4181 new_bb
= create_basic_block (insn
,
4182 insn
? get_last_insn () : NULL
,
4183 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
);
4185 BB_COPY_PARTITION (new_bb
, bb
);
4188 insn
= BB_HEADER (bb
);
4189 while (NEXT_INSN (insn
))
4190 insn
= NEXT_INSN (insn
);
4191 insn
= duplicate_insn_chain (BB_HEADER (bb
), insn
);
4193 SET_BB_HEADER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4198 insn
= BB_FOOTER (bb
);
4199 while (NEXT_INSN (insn
))
4200 insn
= NEXT_INSN (insn
);
4201 insn
= duplicate_insn_chain (BB_FOOTER (bb
), insn
);
4203 SET_BB_FOOTER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4210 /* Main entry point to this module - initialize the datastructures for
4211 CFG layout changes. It keeps LOOPS up-to-date if not null.
4213 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4216 cfg_layout_initialize (unsigned int flags
)
4221 /* Once bb partitioning is complete, cfg layout mode should not be
4222 re-entered. Entering cfg layout mode may require fixups. As an
4223 example, if edge forwarding performed when optimizing the cfg
4224 layout required moving a block from the hot to the cold
4225 section. This would create an illegal partitioning unless some
4226 manual fixup was performed. */
4227 gcc_assert (!(crtl
->bb_reorder_complete
4228 && flag_reorder_blocks_and_partition
));
4230 initialize_original_copy_tables ();
4232 cfg_layout_rtl_register_cfg_hooks ();
4234 record_effective_endpoints ();
4236 /* Make sure that the targets of non local gotos are marked. */
4237 for (x
= nonlocal_goto_handler_labels
; x
; x
= XEXP (x
, 1))
4239 bb
= BLOCK_FOR_INSN (XEXP (x
, 0));
4240 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
4243 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
4246 /* Splits superblocks. */
4248 break_superblocks (void)
4250 sbitmap superblocks
;
4254 superblocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
4255 bitmap_clear (superblocks
);
4257 FOR_EACH_BB_FN (bb
, cfun
)
4258 if (bb
->flags
& BB_SUPERBLOCK
)
4260 bb
->flags
&= ~BB_SUPERBLOCK
;
4261 bitmap_set_bit (superblocks
, bb
->index
);
4267 rebuild_jump_labels (get_insns ());
4268 find_many_sub_basic_blocks (superblocks
);
4274 /* Finalize the changes: reorder insn list according to the sequence specified
4275 by aux pointers, enter compensation code, rebuild scope forest. */
4278 cfg_layout_finalize (void)
4280 #ifdef ENABLE_CHECKING
4281 verify_flow_info ();
4283 force_one_exit_fallthru ();
4284 rtl_register_cfg_hooks ();
4285 if (reload_completed
4286 #ifdef HAVE_epilogue
4290 fixup_fallthru_exit_predecessor ();
4291 fixup_reorder_chain ();
4293 rebuild_jump_labels (get_insns ());
4294 delete_dead_jumptables ();
4296 #ifdef ENABLE_CHECKING
4297 verify_insn_chain ();
4298 verify_flow_info ();
4303 /* Same as split_block but update cfg_layout structures. */
4306 cfg_layout_split_block (basic_block bb
, void *insnp
)
4308 rtx insn
= (rtx
) insnp
;
4309 basic_block new_bb
= rtl_split_block (bb
, insn
);
4311 SET_BB_FOOTER (new_bb
) = BB_FOOTER (bb
);
4312 SET_BB_FOOTER (bb
) = NULL
;
4317 /* Redirect Edge to DEST. */
4319 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
4321 basic_block src
= e
->src
;
4324 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4327 if (e
->dest
== dest
)
4330 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4331 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
4333 df_set_bb_dirty (src
);
4337 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4338 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
4341 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
4342 e
->src
->index
, dest
->index
);
4344 df_set_bb_dirty (e
->src
);
4345 redirect_edge_succ (e
, dest
);
4349 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4350 in the case the basic block appears to be in sequence. Avoid this
4353 if (e
->flags
& EDGE_FALLTHRU
)
4355 /* Redirect any branch edges unified with the fallthru one. */
4356 if (JUMP_P (BB_END (src
))
4357 && label_is_jump_target_p (BB_HEAD (e
->dest
),
4363 fprintf (dump_file
, "Fallthru edge unified with branch "
4364 "%i->%i redirected to %i\n",
4365 e
->src
->index
, e
->dest
->index
, dest
->index
);
4366 e
->flags
&= ~EDGE_FALLTHRU
;
4367 redirected
= redirect_branch_edge (e
, dest
);
4368 gcc_assert (redirected
);
4369 redirected
->flags
|= EDGE_FALLTHRU
;
4370 df_set_bb_dirty (redirected
->src
);
4373 /* In case we are redirecting fallthru edge to the branch edge
4374 of conditional jump, remove it. */
4375 if (EDGE_COUNT (src
->succs
) == 2)
4377 /* Find the edge that is different from E. */
4378 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
4381 && any_condjump_p (BB_END (src
))
4382 && onlyjump_p (BB_END (src
)))
4383 delete_insn (BB_END (src
));
4386 fprintf (dump_file
, "Redirecting fallthru edge %i->%i to %i\n",
4387 e
->src
->index
, e
->dest
->index
, dest
->index
);
4388 ret
= redirect_edge_succ_nodup (e
, dest
);
4391 ret
= redirect_branch_edge (e
, dest
);
4393 /* We don't want simplejumps in the insn stream during cfglayout. */
4394 gcc_assert (!simplejump_p (BB_END (src
)));
4396 df_set_bb_dirty (src
);
4400 /* Simple wrapper as we always can redirect fallthru edges. */
4402 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
4404 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
4406 gcc_assert (redirected
);
4410 /* Same as delete_basic_block but update cfg_layout structures. */
4413 cfg_layout_delete_block (basic_block bb
)
4415 rtx insn
, next
, prev
= PREV_INSN (BB_HEAD (bb
)), *to
, remaints
;
4419 next
= BB_HEAD (bb
);
4421 SET_NEXT_INSN (prev
) = BB_HEADER (bb
);
4423 set_first_insn (BB_HEADER (bb
));
4424 SET_PREV_INSN (BB_HEADER (bb
)) = prev
;
4425 insn
= BB_HEADER (bb
);
4426 while (NEXT_INSN (insn
))
4427 insn
= NEXT_INSN (insn
);
4428 SET_NEXT_INSN (insn
) = next
;
4429 SET_PREV_INSN (next
) = insn
;
4431 next
= NEXT_INSN (BB_END (bb
));
4434 insn
= BB_FOOTER (bb
);
4437 if (BARRIER_P (insn
))
4439 if (PREV_INSN (insn
))
4440 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
4442 SET_BB_FOOTER (bb
) = NEXT_INSN (insn
);
4443 if (NEXT_INSN (insn
))
4444 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
4448 insn
= NEXT_INSN (insn
);
4453 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
4454 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
4455 while (NEXT_INSN (insn
))
4456 insn
= NEXT_INSN (insn
);
4457 SET_NEXT_INSN (insn
) = next
;
4459 SET_PREV_INSN (next
) = insn
;
4461 set_last_insn (insn
);
4464 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
4465 to
= &SET_BB_HEADER (bb
->next_bb
);
4467 to
= &cfg_layout_function_footer
;
4469 rtl_delete_block (bb
);
4472 prev
= NEXT_INSN (prev
);
4474 prev
= get_insns ();
4476 next
= PREV_INSN (next
);
4478 next
= get_last_insn ();
4480 if (next
&& NEXT_INSN (next
) != prev
)
4482 remaints
= unlink_insn_chain (prev
, next
);
4484 while (NEXT_INSN (insn
))
4485 insn
= NEXT_INSN (insn
);
4486 SET_NEXT_INSN (insn
) = *to
;
4488 SET_PREV_INSN (*to
) = insn
;
4493 /* Return true when blocks A and B can be safely merged. */
4496 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
4498 /* If we are partitioning hot/cold basic blocks, we don't want to
4499 mess up unconditional or indirect jumps that cross between hot
4502 Basic block partitioning may result in some jumps that appear to
4503 be optimizable (or blocks that appear to be mergeable), but which really
4504 must be left untouched (they are required to make it safely across
4505 partition boundaries). See the comments at the top of
4506 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4508 if (BB_PARTITION (a
) != BB_PARTITION (b
))
4511 /* Protect the loop latches. */
4512 if (current_loops
&& b
->loop_father
->latch
== b
)
4515 /* If we would end up moving B's instructions, make sure it doesn't fall
4516 through into the exit block, since we cannot recover from a fallthrough
4517 edge into the exit block occurring in the middle of a function. */
4518 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4520 edge e
= find_fallthru_edge (b
->succs
);
4521 if (e
&& e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4525 /* There must be exactly one edge in between the blocks. */
4526 return (single_succ_p (a
)
4527 && single_succ (a
) == b
4528 && single_pred_p (b
) == 1
4530 /* Must be simple edge. */
4531 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
4532 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4533 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
4534 /* If the jump insn has side effects, we can't kill the edge.
4535 When not optimizing, try_redirect_by_replacing_jump will
4536 not allow us to redirect an edge by replacing a table jump. */
4537 && (!JUMP_P (BB_END (a
))
4538 || ((!optimize
|| reload_completed
)
4539 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
4542 /* Merge block A and B. The blocks must be mergeable. */
4545 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
4547 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
4550 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a
, b
));
4553 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
4556 /* If there was a CODE_LABEL beginning B, delete it. */
4557 if (LABEL_P (BB_HEAD (b
)))
4559 delete_insn (BB_HEAD (b
));
4562 /* We should have fallthru edge in a, or we can do dummy redirection to get
4564 if (JUMP_P (BB_END (a
)))
4565 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
4566 gcc_assert (!JUMP_P (BB_END (a
)));
4568 /* When not optimizing and the edge is the only place in RTL which holds
4569 some unique locus, emit a nop with that locus in between. */
4571 emit_nop_for_unique_locus_between (a
, b
);
4573 /* Move things from b->footer after a->footer. */
4577 SET_BB_FOOTER (a
) = SET_BB_FOOTER (b
);
4580 rtx last
= BB_FOOTER (a
);
4582 while (NEXT_INSN (last
))
4583 last
= NEXT_INSN (last
);
4584 SET_NEXT_INSN (last
) = BB_FOOTER (b
);
4585 SET_PREV_INSN (BB_FOOTER (b
)) = last
;
4587 SET_BB_FOOTER (b
) = NULL
;
4590 /* Move things from b->header before a->footer.
4591 Note that this may include dead tablejump data, but we don't clean
4592 those up until we go out of cfglayout mode. */
4595 if (! BB_FOOTER (a
))
4596 SET_BB_FOOTER (a
) = BB_HEADER (b
);
4599 rtx last
= BB_HEADER (b
);
4601 while (NEXT_INSN (last
))
4602 last
= NEXT_INSN (last
);
4603 SET_NEXT_INSN (last
) = BB_FOOTER (a
);
4604 SET_PREV_INSN (BB_FOOTER (a
)) = last
;
4605 SET_BB_FOOTER (a
) = BB_HEADER (b
);
4607 SET_BB_HEADER (b
) = NULL
;
4610 /* In the case basic blocks are not adjacent, move them around. */
4611 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4613 insn
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
4615 emit_insn_after_noloc (insn
, BB_END (a
), a
);
4617 /* Otherwise just re-associate the instructions. */
4621 SET_BB_END (a
) = BB_END (b
);
4624 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4625 We need to explicitly call. */
4626 update_bb_for_insn_chain (insn
, BB_END (b
), a
);
4628 /* Skip possible DELETED_LABEL insn. */
4629 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
4630 insn
= NEXT_INSN (insn
);
4631 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4632 SET_BB_HEAD (b
) = SET_BB_END (b
) = NULL
;
4635 df_bb_delete (b
->index
);
4637 /* If B was a forwarder block, propagate the locus on the edge. */
4639 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
4640 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
4643 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
4649 cfg_layout_split_edge (edge e
)
4651 basic_block new_bb
=
4652 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4653 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
4656 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4657 BB_COPY_PARTITION (new_bb
, e
->src
);
4659 BB_COPY_PARTITION (new_bb
, e
->dest
);
4660 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
4661 redirect_edge_and_branch_force (e
, new_bb
);
4666 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4669 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
4673 /* Return true if BB contains only labels or non-executable
4677 rtl_block_empty_p (basic_block bb
)
4681 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4682 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4685 FOR_BB_INSNS (bb
, insn
)
4686 if (NONDEBUG_INSN_P (insn
) && !any_uncondjump_p (insn
))
4692 /* Split a basic block if it ends with a conditional branch and if
4693 the other part of the block is not empty. */
4696 rtl_split_block_before_cond_jump (basic_block bb
)
4699 rtx split_point
= NULL
;
4701 bool found_code
= false;
4703 FOR_BB_INSNS (bb
, insn
)
4705 if (any_condjump_p (insn
))
4707 else if (NONDEBUG_INSN_P (insn
))
4712 /* Did not find everything. */
4713 if (found_code
&& split_point
)
4714 return split_block (bb
, split_point
)->dest
;
4719 /* Return 1 if BB ends with a call, possibly followed by some
4720 instructions that must stay with the call, 0 otherwise. */
4723 rtl_block_ends_with_call_p (basic_block bb
)
4725 rtx insn
= BB_END (bb
);
4727 while (!CALL_P (insn
)
4728 && insn
!= BB_HEAD (bb
)
4729 && (keep_with_call_p (insn
)
4731 || DEBUG_INSN_P (insn
)))
4732 insn
= PREV_INSN (insn
);
4733 return (CALL_P (insn
));
4736 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4739 rtl_block_ends_with_condjump_p (const_basic_block bb
)
4741 return any_condjump_p (BB_END (bb
));
4744 /* Return true if we need to add fake edge to exit.
4745 Helper function for rtl_flow_call_edges_add. */
4748 need_fake_edge_p (const_rtx insn
)
4754 && !SIBLING_CALL_P (insn
)
4755 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
4756 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
4759 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
4760 && MEM_VOLATILE_P (PATTERN (insn
)))
4761 || (GET_CODE (PATTERN (insn
)) == PARALLEL
4762 && asm_noperands (insn
) != -1
4763 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
4764 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
4767 /* Add fake edges to the function exit for any non constant and non noreturn
4768 calls, volatile inline assembly in the bitmap of blocks specified by
4769 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4772 The goal is to expose cases in which entering a basic block does not imply
4773 that all subsequent instructions must be executed. */
4776 rtl_flow_call_edges_add (sbitmap blocks
)
4779 int blocks_split
= 0;
4780 int last_bb
= last_basic_block_for_fn (cfun
);
4781 bool check_last_block
= false;
4783 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
4787 check_last_block
= true;
4789 check_last_block
= bitmap_bit_p (blocks
,
4790 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
->index
);
4792 /* In the last basic block, before epilogue generation, there will be
4793 a fallthru edge to EXIT. Special care is required if the last insn
4794 of the last basic block is a call because make_edge folds duplicate
4795 edges, which would result in the fallthru edge also being marked
4796 fake, which would result in the fallthru edge being removed by
4797 remove_fake_edges, which would result in an invalid CFG.
4799 Moreover, we can't elide the outgoing fake edge, since the block
4800 profiler needs to take this into account in order to solve the minimal
4801 spanning tree in the case that the call doesn't return.
4803 Handle this by adding a dummy instruction in a new last basic block. */
4804 if (check_last_block
)
4806 basic_block bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
4807 rtx insn
= BB_END (bb
);
4809 /* Back up past insns that must be kept in the same block as a call. */
4810 while (insn
!= BB_HEAD (bb
)
4811 && keep_with_call_p (insn
))
4812 insn
= PREV_INSN (insn
);
4814 if (need_fake_edge_p (insn
))
4818 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4821 insert_insn_on_edge (gen_use (const0_rtx
), e
);
4822 commit_edge_insertions ();
4827 /* Now add fake edges to the function exit for any non constant
4828 calls since there is no way that we can determine if they will
4831 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
4833 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
4840 if (blocks
&& !bitmap_bit_p (blocks
, i
))
4843 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
4845 prev_insn
= PREV_INSN (insn
);
4846 if (need_fake_edge_p (insn
))
4849 rtx split_at_insn
= insn
;
4851 /* Don't split the block between a call and an insn that should
4852 remain in the same block as the call. */
4854 while (split_at_insn
!= BB_END (bb
)
4855 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
4856 split_at_insn
= NEXT_INSN (split_at_insn
);
4858 /* The handling above of the final block before the epilogue
4859 should be enough to verify that there is no edge to the exit
4860 block in CFG already. Calling make_edge in such case would
4861 cause us to mark that edge as fake and remove it later. */
4863 #ifdef ENABLE_CHECKING
4864 if (split_at_insn
== BB_END (bb
))
4866 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4867 gcc_assert (e
== NULL
);
4871 /* Note that the following may create a new basic block
4872 and renumber the existing basic blocks. */
4873 if (split_at_insn
!= BB_END (bb
))
4875 e
= split_block (bb
, split_at_insn
);
4880 make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
4883 if (insn
== BB_HEAD (bb
))
4889 verify_flow_info ();
4891 return blocks_split
;
4894 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4895 the conditional branch target, SECOND_HEAD should be the fall-thru
4896 there is no need to handle this here the loop versioning code handles
4897 this. the reason for SECON_HEAD is that it is needed for condition
4898 in trees, and this should be of the same type since it is a hook. */
4900 rtl_lv_add_condition_to_bb (basic_block first_head
,
4901 basic_block second_head ATTRIBUTE_UNUSED
,
4902 basic_block cond_bb
, void *comp_rtx
)
4904 rtx label
, seq
, jump
;
4905 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
4906 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
4907 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
4908 enum machine_mode mode
;
4911 label
= block_label (first_head
);
4912 mode
= GET_MODE (op0
);
4913 if (mode
== VOIDmode
)
4914 mode
= GET_MODE (op1
);
4917 op0
= force_operand (op0
, NULL_RTX
);
4918 op1
= force_operand (op1
, NULL_RTX
);
4919 do_compare_rtx_and_jump (op0
, op1
, comp
, 0,
4920 mode
, NULL_RTX
, NULL_RTX
, label
, -1);
4921 jump
= get_last_insn ();
4922 JUMP_LABEL (jump
) = label
;
4923 LABEL_NUSES (label
)++;
4927 /* Add the new cond , in the new head. */
4928 emit_insn_after (seq
, BB_END (cond_bb
));
4932 /* Given a block B with unconditional branch at its end, get the
4933 store the return the branch edge and the fall-thru edge in
4934 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4936 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
4937 edge
*fallthru_edge
)
4939 edge e
= EDGE_SUCC (b
, 0);
4941 if (e
->flags
& EDGE_FALLTHRU
)
4944 *branch_edge
= EDGE_SUCC (b
, 1);
4949 *fallthru_edge
= EDGE_SUCC (b
, 1);
4954 init_rtl_bb_info (basic_block bb
)
4956 gcc_assert (!bb
->il
.x
.rtl
);
4957 bb
->il
.x
.head_
= NULL
;
4958 bb
->il
.x
.rtl
= ggc_cleared_alloc
<rtl_bb_info
> ();
4961 /* Returns true if it is possible to remove edge E by redirecting
4962 it to the destination of the other edge from E->src. */
4965 rtl_can_remove_branch_p (const_edge e
)
4967 const_basic_block src
= e
->src
;
4968 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
4969 const_rtx insn
= BB_END (src
), set
;
4971 /* The conditions are taken from try_redirect_by_replacing_jump. */
4972 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4975 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4978 if (BB_PARTITION (src
) != BB_PARTITION (target
))
4981 if (!onlyjump_p (insn
)
4982 || tablejump_p (insn
, NULL
, NULL
))
4985 set
= single_set (insn
);
4986 if (!set
|| side_effects_p (set
))
4993 rtl_duplicate_bb (basic_block bb
)
4995 bb
= cfg_layout_duplicate_bb (bb
);
5000 /* Do book-keeping of basic block BB for the profile consistency checker.
5001 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
5002 then do post-pass accounting. Store the counting in RECORD. */
5004 rtl_account_profile_record (basic_block bb
, int after_pass
,
5005 struct profile_record
*record
)
5008 FOR_BB_INSNS (bb
, insn
)
5011 record
->size
[after_pass
]
5012 += insn_rtx_cost (PATTERN (insn
), false);
5013 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
5014 record
->time
[after_pass
]
5015 += insn_rtx_cost (PATTERN (insn
), true) * bb
->count
;
5016 else if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
5017 record
->time
[after_pass
]
5018 += insn_rtx_cost (PATTERN (insn
), true) * bb
->frequency
;
5022 /* Implementation of CFG manipulation for linearized RTL. */
5023 struct cfg_hooks rtl_cfg_hooks
= {
5025 rtl_verify_flow_info
,
5027 rtl_dump_bb_for_graph
,
5028 rtl_create_basic_block
,
5029 rtl_redirect_edge_and_branch
,
5030 rtl_redirect_edge_and_branch_force
,
5031 rtl_can_remove_branch_p
,
5034 rtl_move_block_after
,
5035 rtl_can_merge_blocks
, /* can_merge_blocks_p */
5039 cfg_layout_can_duplicate_bb_p
,
5042 rtl_make_forwarder_block
,
5043 rtl_tidy_fallthru_edge
,
5044 rtl_force_nonfallthru
,
5045 rtl_block_ends_with_call_p
,
5046 rtl_block_ends_with_condjump_p
,
5047 rtl_flow_call_edges_add
,
5048 NULL
, /* execute_on_growing_pred */
5049 NULL
, /* execute_on_shrinking_pred */
5050 NULL
, /* duplicate loop for trees */
5051 NULL
, /* lv_add_condition_to_bb */
5052 NULL
, /* lv_adjust_loop_header_phi*/
5053 NULL
, /* extract_cond_bb_edges */
5054 NULL
, /* flush_pending_stmts */
5055 rtl_block_empty_p
, /* block_empty_p */
5056 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5057 rtl_account_profile_record
,
5060 /* Implementation of CFG manipulation for cfg layout RTL, where
5061 basic block connected via fallthru edges does not have to be adjacent.
5062 This representation will hopefully become the default one in future
5063 version of the compiler. */
5065 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
5067 rtl_verify_flow_info_1
,
5069 rtl_dump_bb_for_graph
,
5070 cfg_layout_create_basic_block
,
5071 cfg_layout_redirect_edge_and_branch
,
5072 cfg_layout_redirect_edge_and_branch_force
,
5073 rtl_can_remove_branch_p
,
5074 cfg_layout_delete_block
,
5075 cfg_layout_split_block
,
5076 rtl_move_block_after
,
5077 cfg_layout_can_merge_blocks_p
,
5078 cfg_layout_merge_blocks
,
5081 cfg_layout_can_duplicate_bb_p
,
5082 cfg_layout_duplicate_bb
,
5083 cfg_layout_split_edge
,
5084 rtl_make_forwarder_block
,
5085 NULL
, /* tidy_fallthru_edge */
5086 rtl_force_nonfallthru
,
5087 rtl_block_ends_with_call_p
,
5088 rtl_block_ends_with_condjump_p
,
5089 rtl_flow_call_edges_add
,
5090 NULL
, /* execute_on_growing_pred */
5091 NULL
, /* execute_on_shrinking_pred */
5092 duplicate_loop_to_header_edge
, /* duplicate loop for trees */
5093 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
5094 NULL
, /* lv_adjust_loop_header_phi*/
5095 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
5096 NULL
, /* flush_pending_stmts */
5097 rtl_block_empty_p
, /* block_empty_p */
5098 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5099 rtl_account_profile_record
,
5102 /* BB_HEAD as an rvalue. */
5104 rtx_insn
*BB_HEAD (const_basic_block bb
)
5106 rtx insn
= bb
->il
.x
.head_
;
5107 return safe_as_a
<rtx_insn
*> (insn
);
5110 /* BB_HEAD for use as an lvalue. */
5112 rtx
& SET_BB_HEAD (basic_block bb
)
5114 return bb
->il
.x
.head_
;
5117 /* BB_END as an rvalue. */
5119 rtx_insn
*BB_END (const_basic_block bb
)
5121 rtx insn
= bb
->il
.x
.rtl
->end_
;
5122 return safe_as_a
<rtx_insn
*> (insn
);
5125 /* BB_END as an lvalue. */
5127 rtx
& SET_BB_END (basic_block bb
)
5129 return bb
->il
.x
.rtl
->end_
;
5132 /* BB_HEADER as an rvalue. */
5134 rtx_insn
*BB_HEADER (const_basic_block bb
)
5136 rtx insn
= bb
->il
.x
.rtl
->header_
;
5137 return safe_as_a
<rtx_insn
*> (insn
);
5140 /* BB_HEADER as an lvalue. */
5142 rtx
& SET_BB_HEADER (basic_block bb
)
5144 return bb
->il
.x
.rtl
->header_
;
5147 /* BB_FOOTER as an rvalue. */
5149 rtx_insn
*BB_FOOTER (const_basic_block bb
)
5151 rtx insn
= bb
->il
.x
.rtl
->footer_
;
5152 return safe_as_a
<rtx_insn
*> (insn
);
5155 /* BB_FOOTER as an lvalue. */
5157 rtx
& SET_BB_FOOTER (basic_block bb
)
5159 return bb
->il
.x
.rtl
->footer_
;
5162 #include "gt-cfgrtl.h"