1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2015 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"
51 #include "hard-reg-set.h"
55 #include "dominance.h"
60 #include "cfgcleanup.h"
61 #include "basic-block.h"
62 #include "bb-reorder.h"
66 #include "rtl-error.h"
69 #include "insn-attr.h"
70 #include "insn-config.h"
72 #include "statistics.h"
82 #include "common/common-target.h"
85 #include "tree-pass.h"
88 /* Holds the interesting leading and trailing notes for the function.
89 Only applicable if the CFG is in cfglayout mode. */
90 static GTY(()) rtx_insn
*cfg_layout_function_footer
;
91 static GTY(()) rtx_insn
*cfg_layout_function_header
;
93 static rtx_insn
*skip_insns_after_block (basic_block
);
94 static void record_effective_endpoints (void);
95 static rtx
label_for_bb (basic_block
);
96 static void fixup_reorder_chain (void);
98 void verify_insn_chain (void);
99 static void fixup_fallthru_exit_predecessor (void);
100 static int can_delete_note_p (const rtx_note
*);
101 static int can_delete_label_p (const rtx_code_label
*);
102 static basic_block
rtl_split_edge (edge
);
103 static bool rtl_move_block_after (basic_block
, basic_block
);
104 static int rtl_verify_flow_info (void);
105 static basic_block
cfg_layout_split_block (basic_block
, void *);
106 static edge
cfg_layout_redirect_edge_and_branch (edge
, basic_block
);
107 static basic_block
cfg_layout_redirect_edge_and_branch_force (edge
, basic_block
);
108 static void cfg_layout_delete_block (basic_block
);
109 static void rtl_delete_block (basic_block
);
110 static basic_block
rtl_redirect_edge_and_branch_force (edge
, basic_block
);
111 static edge
rtl_redirect_edge_and_branch (edge
, basic_block
);
112 static basic_block
rtl_split_block (basic_block
, void *);
113 static void rtl_dump_bb (FILE *, basic_block
, int, int);
114 static int rtl_verify_flow_info_1 (void);
115 static void rtl_make_forwarder_block (edge
);
117 /* Return true if NOTE is not one of the ones that must be kept paired,
118 so that we may simply delete it. */
121 can_delete_note_p (const rtx_note
*note
)
123 switch (NOTE_KIND (note
))
125 case NOTE_INSN_DELETED
:
126 case NOTE_INSN_BASIC_BLOCK
:
127 case NOTE_INSN_EPILOGUE_BEG
:
135 /* True if a given label can be deleted. */
138 can_delete_label_p (const rtx_code_label
*label
)
140 return (!LABEL_PRESERVE_P (label
)
141 /* User declared labels must be preserved. */
142 && LABEL_NAME (label
) == 0
143 && !in_insn_list_p (forced_labels
, label
));
146 /* Delete INSN by patching it out. */
149 delete_insn (rtx uncast_insn
)
151 rtx_insn
*insn
= as_a
<rtx_insn
*> (uncast_insn
);
153 bool really_delete
= true;
157 /* Some labels can't be directly removed from the INSN chain, as they
158 might be references via variables, constant pool etc.
159 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
160 if (! can_delete_label_p (as_a
<rtx_code_label
*> (insn
)))
162 const char *name
= LABEL_NAME (insn
);
163 basic_block bb
= BLOCK_FOR_INSN (insn
);
164 rtx_insn
*bb_note
= NEXT_INSN (insn
);
166 really_delete
= false;
167 PUT_CODE (insn
, NOTE
);
168 NOTE_KIND (insn
) = NOTE_INSN_DELETED_LABEL
;
169 NOTE_DELETED_LABEL_NAME (insn
) = name
;
171 /* If the note following the label starts a basic block, and the
172 label is a member of the same basic block, interchange the two. */
173 if (bb_note
!= NULL_RTX
174 && NOTE_INSN_BASIC_BLOCK_P (bb_note
)
176 && bb
== BLOCK_FOR_INSN (bb_note
))
178 reorder_insns_nobb (insn
, insn
, bb_note
);
179 BB_HEAD (bb
) = bb_note
;
180 if (BB_END (bb
) == bb_note
)
185 remove_node_from_insn_list (insn
, &nonlocal_goto_handler_labels
);
190 /* If this insn has already been deleted, something is very wrong. */
191 gcc_assert (!insn
->deleted ());
193 df_insn_delete (insn
);
195 insn
->set_deleted ();
198 /* If deleting a jump, decrement the use count of the label. Deleting
199 the label itself should happen in the normal course of block merging. */
202 if (JUMP_LABEL (insn
)
203 && LABEL_P (JUMP_LABEL (insn
)))
204 LABEL_NUSES (JUMP_LABEL (insn
))--;
206 /* If there are more targets, remove them too. */
208 = find_reg_note (insn
, REG_LABEL_TARGET
, NULL_RTX
)) != NULL_RTX
209 && LABEL_P (XEXP (note
, 0)))
211 LABEL_NUSES (XEXP (note
, 0))--;
212 remove_note (insn
, note
);
216 /* Also if deleting any insn that references a label as an operand. */
217 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, NULL_RTX
)) != NULL_RTX
218 && LABEL_P (XEXP (note
, 0)))
220 LABEL_NUSES (XEXP (note
, 0))--;
221 remove_note (insn
, note
);
224 if (rtx_jump_table_data
*table
= dyn_cast
<rtx_jump_table_data
*> (insn
))
226 rtvec vec
= table
->get_labels ();
227 int len
= GET_NUM_ELEM (vec
);
230 for (i
= 0; i
< len
; i
++)
232 rtx label
= XEXP (RTVEC_ELT (vec
, i
), 0);
234 /* When deleting code in bulk (e.g. removing many unreachable
235 blocks) we can delete a label that's a target of the vector
236 before deleting the vector itself. */
238 LABEL_NUSES (label
)--;
243 /* Like delete_insn but also purge dead edges from BB. */
246 delete_insn_and_edges (rtx_insn
*insn
)
251 && BLOCK_FOR_INSN (insn
)
252 && BB_END (BLOCK_FOR_INSN (insn
)) == insn
)
256 purge_dead_edges (BLOCK_FOR_INSN (insn
));
259 /* Unlink a chain of insns between START and FINISH, leaving notes
260 that must be paired. If CLEAR_BB is true, we set bb field for
261 insns that cannot be removed to NULL. */
264 delete_insn_chain (rtx start
, rtx finish
, bool clear_bb
)
266 rtx_insn
*prev
, *current
;
268 /* Unchain the insns one by one. It would be quicker to delete all of these
269 with a single unchaining, rather than one at a time, but we need to keep
271 current
= safe_as_a
<rtx_insn
*> (finish
);
274 prev
= PREV_INSN (current
);
275 if (NOTE_P (current
) && !can_delete_note_p (as_a
<rtx_note
*> (current
)))
278 delete_insn (current
);
280 if (clear_bb
&& !current
->deleted ())
281 set_block_for_insn (current
, NULL
);
283 if (current
== start
)
289 /* Create a new basic block consisting of the instructions between HEAD and END
290 inclusive. This function is designed to allow fast BB construction - reuses
291 the note and basic block struct in BB_NOTE, if any and do not grow
292 BASIC_BLOCK chain and should be used directly only by CFG construction code.
293 END can be NULL in to create new empty basic block before HEAD. Both END
294 and HEAD can be NULL to create basic block at the end of INSN chain.
295 AFTER is the basic block we should be put after. */
298 create_basic_block_structure (rtx_insn
*head
, rtx_insn
*end
, rtx_note
*bb_note
,
304 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
307 /* If we found an existing note, thread it back onto the chain. */
315 after
= PREV_INSN (head
);
319 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
320 reorder_insns_nobb (bb_note
, bb_note
, after
);
324 /* Otherwise we must create a note and a basic block structure. */
328 init_rtl_bb_info (bb
);
331 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
332 else if (LABEL_P (head
) && end
)
334 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
340 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
346 NOTE_BASIC_BLOCK (bb_note
) = bb
;
349 /* Always include the bb note in the block. */
350 if (NEXT_INSN (end
) == bb_note
)
355 bb
->index
= last_basic_block_for_fn (cfun
)++;
356 bb
->flags
= BB_NEW
| BB_RTL
;
357 link_block (bb
, after
);
358 SET_BASIC_BLOCK_FOR_FN (cfun
, bb
->index
, bb
);
359 df_bb_refs_record (bb
->index
, false);
360 update_bb_for_insn (bb
);
361 BB_SET_PARTITION (bb
, BB_UNPARTITIONED
);
363 /* Tag the block so that we know it has been used when considering
364 other basic block notes. */
370 /* Create new basic block consisting of instructions in between HEAD and END
371 and place it to the BB chain after block AFTER. END can be NULL to
372 create a new empty basic block before HEAD. Both END and HEAD can be
373 NULL to create basic block at the end of INSN chain. */
376 rtl_create_basic_block (void *headp
, void *endp
, basic_block after
)
378 rtx_insn
*head
= (rtx_insn
*) headp
;
379 rtx_insn
*end
= (rtx_insn
*) endp
;
382 /* Grow the basic block array if needed. */
383 if ((size_t) last_basic_block_for_fn (cfun
)
384 >= basic_block_info_for_fn (cfun
)->length ())
387 (last_basic_block_for_fn (cfun
)
388 + (last_basic_block_for_fn (cfun
) + 3) / 4);
389 vec_safe_grow_cleared (basic_block_info_for_fn (cfun
), new_size
);
392 n_basic_blocks_for_fn (cfun
)++;
394 bb
= create_basic_block_structure (head
, end
, NULL
, after
);
400 cfg_layout_create_basic_block (void *head
, void *end
, basic_block after
)
402 basic_block newbb
= rtl_create_basic_block (head
, end
, after
);
407 /* Delete the insns in a (non-live) block. We physically delete every
408 non-deleted-note insn, and update the flow graph appropriately.
410 Return nonzero if we deleted an exception handler. */
412 /* ??? Preserving all such notes strikes me as wrong. It would be nice
413 to post-process the stream to remove empty blocks, loops, ranges, etc. */
416 rtl_delete_block (basic_block b
)
418 rtx_insn
*insn
, *end
;
420 /* If the head of this block is a CODE_LABEL, then it might be the
421 label for an exception handler which can't be reached. We need
422 to remove the label from the exception_handler_label list. */
425 end
= get_last_bb_insn (b
);
427 /* Selectively delete the entire chain. */
429 delete_insn_chain (insn
, end
, true);
433 fprintf (dump_file
, "deleting block %d\n", b
->index
);
434 df_bb_delete (b
->index
);
437 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
440 compute_bb_for_insn (void)
444 FOR_EACH_BB_FN (bb
, cfun
)
446 rtx_insn
*end
= BB_END (bb
);
449 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
451 BLOCK_FOR_INSN (insn
) = bb
;
458 /* Release the basic_block_for_insn array. */
461 free_bb_for_insn (void)
464 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
465 if (!BARRIER_P (insn
))
466 BLOCK_FOR_INSN (insn
) = NULL
;
472 const pass_data pass_data_free_cfg
=
475 "*free_cfg", /* name */
476 OPTGROUP_NONE
, /* optinfo_flags */
478 0, /* properties_required */
479 0, /* properties_provided */
480 PROP_cfg
, /* properties_destroyed */
481 0, /* todo_flags_start */
482 0, /* todo_flags_finish */
485 class pass_free_cfg
: public rtl_opt_pass
488 pass_free_cfg (gcc::context
*ctxt
)
489 : rtl_opt_pass (pass_data_free_cfg
, ctxt
)
492 /* opt_pass methods: */
493 virtual unsigned int execute (function
*);
495 }; // class pass_free_cfg
498 pass_free_cfg::execute (function
*)
501 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
502 valid at that point so it would be too late to call df_analyze. */
503 if (optimize
> 0 && flag_delayed_branch
)
505 df_note_add_problem ();
510 if (crtl
->has_bb_partition
)
511 insert_section_boundary_note ();
520 make_pass_free_cfg (gcc::context
*ctxt
)
522 return new pass_free_cfg (ctxt
);
525 /* Return RTX to emit after when we want to emit code on the entry of function. */
527 entry_of_function (void)
529 return (n_basic_blocks_for_fn (cfun
) > NUM_FIXED_BLOCKS
?
530 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
) : get_insns ());
533 /* Emit INSN at the entry point of the function, ensuring that it is only
534 executed once per function. */
536 emit_insn_at_entry (rtx insn
)
538 edge_iterator ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
539 edge e
= ei_safe_edge (ei
);
540 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
542 insert_insn_on_edge (insn
, e
);
543 commit_edge_insertions ();
546 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
547 (or BARRIER if found) and notify df of the bb change.
548 The insn chain range is inclusive
549 (i.e. both BEGIN and END will be updated. */
552 update_bb_for_insn_chain (rtx_insn
*begin
, rtx_insn
*end
, basic_block bb
)
556 end
= NEXT_INSN (end
);
557 for (insn
= begin
; insn
!= end
; insn
= NEXT_INSN (insn
))
558 if (!BARRIER_P (insn
))
559 df_insn_change_bb (insn
, bb
);
562 /* Update BLOCK_FOR_INSN of insns in BB to BB,
563 and notify df of the change. */
566 update_bb_for_insn (basic_block bb
)
568 update_bb_for_insn_chain (BB_HEAD (bb
), BB_END (bb
), bb
);
572 /* Like active_insn_p, except keep the return value clobber around
573 even after reload. */
576 flow_active_insn_p (const rtx_insn
*insn
)
578 if (active_insn_p (insn
))
581 /* A clobber of the function return value exists for buggy
582 programs that fail to return a value. Its effect is to
583 keep the return value from being live across the entire
584 function. If we allow it to be skipped, we introduce the
585 possibility for register lifetime confusion. */
586 if (GET_CODE (PATTERN (insn
)) == CLOBBER
587 && REG_P (XEXP (PATTERN (insn
), 0))
588 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn
), 0)))
594 /* Return true if the block has no effect and only forwards control flow to
595 its single destination. */
598 contains_no_active_insn_p (const_basic_block bb
)
602 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
603 || !single_succ_p (bb
))
606 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
607 if (INSN_P (insn
) && flow_active_insn_p (insn
))
610 return (!INSN_P (insn
)
611 || (JUMP_P (insn
) && simplejump_p (insn
))
612 || !flow_active_insn_p (insn
));
615 /* Likewise, but protect loop latches, headers and preheaders. */
616 /* FIXME: Make this a cfg hook. */
619 forwarder_block_p (const_basic_block bb
)
621 if (!contains_no_active_insn_p (bb
))
624 /* Protect loop latches, headers and preheaders. */
628 if (bb
->loop_father
->header
== bb
)
630 dest
= EDGE_SUCC (bb
, 0)->dest
;
631 if (dest
->loop_father
->header
== dest
)
638 /* Return nonzero if we can reach target from src by falling through. */
639 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
642 can_fallthru (basic_block src
, basic_block target
)
644 rtx_insn
*insn
= BB_END (src
);
649 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
651 if (src
->next_bb
!= target
)
654 /* ??? Later we may add code to move jump tables offline. */
655 if (tablejump_p (insn
, NULL
, NULL
))
658 FOR_EACH_EDGE (e
, ei
, src
->succs
)
659 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
660 && e
->flags
& EDGE_FALLTHRU
)
663 insn2
= BB_HEAD (target
);
664 if (!active_insn_p (insn2
))
665 insn2
= next_active_insn (insn2
);
667 return next_active_insn (insn
) == insn2
;
670 /* Return nonzero if we could reach target from src by falling through,
671 if the target was made adjacent. If we already have a fall-through
672 edge to the exit block, we can't do that. */
674 could_fall_through (basic_block src
, basic_block target
)
679 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
681 FOR_EACH_EDGE (e
, ei
, src
->succs
)
682 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
683 && e
->flags
& EDGE_FALLTHRU
)
688 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
690 bb_note (basic_block bb
)
696 note
= NEXT_INSN (note
);
698 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
699 return as_a
<rtx_note
*> (note
);
702 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
703 note associated with the BLOCK. */
706 first_insn_after_basic_block_note (basic_block block
)
710 /* Get the first instruction in the block. */
711 insn
= BB_HEAD (block
);
713 if (insn
== NULL_RTX
)
716 insn
= NEXT_INSN (insn
);
717 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
719 return NEXT_INSN (insn
);
722 /* Creates a new basic block just after basic block BB by splitting
723 everything after specified instruction INSNP. */
726 rtl_split_block (basic_block bb
, void *insnp
)
729 rtx_insn
*insn
= (rtx_insn
*) insnp
;
735 insn
= first_insn_after_basic_block_note (bb
);
739 rtx_insn
*next
= insn
;
741 insn
= PREV_INSN (insn
);
743 /* If the block contains only debug insns, insn would have
744 been NULL in a non-debug compilation, and then we'd end
745 up emitting a DELETED note. For -fcompare-debug
746 stability, emit the note too. */
747 if (insn
!= BB_END (bb
)
748 && DEBUG_INSN_P (next
)
749 && DEBUG_INSN_P (BB_END (bb
)))
751 while (next
!= BB_END (bb
) && DEBUG_INSN_P (next
))
752 next
= NEXT_INSN (next
);
754 if (next
== BB_END (bb
))
755 emit_note_after (NOTE_INSN_DELETED
, next
);
759 insn
= get_last_insn ();
762 /* We probably should check type of the insn so that we do not create
763 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
765 if (insn
== BB_END (bb
))
766 emit_note_after (NOTE_INSN_DELETED
, insn
);
768 /* Create the new basic block. */
769 new_bb
= create_basic_block (NEXT_INSN (insn
), BB_END (bb
), bb
);
770 BB_COPY_PARTITION (new_bb
, bb
);
773 /* Redirect the outgoing edges. */
774 new_bb
->succs
= bb
->succs
;
776 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
779 /* The new block starts off being dirty. */
780 df_set_bb_dirty (bb
);
784 /* Return true if the single edge between blocks A and B is the only place
785 in RTL which holds some unique locus. */
788 unique_locus_on_edge_between_p (basic_block a
, basic_block b
)
790 const location_t goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
791 rtx_insn
*insn
, *end
;
793 if (LOCATION_LOCUS (goto_locus
) == UNKNOWN_LOCATION
)
796 /* First scan block A backward. */
798 end
= PREV_INSN (BB_HEAD (a
));
799 while (insn
!= end
&& (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
800 insn
= PREV_INSN (insn
);
802 if (insn
!= end
&& INSN_LOCATION (insn
) == goto_locus
)
805 /* Then scan block B forward. */
809 end
= NEXT_INSN (BB_END (b
));
810 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
811 insn
= NEXT_INSN (insn
);
813 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
814 && INSN_LOCATION (insn
) == goto_locus
)
821 /* If the single edge between blocks A and B is the only place in RTL which
822 holds some unique locus, emit a nop with that locus between the blocks. */
825 emit_nop_for_unique_locus_between (basic_block a
, basic_block b
)
827 if (!unique_locus_on_edge_between_p (a
, b
))
830 BB_END (a
) = emit_insn_after_noloc (gen_nop (), BB_END (a
), a
);
831 INSN_LOCATION (BB_END (a
)) = EDGE_SUCC (a
, 0)->goto_locus
;
834 /* Blocks A and B are to be merged into a single block A. The insns
835 are already contiguous. */
838 rtl_merge_blocks (basic_block a
, basic_block b
)
840 rtx_insn
*b_head
= BB_HEAD (b
), *b_end
= BB_END (b
), *a_end
= BB_END (a
);
841 rtx_insn
*del_first
= NULL
, *del_last
= NULL
;
842 rtx_insn
*b_debug_start
= b_end
, *b_debug_end
= b_end
;
843 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
847 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
850 while (DEBUG_INSN_P (b_end
))
851 b_end
= PREV_INSN (b_debug_start
= b_end
);
853 /* If there was a CODE_LABEL beginning B, delete it. */
854 if (LABEL_P (b_head
))
856 /* Detect basic blocks with nothing but a label. This can happen
857 in particular at the end of a function. */
861 del_first
= del_last
= b_head
;
862 b_head
= NEXT_INSN (b_head
);
865 /* Delete the basic block note and handle blocks containing just that
867 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
875 b_head
= NEXT_INSN (b_head
);
878 /* If there was a jump out of A, delete it. */
883 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
885 || NOTE_INSN_BASIC_BLOCK_P (prev
)
886 || prev
== BB_HEAD (a
))
891 /* If this was a conditional jump, we need to also delete
892 the insn that set cc0. */
893 if (HAVE_cc0
&& only_sets_cc0_p (prev
))
895 rtx_insn
*tmp
= prev
;
897 prev
= prev_nonnote_insn (prev
);
903 a_end
= PREV_INSN (del_first
);
905 else if (BARRIER_P (NEXT_INSN (a_end
)))
906 del_first
= NEXT_INSN (a_end
);
908 /* Delete everything marked above as well as crap that might be
909 hanging out between the two blocks. */
911 BB_HEAD (b
) = b_empty
? NULL
: b_head
;
912 delete_insn_chain (del_first
, del_last
, true);
914 /* When not optimizing and the edge is the only place in RTL which holds
915 some unique locus, emit a nop with that locus in between. */
918 emit_nop_for_unique_locus_between (a
, b
);
922 /* Reassociate the insns of B with A. */
925 update_bb_for_insn_chain (a_end
, b_debug_end
, a
);
927 BB_END (a
) = b_debug_end
;
930 else if (b_end
!= b_debug_end
)
932 /* Move any deleted labels and other notes between the end of A
933 and the debug insns that make up B after the debug insns,
934 bringing the debug insns into A while keeping the notes after
936 if (NEXT_INSN (a_end
) != b_debug_start
)
937 reorder_insns_nobb (NEXT_INSN (a_end
), PREV_INSN (b_debug_start
),
939 update_bb_for_insn_chain (b_debug_start
, b_debug_end
, a
);
940 BB_END (a
) = b_debug_end
;
943 df_bb_delete (b
->index
);
945 /* If B was a forwarder block, propagate the locus on the edge. */
947 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
948 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
951 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
955 /* Return true when block A and B can be merged. */
958 rtl_can_merge_blocks (basic_block a
, basic_block b
)
960 /* If we are partitioning hot/cold basic blocks, we don't want to
961 mess up unconditional or indirect jumps that cross between hot
964 Basic block partitioning may result in some jumps that appear to
965 be optimizable (or blocks that appear to be mergeable), but which really
966 must be left untouched (they are required to make it safely across
967 partition boundaries). See the comments at the top of
968 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
970 if (BB_PARTITION (a
) != BB_PARTITION (b
))
973 /* Protect the loop latches. */
974 if (current_loops
&& b
->loop_father
->latch
== b
)
977 /* There must be exactly one edge in between the blocks. */
978 return (single_succ_p (a
)
979 && single_succ (a
) == b
982 /* Must be simple edge. */
983 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
985 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
986 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
987 /* If the jump insn has side effects,
988 we can't kill the edge. */
989 && (!JUMP_P (BB_END (a
))
991 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
994 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
998 block_label (basic_block block
)
1000 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1003 if (!LABEL_P (BB_HEAD (block
)))
1005 BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
1008 return as_a
<rtx_code_label
*> (BB_HEAD (block
));
1011 /* Attempt to perform edge redirection by replacing possibly complex jump
1012 instruction by unconditional jump or removing jump completely. This can
1013 apply only if all edges now point to the same block. The parameters and
1014 return values are equivalent to redirect_edge_and_branch. */
1017 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
1019 basic_block src
= e
->src
;
1020 rtx_insn
*insn
= BB_END (src
), *kill_from
;
1024 /* If we are partitioning hot/cold basic blocks, we don't want to
1025 mess up unconditional or indirect jumps that cross between hot
1028 Basic block partitioning may result in some jumps that appear to
1029 be optimizable (or blocks that appear to be mergeable), but which really
1030 must be left untouched (they are required to make it safely across
1031 partition boundaries). See the comments at the top of
1032 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1034 if (BB_PARTITION (src
) != BB_PARTITION (target
))
1037 /* We can replace or remove a complex jump only when we have exactly
1038 two edges. Also, if we have exactly one outgoing edge, we can
1040 if (EDGE_COUNT (src
->succs
) >= 3
1041 /* Verify that all targets will be TARGET. Specifically, the
1042 edge that is not E must also go to TARGET. */
1043 || (EDGE_COUNT (src
->succs
) == 2
1044 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
1047 if (!onlyjump_p (insn
))
1049 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
1052 /* Avoid removing branch with side effects. */
1053 set
= single_set (insn
);
1054 if (!set
|| side_effects_p (set
))
1057 /* In case we zap a conditional jump, we'll need to kill
1058 the cc0 setter too. */
1060 if (HAVE_cc0
&& reg_mentioned_p (cc0_rtx
, PATTERN (insn
))
1061 && only_sets_cc0_p (PREV_INSN (insn
)))
1062 kill_from
= PREV_INSN (insn
);
1064 /* See if we can create the fallthru edge. */
1065 if (in_cfglayout
|| can_fallthru (src
, target
))
1068 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
1071 /* Selectively unlink whole insn chain. */
1074 rtx_insn
*insn
= BB_FOOTER (src
);
1076 delete_insn_chain (kill_from
, BB_END (src
), false);
1078 /* Remove barriers but keep jumptables. */
1081 if (BARRIER_P (insn
))
1083 if (PREV_INSN (insn
))
1084 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1086 BB_FOOTER (src
) = NEXT_INSN (insn
);
1087 if (NEXT_INSN (insn
))
1088 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1092 insn
= NEXT_INSN (insn
);
1096 delete_insn_chain (kill_from
, PREV_INSN (BB_HEAD (target
)),
1100 /* If this already is simplejump, redirect it. */
1101 else if (simplejump_p (insn
))
1103 if (e
->dest
== target
)
1106 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
1107 INSN_UID (insn
), e
->dest
->index
, target
->index
);
1108 if (!redirect_jump (as_a
<rtx_jump_insn
*> (insn
),
1109 block_label (target
), 0))
1111 gcc_assert (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1116 /* Cannot do anything for target exit block. */
1117 else if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1120 /* Or replace possibly complicated jump insn by simple jump insn. */
1123 rtx target_label
= block_label (target
);
1126 rtx_jump_table_data
*table
;
1128 emit_jump_insn_after_noloc (gen_jump (target_label
), insn
);
1129 JUMP_LABEL (BB_END (src
)) = target_label
;
1130 LABEL_NUSES (target_label
)++;
1132 fprintf (dump_file
, "Replacing insn %i by jump %i\n",
1133 INSN_UID (insn
), INSN_UID (BB_END (src
)));
1136 delete_insn_chain (kill_from
, insn
, false);
1138 /* Recognize a tablejump that we are converting to a
1139 simple jump and remove its associated CODE_LABEL
1140 and ADDR_VEC or ADDR_DIFF_VEC. */
1141 if (tablejump_p (insn
, &label
, &table
))
1142 delete_insn_chain (label
, table
, false);
1144 barrier
= next_nonnote_insn (BB_END (src
));
1145 if (!barrier
|| !BARRIER_P (barrier
))
1146 emit_barrier_after (BB_END (src
));
1149 if (barrier
!= NEXT_INSN (BB_END (src
)))
1151 /* Move the jump before barrier so that the notes
1152 which originally were or were created before jump table are
1153 inside the basic block. */
1154 rtx_insn
*new_insn
= BB_END (src
);
1156 update_bb_for_insn_chain (NEXT_INSN (BB_END (src
)),
1157 PREV_INSN (barrier
), src
);
1159 SET_NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
1160 SET_PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
1162 SET_NEXT_INSN (new_insn
) = barrier
;
1163 SET_NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
1165 SET_PREV_INSN (new_insn
) = PREV_INSN (barrier
);
1166 SET_PREV_INSN (barrier
) = new_insn
;
1171 /* Keep only one edge out and set proper flags. */
1172 if (!single_succ_p (src
))
1174 gcc_assert (single_succ_p (src
));
1176 e
= single_succ_edge (src
);
1178 e
->flags
= EDGE_FALLTHRU
;
1182 e
->probability
= REG_BR_PROB_BASE
;
1183 e
->count
= src
->count
;
1185 if (e
->dest
!= target
)
1186 redirect_edge_succ (e
, target
);
1190 /* Subroutine of redirect_branch_edge that tries to patch the jump
1191 instruction INSN so that it reaches block NEW. Do this
1192 only when it originally reached block OLD. Return true if this
1193 worked or the original target wasn't OLD, return false if redirection
1197 patch_jump_insn (rtx_insn
*insn
, rtx_insn
*old_label
, basic_block new_bb
)
1199 rtx_jump_table_data
*table
;
1201 /* Recognize a tablejump and adjust all matching cases. */
1202 if (tablejump_p (insn
, NULL
, &table
))
1206 rtx new_label
= block_label (new_bb
);
1208 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1210 vec
= table
->get_labels ();
1212 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
1213 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
1215 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
1216 --LABEL_NUSES (old_label
);
1217 ++LABEL_NUSES (new_label
);
1220 /* Handle casesi dispatch insns. */
1221 if ((tmp
= single_set (insn
)) != NULL
1222 && SET_DEST (tmp
) == pc_rtx
1223 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
1224 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
1225 && LABEL_REF_LABEL (XEXP (SET_SRC (tmp
), 2)) == old_label
)
1227 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
1229 --LABEL_NUSES (old_label
);
1230 ++LABEL_NUSES (new_label
);
1233 else if ((tmp
= extract_asm_operands (PATTERN (insn
))) != NULL
)
1235 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (tmp
);
1236 rtx new_label
, note
;
1238 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1240 new_label
= block_label (new_bb
);
1242 for (i
= 0; i
< n
; ++i
)
1244 rtx old_ref
= ASM_OPERANDS_LABEL (tmp
, i
);
1245 gcc_assert (GET_CODE (old_ref
) == LABEL_REF
);
1246 if (XEXP (old_ref
, 0) == old_label
)
1248 ASM_OPERANDS_LABEL (tmp
, i
)
1249 = gen_rtx_LABEL_REF (Pmode
, new_label
);
1250 --LABEL_NUSES (old_label
);
1251 ++LABEL_NUSES (new_label
);
1255 if (JUMP_LABEL (insn
) == old_label
)
1257 JUMP_LABEL (insn
) = new_label
;
1258 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1260 remove_note (insn
, note
);
1264 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1266 remove_note (insn
, note
);
1267 if (JUMP_LABEL (insn
) != new_label
1268 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1269 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1271 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1273 XEXP (note
, 0) = new_label
;
1277 /* ?? We may play the games with moving the named labels from
1278 one basic block to the other in case only one computed_jump is
1280 if (computed_jump_p (insn
)
1281 /* A return instruction can't be redirected. */
1282 || returnjump_p (insn
))
1285 if (!currently_expanding_to_rtl
|| JUMP_LABEL (insn
) == old_label
)
1287 /* If the insn doesn't go where we think, we're confused. */
1288 gcc_assert (JUMP_LABEL (insn
) == old_label
);
1290 /* If the substitution doesn't succeed, die. This can happen
1291 if the back end emitted unrecognizable instructions or if
1292 target is exit block on some arches. */
1293 if (!redirect_jump (as_a
<rtx_jump_insn
*> (insn
),
1294 block_label (new_bb
), 0))
1296 gcc_assert (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1305 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1308 redirect_branch_edge (edge e
, basic_block target
)
1310 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1311 basic_block src
= e
->src
;
1312 rtx_insn
*insn
= BB_END (src
);
1314 /* We can only redirect non-fallthru edges of jump insn. */
1315 if (e
->flags
& EDGE_FALLTHRU
)
1317 else if (!JUMP_P (insn
) && !currently_expanding_to_rtl
)
1320 if (!currently_expanding_to_rtl
)
1322 if (!patch_jump_insn (as_a
<rtx_jump_insn
*> (insn
), old_label
, target
))
1326 /* When expanding this BB might actually contain multiple
1327 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1328 Redirect all of those that match our label. */
1329 FOR_BB_INSNS (src
, insn
)
1330 if (JUMP_P (insn
) && !patch_jump_insn (as_a
<rtx_jump_insn
*> (insn
),
1335 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
1336 e
->src
->index
, e
->dest
->index
, target
->index
);
1338 if (e
->dest
!= target
)
1339 e
= redirect_edge_succ_nodup (e
, target
);
1344 /* Called when edge E has been redirected to a new destination,
1345 in order to update the region crossing flag on the edge and
1349 fixup_partition_crossing (edge e
)
1351 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || e
->dest
1352 == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1354 /* If we redirected an existing edge, it may already be marked
1355 crossing, even though the new src is missing a reg crossing note.
1356 But make sure reg crossing note doesn't already exist before
1358 if (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1360 e
->flags
|= EDGE_CROSSING
;
1361 if (JUMP_P (BB_END (e
->src
))
1362 && !CROSSING_JUMP_P (BB_END (e
->src
)))
1363 CROSSING_JUMP_P (BB_END (e
->src
)) = 1;
1365 else if (BB_PARTITION (e
->src
) == BB_PARTITION (e
->dest
))
1367 e
->flags
&= ~EDGE_CROSSING
;
1368 /* Remove the section crossing note from jump at end of
1369 src if it exists, and if no other successors are
1371 if (JUMP_P (BB_END (e
->src
)) && CROSSING_JUMP_P (BB_END (e
->src
)))
1373 bool has_crossing_succ
= false;
1376 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
1378 has_crossing_succ
|= (e2
->flags
& EDGE_CROSSING
);
1379 if (has_crossing_succ
)
1382 if (!has_crossing_succ
)
1383 CROSSING_JUMP_P (BB_END (e
->src
)) = 0;
1388 /* Called when block BB has been reassigned to the cold partition,
1389 because it is now dominated by another cold block,
1390 to ensure that the region crossing attributes are updated. */
1393 fixup_new_cold_bb (basic_block bb
)
1398 /* This is called when a hot bb is found to now be dominated
1399 by a cold bb and therefore needs to become cold. Therefore,
1400 its preds will no longer be region crossing. Any non-dominating
1401 preds that were previously hot would also have become cold
1402 in the caller for the same region. Any preds that were previously
1403 region-crossing will be adjusted in fixup_partition_crossing. */
1404 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1406 fixup_partition_crossing (e
);
1409 /* Possibly need to make bb's successor edges region crossing,
1410 or remove stale region crossing. */
1411 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1413 /* We can't have fall-through edges across partition boundaries.
1414 Note that force_nonfallthru will do any necessary partition
1415 boundary fixup by calling fixup_partition_crossing itself. */
1416 if ((e
->flags
& EDGE_FALLTHRU
)
1417 && BB_PARTITION (bb
) != BB_PARTITION (e
->dest
)
1418 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1419 force_nonfallthru (e
);
1421 fixup_partition_crossing (e
);
1425 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1426 expense of adding new instructions or reordering basic blocks.
1428 Function can be also called with edge destination equivalent to the TARGET.
1429 Then it should try the simplifications and do nothing if none is possible.
1431 Return edge representing the branch if transformation succeeded. Return NULL
1433 We still return NULL in case E already destinated TARGET and we didn't
1434 managed to simplify instruction stream. */
1437 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
1440 basic_block src
= e
->src
;
1441 basic_block dest
= e
->dest
;
1443 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1449 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
1451 df_set_bb_dirty (src
);
1452 fixup_partition_crossing (ret
);
1456 ret
= redirect_branch_edge (e
, target
);
1460 df_set_bb_dirty (src
);
1461 fixup_partition_crossing (ret
);
1465 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1468 emit_barrier_after_bb (basic_block bb
)
1470 rtx_barrier
*barrier
= emit_barrier_after (BB_END (bb
));
1471 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1472 || current_ir_type () == IR_RTL_CFGLAYOUT
);
1473 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
1475 rtx_insn
*insn
= unlink_insn_chain (barrier
, barrier
);
1479 rtx_insn
*footer_tail
= BB_FOOTER (bb
);
1481 while (NEXT_INSN (footer_tail
))
1482 footer_tail
= NEXT_INSN (footer_tail
);
1483 if (!BARRIER_P (footer_tail
))
1485 SET_NEXT_INSN (footer_tail
) = insn
;
1486 SET_PREV_INSN (insn
) = footer_tail
;
1490 BB_FOOTER (bb
) = insn
;
1494 /* Like force_nonfallthru below, but additionally performs redirection
1495 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1496 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1497 simple_return_rtx, indicating which kind of returnjump to create.
1498 It should be NULL otherwise. */
1501 force_nonfallthru_and_redirect (edge e
, basic_block target
, rtx jump_label
)
1503 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
1506 int abnormal_edge_flags
= 0;
1507 bool asm_goto_edge
= false;
1510 /* In the case the last instruction is conditional jump to the next
1511 instruction, first redirect the jump itself and then continue
1512 by creating a basic block afterwards to redirect fallthru edge. */
1513 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1514 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1515 && any_condjump_p (BB_END (e
->src
))
1516 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1519 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1522 redirected
= redirect_jump (as_a
<rtx_jump_insn
*> (BB_END (e
->src
)),
1523 block_label (target
), 0);
1524 gcc_assert (redirected
);
1526 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1529 int prob
= XINT (note
, 0);
1531 b
->probability
= prob
;
1532 /* Update this to use GCOV_COMPUTE_SCALE. */
1533 b
->count
= e
->count
* prob
/ REG_BR_PROB_BASE
;
1534 e
->probability
-= e
->probability
;
1535 e
->count
-= b
->count
;
1536 if (e
->probability
< 0)
1543 if (e
->flags
& EDGE_ABNORMAL
)
1545 /* Irritating special case - fallthru edge to the same block as abnormal
1547 We can't redirect abnormal edge, but we still can split the fallthru
1548 one and create separate abnormal edge to original destination.
1549 This allows bb-reorder to make such edge non-fallthru. */
1550 gcc_assert (e
->dest
== target
);
1551 abnormal_edge_flags
= e
->flags
& ~EDGE_FALLTHRU
;
1552 e
->flags
&= EDGE_FALLTHRU
;
1556 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1557 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1559 /* We can't redirect the entry block. Create an empty block
1560 at the start of the function which we use to add the new
1566 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
,
1567 ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1569 /* Change the existing edge's source to be the new block, and add
1570 a new edge from the entry block to the new block. */
1572 for (ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
1573 (tmp
= ei_safe_edge (ei
)); )
1577 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
->unordered_remove (ei
.index
);
1587 vec_safe_push (bb
->succs
, e
);
1588 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
,
1593 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1594 don't point to the target or fallthru label. */
1595 if (JUMP_P (BB_END (e
->src
))
1596 && target
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1597 && (e
->flags
& EDGE_FALLTHRU
)
1598 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
1600 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
1601 bool adjust_jump_target
= false;
1603 for (i
= 0; i
< n
; ++i
)
1605 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (e
->dest
))
1607 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))--;
1608 XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) = block_label (target
);
1609 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))++;
1610 adjust_jump_target
= true;
1612 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (target
))
1613 asm_goto_edge
= true;
1615 if (adjust_jump_target
)
1617 rtx_insn
*insn
= BB_END (e
->src
);
1619 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1620 rtx_insn
*new_label
= BB_HEAD (target
);
1622 if (JUMP_LABEL (insn
) == old_label
)
1624 JUMP_LABEL (insn
) = new_label
;
1625 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1627 remove_note (insn
, note
);
1631 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1633 remove_note (insn
, note
);
1634 if (JUMP_LABEL (insn
) != new_label
1635 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1636 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1638 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1640 XEXP (note
, 0) = new_label
;
1644 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
|| asm_goto_edge
)
1647 gcov_type count
= e
->count
;
1648 int probability
= e
->probability
;
1649 /* Create the new structures. */
1651 /* If the old block ended with a tablejump, skip its table
1652 by searching forward from there. Otherwise start searching
1653 forward from the last instruction of the old block. */
1654 rtx_jump_table_data
*table
;
1655 if (tablejump_p (BB_END (e
->src
), NULL
, &table
))
1658 new_head
= BB_END (e
->src
);
1659 new_head
= NEXT_INSN (new_head
);
1661 jump_block
= create_basic_block (new_head
, NULL
, e
->src
);
1662 jump_block
->count
= count
;
1663 jump_block
->frequency
= EDGE_FREQUENCY (e
);
1665 /* Make sure new block ends up in correct hot/cold section. */
1667 BB_COPY_PARTITION (jump_block
, e
->src
);
1670 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1671 new_edge
->probability
= probability
;
1672 new_edge
->count
= count
;
1674 /* Redirect old edge. */
1675 redirect_edge_pred (e
, jump_block
);
1676 e
->probability
= REG_BR_PROB_BASE
;
1678 /* If e->src was previously region crossing, it no longer is
1679 and the reg crossing note should be removed. */
1680 fixup_partition_crossing (new_edge
);
1682 /* If asm goto has any label refs to target's label,
1683 add also edge from asm goto bb to target. */
1686 new_edge
->probability
/= 2;
1687 new_edge
->count
/= 2;
1688 jump_block
->count
/= 2;
1689 jump_block
->frequency
/= 2;
1690 new_edge
= make_edge (new_edge
->src
, target
,
1691 e
->flags
& ~EDGE_FALLTHRU
);
1692 new_edge
->probability
= probability
- probability
/ 2;
1693 new_edge
->count
= count
- count
/ 2;
1696 new_bb
= jump_block
;
1699 jump_block
= e
->src
;
1701 loc
= e
->goto_locus
;
1702 e
->flags
&= ~EDGE_FALLTHRU
;
1703 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1705 if (jump_label
== ret_rtx
)
1710 emit_jump_insn_after_setloc (gen_return (), BB_END (jump_block
), loc
);
1714 gcc_assert (jump_label
== simple_return_rtx
);
1715 if (!HAVE_simple_return
)
1718 emit_jump_insn_after_setloc (gen_simple_return (),
1719 BB_END (jump_block
), loc
);
1721 set_return_jump_label (BB_END (jump_block
));
1725 rtx label
= block_label (target
);
1726 emit_jump_insn_after_setloc (gen_jump (label
), BB_END (jump_block
), loc
);
1727 JUMP_LABEL (BB_END (jump_block
)) = label
;
1728 LABEL_NUSES (label
)++;
1731 /* We might be in cfg layout mode, and if so, the following routine will
1732 insert the barrier correctly. */
1733 emit_barrier_after_bb (jump_block
);
1734 redirect_edge_succ_nodup (e
, target
);
1736 if (abnormal_edge_flags
)
1737 make_edge (src
, target
, abnormal_edge_flags
);
1739 df_mark_solutions_dirty ();
1740 fixup_partition_crossing (e
);
1744 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1745 (and possibly create new basic block) to make edge non-fallthru.
1746 Return newly created BB or NULL if none. */
1749 rtl_force_nonfallthru (edge e
)
1751 return force_nonfallthru_and_redirect (e
, e
->dest
, NULL_RTX
);
1754 /* Redirect edge even at the expense of creating new jump insn or
1755 basic block. Return new basic block if created, NULL otherwise.
1756 Conversion must be possible. */
1759 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1761 if (redirect_edge_and_branch (e
, target
)
1762 || e
->dest
== target
)
1765 /* In case the edge redirection failed, try to force it to be non-fallthru
1766 and redirect newly created simplejump. */
1767 df_set_bb_dirty (e
->src
);
1768 return force_nonfallthru_and_redirect (e
, target
, NULL_RTX
);
1771 /* The given edge should potentially be a fallthru edge. If that is in
1772 fact true, delete the jump and barriers that are in the way. */
1775 rtl_tidy_fallthru_edge (edge e
)
1778 basic_block b
= e
->src
, c
= b
->next_bb
;
1780 /* ??? In a late-running flow pass, other folks may have deleted basic
1781 blocks by nopping out blocks, leaving multiple BARRIERs between here
1782 and the target label. They ought to be chastised and fixed.
1784 We can also wind up with a sequence of undeletable labels between
1785 one block and the next.
1787 So search through a sequence of barriers, labels, and notes for
1788 the head of block C and assert that we really do fall through. */
1790 for (q
= NEXT_INSN (BB_END (b
)); q
!= BB_HEAD (c
); q
= NEXT_INSN (q
))
1794 /* Remove what will soon cease being the jump insn from the source block.
1795 If block B consisted only of this single jump, turn it into a deleted
1800 && (any_uncondjump_p (q
)
1801 || single_succ_p (b
)))
1804 rtx_jump_table_data
*table
;
1806 if (tablejump_p (q
, &label
, &table
))
1808 /* The label is likely mentioned in some instruction before
1809 the tablejump and might not be DCEd, so turn it into
1810 a note instead and move before the tablejump that is going to
1812 const char *name
= LABEL_NAME (label
);
1813 PUT_CODE (label
, NOTE
);
1814 NOTE_KIND (label
) = NOTE_INSN_DELETED_LABEL
;
1815 NOTE_DELETED_LABEL_NAME (label
) = name
;
1816 rtx_insn
*lab
= safe_as_a
<rtx_insn
*> (label
);
1817 reorder_insns (lab
, lab
, PREV_INSN (q
));
1818 delete_insn (table
);
1821 /* If this was a conditional jump, we need to also delete
1822 the insn that set cc0. */
1823 if (HAVE_cc0
&& any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1829 /* Selectively unlink the sequence. */
1830 if (q
!= PREV_INSN (BB_HEAD (c
)))
1831 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1833 e
->flags
|= EDGE_FALLTHRU
;
1836 /* Should move basic block BB after basic block AFTER. NIY. */
1839 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1840 basic_block after ATTRIBUTE_UNUSED
)
1845 /* Locate the last bb in the same partition as START_BB. */
1848 last_bb_in_partition (basic_block start_bb
)
1851 FOR_BB_BETWEEN (bb
, start_bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1853 if (BB_PARTITION (start_bb
) != BB_PARTITION (bb
->next_bb
))
1856 /* Return bb before the exit block. */
1860 /* Split a (typically critical) edge. Return the new block.
1861 The edge must not be abnormal.
1863 ??? The code generally expects to be called on critical edges.
1864 The case of a block ending in an unconditional jump to a
1865 block with multiple predecessors is not handled optimally. */
1868 rtl_split_edge (edge edge_in
)
1870 basic_block bb
, new_bb
;
1873 /* Abnormal edges cannot be split. */
1874 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1876 /* We are going to place the new block in front of edge destination.
1877 Avoid existence of fallthru predecessors. */
1878 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1880 edge e
= find_fallthru_edge (edge_in
->dest
->preds
);
1883 force_nonfallthru (e
);
1886 /* Create the basic block note. */
1887 if (edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1888 before
= BB_HEAD (edge_in
->dest
);
1892 /* If this is a fall through edge to the exit block, the blocks might be
1893 not adjacent, and the right place is after the source. */
1894 if ((edge_in
->flags
& EDGE_FALLTHRU
)
1895 && edge_in
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1897 before
= NEXT_INSN (BB_END (edge_in
->src
));
1898 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1899 BB_COPY_PARTITION (bb
, edge_in
->src
);
1903 if (edge_in
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1905 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1906 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1910 basic_block after
= edge_in
->dest
->prev_bb
;
1911 /* If this is post-bb reordering, and the edge crosses a partition
1912 boundary, the new block needs to be inserted in the bb chain
1913 at the end of the src partition (since we put the new bb into
1914 that partition, see below). Otherwise we may end up creating
1915 an extra partition crossing in the chain, which is illegal.
1916 It can't go after the src, because src may have a fall-through
1917 to a different block. */
1918 if (crtl
->bb_reorder_complete
1919 && (edge_in
->flags
& EDGE_CROSSING
))
1921 after
= last_bb_in_partition (edge_in
->src
);
1922 before
= get_last_bb_insn (after
);
1923 /* The instruction following the last bb in partition should
1924 be a barrier, since it cannot end in a fall-through. */
1925 gcc_checking_assert (BARRIER_P (before
));
1926 before
= NEXT_INSN (before
);
1928 bb
= create_basic_block (before
, NULL
, after
);
1929 /* Put the split bb into the src partition, to avoid creating
1930 a situation where a cold bb dominates a hot bb, in the case
1931 where src is cold and dest is hot. The src will dominate
1932 the new bb (whereas it might not have dominated dest). */
1933 BB_COPY_PARTITION (bb
, edge_in
->src
);
1937 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1939 /* Can't allow a region crossing edge to be fallthrough. */
1940 if (BB_PARTITION (bb
) != BB_PARTITION (edge_in
->dest
)
1941 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1943 new_bb
= force_nonfallthru (single_succ_edge (bb
));
1944 gcc_assert (!new_bb
);
1947 /* For non-fallthru edges, we must adjust the predecessor's
1948 jump instruction to target our new block. */
1949 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1951 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1952 gcc_assert (redirected
);
1956 if (edge_in
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1958 /* For asm goto even splitting of fallthru edge might
1959 need insn patching, as other labels might point to the
1961 rtx_insn
*last
= BB_END (edge_in
->src
);
1964 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1965 && extract_asm_operands (PATTERN (last
)) != NULL_RTX
1966 && patch_jump_insn (last
, before
, bb
))
1967 df_set_bb_dirty (edge_in
->src
);
1969 redirect_edge_succ (edge_in
, bb
);
1975 /* Queue instructions for insertion on an edge between two basic blocks.
1976 The new instructions and basic blocks (if any) will not appear in the
1977 CFG until commit_edge_insertions is called. */
1980 insert_insn_on_edge (rtx pattern
, edge e
)
1982 /* We cannot insert instructions on an abnormal critical edge.
1983 It will be easier to find the culprit if we die now. */
1984 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1986 if (e
->insns
.r
== NULL_RTX
)
1989 push_to_sequence (e
->insns
.r
);
1991 emit_insn (pattern
);
1993 e
->insns
.r
= get_insns ();
1997 /* Update the CFG for the instructions queued on edge E. */
2000 commit_one_edge_insertion (edge e
)
2002 rtx_insn
*before
= NULL
, *after
= NULL
, *insns
, *tmp
, *last
;
2005 /* Pull the insns off the edge now since the edge might go away. */
2009 /* Figure out where to put these insns. If the destination has
2010 one predecessor, insert there. Except for the exit block. */
2011 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2015 /* Get the location correct wrt a code label, and "nice" wrt
2016 a basic block note, and before everything else. */
2019 tmp
= NEXT_INSN (tmp
);
2020 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
2021 tmp
= NEXT_INSN (tmp
);
2022 if (tmp
== BB_HEAD (bb
))
2025 after
= PREV_INSN (tmp
);
2027 after
= get_last_insn ();
2030 /* If the source has one successor and the edge is not abnormal,
2031 insert there. Except for the entry block.
2032 Don't do this if the predecessor ends in a jump other than
2033 unconditional simple jump. E.g. for asm goto that points all
2034 its labels at the fallthru basic block, we can't insert instructions
2035 before the asm goto, as the asm goto can have various of side effects,
2036 and can't emit instructions after the asm goto, as it must end
2038 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
2039 && single_succ_p (e
->src
)
2040 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2041 && (!JUMP_P (BB_END (e
->src
))
2042 || simplejump_p (BB_END (e
->src
))))
2046 /* It is possible to have a non-simple jump here. Consider a target
2047 where some forms of unconditional jumps clobber a register. This
2048 happens on the fr30 for example.
2050 We know this block has a single successor, so we can just emit
2051 the queued insns before the jump. */
2052 if (JUMP_P (BB_END (bb
)))
2053 before
= BB_END (bb
);
2056 /* We'd better be fallthru, or we've lost track of what's what. */
2057 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
2059 after
= BB_END (bb
);
2063 /* Otherwise we must split the edge. */
2066 bb
= split_edge (e
);
2068 /* If E crossed a partition boundary, we needed to make bb end in
2069 a region-crossing jump, even though it was originally fallthru. */
2070 if (JUMP_P (BB_END (bb
)))
2071 before
= BB_END (bb
);
2073 after
= BB_END (bb
);
2076 /* Now that we've found the spot, do the insertion. */
2079 emit_insn_before_noloc (insns
, before
, bb
);
2080 last
= prev_nonnote_insn (before
);
2083 last
= emit_insn_after_noloc (insns
, after
, bb
);
2085 if (returnjump_p (last
))
2087 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2088 This is not currently a problem because this only happens
2089 for the (single) epilogue, which already has a fallthru edge
2092 e
= single_succ_edge (bb
);
2093 gcc_assert (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2094 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
2096 e
->flags
&= ~EDGE_FALLTHRU
;
2097 emit_barrier_after (last
);
2100 delete_insn (before
);
2103 gcc_assert (!JUMP_P (last
));
2106 /* Update the CFG for all queued instructions. */
2109 commit_edge_insertions (void)
2113 /* Optimization passes that invoke this routine can cause hot blocks
2114 previously reached by both hot and cold blocks to become dominated only
2115 by cold blocks. This will cause the verification below to fail,
2116 and lead to now cold code in the hot section. In some cases this
2117 may only be visible after newly unreachable blocks are deleted,
2118 which will be done by fixup_partitions. */
2119 fixup_partitions ();
2121 #ifdef ENABLE_CHECKING
2122 verify_flow_info ();
2125 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
2126 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
2131 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2133 commit_one_edge_insertion (e
);
2138 /* Print out RTL-specific basic block information (live information
2139 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2140 documented in dumpfile.h. */
2143 rtl_dump_bb (FILE *outf
, basic_block bb
, int indent
, int flags
)
2149 s_indent
= (char *) alloca ((size_t) indent
+ 1);
2150 memset (s_indent
, ' ', (size_t) indent
);
2151 s_indent
[indent
] = '\0';
2153 if (df
&& (flags
& TDF_DETAILS
))
2155 df_dump_top (bb
, outf
);
2159 if (bb
->index
!= ENTRY_BLOCK
&& bb
->index
!= EXIT_BLOCK
)
2160 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
)); insn
!= last
;
2161 insn
= NEXT_INSN (insn
))
2163 if (flags
& TDF_DETAILS
)
2164 df_dump_insn_top (insn
, outf
);
2165 if (! (flags
& TDF_SLIM
))
2166 print_rtl_single (outf
, insn
);
2168 dump_insn_slim (outf
, insn
);
2169 if (flags
& TDF_DETAILS
)
2170 df_dump_insn_bottom (insn
, outf
);
2173 if (df
&& (flags
& TDF_DETAILS
))
2175 df_dump_bottom (bb
, outf
);
2181 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2182 for the start of each basic block. FLAGS are the TDF_* masks documented
2186 print_rtl_with_bb (FILE *outf
, const rtx_insn
*rtx_first
, int flags
)
2188 const rtx_insn
*tmp_rtx
;
2190 fprintf (outf
, "(nil)\n");
2193 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
2194 int max_uid
= get_max_uid ();
2195 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
2196 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
2197 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
2200 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2201 insns, but the CFG is not maintained so the basic block info
2202 is not reliable. Therefore it's omitted from the dumps. */
2203 if (! (cfun
->curr_properties
& PROP_cfg
))
2204 flags
&= ~TDF_BLOCKS
;
2207 df_dump_start (outf
);
2209 if (flags
& TDF_BLOCKS
)
2211 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2215 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
2216 end
[INSN_UID (BB_END (bb
))] = bb
;
2217 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
2219 enum bb_state state
= IN_MULTIPLE_BB
;
2221 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
2223 in_bb_p
[INSN_UID (x
)] = state
;
2225 if (x
== BB_END (bb
))
2231 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
2233 if (flags
& TDF_BLOCKS
)
2235 bb
= start
[INSN_UID (tmp_rtx
)];
2238 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, true, false);
2239 if (df
&& (flags
& TDF_DETAILS
))
2240 df_dump_top (bb
, outf
);
2243 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
2244 && !NOTE_P (tmp_rtx
)
2245 && !BARRIER_P (tmp_rtx
))
2246 fprintf (outf
, ";; Insn is not within a basic block\n");
2247 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
2248 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
2251 if (flags
& TDF_DETAILS
)
2252 df_dump_insn_top (tmp_rtx
, outf
);
2253 if (! (flags
& TDF_SLIM
))
2254 print_rtl_single (outf
, tmp_rtx
);
2256 dump_insn_slim (outf
, tmp_rtx
);
2257 if (flags
& TDF_DETAILS
)
2258 df_dump_insn_bottom (tmp_rtx
, outf
);
2260 if (flags
& TDF_BLOCKS
)
2262 bb
= end
[INSN_UID (tmp_rtx
)];
2265 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, false, true);
2266 if (df
&& (flags
& TDF_DETAILS
))
2267 df_dump_bottom (bb
, outf
);
2279 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2282 update_br_prob_note (basic_block bb
)
2285 if (!JUMP_P (BB_END (bb
)))
2287 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
2288 if (!note
|| XINT (note
, 0) == BRANCH_EDGE (bb
)->probability
)
2290 XINT (note
, 0) = BRANCH_EDGE (bb
)->probability
;
2293 /* Get the last insn associated with block BB (that includes barriers and
2294 tablejumps after BB). */
2296 get_last_bb_insn (basic_block bb
)
2298 rtx_jump_table_data
*table
;
2300 rtx_insn
*end
= BB_END (bb
);
2302 /* Include any jump table following the basic block. */
2303 if (tablejump_p (end
, NULL
, &table
))
2306 /* Include any barriers that may follow the basic block. */
2307 tmp
= next_nonnote_insn_bb (end
);
2308 while (tmp
&& BARRIER_P (tmp
))
2311 tmp
= next_nonnote_insn_bb (end
);
2317 /* Sanity check partition hotness to ensure that basic blocks in
2318 Â the cold partition don't dominate basic blocks in the hot partition.
2319 If FLAG_ONLY is true, report violations as errors. Otherwise
2320 re-mark the dominated blocks as cold, since this is run after
2321 cfg optimizations that may make hot blocks previously reached
2322 by both hot and cold blocks now only reachable along cold paths. */
2324 static vec
<basic_block
>
2325 find_partition_fixes (bool flag_only
)
2328 vec
<basic_block
> bbs_in_cold_partition
= vNULL
;
2329 vec
<basic_block
> bbs_to_fix
= vNULL
;
2331 /* Callers check this. */
2332 gcc_checking_assert (crtl
->has_bb_partition
);
2334 FOR_EACH_BB_FN (bb
, cfun
)
2335 if ((BB_PARTITION (bb
) == BB_COLD_PARTITION
))
2336 bbs_in_cold_partition
.safe_push (bb
);
2338 if (bbs_in_cold_partition
.is_empty ())
2341 bool dom_calculated_here
= !dom_info_available_p (CDI_DOMINATORS
);
2343 if (dom_calculated_here
)
2344 calculate_dominance_info (CDI_DOMINATORS
);
2346 while (! bbs_in_cold_partition
.is_empty ())
2348 bb
= bbs_in_cold_partition
.pop ();
2349 /* Any blocks dominated by a block in the cold section
2350 must also be cold. */
2352 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2354 son
= next_dom_son (CDI_DOMINATORS
, son
))
2356 /* If son is not yet cold, then mark it cold here and
2357 enqueue it for further processing. */
2358 if ((BB_PARTITION (son
) != BB_COLD_PARTITION
))
2361 error ("non-cold basic block %d dominated "
2362 "by a block in the cold partition (%d)", son
->index
, bb
->index
);
2364 BB_SET_PARTITION (son
, BB_COLD_PARTITION
);
2365 bbs_to_fix
.safe_push (son
);
2366 bbs_in_cold_partition
.safe_push (son
);
2371 if (dom_calculated_here
)
2372 free_dominance_info (CDI_DOMINATORS
);
2377 /* Perform cleanup on the hot/cold bb partitioning after optimization
2378 passes that modify the cfg. */
2381 fixup_partitions (void)
2385 if (!crtl
->has_bb_partition
)
2388 /* Delete any blocks that became unreachable and weren't
2389 already cleaned up, for example during edge forwarding
2390 and convert_jumps_to_returns. This will expose more
2391 opportunities for fixing the partition boundaries here.
2392 Also, the calculation of the dominance graph during verification
2393 will assert if there are unreachable nodes. */
2394 delete_unreachable_blocks ();
2396 /* If there are partitions, do a sanity check on them: A basic block in
2397 Â a cold partition cannot dominate a basic block in a hot partition.
2398 Fixup any that now violate this requirement, as a result of edge
2399 forwarding and unreachable block deletion. Â */
2400 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (false);
2402 /* Do the partition fixup after all necessary blocks have been converted to
2403 cold, so that we only update the region crossings the minimum number of
2404 places, which can require forcing edges to be non fallthru. */
2405 while (! bbs_to_fix
.is_empty ())
2407 bb
= bbs_to_fix
.pop ();
2408 fixup_new_cold_bb (bb
);
2412 /* Verify, in the basic block chain, that there is at most one switch
2413 between hot/cold partitions. This condition will not be true until
2414 after reorder_basic_blocks is called. */
2417 verify_hot_cold_block_grouping (void)
2421 bool switched_sections
= false;
2422 int current_partition
= BB_UNPARTITIONED
;
2424 /* Even after bb reordering is complete, we go into cfglayout mode
2425 again (in compgoto). Ensure we don't call this before going back
2426 into linearized RTL when any layout fixes would have been committed. */
2427 if (!crtl
->bb_reorder_complete
2428 || current_ir_type () != IR_RTL_CFGRTL
)
2431 FOR_EACH_BB_FN (bb
, cfun
)
2433 if (current_partition
!= BB_UNPARTITIONED
2434 && BB_PARTITION (bb
) != current_partition
)
2436 if (switched_sections
)
2438 error ("multiple hot/cold transitions found (bb %i)",
2443 switched_sections
= true;
2445 if (!crtl
->has_bb_partition
)
2446 error ("partition found but function partition flag not set");
2448 current_partition
= BB_PARTITION (bb
);
2455 /* Perform several checks on the edges out of each block, such as
2456 the consistency of the branch probabilities, the correctness
2457 of hot/cold partition crossing edges, and the number of expected
2458 successor edges. Also verify that the dominance relationship
2459 between hot/cold blocks is sane. */
2462 rtl_verify_edges (void)
2467 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2469 int n_fallthru
= 0, n_branch
= 0, n_abnormal_call
= 0, n_sibcall
= 0;
2470 int n_eh
= 0, n_abnormal
= 0;
2471 edge e
, fallthru
= NULL
;
2474 bool has_crossing_edge
= false;
2476 if (JUMP_P (BB_END (bb
))
2477 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
2478 && EDGE_COUNT (bb
->succs
) >= 2
2479 && any_condjump_p (BB_END (bb
)))
2481 if (XINT (note
, 0) != BRANCH_EDGE (bb
)->probability
2482 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2484 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2485 XINT (note
, 0), BRANCH_EDGE (bb
)->probability
);
2490 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2494 if (e
->flags
& EDGE_FALLTHRU
)
2495 n_fallthru
++, fallthru
= e
;
2497 is_crossing
= (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
2498 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2499 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
2500 has_crossing_edge
|= is_crossing
;
2501 if (e
->flags
& EDGE_CROSSING
)
2505 error ("EDGE_CROSSING incorrectly set across same section");
2508 if (e
->flags
& EDGE_FALLTHRU
)
2510 error ("fallthru edge crosses section boundary in bb %i",
2514 if (e
->flags
& EDGE_EH
)
2516 error ("EH edge crosses section boundary in bb %i",
2520 if (JUMP_P (BB_END (bb
)) && !CROSSING_JUMP_P (BB_END (bb
)))
2522 error ("No region crossing jump at section boundary in bb %i",
2527 else if (is_crossing
)
2529 error ("EDGE_CROSSING missing across section boundary");
2533 if ((e
->flags
& ~(EDGE_DFS_BACK
2535 | EDGE_IRREDUCIBLE_LOOP
2538 | EDGE_PRESERVE
)) == 0)
2541 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2544 if (e
->flags
& EDGE_SIBCALL
)
2547 if (e
->flags
& EDGE_EH
)
2550 if (e
->flags
& EDGE_ABNORMAL
)
2554 if (!has_crossing_edge
2555 && JUMP_P (BB_END (bb
))
2556 && CROSSING_JUMP_P (BB_END (bb
)))
2558 print_rtl_with_bb (stderr
, get_insns (), TDF_RTL
| TDF_BLOCKS
| TDF_DETAILS
);
2559 error ("Region crossing jump across same section in bb %i",
2564 if (n_eh
&& !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
2566 error ("missing REG_EH_REGION note at the end of bb %i", bb
->index
);
2571 error ("too many exception handling edges in bb %i", bb
->index
);
2575 && (!JUMP_P (BB_END (bb
))
2576 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
2577 || any_condjump_p (BB_END (bb
))))))
2579 error ("too many outgoing branch edges from bb %i", bb
->index
);
2582 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
2584 error ("fallthru edge after unconditional jump in bb %i", bb
->index
);
2587 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
2589 error ("wrong number of branch edges after unconditional jump"
2590 " in bb %i", bb
->index
);
2593 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
2594 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
2596 error ("wrong amount of branch edges after conditional jump"
2597 " in bb %i", bb
->index
);
2600 if (n_abnormal_call
&& !CALL_P (BB_END (bb
)))
2602 error ("abnormal call edges for non-call insn in bb %i", bb
->index
);
2605 if (n_sibcall
&& !CALL_P (BB_END (bb
)))
2607 error ("sibcall edges for non-call insn in bb %i", bb
->index
);
2610 if (n_abnormal
> n_eh
2611 && !(CALL_P (BB_END (bb
))
2612 && n_abnormal
== n_abnormal_call
+ n_sibcall
)
2613 && (!JUMP_P (BB_END (bb
))
2614 || any_condjump_p (BB_END (bb
))
2615 || any_uncondjump_p (BB_END (bb
))))
2617 error ("abnormal edges for no purpose in bb %i", bb
->index
);
2622 /* If there are partitions, do a sanity check on them: A basic block in
2623 Â a cold partition cannot dominate a basic block in a hot partition. Â */
2624 if (crtl
->has_bb_partition
&& !err
)
2626 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (true);
2627 err
= !bbs_to_fix
.is_empty ();
2634 /* Checks on the instructions within blocks. Currently checks that each
2635 block starts with a basic block note, and that basic block notes and
2636 control flow jumps are not found in the middle of the block. */
2639 rtl_verify_bb_insns (void)
2645 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2647 /* Now check the header of basic
2648 block. It ought to contain optional CODE_LABEL followed
2649 by NOTE_BASIC_BLOCK. */
2653 if (BB_END (bb
) == x
)
2655 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2663 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2665 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2670 if (BB_END (bb
) == x
)
2671 /* Do checks for empty blocks here. */
2674 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2676 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2678 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2679 INSN_UID (x
), bb
->index
);
2683 if (x
== BB_END (bb
))
2686 if (control_flow_insn_p (x
))
2688 error ("in basic block %d:", bb
->index
);
2689 fatal_insn ("flow control insn inside a basic block", x
);
2698 /* Verify that block pointers for instructions in basic blocks, headers and
2699 footers are set appropriately. */
2702 rtl_verify_bb_pointers (void)
2707 /* Check the general integrity of the basic blocks. */
2708 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2712 if (!(bb
->flags
& BB_RTL
))
2714 error ("BB_RTL flag not set for block %d", bb
->index
);
2718 FOR_BB_INSNS (bb
, insn
)
2719 if (BLOCK_FOR_INSN (insn
) != bb
)
2721 error ("insn %d basic block pointer is %d, should be %d",
2723 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
2728 for (insn
= BB_HEADER (bb
); insn
; insn
= NEXT_INSN (insn
))
2729 if (!BARRIER_P (insn
)
2730 && BLOCK_FOR_INSN (insn
) != NULL
)
2732 error ("insn %d in header of bb %d has non-NULL basic block",
2733 INSN_UID (insn
), bb
->index
);
2736 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
2737 if (!BARRIER_P (insn
)
2738 && BLOCK_FOR_INSN (insn
) != NULL
)
2740 error ("insn %d in footer of bb %d has non-NULL basic block",
2741 INSN_UID (insn
), bb
->index
);
2750 /* Verify the CFG and RTL consistency common for both underlying RTL and
2753 Currently it does following checks:
2755 - overlapping of basic blocks
2756 - insns with wrong BLOCK_FOR_INSN pointers
2757 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2758 - tails of basic blocks (ensure that boundary is necessary)
2759 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2760 and NOTE_INSN_BASIC_BLOCK
2761 - verify that no fall_thru edge crosses hot/cold partition boundaries
2762 - verify that there are no pending RTL branch predictions
2763 - verify that hot blocks are not dominated by cold blocks
2765 In future it can be extended check a lot of other stuff as well
2766 (reachability of basic blocks, life information, etc. etc.). */
2769 rtl_verify_flow_info_1 (void)
2773 err
|= rtl_verify_bb_pointers ();
2775 err
|= rtl_verify_bb_insns ();
2777 err
|= rtl_verify_edges ();
2782 /* Walk the instruction chain and verify that bb head/end pointers
2783 are correct, and that instructions are in exactly one bb and have
2784 correct block pointers. */
2787 rtl_verify_bb_insn_chain (void)
2792 rtx_insn
*last_head
= get_last_insn ();
2793 basic_block
*bb_info
;
2794 const int max_uid
= get_max_uid ();
2796 bb_info
= XCNEWVEC (basic_block
, max_uid
);
2798 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2800 rtx_insn
*head
= BB_HEAD (bb
);
2801 rtx_insn
*end
= BB_END (bb
);
2803 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2805 /* Verify the end of the basic block is in the INSN chain. */
2809 /* And that the code outside of basic blocks has NULL bb field. */
2811 && BLOCK_FOR_INSN (x
) != NULL
)
2813 error ("insn %d outside of basic blocks has non-NULL bb field",
2821 error ("end insn %d for block %d not found in the insn stream",
2822 INSN_UID (end
), bb
->index
);
2826 /* Work backwards from the end to the head of the basic block
2827 to verify the head is in the RTL chain. */
2828 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2830 /* While walking over the insn chain, verify insns appear
2831 in only one basic block. */
2832 if (bb_info
[INSN_UID (x
)] != NULL
)
2834 error ("insn %d is in multiple basic blocks (%d and %d)",
2835 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2839 bb_info
[INSN_UID (x
)] = bb
;
2846 error ("head insn %d for block %d not found in the insn stream",
2847 INSN_UID (head
), bb
->index
);
2851 last_head
= PREV_INSN (x
);
2854 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2856 /* Check that the code before the first basic block has NULL
2859 && BLOCK_FOR_INSN (x
) != NULL
)
2861 error ("insn %d outside of basic blocks has non-NULL bb field",
2871 /* Verify that fallthru edges point to adjacent blocks in layout order and
2872 that barriers exist after non-fallthru blocks. */
2875 rtl_verify_fallthru (void)
2880 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2884 e
= find_fallthru_edge (bb
->succs
);
2889 /* Ensure existence of barrier in BB with no fallthru edges. */
2890 for (insn
= NEXT_INSN (BB_END (bb
)); ; insn
= NEXT_INSN (insn
))
2892 if (!insn
|| NOTE_INSN_BASIC_BLOCK_P (insn
))
2894 error ("missing barrier after block %i", bb
->index
);
2898 if (BARRIER_P (insn
))
2902 else if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2903 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2907 if (e
->src
->next_bb
!= e
->dest
)
2910 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2911 e
->src
->index
, e
->dest
->index
);
2915 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
2916 insn
= NEXT_INSN (insn
))
2917 if (BARRIER_P (insn
) || INSN_P (insn
))
2919 error ("verify_flow_info: Incorrect fallthru %i->%i",
2920 e
->src
->index
, e
->dest
->index
);
2921 fatal_insn ("wrong insn in the fallthru edge", insn
);
2930 /* Verify that blocks are laid out in consecutive order. While walking the
2931 instructions, verify that all expected instructions are inside the basic
2932 blocks, and that all returns are followed by barriers. */
2935 rtl_verify_bb_layout (void)
2941 rtx_insn
* const rtx_first
= get_insns ();
2942 basic_block last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
), curr_bb
= NULL
;
2945 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
2947 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2949 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2951 bb
= NOTE_BASIC_BLOCK (x
);
2954 if (bb
!= last_bb_seen
->next_bb
)
2955 internal_error ("basic blocks not laid down consecutively");
2957 curr_bb
= last_bb_seen
= bb
;
2962 switch (GET_CODE (x
))
2969 /* An ADDR_VEC is placed outside any basic block. */
2971 && JUMP_TABLE_DATA_P (NEXT_INSN (x
)))
2974 /* But in any case, non-deletable labels can appear anywhere. */
2978 fatal_insn ("insn outside basic block", x
);
2983 && returnjump_p (x
) && ! condjump_p (x
)
2984 && ! (next_nonnote_insn (x
) && BARRIER_P (next_nonnote_insn (x
))))
2985 fatal_insn ("return not followed by barrier", x
);
2987 if (curr_bb
&& x
== BB_END (curr_bb
))
2991 if (num_bb_notes
!= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
)
2993 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2994 num_bb_notes
, n_basic_blocks_for_fn (cfun
));
2999 /* Verify the CFG and RTL consistency common for both underlying RTL and
3000 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
3002 Currently it does following checks:
3003 - all checks of rtl_verify_flow_info_1
3004 - test head/end pointers
3005 - check that blocks are laid out in consecutive order
3006 - check that all insns are in the basic blocks
3007 (except the switch handling code, barriers and notes)
3008 - check that all returns are followed by barriers
3009 - check that all fallthru edge points to the adjacent blocks
3010 - verify that there is a single hot/cold partition boundary after bbro */
3013 rtl_verify_flow_info (void)
3017 err
|= rtl_verify_flow_info_1 ();
3019 err
|= rtl_verify_bb_insn_chain ();
3021 err
|= rtl_verify_fallthru ();
3023 err
|= rtl_verify_bb_layout ();
3025 err
|= verify_hot_cold_block_grouping ();
3030 /* Assume that the preceding pass has possibly eliminated jump instructions
3031 or converted the unconditional jumps. Eliminate the edges from CFG.
3032 Return true if any edges are eliminated. */
3035 purge_dead_edges (basic_block bb
)
3038 rtx_insn
*insn
= BB_END (bb
);
3040 bool purged
= false;
3044 if (DEBUG_INSN_P (insn
) && insn
!= BB_HEAD (bb
))
3046 insn
= PREV_INSN (insn
);
3047 while ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
));
3049 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3050 if (NONJUMP_INSN_P (insn
)
3051 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
3055 if (! may_trap_p (PATTERN (insn
))
3056 || ((eqnote
= find_reg_equal_equiv_note (insn
))
3057 && ! may_trap_p (XEXP (eqnote
, 0))))
3058 remove_note (insn
, note
);
3061 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3062 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3064 bool remove
= false;
3066 /* There are three types of edges we need to handle correctly here: EH
3067 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3068 latter can appear when nonlocal gotos are used. */
3069 if (e
->flags
& EDGE_ABNORMAL_CALL
)
3073 else if (can_nonlocal_goto (insn
))
3075 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3077 else if (flag_tm
&& find_reg_note (insn
, REG_TM
, NULL
))
3082 else if (e
->flags
& EDGE_EH
)
3083 remove
= !can_throw_internal (insn
);
3088 df_set_bb_dirty (bb
);
3101 /* We do care only about conditional jumps and simplejumps. */
3102 if (!any_condjump_p (insn
)
3103 && !returnjump_p (insn
)
3104 && !simplejump_p (insn
))
3107 /* Branch probability/prediction notes are defined only for
3108 condjumps. We've possibly turned condjump into simplejump. */
3109 if (simplejump_p (insn
))
3111 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3113 remove_note (insn
, note
);
3114 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
3115 remove_note (insn
, note
);
3118 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3120 /* Avoid abnormal flags to leak from computed jumps turned
3121 into simplejumps. */
3123 e
->flags
&= ~EDGE_ABNORMAL
;
3125 /* See if this edge is one we should keep. */
3126 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
3127 /* A conditional jump can fall through into the next
3128 block, so we should keep the edge. */
3133 else if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3134 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
3135 /* If the destination block is the target of the jump,
3141 else if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
3142 && returnjump_p (insn
))
3143 /* If the destination block is the exit block, and this
3144 instruction is a return, then keep the edge. */
3149 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3150 /* Keep the edges that correspond to exceptions thrown by
3151 this instruction and rematerialize the EDGE_ABNORMAL
3152 flag we just cleared above. */
3154 e
->flags
|= EDGE_ABNORMAL
;
3159 /* We do not need this edge. */
3160 df_set_bb_dirty (bb
);
3165 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
3169 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
3174 /* Redistribute probabilities. */
3175 if (single_succ_p (bb
))
3177 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3178 single_succ_edge (bb
)->count
= bb
->count
;
3182 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3186 b
= BRANCH_EDGE (bb
);
3187 f
= FALLTHRU_EDGE (bb
);
3188 b
->probability
= XINT (note
, 0);
3189 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
3190 /* Update these to use GCOV_COMPUTE_SCALE. */
3191 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
3192 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
3197 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
3199 /* First, there should not be any EH or ABCALL edges resulting
3200 from non-local gotos and the like. If there were, we shouldn't
3201 have created the sibcall in the first place. Second, there
3202 should of course never have been a fallthru edge. */
3203 gcc_assert (single_succ_p (bb
));
3204 gcc_assert (single_succ_edge (bb
)->flags
3205 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
3210 /* If we don't see a jump insn, we don't know exactly why the block would
3211 have been broken at this point. Look for a simple, non-fallthru edge,
3212 as these are only created by conditional branches. If we find such an
3213 edge we know that there used to be a jump here and can then safely
3214 remove all non-fallthru edges. */
3216 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3217 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
3226 /* Remove all but the fake and fallthru edges. The fake edge may be
3227 the only successor for this block in the case of noreturn
3229 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3231 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
3233 df_set_bb_dirty (bb
);
3241 gcc_assert (single_succ_p (bb
));
3243 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3244 single_succ_edge (bb
)->count
= bb
->count
;
3247 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
3252 /* Search all basic blocks for potentially dead edges and purge them. Return
3253 true if some edge has been eliminated. */
3256 purge_all_dead_edges (void)
3261 FOR_EACH_BB_FN (bb
, cfun
)
3263 bool purged_here
= purge_dead_edges (bb
);
3265 purged
|= purged_here
;
3271 /* This is used by a few passes that emit some instructions after abnormal
3272 calls, moving the basic block's end, while they in fact do want to emit
3273 them on the fallthru edge. Look for abnormal call edges, find backward
3274 the call in the block and insert the instructions on the edge instead.
3276 Similarly, handle instructions throwing exceptions internally.
3278 Return true when instructions have been found and inserted on edges. */
3281 fixup_abnormal_edges (void)
3283 bool inserted
= false;
3286 FOR_EACH_BB_FN (bb
, cfun
)
3291 /* Look for cases we are interested in - calls or instructions causing
3293 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3294 if ((e
->flags
& EDGE_ABNORMAL_CALL
)
3295 || ((e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
3296 == (EDGE_ABNORMAL
| EDGE_EH
)))
3299 if (e
&& !CALL_P (BB_END (bb
)) && !can_throw_internal (BB_END (bb
)))
3303 /* Get past the new insns generated. Allow notes, as the insns
3304 may be already deleted. */
3306 while ((NONJUMP_INSN_P (insn
) || NOTE_P (insn
))
3307 && !can_throw_internal (insn
)
3308 && insn
!= BB_HEAD (bb
))
3309 insn
= PREV_INSN (insn
);
3311 if (CALL_P (insn
) || can_throw_internal (insn
))
3313 rtx_insn
*stop
, *next
;
3315 e
= find_fallthru_edge (bb
->succs
);
3317 stop
= NEXT_INSN (BB_END (bb
));
3320 for (insn
= NEXT_INSN (insn
); insn
!= stop
; insn
= next
)
3322 next
= NEXT_INSN (insn
);
3327 /* Sometimes there's still the return value USE.
3328 If it's placed after a trapping call (i.e. that
3329 call is the last insn anyway), we have no fallthru
3330 edge. Simply delete this use and don't try to insert
3331 on the non-existent edge. */
3332 if (GET_CODE (PATTERN (insn
)) != USE
)
3334 /* We're not deleting it, we're moving it. */
3335 insn
->set_undeleted ();
3336 SET_PREV_INSN (insn
) = NULL_RTX
;
3337 SET_NEXT_INSN (insn
) = NULL_RTX
;
3339 insert_insn_on_edge (insn
, e
);
3343 else if (!BARRIER_P (insn
))
3344 set_block_for_insn (insn
, NULL
);
3348 /* It may be that we don't find any trapping insn. In this
3349 case we discovered quite late that the insn that had been
3350 marked as can_throw_internal in fact couldn't trap at all.
3351 So we should in fact delete the EH edges out of the block. */
3353 purge_dead_edges (bb
);
3360 /* Cut the insns from FIRST to LAST out of the insns stream. */
3363 unlink_insn_chain (rtx_insn
*first
, rtx_insn
*last
)
3365 rtx_insn
*prevfirst
= PREV_INSN (first
);
3366 rtx_insn
*nextlast
= NEXT_INSN (last
);
3368 SET_PREV_INSN (first
) = NULL
;
3369 SET_NEXT_INSN (last
) = NULL
;
3371 SET_NEXT_INSN (prevfirst
) = nextlast
;
3373 SET_PREV_INSN (nextlast
) = prevfirst
;
3375 set_last_insn (prevfirst
);
3377 set_first_insn (nextlast
);
3381 /* Skip over inter-block insns occurring after BB which are typically
3382 associated with BB (e.g., barriers). If there are any such insns,
3383 we return the last one. Otherwise, we return the end of BB. */
3386 skip_insns_after_block (basic_block bb
)
3388 rtx_insn
*insn
, *last_insn
, *next_head
, *prev
;
3391 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3392 next_head
= BB_HEAD (bb
->next_bb
);
3394 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
3396 if (insn
== next_head
)
3399 switch (GET_CODE (insn
))
3406 switch (NOTE_KIND (insn
))
3408 case NOTE_INSN_BLOCK_END
:
3418 if (NEXT_INSN (insn
)
3419 && JUMP_TABLE_DATA_P (NEXT_INSN (insn
)))
3421 insn
= NEXT_INSN (insn
);
3434 /* It is possible to hit contradictory sequence. For instance:
3440 Where barrier belongs to jump_insn, but the note does not. This can be
3441 created by removing the basic block originally following
3442 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3444 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
3446 prev
= PREV_INSN (insn
);
3448 switch (NOTE_KIND (insn
))
3450 case NOTE_INSN_BLOCK_END
:
3453 case NOTE_INSN_DELETED
:
3454 case NOTE_INSN_DELETED_LABEL
:
3455 case NOTE_INSN_DELETED_DEBUG_LABEL
:
3458 reorder_insns (insn
, insn
, last_insn
);
3465 /* Locate or create a label for a given basic block. */
3468 label_for_bb (basic_block bb
)
3470 rtx label
= BB_HEAD (bb
);
3472 if (!LABEL_P (label
))
3475 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
3477 label
= block_label (bb
);
3483 /* Locate the effective beginning and end of the insn chain for each
3484 block, as defined by skip_insns_after_block above. */
3487 record_effective_endpoints (void)
3489 rtx_insn
*next_insn
;
3493 for (insn
= get_insns ();
3496 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
;
3497 insn
= NEXT_INSN (insn
))
3499 /* No basic blocks at all? */
3502 if (PREV_INSN (insn
))
3503 cfg_layout_function_header
=
3504 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
3506 cfg_layout_function_header
= NULL
;
3508 next_insn
= get_insns ();
3509 FOR_EACH_BB_FN (bb
, cfun
)
3513 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
3514 BB_HEADER (bb
) = unlink_insn_chain (next_insn
,
3515 PREV_INSN (BB_HEAD (bb
)));
3516 end
= skip_insns_after_block (bb
);
3517 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
3518 BB_FOOTER (bb
) = unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
3519 next_insn
= NEXT_INSN (BB_END (bb
));
3522 cfg_layout_function_footer
= next_insn
;
3523 if (cfg_layout_function_footer
)
3524 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
3529 const pass_data pass_data_into_cfg_layout_mode
=
3531 RTL_PASS
, /* type */
3532 "into_cfglayout", /* name */
3533 OPTGROUP_NONE
, /* optinfo_flags */
3535 0, /* properties_required */
3536 PROP_cfglayout
, /* properties_provided */
3537 0, /* properties_destroyed */
3538 0, /* todo_flags_start */
3539 0, /* todo_flags_finish */
3542 class pass_into_cfg_layout_mode
: public rtl_opt_pass
3545 pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3546 : rtl_opt_pass (pass_data_into_cfg_layout_mode
, ctxt
)
3549 /* opt_pass methods: */
3550 virtual unsigned int execute (function
*)
3552 cfg_layout_initialize (0);
3556 }; // class pass_into_cfg_layout_mode
3561 make_pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3563 return new pass_into_cfg_layout_mode (ctxt
);
3568 const pass_data pass_data_outof_cfg_layout_mode
=
3570 RTL_PASS
, /* type */
3571 "outof_cfglayout", /* name */
3572 OPTGROUP_NONE
, /* optinfo_flags */
3574 0, /* properties_required */
3575 0, /* properties_provided */
3576 PROP_cfglayout
, /* properties_destroyed */
3577 0, /* todo_flags_start */
3578 0, /* todo_flags_finish */
3581 class pass_outof_cfg_layout_mode
: public rtl_opt_pass
3584 pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3585 : rtl_opt_pass (pass_data_outof_cfg_layout_mode
, ctxt
)
3588 /* opt_pass methods: */
3589 virtual unsigned int execute (function
*);
3591 }; // class pass_outof_cfg_layout_mode
3594 pass_outof_cfg_layout_mode::execute (function
*fun
)
3598 FOR_EACH_BB_FN (bb
, fun
)
3599 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3600 bb
->aux
= bb
->next_bb
;
3602 cfg_layout_finalize ();
3610 make_pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3612 return new pass_outof_cfg_layout_mode (ctxt
);
3616 /* Link the basic blocks in the correct order, compacting the basic
3617 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3618 function also clears the basic block header and footer fields.
3620 This function is usually called after a pass (e.g. tracer) finishes
3621 some transformations while in cfglayout mode. The required sequence
3622 of the basic blocks is in a linked list along the bb->aux field.
3623 This functions re-links the basic block prev_bb and next_bb pointers
3624 accordingly, and it compacts and renumbers the blocks.
3626 FIXME: This currently works only for RTL, but the only RTL-specific
3627 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3628 to GIMPLE a long time ago, but it doesn't relink the basic block
3629 chain. It could do that (to give better initial RTL) if this function
3630 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3633 relink_block_chain (bool stay_in_cfglayout_mode
)
3635 basic_block bb
, prev_bb
;
3638 /* Maybe dump the re-ordered sequence. */
3641 fprintf (dump_file
, "Reordered sequence:\n");
3642 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, index
=
3645 bb
= (basic_block
) bb
->aux
, index
++)
3647 fprintf (dump_file
, " %i ", index
);
3648 if (get_bb_original (bb
))
3649 fprintf (dump_file
, "duplicate of %i ",
3650 get_bb_original (bb
)->index
);
3651 else if (forwarder_block_p (bb
)
3652 && !LABEL_P (BB_HEAD (bb
)))
3653 fprintf (dump_file
, "compensation ");
3655 fprintf (dump_file
, "bb %i ", bb
->index
);
3656 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
3660 /* Now reorder the blocks. */
3661 prev_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
3662 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
3663 for (; bb
; prev_bb
= bb
, bb
= (basic_block
) bb
->aux
)
3665 bb
->prev_bb
= prev_bb
;
3666 prev_bb
->next_bb
= bb
;
3668 prev_bb
->next_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
3669 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
= prev_bb
;
3671 /* Then, clean up the aux fields. */
3672 FOR_ALL_BB_FN (bb
, cfun
)
3675 if (!stay_in_cfglayout_mode
)
3676 BB_HEADER (bb
) = BB_FOOTER (bb
) = NULL
;
3679 /* Maybe reset the original copy tables, they are not valid anymore
3680 when we renumber the basic blocks in compact_blocks. If we are
3681 are going out of cfglayout mode, don't re-allocate the tables. */
3682 free_original_copy_tables ();
3683 if (stay_in_cfglayout_mode
)
3684 initialize_original_copy_tables ();
3686 /* Finally, put basic_block_info in the new order. */
3691 /* Given a reorder chain, rearrange the code to match. */
3694 fixup_reorder_chain (void)
3697 rtx_insn
*insn
= NULL
;
3699 if (cfg_layout_function_header
)
3701 set_first_insn (cfg_layout_function_header
);
3702 insn
= cfg_layout_function_header
;
3703 while (NEXT_INSN (insn
))
3704 insn
= NEXT_INSN (insn
);
3707 /* First do the bulk reordering -- rechain the blocks without regard to
3708 the needed changes to jumps and labels. */
3710 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3716 SET_NEXT_INSN (insn
) = BB_HEADER (bb
);
3718 set_first_insn (BB_HEADER (bb
));
3719 SET_PREV_INSN (BB_HEADER (bb
)) = insn
;
3720 insn
= BB_HEADER (bb
);
3721 while (NEXT_INSN (insn
))
3722 insn
= NEXT_INSN (insn
);
3725 SET_NEXT_INSN (insn
) = BB_HEAD (bb
);
3727 set_first_insn (BB_HEAD (bb
));
3728 SET_PREV_INSN (BB_HEAD (bb
)) = insn
;
3732 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
3733 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
3734 while (NEXT_INSN (insn
))
3735 insn
= NEXT_INSN (insn
);
3739 SET_NEXT_INSN (insn
) = cfg_layout_function_footer
;
3740 if (cfg_layout_function_footer
)
3741 SET_PREV_INSN (cfg_layout_function_footer
) = insn
;
3743 while (NEXT_INSN (insn
))
3744 insn
= NEXT_INSN (insn
);
3746 set_last_insn (insn
);
3747 #ifdef ENABLE_CHECKING
3748 verify_insn_chain ();
3751 /* Now add jumps and labels as needed to match the blocks new
3754 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3757 edge e_fall
, e_taken
, e
;
3758 rtx_insn
*bb_end_insn
;
3759 rtx ret_label
= NULL_RTX
;
3763 if (EDGE_COUNT (bb
->succs
) == 0)
3766 /* Find the old fallthru edge, and another non-EH edge for
3768 e_taken
= e_fall
= NULL
;
3770 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3771 if (e
->flags
& EDGE_FALLTHRU
)
3773 else if (! (e
->flags
& EDGE_EH
))
3776 bb_end_insn
= BB_END (bb
);
3777 if (rtx_jump_insn
*bb_end_jump
= dyn_cast
<rtx_jump_insn
*> (bb_end_insn
))
3779 ret_label
= JUMP_LABEL (bb_end_jump
);
3780 if (any_condjump_p (bb_end_jump
))
3782 /* This might happen if the conditional jump has side
3783 effects and could therefore not be optimized away.
3784 Make the basic block to end with a barrier in order
3785 to prevent rtl_verify_flow_info from complaining. */
3788 gcc_assert (!onlyjump_p (bb_end_jump
)
3789 || returnjump_p (bb_end_jump
)
3790 || (e_taken
->flags
& EDGE_CROSSING
));
3791 emit_barrier_after (bb_end_jump
);
3795 /* If the old fallthru is still next, nothing to do. */
3796 if (bb
->aux
== e_fall
->dest
3797 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3800 /* The degenerated case of conditional jump jumping to the next
3801 instruction can happen for jumps with side effects. We need
3802 to construct a forwarder block and this will be done just
3803 fine by force_nonfallthru below. */
3807 /* There is another special case: if *neither* block is next,
3808 such as happens at the very end of a function, then we'll
3809 need to add a new unconditional jump. Choose the taken
3810 edge based on known or assumed probability. */
3811 else if (bb
->aux
!= e_taken
->dest
)
3813 rtx note
= find_reg_note (bb_end_jump
, REG_BR_PROB
, 0);
3816 && XINT (note
, 0) < REG_BR_PROB_BASE
/ 2
3817 && invert_jump (bb_end_jump
,
3819 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3821 : label_for_bb (e_fall
->dest
)), 0))
3823 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3824 gcc_checking_assert (could_fall_through
3825 (e_taken
->src
, e_taken
->dest
));
3826 e_taken
->flags
|= EDGE_FALLTHRU
;
3827 update_br_prob_note (bb
);
3828 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
3832 /* If the "jumping" edge is a crossing edge, and the fall
3833 through edge is non-crossing, leave things as they are. */
3834 else if ((e_taken
->flags
& EDGE_CROSSING
)
3835 && !(e_fall
->flags
& EDGE_CROSSING
))
3838 /* Otherwise we can try to invert the jump. This will
3839 basically never fail, however, keep up the pretense. */
3840 else if (invert_jump (bb_end_jump
,
3842 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3844 : label_for_bb (e_fall
->dest
)), 0))
3846 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3847 gcc_checking_assert (could_fall_through
3848 (e_taken
->src
, e_taken
->dest
));
3849 e_taken
->flags
|= EDGE_FALLTHRU
;
3850 update_br_prob_note (bb
);
3851 if (LABEL_NUSES (ret_label
) == 0
3852 && single_pred_p (e_taken
->dest
))
3853 delete_insn (ret_label
);
3857 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
3859 /* If the old fallthru is still next or if
3860 asm goto doesn't have a fallthru (e.g. when followed by
3861 __builtin_unreachable ()), nothing to do. */
3863 || bb
->aux
== e_fall
->dest
3864 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3867 /* Otherwise we'll have to use the fallthru fixup below. */
3871 /* Otherwise we have some return, switch or computed
3872 jump. In the 99% case, there should not have been a
3874 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
3880 /* No fallthru implies a noreturn function with EH edges, or
3881 something similarly bizarre. In any case, we don't need to
3886 /* If the fallthru block is still next, nothing to do. */
3887 if (bb
->aux
== e_fall
->dest
)
3890 /* A fallthru to exit block. */
3891 if (e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3895 /* We got here if we need to add a new jump insn.
3896 Note force_nonfallthru can delete E_FALL and thus we have to
3897 save E_FALL->src prior to the call to force_nonfallthru. */
3898 nb
= force_nonfallthru_and_redirect (e_fall
, e_fall
->dest
, ret_label
);
3903 /* Don't process this new block. */
3908 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3910 /* Annoying special case - jump around dead jumptables left in the code. */
3911 FOR_EACH_BB_FN (bb
, cfun
)
3913 edge e
= find_fallthru_edge (bb
->succs
);
3915 if (e
&& !can_fallthru (e
->src
, e
->dest
))
3916 force_nonfallthru (e
);
3919 /* Ensure goto_locus from edges has some instructions with that locus
3922 FOR_EACH_BB_FN (bb
, cfun
)
3927 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3928 if (LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
3929 && !(e
->flags
& EDGE_ABNORMAL
))
3933 basic_block dest
, nb
;
3936 insn
= BB_END (e
->src
);
3937 end
= PREV_INSN (BB_HEAD (e
->src
));
3939 && (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
3940 insn
= PREV_INSN (insn
);
3942 && INSN_LOCATION (insn
) == e
->goto_locus
)
3944 if (simplejump_p (BB_END (e
->src
))
3945 && !INSN_HAS_LOCATION (BB_END (e
->src
)))
3947 INSN_LOCATION (BB_END (e
->src
)) = e
->goto_locus
;
3951 if (dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3953 /* Non-fallthru edges to the exit block cannot be split. */
3954 if (!(e
->flags
& EDGE_FALLTHRU
))
3959 insn
= BB_HEAD (dest
);
3960 end
= NEXT_INSN (BB_END (dest
));
3961 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
3962 insn
= NEXT_INSN (insn
);
3963 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
3964 && INSN_LOCATION (insn
) == e
->goto_locus
)
3967 nb
= split_edge (e
);
3968 if (!INSN_P (BB_END (nb
)))
3969 BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
3971 INSN_LOCATION (BB_END (nb
)) = e
->goto_locus
;
3973 /* If there are other incoming edges to the destination block
3974 with the same goto locus, redirect them to the new block as
3975 well, this can prevent other such blocks from being created
3976 in subsequent iterations of the loop. */
3977 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
3978 if (LOCATION_LOCUS (e2
->goto_locus
) != UNKNOWN_LOCATION
3979 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
3980 && e
->goto_locus
== e2
->goto_locus
)
3981 redirect_edge_and_branch (e2
, nb
);
3988 /* Perform sanity checks on the insn chain.
3989 1. Check that next/prev pointers are consistent in both the forward and
3991 2. Count insns in chain, going both directions, and check if equal.
3992 3. Check that get_last_insn () returns the actual end of chain. */
3995 verify_insn_chain (void)
3997 rtx_insn
*x
, *prevx
, *nextx
;
3998 int insn_cnt1
, insn_cnt2
;
4000 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
4002 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
4003 gcc_assert (PREV_INSN (x
) == prevx
);
4005 gcc_assert (prevx
== get_last_insn ());
4007 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
4009 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
4010 gcc_assert (NEXT_INSN (x
) == nextx
);
4012 gcc_assert (insn_cnt1
== insn_cnt2
);
4015 /* If we have assembler epilogues, the block falling through to exit must
4016 be the last one in the reordered chain when we reach final. Ensure
4017 that this condition is met. */
4019 fixup_fallthru_exit_predecessor (void)
4022 basic_block bb
= NULL
;
4024 /* This transformation is not valid before reload, because we might
4025 separate a call from the instruction that copies the return
4027 gcc_assert (reload_completed
);
4029 e
= find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4035 basic_block c
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
4037 /* If the very first block is the one with the fall-through exit
4038 edge, we have to split that block. */
4041 bb
= split_block_after_labels (bb
)->dest
;
4044 BB_FOOTER (bb
) = BB_FOOTER (c
);
4045 BB_FOOTER (c
) = NULL
;
4048 while (c
->aux
!= bb
)
4049 c
= (basic_block
) c
->aux
;
4053 c
= (basic_block
) c
->aux
;
4060 /* In case there are more than one fallthru predecessors of exit, force that
4061 there is only one. */
4064 force_one_exit_fallthru (void)
4066 edge e
, predecessor
= NULL
;
4069 basic_block forwarder
, bb
;
4071 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
4072 if (e
->flags
& EDGE_FALLTHRU
)
4074 if (predecessor
== NULL
)
4086 /* Exit has several fallthru predecessors. Create a forwarder block for
4088 forwarder
= split_edge (predecessor
);
4089 for (ei
= ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4090 (e
= ei_safe_edge (ei
)); )
4092 if (e
->src
== forwarder
4093 || !(e
->flags
& EDGE_FALLTHRU
))
4096 redirect_edge_and_branch_force (e
, forwarder
);
4099 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4101 FOR_EACH_BB_FN (bb
, cfun
)
4103 if (bb
->aux
== NULL
&& bb
!= forwarder
)
4105 bb
->aux
= forwarder
;
4111 /* Return true in case it is possible to duplicate the basic block BB. */
4114 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
4116 /* Do not attempt to duplicate tablejumps, as we need to unshare
4117 the dispatch table. This is difficult to do, as the instructions
4118 computing jump destination may be hoisted outside the basic block. */
4119 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
4122 /* Do not duplicate blocks containing insns that can't be copied. */
4123 if (targetm
.cannot_copy_insn_p
)
4125 rtx_insn
*insn
= BB_HEAD (bb
);
4128 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
4130 if (insn
== BB_END (bb
))
4132 insn
= NEXT_INSN (insn
);
4140 duplicate_insn_chain (rtx_insn
*from
, rtx_insn
*to
)
4142 rtx_insn
*insn
, *next
, *copy
;
4145 /* Avoid updating of boundaries of previous basic block. The
4146 note will get removed from insn stream in fixup. */
4147 last
= emit_note (NOTE_INSN_DELETED
);
4149 /* Create copy at the end of INSN chain. The chain will
4150 be reordered later. */
4151 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
4153 switch (GET_CODE (insn
))
4156 /* Don't duplicate label debug insns. */
4157 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
)
4163 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
4164 if (JUMP_P (insn
) && JUMP_LABEL (insn
) != NULL_RTX
4165 && ANY_RETURN_P (JUMP_LABEL (insn
)))
4166 JUMP_LABEL (copy
) = JUMP_LABEL (insn
);
4167 maybe_copy_prologue_epilogue_insn (insn
, copy
);
4170 case JUMP_TABLE_DATA
:
4171 /* Avoid copying of dispatch tables. We never duplicate
4172 tablejumps, so this can hit only in case the table got
4173 moved far from original jump.
4174 Avoid copying following barrier as well if any
4175 (and debug insns in between). */
4176 for (next
= NEXT_INSN (insn
);
4177 next
!= NEXT_INSN (to
);
4178 next
= NEXT_INSN (next
))
4179 if (!DEBUG_INSN_P (next
))
4181 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
4193 switch (NOTE_KIND (insn
))
4195 /* In case prologue is empty and function contain label
4196 in first BB, we may want to copy the block. */
4197 case NOTE_INSN_PROLOGUE_END
:
4199 case NOTE_INSN_DELETED
:
4200 case NOTE_INSN_DELETED_LABEL
:
4201 case NOTE_INSN_DELETED_DEBUG_LABEL
:
4202 /* No problem to strip these. */
4203 case NOTE_INSN_FUNCTION_BEG
:
4204 /* There is always just single entry to function. */
4205 case NOTE_INSN_BASIC_BLOCK
:
4206 /* We should only switch text sections once. */
4207 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
4210 case NOTE_INSN_EPILOGUE_BEG
:
4211 case NOTE_INSN_UPDATE_SJLJ_CONTEXT
:
4212 emit_note_copy (as_a
<rtx_note
*> (insn
));
4216 /* All other notes should have already been eliminated. */
4224 insn
= NEXT_INSN (last
);
4229 /* Create a duplicate of the basic block BB. */
4232 cfg_layout_duplicate_bb (basic_block bb
)
4237 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
4238 new_bb
= create_basic_block (insn
,
4239 insn
? get_last_insn () : NULL
,
4240 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
);
4242 BB_COPY_PARTITION (new_bb
, bb
);
4245 insn
= BB_HEADER (bb
);
4246 while (NEXT_INSN (insn
))
4247 insn
= NEXT_INSN (insn
);
4248 insn
= duplicate_insn_chain (BB_HEADER (bb
), insn
);
4250 BB_HEADER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4255 insn
= BB_FOOTER (bb
);
4256 while (NEXT_INSN (insn
))
4257 insn
= NEXT_INSN (insn
);
4258 insn
= duplicate_insn_chain (BB_FOOTER (bb
), insn
);
4260 BB_FOOTER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4267 /* Main entry point to this module - initialize the datastructures for
4268 CFG layout changes. It keeps LOOPS up-to-date if not null.
4270 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4273 cfg_layout_initialize (unsigned int flags
)
4278 /* Once bb partitioning is complete, cfg layout mode should not be
4279 re-entered. Entering cfg layout mode may require fixups. As an
4280 example, if edge forwarding performed when optimizing the cfg
4281 layout required moving a block from the hot to the cold
4282 section. This would create an illegal partitioning unless some
4283 manual fixup was performed. */
4284 gcc_assert (!(crtl
->bb_reorder_complete
4285 && flag_reorder_blocks_and_partition
));
4287 initialize_original_copy_tables ();
4289 cfg_layout_rtl_register_cfg_hooks ();
4291 record_effective_endpoints ();
4293 /* Make sure that the targets of non local gotos are marked. */
4294 for (x
= nonlocal_goto_handler_labels
; x
; x
= x
->next ())
4296 bb
= BLOCK_FOR_INSN (x
->insn ());
4297 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
4300 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
4303 /* Splits superblocks. */
4305 break_superblocks (void)
4307 sbitmap superblocks
;
4311 superblocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
4312 bitmap_clear (superblocks
);
4314 FOR_EACH_BB_FN (bb
, cfun
)
4315 if (bb
->flags
& BB_SUPERBLOCK
)
4317 bb
->flags
&= ~BB_SUPERBLOCK
;
4318 bitmap_set_bit (superblocks
, bb
->index
);
4324 rebuild_jump_labels (get_insns ());
4325 find_many_sub_basic_blocks (superblocks
);
4331 /* Finalize the changes: reorder insn list according to the sequence specified
4332 by aux pointers, enter compensation code, rebuild scope forest. */
4335 cfg_layout_finalize (void)
4337 #ifdef ENABLE_CHECKING
4338 verify_flow_info ();
4340 force_one_exit_fallthru ();
4341 rtl_register_cfg_hooks ();
4342 if (reload_completed
&& !HAVE_epilogue
)
4343 fixup_fallthru_exit_predecessor ();
4344 fixup_reorder_chain ();
4346 rebuild_jump_labels (get_insns ());
4347 delete_dead_jumptables ();
4349 #ifdef ENABLE_CHECKING
4350 verify_insn_chain ();
4351 verify_flow_info ();
4356 /* Same as split_block but update cfg_layout structures. */
4359 cfg_layout_split_block (basic_block bb
, void *insnp
)
4361 rtx insn
= (rtx
) insnp
;
4362 basic_block new_bb
= rtl_split_block (bb
, insn
);
4364 BB_FOOTER (new_bb
) = BB_FOOTER (bb
);
4365 BB_FOOTER (bb
) = NULL
;
4370 /* Redirect Edge to DEST. */
4372 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
4374 basic_block src
= e
->src
;
4377 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4380 if (e
->dest
== dest
)
4383 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4384 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
4386 df_set_bb_dirty (src
);
4390 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4391 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
4394 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
4395 e
->src
->index
, dest
->index
);
4397 df_set_bb_dirty (e
->src
);
4398 redirect_edge_succ (e
, dest
);
4402 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4403 in the case the basic block appears to be in sequence. Avoid this
4406 if (e
->flags
& EDGE_FALLTHRU
)
4408 /* Redirect any branch edges unified with the fallthru one. */
4409 if (JUMP_P (BB_END (src
))
4410 && label_is_jump_target_p (BB_HEAD (e
->dest
),
4416 fprintf (dump_file
, "Fallthru edge unified with branch "
4417 "%i->%i redirected to %i\n",
4418 e
->src
->index
, e
->dest
->index
, dest
->index
);
4419 e
->flags
&= ~EDGE_FALLTHRU
;
4420 redirected
= redirect_branch_edge (e
, dest
);
4421 gcc_assert (redirected
);
4422 redirected
->flags
|= EDGE_FALLTHRU
;
4423 df_set_bb_dirty (redirected
->src
);
4426 /* In case we are redirecting fallthru edge to the branch edge
4427 of conditional jump, remove it. */
4428 if (EDGE_COUNT (src
->succs
) == 2)
4430 /* Find the edge that is different from E. */
4431 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
4434 && any_condjump_p (BB_END (src
))
4435 && onlyjump_p (BB_END (src
)))
4436 delete_insn (BB_END (src
));
4439 fprintf (dump_file
, "Redirecting fallthru edge %i->%i to %i\n",
4440 e
->src
->index
, e
->dest
->index
, dest
->index
);
4441 ret
= redirect_edge_succ_nodup (e
, dest
);
4444 ret
= redirect_branch_edge (e
, dest
);
4446 /* We don't want simplejumps in the insn stream during cfglayout. */
4447 gcc_assert (!simplejump_p (BB_END (src
)));
4449 df_set_bb_dirty (src
);
4453 /* Simple wrapper as we always can redirect fallthru edges. */
4455 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
4457 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
4459 gcc_assert (redirected
);
4463 /* Same as delete_basic_block but update cfg_layout structures. */
4466 cfg_layout_delete_block (basic_block bb
)
4468 rtx_insn
*insn
, *next
, *prev
= PREV_INSN (BB_HEAD (bb
)), *remaints
;
4473 next
= BB_HEAD (bb
);
4475 SET_NEXT_INSN (prev
) = BB_HEADER (bb
);
4477 set_first_insn (BB_HEADER (bb
));
4478 SET_PREV_INSN (BB_HEADER (bb
)) = prev
;
4479 insn
= BB_HEADER (bb
);
4480 while (NEXT_INSN (insn
))
4481 insn
= NEXT_INSN (insn
);
4482 SET_NEXT_INSN (insn
) = next
;
4483 SET_PREV_INSN (next
) = insn
;
4485 next
= NEXT_INSN (BB_END (bb
));
4488 insn
= BB_FOOTER (bb
);
4491 if (BARRIER_P (insn
))
4493 if (PREV_INSN (insn
))
4494 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
4496 BB_FOOTER (bb
) = NEXT_INSN (insn
);
4497 if (NEXT_INSN (insn
))
4498 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
4502 insn
= NEXT_INSN (insn
);
4507 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
4508 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
4509 while (NEXT_INSN (insn
))
4510 insn
= NEXT_INSN (insn
);
4511 SET_NEXT_INSN (insn
) = next
;
4513 SET_PREV_INSN (next
) = insn
;
4515 set_last_insn (insn
);
4518 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
4519 to
= &BB_HEADER (bb
->next_bb
);
4521 to
= &cfg_layout_function_footer
;
4523 rtl_delete_block (bb
);
4526 prev
= NEXT_INSN (prev
);
4528 prev
= get_insns ();
4530 next
= PREV_INSN (next
);
4532 next
= get_last_insn ();
4534 if (next
&& NEXT_INSN (next
) != prev
)
4536 remaints
= unlink_insn_chain (prev
, next
);
4538 while (NEXT_INSN (insn
))
4539 insn
= NEXT_INSN (insn
);
4540 SET_NEXT_INSN (insn
) = *to
;
4542 SET_PREV_INSN (*to
) = insn
;
4547 /* Return true when blocks A and B can be safely merged. */
4550 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
4552 /* If we are partitioning hot/cold basic blocks, we don't want to
4553 mess up unconditional or indirect jumps that cross between hot
4556 Basic block partitioning may result in some jumps that appear to
4557 be optimizable (or blocks that appear to be mergeable), but which really
4558 must be left untouched (they are required to make it safely across
4559 partition boundaries). See the comments at the top of
4560 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4562 if (BB_PARTITION (a
) != BB_PARTITION (b
))
4565 /* Protect the loop latches. */
4566 if (current_loops
&& b
->loop_father
->latch
== b
)
4569 /* If we would end up moving B's instructions, make sure it doesn't fall
4570 through into the exit block, since we cannot recover from a fallthrough
4571 edge into the exit block occurring in the middle of a function. */
4572 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4574 edge e
= find_fallthru_edge (b
->succs
);
4575 if (e
&& e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4579 /* There must be exactly one edge in between the blocks. */
4580 return (single_succ_p (a
)
4581 && single_succ (a
) == b
4582 && single_pred_p (b
) == 1
4584 /* Must be simple edge. */
4585 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
4586 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4587 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
4588 /* If the jump insn has side effects, we can't kill the edge.
4589 When not optimizing, try_redirect_by_replacing_jump will
4590 not allow us to redirect an edge by replacing a table jump. */
4591 && (!JUMP_P (BB_END (a
))
4592 || ((!optimize
|| reload_completed
)
4593 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
4596 /* Merge block A and B. The blocks must be mergeable. */
4599 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
4601 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
4604 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a
, b
));
4607 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
4610 /* If there was a CODE_LABEL beginning B, delete it. */
4611 if (LABEL_P (BB_HEAD (b
)))
4613 delete_insn (BB_HEAD (b
));
4616 /* We should have fallthru edge in a, or we can do dummy redirection to get
4618 if (JUMP_P (BB_END (a
)))
4619 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
4620 gcc_assert (!JUMP_P (BB_END (a
)));
4622 /* When not optimizing and the edge is the only place in RTL which holds
4623 some unique locus, emit a nop with that locus in between. */
4625 emit_nop_for_unique_locus_between (a
, b
);
4627 /* Move things from b->footer after a->footer. */
4631 BB_FOOTER (a
) = BB_FOOTER (b
);
4634 rtx_insn
*last
= BB_FOOTER (a
);
4636 while (NEXT_INSN (last
))
4637 last
= NEXT_INSN (last
);
4638 SET_NEXT_INSN (last
) = BB_FOOTER (b
);
4639 SET_PREV_INSN (BB_FOOTER (b
)) = last
;
4641 BB_FOOTER (b
) = NULL
;
4644 /* Move things from b->header before a->footer.
4645 Note that this may include dead tablejump data, but we don't clean
4646 those up until we go out of cfglayout mode. */
4649 if (! BB_FOOTER (a
))
4650 BB_FOOTER (a
) = BB_HEADER (b
);
4653 rtx_insn
*last
= BB_HEADER (b
);
4655 while (NEXT_INSN (last
))
4656 last
= NEXT_INSN (last
);
4657 SET_NEXT_INSN (last
) = BB_FOOTER (a
);
4658 SET_PREV_INSN (BB_FOOTER (a
)) = last
;
4659 BB_FOOTER (a
) = BB_HEADER (b
);
4661 BB_HEADER (b
) = NULL
;
4664 /* In the case basic blocks are not adjacent, move them around. */
4665 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4667 insn
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
4669 emit_insn_after_noloc (insn
, BB_END (a
), a
);
4671 /* Otherwise just re-associate the instructions. */
4675 BB_END (a
) = BB_END (b
);
4678 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4679 We need to explicitly call. */
4680 update_bb_for_insn_chain (insn
, BB_END (b
), a
);
4682 /* Skip possible DELETED_LABEL insn. */
4683 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
4684 insn
= NEXT_INSN (insn
);
4685 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4686 BB_HEAD (b
) = BB_END (b
) = NULL
;
4689 df_bb_delete (b
->index
);
4691 /* If B was a forwarder block, propagate the locus on the edge. */
4693 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
4694 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
4697 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
4703 cfg_layout_split_edge (edge e
)
4705 basic_block new_bb
=
4706 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4707 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
4710 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4711 BB_COPY_PARTITION (new_bb
, e
->src
);
4713 BB_COPY_PARTITION (new_bb
, e
->dest
);
4714 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
4715 redirect_edge_and_branch_force (e
, new_bb
);
4720 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4723 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
4727 /* Return true if BB contains only labels or non-executable
4731 rtl_block_empty_p (basic_block bb
)
4735 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4736 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4739 FOR_BB_INSNS (bb
, insn
)
4740 if (NONDEBUG_INSN_P (insn
) && !any_uncondjump_p (insn
))
4746 /* Split a basic block if it ends with a conditional branch and if
4747 the other part of the block is not empty. */
4750 rtl_split_block_before_cond_jump (basic_block bb
)
4753 rtx_insn
*split_point
= NULL
;
4754 rtx_insn
*last
= NULL
;
4755 bool found_code
= false;
4757 FOR_BB_INSNS (bb
, insn
)
4759 if (any_condjump_p (insn
))
4761 else if (NONDEBUG_INSN_P (insn
))
4766 /* Did not find everything. */
4767 if (found_code
&& split_point
)
4768 return split_block (bb
, split_point
)->dest
;
4773 /* Return 1 if BB ends with a call, possibly followed by some
4774 instructions that must stay with the call, 0 otherwise. */
4777 rtl_block_ends_with_call_p (basic_block bb
)
4779 rtx_insn
*insn
= BB_END (bb
);
4781 while (!CALL_P (insn
)
4782 && insn
!= BB_HEAD (bb
)
4783 && (keep_with_call_p (insn
)
4785 || DEBUG_INSN_P (insn
)))
4786 insn
= PREV_INSN (insn
);
4787 return (CALL_P (insn
));
4790 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4793 rtl_block_ends_with_condjump_p (const_basic_block bb
)
4795 return any_condjump_p (BB_END (bb
));
4798 /* Return true if we need to add fake edge to exit.
4799 Helper function for rtl_flow_call_edges_add. */
4802 need_fake_edge_p (const rtx_insn
*insn
)
4808 && !SIBLING_CALL_P (insn
)
4809 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
4810 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
4813 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
4814 && MEM_VOLATILE_P (PATTERN (insn
)))
4815 || (GET_CODE (PATTERN (insn
)) == PARALLEL
4816 && asm_noperands (insn
) != -1
4817 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
4818 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
4821 /* Add fake edges to the function exit for any non constant and non noreturn
4822 calls, volatile inline assembly in the bitmap of blocks specified by
4823 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4826 The goal is to expose cases in which entering a basic block does not imply
4827 that all subsequent instructions must be executed. */
4830 rtl_flow_call_edges_add (sbitmap blocks
)
4833 int blocks_split
= 0;
4834 int last_bb
= last_basic_block_for_fn (cfun
);
4835 bool check_last_block
= false;
4837 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
4841 check_last_block
= true;
4843 check_last_block
= bitmap_bit_p (blocks
,
4844 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
->index
);
4846 /* In the last basic block, before epilogue generation, there will be
4847 a fallthru edge to EXIT. Special care is required if the last insn
4848 of the last basic block is a call because make_edge folds duplicate
4849 edges, which would result in the fallthru edge also being marked
4850 fake, which would result in the fallthru edge being removed by
4851 remove_fake_edges, which would result in an invalid CFG.
4853 Moreover, we can't elide the outgoing fake edge, since the block
4854 profiler needs to take this into account in order to solve the minimal
4855 spanning tree in the case that the call doesn't return.
4857 Handle this by adding a dummy instruction in a new last basic block. */
4858 if (check_last_block
)
4860 basic_block bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
4861 rtx_insn
*insn
= BB_END (bb
);
4863 /* Back up past insns that must be kept in the same block as a call. */
4864 while (insn
!= BB_HEAD (bb
)
4865 && keep_with_call_p (insn
))
4866 insn
= PREV_INSN (insn
);
4868 if (need_fake_edge_p (insn
))
4872 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4875 insert_insn_on_edge (gen_use (const0_rtx
), e
);
4876 commit_edge_insertions ();
4881 /* Now add fake edges to the function exit for any non constant
4882 calls since there is no way that we can determine if they will
4885 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
4887 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
4889 rtx_insn
*prev_insn
;
4894 if (blocks
&& !bitmap_bit_p (blocks
, i
))
4897 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
4899 prev_insn
= PREV_INSN (insn
);
4900 if (need_fake_edge_p (insn
))
4903 rtx_insn
*split_at_insn
= insn
;
4905 /* Don't split the block between a call and an insn that should
4906 remain in the same block as the call. */
4908 while (split_at_insn
!= BB_END (bb
)
4909 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
4910 split_at_insn
= NEXT_INSN (split_at_insn
);
4912 /* The handling above of the final block before the epilogue
4913 should be enough to verify that there is no edge to the exit
4914 block in CFG already. Calling make_edge in such case would
4915 cause us to mark that edge as fake and remove it later. */
4917 #ifdef ENABLE_CHECKING
4918 if (split_at_insn
== BB_END (bb
))
4920 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4921 gcc_assert (e
== NULL
);
4925 /* Note that the following may create a new basic block
4926 and renumber the existing basic blocks. */
4927 if (split_at_insn
!= BB_END (bb
))
4929 e
= split_block (bb
, split_at_insn
);
4934 make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
4937 if (insn
== BB_HEAD (bb
))
4943 verify_flow_info ();
4945 return blocks_split
;
4948 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4949 the conditional branch target, SECOND_HEAD should be the fall-thru
4950 there is no need to handle this here the loop versioning code handles
4951 this. the reason for SECON_HEAD is that it is needed for condition
4952 in trees, and this should be of the same type since it is a hook. */
4954 rtl_lv_add_condition_to_bb (basic_block first_head
,
4955 basic_block second_head ATTRIBUTE_UNUSED
,
4956 basic_block cond_bb
, void *comp_rtx
)
4958 rtx_code_label
*label
;
4959 rtx_insn
*seq
, *jump
;
4960 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
4961 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
4962 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
4966 label
= block_label (first_head
);
4967 mode
= GET_MODE (op0
);
4968 if (mode
== VOIDmode
)
4969 mode
= GET_MODE (op1
);
4972 op0
= force_operand (op0
, NULL_RTX
);
4973 op1
= force_operand (op1
, NULL_RTX
);
4974 do_compare_rtx_and_jump (op0
, op1
, comp
, 0, mode
, NULL_RTX
, NULL
, label
, -1);
4975 jump
= get_last_insn ();
4976 JUMP_LABEL (jump
) = label
;
4977 LABEL_NUSES (label
)++;
4981 /* Add the new cond, in the new head. */
4982 emit_insn_after (seq
, BB_END (cond_bb
));
4986 /* Given a block B with unconditional branch at its end, get the
4987 store the return the branch edge and the fall-thru edge in
4988 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4990 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
4991 edge
*fallthru_edge
)
4993 edge e
= EDGE_SUCC (b
, 0);
4995 if (e
->flags
& EDGE_FALLTHRU
)
4998 *branch_edge
= EDGE_SUCC (b
, 1);
5003 *fallthru_edge
= EDGE_SUCC (b
, 1);
5008 init_rtl_bb_info (basic_block bb
)
5010 gcc_assert (!bb
->il
.x
.rtl
);
5011 bb
->il
.x
.head_
= NULL
;
5012 bb
->il
.x
.rtl
= ggc_cleared_alloc
<rtl_bb_info
> ();
5015 /* Returns true if it is possible to remove edge E by redirecting
5016 it to the destination of the other edge from E->src. */
5019 rtl_can_remove_branch_p (const_edge e
)
5021 const_basic_block src
= e
->src
;
5022 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
5023 const rtx_insn
*insn
= BB_END (src
);
5026 /* The conditions are taken from try_redirect_by_replacing_jump. */
5027 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
5030 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
5033 if (BB_PARTITION (src
) != BB_PARTITION (target
))
5036 if (!onlyjump_p (insn
)
5037 || tablejump_p (insn
, NULL
, NULL
))
5040 set
= single_set (insn
);
5041 if (!set
|| side_effects_p (set
))
5048 rtl_duplicate_bb (basic_block bb
)
5050 bb
= cfg_layout_duplicate_bb (bb
);
5055 /* Do book-keeping of basic block BB for the profile consistency checker.
5056 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
5057 then do post-pass accounting. Store the counting in RECORD. */
5059 rtl_account_profile_record (basic_block bb
, int after_pass
,
5060 struct profile_record
*record
)
5063 FOR_BB_INSNS (bb
, insn
)
5066 record
->size
[after_pass
]
5067 += insn_rtx_cost (PATTERN (insn
), false);
5068 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
5069 record
->time
[after_pass
]
5070 += insn_rtx_cost (PATTERN (insn
), true) * bb
->count
;
5071 else if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
5072 record
->time
[after_pass
]
5073 += insn_rtx_cost (PATTERN (insn
), true) * bb
->frequency
;
5077 /* Implementation of CFG manipulation for linearized RTL. */
5078 struct cfg_hooks rtl_cfg_hooks
= {
5080 rtl_verify_flow_info
,
5082 rtl_dump_bb_for_graph
,
5083 rtl_create_basic_block
,
5084 rtl_redirect_edge_and_branch
,
5085 rtl_redirect_edge_and_branch_force
,
5086 rtl_can_remove_branch_p
,
5089 rtl_move_block_after
,
5090 rtl_can_merge_blocks
, /* can_merge_blocks_p */
5094 cfg_layout_can_duplicate_bb_p
,
5097 rtl_make_forwarder_block
,
5098 rtl_tidy_fallthru_edge
,
5099 rtl_force_nonfallthru
,
5100 rtl_block_ends_with_call_p
,
5101 rtl_block_ends_with_condjump_p
,
5102 rtl_flow_call_edges_add
,
5103 NULL
, /* execute_on_growing_pred */
5104 NULL
, /* execute_on_shrinking_pred */
5105 NULL
, /* duplicate loop for trees */
5106 NULL
, /* lv_add_condition_to_bb */
5107 NULL
, /* lv_adjust_loop_header_phi*/
5108 NULL
, /* extract_cond_bb_edges */
5109 NULL
, /* flush_pending_stmts */
5110 rtl_block_empty_p
, /* block_empty_p */
5111 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5112 rtl_account_profile_record
,
5115 /* Implementation of CFG manipulation for cfg layout RTL, where
5116 basic block connected via fallthru edges does not have to be adjacent.
5117 This representation will hopefully become the default one in future
5118 version of the compiler. */
5120 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
5122 rtl_verify_flow_info_1
,
5124 rtl_dump_bb_for_graph
,
5125 cfg_layout_create_basic_block
,
5126 cfg_layout_redirect_edge_and_branch
,
5127 cfg_layout_redirect_edge_and_branch_force
,
5128 rtl_can_remove_branch_p
,
5129 cfg_layout_delete_block
,
5130 cfg_layout_split_block
,
5131 rtl_move_block_after
,
5132 cfg_layout_can_merge_blocks_p
,
5133 cfg_layout_merge_blocks
,
5136 cfg_layout_can_duplicate_bb_p
,
5137 cfg_layout_duplicate_bb
,
5138 cfg_layout_split_edge
,
5139 rtl_make_forwarder_block
,
5140 NULL
, /* tidy_fallthru_edge */
5141 rtl_force_nonfallthru
,
5142 rtl_block_ends_with_call_p
,
5143 rtl_block_ends_with_condjump_p
,
5144 rtl_flow_call_edges_add
,
5145 NULL
, /* execute_on_growing_pred */
5146 NULL
, /* execute_on_shrinking_pred */
5147 duplicate_loop_to_header_edge
, /* duplicate loop for trees */
5148 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
5149 NULL
, /* lv_adjust_loop_header_phi*/
5150 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
5151 NULL
, /* flush_pending_stmts */
5152 rtl_block_empty_p
, /* block_empty_p */
5153 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5154 rtl_account_profile_record
,
5157 #include "gt-cfgrtl.h"