1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This file contains low level functions to manipulate the CFG and analyze it
21 that are aware of the RTL intermediate language.
23 Available functionality:
24 - Basic CFG/RTL manipulation API documented in cfghooks.h
25 - CFG-aware instruction chain manipulation
26 delete_insn, delete_insn_chain
27 - Edge splitting and committing to edges
28 insert_insn_on_edge, commit_edge_insertions
29 - CFG updating after insn simplification
30 purge_dead_edges, purge_all_dead_edges
31 - CFG fixing after coarse manipulation
34 Functions not supposed for generic use:
35 - Infrastructure to determine quickly basic block for insn
36 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
37 - Edge redirection with updating and optimizing of insn chain
38 block_label, tidy_fallthru_edge, force_nonfallthru */
42 #include "coretypes.h"
45 #include "hard-reg-set.h"
46 #include "basic-block.h"
47 #include "bb-reorder.h"
52 #include "rtl-error.h"
55 #include "insn-attr.h"
56 #include "insn-config.h"
59 #include "common/common-target.h"
62 #include "tree-pass.h"
65 /* Holds the interesting leading and trailing notes for the function.
66 Only applicable if the CFG is in cfglayout mode. */
67 static GTY(()) rtx cfg_layout_function_footer
;
68 static GTY(()) rtx cfg_layout_function_header
;
70 static rtx_insn
*skip_insns_after_block (basic_block
);
71 static void record_effective_endpoints (void);
72 static rtx
label_for_bb (basic_block
);
73 static void fixup_reorder_chain (void);
75 void verify_insn_chain (void);
76 static void fixup_fallthru_exit_predecessor (void);
77 static int can_delete_note_p (const rtx_note
*);
78 static int can_delete_label_p (const rtx_code_label
*);
79 static basic_block
rtl_split_edge (edge
);
80 static bool rtl_move_block_after (basic_block
, basic_block
);
81 static int rtl_verify_flow_info (void);
82 static basic_block
cfg_layout_split_block (basic_block
, void *);
83 static edge
cfg_layout_redirect_edge_and_branch (edge
, basic_block
);
84 static basic_block
cfg_layout_redirect_edge_and_branch_force (edge
, basic_block
);
85 static void cfg_layout_delete_block (basic_block
);
86 static void rtl_delete_block (basic_block
);
87 static basic_block
rtl_redirect_edge_and_branch_force (edge
, basic_block
);
88 static edge
rtl_redirect_edge_and_branch (edge
, basic_block
);
89 static basic_block
rtl_split_block (basic_block
, void *);
90 static void rtl_dump_bb (FILE *, basic_block
, int, int);
91 static int rtl_verify_flow_info_1 (void);
92 static void rtl_make_forwarder_block (edge
);
94 /* Return true if NOTE is not one of the ones that must be kept paired,
95 so that we may simply delete it. */
98 can_delete_note_p (const rtx_note
*note
)
100 switch (NOTE_KIND (note
))
102 case NOTE_INSN_DELETED
:
103 case NOTE_INSN_BASIC_BLOCK
:
104 case NOTE_INSN_EPILOGUE_BEG
:
112 /* True if a given label can be deleted. */
115 can_delete_label_p (const rtx_code_label
*label
)
117 return (!LABEL_PRESERVE_P (label
)
118 /* User declared labels must be preserved. */
119 && LABEL_NAME (label
) == 0
120 && !in_expr_list_p (forced_labels
, label
));
123 /* Delete INSN by patching it out. */
126 delete_insn (rtx insn
)
129 bool really_delete
= true;
133 /* Some labels can't be directly removed from the INSN chain, as they
134 might be references via variables, constant pool etc.
135 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
136 if (! can_delete_label_p (as_a
<rtx_code_label
*> (insn
)))
138 const char *name
= LABEL_NAME (insn
);
139 basic_block bb
= BLOCK_FOR_INSN (insn
);
140 rtx_insn
*bb_note
= NEXT_INSN (insn
);
142 really_delete
= false;
143 PUT_CODE (insn
, NOTE
);
144 NOTE_KIND (insn
) = NOTE_INSN_DELETED_LABEL
;
145 NOTE_DELETED_LABEL_NAME (insn
) = name
;
147 /* If the note following the label starts a basic block, and the
148 label is a member of the same basic block, interchange the two. */
149 if (bb_note
!= NULL_RTX
150 && NOTE_INSN_BASIC_BLOCK_P (bb_note
)
152 && bb
== BLOCK_FOR_INSN (bb_note
))
154 reorder_insns_nobb (insn
, insn
, bb_note
);
155 SET_BB_HEAD (bb
) = bb_note
;
156 if (BB_END (bb
) == bb_note
)
157 SET_BB_END (bb
) = insn
;
161 remove_node_from_expr_list (insn
, &nonlocal_goto_handler_labels
);
166 /* If this insn has already been deleted, something is very wrong. */
167 gcc_assert (!INSN_DELETED_P (insn
));
169 df_insn_delete (insn
);
171 INSN_DELETED_P (insn
) = 1;
174 /* If deleting a jump, decrement the use count of the label. Deleting
175 the label itself should happen in the normal course of block merging. */
178 if (JUMP_LABEL (insn
)
179 && LABEL_P (JUMP_LABEL (insn
)))
180 LABEL_NUSES (JUMP_LABEL (insn
))--;
182 /* If there are more targets, remove them too. */
184 = find_reg_note (insn
, REG_LABEL_TARGET
, NULL_RTX
)) != NULL_RTX
185 && LABEL_P (XEXP (note
, 0)))
187 LABEL_NUSES (XEXP (note
, 0))--;
188 remove_note (insn
, note
);
192 /* Also if deleting any insn that references a label as an operand. */
193 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, NULL_RTX
)) != NULL_RTX
194 && LABEL_P (XEXP (note
, 0)))
196 LABEL_NUSES (XEXP (note
, 0))--;
197 remove_note (insn
, note
);
200 if (rtx_jump_table_data
*table
= dyn_cast
<rtx_jump_table_data
*> (insn
))
202 rtvec vec
= table
->get_labels ();
203 int len
= GET_NUM_ELEM (vec
);
206 for (i
= 0; i
< len
; i
++)
208 rtx label
= XEXP (RTVEC_ELT (vec
, i
), 0);
210 /* When deleting code in bulk (e.g. removing many unreachable
211 blocks) we can delete a label that's a target of the vector
212 before deleting the vector itself. */
214 LABEL_NUSES (label
)--;
219 /* Like delete_insn but also purge dead edges from BB. */
222 delete_insn_and_edges (rtx_insn
*insn
)
227 && BLOCK_FOR_INSN (insn
)
228 && BB_END (BLOCK_FOR_INSN (insn
)) == insn
)
232 purge_dead_edges (BLOCK_FOR_INSN (insn
));
235 /* Unlink a chain of insns between START and FINISH, leaving notes
236 that must be paired. If CLEAR_BB is true, we set bb field for
237 insns that cannot be removed to NULL. */
240 delete_insn_chain (rtx start
, rtx finish
, bool clear_bb
)
242 rtx_insn
*prev
, *current
;
244 /* Unchain the insns one by one. It would be quicker to delete all of these
245 with a single unchaining, rather than one at a time, but we need to keep
247 current
= safe_as_a
<rtx_insn
*> (finish
);
250 prev
= PREV_INSN (current
);
251 if (NOTE_P (current
) && !can_delete_note_p (as_a
<rtx_note
*> (current
)))
254 delete_insn (current
);
256 if (clear_bb
&& !INSN_DELETED_P (current
))
257 set_block_for_insn (current
, NULL
);
259 if (current
== start
)
265 /* Create a new basic block consisting of the instructions between HEAD and END
266 inclusive. This function is designed to allow fast BB construction - reuses
267 the note and basic block struct in BB_NOTE, if any and do not grow
268 BASIC_BLOCK chain and should be used directly only by CFG construction code.
269 END can be NULL in to create new empty basic block before HEAD. Both END
270 and HEAD can be NULL to create basic block at the end of INSN chain.
271 AFTER is the basic block we should be put after. */
274 create_basic_block_structure (rtx head
, rtx end
, rtx_note
*bb_note
,
280 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
283 /* If we found an existing note, thread it back onto the chain. */
291 after
= PREV_INSN (head
);
295 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
296 reorder_insns_nobb (bb_note
, bb_note
, after
);
300 /* Otherwise we must create a note and a basic block structure. */
304 init_rtl_bb_info (bb
);
307 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
308 else if (LABEL_P (head
) && end
)
310 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
316 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
322 NOTE_BASIC_BLOCK (bb_note
) = bb
;
325 /* Always include the bb note in the block. */
326 if (NEXT_INSN (end
) == bb_note
)
329 SET_BB_HEAD (bb
) = head
;
330 SET_BB_END (bb
) = end
;
331 bb
->index
= last_basic_block_for_fn (cfun
)++;
332 bb
->flags
= BB_NEW
| BB_RTL
;
333 link_block (bb
, after
);
334 SET_BASIC_BLOCK_FOR_FN (cfun
, bb
->index
, bb
);
335 df_bb_refs_record (bb
->index
, false);
336 update_bb_for_insn (bb
);
337 BB_SET_PARTITION (bb
, BB_UNPARTITIONED
);
339 /* Tag the block so that we know it has been used when considering
340 other basic block notes. */
346 /* Create new basic block consisting of instructions in between HEAD and END
347 and place it to the BB chain after block AFTER. END can be NULL to
348 create a new empty basic block before HEAD. Both END and HEAD can be
349 NULL to create basic block at the end of INSN chain. */
352 rtl_create_basic_block (void *headp
, void *endp
, basic_block after
)
354 rtx head
= (rtx
) headp
, end
= (rtx
) endp
;
357 /* Grow the basic block array if needed. */
358 if ((size_t) last_basic_block_for_fn (cfun
)
359 >= basic_block_info_for_fn (cfun
)->length ())
362 (last_basic_block_for_fn (cfun
)
363 + (last_basic_block_for_fn (cfun
) + 3) / 4);
364 vec_safe_grow_cleared (basic_block_info_for_fn (cfun
), new_size
);
367 n_basic_blocks_for_fn (cfun
)++;
369 bb
= create_basic_block_structure (head
, end
, NULL
, after
);
375 cfg_layout_create_basic_block (void *head
, void *end
, basic_block after
)
377 basic_block newbb
= rtl_create_basic_block (head
, end
, after
);
382 /* Delete the insns in a (non-live) block. We physically delete every
383 non-deleted-note insn, and update the flow graph appropriately.
385 Return nonzero if we deleted an exception handler. */
387 /* ??? Preserving all such notes strikes me as wrong. It would be nice
388 to post-process the stream to remove empty blocks, loops, ranges, etc. */
391 rtl_delete_block (basic_block b
)
393 rtx_insn
*insn
, *end
;
395 /* If the head of this block is a CODE_LABEL, then it might be the
396 label for an exception handler which can't be reached. We need
397 to remove the label from the exception_handler_label list. */
400 end
= get_last_bb_insn (b
);
402 /* Selectively delete the entire chain. */
403 SET_BB_HEAD (b
) = NULL
;
404 delete_insn_chain (insn
, end
, true);
408 fprintf (dump_file
, "deleting block %d\n", b
->index
);
409 df_bb_delete (b
->index
);
412 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
415 compute_bb_for_insn (void)
419 FOR_EACH_BB_FN (bb
, cfun
)
421 rtx_insn
*end
= BB_END (bb
);
424 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
426 BLOCK_FOR_INSN (insn
) = bb
;
433 /* Release the basic_block_for_insn array. */
436 free_bb_for_insn (void)
439 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
440 if (!BARRIER_P (insn
))
441 BLOCK_FOR_INSN (insn
) = NULL
;
447 const pass_data pass_data_free_cfg
=
450 "*free_cfg", /* name */
451 OPTGROUP_NONE
, /* optinfo_flags */
453 0, /* properties_required */
454 0, /* properties_provided */
455 PROP_cfg
, /* properties_destroyed */
456 0, /* todo_flags_start */
457 0, /* todo_flags_finish */
460 class pass_free_cfg
: public rtl_opt_pass
463 pass_free_cfg (gcc::context
*ctxt
)
464 : rtl_opt_pass (pass_data_free_cfg
, ctxt
)
467 /* opt_pass methods: */
468 virtual unsigned int execute (function
*);
470 }; // class pass_free_cfg
473 pass_free_cfg::execute (function
*)
476 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
477 valid at that point so it would be too late to call df_analyze. */
478 if (optimize
> 0 && flag_delayed_branch
)
480 df_note_add_problem ();
485 if (crtl
->has_bb_partition
)
486 insert_section_boundary_note ();
495 make_pass_free_cfg (gcc::context
*ctxt
)
497 return new pass_free_cfg (ctxt
);
500 /* Return RTX to emit after when we want to emit code on the entry of function. */
502 entry_of_function (void)
504 return (n_basic_blocks_for_fn (cfun
) > NUM_FIXED_BLOCKS
?
505 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
) : get_insns ());
508 /* Emit INSN at the entry point of the function, ensuring that it is only
509 executed once per function. */
511 emit_insn_at_entry (rtx insn
)
513 edge_iterator ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
514 edge e
= ei_safe_edge (ei
);
515 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
517 insert_insn_on_edge (insn
, e
);
518 commit_edge_insertions ();
521 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
522 (or BARRIER if found) and notify df of the bb change.
523 The insn chain range is inclusive
524 (i.e. both BEGIN and END will be updated. */
527 update_bb_for_insn_chain (rtx_insn
*begin
, rtx_insn
*end
, basic_block bb
)
531 end
= NEXT_INSN (end
);
532 for (insn
= begin
; insn
!= end
; insn
= NEXT_INSN (insn
))
533 if (!BARRIER_P (insn
))
534 df_insn_change_bb (insn
, bb
);
537 /* Update BLOCK_FOR_INSN of insns in BB to BB,
538 and notify df of the change. */
541 update_bb_for_insn (basic_block bb
)
543 update_bb_for_insn_chain (BB_HEAD (bb
), BB_END (bb
), bb
);
547 /* Like active_insn_p, except keep the return value clobber around
548 even after reload. */
551 flow_active_insn_p (const rtx_insn
*insn
)
553 if (active_insn_p (insn
))
556 /* A clobber of the function return value exists for buggy
557 programs that fail to return a value. Its effect is to
558 keep the return value from being live across the entire
559 function. If we allow it to be skipped, we introduce the
560 possibility for register lifetime confusion. */
561 if (GET_CODE (PATTERN (insn
)) == CLOBBER
562 && REG_P (XEXP (PATTERN (insn
), 0))
563 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn
), 0)))
569 /* Return true if the block has no effect and only forwards control flow to
570 its single destination. */
573 contains_no_active_insn_p (const_basic_block bb
)
577 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
578 || !single_succ_p (bb
))
581 for (insn
= BB_HEAD (bb
); insn
!= BB_END (bb
); insn
= NEXT_INSN (insn
))
582 if (INSN_P (insn
) && flow_active_insn_p (insn
))
585 return (!INSN_P (insn
)
586 || (JUMP_P (insn
) && simplejump_p (insn
))
587 || !flow_active_insn_p (insn
));
590 /* Likewise, but protect loop latches, headers and preheaders. */
591 /* FIXME: Make this a cfg hook. */
594 forwarder_block_p (const_basic_block bb
)
596 if (!contains_no_active_insn_p (bb
))
599 /* Protect loop latches, headers and preheaders. */
603 if (bb
->loop_father
->header
== bb
)
605 dest
= EDGE_SUCC (bb
, 0)->dest
;
606 if (dest
->loop_father
->header
== dest
)
613 /* Return nonzero if we can reach target from src by falling through. */
614 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
617 can_fallthru (basic_block src
, basic_block target
)
619 rtx_insn
*insn
= BB_END (src
);
624 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
626 if (src
->next_bb
!= target
)
629 /* ??? Later we may add code to move jump tables offline. */
630 if (tablejump_p (insn
, NULL
, NULL
))
633 FOR_EACH_EDGE (e
, ei
, src
->succs
)
634 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
635 && e
->flags
& EDGE_FALLTHRU
)
638 insn2
= BB_HEAD (target
);
639 if (!active_insn_p (insn2
))
640 insn2
= next_active_insn (insn2
);
642 return next_active_insn (insn
) == insn2
;
645 /* Return nonzero if we could reach target from src by falling through,
646 if the target was made adjacent. If we already have a fall-through
647 edge to the exit block, we can't do that. */
649 could_fall_through (basic_block src
, basic_block target
)
654 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
656 FOR_EACH_EDGE (e
, ei
, src
->succs
)
657 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
658 && e
->flags
& EDGE_FALLTHRU
)
663 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
665 bb_note (basic_block bb
)
671 note
= NEXT_INSN (note
);
673 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
674 return as_a
<rtx_note
*> (note
);
677 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
678 note associated with the BLOCK. */
681 first_insn_after_basic_block_note (basic_block block
)
685 /* Get the first instruction in the block. */
686 insn
= BB_HEAD (block
);
688 if (insn
== NULL_RTX
)
691 insn
= NEXT_INSN (insn
);
692 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
694 return NEXT_INSN (insn
);
697 /* Creates a new basic block just after basic block B by splitting
698 everything after specified instruction I. */
701 rtl_split_block (basic_block bb
, void *insnp
)
704 rtx_insn
*insn
= (rtx_insn
*) insnp
;
710 insn
= first_insn_after_basic_block_note (bb
);
714 rtx_insn
*next
= insn
;
716 insn
= PREV_INSN (insn
);
718 /* If the block contains only debug insns, insn would have
719 been NULL in a non-debug compilation, and then we'd end
720 up emitting a DELETED note. For -fcompare-debug
721 stability, emit the note too. */
722 if (insn
!= BB_END (bb
)
723 && DEBUG_INSN_P (next
)
724 && DEBUG_INSN_P (BB_END (bb
)))
726 while (next
!= BB_END (bb
) && DEBUG_INSN_P (next
))
727 next
= NEXT_INSN (next
);
729 if (next
== BB_END (bb
))
730 emit_note_after (NOTE_INSN_DELETED
, next
);
734 insn
= get_last_insn ();
737 /* We probably should check type of the insn so that we do not create
738 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
740 if (insn
== BB_END (bb
))
741 emit_note_after (NOTE_INSN_DELETED
, insn
);
743 /* Create the new basic block. */
744 new_bb
= create_basic_block (NEXT_INSN (insn
), BB_END (bb
), bb
);
745 BB_COPY_PARTITION (new_bb
, bb
);
746 SET_BB_END (bb
) = insn
;
748 /* Redirect the outgoing edges. */
749 new_bb
->succs
= bb
->succs
;
751 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
754 /* The new block starts off being dirty. */
755 df_set_bb_dirty (bb
);
759 /* Return true if the single edge between blocks A and B is the only place
760 in RTL which holds some unique locus. */
763 unique_locus_on_edge_between_p (basic_block a
, basic_block b
)
765 const location_t goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
766 rtx_insn
*insn
, *end
;
768 if (LOCATION_LOCUS (goto_locus
) == UNKNOWN_LOCATION
)
771 /* First scan block A backward. */
773 end
= PREV_INSN (BB_HEAD (a
));
774 while (insn
!= end
&& (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
775 insn
= PREV_INSN (insn
);
777 if (insn
!= end
&& INSN_LOCATION (insn
) == goto_locus
)
780 /* Then scan block B forward. */
784 end
= NEXT_INSN (BB_END (b
));
785 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
786 insn
= NEXT_INSN (insn
);
788 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
789 && INSN_LOCATION (insn
) == goto_locus
)
796 /* If the single edge between blocks A and B is the only place in RTL which
797 holds some unique locus, emit a nop with that locus between the blocks. */
800 emit_nop_for_unique_locus_between (basic_block a
, basic_block b
)
802 if (!unique_locus_on_edge_between_p (a
, b
))
805 SET_BB_END (a
) = emit_insn_after_noloc (gen_nop (), BB_END (a
), a
);
806 INSN_LOCATION (BB_END (a
)) = EDGE_SUCC (a
, 0)->goto_locus
;
809 /* Blocks A and B are to be merged into a single block A. The insns
810 are already contiguous. */
813 rtl_merge_blocks (basic_block a
, basic_block b
)
815 rtx_insn
*b_head
= BB_HEAD (b
), *b_end
= BB_END (b
), *a_end
= BB_END (a
);
816 rtx_insn
*del_first
= NULL
, *del_last
= NULL
;
817 rtx_insn
*b_debug_start
= b_end
, *b_debug_end
= b_end
;
818 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
822 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
825 while (DEBUG_INSN_P (b_end
))
826 b_end
= PREV_INSN (b_debug_start
= b_end
);
828 /* If there was a CODE_LABEL beginning B, delete it. */
829 if (LABEL_P (b_head
))
831 /* Detect basic blocks with nothing but a label. This can happen
832 in particular at the end of a function. */
836 del_first
= del_last
= b_head
;
837 b_head
= NEXT_INSN (b_head
);
840 /* Delete the basic block note and handle blocks containing just that
842 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
850 b_head
= NEXT_INSN (b_head
);
853 /* If there was a jump out of A, delete it. */
858 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
860 || NOTE_INSN_BASIC_BLOCK_P (prev
)
861 || prev
== BB_HEAD (a
))
867 /* If this was a conditional jump, we need to also delete
868 the insn that set cc0. */
869 if (only_sets_cc0_p (prev
))
871 rtx_insn
*tmp
= prev
;
873 prev
= prev_nonnote_insn (prev
);
880 a_end
= PREV_INSN (del_first
);
882 else if (BARRIER_P (NEXT_INSN (a_end
)))
883 del_first
= NEXT_INSN (a_end
);
885 /* Delete everything marked above as well as crap that might be
886 hanging out between the two blocks. */
887 SET_BB_END (a
) = a_end
;
888 SET_BB_HEAD (b
) = b_empty
? NULL_RTX
: b_head
;
889 delete_insn_chain (del_first
, del_last
, true);
891 /* When not optimizing and the edge is the only place in RTL which holds
892 some unique locus, emit a nop with that locus in between. */
895 emit_nop_for_unique_locus_between (a
, b
);
899 /* Reassociate the insns of B with A. */
902 update_bb_for_insn_chain (a_end
, b_debug_end
, a
);
904 SET_BB_END (a
) = b_debug_end
;
905 SET_BB_HEAD (b
) = NULL_RTX
;
907 else if (b_end
!= b_debug_end
)
909 /* Move any deleted labels and other notes between the end of A
910 and the debug insns that make up B after the debug insns,
911 bringing the debug insns into A while keeping the notes after
913 if (NEXT_INSN (a_end
) != b_debug_start
)
914 reorder_insns_nobb (NEXT_INSN (a_end
), PREV_INSN (b_debug_start
),
916 update_bb_for_insn_chain (b_debug_start
, b_debug_end
, a
);
917 SET_BB_END (a
) = b_debug_end
;
920 df_bb_delete (b
->index
);
922 /* If B was a forwarder block, propagate the locus on the edge. */
924 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
925 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
928 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
932 /* Return true when block A and B can be merged. */
935 rtl_can_merge_blocks (basic_block a
, basic_block b
)
937 /* If we are partitioning hot/cold basic blocks, we don't want to
938 mess up unconditional or indirect jumps that cross between hot
941 Basic block partitioning may result in some jumps that appear to
942 be optimizable (or blocks that appear to be mergeable), but which really
943 must be left untouched (they are required to make it safely across
944 partition boundaries). See the comments at the top of
945 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
947 if (BB_PARTITION (a
) != BB_PARTITION (b
))
950 /* Protect the loop latches. */
951 if (current_loops
&& b
->loop_father
->latch
== b
)
954 /* There must be exactly one edge in between the blocks. */
955 return (single_succ_p (a
)
956 && single_succ (a
) == b
959 /* Must be simple edge. */
960 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
962 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
963 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
964 /* If the jump insn has side effects,
965 we can't kill the edge. */
966 && (!JUMP_P (BB_END (a
))
968 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
971 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
975 block_label (basic_block block
)
977 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
980 if (!LABEL_P (BB_HEAD (block
)))
982 SET_BB_HEAD (block
) = emit_label_before (gen_label_rtx (), BB_HEAD (block
));
985 return BB_HEAD (block
);
988 /* Attempt to perform edge redirection by replacing possibly complex jump
989 instruction by unconditional jump or removing jump completely. This can
990 apply only if all edges now point to the same block. The parameters and
991 return values are equivalent to redirect_edge_and_branch. */
994 try_redirect_by_replacing_jump (edge e
, basic_block target
, bool in_cfglayout
)
996 basic_block src
= e
->src
;
997 rtx_insn
*insn
= BB_END (src
), *kill_from
;
1001 /* If we are partitioning hot/cold basic blocks, we don't want to
1002 mess up unconditional or indirect jumps that cross between hot
1005 Basic block partitioning may result in some jumps that appear to
1006 be optimizable (or blocks that appear to be mergeable), but which really
1007 must be left untouched (they are required to make it safely across
1008 partition boundaries). See the comments at the top of
1009 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1011 if (BB_PARTITION (src
) != BB_PARTITION (target
))
1014 /* We can replace or remove a complex jump only when we have exactly
1015 two edges. Also, if we have exactly one outgoing edge, we can
1017 if (EDGE_COUNT (src
->succs
) >= 3
1018 /* Verify that all targets will be TARGET. Specifically, the
1019 edge that is not E must also go to TARGET. */
1020 || (EDGE_COUNT (src
->succs
) == 2
1021 && EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
))
1024 if (!onlyjump_p (insn
))
1026 if ((!optimize
|| reload_completed
) && tablejump_p (insn
, NULL
, NULL
))
1029 /* Avoid removing branch with side effects. */
1030 set
= single_set (insn
);
1031 if (!set
|| side_effects_p (set
))
1034 /* In case we zap a conditional jump, we'll need to kill
1035 the cc0 setter too. */
1038 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
))
1039 && only_sets_cc0_p (PREV_INSN (insn
)))
1040 kill_from
= PREV_INSN (insn
);
1043 /* See if we can create the fallthru edge. */
1044 if (in_cfglayout
|| can_fallthru (src
, target
))
1047 fprintf (dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
1050 /* Selectively unlink whole insn chain. */
1053 rtx_insn
*insn
= BB_FOOTER (src
);
1055 delete_insn_chain (kill_from
, BB_END (src
), false);
1057 /* Remove barriers but keep jumptables. */
1060 if (BARRIER_P (insn
))
1062 if (PREV_INSN (insn
))
1063 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
1065 BB_FOOTER (src
) = NEXT_INSN (insn
);
1066 if (NEXT_INSN (insn
))
1067 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
1071 insn
= NEXT_INSN (insn
);
1075 delete_insn_chain (kill_from
, PREV_INSN (BB_HEAD (target
)),
1079 /* If this already is simplejump, redirect it. */
1080 else if (simplejump_p (insn
))
1082 if (e
->dest
== target
)
1085 fprintf (dump_file
, "Redirecting jump %i from %i to %i.\n",
1086 INSN_UID (insn
), e
->dest
->index
, target
->index
);
1087 if (!redirect_jump (insn
, block_label (target
), 0))
1089 gcc_assert (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1094 /* Cannot do anything for target exit block. */
1095 else if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1098 /* Or replace possibly complicated jump insn by simple jump insn. */
1101 rtx target_label
= block_label (target
);
1104 rtx_jump_table_data
*table
;
1106 emit_jump_insn_after_noloc (gen_jump (target_label
), insn
);
1107 JUMP_LABEL (BB_END (src
)) = target_label
;
1108 LABEL_NUSES (target_label
)++;
1110 fprintf (dump_file
, "Replacing insn %i by jump %i\n",
1111 INSN_UID (insn
), INSN_UID (BB_END (src
)));
1114 delete_insn_chain (kill_from
, insn
, false);
1116 /* Recognize a tablejump that we are converting to a
1117 simple jump and remove its associated CODE_LABEL
1118 and ADDR_VEC or ADDR_DIFF_VEC. */
1119 if (tablejump_p (insn
, &label
, &table
))
1120 delete_insn_chain (label
, table
, false);
1122 barrier
= next_nonnote_insn (BB_END (src
));
1123 if (!barrier
|| !BARRIER_P (barrier
))
1124 emit_barrier_after (BB_END (src
));
1127 if (barrier
!= NEXT_INSN (BB_END (src
)))
1129 /* Move the jump before barrier so that the notes
1130 which originally were or were created before jump table are
1131 inside the basic block. */
1132 rtx_insn
*new_insn
= BB_END (src
);
1134 update_bb_for_insn_chain (NEXT_INSN (BB_END (src
)),
1135 PREV_INSN (barrier
), src
);
1137 SET_NEXT_INSN (PREV_INSN (new_insn
)) = NEXT_INSN (new_insn
);
1138 SET_PREV_INSN (NEXT_INSN (new_insn
)) = PREV_INSN (new_insn
);
1140 SET_NEXT_INSN (new_insn
) = barrier
;
1141 SET_NEXT_INSN (PREV_INSN (barrier
)) = new_insn
;
1143 SET_PREV_INSN (new_insn
) = PREV_INSN (barrier
);
1144 SET_PREV_INSN (barrier
) = new_insn
;
1149 /* Keep only one edge out and set proper flags. */
1150 if (!single_succ_p (src
))
1152 gcc_assert (single_succ_p (src
));
1154 e
= single_succ_edge (src
);
1156 e
->flags
= EDGE_FALLTHRU
;
1160 e
->probability
= REG_BR_PROB_BASE
;
1161 e
->count
= src
->count
;
1163 if (e
->dest
!= target
)
1164 redirect_edge_succ (e
, target
);
1168 /* Subroutine of redirect_branch_edge that tries to patch the jump
1169 instruction INSN so that it reaches block NEW. Do this
1170 only when it originally reached block OLD. Return true if this
1171 worked or the original target wasn't OLD, return false if redirection
1175 patch_jump_insn (rtx_insn
*insn
, rtx_insn
*old_label
, basic_block new_bb
)
1177 rtx_jump_table_data
*table
;
1179 /* Recognize a tablejump and adjust all matching cases. */
1180 if (tablejump_p (insn
, NULL
, &table
))
1184 rtx new_label
= block_label (new_bb
);
1186 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1188 vec
= table
->get_labels ();
1190 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
1191 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
1193 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
1194 --LABEL_NUSES (old_label
);
1195 ++LABEL_NUSES (new_label
);
1198 /* Handle casesi dispatch insns. */
1199 if ((tmp
= single_set (insn
)) != NULL
1200 && SET_DEST (tmp
) == pc_rtx
1201 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
1202 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
1203 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
1205 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (Pmode
,
1207 --LABEL_NUSES (old_label
);
1208 ++LABEL_NUSES (new_label
);
1211 else if ((tmp
= extract_asm_operands (PATTERN (insn
))) != NULL
)
1213 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (tmp
);
1214 rtx new_label
, note
;
1216 if (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1218 new_label
= block_label (new_bb
);
1220 for (i
= 0; i
< n
; ++i
)
1222 rtx old_ref
= ASM_OPERANDS_LABEL (tmp
, i
);
1223 gcc_assert (GET_CODE (old_ref
) == LABEL_REF
);
1224 if (XEXP (old_ref
, 0) == old_label
)
1226 ASM_OPERANDS_LABEL (tmp
, i
)
1227 = gen_rtx_LABEL_REF (Pmode
, new_label
);
1228 --LABEL_NUSES (old_label
);
1229 ++LABEL_NUSES (new_label
);
1233 if (JUMP_LABEL (insn
) == old_label
)
1235 JUMP_LABEL (insn
) = new_label
;
1236 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1238 remove_note (insn
, note
);
1242 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1244 remove_note (insn
, note
);
1245 if (JUMP_LABEL (insn
) != new_label
1246 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1247 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1249 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1251 XEXP (note
, 0) = new_label
;
1255 /* ?? We may play the games with moving the named labels from
1256 one basic block to the other in case only one computed_jump is
1258 if (computed_jump_p (insn
)
1259 /* A return instruction can't be redirected. */
1260 || returnjump_p (insn
))
1263 if (!currently_expanding_to_rtl
|| JUMP_LABEL (insn
) == old_label
)
1265 /* If the insn doesn't go where we think, we're confused. */
1266 gcc_assert (JUMP_LABEL (insn
) == old_label
);
1268 /* If the substitution doesn't succeed, die. This can happen
1269 if the back end emitted unrecognizable instructions or if
1270 target is exit block on some arches. */
1271 if (!redirect_jump (insn
, block_label (new_bb
), 0))
1273 gcc_assert (new_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
));
1282 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1285 redirect_branch_edge (edge e
, basic_block target
)
1287 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1288 basic_block src
= e
->src
;
1289 rtx_insn
*insn
= BB_END (src
);
1291 /* We can only redirect non-fallthru edges of jump insn. */
1292 if (e
->flags
& EDGE_FALLTHRU
)
1294 else if (!JUMP_P (insn
) && !currently_expanding_to_rtl
)
1297 if (!currently_expanding_to_rtl
)
1299 if (!patch_jump_insn (insn
, old_label
, target
))
1303 /* When expanding this BB might actually contain multiple
1304 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1305 Redirect all of those that match our label. */
1306 FOR_BB_INSNS (src
, insn
)
1307 if (JUMP_P (insn
) && !patch_jump_insn (insn
, old_label
, target
))
1311 fprintf (dump_file
, "Edge %i->%i redirected to %i\n",
1312 e
->src
->index
, e
->dest
->index
, target
->index
);
1314 if (e
->dest
!= target
)
1315 e
= redirect_edge_succ_nodup (e
, target
);
1320 /* Called when edge E has been redirected to a new destination,
1321 in order to update the region crossing flag on the edge and
1325 fixup_partition_crossing (edge e
)
1327 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
) || e
->dest
1328 == EXIT_BLOCK_PTR_FOR_FN (cfun
))
1330 /* If we redirected an existing edge, it may already be marked
1331 crossing, even though the new src is missing a reg crossing note.
1332 But make sure reg crossing note doesn't already exist before
1334 if (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1336 e
->flags
|= EDGE_CROSSING
;
1337 if (JUMP_P (BB_END (e
->src
))
1338 && !CROSSING_JUMP_P (BB_END (e
->src
)))
1339 CROSSING_JUMP_P (BB_END (e
->src
)) = 1;
1341 else if (BB_PARTITION (e
->src
) == BB_PARTITION (e
->dest
))
1343 e
->flags
&= ~EDGE_CROSSING
;
1344 /* Remove the section crossing note from jump at end of
1345 src if it exists, and if no other successors are
1347 if (JUMP_P (BB_END (e
->src
)) && CROSSING_JUMP_P (BB_END (e
->src
)))
1349 bool has_crossing_succ
= false;
1352 FOR_EACH_EDGE (e2
, ei
, e
->src
->succs
)
1354 has_crossing_succ
|= (e2
->flags
& EDGE_CROSSING
);
1355 if (has_crossing_succ
)
1358 if (!has_crossing_succ
)
1359 CROSSING_JUMP_P (BB_END (e
->src
)) = 0;
1364 /* Called when block BB has been reassigned to the cold partition,
1365 because it is now dominated by another cold block,
1366 to ensure that the region crossing attributes are updated. */
1369 fixup_new_cold_bb (basic_block bb
)
1374 /* This is called when a hot bb is found to now be dominated
1375 by a cold bb and therefore needs to become cold. Therefore,
1376 its preds will no longer be region crossing. Any non-dominating
1377 preds that were previously hot would also have become cold
1378 in the caller for the same region. Any preds that were previously
1379 region-crossing will be adjusted in fixup_partition_crossing. */
1380 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1382 fixup_partition_crossing (e
);
1385 /* Possibly need to make bb's successor edges region crossing,
1386 or remove stale region crossing. */
1387 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1389 /* We can't have fall-through edges across partition boundaries.
1390 Note that force_nonfallthru will do any necessary partition
1391 boundary fixup by calling fixup_partition_crossing itself. */
1392 if ((e
->flags
& EDGE_FALLTHRU
)
1393 && BB_PARTITION (bb
) != BB_PARTITION (e
->dest
)
1394 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1395 force_nonfallthru (e
);
1397 fixup_partition_crossing (e
);
1401 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1402 expense of adding new instructions or reordering basic blocks.
1404 Function can be also called with edge destination equivalent to the TARGET.
1405 Then it should try the simplifications and do nothing if none is possible.
1407 Return edge representing the branch if transformation succeeded. Return NULL
1409 We still return NULL in case E already destinated TARGET and we didn't
1410 managed to simplify instruction stream. */
1413 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
1416 basic_block src
= e
->src
;
1417 basic_block dest
= e
->dest
;
1419 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
1425 if ((ret
= try_redirect_by_replacing_jump (e
, target
, false)) != NULL
)
1427 df_set_bb_dirty (src
);
1428 fixup_partition_crossing (ret
);
1432 ret
= redirect_branch_edge (e
, target
);
1436 df_set_bb_dirty (src
);
1437 fixup_partition_crossing (ret
);
1441 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1444 emit_barrier_after_bb (basic_block bb
)
1446 rtx_barrier
*barrier
= emit_barrier_after (BB_END (bb
));
1447 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1448 || current_ir_type () == IR_RTL_CFGLAYOUT
);
1449 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
1450 BB_FOOTER (bb
) = unlink_insn_chain (barrier
, barrier
);
1453 /* Like force_nonfallthru below, but additionally performs redirection
1454 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1455 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1456 simple_return_rtx, indicating which kind of returnjump to create.
1457 It should be NULL otherwise. */
1460 force_nonfallthru_and_redirect (edge e
, basic_block target
, rtx jump_label
)
1462 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
1465 int abnormal_edge_flags
= 0;
1466 bool asm_goto_edge
= false;
1469 /* In the case the last instruction is conditional jump to the next
1470 instruction, first redirect the jump itself and then continue
1471 by creating a basic block afterwards to redirect fallthru edge. */
1472 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1473 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1474 && any_condjump_p (BB_END (e
->src
))
1475 && JUMP_LABEL (BB_END (e
->src
)) == BB_HEAD (e
->dest
))
1478 edge b
= unchecked_make_edge (e
->src
, target
, 0);
1481 redirected
= redirect_jump (BB_END (e
->src
), block_label (target
), 0);
1482 gcc_assert (redirected
);
1484 note
= find_reg_note (BB_END (e
->src
), REG_BR_PROB
, NULL_RTX
);
1487 int prob
= XINT (note
, 0);
1489 b
->probability
= prob
;
1490 /* Update this to use GCOV_COMPUTE_SCALE. */
1491 b
->count
= e
->count
* prob
/ REG_BR_PROB_BASE
;
1492 e
->probability
-= e
->probability
;
1493 e
->count
-= b
->count
;
1494 if (e
->probability
< 0)
1501 if (e
->flags
& EDGE_ABNORMAL
)
1503 /* Irritating special case - fallthru edge to the same block as abnormal
1505 We can't redirect abnormal edge, but we still can split the fallthru
1506 one and create separate abnormal edge to original destination.
1507 This allows bb-reorder to make such edge non-fallthru. */
1508 gcc_assert (e
->dest
== target
);
1509 abnormal_edge_flags
= e
->flags
& ~EDGE_FALLTHRU
;
1510 e
->flags
&= EDGE_FALLTHRU
;
1514 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
1515 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1517 /* We can't redirect the entry block. Create an empty block
1518 at the start of the function which we use to add the new
1524 basic_block bb
= create_basic_block (BB_HEAD (e
->dest
), NULL
,
1525 ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1527 /* Change the existing edge's source to be the new block, and add
1528 a new edge from the entry block to the new block. */
1530 for (ei
= ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
);
1531 (tmp
= ei_safe_edge (ei
)); )
1535 ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
->unordered_remove (ei
.index
);
1545 vec_safe_push (bb
->succs
, e
);
1546 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), bb
,
1551 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1552 don't point to the target or fallthru label. */
1553 if (JUMP_P (BB_END (e
->src
))
1554 && target
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1555 && (e
->flags
& EDGE_FALLTHRU
)
1556 && (note
= extract_asm_operands (PATTERN (BB_END (e
->src
)))))
1558 int i
, n
= ASM_OPERANDS_LABEL_LENGTH (note
);
1559 bool adjust_jump_target
= false;
1561 for (i
= 0; i
< n
; ++i
)
1563 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (e
->dest
))
1565 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))--;
1566 XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) = block_label (target
);
1567 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0))++;
1568 adjust_jump_target
= true;
1570 if (XEXP (ASM_OPERANDS_LABEL (note
, i
), 0) == BB_HEAD (target
))
1571 asm_goto_edge
= true;
1573 if (adjust_jump_target
)
1575 rtx_insn
*insn
= BB_END (e
->src
);
1577 rtx_insn
*old_label
= BB_HEAD (e
->dest
);
1578 rtx_insn
*new_label
= BB_HEAD (target
);
1580 if (JUMP_LABEL (insn
) == old_label
)
1582 JUMP_LABEL (insn
) = new_label
;
1583 note
= find_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1585 remove_note (insn
, note
);
1589 note
= find_reg_note (insn
, REG_LABEL_TARGET
, old_label
);
1591 remove_note (insn
, note
);
1592 if (JUMP_LABEL (insn
) != new_label
1593 && !find_reg_note (insn
, REG_LABEL_TARGET
, new_label
))
1594 add_reg_note (insn
, REG_LABEL_TARGET
, new_label
);
1596 while ((note
= find_reg_note (insn
, REG_LABEL_OPERAND
, old_label
))
1598 XEXP (note
, 0) = new_label
;
1602 if (EDGE_COUNT (e
->src
->succs
) >= 2 || abnormal_edge_flags
|| asm_goto_edge
)
1604 gcov_type count
= e
->count
;
1605 int probability
= e
->probability
;
1606 /* Create the new structures. */
1608 /* If the old block ended with a tablejump, skip its table
1609 by searching forward from there. Otherwise start searching
1610 forward from the last instruction of the old block. */
1611 rtx_jump_table_data
*table
;
1612 if (tablejump_p (BB_END (e
->src
), NULL
, &table
))
1615 note
= BB_END (e
->src
);
1616 note
= NEXT_INSN (note
);
1618 jump_block
= create_basic_block (note
, NULL
, e
->src
);
1619 jump_block
->count
= count
;
1620 jump_block
->frequency
= EDGE_FREQUENCY (e
);
1622 /* Make sure new block ends up in correct hot/cold section. */
1624 BB_COPY_PARTITION (jump_block
, e
->src
);
1627 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1628 new_edge
->probability
= probability
;
1629 new_edge
->count
= count
;
1631 /* Redirect old edge. */
1632 redirect_edge_pred (e
, jump_block
);
1633 e
->probability
= REG_BR_PROB_BASE
;
1635 /* If e->src was previously region crossing, it no longer is
1636 and the reg crossing note should be removed. */
1637 fixup_partition_crossing (new_edge
);
1639 /* If asm goto has any label refs to target's label,
1640 add also edge from asm goto bb to target. */
1643 new_edge
->probability
/= 2;
1644 new_edge
->count
/= 2;
1645 jump_block
->count
/= 2;
1646 jump_block
->frequency
/= 2;
1647 new_edge
= make_edge (new_edge
->src
, target
,
1648 e
->flags
& ~EDGE_FALLTHRU
);
1649 new_edge
->probability
= probability
- probability
/ 2;
1650 new_edge
->count
= count
- count
/ 2;
1653 new_bb
= jump_block
;
1656 jump_block
= e
->src
;
1658 loc
= e
->goto_locus
;
1659 e
->flags
&= ~EDGE_FALLTHRU
;
1660 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1662 if (jump_label
== ret_rtx
)
1665 emit_jump_insn_after_setloc (gen_return (), BB_END (jump_block
), loc
);
1672 gcc_assert (jump_label
== simple_return_rtx
);
1673 #ifdef HAVE_simple_return
1674 emit_jump_insn_after_setloc (gen_simple_return (),
1675 BB_END (jump_block
), loc
);
1680 set_return_jump_label (BB_END (jump_block
));
1684 rtx label
= block_label (target
);
1685 emit_jump_insn_after_setloc (gen_jump (label
), BB_END (jump_block
), loc
);
1686 JUMP_LABEL (BB_END (jump_block
)) = label
;
1687 LABEL_NUSES (label
)++;
1690 /* We might be in cfg layout mode, and if so, the following routine will
1691 insert the barrier correctly. */
1692 emit_barrier_after_bb (jump_block
);
1693 redirect_edge_succ_nodup (e
, target
);
1695 if (abnormal_edge_flags
)
1696 make_edge (src
, target
, abnormal_edge_flags
);
1698 df_mark_solutions_dirty ();
1699 fixup_partition_crossing (e
);
1703 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1704 (and possibly create new basic block) to make edge non-fallthru.
1705 Return newly created BB or NULL if none. */
1708 rtl_force_nonfallthru (edge e
)
1710 return force_nonfallthru_and_redirect (e
, e
->dest
, NULL_RTX
);
1713 /* Redirect edge even at the expense of creating new jump insn or
1714 basic block. Return new basic block if created, NULL otherwise.
1715 Conversion must be possible. */
1718 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1720 if (redirect_edge_and_branch (e
, target
)
1721 || e
->dest
== target
)
1724 /* In case the edge redirection failed, try to force it to be non-fallthru
1725 and redirect newly created simplejump. */
1726 df_set_bb_dirty (e
->src
);
1727 return force_nonfallthru_and_redirect (e
, target
, NULL_RTX
);
1730 /* The given edge should potentially be a fallthru edge. If that is in
1731 fact true, delete the jump and barriers that are in the way. */
1734 rtl_tidy_fallthru_edge (edge e
)
1737 basic_block b
= e
->src
, c
= b
->next_bb
;
1739 /* ??? In a late-running flow pass, other folks may have deleted basic
1740 blocks by nopping out blocks, leaving multiple BARRIERs between here
1741 and the target label. They ought to be chastised and fixed.
1743 We can also wind up with a sequence of undeletable labels between
1744 one block and the next.
1746 So search through a sequence of barriers, labels, and notes for
1747 the head of block C and assert that we really do fall through. */
1749 for (q
= NEXT_INSN (BB_END (b
)); q
!= BB_HEAD (c
); q
= NEXT_INSN (q
))
1753 /* Remove what will soon cease being the jump insn from the source block.
1754 If block B consisted only of this single jump, turn it into a deleted
1759 && (any_uncondjump_p (q
)
1760 || single_succ_p (b
)))
1763 /* If this was a conditional jump, we need to also delete
1764 the insn that set cc0. */
1765 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1772 /* Selectively unlink the sequence. */
1773 if (q
!= PREV_INSN (BB_HEAD (c
)))
1774 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (BB_HEAD (c
)), false);
1776 e
->flags
|= EDGE_FALLTHRU
;
1779 /* Should move basic block BB after basic block AFTER. NIY. */
1782 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED
,
1783 basic_block after ATTRIBUTE_UNUSED
)
1788 /* Locate the last bb in the same partition as START_BB. */
1791 last_bb_in_partition (basic_block start_bb
)
1794 FOR_BB_BETWEEN (bb
, start_bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
1796 if (BB_PARTITION (start_bb
) != BB_PARTITION (bb
->next_bb
))
1799 /* Return bb before the exit block. */
1803 /* Split a (typically critical) edge. Return the new block.
1804 The edge must not be abnormal.
1806 ??? The code generally expects to be called on critical edges.
1807 The case of a block ending in an unconditional jump to a
1808 block with multiple predecessors is not handled optimally. */
1811 rtl_split_edge (edge edge_in
)
1813 basic_block bb
, new_bb
;
1816 /* Abnormal edges cannot be split. */
1817 gcc_assert (!(edge_in
->flags
& EDGE_ABNORMAL
));
1819 /* We are going to place the new block in front of edge destination.
1820 Avoid existence of fallthru predecessors. */
1821 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1823 edge e
= find_fallthru_edge (edge_in
->dest
->preds
);
1826 force_nonfallthru (e
);
1829 /* Create the basic block note. */
1830 if (edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1831 before
= BB_HEAD (edge_in
->dest
);
1835 /* If this is a fall through edge to the exit block, the blocks might be
1836 not adjacent, and the right place is after the source. */
1837 if ((edge_in
->flags
& EDGE_FALLTHRU
)
1838 && edge_in
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1840 before
= NEXT_INSN (BB_END (edge_in
->src
));
1841 bb
= create_basic_block (before
, NULL
, edge_in
->src
);
1842 BB_COPY_PARTITION (bb
, edge_in
->src
);
1846 if (edge_in
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1848 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1849 BB_COPY_PARTITION (bb
, edge_in
->dest
);
1853 basic_block after
= edge_in
->dest
->prev_bb
;
1854 /* If this is post-bb reordering, and the edge crosses a partition
1855 boundary, the new block needs to be inserted in the bb chain
1856 at the end of the src partition (since we put the new bb into
1857 that partition, see below). Otherwise we may end up creating
1858 an extra partition crossing in the chain, which is illegal.
1859 It can't go after the src, because src may have a fall-through
1860 to a different block. */
1861 if (crtl
->bb_reorder_complete
1862 && (edge_in
->flags
& EDGE_CROSSING
))
1864 after
= last_bb_in_partition (edge_in
->src
);
1865 before
= NEXT_INSN (BB_END (after
));
1866 /* The instruction following the last bb in partition should
1867 be a barrier, since it cannot end in a fall-through. */
1868 gcc_checking_assert (BARRIER_P (before
));
1869 before
= NEXT_INSN (before
);
1871 bb
= create_basic_block (before
, NULL
, after
);
1872 /* Put the split bb into the src partition, to avoid creating
1873 a situation where a cold bb dominates a hot bb, in the case
1874 where src is cold and dest is hot. The src will dominate
1875 the new bb (whereas it might not have dominated dest). */
1876 BB_COPY_PARTITION (bb
, edge_in
->src
);
1880 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1882 /* Can't allow a region crossing edge to be fallthrough. */
1883 if (BB_PARTITION (bb
) != BB_PARTITION (edge_in
->dest
)
1884 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1886 new_bb
= force_nonfallthru (single_succ_edge (bb
));
1887 gcc_assert (!new_bb
);
1890 /* For non-fallthru edges, we must adjust the predecessor's
1891 jump instruction to target our new block. */
1892 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1894 edge redirected
= redirect_edge_and_branch (edge_in
, bb
);
1895 gcc_assert (redirected
);
1899 if (edge_in
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1901 /* For asm goto even splitting of fallthru edge might
1902 need insn patching, as other labels might point to the
1904 rtx_insn
*last
= BB_END (edge_in
->src
);
1907 && edge_in
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1908 && extract_asm_operands (PATTERN (last
)) != NULL_RTX
1909 && patch_jump_insn (last
, before
, bb
))
1910 df_set_bb_dirty (edge_in
->src
);
1912 redirect_edge_succ (edge_in
, bb
);
1918 /* Queue instructions for insertion on an edge between two basic blocks.
1919 The new instructions and basic blocks (if any) will not appear in the
1920 CFG until commit_edge_insertions is called. */
1923 insert_insn_on_edge (rtx pattern
, edge e
)
1925 /* We cannot insert instructions on an abnormal critical edge.
1926 It will be easier to find the culprit if we die now. */
1927 gcc_assert (!((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
)));
1929 if (e
->insns
.r
== NULL_RTX
)
1932 push_to_sequence (e
->insns
.r
);
1934 emit_insn (pattern
);
1936 e
->insns
.r
= get_insns ();
1940 /* Update the CFG for the instructions queued on edge E. */
1943 commit_one_edge_insertion (edge e
)
1945 rtx_insn
*before
= NULL
, *after
= NULL
, *insns
, *tmp
, *last
;
1948 /* Pull the insns off the edge now since the edge might go away. */
1952 /* Figure out where to put these insns. If the destination has
1953 one predecessor, insert there. Except for the exit block. */
1954 if (single_pred_p (e
->dest
) && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1958 /* Get the location correct wrt a code label, and "nice" wrt
1959 a basic block note, and before everything else. */
1962 tmp
= NEXT_INSN (tmp
);
1963 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1964 tmp
= NEXT_INSN (tmp
);
1965 if (tmp
== BB_HEAD (bb
))
1968 after
= PREV_INSN (tmp
);
1970 after
= get_last_insn ();
1973 /* If the source has one successor and the edge is not abnormal,
1974 insert there. Except for the entry block.
1975 Don't do this if the predecessor ends in a jump other than
1976 unconditional simple jump. E.g. for asm goto that points all
1977 its labels at the fallthru basic block, we can't insert instructions
1978 before the asm goto, as the asm goto can have various of side effects,
1979 and can't emit instructions after the asm goto, as it must end
1981 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1982 && single_succ_p (e
->src
)
1983 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1984 && (!JUMP_P (BB_END (e
->src
))
1985 || simplejump_p (BB_END (e
->src
))))
1989 /* It is possible to have a non-simple jump here. Consider a target
1990 where some forms of unconditional jumps clobber a register. This
1991 happens on the fr30 for example.
1993 We know this block has a single successor, so we can just emit
1994 the queued insns before the jump. */
1995 if (JUMP_P (BB_END (bb
)))
1996 before
= BB_END (bb
);
1999 /* We'd better be fallthru, or we've lost track of what's what. */
2000 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
2002 after
= BB_END (bb
);
2006 /* Otherwise we must split the edge. */
2009 bb
= split_edge (e
);
2011 /* If E crossed a partition boundary, we needed to make bb end in
2012 a region-crossing jump, even though it was originally fallthru. */
2013 if (JUMP_P (BB_END (bb
)))
2014 before
= BB_END (bb
);
2016 after
= BB_END (bb
);
2019 /* Now that we've found the spot, do the insertion. */
2022 emit_insn_before_noloc (insns
, before
, bb
);
2023 last
= prev_nonnote_insn (before
);
2026 last
= emit_insn_after_noloc (insns
, after
, bb
);
2028 if (returnjump_p (last
))
2030 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2031 This is not currently a problem because this only happens
2032 for the (single) epilogue, which already has a fallthru edge
2035 e
= single_succ_edge (bb
);
2036 gcc_assert (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
2037 && single_succ_p (bb
) && (e
->flags
& EDGE_FALLTHRU
));
2039 e
->flags
&= ~EDGE_FALLTHRU
;
2040 emit_barrier_after (last
);
2043 delete_insn (before
);
2046 gcc_assert (!JUMP_P (last
));
2049 /* Update the CFG for all queued instructions. */
2052 commit_edge_insertions (void)
2056 /* Optimization passes that invoke this routine can cause hot blocks
2057 previously reached by both hot and cold blocks to become dominated only
2058 by cold blocks. This will cause the verification below to fail,
2059 and lead to now cold code in the hot section. In some cases this
2060 may only be visible after newly unreachable blocks are deleted,
2061 which will be done by fixup_partitions. */
2062 fixup_partitions ();
2064 #ifdef ENABLE_CHECKING
2065 verify_flow_info ();
2068 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR_FOR_FN (cfun
),
2069 EXIT_BLOCK_PTR_FOR_FN (cfun
), next_bb
)
2074 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2076 commit_one_edge_insertion (e
);
2081 /* Print out RTL-specific basic block information (live information
2082 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2083 documented in dumpfile.h. */
2086 rtl_dump_bb (FILE *outf
, basic_block bb
, int indent
, int flags
)
2092 s_indent
= (char *) alloca ((size_t) indent
+ 1);
2093 memset (s_indent
, ' ', (size_t) indent
);
2094 s_indent
[indent
] = '\0';
2096 if (df
&& (flags
& TDF_DETAILS
))
2098 df_dump_top (bb
, outf
);
2102 if (bb
->index
!= ENTRY_BLOCK
&& bb
->index
!= EXIT_BLOCK
)
2103 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
)); insn
!= last
;
2104 insn
= NEXT_INSN (insn
))
2106 if (flags
& TDF_DETAILS
)
2107 df_dump_insn_top (insn
, outf
);
2108 if (! (flags
& TDF_SLIM
))
2109 print_rtl_single (outf
, insn
);
2111 dump_insn_slim (outf
, insn
);
2112 if (flags
& TDF_DETAILS
)
2113 df_dump_insn_bottom (insn
, outf
);
2116 if (df
&& (flags
& TDF_DETAILS
))
2118 df_dump_bottom (bb
, outf
);
2124 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2125 for the start of each basic block. FLAGS are the TDF_* masks documented
2129 print_rtl_with_bb (FILE *outf
, const_rtx rtx_first
, int flags
)
2133 fprintf (outf
, "(nil)\n");
2136 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
2137 int max_uid
= get_max_uid ();
2138 basic_block
*start
= XCNEWVEC (basic_block
, max_uid
);
2139 basic_block
*end
= XCNEWVEC (basic_block
, max_uid
);
2140 enum bb_state
*in_bb_p
= XCNEWVEC (enum bb_state
, max_uid
);
2143 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2144 insns, but the CFG is not maintained so the basic block info
2145 is not reliable. Therefore it's omitted from the dumps. */
2146 if (! (cfun
->curr_properties
& PROP_cfg
))
2147 flags
&= ~TDF_BLOCKS
;
2150 df_dump_start (outf
);
2152 if (flags
& TDF_BLOCKS
)
2154 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2158 start
[INSN_UID (BB_HEAD (bb
))] = bb
;
2159 end
[INSN_UID (BB_END (bb
))] = bb
;
2160 for (x
= BB_HEAD (bb
); x
!= NULL_RTX
; x
= NEXT_INSN (x
))
2162 enum bb_state state
= IN_MULTIPLE_BB
;
2164 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
2166 in_bb_p
[INSN_UID (x
)] = state
;
2168 if (x
== BB_END (bb
))
2174 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
2176 if (flags
& TDF_BLOCKS
)
2178 bb
= start
[INSN_UID (tmp_rtx
)];
2181 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, true, false);
2182 if (df
&& (flags
& TDF_DETAILS
))
2183 df_dump_top (bb
, outf
);
2186 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
2187 && !NOTE_P (tmp_rtx
)
2188 && !BARRIER_P (tmp_rtx
))
2189 fprintf (outf
, ";; Insn is not within a basic block\n");
2190 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
2191 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
2194 if (flags
& TDF_DETAILS
)
2195 df_dump_insn_top (tmp_rtx
, outf
);
2196 if (! (flags
& TDF_SLIM
))
2197 print_rtl_single (outf
, tmp_rtx
);
2199 dump_insn_slim (outf
, tmp_rtx
);
2200 if (flags
& TDF_DETAILS
)
2201 df_dump_insn_bottom (tmp_rtx
, outf
);
2203 if (flags
& TDF_BLOCKS
)
2205 bb
= end
[INSN_UID (tmp_rtx
)];
2208 dump_bb_info (outf
, bb
, 0, dump_flags
| TDF_COMMENT
, false, true);
2209 if (df
&& (flags
& TDF_DETAILS
))
2210 df_dump_bottom (bb
, outf
);
2222 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2225 update_br_prob_note (basic_block bb
)
2228 if (!JUMP_P (BB_END (bb
)))
2230 note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
);
2231 if (!note
|| XINT (note
, 0) == BRANCH_EDGE (bb
)->probability
)
2233 XINT (note
, 0) = BRANCH_EDGE (bb
)->probability
;
2236 /* Get the last insn associated with block BB (that includes barriers and
2237 tablejumps after BB). */
2239 get_last_bb_insn (basic_block bb
)
2241 rtx_jump_table_data
*table
;
2243 rtx_insn
*end
= BB_END (bb
);
2245 /* Include any jump table following the basic block. */
2246 if (tablejump_p (end
, NULL
, &table
))
2249 /* Include any barriers that may follow the basic block. */
2250 tmp
= next_nonnote_insn_bb (end
);
2251 while (tmp
&& BARRIER_P (tmp
))
2254 tmp
= next_nonnote_insn_bb (end
);
2260 /* Sanity check partition hotness to ensure that basic blocks in
2261 Â the cold partition don't dominate basic blocks in the hot partition.
2262 If FLAG_ONLY is true, report violations as errors. Otherwise
2263 re-mark the dominated blocks as cold, since this is run after
2264 cfg optimizations that may make hot blocks previously reached
2265 by both hot and cold blocks now only reachable along cold paths. */
2267 static vec
<basic_block
>
2268 find_partition_fixes (bool flag_only
)
2271 vec
<basic_block
> bbs_in_cold_partition
= vNULL
;
2272 vec
<basic_block
> bbs_to_fix
= vNULL
;
2274 /* Callers check this. */
2275 gcc_checking_assert (crtl
->has_bb_partition
);
2277 FOR_EACH_BB_FN (bb
, cfun
)
2278 if ((BB_PARTITION (bb
) == BB_COLD_PARTITION
))
2279 bbs_in_cold_partition
.safe_push (bb
);
2281 if (bbs_in_cold_partition
.is_empty ())
2284 bool dom_calculated_here
= !dom_info_available_p (CDI_DOMINATORS
);
2286 if (dom_calculated_here
)
2287 calculate_dominance_info (CDI_DOMINATORS
);
2289 while (! bbs_in_cold_partition
.is_empty ())
2291 bb
= bbs_in_cold_partition
.pop ();
2292 /* Any blocks dominated by a block in the cold section
2293 must also be cold. */
2295 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2297 son
= next_dom_son (CDI_DOMINATORS
, son
))
2299 /* If son is not yet cold, then mark it cold here and
2300 enqueue it for further processing. */
2301 if ((BB_PARTITION (son
) != BB_COLD_PARTITION
))
2304 error ("non-cold basic block %d dominated "
2305 "by a block in the cold partition (%d)", son
->index
, bb
->index
);
2307 BB_SET_PARTITION (son
, BB_COLD_PARTITION
);
2308 bbs_to_fix
.safe_push (son
);
2309 bbs_in_cold_partition
.safe_push (son
);
2314 if (dom_calculated_here
)
2315 free_dominance_info (CDI_DOMINATORS
);
2320 /* Perform cleanup on the hot/cold bb partitioning after optimization
2321 passes that modify the cfg. */
2324 fixup_partitions (void)
2328 if (!crtl
->has_bb_partition
)
2331 /* Delete any blocks that became unreachable and weren't
2332 already cleaned up, for example during edge forwarding
2333 and convert_jumps_to_returns. This will expose more
2334 opportunities for fixing the partition boundaries here.
2335 Also, the calculation of the dominance graph during verification
2336 will assert if there are unreachable nodes. */
2337 delete_unreachable_blocks ();
2339 /* If there are partitions, do a sanity check on them: A basic block in
2340 Â a cold partition cannot dominate a basic block in a hot partition.
2341 Fixup any that now violate this requirement, as a result of edge
2342 forwarding and unreachable block deletion. Â */
2343 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (false);
2345 /* Do the partition fixup after all necessary blocks have been converted to
2346 cold, so that we only update the region crossings the minimum number of
2347 places, which can require forcing edges to be non fallthru. */
2348 while (! bbs_to_fix
.is_empty ())
2350 bb
= bbs_to_fix
.pop ();
2351 fixup_new_cold_bb (bb
);
2355 /* Verify, in the basic block chain, that there is at most one switch
2356 between hot/cold partitions. This condition will not be true until
2357 after reorder_basic_blocks is called. */
2360 verify_hot_cold_block_grouping (void)
2364 bool switched_sections
= false;
2365 int current_partition
= BB_UNPARTITIONED
;
2367 /* Even after bb reordering is complete, we go into cfglayout mode
2368 again (in compgoto). Ensure we don't call this before going back
2369 into linearized RTL when any layout fixes would have been committed. */
2370 if (!crtl
->bb_reorder_complete
2371 || current_ir_type () != IR_RTL_CFGRTL
)
2374 FOR_EACH_BB_FN (bb
, cfun
)
2376 if (current_partition
!= BB_UNPARTITIONED
2377 && BB_PARTITION (bb
) != current_partition
)
2379 if (switched_sections
)
2381 error ("multiple hot/cold transitions found (bb %i)",
2386 switched_sections
= true;
2388 if (!crtl
->has_bb_partition
)
2389 error ("partition found but function partition flag not set");
2391 current_partition
= BB_PARTITION (bb
);
2398 /* Perform several checks on the edges out of each block, such as
2399 the consistency of the branch probabilities, the correctness
2400 of hot/cold partition crossing edges, and the number of expected
2401 successor edges. Also verify that the dominance relationship
2402 between hot/cold blocks is sane. */
2405 rtl_verify_edges (void)
2410 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2412 int n_fallthru
= 0, n_branch
= 0, n_abnormal_call
= 0, n_sibcall
= 0;
2413 int n_eh
= 0, n_abnormal
= 0;
2414 edge e
, fallthru
= NULL
;
2417 bool has_crossing_edge
= false;
2419 if (JUMP_P (BB_END (bb
))
2420 && (note
= find_reg_note (BB_END (bb
), REG_BR_PROB
, NULL_RTX
))
2421 && EDGE_COUNT (bb
->succs
) >= 2
2422 && any_condjump_p (BB_END (bb
)))
2424 if (XINT (note
, 0) != BRANCH_EDGE (bb
)->probability
2425 && profile_status_for_fn (cfun
) != PROFILE_ABSENT
)
2427 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2428 XINT (note
, 0), BRANCH_EDGE (bb
)->probability
);
2433 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2437 if (e
->flags
& EDGE_FALLTHRU
)
2438 n_fallthru
++, fallthru
= e
;
2440 is_crossing
= (BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
)
2441 && e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2442 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
2443 has_crossing_edge
|= is_crossing
;
2444 if (e
->flags
& EDGE_CROSSING
)
2448 error ("EDGE_CROSSING incorrectly set across same section");
2451 if (e
->flags
& EDGE_FALLTHRU
)
2453 error ("fallthru edge crosses section boundary in bb %i",
2457 if (e
->flags
& EDGE_EH
)
2459 error ("EH edge crosses section boundary in bb %i",
2463 if (JUMP_P (BB_END (bb
)) && !CROSSING_JUMP_P (BB_END (bb
)))
2465 error ("No region crossing jump at section boundary in bb %i",
2470 else if (is_crossing
)
2472 error ("EDGE_CROSSING missing across section boundary");
2476 if ((e
->flags
& ~(EDGE_DFS_BACK
2478 | EDGE_IRREDUCIBLE_LOOP
2481 | EDGE_PRESERVE
)) == 0)
2484 if (e
->flags
& EDGE_ABNORMAL_CALL
)
2487 if (e
->flags
& EDGE_SIBCALL
)
2490 if (e
->flags
& EDGE_EH
)
2493 if (e
->flags
& EDGE_ABNORMAL
)
2497 if (!has_crossing_edge
2498 && JUMP_P (BB_END (bb
))
2499 && CROSSING_JUMP_P (BB_END (bb
)))
2501 print_rtl_with_bb (stderr
, get_insns (), TDF_RTL
| TDF_BLOCKS
| TDF_DETAILS
);
2502 error ("Region crossing jump across same section in bb %i",
2507 if (n_eh
&& !find_reg_note (BB_END (bb
), REG_EH_REGION
, NULL_RTX
))
2509 error ("missing REG_EH_REGION note at the end of bb %i", bb
->index
);
2514 error ("too many exception handling edges in bb %i", bb
->index
);
2518 && (!JUMP_P (BB_END (bb
))
2519 || (n_branch
> 1 && (any_uncondjump_p (BB_END (bb
))
2520 || any_condjump_p (BB_END (bb
))))))
2522 error ("too many outgoing branch edges from bb %i", bb
->index
);
2525 if (n_fallthru
&& any_uncondjump_p (BB_END (bb
)))
2527 error ("fallthru edge after unconditional jump in bb %i", bb
->index
);
2530 if (n_branch
!= 1 && any_uncondjump_p (BB_END (bb
)))
2532 error ("wrong number of branch edges after unconditional jump"
2533 " in bb %i", bb
->index
);
2536 if (n_branch
!= 1 && any_condjump_p (BB_END (bb
))
2537 && JUMP_LABEL (BB_END (bb
)) != BB_HEAD (fallthru
->dest
))
2539 error ("wrong amount of branch edges after conditional jump"
2540 " in bb %i", bb
->index
);
2543 if (n_abnormal_call
&& !CALL_P (BB_END (bb
)))
2545 error ("abnormal call edges for non-call insn in bb %i", bb
->index
);
2548 if (n_sibcall
&& !CALL_P (BB_END (bb
)))
2550 error ("sibcall edges for non-call insn in bb %i", bb
->index
);
2553 if (n_abnormal
> n_eh
2554 && !(CALL_P (BB_END (bb
))
2555 && n_abnormal
== n_abnormal_call
+ n_sibcall
)
2556 && (!JUMP_P (BB_END (bb
))
2557 || any_condjump_p (BB_END (bb
))
2558 || any_uncondjump_p (BB_END (bb
))))
2560 error ("abnormal edges for no purpose in bb %i", bb
->index
);
2565 /* If there are partitions, do a sanity check on them: A basic block in
2566 Â a cold partition cannot dominate a basic block in a hot partition. Â */
2567 if (crtl
->has_bb_partition
&& !err
)
2569 vec
<basic_block
> bbs_to_fix
= find_partition_fixes (true);
2570 err
= !bbs_to_fix
.is_empty ();
2577 /* Checks on the instructions within blocks. Currently checks that each
2578 block starts with a basic block note, and that basic block notes and
2579 control flow jumps are not found in the middle of the block. */
2582 rtl_verify_bb_insns (void)
2588 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2590 /* Now check the header of basic
2591 block. It ought to contain optional CODE_LABEL followed
2592 by NOTE_BASIC_BLOCK. */
2596 if (BB_END (bb
) == x
)
2598 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2606 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2608 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2613 if (BB_END (bb
) == x
)
2614 /* Do checks for empty blocks here. */
2617 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2619 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2621 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2622 INSN_UID (x
), bb
->index
);
2626 if (x
== BB_END (bb
))
2629 if (control_flow_insn_p (x
))
2631 error ("in basic block %d:", bb
->index
);
2632 fatal_insn ("flow control insn inside a basic block", x
);
2641 /* Verify that block pointers for instructions in basic blocks, headers and
2642 footers are set appropriately. */
2645 rtl_verify_bb_pointers (void)
2650 /* Check the general integrity of the basic blocks. */
2651 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2655 if (!(bb
->flags
& BB_RTL
))
2657 error ("BB_RTL flag not set for block %d", bb
->index
);
2661 FOR_BB_INSNS (bb
, insn
)
2662 if (BLOCK_FOR_INSN (insn
) != bb
)
2664 error ("insn %d basic block pointer is %d, should be %d",
2666 BLOCK_FOR_INSN (insn
) ? BLOCK_FOR_INSN (insn
)->index
: 0,
2671 for (insn
= BB_HEADER (bb
); insn
; insn
= NEXT_INSN (insn
))
2672 if (!BARRIER_P (insn
)
2673 && BLOCK_FOR_INSN (insn
) != NULL
)
2675 error ("insn %d in header of bb %d has non-NULL basic block",
2676 INSN_UID (insn
), bb
->index
);
2679 for (insn
= BB_FOOTER (bb
); insn
; insn
= NEXT_INSN (insn
))
2680 if (!BARRIER_P (insn
)
2681 && BLOCK_FOR_INSN (insn
) != NULL
)
2683 error ("insn %d in footer of bb %d has non-NULL basic block",
2684 INSN_UID (insn
), bb
->index
);
2693 /* Verify the CFG and RTL consistency common for both underlying RTL and
2696 Currently it does following checks:
2698 - overlapping of basic blocks
2699 - insns with wrong BLOCK_FOR_INSN pointers
2700 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2701 - tails of basic blocks (ensure that boundary is necessary)
2702 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2703 and NOTE_INSN_BASIC_BLOCK
2704 - verify that no fall_thru edge crosses hot/cold partition boundaries
2705 - verify that there are no pending RTL branch predictions
2706 - verify that hot blocks are not dominated by cold blocks
2708 In future it can be extended check a lot of other stuff as well
2709 (reachability of basic blocks, life information, etc. etc.). */
2712 rtl_verify_flow_info_1 (void)
2716 err
|= rtl_verify_bb_pointers ();
2718 err
|= rtl_verify_bb_insns ();
2720 err
|= rtl_verify_edges ();
2725 /* Walk the instruction chain and verify that bb head/end pointers
2726 are correct, and that instructions are in exactly one bb and have
2727 correct block pointers. */
2730 rtl_verify_bb_insn_chain (void)
2735 rtx_insn
*last_head
= get_last_insn ();
2736 basic_block
*bb_info
;
2737 const int max_uid
= get_max_uid ();
2739 bb_info
= XCNEWVEC (basic_block
, max_uid
);
2741 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2743 rtx_insn
*head
= BB_HEAD (bb
);
2744 rtx_insn
*end
= BB_END (bb
);
2746 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2748 /* Verify the end of the basic block is in the INSN chain. */
2752 /* And that the code outside of basic blocks has NULL bb field. */
2754 && BLOCK_FOR_INSN (x
) != NULL
)
2756 error ("insn %d outside of basic blocks has non-NULL bb field",
2764 error ("end insn %d for block %d not found in the insn stream",
2765 INSN_UID (end
), bb
->index
);
2769 /* Work backwards from the end to the head of the basic block
2770 to verify the head is in the RTL chain. */
2771 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2773 /* While walking over the insn chain, verify insns appear
2774 in only one basic block. */
2775 if (bb_info
[INSN_UID (x
)] != NULL
)
2777 error ("insn %d is in multiple basic blocks (%d and %d)",
2778 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
2782 bb_info
[INSN_UID (x
)] = bb
;
2789 error ("head insn %d for block %d not found in the insn stream",
2790 INSN_UID (head
), bb
->index
);
2794 last_head
= PREV_INSN (x
);
2797 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
2799 /* Check that the code before the first basic block has NULL
2802 && BLOCK_FOR_INSN (x
) != NULL
)
2804 error ("insn %d outside of basic blocks has non-NULL bb field",
2814 /* Verify that fallthru edges point to adjacent blocks in layout order and
2815 that barriers exist after non-fallthru blocks. */
2818 rtl_verify_fallthru (void)
2823 FOR_EACH_BB_REVERSE_FN (bb
, cfun
)
2827 e
= find_fallthru_edge (bb
->succs
);
2832 /* Ensure existence of barrier in BB with no fallthru edges. */
2833 for (insn
= NEXT_INSN (BB_END (bb
)); ; insn
= NEXT_INSN (insn
))
2835 if (!insn
|| NOTE_INSN_BASIC_BLOCK_P (insn
))
2837 error ("missing barrier after block %i", bb
->index
);
2841 if (BARRIER_P (insn
))
2845 else if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
2846 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
2850 if (e
->src
->next_bb
!= e
->dest
)
2853 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2854 e
->src
->index
, e
->dest
->index
);
2858 for (insn
= NEXT_INSN (BB_END (e
->src
)); insn
!= BB_HEAD (e
->dest
);
2859 insn
= NEXT_INSN (insn
))
2860 if (BARRIER_P (insn
) || INSN_P (insn
))
2862 error ("verify_flow_info: Incorrect fallthru %i->%i",
2863 e
->src
->index
, e
->dest
->index
);
2864 fatal_insn ("wrong insn in the fallthru edge", insn
);
2873 /* Verify that blocks are laid out in consecutive order. While walking the
2874 instructions, verify that all expected instructions are inside the basic
2875 blocks, and that all returns are followed by barriers. */
2878 rtl_verify_bb_layout (void)
2884 rtx_insn
* const rtx_first
= get_insns ();
2885 basic_block last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
), curr_bb
= NULL
;
2888 last_bb_seen
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
2890 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2892 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2894 bb
= NOTE_BASIC_BLOCK (x
);
2897 if (bb
!= last_bb_seen
->next_bb
)
2898 internal_error ("basic blocks not laid down consecutively");
2900 curr_bb
= last_bb_seen
= bb
;
2905 switch (GET_CODE (x
))
2912 /* An ADDR_VEC is placed outside any basic block. */
2914 && JUMP_TABLE_DATA_P (NEXT_INSN (x
)))
2917 /* But in any case, non-deletable labels can appear anywhere. */
2921 fatal_insn ("insn outside basic block", x
);
2926 && returnjump_p (x
) && ! condjump_p (x
)
2927 && ! (next_nonnote_insn (x
) && BARRIER_P (next_nonnote_insn (x
))))
2928 fatal_insn ("return not followed by barrier", x
);
2930 if (curr_bb
&& x
== BB_END (curr_bb
))
2934 if (num_bb_notes
!= n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
)
2936 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2937 num_bb_notes
, n_basic_blocks_for_fn (cfun
));
2942 /* Verify the CFG and RTL consistency common for both underlying RTL and
2943 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
2945 Currently it does following checks:
2946 - all checks of rtl_verify_flow_info_1
2947 - test head/end pointers
2948 - check that blocks are laid out in consecutive order
2949 - check that all insns are in the basic blocks
2950 (except the switch handling code, barriers and notes)
2951 - check that all returns are followed by barriers
2952 - check that all fallthru edge points to the adjacent blocks
2953 - verify that there is a single hot/cold partition boundary after bbro */
2956 rtl_verify_flow_info (void)
2960 err
|= rtl_verify_flow_info_1 ();
2962 err
|= rtl_verify_bb_insn_chain ();
2964 err
|= rtl_verify_fallthru ();
2966 err
|= rtl_verify_bb_layout ();
2968 err
|= verify_hot_cold_block_grouping ();
2973 /* Assume that the preceding pass has possibly eliminated jump instructions
2974 or converted the unconditional jumps. Eliminate the edges from CFG.
2975 Return true if any edges are eliminated. */
2978 purge_dead_edges (basic_block bb
)
2981 rtx_insn
*insn
= BB_END (bb
);
2983 bool purged
= false;
2987 if (DEBUG_INSN_P (insn
) && insn
!= BB_HEAD (bb
))
2989 insn
= PREV_INSN (insn
);
2990 while ((DEBUG_INSN_P (insn
) || NOTE_P (insn
)) && insn
!= BB_HEAD (bb
));
2992 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2993 if (NONJUMP_INSN_P (insn
)
2994 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
2998 if (! may_trap_p (PATTERN (insn
))
2999 || ((eqnote
= find_reg_equal_equiv_note (insn
))
3000 && ! may_trap_p (XEXP (eqnote
, 0))))
3001 remove_note (insn
, note
);
3004 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3005 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3007 bool remove
= false;
3009 /* There are three types of edges we need to handle correctly here: EH
3010 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3011 latter can appear when nonlocal gotos are used. */
3012 if (e
->flags
& EDGE_ABNORMAL_CALL
)
3016 else if (can_nonlocal_goto (insn
))
3018 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3020 else if (flag_tm
&& find_reg_note (insn
, REG_TM
, NULL
))
3025 else if (e
->flags
& EDGE_EH
)
3026 remove
= !can_throw_internal (insn
);
3031 df_set_bb_dirty (bb
);
3044 /* We do care only about conditional jumps and simplejumps. */
3045 if (!any_condjump_p (insn
)
3046 && !returnjump_p (insn
)
3047 && !simplejump_p (insn
))
3050 /* Branch probability/prediction notes are defined only for
3051 condjumps. We've possibly turned condjump into simplejump. */
3052 if (simplejump_p (insn
))
3054 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3056 remove_note (insn
, note
);
3057 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
3058 remove_note (insn
, note
);
3061 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3063 /* Avoid abnormal flags to leak from computed jumps turned
3064 into simplejumps. */
3066 e
->flags
&= ~EDGE_ABNORMAL
;
3068 /* See if this edge is one we should keep. */
3069 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
3070 /* A conditional jump can fall through into the next
3071 block, so we should keep the edge. */
3076 else if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
3077 && BB_HEAD (e
->dest
) == JUMP_LABEL (insn
))
3078 /* If the destination block is the target of the jump,
3084 else if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
3085 && returnjump_p (insn
))
3086 /* If the destination block is the exit block, and this
3087 instruction is a return, then keep the edge. */
3092 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
3093 /* Keep the edges that correspond to exceptions thrown by
3094 this instruction and rematerialize the EDGE_ABNORMAL
3095 flag we just cleared above. */
3097 e
->flags
|= EDGE_ABNORMAL
;
3102 /* We do not need this edge. */
3103 df_set_bb_dirty (bb
);
3108 if (EDGE_COUNT (bb
->succs
) == 0 || !purged
)
3112 fprintf (dump_file
, "Purged edges from bb %i\n", bb
->index
);
3117 /* Redistribute probabilities. */
3118 if (single_succ_p (bb
))
3120 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3121 single_succ_edge (bb
)->count
= bb
->count
;
3125 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
3129 b
= BRANCH_EDGE (bb
);
3130 f
= FALLTHRU_EDGE (bb
);
3131 b
->probability
= XINT (note
, 0);
3132 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
3133 /* Update these to use GCOV_COMPUTE_SCALE. */
3134 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
3135 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
3140 else if (CALL_P (insn
) && SIBLING_CALL_P (insn
))
3142 /* First, there should not be any EH or ABCALL edges resulting
3143 from non-local gotos and the like. If there were, we shouldn't
3144 have created the sibcall in the first place. Second, there
3145 should of course never have been a fallthru edge. */
3146 gcc_assert (single_succ_p (bb
));
3147 gcc_assert (single_succ_edge (bb
)->flags
3148 == (EDGE_SIBCALL
| EDGE_ABNORMAL
));
3153 /* If we don't see a jump insn, we don't know exactly why the block would
3154 have been broken at this point. Look for a simple, non-fallthru edge,
3155 as these are only created by conditional branches. If we find such an
3156 edge we know that there used to be a jump here and can then safely
3157 remove all non-fallthru edges. */
3159 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3160 if (! (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
)))
3169 /* Remove all but the fake and fallthru edges. The fake edge may be
3170 the only successor for this block in the case of noreturn
3172 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
3174 if (!(e
->flags
& (EDGE_FALLTHRU
| EDGE_FAKE
)))
3176 df_set_bb_dirty (bb
);
3184 gcc_assert (single_succ_p (bb
));
3186 single_succ_edge (bb
)->probability
= REG_BR_PROB_BASE
;
3187 single_succ_edge (bb
)->count
= bb
->count
;
3190 fprintf (dump_file
, "Purged non-fallthru edges from bb %i\n",
3195 /* Search all basic blocks for potentially dead edges and purge them. Return
3196 true if some edge has been eliminated. */
3199 purge_all_dead_edges (void)
3204 FOR_EACH_BB_FN (bb
, cfun
)
3206 bool purged_here
= purge_dead_edges (bb
);
3208 purged
|= purged_here
;
3214 /* This is used by a few passes that emit some instructions after abnormal
3215 calls, moving the basic block's end, while they in fact do want to emit
3216 them on the fallthru edge. Look for abnormal call edges, find backward
3217 the call in the block and insert the instructions on the edge instead.
3219 Similarly, handle instructions throwing exceptions internally.
3221 Return true when instructions have been found and inserted on edges. */
3224 fixup_abnormal_edges (void)
3226 bool inserted
= false;
3229 FOR_EACH_BB_FN (bb
, cfun
)
3234 /* Look for cases we are interested in - calls or instructions causing
3236 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3237 if ((e
->flags
& EDGE_ABNORMAL_CALL
)
3238 || ((e
->flags
& (EDGE_ABNORMAL
| EDGE_EH
))
3239 == (EDGE_ABNORMAL
| EDGE_EH
)))
3242 if (e
&& !CALL_P (BB_END (bb
)) && !can_throw_internal (BB_END (bb
)))
3246 /* Get past the new insns generated. Allow notes, as the insns
3247 may be already deleted. */
3249 while ((NONJUMP_INSN_P (insn
) || NOTE_P (insn
))
3250 && !can_throw_internal (insn
)
3251 && insn
!= BB_HEAD (bb
))
3252 insn
= PREV_INSN (insn
);
3254 if (CALL_P (insn
) || can_throw_internal (insn
))
3256 rtx_insn
*stop
, *next
;
3258 e
= find_fallthru_edge (bb
->succs
);
3260 stop
= NEXT_INSN (BB_END (bb
));
3261 SET_BB_END (bb
) = insn
;
3263 for (insn
= NEXT_INSN (insn
); insn
!= stop
; insn
= next
)
3265 next
= NEXT_INSN (insn
);
3270 /* Sometimes there's still the return value USE.
3271 If it's placed after a trapping call (i.e. that
3272 call is the last insn anyway), we have no fallthru
3273 edge. Simply delete this use and don't try to insert
3274 on the non-existent edge. */
3275 if (GET_CODE (PATTERN (insn
)) != USE
)
3277 /* We're not deleting it, we're moving it. */
3278 INSN_DELETED_P (insn
) = 0;
3279 SET_PREV_INSN (insn
) = NULL_RTX
;
3280 SET_NEXT_INSN (insn
) = NULL_RTX
;
3282 insert_insn_on_edge (insn
, e
);
3286 else if (!BARRIER_P (insn
))
3287 set_block_for_insn (insn
, NULL
);
3291 /* It may be that we don't find any trapping insn. In this
3292 case we discovered quite late that the insn that had been
3293 marked as can_throw_internal in fact couldn't trap at all.
3294 So we should in fact delete the EH edges out of the block. */
3296 purge_dead_edges (bb
);
3303 /* Cut the insns from FIRST to LAST out of the insns stream. */
3306 unlink_insn_chain (rtx first
, rtx last
)
3308 rtx_insn
*prevfirst
= PREV_INSN (first
);
3309 rtx_insn
*nextlast
= NEXT_INSN (last
);
3311 SET_PREV_INSN (first
) = NULL
;
3312 SET_NEXT_INSN (last
) = NULL
;
3314 SET_NEXT_INSN (prevfirst
) = nextlast
;
3316 SET_PREV_INSN (nextlast
) = prevfirst
;
3318 set_last_insn (prevfirst
);
3320 set_first_insn (nextlast
);
3321 return as_a
<rtx_insn
*> (first
);
3324 /* Skip over inter-block insns occurring after BB which are typically
3325 associated with BB (e.g., barriers). If there are any such insns,
3326 we return the last one. Otherwise, we return the end of BB. */
3329 skip_insns_after_block (basic_block bb
)
3331 rtx_insn
*insn
, *last_insn
, *next_head
, *prev
;
3334 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3335 next_head
= BB_HEAD (bb
->next_bb
);
3337 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
3339 if (insn
== next_head
)
3342 switch (GET_CODE (insn
))
3349 switch (NOTE_KIND (insn
))
3351 case NOTE_INSN_BLOCK_END
:
3361 if (NEXT_INSN (insn
)
3362 && JUMP_TABLE_DATA_P (NEXT_INSN (insn
)))
3364 insn
= NEXT_INSN (insn
);
3377 /* It is possible to hit contradictory sequence. For instance:
3383 Where barrier belongs to jump_insn, but the note does not. This can be
3384 created by removing the basic block originally following
3385 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3387 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
3389 prev
= PREV_INSN (insn
);
3391 switch (NOTE_KIND (insn
))
3393 case NOTE_INSN_BLOCK_END
:
3396 case NOTE_INSN_DELETED
:
3397 case NOTE_INSN_DELETED_LABEL
:
3398 case NOTE_INSN_DELETED_DEBUG_LABEL
:
3401 reorder_insns (insn
, insn
, last_insn
);
3408 /* Locate or create a label for a given basic block. */
3411 label_for_bb (basic_block bb
)
3413 rtx label
= BB_HEAD (bb
);
3415 if (!LABEL_P (label
))
3418 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
3420 label
= block_label (bb
);
3426 /* Locate the effective beginning and end of the insn chain for each
3427 block, as defined by skip_insns_after_block above. */
3430 record_effective_endpoints (void)
3432 rtx_insn
*next_insn
;
3436 for (insn
= get_insns ();
3439 && NOTE_KIND (insn
) != NOTE_INSN_BASIC_BLOCK
;
3440 insn
= NEXT_INSN (insn
))
3442 /* No basic blocks at all? */
3445 if (PREV_INSN (insn
))
3446 cfg_layout_function_header
=
3447 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
3449 cfg_layout_function_header
= NULL_RTX
;
3451 next_insn
= get_insns ();
3452 FOR_EACH_BB_FN (bb
, cfun
)
3456 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
3457 SET_BB_HEADER (bb
) = unlink_insn_chain (next_insn
,
3458 PREV_INSN (BB_HEAD (bb
)));
3459 end
= skip_insns_after_block (bb
);
3460 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
3461 BB_FOOTER (bb
) = unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
3462 next_insn
= NEXT_INSN (BB_END (bb
));
3465 cfg_layout_function_footer
= next_insn
;
3466 if (cfg_layout_function_footer
)
3467 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
3472 const pass_data pass_data_into_cfg_layout_mode
=
3474 RTL_PASS
, /* type */
3475 "into_cfglayout", /* name */
3476 OPTGROUP_NONE
, /* optinfo_flags */
3478 0, /* properties_required */
3479 PROP_cfglayout
, /* properties_provided */
3480 0, /* properties_destroyed */
3481 0, /* todo_flags_start */
3482 0, /* todo_flags_finish */
3485 class pass_into_cfg_layout_mode
: public rtl_opt_pass
3488 pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3489 : rtl_opt_pass (pass_data_into_cfg_layout_mode
, ctxt
)
3492 /* opt_pass methods: */
3493 virtual unsigned int execute (function
*)
3495 cfg_layout_initialize (0);
3499 }; // class pass_into_cfg_layout_mode
3504 make_pass_into_cfg_layout_mode (gcc::context
*ctxt
)
3506 return new pass_into_cfg_layout_mode (ctxt
);
3511 const pass_data pass_data_outof_cfg_layout_mode
=
3513 RTL_PASS
, /* type */
3514 "outof_cfglayout", /* name */
3515 OPTGROUP_NONE
, /* optinfo_flags */
3517 0, /* properties_required */
3518 0, /* properties_provided */
3519 PROP_cfglayout
, /* properties_destroyed */
3520 0, /* todo_flags_start */
3521 0, /* todo_flags_finish */
3524 class pass_outof_cfg_layout_mode
: public rtl_opt_pass
3527 pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3528 : rtl_opt_pass (pass_data_outof_cfg_layout_mode
, ctxt
)
3531 /* opt_pass methods: */
3532 virtual unsigned int execute (function
*);
3534 }; // class pass_outof_cfg_layout_mode
3537 pass_outof_cfg_layout_mode::execute (function
*fun
)
3541 FOR_EACH_BB_FN (bb
, fun
)
3542 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
3543 bb
->aux
= bb
->next_bb
;
3545 cfg_layout_finalize ();
3553 make_pass_outof_cfg_layout_mode (gcc::context
*ctxt
)
3555 return new pass_outof_cfg_layout_mode (ctxt
);
3559 /* Link the basic blocks in the correct order, compacting the basic
3560 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3561 function also clears the basic block header and footer fields.
3563 This function is usually called after a pass (e.g. tracer) finishes
3564 some transformations while in cfglayout mode. The required sequence
3565 of the basic blocks is in a linked list along the bb->aux field.
3566 This functions re-links the basic block prev_bb and next_bb pointers
3567 accordingly, and it compacts and renumbers the blocks.
3569 FIXME: This currently works only for RTL, but the only RTL-specific
3570 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3571 to GIMPLE a long time ago, but it doesn't relink the basic block
3572 chain. It could do that (to give better initial RTL) if this function
3573 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3576 relink_block_chain (bool stay_in_cfglayout_mode
)
3578 basic_block bb
, prev_bb
;
3581 /* Maybe dump the re-ordered sequence. */
3584 fprintf (dump_file
, "Reordered sequence:\n");
3585 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
, index
=
3588 bb
= (basic_block
) bb
->aux
, index
++)
3590 fprintf (dump_file
, " %i ", index
);
3591 if (get_bb_original (bb
))
3592 fprintf (dump_file
, "duplicate of %i ",
3593 get_bb_original (bb
)->index
);
3594 else if (forwarder_block_p (bb
)
3595 && !LABEL_P (BB_HEAD (bb
)))
3596 fprintf (dump_file
, "compensation ");
3598 fprintf (dump_file
, "bb %i ", bb
->index
);
3599 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
3603 /* Now reorder the blocks. */
3604 prev_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
3605 bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
3606 for (; bb
; prev_bb
= bb
, bb
= (basic_block
) bb
->aux
)
3608 bb
->prev_bb
= prev_bb
;
3609 prev_bb
->next_bb
= bb
;
3611 prev_bb
->next_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
3612 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
= prev_bb
;
3614 /* Then, clean up the aux fields. */
3615 FOR_ALL_BB_FN (bb
, cfun
)
3618 if (!stay_in_cfglayout_mode
)
3619 SET_BB_HEADER (bb
) = BB_FOOTER (bb
) = NULL
;
3622 /* Maybe reset the original copy tables, they are not valid anymore
3623 when we renumber the basic blocks in compact_blocks. If we are
3624 are going out of cfglayout mode, don't re-allocate the tables. */
3625 free_original_copy_tables ();
3626 if (stay_in_cfglayout_mode
)
3627 initialize_original_copy_tables ();
3629 /* Finally, put basic_block_info in the new order. */
3634 /* Given a reorder chain, rearrange the code to match. */
3637 fixup_reorder_chain (void)
3642 if (cfg_layout_function_header
)
3644 set_first_insn (cfg_layout_function_header
);
3645 insn
= cfg_layout_function_header
;
3646 while (NEXT_INSN (insn
))
3647 insn
= NEXT_INSN (insn
);
3650 /* First do the bulk reordering -- rechain the blocks without regard to
3651 the needed changes to jumps and labels. */
3653 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3659 SET_NEXT_INSN (insn
) = BB_HEADER (bb
);
3661 set_first_insn (BB_HEADER (bb
));
3662 SET_PREV_INSN (BB_HEADER (bb
)) = insn
;
3663 insn
= BB_HEADER (bb
);
3664 while (NEXT_INSN (insn
))
3665 insn
= NEXT_INSN (insn
);
3668 SET_NEXT_INSN (insn
) = BB_HEAD (bb
);
3670 set_first_insn (BB_HEAD (bb
));
3671 SET_PREV_INSN (BB_HEAD (bb
)) = insn
;
3675 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
3676 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
3677 while (NEXT_INSN (insn
))
3678 insn
= NEXT_INSN (insn
);
3682 SET_NEXT_INSN (insn
) = cfg_layout_function_footer
;
3683 if (cfg_layout_function_footer
)
3684 SET_PREV_INSN (cfg_layout_function_footer
) = insn
;
3686 while (NEXT_INSN (insn
))
3687 insn
= NEXT_INSN (insn
);
3689 set_last_insn (insn
);
3690 #ifdef ENABLE_CHECKING
3691 verify_insn_chain ();
3694 /* Now add jumps and labels as needed to match the blocks new
3697 for (bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
; bb
; bb
= (basic_block
)
3700 edge e_fall
, e_taken
, e
;
3701 rtx_insn
*bb_end_insn
;
3702 rtx ret_label
= NULL_RTX
;
3706 if (EDGE_COUNT (bb
->succs
) == 0)
3709 /* Find the old fallthru edge, and another non-EH edge for
3711 e_taken
= e_fall
= NULL
;
3713 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3714 if (e
->flags
& EDGE_FALLTHRU
)
3716 else if (! (e
->flags
& EDGE_EH
))
3719 bb_end_insn
= BB_END (bb
);
3720 if (JUMP_P (bb_end_insn
))
3722 ret_label
= JUMP_LABEL (bb_end_insn
);
3723 if (any_condjump_p (bb_end_insn
))
3725 /* This might happen if the conditional jump has side
3726 effects and could therefore not be optimized away.
3727 Make the basic block to end with a barrier in order
3728 to prevent rtl_verify_flow_info from complaining. */
3731 gcc_assert (!onlyjump_p (bb_end_insn
)
3732 || returnjump_p (bb_end_insn
)
3733 || (e_taken
->flags
& EDGE_CROSSING
));
3734 emit_barrier_after (bb_end_insn
);
3738 /* If the old fallthru is still next, nothing to do. */
3739 if (bb
->aux
== e_fall
->dest
3740 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3743 /* The degenerated case of conditional jump jumping to the next
3744 instruction can happen for jumps with side effects. We need
3745 to construct a forwarder block and this will be done just
3746 fine by force_nonfallthru below. */
3750 /* There is another special case: if *neither* block is next,
3751 such as happens at the very end of a function, then we'll
3752 need to add a new unconditional jump. Choose the taken
3753 edge based on known or assumed probability. */
3754 else if (bb
->aux
!= e_taken
->dest
)
3756 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
3759 && XINT (note
, 0) < REG_BR_PROB_BASE
/ 2
3760 && invert_jump (bb_end_insn
,
3762 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3764 : label_for_bb (e_fall
->dest
)), 0))
3766 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3767 gcc_checking_assert (could_fall_through
3768 (e_taken
->src
, e_taken
->dest
));
3769 e_taken
->flags
|= EDGE_FALLTHRU
;
3770 update_br_prob_note (bb
);
3771 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
3775 /* If the "jumping" edge is a crossing edge, and the fall
3776 through edge is non-crossing, leave things as they are. */
3777 else if ((e_taken
->flags
& EDGE_CROSSING
)
3778 && !(e_fall
->flags
& EDGE_CROSSING
))
3781 /* Otherwise we can try to invert the jump. This will
3782 basically never fail, however, keep up the pretense. */
3783 else if (invert_jump (bb_end_insn
,
3785 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3787 : label_for_bb (e_fall
->dest
)), 0))
3789 e_fall
->flags
&= ~EDGE_FALLTHRU
;
3790 gcc_checking_assert (could_fall_through
3791 (e_taken
->src
, e_taken
->dest
));
3792 e_taken
->flags
|= EDGE_FALLTHRU
;
3793 update_br_prob_note (bb
);
3794 if (LABEL_NUSES (ret_label
) == 0
3795 && single_pred_p (e_taken
->dest
))
3796 delete_insn (ret_label
);
3800 else if (extract_asm_operands (PATTERN (bb_end_insn
)) != NULL
)
3802 /* If the old fallthru is still next or if
3803 asm goto doesn't have a fallthru (e.g. when followed by
3804 __builtin_unreachable ()), nothing to do. */
3806 || bb
->aux
== e_fall
->dest
3807 || e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3810 /* Otherwise we'll have to use the fallthru fixup below. */
3814 /* Otherwise we have some return, switch or computed
3815 jump. In the 99% case, there should not have been a
3817 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
3823 /* No fallthru implies a noreturn function with EH edges, or
3824 something similarly bizarre. In any case, we don't need to
3829 /* If the fallthru block is still next, nothing to do. */
3830 if (bb
->aux
== e_fall
->dest
)
3833 /* A fallthru to exit block. */
3834 if (e_fall
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3838 /* We got here if we need to add a new jump insn.
3839 Note force_nonfallthru can delete E_FALL and thus we have to
3840 save E_FALL->src prior to the call to force_nonfallthru. */
3841 nb
= force_nonfallthru_and_redirect (e_fall
, e_fall
->dest
, ret_label
);
3846 /* Don't process this new block. */
3851 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3853 /* Annoying special case - jump around dead jumptables left in the code. */
3854 FOR_EACH_BB_FN (bb
, cfun
)
3856 edge e
= find_fallthru_edge (bb
->succs
);
3858 if (e
&& !can_fallthru (e
->src
, e
->dest
))
3859 force_nonfallthru (e
);
3862 /* Ensure goto_locus from edges has some instructions with that locus
3865 FOR_EACH_BB_FN (bb
, cfun
)
3870 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3871 if (LOCATION_LOCUS (e
->goto_locus
) != UNKNOWN_LOCATION
3872 && !(e
->flags
& EDGE_ABNORMAL
))
3876 basic_block dest
, nb
;
3879 insn
= BB_END (e
->src
);
3880 end
= PREV_INSN (BB_HEAD (e
->src
));
3882 && (!NONDEBUG_INSN_P (insn
) || !INSN_HAS_LOCATION (insn
)))
3883 insn
= PREV_INSN (insn
);
3885 && INSN_LOCATION (insn
) == e
->goto_locus
)
3887 if (simplejump_p (BB_END (e
->src
))
3888 && !INSN_HAS_LOCATION (BB_END (e
->src
)))
3890 INSN_LOCATION (BB_END (e
->src
)) = e
->goto_locus
;
3894 if (dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3896 /* Non-fallthru edges to the exit block cannot be split. */
3897 if (!(e
->flags
& EDGE_FALLTHRU
))
3902 insn
= BB_HEAD (dest
);
3903 end
= NEXT_INSN (BB_END (dest
));
3904 while (insn
!= end
&& !NONDEBUG_INSN_P (insn
))
3905 insn
= NEXT_INSN (insn
);
3906 if (insn
!= end
&& INSN_HAS_LOCATION (insn
)
3907 && INSN_LOCATION (insn
) == e
->goto_locus
)
3910 nb
= split_edge (e
);
3911 if (!INSN_P (BB_END (nb
)))
3912 SET_BB_END (nb
) = emit_insn_after_noloc (gen_nop (), BB_END (nb
),
3914 INSN_LOCATION (BB_END (nb
)) = e
->goto_locus
;
3916 /* If there are other incoming edges to the destination block
3917 with the same goto locus, redirect them to the new block as
3918 well, this can prevent other such blocks from being created
3919 in subsequent iterations of the loop. */
3920 for (ei2
= ei_start (dest
->preds
); (e2
= ei_safe_edge (ei2
)); )
3921 if (LOCATION_LOCUS (e2
->goto_locus
) != UNKNOWN_LOCATION
3922 && !(e2
->flags
& (EDGE_ABNORMAL
| EDGE_FALLTHRU
))
3923 && e
->goto_locus
== e2
->goto_locus
)
3924 redirect_edge_and_branch (e2
, nb
);
3931 /* Perform sanity checks on the insn chain.
3932 1. Check that next/prev pointers are consistent in both the forward and
3934 2. Count insns in chain, going both directions, and check if equal.
3935 3. Check that get_last_insn () returns the actual end of chain. */
3938 verify_insn_chain (void)
3940 rtx_insn
*x
, *prevx
, *nextx
;
3941 int insn_cnt1
, insn_cnt2
;
3943 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
3945 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
3946 gcc_assert (PREV_INSN (x
) == prevx
);
3948 gcc_assert (prevx
== get_last_insn ());
3950 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
3952 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
3953 gcc_assert (NEXT_INSN (x
) == nextx
);
3955 gcc_assert (insn_cnt1
== insn_cnt2
);
3958 /* If we have assembler epilogues, the block falling through to exit must
3959 be the last one in the reordered chain when we reach final. Ensure
3960 that this condition is met. */
3962 fixup_fallthru_exit_predecessor (void)
3965 basic_block bb
= NULL
;
3967 /* This transformation is not valid before reload, because we might
3968 separate a call from the instruction that copies the return
3970 gcc_assert (reload_completed
);
3972 e
= find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
3978 basic_block c
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
;
3980 /* If the very first block is the one with the fall-through exit
3981 edge, we have to split that block. */
3984 bb
= split_block (bb
, NULL
)->dest
;
3987 BB_FOOTER (bb
) = BB_FOOTER (c
);
3988 BB_FOOTER (c
) = NULL
;
3991 while (c
->aux
!= bb
)
3992 c
= (basic_block
) c
->aux
;
3996 c
= (basic_block
) c
->aux
;
4003 /* In case there are more than one fallthru predecessors of exit, force that
4004 there is only one. */
4007 force_one_exit_fallthru (void)
4009 edge e
, predecessor
= NULL
;
4012 basic_block forwarder
, bb
;
4014 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
)
4015 if (e
->flags
& EDGE_FALLTHRU
)
4017 if (predecessor
== NULL
)
4029 /* Exit has several fallthru predecessors. Create a forwarder block for
4031 forwarder
= split_edge (predecessor
);
4032 for (ei
= ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun
)->preds
);
4033 (e
= ei_safe_edge (ei
)); )
4035 if (e
->src
== forwarder
4036 || !(e
->flags
& EDGE_FALLTHRU
))
4039 redirect_edge_and_branch_force (e
, forwarder
);
4042 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4044 FOR_EACH_BB_FN (bb
, cfun
)
4046 if (bb
->aux
== NULL
&& bb
!= forwarder
)
4048 bb
->aux
= forwarder
;
4054 /* Return true in case it is possible to duplicate the basic block BB. */
4057 cfg_layout_can_duplicate_bb_p (const_basic_block bb
)
4059 /* Do not attempt to duplicate tablejumps, as we need to unshare
4060 the dispatch table. This is difficult to do, as the instructions
4061 computing jump destination may be hoisted outside the basic block. */
4062 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
4065 /* Do not duplicate blocks containing insns that can't be copied. */
4066 if (targetm
.cannot_copy_insn_p
)
4068 rtx_insn
*insn
= BB_HEAD (bb
);
4071 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
4073 if (insn
== BB_END (bb
))
4075 insn
= NEXT_INSN (insn
);
4083 duplicate_insn_chain (rtx from
, rtx to
)
4085 rtx insn
, next
, copy
;
4088 /* Avoid updating of boundaries of previous basic block. The
4089 note will get removed from insn stream in fixup. */
4090 last
= emit_note (NOTE_INSN_DELETED
);
4092 /* Create copy at the end of INSN chain. The chain will
4093 be reordered later. */
4094 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
4096 switch (GET_CODE (insn
))
4099 /* Don't duplicate label debug insns. */
4100 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
)
4106 copy
= emit_copy_of_insn_after (insn
, get_last_insn ());
4107 if (JUMP_P (insn
) && JUMP_LABEL (insn
) != NULL_RTX
4108 && ANY_RETURN_P (JUMP_LABEL (insn
)))
4109 JUMP_LABEL (copy
) = JUMP_LABEL (insn
);
4110 maybe_copy_prologue_epilogue_insn (insn
, copy
);
4113 case JUMP_TABLE_DATA
:
4114 /* Avoid copying of dispatch tables. We never duplicate
4115 tablejumps, so this can hit only in case the table got
4116 moved far from original jump.
4117 Avoid copying following barrier as well if any
4118 (and debug insns in between). */
4119 for (next
= NEXT_INSN (insn
);
4120 next
!= NEXT_INSN (to
);
4121 next
= NEXT_INSN (next
))
4122 if (!DEBUG_INSN_P (next
))
4124 if (next
!= NEXT_INSN (to
) && BARRIER_P (next
))
4136 switch (NOTE_KIND (insn
))
4138 /* In case prologue is empty and function contain label
4139 in first BB, we may want to copy the block. */
4140 case NOTE_INSN_PROLOGUE_END
:
4142 case NOTE_INSN_DELETED
:
4143 case NOTE_INSN_DELETED_LABEL
:
4144 case NOTE_INSN_DELETED_DEBUG_LABEL
:
4145 /* No problem to strip these. */
4146 case NOTE_INSN_FUNCTION_BEG
:
4147 /* There is always just single entry to function. */
4148 case NOTE_INSN_BASIC_BLOCK
:
4149 /* We should only switch text sections once. */
4150 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
4153 case NOTE_INSN_EPILOGUE_BEG
:
4154 emit_note_copy (as_a
<rtx_note
*> (insn
));
4158 /* All other notes should have already been eliminated. */
4166 insn
= NEXT_INSN (last
);
4168 return safe_as_a
<rtx_insn
*> (insn
);
4171 /* Create a duplicate of the basic block BB. */
4174 cfg_layout_duplicate_bb (basic_block bb
)
4179 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
4180 new_bb
= create_basic_block (insn
,
4181 insn
? get_last_insn () : NULL
,
4182 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
);
4184 BB_COPY_PARTITION (new_bb
, bb
);
4187 insn
= BB_HEADER (bb
);
4188 while (NEXT_INSN (insn
))
4189 insn
= NEXT_INSN (insn
);
4190 insn
= duplicate_insn_chain (BB_HEADER (bb
), insn
);
4192 SET_BB_HEADER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4197 insn
= BB_FOOTER (bb
);
4198 while (NEXT_INSN (insn
))
4199 insn
= NEXT_INSN (insn
);
4200 insn
= duplicate_insn_chain (BB_FOOTER (bb
), insn
);
4202 BB_FOOTER (new_bb
) = unlink_insn_chain (insn
, get_last_insn ());
4209 /* Main entry point to this module - initialize the datastructures for
4210 CFG layout changes. It keeps LOOPS up-to-date if not null.
4212 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4215 cfg_layout_initialize (unsigned int flags
)
4220 /* Once bb partitioning is complete, cfg layout mode should not be
4221 re-entered. Entering cfg layout mode may require fixups. As an
4222 example, if edge forwarding performed when optimizing the cfg
4223 layout required moving a block from the hot to the cold
4224 section. This would create an illegal partitioning unless some
4225 manual fixup was performed. */
4226 gcc_assert (!(crtl
->bb_reorder_complete
4227 && flag_reorder_blocks_and_partition
));
4229 initialize_original_copy_tables ();
4231 cfg_layout_rtl_register_cfg_hooks ();
4233 record_effective_endpoints ();
4235 /* Make sure that the targets of non local gotos are marked. */
4236 for (x
= nonlocal_goto_handler_labels
; x
; x
= XEXP (x
, 1))
4238 bb
= BLOCK_FOR_INSN (XEXP (x
, 0));
4239 bb
->flags
|= BB_NON_LOCAL_GOTO_TARGET
;
4242 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
4245 /* Splits superblocks. */
4247 break_superblocks (void)
4249 sbitmap superblocks
;
4253 superblocks
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
4254 bitmap_clear (superblocks
);
4256 FOR_EACH_BB_FN (bb
, cfun
)
4257 if (bb
->flags
& BB_SUPERBLOCK
)
4259 bb
->flags
&= ~BB_SUPERBLOCK
;
4260 bitmap_set_bit (superblocks
, bb
->index
);
4266 rebuild_jump_labels (get_insns ());
4267 find_many_sub_basic_blocks (superblocks
);
4273 /* Finalize the changes: reorder insn list according to the sequence specified
4274 by aux pointers, enter compensation code, rebuild scope forest. */
4277 cfg_layout_finalize (void)
4279 #ifdef ENABLE_CHECKING
4280 verify_flow_info ();
4282 force_one_exit_fallthru ();
4283 rtl_register_cfg_hooks ();
4284 if (reload_completed
4285 #ifdef HAVE_epilogue
4289 fixup_fallthru_exit_predecessor ();
4290 fixup_reorder_chain ();
4292 rebuild_jump_labels (get_insns ());
4293 delete_dead_jumptables ();
4295 #ifdef ENABLE_CHECKING
4296 verify_insn_chain ();
4297 verify_flow_info ();
4302 /* Same as split_block but update cfg_layout structures. */
4305 cfg_layout_split_block (basic_block bb
, void *insnp
)
4307 rtx insn
= (rtx
) insnp
;
4308 basic_block new_bb
= rtl_split_block (bb
, insn
);
4310 BB_FOOTER (new_bb
) = BB_FOOTER (bb
);
4311 BB_FOOTER (bb
) = NULL
;
4316 /* Redirect Edge to DEST. */
4318 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
4320 basic_block src
= e
->src
;
4323 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4326 if (e
->dest
== dest
)
4329 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4330 && (ret
= try_redirect_by_replacing_jump (e
, dest
, true)))
4332 df_set_bb_dirty (src
);
4336 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4337 && (e
->flags
& EDGE_FALLTHRU
) && !(e
->flags
& EDGE_COMPLEX
))
4340 fprintf (dump_file
, "Redirecting entry edge from bb %i to %i\n",
4341 e
->src
->index
, dest
->index
);
4343 df_set_bb_dirty (e
->src
);
4344 redirect_edge_succ (e
, dest
);
4348 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4349 in the case the basic block appears to be in sequence. Avoid this
4352 if (e
->flags
& EDGE_FALLTHRU
)
4354 /* Redirect any branch edges unified with the fallthru one. */
4355 if (JUMP_P (BB_END (src
))
4356 && label_is_jump_target_p (BB_HEAD (e
->dest
),
4362 fprintf (dump_file
, "Fallthru edge unified with branch "
4363 "%i->%i redirected to %i\n",
4364 e
->src
->index
, e
->dest
->index
, dest
->index
);
4365 e
->flags
&= ~EDGE_FALLTHRU
;
4366 redirected
= redirect_branch_edge (e
, dest
);
4367 gcc_assert (redirected
);
4368 redirected
->flags
|= EDGE_FALLTHRU
;
4369 df_set_bb_dirty (redirected
->src
);
4372 /* In case we are redirecting fallthru edge to the branch edge
4373 of conditional jump, remove it. */
4374 if (EDGE_COUNT (src
->succs
) == 2)
4376 /* Find the edge that is different from E. */
4377 edge s
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
);
4380 && any_condjump_p (BB_END (src
))
4381 && onlyjump_p (BB_END (src
)))
4382 delete_insn (BB_END (src
));
4385 fprintf (dump_file
, "Redirecting fallthru edge %i->%i to %i\n",
4386 e
->src
->index
, e
->dest
->index
, dest
->index
);
4387 ret
= redirect_edge_succ_nodup (e
, dest
);
4390 ret
= redirect_branch_edge (e
, dest
);
4392 /* We don't want simplejumps in the insn stream during cfglayout. */
4393 gcc_assert (!simplejump_p (BB_END (src
)));
4395 df_set_bb_dirty (src
);
4399 /* Simple wrapper as we always can redirect fallthru edges. */
4401 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
4403 edge redirected
= cfg_layout_redirect_edge_and_branch (e
, dest
);
4405 gcc_assert (redirected
);
4409 /* Same as delete_basic_block but update cfg_layout structures. */
4412 cfg_layout_delete_block (basic_block bb
)
4414 rtx_insn
*insn
, *next
, *prev
= PREV_INSN (BB_HEAD (bb
)), *remaints
;
4419 next
= BB_HEAD (bb
);
4421 SET_NEXT_INSN (prev
) = BB_HEADER (bb
);
4423 set_first_insn (BB_HEADER (bb
));
4424 SET_PREV_INSN (BB_HEADER (bb
)) = prev
;
4425 insn
= BB_HEADER (bb
);
4426 while (NEXT_INSN (insn
))
4427 insn
= NEXT_INSN (insn
);
4428 SET_NEXT_INSN (insn
) = next
;
4429 SET_PREV_INSN (next
) = insn
;
4431 next
= NEXT_INSN (BB_END (bb
));
4434 insn
= BB_FOOTER (bb
);
4437 if (BARRIER_P (insn
))
4439 if (PREV_INSN (insn
))
4440 SET_NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (insn
);
4442 BB_FOOTER (bb
) = NEXT_INSN (insn
);
4443 if (NEXT_INSN (insn
))
4444 SET_PREV_INSN (NEXT_INSN (insn
)) = PREV_INSN (insn
);
4448 insn
= NEXT_INSN (insn
);
4453 SET_NEXT_INSN (insn
) = BB_FOOTER (bb
);
4454 SET_PREV_INSN (BB_FOOTER (bb
)) = insn
;
4455 while (NEXT_INSN (insn
))
4456 insn
= NEXT_INSN (insn
);
4457 SET_NEXT_INSN (insn
) = next
;
4459 SET_PREV_INSN (next
) = insn
;
4461 set_last_insn (insn
);
4464 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
4465 to
= &SET_BB_HEADER (bb
->next_bb
);
4467 to
= &cfg_layout_function_footer
;
4469 rtl_delete_block (bb
);
4472 prev
= NEXT_INSN (prev
);
4474 prev
= get_insns ();
4476 next
= PREV_INSN (next
);
4478 next
= get_last_insn ();
4480 if (next
&& NEXT_INSN (next
) != prev
)
4482 remaints
= unlink_insn_chain (prev
, next
);
4484 while (NEXT_INSN (insn
))
4485 insn
= NEXT_INSN (insn
);
4486 SET_NEXT_INSN (insn
) = *to
;
4488 SET_PREV_INSN (*to
) = insn
;
4493 /* Return true when blocks A and B can be safely merged. */
4496 cfg_layout_can_merge_blocks_p (basic_block a
, basic_block b
)
4498 /* If we are partitioning hot/cold basic blocks, we don't want to
4499 mess up unconditional or indirect jumps that cross between hot
4502 Basic block partitioning may result in some jumps that appear to
4503 be optimizable (or blocks that appear to be mergeable), but which really
4504 must be left untouched (they are required to make it safely across
4505 partition boundaries). See the comments at the top of
4506 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4508 if (BB_PARTITION (a
) != BB_PARTITION (b
))
4511 /* Protect the loop latches. */
4512 if (current_loops
&& b
->loop_father
->latch
== b
)
4515 /* If we would end up moving B's instructions, make sure it doesn't fall
4516 through into the exit block, since we cannot recover from a fallthrough
4517 edge into the exit block occurring in the middle of a function. */
4518 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4520 edge e
= find_fallthru_edge (b
->succs
);
4521 if (e
&& e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4525 /* There must be exactly one edge in between the blocks. */
4526 return (single_succ_p (a
)
4527 && single_succ (a
) == b
4528 && single_pred_p (b
) == 1
4530 /* Must be simple edge. */
4531 && !(single_succ_edge (a
)->flags
& EDGE_COMPLEX
)
4532 && a
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4533 && b
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
4534 /* If the jump insn has side effects, we can't kill the edge.
4535 When not optimizing, try_redirect_by_replacing_jump will
4536 not allow us to redirect an edge by replacing a table jump. */
4537 && (!JUMP_P (BB_END (a
))
4538 || ((!optimize
|| reload_completed
)
4539 ? simplejump_p (BB_END (a
)) : onlyjump_p (BB_END (a
)))));
4542 /* Merge block A and B. The blocks must be mergeable. */
4545 cfg_layout_merge_blocks (basic_block a
, basic_block b
)
4547 bool forwarder_p
= (b
->flags
& BB_FORWARDER_BLOCK
) != 0;
4550 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a
, b
));
4553 fprintf (dump_file
, "Merging block %d into block %d...\n", b
->index
,
4556 /* If there was a CODE_LABEL beginning B, delete it. */
4557 if (LABEL_P (BB_HEAD (b
)))
4559 delete_insn (BB_HEAD (b
));
4562 /* We should have fallthru edge in a, or we can do dummy redirection to get
4564 if (JUMP_P (BB_END (a
)))
4565 try_redirect_by_replacing_jump (EDGE_SUCC (a
, 0), b
, true);
4566 gcc_assert (!JUMP_P (BB_END (a
)));
4568 /* When not optimizing and the edge is the only place in RTL which holds
4569 some unique locus, emit a nop with that locus in between. */
4571 emit_nop_for_unique_locus_between (a
, b
);
4573 /* Move things from b->footer after a->footer. */
4577 BB_FOOTER (a
) = BB_FOOTER (b
);
4580 rtx_insn
*last
= BB_FOOTER (a
);
4582 while (NEXT_INSN (last
))
4583 last
= NEXT_INSN (last
);
4584 SET_NEXT_INSN (last
) = BB_FOOTER (b
);
4585 SET_PREV_INSN (BB_FOOTER (b
)) = last
;
4587 BB_FOOTER (b
) = NULL
;
4590 /* Move things from b->header before a->footer.
4591 Note that this may include dead tablejump data, but we don't clean
4592 those up until we go out of cfglayout mode. */
4595 if (! BB_FOOTER (a
))
4596 BB_FOOTER (a
) = BB_HEADER (b
);
4599 rtx_insn
*last
= BB_HEADER (b
);
4601 while (NEXT_INSN (last
))
4602 last
= NEXT_INSN (last
);
4603 SET_NEXT_INSN (last
) = BB_FOOTER (a
);
4604 SET_PREV_INSN (BB_FOOTER (a
)) = last
;
4605 BB_FOOTER (a
) = BB_HEADER (b
);
4607 SET_BB_HEADER (b
) = NULL
;
4610 /* In the case basic blocks are not adjacent, move them around. */
4611 if (NEXT_INSN (BB_END (a
)) != BB_HEAD (b
))
4613 insn
= unlink_insn_chain (BB_HEAD (b
), BB_END (b
));
4615 emit_insn_after_noloc (insn
, BB_END (a
), a
);
4617 /* Otherwise just re-associate the instructions. */
4621 SET_BB_END (a
) = BB_END (b
);
4624 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4625 We need to explicitly call. */
4626 update_bb_for_insn_chain (insn
, BB_END (b
), a
);
4628 /* Skip possible DELETED_LABEL insn. */
4629 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
4630 insn
= NEXT_INSN (insn
);
4631 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
4632 SET_BB_HEAD (b
) = SET_BB_END (b
) = NULL
;
4635 df_bb_delete (b
->index
);
4637 /* If B was a forwarder block, propagate the locus on the edge. */
4639 && LOCATION_LOCUS (EDGE_SUCC (b
, 0)->goto_locus
) == UNKNOWN_LOCATION
)
4640 EDGE_SUCC (b
, 0)->goto_locus
= EDGE_SUCC (a
, 0)->goto_locus
;
4643 fprintf (dump_file
, "Merged blocks %d and %d.\n", a
->index
, b
->index
);
4649 cfg_layout_split_edge (edge e
)
4651 basic_block new_bb
=
4652 create_basic_block (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4653 ? NEXT_INSN (BB_END (e
->src
)) : get_insns (),
4656 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4657 BB_COPY_PARTITION (new_bb
, e
->src
);
4659 BB_COPY_PARTITION (new_bb
, e
->dest
);
4660 make_edge (new_bb
, e
->dest
, EDGE_FALLTHRU
);
4661 redirect_edge_and_branch_force (e
, new_bb
);
4666 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4669 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED
)
4673 /* Return true if BB contains only labels or non-executable
4677 rtl_block_empty_p (basic_block bb
)
4681 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
4682 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4685 FOR_BB_INSNS (bb
, insn
)
4686 if (NONDEBUG_INSN_P (insn
) && !any_uncondjump_p (insn
))
4692 /* Split a basic block if it ends with a conditional branch and if
4693 the other part of the block is not empty. */
4696 rtl_split_block_before_cond_jump (basic_block bb
)
4699 rtx_insn
*split_point
= NULL
;
4700 rtx_insn
*last
= NULL
;
4701 bool found_code
= false;
4703 FOR_BB_INSNS (bb
, insn
)
4705 if (any_condjump_p (insn
))
4707 else if (NONDEBUG_INSN_P (insn
))
4712 /* Did not find everything. */
4713 if (found_code
&& split_point
)
4714 return split_block (bb
, split_point
)->dest
;
4719 /* Return 1 if BB ends with a call, possibly followed by some
4720 instructions that must stay with the call, 0 otherwise. */
4723 rtl_block_ends_with_call_p (basic_block bb
)
4725 rtx_insn
*insn
= BB_END (bb
);
4727 while (!CALL_P (insn
)
4728 && insn
!= BB_HEAD (bb
)
4729 && (keep_with_call_p (insn
)
4731 || DEBUG_INSN_P (insn
)))
4732 insn
= PREV_INSN (insn
);
4733 return (CALL_P (insn
));
4736 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4739 rtl_block_ends_with_condjump_p (const_basic_block bb
)
4741 return any_condjump_p (BB_END (bb
));
4744 /* Return true if we need to add fake edge to exit.
4745 Helper function for rtl_flow_call_edges_add. */
4748 need_fake_edge_p (const rtx_insn
*insn
)
4754 && !SIBLING_CALL_P (insn
)
4755 && !find_reg_note (insn
, REG_NORETURN
, NULL
)
4756 && !(RTL_CONST_OR_PURE_CALL_P (insn
))))
4759 return ((GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
4760 && MEM_VOLATILE_P (PATTERN (insn
)))
4761 || (GET_CODE (PATTERN (insn
)) == PARALLEL
4762 && asm_noperands (insn
) != -1
4763 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn
), 0, 0)))
4764 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
);
4767 /* Add fake edges to the function exit for any non constant and non noreturn
4768 calls, volatile inline assembly in the bitmap of blocks specified by
4769 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4772 The goal is to expose cases in which entering a basic block does not imply
4773 that all subsequent instructions must be executed. */
4776 rtl_flow_call_edges_add (sbitmap blocks
)
4779 int blocks_split
= 0;
4780 int last_bb
= last_basic_block_for_fn (cfun
);
4781 bool check_last_block
= false;
4783 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
4787 check_last_block
= true;
4789 check_last_block
= bitmap_bit_p (blocks
,
4790 EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
->index
);
4792 /* In the last basic block, before epilogue generation, there will be
4793 a fallthru edge to EXIT. Special care is required if the last insn
4794 of the last basic block is a call because make_edge folds duplicate
4795 edges, which would result in the fallthru edge also being marked
4796 fake, which would result in the fallthru edge being removed by
4797 remove_fake_edges, which would result in an invalid CFG.
4799 Moreover, we can't elide the outgoing fake edge, since the block
4800 profiler needs to take this into account in order to solve the minimal
4801 spanning tree in the case that the call doesn't return.
4803 Handle this by adding a dummy instruction in a new last basic block. */
4804 if (check_last_block
)
4806 basic_block bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
4807 rtx_insn
*insn
= BB_END (bb
);
4809 /* Back up past insns that must be kept in the same block as a call. */
4810 while (insn
!= BB_HEAD (bb
)
4811 && keep_with_call_p (insn
))
4812 insn
= PREV_INSN (insn
);
4814 if (need_fake_edge_p (insn
))
4818 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4821 insert_insn_on_edge (gen_use (const0_rtx
), e
);
4822 commit_edge_insertions ();
4827 /* Now add fake edges to the function exit for any non constant
4828 calls since there is no way that we can determine if they will
4831 for (i
= NUM_FIXED_BLOCKS
; i
< last_bb
; i
++)
4833 basic_block bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
4835 rtx_insn
*prev_insn
;
4840 if (blocks
&& !bitmap_bit_p (blocks
, i
))
4843 for (insn
= BB_END (bb
); ; insn
= prev_insn
)
4845 prev_insn
= PREV_INSN (insn
);
4846 if (need_fake_edge_p (insn
))
4849 rtx_insn
*split_at_insn
= insn
;
4851 /* Don't split the block between a call and an insn that should
4852 remain in the same block as the call. */
4854 while (split_at_insn
!= BB_END (bb
)
4855 && keep_with_call_p (NEXT_INSN (split_at_insn
)))
4856 split_at_insn
= NEXT_INSN (split_at_insn
);
4858 /* The handling above of the final block before the epilogue
4859 should be enough to verify that there is no edge to the exit
4860 block in CFG already. Calling make_edge in such case would
4861 cause us to mark that edge as fake and remove it later. */
4863 #ifdef ENABLE_CHECKING
4864 if (split_at_insn
== BB_END (bb
))
4866 e
= find_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
));
4867 gcc_assert (e
== NULL
);
4871 /* Note that the following may create a new basic block
4872 and renumber the existing basic blocks. */
4873 if (split_at_insn
!= BB_END (bb
))
4875 e
= split_block (bb
, split_at_insn
);
4880 make_edge (bb
, EXIT_BLOCK_PTR_FOR_FN (cfun
), EDGE_FAKE
);
4883 if (insn
== BB_HEAD (bb
))
4889 verify_flow_info ();
4891 return blocks_split
;
4894 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4895 the conditional branch target, SECOND_HEAD should be the fall-thru
4896 there is no need to handle this here the loop versioning code handles
4897 this. the reason for SECON_HEAD is that it is needed for condition
4898 in trees, and this should be of the same type since it is a hook. */
4900 rtl_lv_add_condition_to_bb (basic_block first_head
,
4901 basic_block second_head ATTRIBUTE_UNUSED
,
4902 basic_block cond_bb
, void *comp_rtx
)
4905 rtx_insn
*seq
, *jump
;
4906 rtx op0
= XEXP ((rtx
)comp_rtx
, 0);
4907 rtx op1
= XEXP ((rtx
)comp_rtx
, 1);
4908 enum rtx_code comp
= GET_CODE ((rtx
)comp_rtx
);
4909 enum machine_mode mode
;
4912 label
= block_label (first_head
);
4913 mode
= GET_MODE (op0
);
4914 if (mode
== VOIDmode
)
4915 mode
= GET_MODE (op1
);
4918 op0
= force_operand (op0
, NULL_RTX
);
4919 op1
= force_operand (op1
, NULL_RTX
);
4920 do_compare_rtx_and_jump (op0
, op1
, comp
, 0,
4921 mode
, NULL_RTX
, NULL_RTX
, label
, -1);
4922 jump
= get_last_insn ();
4923 JUMP_LABEL (jump
) = label
;
4924 LABEL_NUSES (label
)++;
4928 /* Add the new cond , in the new head. */
4929 emit_insn_after (seq
, BB_END (cond_bb
));
4933 /* Given a block B with unconditional branch at its end, get the
4934 store the return the branch edge and the fall-thru edge in
4935 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4937 rtl_extract_cond_bb_edges (basic_block b
, edge
*branch_edge
,
4938 edge
*fallthru_edge
)
4940 edge e
= EDGE_SUCC (b
, 0);
4942 if (e
->flags
& EDGE_FALLTHRU
)
4945 *branch_edge
= EDGE_SUCC (b
, 1);
4950 *fallthru_edge
= EDGE_SUCC (b
, 1);
4955 init_rtl_bb_info (basic_block bb
)
4957 gcc_assert (!bb
->il
.x
.rtl
);
4958 bb
->il
.x
.head_
= NULL
;
4959 bb
->il
.x
.rtl
= ggc_cleared_alloc
<rtl_bb_info
> ();
4962 /* Returns true if it is possible to remove edge E by redirecting
4963 it to the destination of the other edge from E->src. */
4966 rtl_can_remove_branch_p (const_edge e
)
4968 const_basic_block src
= e
->src
;
4969 const_basic_block target
= EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
;
4970 const rtx_insn
*insn
= BB_END (src
);
4973 /* The conditions are taken from try_redirect_by_replacing_jump. */
4974 if (target
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4977 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4980 if (BB_PARTITION (src
) != BB_PARTITION (target
))
4983 if (!onlyjump_p (insn
)
4984 || tablejump_p (insn
, NULL
, NULL
))
4987 set
= single_set (insn
);
4988 if (!set
|| side_effects_p (set
))
4995 rtl_duplicate_bb (basic_block bb
)
4997 bb
= cfg_layout_duplicate_bb (bb
);
5002 /* Do book-keeping of basic block BB for the profile consistency checker.
5003 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
5004 then do post-pass accounting. Store the counting in RECORD. */
5006 rtl_account_profile_record (basic_block bb
, int after_pass
,
5007 struct profile_record
*record
)
5010 FOR_BB_INSNS (bb
, insn
)
5013 record
->size
[after_pass
]
5014 += insn_rtx_cost (PATTERN (insn
), false);
5015 if (profile_status_for_fn (cfun
) == PROFILE_READ
)
5016 record
->time
[after_pass
]
5017 += insn_rtx_cost (PATTERN (insn
), true) * bb
->count
;
5018 else if (profile_status_for_fn (cfun
) == PROFILE_GUESSED
)
5019 record
->time
[after_pass
]
5020 += insn_rtx_cost (PATTERN (insn
), true) * bb
->frequency
;
5024 /* Implementation of CFG manipulation for linearized RTL. */
5025 struct cfg_hooks rtl_cfg_hooks
= {
5027 rtl_verify_flow_info
,
5029 rtl_dump_bb_for_graph
,
5030 rtl_create_basic_block
,
5031 rtl_redirect_edge_and_branch
,
5032 rtl_redirect_edge_and_branch_force
,
5033 rtl_can_remove_branch_p
,
5036 rtl_move_block_after
,
5037 rtl_can_merge_blocks
, /* can_merge_blocks_p */
5041 cfg_layout_can_duplicate_bb_p
,
5044 rtl_make_forwarder_block
,
5045 rtl_tidy_fallthru_edge
,
5046 rtl_force_nonfallthru
,
5047 rtl_block_ends_with_call_p
,
5048 rtl_block_ends_with_condjump_p
,
5049 rtl_flow_call_edges_add
,
5050 NULL
, /* execute_on_growing_pred */
5051 NULL
, /* execute_on_shrinking_pred */
5052 NULL
, /* duplicate loop for trees */
5053 NULL
, /* lv_add_condition_to_bb */
5054 NULL
, /* lv_adjust_loop_header_phi*/
5055 NULL
, /* extract_cond_bb_edges */
5056 NULL
, /* flush_pending_stmts */
5057 rtl_block_empty_p
, /* block_empty_p */
5058 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5059 rtl_account_profile_record
,
5062 /* Implementation of CFG manipulation for cfg layout RTL, where
5063 basic block connected via fallthru edges does not have to be adjacent.
5064 This representation will hopefully become the default one in future
5065 version of the compiler. */
5067 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
5069 rtl_verify_flow_info_1
,
5071 rtl_dump_bb_for_graph
,
5072 cfg_layout_create_basic_block
,
5073 cfg_layout_redirect_edge_and_branch
,
5074 cfg_layout_redirect_edge_and_branch_force
,
5075 rtl_can_remove_branch_p
,
5076 cfg_layout_delete_block
,
5077 cfg_layout_split_block
,
5078 rtl_move_block_after
,
5079 cfg_layout_can_merge_blocks_p
,
5080 cfg_layout_merge_blocks
,
5083 cfg_layout_can_duplicate_bb_p
,
5084 cfg_layout_duplicate_bb
,
5085 cfg_layout_split_edge
,
5086 rtl_make_forwarder_block
,
5087 NULL
, /* tidy_fallthru_edge */
5088 rtl_force_nonfallthru
,
5089 rtl_block_ends_with_call_p
,
5090 rtl_block_ends_with_condjump_p
,
5091 rtl_flow_call_edges_add
,
5092 NULL
, /* execute_on_growing_pred */
5093 NULL
, /* execute_on_shrinking_pred */
5094 duplicate_loop_to_header_edge
, /* duplicate loop for trees */
5095 rtl_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
5096 NULL
, /* lv_adjust_loop_header_phi*/
5097 rtl_extract_cond_bb_edges
, /* extract_cond_bb_edges */
5098 NULL
, /* flush_pending_stmts */
5099 rtl_block_empty_p
, /* block_empty_p */
5100 rtl_split_block_before_cond_jump
, /* split_block_before_cond_jump */
5101 rtl_account_profile_record
,
5104 /* BB_HEAD as an rvalue. */
5106 rtx_insn
*BB_HEAD (const_basic_block bb
)
5108 rtx insn
= bb
->il
.x
.head_
;
5109 return safe_as_a
<rtx_insn
*> (insn
);
5112 /* BB_HEAD for use as an lvalue. */
5114 rtx
& SET_BB_HEAD (basic_block bb
)
5116 return bb
->il
.x
.head_
;
5119 /* BB_END as an rvalue. */
5121 rtx_insn
*BB_END (const_basic_block bb
)
5123 rtx insn
= bb
->il
.x
.rtl
->end_
;
5124 return safe_as_a
<rtx_insn
*> (insn
);
5127 /* BB_END as an lvalue. */
5129 rtx
& SET_BB_END (basic_block bb
)
5131 return bb
->il
.x
.rtl
->end_
;
5134 /* BB_HEADER as an rvalue. */
5136 rtx_insn
*BB_HEADER (const_basic_block bb
)
5138 rtx insn
= bb
->il
.x
.rtl
->header_
;
5139 return safe_as_a
<rtx_insn
*> (insn
);
5142 /* BB_HEADER as an lvalue. */
5144 rtx
& SET_BB_HEADER (basic_block bb
)
5146 return bb
->il
.x
.rtl
->header_
;
5149 #include "gt-cfgrtl.h"