1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 /* This file contains low level functions to manipulate the CFG and analyze it
23 that are aware of the RTL intermediate language.
25 Available functionality:
26 - CFG-aware instruction chain manipulation
27 delete_insn, delete_insn_chain
28 - Basic block manipulation
29 create_basic_block, rtl_delete_block,rtl_split_block,
31 - Infrastructure to determine quickly basic block for insn
32 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
33 - Edge redirection with updating and optimizing of insn chain
34 block_label, redirect_edge_and_branch,
35 redirect_edge_and_branch_force, tidy_fallthru_edge, force_nonfallthru
36 - Edge splitting and committing to edges
37 split_edge, insert_insn_on_edge, commit_edge_insertions
38 - CFG updating after constant propagation
39 purge_dead_edges, purge_all_dead_edges */
43 #include "coretypes.h"
47 #include "hard-reg-set.h"
48 #include "basic-block.h"
57 #include "insn-config.h"
58 #include "cfglayout.h"
61 /* Stubs in case we don't have a return insn. */
64 #define gen_return() NULL_RTX
67 /* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */
68 /* ??? Should probably be using LABEL_NUSES instead. It would take a
69 bit of surgery to be able to use or co-opt the routines in jump. */
71 rtx tail_recursion_label_list
;
73 static int can_delete_note_p (rtx
);
74 static int can_delete_label_p (rtx
);
75 static void commit_one_edge_insertion (edge
, int);
76 static bool try_redirect_by_replacing_jump (edge
, basic_block
);
77 static rtx
last_loop_beg_note (rtx
);
78 static bool back_edge_of_syntactic_loop_p (basic_block
, basic_block
);
79 basic_block
force_nonfallthru_and_redirect (edge
, basic_block
);
80 static basic_block
rtl_split_edge (edge
);
81 static int rtl_verify_flow_info (void);
82 static edge
cfg_layout_split_block (basic_block
, void *);
83 static bool 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 bool rtl_redirect_edge_and_branch (edge
, basic_block
);
89 static edge
rtl_split_block (basic_block
, void *);
90 static void rtl_dump_bb (basic_block
, FILE *);
91 static int rtl_verify_flow_info_1 (void);
92 static void mark_killed_regs (rtx
, rtx
, void *);
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 (rtx note
)
100 return (NOTE_LINE_NUMBER (note
) == NOTE_INSN_DELETED
101 || NOTE_LINE_NUMBER (note
) == NOTE_INSN_BASIC_BLOCK
102 || NOTE_LINE_NUMBER (note
) == NOTE_INSN_PREDICTION
);
105 /* True if a given label can be deleted. */
108 can_delete_label_p (rtx label
)
110 return (!LABEL_PRESERVE_P (label
)
111 /* User declared labels must be preserved. */
112 && LABEL_NAME (label
) == 0
113 && !in_expr_list_p (forced_labels
, label
)
114 && !in_expr_list_p (label_value_list
, label
));
117 /* Delete INSN by patching it out. Return the next insn. */
120 delete_insn (rtx insn
)
122 rtx next
= NEXT_INSN (insn
);
124 bool really_delete
= true;
126 if (GET_CODE (insn
) == CODE_LABEL
)
128 /* Some labels can't be directly removed from the INSN chain, as they
129 might be references via variables, constant pool etc.
130 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
131 if (! can_delete_label_p (insn
))
133 const char *name
= LABEL_NAME (insn
);
135 really_delete
= false;
136 PUT_CODE (insn
, NOTE
);
137 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED_LABEL
;
138 NOTE_SOURCE_FILE (insn
) = name
;
141 remove_node_from_expr_list (insn
, &nonlocal_goto_handler_labels
);
146 /* If this insn has already been deleted, something is very wrong. */
147 if (INSN_DELETED_P (insn
))
150 INSN_DELETED_P (insn
) = 1;
153 /* If deleting a jump, decrement the use count of the label. Deleting
154 the label itself should happen in the normal course of block merging. */
155 if (GET_CODE (insn
) == JUMP_INSN
157 && GET_CODE (JUMP_LABEL (insn
)) == CODE_LABEL
)
158 LABEL_NUSES (JUMP_LABEL (insn
))--;
160 /* Also if deleting an insn that references a label. */
161 else if ((note
= find_reg_note (insn
, REG_LABEL
, NULL_RTX
)) != NULL_RTX
162 && GET_CODE (XEXP (note
, 0)) == CODE_LABEL
)
163 LABEL_NUSES (XEXP (note
, 0))--;
165 if (GET_CODE (insn
) == JUMP_INSN
166 && (GET_CODE (PATTERN (insn
)) == ADDR_VEC
167 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
))
169 rtx pat
= PATTERN (insn
);
170 int diff_vec_p
= GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
;
171 int len
= XVECLEN (pat
, diff_vec_p
);
174 for (i
= 0; i
< len
; i
++)
176 rtx label
= XEXP (XVECEXP (pat
, diff_vec_p
, i
), 0);
178 /* When deleting code in bulk (e.g. removing many unreachable
179 blocks) we can delete a label that's a target of the vector
180 before deleting the vector itself. */
181 if (GET_CODE (label
) != NOTE
)
182 LABEL_NUSES (label
)--;
189 /* Like delete_insn but also purge dead edges from BB. */
191 delete_insn_and_edges (rtx insn
)
197 && BLOCK_FOR_INSN (insn
)
198 && BLOCK_FOR_INSN (insn
)->end
== insn
)
200 x
= delete_insn (insn
);
202 purge_dead_edges (BLOCK_FOR_INSN (insn
));
206 /* Unlink a chain of insns between START and FINISH, leaving notes
207 that must be paired. */
210 delete_insn_chain (rtx start
, rtx finish
)
214 /* Unchain the insns one by one. It would be quicker to delete all of these
215 with a single unchaining, rather than one at a time, but we need to keep
219 next
= NEXT_INSN (start
);
220 if (GET_CODE (start
) == NOTE
&& !can_delete_note_p (start
))
223 next
= delete_insn (start
);
231 /* Like delete_insn but also purge dead edges from BB. */
233 delete_insn_chain_and_edges (rtx first
, rtx last
)
238 && BLOCK_FOR_INSN (last
)
239 && BLOCK_FOR_INSN (last
)->end
== last
)
241 delete_insn_chain (first
, last
);
243 purge_dead_edges (BLOCK_FOR_INSN (last
));
246 /* Create a new basic block consisting of the instructions between HEAD and END
247 inclusive. This function is designed to allow fast BB construction - reuses
248 the note and basic block struct in BB_NOTE, if any and do not grow
249 BASIC_BLOCK chain and should be used directly only by CFG construction code.
250 END can be NULL in to create new empty basic block before HEAD. Both END
251 and HEAD can be NULL to create basic block at the end of INSN chain.
252 AFTER is the basic block we should be put after. */
255 create_basic_block_structure (rtx head
, rtx end
, rtx bb_note
, basic_block after
)
260 && ! RTX_INTEGRATED_P (bb_note
)
261 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
264 /* If we found an existing note, thread it back onto the chain. */
268 if (GET_CODE (head
) == CODE_LABEL
)
272 after
= PREV_INSN (head
);
276 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
277 reorder_insns_nobb (bb_note
, bb_note
, after
);
281 /* Otherwise we must create a note and a basic block structure. */
287 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
288 else if (GET_CODE (head
) == CODE_LABEL
&& end
)
290 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
296 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
302 NOTE_BASIC_BLOCK (bb_note
) = bb
;
305 /* Always include the bb note in the block. */
306 if (NEXT_INSN (end
) == bb_note
)
311 bb
->index
= last_basic_block
++;
313 link_block (bb
, after
);
314 BASIC_BLOCK (bb
->index
) = bb
;
315 update_bb_for_insn (bb
);
317 /* Tag the block so that we know it has been used when considering
318 other basic block notes. */
324 /* Create new basic block consisting of instructions in between HEAD and END
325 and place it to the BB chain after block AFTER. END can be NULL in to
326 create new empty basic block before HEAD. Both END and HEAD can be NULL to
327 create basic block at the end of INSN chain. */
330 create_basic_block (rtx head
, rtx end
, basic_block after
)
334 /* Place the new block just after the end. */
335 VARRAY_GROW (basic_block_info
, last_basic_block
+1);
339 bb
= create_basic_block_structure (head
, end
, NULL
, after
);
344 /* Delete the insns in a (non-live) block. We physically delete every
345 non-deleted-note insn, and update the flow graph appropriately.
347 Return nonzero if we deleted an exception handler. */
349 /* ??? Preserving all such notes strikes me as wrong. It would be nice
350 to post-process the stream to remove empty blocks, loops, ranges, etc. */
353 rtl_delete_block (basic_block b
)
357 /* If the head of this block is a CODE_LABEL, then it might be the
358 label for an exception handler which can't be reached.
360 We need to remove the label from the exception_handler_label list
361 and remove the associated NOTE_INSN_EH_REGION_BEG and
362 NOTE_INSN_EH_REGION_END notes. */
364 /* Get rid of all NOTE_INSN_PREDICTIONs and NOTE_INSN_LOOP_CONTs
365 hanging before the block. */
367 for (insn
= PREV_INSN (b
->head
); insn
; insn
= PREV_INSN (insn
))
369 if (GET_CODE (insn
) != NOTE
)
371 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_PREDICTION
372 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_CONT
)
373 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
378 never_reached_warning (insn
, b
->end
);
380 if (GET_CODE (insn
) == CODE_LABEL
)
381 maybe_remove_eh_handler (insn
);
383 /* Include any jump table following the basic block. */
385 if (tablejump_p (end
, NULL
, &tmp
))
388 /* Include any barrier that may follow the basic block. */
389 tmp
= next_nonnote_insn (end
);
390 if (tmp
&& GET_CODE (tmp
) == BARRIER
)
393 /* Selectively delete the entire chain. */
395 delete_insn_chain (insn
, end
);
397 /* Remove the edges into and out of this block. Note that there may
398 indeed be edges in, if we are removing an unreachable loop. */
399 while (b
->pred
!= NULL
)
400 remove_edge (b
->pred
);
401 while (b
->succ
!= NULL
)
402 remove_edge (b
->succ
);
407 /* Remove the basic block from the array. */
411 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
414 compute_bb_for_insn (void)
423 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
425 BLOCK_FOR_INSN (insn
) = bb
;
432 /* Release the basic_block_for_insn array. */
435 free_bb_for_insn (void)
438 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
439 if (GET_CODE (insn
) != BARRIER
)
440 BLOCK_FOR_INSN (insn
) = NULL
;
443 /* Update insns block within BB. */
446 update_bb_for_insn (basic_block bb
)
450 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
452 if (GET_CODE (insn
) != BARRIER
)
453 set_block_for_insn (insn
, bb
);
459 /* Split a block BB after insn INSN creating a new fallthru edge.
460 Return the new edge. Note that to keep other parts of the compiler happy,
461 this function renumbers all the basic blocks so that the new
462 one has a number one greater than the block split. */
465 rtl_split_block (basic_block bb
, void *insnp
)
472 /* There is no point splitting the block after its end. */
476 /* Create the new basic block. */
477 new_bb
= create_basic_block (NEXT_INSN (insn
), bb
->end
, bb
);
478 new_bb
->count
= bb
->count
;
479 new_bb
->frequency
= bb
->frequency
;
480 new_bb
->loop_depth
= bb
->loop_depth
;
483 /* Redirect the outgoing edges. */
484 new_bb
->succ
= bb
->succ
;
486 for (e
= new_bb
->succ
; e
; e
= e
->succ_next
)
489 new_edge
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
491 if (bb
->global_live_at_start
)
493 new_bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
494 new_bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
495 COPY_REG_SET (new_bb
->global_live_at_end
, bb
->global_live_at_end
);
497 /* We now have to calculate which registers are live at the end
498 of the split basic block and at the start of the new basic
499 block. Start with those registers that are known to be live
500 at the end of the original basic block and get
501 propagate_block to determine which registers are live. */
502 COPY_REG_SET (new_bb
->global_live_at_start
, bb
->global_live_at_end
);
503 propagate_block (new_bb
, new_bb
->global_live_at_start
, NULL
, NULL
, 0);
504 COPY_REG_SET (bb
->global_live_at_end
,
505 new_bb
->global_live_at_start
);
506 #ifdef HAVE_conditional_execution
507 /* In the presence of conditional execution we are not able to update
508 liveness precisely. */
509 if (reload_completed
)
511 bb
->flags
|= BB_DIRTY
;
512 new_bb
->flags
|= BB_DIRTY
;
520 /* Blocks A and B are to be merged into a single block A. The insns
521 are already contiguous, hence `nomove'. */
524 merge_blocks_nomove (basic_block a
, basic_block b
)
526 rtx b_head
= b
->head
, b_end
= b
->end
, a_end
= a
->end
;
527 rtx del_first
= NULL_RTX
, del_last
= NULL_RTX
;
531 /* If there was a CODE_LABEL beginning B, delete it. */
532 if (GET_CODE (b_head
) == CODE_LABEL
)
534 /* Detect basic blocks with nothing but a label. This can happen
535 in particular at the end of a function. */
539 del_first
= del_last
= b_head
;
540 b_head
= NEXT_INSN (b_head
);
543 /* Delete the basic block note and handle blocks containing just that
545 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
553 b_head
= NEXT_INSN (b_head
);
556 /* If there was a jump out of A, delete it. */
557 if (GET_CODE (a_end
) == JUMP_INSN
)
561 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
562 if (GET_CODE (prev
) != NOTE
563 || NOTE_LINE_NUMBER (prev
) == NOTE_INSN_BASIC_BLOCK
570 /* If this was a conditional jump, we need to also delete
571 the insn that set cc0. */
572 if (only_sets_cc0_p (prev
))
576 prev
= prev_nonnote_insn (prev
);
583 a_end
= PREV_INSN (del_first
);
585 else if (GET_CODE (NEXT_INSN (a_end
)) == BARRIER
)
586 del_first
= NEXT_INSN (a_end
);
588 /* Normally there should only be one successor of A and that is B, but
589 partway though the merge of blocks for conditional_execution we'll
590 be merging a TEST block with THEN and ELSE successors. Free the
591 whole lot of them and hope the caller knows what they're doing. */
593 remove_edge (a
->succ
);
595 /* Adjust the edges out of B for the new owner. */
596 for (e
= b
->succ
; e
; e
= e
->succ_next
)
599 a
->flags
|= b
->flags
;
601 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
602 b
->pred
= b
->succ
= NULL
;
603 a
->global_live_at_end
= b
->global_live_at_end
;
607 /* Delete everything marked above as well as crap that might be
608 hanging out between the two blocks. */
609 delete_insn_chain (del_first
, del_last
);
611 /* Reassociate the insns of B with A. */
616 for (x
= a_end
; x
!= b_end
; x
= NEXT_INSN (x
))
617 set_block_for_insn (x
, a
);
619 set_block_for_insn (b_end
, a
);
627 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
631 block_label (basic_block block
)
633 if (block
== EXIT_BLOCK_PTR
)
636 if (GET_CODE (block
->head
) != CODE_LABEL
)
638 block
->head
= emit_label_before (gen_label_rtx (), block
->head
);
644 /* Attempt to perform edge redirection by replacing possibly complex jump
645 instruction by unconditional jump or removing jump completely. This can
646 apply only if all edges now point to the same block. The parameters and
647 return values are equivalent to redirect_edge_and_branch. */
650 try_redirect_by_replacing_jump (edge e
, basic_block target
)
652 basic_block src
= e
->src
;
653 rtx insn
= src
->end
, kill_from
;
658 /* Verify that all targets will be TARGET. */
659 for (tmp
= src
->succ
; tmp
; tmp
= tmp
->succ_next
)
660 if (tmp
->dest
!= target
&& tmp
!= e
)
663 if (tmp
|| !onlyjump_p (insn
))
665 if ((!optimize
|| flow2_completed
) && tablejump_p (insn
, NULL
, NULL
))
668 /* Avoid removing branch with side effects. */
669 set
= single_set (insn
);
670 if (!set
|| side_effects_p (set
))
673 /* In case we zap a conditional jump, we'll need to kill
674 the cc0 setter too. */
677 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
)))
678 kill_from
= PREV_INSN (insn
);
681 /* See if we can create the fallthru edge. */
682 if (can_fallthru (src
, target
))
685 fprintf (rtl_dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
688 /* Selectively unlink whole insn chain. */
689 delete_insn_chain (kill_from
, PREV_INSN (target
->head
));
692 /* If this already is simplejump, redirect it. */
693 else if (simplejump_p (insn
))
695 if (e
->dest
== target
)
698 fprintf (rtl_dump_file
, "Redirecting jump %i from %i to %i.\n",
699 INSN_UID (insn
), e
->dest
->index
, target
->index
);
700 if (!redirect_jump (insn
, block_label (target
), 0))
702 if (target
== EXIT_BLOCK_PTR
)
708 /* Cannot do anything for target exit block. */
709 else if (target
== EXIT_BLOCK_PTR
)
712 /* Or replace possibly complicated jump insn by simple jump insn. */
715 rtx target_label
= block_label (target
);
716 rtx barrier
, label
, table
;
718 emit_jump_insn_after (gen_jump (target_label
), insn
);
719 JUMP_LABEL (src
->end
) = target_label
;
720 LABEL_NUSES (target_label
)++;
722 fprintf (rtl_dump_file
, "Replacing insn %i by jump %i\n",
723 INSN_UID (insn
), INSN_UID (src
->end
));
726 delete_insn_chain (kill_from
, insn
);
728 /* Recognize a tablejump that we are converting to a
729 simple jump and remove its associated CODE_LABEL
730 and ADDR_VEC or ADDR_DIFF_VEC. */
731 if (tablejump_p (insn
, &label
, &table
))
732 delete_insn_chain (label
, table
);
734 barrier
= next_nonnote_insn (src
->end
);
735 if (!barrier
|| GET_CODE (barrier
) != BARRIER
)
736 emit_barrier_after (src
->end
);
739 /* Keep only one edge out and set proper flags. */
740 while (src
->succ
->succ_next
)
741 remove_edge (src
->succ
);
744 e
->flags
= EDGE_FALLTHRU
;
748 e
->probability
= REG_BR_PROB_BASE
;
749 e
->count
= src
->count
;
751 /* We don't want a block to end on a line-number note since that has
752 the potential of changing the code between -g and not -g. */
753 while (GET_CODE (e
->src
->end
) == NOTE
754 && NOTE_LINE_NUMBER (e
->src
->end
) >= 0)
755 delete_insn (e
->src
->end
);
757 if (e
->dest
!= target
)
758 redirect_edge_succ (e
, target
);
763 /* Return last loop_beg note appearing after INSN, before start of next
764 basic block. Return INSN if there are no such notes.
766 When emitting jump to redirect a fallthru edge, it should always appear
767 after the LOOP_BEG notes, as loop optimizer expect loop to either start by
768 fallthru edge or jump following the LOOP_BEG note jumping to the loop exit
772 last_loop_beg_note (rtx insn
)
776 for (insn
= NEXT_INSN (insn
); insn
&& GET_CODE (insn
) == NOTE
777 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
;
778 insn
= NEXT_INSN (insn
))
779 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
785 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
786 expense of adding new instructions or reordering basic blocks.
788 Function can be also called with edge destination equivalent to the TARGET.
789 Then it should try the simplifications and do nothing if none is possible.
791 Return true if transformation succeeded. We still return false in case E
792 already destinated TARGET and we didn't managed to simplify instruction
796 rtl_redirect_edge_and_branch (edge e
, basic_block target
)
799 rtx old_label
= e
->dest
->head
;
800 basic_block src
= e
->src
;
803 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
806 if (try_redirect_by_replacing_jump (e
, target
))
809 /* Do this fast path late, as we want above code to simplify for cases
810 where called on single edge leaving basic block containing nontrivial
812 else if (e
->dest
== target
)
815 /* We can only redirect non-fallthru edges of jump insn. */
816 if (e
->flags
& EDGE_FALLTHRU
)
818 else if (GET_CODE (insn
) != JUMP_INSN
)
821 /* Recognize a tablejump and adjust all matching cases. */
822 if (tablejump_p (insn
, NULL
, &tmp
))
826 rtx new_label
= block_label (target
);
828 if (target
== EXIT_BLOCK_PTR
)
830 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
831 vec
= XVEC (PATTERN (tmp
), 0);
833 vec
= XVEC (PATTERN (tmp
), 1);
835 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
836 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
838 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
839 --LABEL_NUSES (old_label
);
840 ++LABEL_NUSES (new_label
);
843 /* Handle casesi dispatch insns */
844 if ((tmp
= single_set (insn
)) != NULL
845 && SET_DEST (tmp
) == pc_rtx
846 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
847 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
848 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
850 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (VOIDmode
,
852 --LABEL_NUSES (old_label
);
853 ++LABEL_NUSES (new_label
);
858 /* ?? We may play the games with moving the named labels from
859 one basic block to the other in case only one computed_jump is
861 if (computed_jump_p (insn
)
862 /* A return instruction can't be redirected. */
863 || returnjump_p (insn
))
866 /* If the insn doesn't go where we think, we're confused. */
867 if (JUMP_LABEL (insn
) != old_label
)
870 /* If the substitution doesn't succeed, die. This can happen
871 if the back end emitted unrecognizable instructions or if
872 target is exit block on some arches. */
873 if (!redirect_jump (insn
, block_label (target
), 0))
875 if (target
== EXIT_BLOCK_PTR
)
882 fprintf (rtl_dump_file
, "Edge %i->%i redirected to %i\n",
883 e
->src
->index
, e
->dest
->index
, target
->index
);
885 if (e
->dest
!= target
)
886 redirect_edge_succ_nodup (e
, target
);
891 /* Like force_nonfallthru below, but additionally performs redirection
892 Used by redirect_edge_and_branch_force. */
895 force_nonfallthru_and_redirect (edge e
, basic_block target
)
897 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
900 int abnormal_edge_flags
= 0;
902 /* In the case the last instruction is conditional jump to the next
903 instruction, first redirect the jump itself and then continue
904 by creating a basic block afterwards to redirect fallthru edge. */
905 if (e
->src
!= ENTRY_BLOCK_PTR
&& e
->dest
!= EXIT_BLOCK_PTR
906 && any_condjump_p (e
->src
->end
)
907 /* When called from cfglayout, fallthru edges do not
908 neccessarily go to the next block. */
909 && e
->src
->next_bb
== e
->dest
910 && JUMP_LABEL (e
->src
->end
) == e
->dest
->head
)
913 edge b
= unchecked_make_edge (e
->src
, target
, 0);
915 if (!redirect_jump (e
->src
->end
, block_label (target
), 0))
917 note
= find_reg_note (e
->src
->end
, REG_BR_PROB
, NULL_RTX
);
920 int prob
= INTVAL (XEXP (note
, 0));
922 b
->probability
= prob
;
923 b
->count
= e
->count
* prob
/ REG_BR_PROB_BASE
;
924 e
->probability
-= e
->probability
;
925 e
->count
-= b
->count
;
926 if (e
->probability
< 0)
933 if (e
->flags
& EDGE_ABNORMAL
)
935 /* Irritating special case - fallthru edge to the same block as abnormal
937 We can't redirect abnormal edge, but we still can split the fallthru
938 one and create separate abnormal edge to original destination.
939 This allows bb-reorder to make such edge non-fallthru. */
940 if (e
->dest
!= target
)
942 abnormal_edge_flags
= e
->flags
& ~(EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
);
943 e
->flags
&= EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
;
945 else if (!(e
->flags
& EDGE_FALLTHRU
))
947 else if (e
->src
== ENTRY_BLOCK_PTR
)
949 /* We can't redirect the entry block. Create an empty block at the
950 start of the function which we use to add the new jump. */
952 basic_block bb
= create_basic_block (e
->dest
->head
, NULL
, ENTRY_BLOCK_PTR
);
954 /* Change the existing edge's source to be the new block, and add
955 a new edge from the entry block to the new block. */
957 for (pe1
= &ENTRY_BLOCK_PTR
->succ
; *pe1
; pe1
= &(*pe1
)->succ_next
)
965 make_single_succ_edge (ENTRY_BLOCK_PTR
, bb
, EDGE_FALLTHRU
);
968 if (e
->src
->succ
->succ_next
|| abnormal_edge_flags
)
970 /* Create the new structures. */
972 /* Position the new block correctly relative to loop notes. */
973 note
= last_loop_beg_note (e
->src
->end
);
974 note
= NEXT_INSN (note
);
976 /* ... and ADDR_VECs. */
978 && GET_CODE (note
) == CODE_LABEL
980 && GET_CODE (NEXT_INSN (note
)) == JUMP_INSN
981 && (GET_CODE (PATTERN (NEXT_INSN (note
))) == ADDR_DIFF_VEC
982 || GET_CODE (PATTERN (NEXT_INSN (note
))) == ADDR_VEC
))
983 note
= NEXT_INSN (NEXT_INSN (note
));
985 jump_block
= create_basic_block (note
, NULL
, e
->src
);
986 jump_block
->count
= e
->count
;
987 jump_block
->frequency
= EDGE_FREQUENCY (e
);
988 jump_block
->loop_depth
= target
->loop_depth
;
990 if (target
->global_live_at_start
)
992 jump_block
->global_live_at_start
993 = OBSTACK_ALLOC_REG_SET (&flow_obstack
);
994 jump_block
->global_live_at_end
995 = OBSTACK_ALLOC_REG_SET (&flow_obstack
);
996 COPY_REG_SET (jump_block
->global_live_at_start
,
997 target
->global_live_at_start
);
998 COPY_REG_SET (jump_block
->global_live_at_end
,
999 target
->global_live_at_start
);
1003 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1004 new_edge
->probability
= e
->probability
;
1005 new_edge
->count
= e
->count
;
1007 /* Redirect old edge. */
1008 redirect_edge_pred (e
, jump_block
);
1009 e
->probability
= REG_BR_PROB_BASE
;
1011 new_bb
= jump_block
;
1014 jump_block
= e
->src
;
1016 e
->flags
&= ~EDGE_FALLTHRU
;
1017 if (target
== EXIT_BLOCK_PTR
)
1020 emit_jump_insn_after (gen_return (), jump_block
->end
);
1026 rtx label
= block_label (target
);
1027 emit_jump_insn_after (gen_jump (label
), jump_block
->end
);
1028 JUMP_LABEL (jump_block
->end
) = label
;
1029 LABEL_NUSES (label
)++;
1032 emit_barrier_after (jump_block
->end
);
1033 redirect_edge_succ_nodup (e
, target
);
1035 if (abnormal_edge_flags
)
1036 make_edge (src
, target
, abnormal_edge_flags
);
1041 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1042 (and possibly create new basic block) to make edge non-fallthru.
1043 Return newly created BB or NULL if none. */
1046 force_nonfallthru (edge e
)
1048 return force_nonfallthru_and_redirect (e
, e
->dest
);
1051 /* Redirect edge even at the expense of creating new jump insn or
1052 basic block. Return new basic block if created, NULL otherwise.
1053 Abort if conversion is impossible. */
1056 rtl_redirect_edge_and_branch_force (edge e
, basic_block target
)
1058 if (redirect_edge_and_branch (e
, target
)
1059 || e
->dest
== target
)
1062 /* In case the edge redirection failed, try to force it to be non-fallthru
1063 and redirect newly created simplejump. */
1064 return force_nonfallthru_and_redirect (e
, target
);
1067 /* The given edge should potentially be a fallthru edge. If that is in
1068 fact true, delete the jump and barriers that are in the way. */
1071 tidy_fallthru_edge (edge e
, basic_block b
, basic_block c
)
1075 /* ??? In a late-running flow pass, other folks may have deleted basic
1076 blocks by nopping out blocks, leaving multiple BARRIERs between here
1077 and the target label. They ought to be chastized and fixed.
1079 We can also wind up with a sequence of undeletable labels between
1080 one block and the next.
1082 So search through a sequence of barriers, labels, and notes for
1083 the head of block C and assert that we really do fall through. */
1085 for (q
= NEXT_INSN (b
->end
); q
!= c
->head
; q
= NEXT_INSN (q
))
1089 /* Remove what will soon cease being the jump insn from the source block.
1090 If block B consisted only of this single jump, turn it into a deleted
1093 if (GET_CODE (q
) == JUMP_INSN
1095 && (any_uncondjump_p (q
)
1096 || (b
->succ
== e
&& e
->succ_next
== NULL
)))
1099 /* If this was a conditional jump, we need to also delete
1100 the insn that set cc0. */
1101 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1107 /* We don't want a block to end on a line-number note since that has
1108 the potential of changing the code between -g and not -g. */
1109 while (GET_CODE (q
) == NOTE
&& NOTE_LINE_NUMBER (q
) >= 0)
1113 /* Selectively unlink the sequence. */
1114 if (q
!= PREV_INSN (c
->head
))
1115 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (c
->head
));
1117 e
->flags
|= EDGE_FALLTHRU
;
1120 /* Fix up edges that now fall through, or rather should now fall through
1121 but previously required a jump around now deleted blocks. Simplify
1122 the search by only examining blocks numerically adjacent, since this
1123 is how find_basic_blocks created them. */
1126 tidy_fallthru_edges (void)
1130 if (ENTRY_BLOCK_PTR
->next_bb
== EXIT_BLOCK_PTR
)
1133 FOR_BB_BETWEEN (b
, ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
->prev_bb
, next_bb
)
1139 /* We care about simple conditional or unconditional jumps with
1142 If we had a conditional branch to the next instruction when
1143 find_basic_blocks was called, then there will only be one
1144 out edge for the block which ended with the conditional
1145 branch (since we do not create duplicate edges).
1147 Furthermore, the edge will be marked as a fallthru because we
1148 merge the flags for the duplicate edges. So we do not want to
1149 check that the edge is not a FALLTHRU edge. */
1151 if ((s
= b
->succ
) != NULL
1152 && ! (s
->flags
& EDGE_COMPLEX
)
1153 && s
->succ_next
== NULL
1155 /* If the jump insn has side effects, we can't tidy the edge. */
1156 && (GET_CODE (b
->end
) != JUMP_INSN
1157 || onlyjump_p (b
->end
)))
1158 tidy_fallthru_edge (s
, b
, c
);
1162 /* Helper function for split_edge. Return true in case edge BB2 to BB1
1163 is back edge of syntactic loop. */
1166 back_edge_of_syntactic_loop_p (basic_block bb1
, basic_block bb2
)
1175 /* ??? Could we guarantee that bb indices are monotone, so that we could
1176 just compare them? */
1177 for (bb
= bb1
; bb
&& bb
!= bb2
; bb
= bb
->next_bb
)
1183 for (insn
= bb1
->end
; insn
!= bb2
->head
&& count
>= 0;
1184 insn
= NEXT_INSN (insn
))
1185 if (GET_CODE (insn
) == NOTE
)
1187 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
1189 else if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
)
1196 /* Split a (typically critical) edge. Return the new block.
1197 Abort on abnormal edges.
1199 ??? The code generally expects to be called on critical edges.
1200 The case of a block ending in an unconditional jump to a
1201 block with multiple predecessors is not handled optimally. */
1204 rtl_split_edge (edge edge_in
)
1209 /* Abnormal edges cannot be split. */
1210 if ((edge_in
->flags
& EDGE_ABNORMAL
) != 0)
1213 /* We are going to place the new block in front of edge destination.
1214 Avoid existence of fallthru predecessors. */
1215 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1219 for (e
= edge_in
->dest
->pred
; e
; e
= e
->pred_next
)
1220 if (e
->flags
& EDGE_FALLTHRU
)
1224 force_nonfallthru (e
);
1227 /* Create the basic block note.
1229 Where we place the note can have a noticeable impact on the generated
1230 code. Consider this cfg:
1240 If we need to insert an insn on the edge from block 0 to block 1,
1241 we want to ensure the instructions we insert are outside of any
1242 loop notes that physically sit between block 0 and block 1. Otherwise
1243 we confuse the loop optimizer into thinking the loop is a phony. */
1245 if (edge_in
->dest
!= EXIT_BLOCK_PTR
1246 && PREV_INSN (edge_in
->dest
->head
)
1247 && GET_CODE (PREV_INSN (edge_in
->dest
->head
)) == NOTE
1248 && (NOTE_LINE_NUMBER (PREV_INSN (edge_in
->dest
->head
))
1249 == NOTE_INSN_LOOP_BEG
)
1250 && !back_edge_of_syntactic_loop_p (edge_in
->dest
, edge_in
->src
))
1251 before
= PREV_INSN (edge_in
->dest
->head
);
1252 else if (edge_in
->dest
!= EXIT_BLOCK_PTR
)
1253 before
= edge_in
->dest
->head
;
1257 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1258 bb
->count
= edge_in
->count
;
1259 bb
->frequency
= EDGE_FREQUENCY (edge_in
);
1261 /* ??? This info is likely going to be out of date very soon. */
1262 if (edge_in
->dest
->global_live_at_start
)
1264 bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1265 bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1266 COPY_REG_SET (bb
->global_live_at_start
,
1267 edge_in
->dest
->global_live_at_start
);
1268 COPY_REG_SET (bb
->global_live_at_end
,
1269 edge_in
->dest
->global_live_at_start
);
1272 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1274 /* For non-fallthry edges, we must adjust the predecessor's
1275 jump instruction to target our new block. */
1276 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1278 if (!redirect_edge_and_branch (edge_in
, bb
))
1282 redirect_edge_succ (edge_in
, bb
);
1287 /* Queue instructions for insertion on an edge between two basic blocks.
1288 The new instructions and basic blocks (if any) will not appear in the
1289 CFG until commit_edge_insertions is called. */
1292 insert_insn_on_edge (rtx pattern
, edge e
)
1294 /* We cannot insert instructions on an abnormal critical edge.
1295 It will be easier to find the culprit if we die now. */
1296 if ((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
1299 if (e
->insns
== NULL_RTX
)
1302 push_to_sequence (e
->insns
);
1304 emit_insn (pattern
);
1306 e
->insns
= get_insns ();
1310 /* Called from safe_insert_insn_on_edge through note_stores, marks live
1311 registers that are killed by the store. */
1313 mark_killed_regs (rtx reg
, rtx set ATTRIBUTE_UNUSED
, void *data
)
1315 regset killed
= data
;
1318 if (GET_CODE (reg
) == SUBREG
)
1319 reg
= SUBREG_REG (reg
);
1322 regno
= REGNO (reg
);
1323 if (regno
>= FIRST_PSEUDO_REGISTER
)
1324 SET_REGNO_REG_SET (killed
, regno
);
1327 for (i
= 0; i
< HARD_REGNO_NREGS (regno
, GET_MODE (reg
)); i
++)
1328 SET_REGNO_REG_SET (killed
, regno
+ i
);
1332 /* Similar to insert_insn_on_edge, tries to put INSN to edge E. Additionally
1333 it checks whether this will not clobber the registers that are live on the
1334 edge (i.e. it requieres liveness information to be up-to-date) and if there
1335 are some, then it tries to save and restore them. Returns true if
1338 safe_insert_insn_on_edge (rtx insn
, edge e
)
1341 regset_head killed_head
;
1342 regset killed
= INITIALIZE_REG_SET (killed_head
);
1343 rtx save_regs
= NULL_RTX
;
1344 int regno
, noccmode
;
1345 enum machine_mode mode
;
1347 #ifdef AVOID_CCMODE_COPIES
1353 for (x
= insn
; x
; x
= NEXT_INSN (x
))
1355 note_stores (PATTERN (x
), mark_killed_regs
, killed
);
1356 bitmap_operation (killed
, killed
, e
->dest
->global_live_at_start
,
1359 EXECUTE_IF_SET_IN_REG_SET (killed
, 0, regno
,
1361 mode
= regno
< FIRST_PSEUDO_REGISTER
1362 ? reg_raw_mode
[regno
]
1363 : GET_MODE (regno_reg_rtx
[regno
]);
1364 if (mode
== VOIDmode
)
1367 if (noccmode
&& mode
== CCmode
)
1370 save_regs
= alloc_EXPR_LIST (0,
1373 gen_raw_REG (mode
, regno
)),
1382 for (x
= save_regs
; x
; x
= XEXP (x
, 1))
1384 from
= XEXP (XEXP (x
, 0), 1);
1385 to
= XEXP (XEXP (x
, 0), 0);
1386 emit_move_insn (to
, from
);
1389 for (x
= save_regs
; x
; x
= XEXP (x
, 1))
1391 from
= XEXP (XEXP (x
, 0), 0);
1392 to
= XEXP (XEXP (x
, 0), 1);
1393 emit_move_insn (to
, from
);
1395 insn
= get_insns ();
1397 free_EXPR_LIST_list (&save_regs
);
1399 insert_insn_on_edge (insn
, e
);
1401 FREE_REG_SET (killed
);
1405 /* Update the CFG for the instructions queued on edge E. */
1408 commit_one_edge_insertion (edge e
, int watch_calls
)
1410 rtx before
= NULL_RTX
, after
= NULL_RTX
, insns
, tmp
, last
;
1411 basic_block bb
= NULL
;
1413 /* Pull the insns off the edge now since the edge might go away. */
1415 e
->insns
= NULL_RTX
;
1417 /* Special case -- avoid inserting code between call and storing
1418 its return value. */
1419 if (watch_calls
&& (e
->flags
& EDGE_FALLTHRU
) && !e
->dest
->pred
->pred_next
1420 && e
->src
!= ENTRY_BLOCK_PTR
1421 && GET_CODE (e
->src
->end
) == CALL_INSN
)
1423 rtx next
= next_nonnote_insn (e
->src
->end
);
1425 after
= e
->dest
->head
;
1426 /* The first insn after the call may be a stack pop, skip it. */
1428 && keep_with_call_p (next
))
1431 next
= next_nonnote_insn (next
);
1435 if (!before
&& !after
)
1437 /* Figure out where to put these things. If the destination has
1438 one predecessor, insert there. Except for the exit block. */
1439 if (e
->dest
->pred
->pred_next
== NULL
&& e
->dest
!= EXIT_BLOCK_PTR
)
1443 /* Get the location correct wrt a code label, and "nice" wrt
1444 a basic block note, and before everything else. */
1446 if (GET_CODE (tmp
) == CODE_LABEL
)
1447 tmp
= NEXT_INSN (tmp
);
1448 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1449 tmp
= NEXT_INSN (tmp
);
1450 if (tmp
== bb
->head
)
1453 after
= PREV_INSN (tmp
);
1455 after
= get_last_insn ();
1458 /* If the source has one successor and the edge is not abnormal,
1459 insert there. Except for the entry block. */
1460 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1461 && e
->src
->succ
->succ_next
== NULL
1462 && e
->src
!= ENTRY_BLOCK_PTR
)
1466 /* It is possible to have a non-simple jump here. Consider a target
1467 where some forms of unconditional jumps clobber a register. This
1468 happens on the fr30 for example.
1470 We know this block has a single successor, so we can just emit
1471 the queued insns before the jump. */
1472 if (GET_CODE (bb
->end
) == JUMP_INSN
)
1473 for (before
= bb
->end
;
1474 GET_CODE (PREV_INSN (before
)) == NOTE
1475 && NOTE_LINE_NUMBER (PREV_INSN (before
)) ==
1476 NOTE_INSN_LOOP_BEG
; before
= PREV_INSN (before
))
1480 /* We'd better be fallthru, or we've lost track of what's what. */
1481 if ((e
->flags
& EDGE_FALLTHRU
) == 0)
1487 /* Otherwise we must split the edge. */
1490 bb
= split_edge (e
);
1495 /* Now that we've found the spot, do the insertion. */
1499 emit_insn_before (insns
, before
);
1500 last
= prev_nonnote_insn (before
);
1503 last
= emit_insn_after (insns
, after
);
1505 if (returnjump_p (last
))
1507 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1508 This is not currently a problem because this only happens
1509 for the (single) epilogue, which already has a fallthru edge
1513 if (e
->dest
!= EXIT_BLOCK_PTR
1514 || e
->succ_next
!= NULL
|| (e
->flags
& EDGE_FALLTHRU
) == 0)
1517 e
->flags
&= ~EDGE_FALLTHRU
;
1518 emit_barrier_after (last
);
1521 delete_insn (before
);
1523 else if (GET_CODE (last
) == JUMP_INSN
)
1526 /* Mark the basic block for find_sub_basic_blocks. */
1530 /* Update the CFG for all queued instructions. */
1533 commit_edge_insertions (void)
1537 bool changed
= false;
1539 #ifdef ENABLE_CHECKING
1540 verify_flow_info ();
1543 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
1547 for (e
= bb
->succ
; e
; e
= next
)
1549 next
= e
->succ_next
;
1553 commit_one_edge_insertion (e
, false);
1561 blocks
= sbitmap_alloc (last_basic_block
);
1562 sbitmap_zero (blocks
);
1566 SET_BIT (blocks
, bb
->index
);
1567 /* Check for forgotten bb->aux values before commit_edge_insertions
1569 if (bb
->aux
!= &bb
->aux
)
1573 find_many_sub_basic_blocks (blocks
);
1574 sbitmap_free (blocks
);
1577 /* Update the CFG for all queued instructions, taking special care of inserting
1578 code on edges between call and storing its return value. */
1581 commit_edge_insertions_watch_calls (void)
1585 bool changed
= false;
1587 #ifdef ENABLE_CHECKING
1588 verify_flow_info ();
1591 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
1595 for (e
= bb
->succ
; e
; e
= next
)
1597 next
= e
->succ_next
;
1601 commit_one_edge_insertion (e
, true);
1609 blocks
= sbitmap_alloc (last_basic_block
);
1610 sbitmap_zero (blocks
);
1614 SET_BIT (blocks
, bb
->index
);
1615 /* Check for forgotten bb->aux values before commit_edge_insertions
1617 if (bb
->aux
!= &bb
->aux
)
1621 find_many_sub_basic_blocks (blocks
);
1622 sbitmap_free (blocks
);
1625 /* Print out one basic block with live information at start and end. */
1628 rtl_dump_bb (basic_block bb
, FILE *outf
)
1633 fputs (";; Registers live at start:", outf
);
1634 dump_regset (bb
->global_live_at_start
, outf
);
1637 for (insn
= bb
->head
, last
= NEXT_INSN (bb
->end
); insn
!= last
;
1638 insn
= NEXT_INSN (insn
))
1639 print_rtl_single (outf
, insn
);
1641 fputs (";; Registers live at end:", outf
);
1642 dump_regset (bb
->global_live_at_end
, outf
);
1646 /* Like print_rtl, but also print out live information for the start of each
1650 print_rtl_with_bb (FILE *outf
, rtx rtx_first
)
1655 fprintf (outf
, "(nil)\n");
1658 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
1659 int max_uid
= get_max_uid ();
1661 = (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1663 = (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1664 enum bb_state
*in_bb_p
1665 = (enum bb_state
*) xcalloc (max_uid
, sizeof (enum bb_state
));
1669 FOR_EACH_BB_REVERSE (bb
)
1673 start
[INSN_UID (bb
->head
)] = bb
;
1674 end
[INSN_UID (bb
->end
)] = bb
;
1675 for (x
= bb
->head
; x
!= NULL_RTX
; x
= NEXT_INSN (x
))
1677 enum bb_state state
= IN_MULTIPLE_BB
;
1679 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
1681 in_bb_p
[INSN_UID (x
)] = state
;
1688 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
1692 if ((bb
= start
[INSN_UID (tmp_rtx
)]) != NULL
)
1694 fprintf (outf
, ";; Start of basic block %d, registers live:",
1696 dump_regset (bb
->global_live_at_start
, outf
);
1700 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
1701 && GET_CODE (tmp_rtx
) != NOTE
1702 && GET_CODE (tmp_rtx
) != BARRIER
)
1703 fprintf (outf
, ";; Insn is not within a basic block\n");
1704 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
1705 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
1707 did_output
= print_rtl_single (outf
, tmp_rtx
);
1709 if ((bb
= end
[INSN_UID (tmp_rtx
)]) != NULL
)
1711 fprintf (outf
, ";; End of basic block %d, registers live:\n",
1713 dump_regset (bb
->global_live_at_end
, outf
);
1726 if (current_function_epilogue_delay_list
!= 0)
1728 fprintf (outf
, "\n;; Insns in epilogue delay list:\n\n");
1729 for (tmp_rtx
= current_function_epilogue_delay_list
; tmp_rtx
!= 0;
1730 tmp_rtx
= XEXP (tmp_rtx
, 1))
1731 print_rtl_single (outf
, XEXP (tmp_rtx
, 0));
1736 update_br_prob_note (basic_block bb
)
1739 if (GET_CODE (bb
->end
) != JUMP_INSN
)
1741 note
= find_reg_note (bb
->end
, REG_BR_PROB
, NULL_RTX
);
1742 if (!note
|| INTVAL (XEXP (note
, 0)) == BRANCH_EDGE (bb
)->probability
)
1744 XEXP (note
, 0) = GEN_INT (BRANCH_EDGE (bb
)->probability
);
1747 /* Verify the CFG and RTL consistency common for both underlying RTL and
1750 Currently it does following checks:
1752 - test head/end pointers
1753 - overlapping of basic blocks
1754 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1755 - tails of basic blocks (ensure that boundary is necessary)
1756 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1757 and NOTE_INSN_BASIC_BLOCK
1759 In future it can be extended check a lot of other stuff as well
1760 (reachability of basic blocks, life information, etc. etc.). */
1762 rtl_verify_flow_info_1 (void)
1764 const int max_uid
= get_max_uid ();
1765 rtx last_head
= get_last_insn ();
1766 basic_block
*bb_info
;
1769 basic_block bb
, last_bb_seen
;
1771 bb_info
= (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1773 /* Check bb chain & numbers. */
1774 last_bb_seen
= ENTRY_BLOCK_PTR
;
1776 FOR_EACH_BB_REVERSE (bb
)
1778 rtx head
= bb
->head
;
1781 /* Verify the end of the basic block is in the INSN chain. */
1782 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1788 error ("end insn %d for block %d not found in the insn stream",
1789 INSN_UID (end
), bb
->index
);
1793 /* Work backwards from the end to the head of the basic block
1794 to verify the head is in the RTL chain. */
1795 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1797 /* While walking over the insn chain, verify insns appear
1798 in only one basic block and initialize the BB_INFO array
1799 used by other passes. */
1800 if (bb_info
[INSN_UID (x
)] != NULL
)
1802 error ("insn %d is in multiple basic blocks (%d and %d)",
1803 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
1807 bb_info
[INSN_UID (x
)] = bb
;
1814 error ("head insn %d for block %d not found in the insn stream",
1815 INSN_UID (head
), bb
->index
);
1822 /* Now check the basic blocks (boundaries etc.) */
1823 FOR_EACH_BB_REVERSE (bb
)
1825 int n_fallthru
= 0, n_eh
= 0, n_call
= 0, n_abnormal
= 0, n_branch
= 0;
1829 if (INSN_P (bb
->end
)
1830 && (note
= find_reg_note (bb
->end
, REG_BR_PROB
, NULL_RTX
))
1831 && bb
->succ
&& bb
->succ
->succ_next
1832 && any_condjump_p (bb
->end
))
1834 if (INTVAL (XEXP (note
, 0)) != BRANCH_EDGE (bb
)->probability
)
1836 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
1837 INTVAL (XEXP (note
, 0)), BRANCH_EDGE (bb
)->probability
);
1841 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1843 if (e
->flags
& EDGE_FALLTHRU
)
1846 if ((e
->flags
& ~(EDGE_DFS_BACK
| EDGE_CAN_FALLTHRU
| EDGE_IRREDUCIBLE_LOOP
)) == 0)
1849 if (e
->flags
& EDGE_ABNORMAL_CALL
)
1852 if (e
->flags
& EDGE_EH
)
1854 else if (e
->flags
& EDGE_ABNORMAL
)
1858 if (n_eh
&& GET_CODE (PATTERN (bb
->end
)) != RESX
1859 && !find_reg_note (bb
->end
, REG_EH_REGION
, NULL_RTX
))
1861 error ("Missing REG_EH_REGION note in the end of bb %i", bb
->index
);
1865 && (GET_CODE (bb
->end
) != JUMP_INSN
1866 || (n_branch
> 1 && (any_uncondjump_p (bb
->end
)
1867 || any_condjump_p (bb
->end
)))))
1869 error ("Too many outgoing branch edges from bb %i", bb
->index
);
1872 if (n_fallthru
&& any_uncondjump_p (bb
->end
))
1874 error ("Fallthru edge after unconditional jump %i", bb
->index
);
1877 if (n_branch
!= 1 && any_uncondjump_p (bb
->end
))
1879 error ("Wrong amount of branch edges after unconditional jump %i", bb
->index
);
1882 if (n_branch
!= 1 && any_condjump_p (bb
->end
)
1883 && JUMP_LABEL (bb
->end
) != bb
->next_bb
->head
)
1885 error ("Wrong amount of branch edges after conditional jump %i", bb
->index
);
1888 if (n_call
&& GET_CODE (bb
->end
) != CALL_INSN
)
1890 error ("Call edges for non-call insn in bb %i", bb
->index
);
1894 && (GET_CODE (bb
->end
) != CALL_INSN
&& n_call
!= n_abnormal
)
1895 && (GET_CODE (bb
->end
) != JUMP_INSN
1896 || any_condjump_p (bb
->end
)
1897 || any_uncondjump_p (bb
->end
)))
1899 error ("Abnormal edges for no purpose in bb %i", bb
->index
);
1903 for (x
= bb
->head
; x
!= NEXT_INSN (bb
->end
); x
= NEXT_INSN (x
))
1904 if (BLOCK_FOR_INSN (x
) != bb
)
1907 if (! BLOCK_FOR_INSN (x
))
1909 ("insn %d inside basic block %d but block_for_insn is NULL",
1910 INSN_UID (x
), bb
->index
);
1913 ("insn %d inside basic block %d but block_for_insn is %i",
1914 INSN_UID (x
), bb
->index
, BLOCK_FOR_INSN (x
)->index
);
1919 /* OK pointers are correct. Now check the header of basic
1920 block. It ought to contain optional CODE_LABEL followed
1921 by NOTE_BASIC_BLOCK. */
1923 if (GET_CODE (x
) == CODE_LABEL
)
1927 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1935 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
1937 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1943 /* Do checks for empty blocks her. e */
1946 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
1948 if (NOTE_INSN_BASIC_BLOCK_P (x
))
1950 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
1951 INSN_UID (x
), bb
->index
);
1958 if (control_flow_insn_p (x
))
1960 error ("in basic block %d:", bb
->index
);
1961 fatal_insn ("flow control insn inside a basic block", x
);
1971 /* Verify the CFG and RTL consistency common for both underlying RTL and
1974 Currently it does following checks:
1975 - all checks of rtl_verify_flow_info_1
1976 - check that all insns are in the basic blocks
1977 (except the switch handling code, barriers and notes)
1978 - check that all returns are followed by barriers
1979 - check that all fallthru edge points to the adjacent blocks. */
1981 rtl_verify_flow_info (void)
1984 int err
= rtl_verify_flow_info_1 ();
1987 const rtx rtx_first
= get_insns ();
1988 basic_block last_bb_seen
= ENTRY_BLOCK_PTR
, curr_bb
= NULL
;
1990 FOR_EACH_BB_REVERSE (bb
)
1993 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1994 if (e
->flags
& EDGE_FALLTHRU
)
2000 /* Ensure existence of barrier in BB with no fallthru edges. */
2001 for (insn
= bb
->end
; !insn
|| GET_CODE (insn
) != BARRIER
;
2002 insn
= NEXT_INSN (insn
))
2004 || (GET_CODE (insn
) == NOTE
2005 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BASIC_BLOCK
))
2007 error ("missing barrier after block %i", bb
->index
);
2012 else if (e
->src
!= ENTRY_BLOCK_PTR
2013 && e
->dest
!= EXIT_BLOCK_PTR
)
2017 if (e
->src
->next_bb
!= e
->dest
)
2020 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2021 e
->src
->index
, e
->dest
->index
);
2025 for (insn
= NEXT_INSN (e
->src
->end
); insn
!= e
->dest
->head
;
2026 insn
= NEXT_INSN (insn
))
2027 if (GET_CODE (insn
) == BARRIER
2028 #ifndef CASE_DROPS_THROUGH
2031 || (INSN_P (insn
) && ! JUMP_TABLE_DATA_P (insn
))
2035 error ("verify_flow_info: Incorrect fallthru %i->%i",
2036 e
->src
->index
, e
->dest
->index
);
2037 fatal_insn ("wrong insn in the fallthru edge", insn
);
2044 last_bb_seen
= ENTRY_BLOCK_PTR
;
2046 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2048 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2050 bb
= NOTE_BASIC_BLOCK (x
);
2053 if (bb
!= last_bb_seen
->next_bb
)
2054 internal_error ("basic blocks not laid down consecutively");
2056 curr_bb
= last_bb_seen
= bb
;
2061 switch (GET_CODE (x
))
2068 /* An addr_vec is placed outside any block block. */
2070 && GET_CODE (NEXT_INSN (x
)) == JUMP_INSN
2071 && (GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_DIFF_VEC
2072 || GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_VEC
))
2075 /* But in any case, non-deletable labels can appear anywhere. */
2079 fatal_insn ("insn outside basic block", x
);
2084 && GET_CODE (x
) == JUMP_INSN
2085 && returnjump_p (x
) && ! condjump_p (x
)
2086 && ! (NEXT_INSN (x
) && GET_CODE (NEXT_INSN (x
)) == BARRIER
))
2087 fatal_insn ("return not followed by barrier", x
);
2088 if (curr_bb
&& x
== curr_bb
->end
)
2092 if (num_bb_notes
!= n_basic_blocks
)
2094 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2095 num_bb_notes
, n_basic_blocks
);
2100 /* Assume that the preceding pass has possibly eliminated jump instructions
2101 or converted the unconditional jumps. Eliminate the edges from CFG.
2102 Return true if any edges are eliminated. */
2105 purge_dead_edges (basic_block bb
)
2108 rtx insn
= bb
->end
, note
;
2109 bool purged
= false;
2111 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2112 if (GET_CODE (insn
) == INSN
2113 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
2117 if (! may_trap_p (PATTERN (insn
))
2118 || ((eqnote
= find_reg_equal_equiv_note (insn
))
2119 && ! may_trap_p (XEXP (eqnote
, 0))))
2120 remove_note (insn
, note
);
2123 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
2124 for (e
= bb
->succ
; e
; e
= next
)
2126 next
= e
->succ_next
;
2127 if (e
->flags
& EDGE_EH
)
2129 if (can_throw_internal (bb
->end
))
2132 else if (e
->flags
& EDGE_ABNORMAL_CALL
)
2134 if (GET_CODE (bb
->end
) == CALL_INSN
2135 && (! (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
))
2136 || INTVAL (XEXP (note
, 0)) >= 0))
2143 bb
->flags
|= BB_DIRTY
;
2147 if (GET_CODE (insn
) == JUMP_INSN
)
2152 /* We do care only about conditional jumps and simplejumps. */
2153 if (!any_condjump_p (insn
)
2154 && !returnjump_p (insn
)
2155 && !simplejump_p (insn
))
2158 /* Branch probability/prediction notes are defined only for
2159 condjumps. We've possibly turned condjump into simplejump. */
2160 if (simplejump_p (insn
))
2162 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2164 remove_note (insn
, note
);
2165 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
2166 remove_note (insn
, note
);
2169 for (e
= bb
->succ
; e
; e
= next
)
2171 next
= e
->succ_next
;
2173 /* Avoid abnormal flags to leak from computed jumps turned
2174 into simplejumps. */
2176 e
->flags
&= ~EDGE_ABNORMAL
;
2178 /* See if this edge is one we should keep. */
2179 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
2180 /* A conditional jump can fall through into the next
2181 block, so we should keep the edge. */
2183 else if (e
->dest
!= EXIT_BLOCK_PTR
2184 && e
->dest
->head
== JUMP_LABEL (insn
))
2185 /* If the destination block is the target of the jump,
2188 else if (e
->dest
== EXIT_BLOCK_PTR
&& returnjump_p (insn
))
2189 /* If the destination block is the exit block, and this
2190 instruction is a return, then keep the edge. */
2192 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
2193 /* Keep the edges that correspond to exceptions thrown by
2194 this instruction. */
2197 /* We do not need this edge. */
2198 bb
->flags
|= BB_DIRTY
;
2203 if (!bb
->succ
|| !purged
)
2207 fprintf (rtl_dump_file
, "Purged edges from bb %i\n", bb
->index
);
2212 /* Redistribute probabilities. */
2213 if (!bb
->succ
->succ_next
)
2215 bb
->succ
->probability
= REG_BR_PROB_BASE
;
2216 bb
->succ
->count
= bb
->count
;
2220 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2224 b
= BRANCH_EDGE (bb
);
2225 f
= FALLTHRU_EDGE (bb
);
2226 b
->probability
= INTVAL (XEXP (note
, 0));
2227 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
2228 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
2229 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
2234 else if (GET_CODE (insn
) == CALL_INSN
&& SIBLING_CALL_P (insn
))
2236 /* First, there should not be any EH or ABCALL edges resulting
2237 from non-local gotos and the like. If there were, we shouldn't
2238 have created the sibcall in the first place. Second, there
2239 should of course never have been a fallthru edge. */
2240 if (!bb
->succ
|| bb
->succ
->succ_next
)
2242 if (bb
->succ
->flags
!= (EDGE_SIBCALL
| EDGE_ABNORMAL
))
2248 /* If we don't see a jump insn, we don't know exactly why the block would
2249 have been broken at this point. Look for a simple, non-fallthru edge,
2250 as these are only created by conditional branches. If we find such an
2251 edge we know that there used to be a jump here and can then safely
2252 remove all non-fallthru edges. */
2253 for (e
= bb
->succ
; e
&& (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
));
2260 for (e
= bb
->succ
; e
; e
= next
)
2262 next
= e
->succ_next
;
2263 if (!(e
->flags
& EDGE_FALLTHRU
))
2265 bb
->flags
|= BB_DIRTY
;
2271 if (!bb
->succ
|| bb
->succ
->succ_next
)
2274 bb
->succ
->probability
= REG_BR_PROB_BASE
;
2275 bb
->succ
->count
= bb
->count
;
2278 fprintf (rtl_dump_file
, "Purged non-fallthru edges from bb %i\n",
2283 /* Search all basic blocks for potentially dead edges and purge them. Return
2284 true if some edge has been eliminated. */
2287 purge_all_dead_edges (int update_life_p
)
2295 blocks
= sbitmap_alloc (last_basic_block
);
2296 sbitmap_zero (blocks
);
2301 bool purged_here
= purge_dead_edges (bb
);
2303 purged
|= purged_here
;
2304 if (purged_here
&& update_life_p
)
2305 SET_BIT (blocks
, bb
->index
);
2308 if (update_life_p
&& purged
)
2309 update_life_info (blocks
, UPDATE_LIFE_GLOBAL
,
2310 PROP_DEATH_NOTES
| PROP_SCAN_DEAD_CODE
2311 | PROP_KILL_DEAD_CODE
);
2314 sbitmap_free (blocks
);
2318 /* Same as split_block but update cfg_layout structures. */
2320 cfg_layout_split_block (basic_block bb
, void *insnp
)
2324 edge fallthru
= rtl_split_block (bb
, insn
);
2326 alloc_aux_for_block (fallthru
->dest
, sizeof (struct reorder_block_def
));
2327 RBI (fallthru
->dest
)->footer
= RBI (fallthru
->src
)->footer
;
2328 RBI (fallthru
->src
)->footer
= NULL
;
2333 /* Redirect Edge to DEST. */
2335 cfg_layout_redirect_edge_and_branch (edge e
, basic_block dest
)
2337 basic_block src
= e
->src
;
2338 basic_block old_next_bb
= src
->next_bb
;
2341 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
2342 in the case the basic block appears to be in sequence. Avoid this
2345 src
->next_bb
= NULL
;
2346 if (e
->flags
& EDGE_FALLTHRU
)
2348 /* Redirect any branch edges unified with the fallthru one. */
2349 if (GET_CODE (src
->end
) == JUMP_INSN
2350 && JUMP_LABEL (src
->end
) == e
->dest
->head
)
2352 if (!redirect_jump (src
->end
, block_label (dest
), 0))
2355 /* In case we are redirecting fallthru edge to the branch edge
2356 of conditional jump, remove it. */
2357 if (src
->succ
->succ_next
2358 && !src
->succ
->succ_next
->succ_next
)
2360 edge s
= e
->succ_next
? e
->succ_next
: src
->succ
;
2362 && any_condjump_p (src
->end
)
2363 && onlyjump_p (src
->end
))
2364 delete_insn (src
->end
);
2366 redirect_edge_succ_nodup (e
, dest
);
2371 ret
= rtl_redirect_edge_and_branch (e
, dest
);
2373 /* We don't want simplejumps in the insn stream during cfglayout. */
2374 if (simplejump_p (src
->end
))
2376 delete_insn (src
->end
);
2377 delete_barrier (NEXT_INSN (src
->end
));
2378 src
->succ
->flags
|= EDGE_FALLTHRU
;
2380 src
->next_bb
= old_next_bb
;
2385 /* Simple wrapper as we always can redirect fallthru edges. */
2387 cfg_layout_redirect_edge_and_branch_force (edge e
, basic_block dest
)
2389 if (!cfg_layout_redirect_edge_and_branch (e
, dest
))
2394 /* Same as flow_delete_block but update cfg_layout structures. */
2396 cfg_layout_delete_block (basic_block bb
)
2398 rtx insn
, next
, prev
= PREV_INSN (bb
->head
), *to
, remaints
;
2400 if (RBI (bb
)->header
)
2404 NEXT_INSN (prev
) = RBI (bb
)->header
;
2406 set_first_insn (RBI (bb
)->header
);
2407 PREV_INSN (RBI (bb
)->header
) = prev
;
2408 insn
= RBI (bb
)->header
;
2409 while (NEXT_INSN (insn
))
2410 insn
= NEXT_INSN (insn
);
2411 NEXT_INSN (insn
) = next
;
2412 PREV_INSN (next
) = insn
;
2414 next
= NEXT_INSN (bb
->end
);
2415 if (RBI (bb
)->footer
)
2418 NEXT_INSN (insn
) = RBI (bb
)->footer
;
2419 PREV_INSN (RBI (bb
)->footer
) = insn
;
2420 while (NEXT_INSN (insn
))
2421 insn
= NEXT_INSN (insn
);
2422 NEXT_INSN (insn
) = next
;
2424 PREV_INSN (next
) = insn
;
2426 set_last_insn (insn
);
2428 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
2429 to
= &RBI(bb
->next_bb
)->header
;
2431 to
= &cfg_layout_function_footer
;
2432 rtl_delete_block (bb
);
2435 prev
= NEXT_INSN (prev
);
2437 prev
= get_insns ();
2439 next
= PREV_INSN (next
);
2441 next
= get_last_insn ();
2443 if (next
&& NEXT_INSN (next
) != prev
)
2445 remaints
= unlink_insn_chain (prev
, next
);
2447 while (NEXT_INSN (insn
))
2448 insn
= NEXT_INSN (insn
);
2449 NEXT_INSN (insn
) = *to
;
2451 PREV_INSN (*to
) = insn
;
2456 /* Implementation of CFG manipulation for linearized RTL. */
2457 struct cfg_hooks rtl_cfg_hooks
= {
2458 rtl_verify_flow_info
,
2460 rtl_redirect_edge_and_branch
,
2461 rtl_redirect_edge_and_branch_force
,
2467 /* Implementation of CFG manipulation for cfg layout RTL, where
2468 basic block connected via fallthru edges does not have to be adjacent.
2469 This representation will hopefully become the default one in future
2470 version of the compiler. */
2471 struct cfg_hooks cfg_layout_rtl_cfg_hooks
= {
2472 rtl_verify_flow_info_1
, /* verify_flow_info. */
2474 cfg_layout_redirect_edge_and_branch
,
2475 cfg_layout_redirect_edge_and_branch_force
,
2476 cfg_layout_delete_block
,
2477 cfg_layout_split_block
,
2478 NULL
/* split_edge. */