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 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, flow_delete_block, 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 commiting to edges
37 split_edge, insert_insn_on_edge, commit_edge_insertions
38 - Dumping and debugging
39 print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
40 - Consistency checking
42 - CFG updating after constant propagation
43 purge_dead_edges, purge_all_dead_edges */
49 #include "hard-reg-set.h"
50 #include "basic-block.h"
59 #include "insn-config.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
PARAMS ((rtx
));
74 static int can_delete_label_p
PARAMS ((rtx
));
75 static void commit_one_edge_insertion
PARAMS ((edge
, int));
76 static bool try_redirect_by_replacing_jump
PARAMS ((edge
, basic_block
));
77 static rtx last_loop_beg_note
PARAMS ((rtx
));
78 static bool back_edge_of_syntactic_loop_p
PARAMS ((basic_block
, basic_block
));
79 static basic_block force_nonfallthru_and_redirect
PARAMS ((edge
, basic_block
));
81 /* Return true if NOTE is not one of the ones that must be kept paired,
82 so that we may simply delete it. */
85 can_delete_note_p (note
)
88 return (NOTE_LINE_NUMBER (note
) == NOTE_INSN_DELETED
89 || NOTE_LINE_NUMBER (note
) == NOTE_INSN_BASIC_BLOCK
90 || NOTE_LINE_NUMBER (note
) == NOTE_INSN_PREDICTION
);
93 /* True if a given label can be deleted. */
96 can_delete_label_p (label
)
99 return (!LABEL_PRESERVE_P (label
)
100 /* User declared labels must be preserved. */
101 && LABEL_NAME (label
) == 0
102 && !in_expr_list_p (forced_labels
, label
)
103 && !in_expr_list_p (label_value_list
, label
));
106 /* Delete INSN by patching it out. Return the next insn. */
112 rtx next
= NEXT_INSN (insn
);
114 bool really_delete
= true;
116 if (GET_CODE (insn
) == CODE_LABEL
)
118 /* Some labels can't be directly removed from the INSN chain, as they
119 might be references via variables, constant pool etc.
120 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
121 if (! can_delete_label_p (insn
))
123 const char *name
= LABEL_NAME (insn
);
125 really_delete
= false;
126 PUT_CODE (insn
, NOTE
);
127 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED_LABEL
;
128 NOTE_SOURCE_FILE (insn
) = name
;
131 remove_node_from_expr_list (insn
, &nonlocal_goto_handler_labels
);
136 /* If this insn has already been deleted, something is very wrong. */
137 if (INSN_DELETED_P (insn
))
140 INSN_DELETED_P (insn
) = 1;
143 /* If deleting a jump, decrement the use count of the label. Deleting
144 the label itself should happen in the normal course of block merging. */
145 if (GET_CODE (insn
) == JUMP_INSN
147 && GET_CODE (JUMP_LABEL (insn
)) == CODE_LABEL
)
148 LABEL_NUSES (JUMP_LABEL (insn
))--;
150 /* Also if deleting an insn that references a label. */
151 else if ((note
= find_reg_note (insn
, REG_LABEL
, NULL_RTX
)) != NULL_RTX
152 && GET_CODE (XEXP (note
, 0)) == CODE_LABEL
)
153 LABEL_NUSES (XEXP (note
, 0))--;
155 if (GET_CODE (insn
) == JUMP_INSN
156 && (GET_CODE (PATTERN (insn
)) == ADDR_VEC
157 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
))
159 rtx pat
= PATTERN (insn
);
160 int diff_vec_p
= GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
;
161 int len
= XVECLEN (pat
, diff_vec_p
);
164 for (i
= 0; i
< len
; i
++)
166 rtx label
= XEXP (XVECEXP (pat
, diff_vec_p
, i
), 0);
168 /* When deleting code in bulk (e.g. removing many unreachable
169 blocks) we can delete a label that's a target of the vector
170 before deleting the vector itself. */
171 if (GET_CODE (label
) != NOTE
)
172 LABEL_NUSES (label
)--;
179 /* Like delete_insn but also purge dead edges from BB. */
181 delete_insn_and_edges (insn
)
188 && BLOCK_FOR_INSN (insn
)
189 && BLOCK_FOR_INSN (insn
)->end
== insn
)
191 x
= delete_insn (insn
);
193 purge_dead_edges (BLOCK_FOR_INSN (insn
));
197 /* Unlink a chain of insns between START and FINISH, leaving notes
198 that must be paired. */
201 delete_insn_chain (start
, finish
)
206 /* Unchain the insns one by one. It would be quicker to delete all of these
207 with a single unchaining, rather than one at a time, but we need to keep
211 next
= NEXT_INSN (start
);
212 if (GET_CODE (start
) == NOTE
&& !can_delete_note_p (start
))
215 next
= delete_insn (start
);
223 /* Like delete_insn but also purge dead edges from BB. */
225 delete_insn_chain_and_edges (first
, last
)
231 && BLOCK_FOR_INSN (last
)
232 && BLOCK_FOR_INSN (last
)->end
== last
)
234 delete_insn_chain (first
, last
);
236 purge_dead_edges (BLOCK_FOR_INSN (last
));
239 /* Create a new basic block consisting of the instructions between HEAD and END
240 inclusive. This function is designed to allow fast BB construction - reuses
241 the note and basic block struct in BB_NOTE, if any and do not grow
242 BASIC_BLOCK chain and should be used directly only by CFG construction code.
243 END can be NULL in to create new empty basic block before HEAD. Both END
244 and HEAD can be NULL to create basic block at the end of INSN chain.
245 AFTER is the basic block we should be put after. */
248 create_basic_block_structure (head
, end
, bb_note
, after
)
249 rtx head
, end
, bb_note
;
255 && ! RTX_INTEGRATED_P (bb_note
)
256 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
259 /* If we found an existing note, thread it back onto the chain. */
263 if (GET_CODE (head
) == CODE_LABEL
)
267 after
= PREV_INSN (head
);
271 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
272 reorder_insns_nobb (bb_note
, bb_note
, after
);
276 /* Otherwise we must create a note and a basic block structure. */
282 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
283 else if (GET_CODE (head
) == CODE_LABEL
&& end
)
285 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
291 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
297 NOTE_BASIC_BLOCK (bb_note
) = bb
;
300 /* Always include the bb note in the block. */
301 if (NEXT_INSN (end
) == bb_note
)
306 bb
->index
= last_basic_block
++;
308 link_block (bb
, after
);
309 BASIC_BLOCK (bb
->index
) = bb
;
310 update_bb_for_insn (bb
);
312 /* Tag the block so that we know it has been used when considering
313 other basic block notes. */
319 /* Create new basic block consisting of instructions in between HEAD and END
320 and place it to the BB chain after block AFTER. END can be NULL in to
321 create new empty basic block before HEAD. Both END and HEAD can be NULL to
322 create basic block at the end of INSN chain. */
325 create_basic_block (head
, end
, after
)
331 /* Place the new block just after the end. */
332 VARRAY_GROW (basic_block_info
, last_basic_block
+1);
336 bb
= create_basic_block_structure (head
, end
, NULL
, after
);
341 /* Delete the insns in a (non-live) block. We physically delete every
342 non-deleted-note insn, and update the flow graph appropriately.
344 Return nonzero if we deleted an exception handler. */
346 /* ??? Preserving all such notes strikes me as wrong. It would be nice
347 to post-process the stream to remove empty blocks, loops, ranges, etc. */
350 flow_delete_block_noexpunge (b
)
353 int deleted_handler
= 0;
356 /* If the head of this block is a CODE_LABEL, then it might be the
357 label for an exception handler which can't be reached.
359 We need to remove the label from the exception_handler_label list
360 and remove the associated NOTE_INSN_EH_REGION_BEG and
361 NOTE_INSN_EH_REGION_END notes. */
363 /* Get rid of all NOTE_INSN_PREDICTIONs and NOTE_INSN_LOOP_CONTs
364 hanging before the block. */
366 for (insn
= PREV_INSN (b
->head
); insn
; insn
= PREV_INSN (insn
))
368 if (GET_CODE (insn
) != NOTE
)
370 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_PREDICTION
371 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_CONT
)
372 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
377 never_reached_warning (insn
, b
->end
);
379 if (GET_CODE (insn
) == CODE_LABEL
)
380 maybe_remove_eh_handler (insn
);
382 /* Include any jump table following the basic block. */
384 if (GET_CODE (end
) == JUMP_INSN
385 && (tmp
= JUMP_LABEL (end
)) != NULL_RTX
386 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
387 && GET_CODE (tmp
) == JUMP_INSN
388 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
389 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
392 /* Include any barrier that may follow the basic block. */
393 tmp
= next_nonnote_insn (end
);
394 if (tmp
&& GET_CODE (tmp
) == BARRIER
)
397 /* Selectively delete the entire chain. */
399 delete_insn_chain (insn
, end
);
401 /* Remove the edges into and out of this block. Note that there may
402 indeed be edges in, if we are removing an unreachable loop. */
403 while (b
->pred
!= NULL
)
404 remove_edge (b
->pred
);
405 while (b
->succ
!= NULL
)
406 remove_edge (b
->succ
);
411 return deleted_handler
;
415 flow_delete_block (b
)
418 int deleted_handler
= flow_delete_block_noexpunge (b
);
420 /* Remove the basic block from the array. */
423 return deleted_handler
;
426 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
429 compute_bb_for_insn ()
438 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
440 BLOCK_FOR_INSN (insn
) = bb
;
447 /* Release the basic_block_for_insn array. */
453 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
454 if (GET_CODE (insn
) != BARRIER
)
455 BLOCK_FOR_INSN (insn
) = NULL
;
458 /* Update insns block within BB. */
461 update_bb_for_insn (bb
)
466 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
468 set_block_for_insn (insn
, bb
);
474 /* Split a block BB after insn INSN creating a new fallthru edge.
475 Return the new edge. Note that to keep other parts of the compiler happy,
476 this function renumbers all the basic blocks so that the new
477 one has a number one greater than the block split. */
480 split_block (bb
, insn
)
488 /* There is no point splitting the block after its end. */
492 /* Create the new basic block. */
493 new_bb
= create_basic_block (NEXT_INSN (insn
), bb
->end
, bb
);
494 new_bb
->count
= bb
->count
;
495 new_bb
->frequency
= bb
->frequency
;
496 new_bb
->loop_depth
= bb
->loop_depth
;
499 /* Redirect the outgoing edges. */
500 new_bb
->succ
= bb
->succ
;
502 for (e
= new_bb
->succ
; e
; e
= e
->succ_next
)
505 new_edge
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
507 if (bb
->global_live_at_start
)
509 new_bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
510 new_bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
511 COPY_REG_SET (new_bb
->global_live_at_end
, bb
->global_live_at_end
);
513 /* We now have to calculate which registers are live at the end
514 of the split basic block and at the start of the new basic
515 block. Start with those registers that are known to be live
516 at the end of the original basic block and get
517 propagate_block to determine which registers are live. */
518 COPY_REG_SET (new_bb
->global_live_at_start
, bb
->global_live_at_end
);
519 propagate_block (new_bb
, new_bb
->global_live_at_start
, NULL
, NULL
, 0);
520 COPY_REG_SET (bb
->global_live_at_end
,
521 new_bb
->global_live_at_start
);
522 #ifdef HAVE_conditional_execution
523 /* In the presence of conditional execution we are not able to update
524 liveness precisely. */
525 if (reload_completed
)
527 bb
->flags
|= BB_DIRTY
;
528 new_bb
->flags
|= BB_DIRTY
;
536 /* Blocks A and B are to be merged into a single block A. The insns
537 are already contiguous, hence `nomove'. */
540 merge_blocks_nomove (a
, b
)
543 rtx b_head
= b
->head
, b_end
= b
->end
, a_end
= a
->end
;
544 rtx del_first
= NULL_RTX
, del_last
= NULL_RTX
;
548 /* If there was a CODE_LABEL beginning B, delete it. */
549 if (GET_CODE (b_head
) == CODE_LABEL
)
551 /* Detect basic blocks with nothing but a label. This can happen
552 in particular at the end of a function. */
556 del_first
= del_last
= b_head
;
557 b_head
= NEXT_INSN (b_head
);
560 /* Delete the basic block note and handle blocks containing just that
562 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
570 b_head
= NEXT_INSN (b_head
);
573 /* If there was a jump out of A, delete it. */
574 if (GET_CODE (a_end
) == JUMP_INSN
)
578 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
579 if (GET_CODE (prev
) != NOTE
580 || NOTE_LINE_NUMBER (prev
) == NOTE_INSN_BASIC_BLOCK
587 /* If this was a conditional jump, we need to also delete
588 the insn that set cc0. */
589 if (only_sets_cc0_p (prev
))
593 prev
= prev_nonnote_insn (prev
);
600 a_end
= PREV_INSN (del_first
);
602 else if (GET_CODE (NEXT_INSN (a_end
)) == BARRIER
)
603 del_first
= NEXT_INSN (a_end
);
605 /* Normally there should only be one successor of A and that is B, but
606 partway though the merge of blocks for conditional_execution we'll
607 be merging a TEST block with THEN and ELSE successors. Free the
608 whole lot of them and hope the caller knows what they're doing. */
610 remove_edge (a
->succ
);
612 /* Adjust the edges out of B for the new owner. */
613 for (e
= b
->succ
; e
; e
= e
->succ_next
)
616 a
->flags
|= b
->flags
;
618 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
619 b
->pred
= b
->succ
= NULL
;
620 a
->global_live_at_end
= b
->global_live_at_end
;
624 /* Delete everything marked above as well as crap that might be
625 hanging out between the two blocks. */
626 delete_insn_chain (del_first
, del_last
);
628 /* Reassociate the insns of B with A. */
633 for (x
= a_end
; x
!= b_end
; x
= NEXT_INSN (x
))
634 set_block_for_insn (x
, a
);
636 set_block_for_insn (b_end
, a
);
644 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
651 if (block
== EXIT_BLOCK_PTR
)
654 if (GET_CODE (block
->head
) != CODE_LABEL
)
656 block
->head
= emit_label_before (gen_label_rtx (), block
->head
);
662 /* Attempt to perform edge redirection by replacing possibly complex jump
663 instruction by unconditional jump or removing jump completely. This can
664 apply only if all edges now point to the same block. The parameters and
665 return values are equivalent to redirect_edge_and_branch. */
668 try_redirect_by_replacing_jump (e
, target
)
672 basic_block src
= e
->src
;
673 rtx insn
= src
->end
, kill_from
;
678 /* Verify that all targets will be TARGET. */
679 for (tmp
= src
->succ
; tmp
; tmp
= tmp
->succ_next
)
680 if (tmp
->dest
!= target
&& tmp
!= e
)
683 if (tmp
|| !onlyjump_p (insn
))
685 if (reload_completed
&& JUMP_LABEL (insn
)
686 && (table
= NEXT_INSN (JUMP_LABEL (insn
))) != NULL_RTX
687 && GET_CODE (table
) == JUMP_INSN
688 && (GET_CODE (PATTERN (table
)) == ADDR_VEC
689 || GET_CODE (PATTERN (table
)) == ADDR_DIFF_VEC
))
692 /* Avoid removing branch with side effects. */
693 set
= single_set (insn
);
694 if (!set
|| side_effects_p (set
))
697 /* In case we zap a conditional jump, we'll need to kill
698 the cc0 setter too. */
701 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
)))
702 kill_from
= PREV_INSN (insn
);
705 /* See if we can create the fallthru edge. */
706 if (can_fallthru (src
, target
))
709 fprintf (rtl_dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
712 /* Selectively unlink whole insn chain. */
713 delete_insn_chain (kill_from
, PREV_INSN (target
->head
));
716 /* If this already is simplejump, redirect it. */
717 else if (simplejump_p (insn
))
719 if (e
->dest
== target
)
722 fprintf (rtl_dump_file
, "Redirecting jump %i from %i to %i.\n",
723 INSN_UID (insn
), e
->dest
->index
, target
->index
);
724 if (!redirect_jump (insn
, block_label (target
), 0))
726 if (target
== EXIT_BLOCK_PTR
)
732 /* Cannot do anything for target exit block. */
733 else if (target
== EXIT_BLOCK_PTR
)
736 /* Or replace possibly complicated jump insn by simple jump insn. */
739 rtx target_label
= block_label (target
);
742 emit_jump_insn_after (gen_jump (target_label
), insn
);
743 JUMP_LABEL (src
->end
) = target_label
;
744 LABEL_NUSES (target_label
)++;
746 fprintf (rtl_dump_file
, "Replacing insn %i by jump %i\n",
747 INSN_UID (insn
), INSN_UID (src
->end
));
750 delete_insn_chain (kill_from
, insn
);
752 /* Recognize a tablejump that we are converting to a
753 simple jump and remove its associated CODE_LABEL
754 and ADDR_VEC or ADDR_DIFF_VEC. */
755 if ((tmp
= JUMP_LABEL (insn
)) != NULL_RTX
756 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
757 && GET_CODE (tmp
) == JUMP_INSN
758 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
759 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
761 delete_insn_chain (JUMP_LABEL (insn
), tmp
);
764 barrier
= next_nonnote_insn (src
->end
);
765 if (!barrier
|| GET_CODE (barrier
) != BARRIER
)
766 emit_barrier_after (src
->end
);
769 /* Keep only one edge out and set proper flags. */
770 while (src
->succ
->succ_next
)
771 remove_edge (src
->succ
);
774 e
->flags
= EDGE_FALLTHRU
;
778 e
->probability
= REG_BR_PROB_BASE
;
779 e
->count
= src
->count
;
781 /* We don't want a block to end on a line-number note since that has
782 the potential of changing the code between -g and not -g. */
783 while (GET_CODE (e
->src
->end
) == NOTE
784 && NOTE_LINE_NUMBER (e
->src
->end
) >= 0)
785 delete_insn (e
->src
->end
);
787 if (e
->dest
!= target
)
788 redirect_edge_succ (e
, target
);
793 /* Return last loop_beg note appearing after INSN, before start of next
794 basic block. Return INSN if there are no such notes.
796 When emitting jump to redirect a fallthru edge, it should always appear
797 after the LOOP_BEG notes, as loop optimizer expect loop to either start by
798 fallthru edge or jump following the LOOP_BEG note jumping to the loop exit
802 last_loop_beg_note (insn
)
807 for (insn
= NEXT_INSN (insn
); insn
&& GET_CODE (insn
) == NOTE
808 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
;
809 insn
= NEXT_INSN (insn
))
810 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
816 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
817 expense of adding new instructions or reordering basic blocks.
819 Function can be also called with edge destination equivalent to the TARGET.
820 Then it should try the simplifications and do nothing if none is possible.
822 Return true if transformation succeeded. We still return false in case E
823 already destinated TARGET and we didn't managed to simplify instruction
827 redirect_edge_and_branch (e
, target
)
832 rtx old_label
= e
->dest
->head
;
833 basic_block src
= e
->src
;
836 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
839 if (try_redirect_by_replacing_jump (e
, target
))
842 /* Do this fast path late, as we want above code to simplify for cases
843 where called on single edge leaving basic block containing nontrivial
845 else if (e
->dest
== target
)
848 /* We can only redirect non-fallthru edges of jump insn. */
849 if (e
->flags
& EDGE_FALLTHRU
)
851 else if (GET_CODE (insn
) != JUMP_INSN
)
854 /* Recognize a tablejump and adjust all matching cases. */
855 if ((tmp
= JUMP_LABEL (insn
)) != NULL_RTX
856 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
857 && GET_CODE (tmp
) == JUMP_INSN
858 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
859 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
863 rtx new_label
= block_label (target
);
865 if (target
== EXIT_BLOCK_PTR
)
867 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
868 vec
= XVEC (PATTERN (tmp
), 0);
870 vec
= XVEC (PATTERN (tmp
), 1);
872 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
873 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
875 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
876 --LABEL_NUSES (old_label
);
877 ++LABEL_NUSES (new_label
);
880 /* Handle casesi dispatch insns */
881 if ((tmp
= single_set (insn
)) != NULL
882 && SET_DEST (tmp
) == pc_rtx
883 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
884 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
885 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
887 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (VOIDmode
,
889 --LABEL_NUSES (old_label
);
890 ++LABEL_NUSES (new_label
);
895 /* ?? We may play the games with moving the named labels from
896 one basic block to the other in case only one computed_jump is
898 if (computed_jump_p (insn
)
899 /* A return instruction can't be redirected. */
900 || returnjump_p (insn
))
903 /* If the insn doesn't go where we think, we're confused. */
904 if (JUMP_LABEL (insn
) != old_label
)
907 /* If the substitution doesn't succeed, die. This can happen
908 if the back end emitted unrecognizable instructions or if
909 target is exit block on some arches. */
910 if (!redirect_jump (insn
, block_label (target
), 0))
912 if (target
== EXIT_BLOCK_PTR
)
919 fprintf (rtl_dump_file
, "Edge %i->%i redirected to %i\n",
920 e
->src
->index
, e
->dest
->index
, target
->index
);
922 if (e
->dest
!= target
)
923 redirect_edge_succ_nodup (e
, target
);
928 /* Like force_nonfallthru below, but additionally performs redirection
929 Used by redirect_edge_and_branch_force. */
932 force_nonfallthru_and_redirect (e
, target
)
936 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
939 int abnormal_edge_flags
= 0;
941 if (e
->flags
& EDGE_ABNORMAL
)
943 /* Irritating special case - fallthru edge to the same block as abnormal
945 We can't redirect abnormal edge, but we still can split the fallthru
946 one and create separate abnormal edge to original destination.
947 This allows bb-reorder to make such edge non-fallthru. */
948 if (e
->dest
!= target
)
950 abnormal_edge_flags
= e
->flags
& ~(EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
);
951 e
->flags
&= EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
;
953 else if (!(e
->flags
& EDGE_FALLTHRU
))
955 else if (e
->src
== ENTRY_BLOCK_PTR
)
957 /* We can't redirect the entry block. Create an empty block at the
958 start of the function which we use to add the new jump. */
960 basic_block bb
= create_basic_block (e
->dest
->head
, NULL
, ENTRY_BLOCK_PTR
);
962 /* Change the existing edge's source to be the new block, and add
963 a new edge from the entry block to the new block. */
965 for (pe1
= &ENTRY_BLOCK_PTR
->succ
; *pe1
; pe1
= &(*pe1
)->succ_next
)
973 make_single_succ_edge (ENTRY_BLOCK_PTR
, bb
, EDGE_FALLTHRU
);
976 if (e
->src
->succ
->succ_next
|| abnormal_edge_flags
)
978 /* Create the new structures. */
980 /* Position the new block correctly relative to loop notes. */
981 note
= last_loop_beg_note (e
->src
->end
);
982 note
= NEXT_INSN (note
);
984 /* ... and ADDR_VECs. */
986 && GET_CODE (note
) == CODE_LABEL
988 && GET_CODE (NEXT_INSN (note
)) == JUMP_INSN
989 && (GET_CODE (PATTERN (NEXT_INSN (note
))) == ADDR_DIFF_VEC
990 || GET_CODE (PATTERN (NEXT_INSN (note
))) == ADDR_VEC
))
991 note
= NEXT_INSN (NEXT_INSN (note
));
993 jump_block
= create_basic_block (note
, NULL
, e
->src
);
994 jump_block
->count
= e
->count
;
995 jump_block
->frequency
= EDGE_FREQUENCY (e
);
996 jump_block
->loop_depth
= target
->loop_depth
;
998 if (target
->global_live_at_start
)
1000 jump_block
->global_live_at_start
1001 = OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1002 jump_block
->global_live_at_end
1003 = OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1004 COPY_REG_SET (jump_block
->global_live_at_start
,
1005 target
->global_live_at_start
);
1006 COPY_REG_SET (jump_block
->global_live_at_end
,
1007 target
->global_live_at_start
);
1011 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1012 new_edge
->probability
= e
->probability
;
1013 new_edge
->count
= e
->count
;
1015 /* Redirect old edge. */
1016 redirect_edge_pred (e
, jump_block
);
1017 e
->probability
= REG_BR_PROB_BASE
;
1019 new_bb
= jump_block
;
1022 jump_block
= e
->src
;
1024 e
->flags
&= ~EDGE_FALLTHRU
;
1025 if (target
== EXIT_BLOCK_PTR
)
1028 emit_jump_insn_after (gen_return (), jump_block
->end
);
1034 rtx label
= block_label (target
);
1035 emit_jump_insn_after (gen_jump (label
), jump_block
->end
);
1036 JUMP_LABEL (jump_block
->end
) = label
;
1037 LABEL_NUSES (label
)++;
1040 emit_barrier_after (jump_block
->end
);
1041 redirect_edge_succ_nodup (e
, target
);
1043 if (abnormal_edge_flags
)
1044 make_edge (src
, target
, abnormal_edge_flags
);
1049 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1050 (and possibly create new basic block) to make edge non-fallthru.
1051 Return newly created BB or NULL if none. */
1054 force_nonfallthru (e
)
1057 return force_nonfallthru_and_redirect (e
, e
->dest
);
1060 /* Redirect edge even at the expense of creating new jump insn or
1061 basic block. Return new basic block if created, NULL otherwise.
1062 Abort if conversion is impossible. */
1065 redirect_edge_and_branch_force (e
, target
)
1069 if (redirect_edge_and_branch (e
, target
)
1070 || e
->dest
== target
)
1073 /* In case the edge redirection failed, try to force it to be non-fallthru
1074 and redirect newly created simplejump. */
1075 return force_nonfallthru_and_redirect (e
, target
);
1078 /* The given edge should potentially be a fallthru edge. If that is in
1079 fact true, delete the jump and barriers that are in the way. */
1082 tidy_fallthru_edge (e
, b
, c
)
1088 /* ??? In a late-running flow pass, other folks may have deleted basic
1089 blocks by nopping out blocks, leaving multiple BARRIERs between here
1090 and the target label. They ought to be chastized and fixed.
1092 We can also wind up with a sequence of undeletable labels between
1093 one block and the next.
1095 So search through a sequence of barriers, labels, and notes for
1096 the head of block C and assert that we really do fall through. */
1098 for (q
= NEXT_INSN (b
->end
); q
!= c
->head
; q
= NEXT_INSN (q
))
1102 /* Remove what will soon cease being the jump insn from the source block.
1103 If block B consisted only of this single jump, turn it into a deleted
1106 if (GET_CODE (q
) == JUMP_INSN
1108 && (any_uncondjump_p (q
)
1109 || (b
->succ
== e
&& e
->succ_next
== NULL
)))
1112 /* If this was a conditional jump, we need to also delete
1113 the insn that set cc0. */
1114 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1120 /* We don't want a block to end on a line-number note since that has
1121 the potential of changing the code between -g and not -g. */
1122 while (GET_CODE (q
) == NOTE
&& NOTE_LINE_NUMBER (q
) >= 0)
1126 /* Selectively unlink the sequence. */
1127 if (q
!= PREV_INSN (c
->head
))
1128 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (c
->head
));
1130 e
->flags
|= EDGE_FALLTHRU
;
1133 /* Fix up edges that now fall through, or rather should now fall through
1134 but previously required a jump around now deleted blocks. Simplify
1135 the search by only examining blocks numerically adjacent, since this
1136 is how find_basic_blocks created them. */
1139 tidy_fallthru_edges ()
1143 if (ENTRY_BLOCK_PTR
->next_bb
== EXIT_BLOCK_PTR
)
1146 FOR_BB_BETWEEN (b
, ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
->prev_bb
, next_bb
)
1152 /* We care about simple conditional or unconditional jumps with
1155 If we had a conditional branch to the next instruction when
1156 find_basic_blocks was called, then there will only be one
1157 out edge for the block which ended with the conditional
1158 branch (since we do not create duplicate edges).
1160 Furthermore, the edge will be marked as a fallthru because we
1161 merge the flags for the duplicate edges. So we do not want to
1162 check that the edge is not a FALLTHRU edge. */
1164 if ((s
= b
->succ
) != NULL
1165 && ! (s
->flags
& EDGE_COMPLEX
)
1166 && s
->succ_next
== NULL
1168 /* If the jump insn has side effects, we can't tidy the edge. */
1169 && (GET_CODE (b
->end
) != JUMP_INSN
1170 || onlyjump_p (b
->end
)))
1171 tidy_fallthru_edge (s
, b
, c
);
1175 /* Helper function for split_edge. Return true in case edge BB2 to BB1
1176 is back edge of syntactic loop. */
1179 back_edge_of_syntactic_loop_p (bb1
, bb2
)
1180 basic_block bb1
, bb2
;
1189 /* ??? Could we guarantee that bb indices are monotone, so that we could
1190 just compare them? */
1191 for (bb
= bb1
; bb
&& bb
!= bb2
; bb
= bb
->next_bb
)
1197 for (insn
= bb1
->end
; insn
!= bb2
->head
&& count
>= 0;
1198 insn
= NEXT_INSN (insn
))
1199 if (GET_CODE (insn
) == NOTE
)
1201 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
1203 else if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
)
1210 /* Split a (typically critical) edge. Return the new block.
1211 Abort on abnormal edges.
1213 ??? The code generally expects to be called on critical edges.
1214 The case of a block ending in an unconditional jump to a
1215 block with multiple predecessors is not handled optimally. */
1218 split_edge (edge_in
)
1225 /* Abnormal edges cannot be split. */
1226 if ((edge_in
->flags
& EDGE_ABNORMAL
) != 0)
1229 /* We are going to place the new block in front of edge destination.
1230 Avoid existence of fallthru predecessors. */
1231 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1235 for (e
= edge_in
->dest
->pred
; e
; e
= e
->pred_next
)
1236 if (e
->flags
& EDGE_FALLTHRU
)
1240 force_nonfallthru (e
);
1243 /* Create the basic block note.
1245 Where we place the note can have a noticeable impact on the generated
1246 code. Consider this cfg:
1256 If we need to insert an insn on the edge from block 0 to block 1,
1257 we want to ensure the instructions we insert are outside of any
1258 loop notes that physically sit between block 0 and block 1. Otherwise
1259 we confuse the loop optimizer into thinking the loop is a phony. */
1261 if (edge_in
->dest
!= EXIT_BLOCK_PTR
1262 && PREV_INSN (edge_in
->dest
->head
)
1263 && GET_CODE (PREV_INSN (edge_in
->dest
->head
)) == NOTE
1264 && (NOTE_LINE_NUMBER (PREV_INSN (edge_in
->dest
->head
))
1265 == NOTE_INSN_LOOP_BEG
)
1266 && !back_edge_of_syntactic_loop_p (edge_in
->dest
, edge_in
->src
))
1267 before
= PREV_INSN (edge_in
->dest
->head
);
1268 else if (edge_in
->dest
!= EXIT_BLOCK_PTR
)
1269 before
= edge_in
->dest
->head
;
1273 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1274 bb
->count
= edge_in
->count
;
1275 bb
->frequency
= EDGE_FREQUENCY (edge_in
);
1277 /* ??? This info is likely going to be out of date very soon. */
1278 if (edge_in
->dest
->global_live_at_start
)
1280 bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1281 bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1282 COPY_REG_SET (bb
->global_live_at_start
,
1283 edge_in
->dest
->global_live_at_start
);
1284 COPY_REG_SET (bb
->global_live_at_end
,
1285 edge_in
->dest
->global_live_at_start
);
1288 edge_out
= make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1290 /* For non-fallthry edges, we must adjust the predecessor's
1291 jump instruction to target our new block. */
1292 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1294 if (!redirect_edge_and_branch (edge_in
, bb
))
1298 redirect_edge_succ (edge_in
, bb
);
1303 /* Queue instructions for insertion on an edge between two basic blocks.
1304 The new instructions and basic blocks (if any) will not appear in the
1305 CFG until commit_edge_insertions is called. */
1308 insert_insn_on_edge (pattern
, e
)
1312 /* We cannot insert instructions on an abnormal critical edge.
1313 It will be easier to find the culprit if we die now. */
1314 if ((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
1317 if (e
->insns
== NULL_RTX
)
1320 push_to_sequence (e
->insns
);
1322 emit_insn (pattern
);
1324 e
->insns
= get_insns ();
1328 /* Update the CFG for the instructions queued on edge E. */
1331 commit_one_edge_insertion (e
, watch_calls
)
1335 rtx before
= NULL_RTX
, after
= NULL_RTX
, insns
, tmp
, last
;
1336 basic_block bb
= NULL
;
1338 /* Pull the insns off the edge now since the edge might go away. */
1340 e
->insns
= NULL_RTX
;
1342 /* Special case -- avoid inserting code between call and storing
1343 its return value. */
1344 if (watch_calls
&& (e
->flags
& EDGE_FALLTHRU
) && !e
->dest
->pred
->pred_next
1345 && e
->src
!= ENTRY_BLOCK_PTR
1346 && GET_CODE (e
->src
->end
) == CALL_INSN
)
1348 rtx next
= next_nonnote_insn (e
->src
->end
);
1350 after
= e
->dest
->head
;
1351 /* The first insn after the call may be a stack pop, skip it. */
1353 && keep_with_call_p (next
))
1356 next
= next_nonnote_insn (next
);
1360 if (!before
&& !after
)
1362 /* Figure out where to put these things. If the destination has
1363 one predecessor, insert there. Except for the exit block. */
1364 if (e
->dest
->pred
->pred_next
== NULL
&& e
->dest
!= EXIT_BLOCK_PTR
)
1368 /* Get the location correct wrt a code label, and "nice" wrt
1369 a basic block note, and before everything else. */
1371 if (GET_CODE (tmp
) == CODE_LABEL
)
1372 tmp
= NEXT_INSN (tmp
);
1373 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1374 tmp
= NEXT_INSN (tmp
);
1375 if (tmp
== bb
->head
)
1378 after
= PREV_INSN (tmp
);
1380 after
= get_last_insn ();
1383 /* If the source has one successor and the edge is not abnormal,
1384 insert there. Except for the entry block. */
1385 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1386 && e
->src
->succ
->succ_next
== NULL
1387 && e
->src
!= ENTRY_BLOCK_PTR
)
1391 /* It is possible to have a non-simple jump here. Consider a target
1392 where some forms of unconditional jumps clobber a register. This
1393 happens on the fr30 for example.
1395 We know this block has a single successor, so we can just emit
1396 the queued insns before the jump. */
1397 if (GET_CODE (bb
->end
) == JUMP_INSN
)
1398 for (before
= bb
->end
;
1399 GET_CODE (PREV_INSN (before
)) == NOTE
1400 && NOTE_LINE_NUMBER (PREV_INSN (before
)) ==
1401 NOTE_INSN_LOOP_BEG
; before
= PREV_INSN (before
))
1405 /* We'd better be fallthru, or we've lost track of what's what. */
1406 if ((e
->flags
& EDGE_FALLTHRU
) == 0)
1412 /* Otherwise we must split the edge. */
1415 bb
= split_edge (e
);
1420 /* Now that we've found the spot, do the insertion. */
1424 emit_insn_before (insns
, before
);
1425 last
= prev_nonnote_insn (before
);
1428 last
= emit_insn_after (insns
, after
);
1430 if (returnjump_p (last
))
1432 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1433 This is not currently a problem because this only happens
1434 for the (single) epilogue, which already has a fallthru edge
1438 if (e
->dest
!= EXIT_BLOCK_PTR
1439 || e
->succ_next
!= NULL
|| (e
->flags
& EDGE_FALLTHRU
) == 0)
1442 e
->flags
&= ~EDGE_FALLTHRU
;
1443 emit_barrier_after (last
);
1446 delete_insn (before
);
1448 else if (GET_CODE (last
) == JUMP_INSN
)
1451 find_sub_basic_blocks (bb
);
1454 /* Update the CFG for all queued instructions. */
1457 commit_edge_insertions ()
1461 #ifdef ENABLE_CHECKING
1462 verify_flow_info ();
1465 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
1469 for (e
= bb
->succ
; e
; e
= next
)
1471 next
= e
->succ_next
;
1473 commit_one_edge_insertion (e
, false);
1478 /* Update the CFG for all queued instructions, taking special care of inserting
1479 code on edges between call and storing its return value. */
1482 commit_edge_insertions_watch_calls ()
1486 #ifdef ENABLE_CHECKING
1487 verify_flow_info ();
1490 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
1494 for (e
= bb
->succ
; e
; e
= next
)
1496 next
= e
->succ_next
;
1498 commit_one_edge_insertion (e
, true);
1503 /* Print out one basic block with live information at start and end. */
1514 fprintf (outf
, ";; Basic block %d, loop depth %d, count ",
1515 bb
->index
, bb
->loop_depth
);
1516 fprintf (outf
, HOST_WIDEST_INT_PRINT_DEC
, (HOST_WIDEST_INT
) bb
->count
);
1519 fputs (";; Predecessors: ", outf
);
1520 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1521 dump_edge_info (outf
, e
, 0);
1524 fputs (";; Registers live at start:", outf
);
1525 dump_regset (bb
->global_live_at_start
, outf
);
1528 for (insn
= bb
->head
, last
= NEXT_INSN (bb
->end
); insn
!= last
;
1529 insn
= NEXT_INSN (insn
))
1530 print_rtl_single (outf
, insn
);
1532 fputs (";; Registers live at end:", outf
);
1533 dump_regset (bb
->global_live_at_end
, outf
);
1536 fputs (";; Successors: ", outf
);
1537 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1538 dump_edge_info (outf
, e
, 1);
1546 dump_bb (bb
, stderr
);
1553 dump_bb (BASIC_BLOCK (n
), stderr
);
1556 /* Like print_rtl, but also print out live information for the start of each
1560 print_rtl_with_bb (outf
, rtx_first
)
1567 fprintf (outf
, "(nil)\n");
1570 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
1571 int max_uid
= get_max_uid ();
1573 = (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1575 = (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1576 enum bb_state
*in_bb_p
1577 = (enum bb_state
*) xcalloc (max_uid
, sizeof (enum bb_state
));
1581 FOR_EACH_BB_REVERSE (bb
)
1585 start
[INSN_UID (bb
->head
)] = bb
;
1586 end
[INSN_UID (bb
->end
)] = bb
;
1587 for (x
= bb
->head
; x
!= NULL_RTX
; x
= NEXT_INSN (x
))
1589 enum bb_state state
= IN_MULTIPLE_BB
;
1591 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
1593 in_bb_p
[INSN_UID (x
)] = state
;
1600 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
1604 if ((bb
= start
[INSN_UID (tmp_rtx
)]) != NULL
)
1606 fprintf (outf
, ";; Start of basic block %d, registers live:",
1608 dump_regset (bb
->global_live_at_start
, outf
);
1612 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
1613 && GET_CODE (tmp_rtx
) != NOTE
1614 && GET_CODE (tmp_rtx
) != BARRIER
)
1615 fprintf (outf
, ";; Insn is not within a basic block\n");
1616 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
1617 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
1619 did_output
= print_rtl_single (outf
, tmp_rtx
);
1621 if ((bb
= end
[INSN_UID (tmp_rtx
)]) != NULL
)
1623 fprintf (outf
, ";; End of basic block %d, registers live:\n",
1625 dump_regset (bb
->global_live_at_end
, outf
);
1638 if (current_function_epilogue_delay_list
!= 0)
1640 fprintf (outf
, "\n;; Insns in epilogue delay list:\n\n");
1641 for (tmp_rtx
= current_function_epilogue_delay_list
; tmp_rtx
!= 0;
1642 tmp_rtx
= XEXP (tmp_rtx
, 1))
1643 print_rtl_single (outf
, XEXP (tmp_rtx
, 0));
1648 update_br_prob_note (bb
)
1652 if (GET_CODE (bb
->end
) != JUMP_INSN
)
1654 note
= find_reg_note (bb
->end
, REG_BR_PROB
, NULL_RTX
);
1655 if (!note
|| INTVAL (XEXP (note
, 0)) == BRANCH_EDGE (bb
)->probability
)
1657 XEXP (note
, 0) = GEN_INT (BRANCH_EDGE (bb
)->probability
);
1660 /* Verify the CFG consistency. This function check some CFG invariants and
1661 aborts when something is wrong. Hope that this function will help to
1662 convert many optimization passes to preserve CFG consistent.
1664 Currently it does following checks:
1666 - test head/end pointers
1667 - overlapping of basic blocks
1668 - edge list correctness
1669 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1670 - tails of basic blocks (ensure that boundary is necessary)
1671 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1672 and NOTE_INSN_BASIC_BLOCK
1673 - check that all insns are in the basic blocks
1674 (except the switch handling code, barriers and notes)
1675 - check that all returns are followed by barriers
1677 In future it can be extended check a lot of other stuff as well
1678 (reachability of basic blocks, life information, etc. etc.). */
1683 const int max_uid
= get_max_uid ();
1684 const rtx rtx_first
= get_insns ();
1685 rtx last_head
= get_last_insn ();
1686 basic_block
*bb_info
, *last_visited
;
1687 size_t *edge_checksum
;
1689 int num_bb_notes
, err
= 0;
1690 basic_block bb
, last_bb_seen
;
1692 bb_info
= (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1693 last_visited
= (basic_block
*) xcalloc (last_basic_block
+ 2,
1694 sizeof (basic_block
));
1695 edge_checksum
= (size_t *) xcalloc (last_basic_block
+ 2, sizeof (size_t));
1697 /* Check bb chain & numbers. */
1698 last_bb_seen
= ENTRY_BLOCK_PTR
;
1699 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
, NULL
, next_bb
)
1701 if (bb
!= EXIT_BLOCK_PTR
1702 && bb
!= BASIC_BLOCK (bb
->index
))
1704 error ("bb %d on wrong place", bb
->index
);
1708 if (bb
->prev_bb
!= last_bb_seen
)
1710 error ("prev_bb of %d should be %d, not %d",
1711 bb
->index
, last_bb_seen
->index
, bb
->prev_bb
->index
);
1718 FOR_EACH_BB_REVERSE (bb
)
1720 rtx head
= bb
->head
;
1723 /* Verify the end of the basic block is in the INSN chain. */
1724 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1730 error ("end insn %d for block %d not found in the insn stream",
1731 INSN_UID (end
), bb
->index
);
1735 /* Work backwards from the end to the head of the basic block
1736 to verify the head is in the RTL chain. */
1737 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1739 /* While walking over the insn chain, verify insns appear
1740 in only one basic block and initialize the BB_INFO array
1741 used by other passes. */
1742 if (bb_info
[INSN_UID (x
)] != NULL
)
1744 error ("insn %d is in multiple basic blocks (%d and %d)",
1745 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
1749 bb_info
[INSN_UID (x
)] = bb
;
1756 error ("head insn %d for block %d not found in the insn stream",
1757 INSN_UID (head
), bb
->index
);
1764 /* Now check the basic blocks (boundaries etc.) */
1765 FOR_EACH_BB_REVERSE (bb
)
1767 int n_fallthru
= 0, n_eh
= 0, n_call
= 0, n_abnormal
= 0, n_branch
= 0;
1771 if (INSN_P (bb
->end
)
1772 && (note
= find_reg_note (bb
->end
, REG_BR_PROB
, NULL_RTX
))
1773 && bb
->succ
&& bb
->succ
->succ_next
1774 && any_condjump_p (bb
->end
))
1776 if (INTVAL (XEXP (note
, 0)) != BRANCH_EDGE (bb
)->probability
)
1778 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
1779 INTVAL (XEXP (note
, 0)), BRANCH_EDGE (bb
)->probability
);
1785 error ("verify_flow_info: Wrong count of block %i %i",
1786 bb
->index
, (int)bb
->count
);
1789 if (bb
->frequency
< 0)
1791 error ("verify_flow_info: Wrong frequency of block %i %i",
1792 bb
->index
, bb
->frequency
);
1795 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1797 if (last_visited
[e
->dest
->index
+ 2] == bb
)
1799 error ("verify_flow_info: Duplicate edge %i->%i",
1800 e
->src
->index
, e
->dest
->index
);
1803 if (e
->probability
< 0 || e
->probability
> REG_BR_PROB_BASE
)
1805 error ("verify_flow_info: Wrong probability of edge %i->%i %i",
1806 e
->src
->index
, e
->dest
->index
, e
->probability
);
1811 error ("verify_flow_info: Wrong count of edge %i->%i %i",
1812 e
->src
->index
, e
->dest
->index
, (int)e
->count
);
1816 last_visited
[e
->dest
->index
+ 2] = bb
;
1818 if (e
->flags
& EDGE_FALLTHRU
)
1821 if ((e
->flags
& ~EDGE_DFS_BACK
) == 0)
1824 if (e
->flags
& EDGE_ABNORMAL_CALL
)
1827 if (e
->flags
& EDGE_EH
)
1829 else if (e
->flags
& EDGE_ABNORMAL
)
1832 if ((e
->flags
& EDGE_FALLTHRU
)
1833 && e
->src
!= ENTRY_BLOCK_PTR
1834 && e
->dest
!= EXIT_BLOCK_PTR
)
1838 if (e
->src
->next_bb
!= e
->dest
)
1841 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
1842 e
->src
->index
, e
->dest
->index
);
1846 for (insn
= NEXT_INSN (e
->src
->end
); insn
!= e
->dest
->head
;
1847 insn
= NEXT_INSN (insn
))
1848 if (GET_CODE (insn
) == BARRIER
1849 #ifndef CASE_DROPS_THROUGH
1852 || (INSN_P (insn
) && ! JUMP_TABLE_DATA_P (insn
))
1856 error ("verify_flow_info: Incorrect fallthru %i->%i",
1857 e
->src
->index
, e
->dest
->index
);
1858 fatal_insn ("wrong insn in the fallthru edge", insn
);
1865 error ("verify_flow_info: Basic block %d succ edge is corrupted",
1867 fprintf (stderr
, "Predecessor: ");
1868 dump_edge_info (stderr
, e
, 0);
1869 fprintf (stderr
, "\nSuccessor: ");
1870 dump_edge_info (stderr
, e
, 1);
1871 fprintf (stderr
, "\n");
1875 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
1878 if (n_eh
&& GET_CODE (PATTERN (bb
->end
)) != RESX
1879 && !find_reg_note (bb
->end
, REG_EH_REGION
, NULL_RTX
))
1881 error ("Missing REG_EH_REGION note in the end of bb %i", bb
->index
);
1885 && (GET_CODE (bb
->end
) != JUMP_INSN
1886 || (n_branch
> 1 && (any_uncondjump_p (bb
->end
)
1887 || any_condjump_p (bb
->end
)))))
1889 error ("Too many outgoing branch edges from bb %i", bb
->index
);
1892 if (n_fallthru
&& any_uncondjump_p (bb
->end
))
1894 error ("Fallthru edge after unconditional jump %i", bb
->index
);
1897 if (n_branch
!= 1 && any_uncondjump_p (bb
->end
))
1899 error ("Wrong amount of branch edges after unconditional jump %i", bb
->index
);
1902 if (n_branch
!= 1 && any_condjump_p (bb
->end
)
1903 && JUMP_LABEL (bb
->end
) != bb
->next_bb
->head
)
1905 error ("Wrong amount of branch edges after conditional jump %i", bb
->index
);
1908 if (n_call
&& GET_CODE (bb
->end
) != CALL_INSN
)
1910 error ("Call edges for non-call insn in bb %i", bb
->index
);
1914 && (GET_CODE (bb
->end
) != CALL_INSN
&& n_call
!= n_abnormal
)
1915 && (GET_CODE (bb
->end
) != JUMP_INSN
1916 || any_condjump_p (bb
->end
)
1917 || any_uncondjump_p (bb
->end
)))
1919 error ("Abnormal edges for no purpose in bb %i", bb
->index
);
1927 /* Ensure existence of barrier in BB with no fallthru edges. */
1928 for (insn
= bb
->end
; !insn
|| GET_CODE (insn
) != BARRIER
;
1929 insn
= NEXT_INSN (insn
))
1931 || (GET_CODE (insn
) == NOTE
1932 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BASIC_BLOCK
))
1934 error ("missing barrier after block %i", bb
->index
);
1940 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1944 error ("basic block %d pred edge is corrupted", bb
->index
);
1945 fputs ("Predecessor: ", stderr
);
1946 dump_edge_info (stderr
, e
, 0);
1947 fputs ("\nSuccessor: ", stderr
);
1948 dump_edge_info (stderr
, e
, 1);
1949 fputc ('\n', stderr
);
1952 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
1955 for (x
= bb
->head
; x
!= NEXT_INSN (bb
->end
); x
= NEXT_INSN (x
))
1956 if (BLOCK_FOR_INSN (x
) != bb
)
1959 if (! BLOCK_FOR_INSN (x
))
1961 ("insn %d inside basic block %d but block_for_insn is NULL",
1962 INSN_UID (x
), bb
->index
);
1965 ("insn %d inside basic block %d but block_for_insn is %i",
1966 INSN_UID (x
), bb
->index
, BLOCK_FOR_INSN (x
)->index
);
1971 /* OK pointers are correct. Now check the header of basic
1972 block. It ought to contain optional CODE_LABEL followed
1973 by NOTE_BASIC_BLOCK. */
1975 if (GET_CODE (x
) == CODE_LABEL
)
1979 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1987 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
1989 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1995 /* Do checks for empty blocks her. e */
1998 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2000 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2002 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2003 INSN_UID (x
), bb
->index
);
2010 if (GET_CODE (x
) == JUMP_INSN
2011 || GET_CODE (x
) == CODE_LABEL
2012 || GET_CODE (x
) == BARRIER
)
2014 error ("in basic block %d:", bb
->index
);
2015 fatal_insn ("flow control insn inside a basic block", x
);
2020 /* Complete edge checksumming for ENTRY and EXIT. */
2024 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
2025 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
2027 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
2028 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
2031 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2032 if (edge_checksum
[bb
->index
+ 2])
2034 error ("basic block %i edge lists are corrupted", bb
->index
);
2039 last_bb_seen
= ENTRY_BLOCK_PTR
;
2041 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2043 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2045 bb
= NOTE_BASIC_BLOCK (x
);
2048 if (bb
!= last_bb_seen
->next_bb
)
2049 internal_error ("basic blocks not numbered consecutively");
2054 if (!bb_info
[INSN_UID (x
)])
2056 switch (GET_CODE (x
))
2063 /* An addr_vec is placed outside any block block. */
2065 && GET_CODE (NEXT_INSN (x
)) == JUMP_INSN
2066 && (GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_DIFF_VEC
2067 || GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_VEC
))
2070 /* But in any case, non-deletable labels can appear anywhere. */
2074 fatal_insn ("insn outside basic block", x
);
2079 && GET_CODE (x
) == JUMP_INSN
2080 && returnjump_p (x
) && ! condjump_p (x
)
2081 && ! (NEXT_INSN (x
) && GET_CODE (NEXT_INSN (x
)) == BARRIER
))
2082 fatal_insn ("return not followed by barrier", x
);
2085 if (num_bb_notes
!= n_basic_blocks
)
2087 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2088 num_bb_notes
, n_basic_blocks
);
2091 internal_error ("verify_flow_info failed");
2095 free (last_visited
);
2096 free (edge_checksum
);
2099 /* Assume that the preceding pass has possibly eliminated jump instructions
2100 or converted the unconditional jumps. Eliminate the edges from CFG.
2101 Return true if any edges are eliminated. */
2104 purge_dead_edges (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
;
2235 /* If we don't see a jump insn, we don't know exactly why the block would
2236 have been broken at this point. Look for a simple, non-fallthru edge,
2237 as these are only created by conditional branches. If we find such an
2238 edge we know that there used to be a jump here and can then safely
2239 remove all non-fallthru edges. */
2240 for (e
= bb
->succ
; e
&& (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
));
2247 for (e
= bb
->succ
; e
; e
= next
)
2249 next
= e
->succ_next
;
2250 if (!(e
->flags
& EDGE_FALLTHRU
))
2252 bb
->flags
|= BB_DIRTY
;
2258 if (!bb
->succ
|| bb
->succ
->succ_next
)
2261 bb
->succ
->probability
= REG_BR_PROB_BASE
;
2262 bb
->succ
->count
= bb
->count
;
2265 fprintf (rtl_dump_file
, "Purged non-fallthru edges from bb %i\n",
2270 /* Search all basic blocks for potentially dead edges and purge them. Return
2271 true if some edge has been eliminated. */
2274 purge_all_dead_edges (update_life_p
)
2283 blocks
= sbitmap_alloc (last_basic_block
);
2284 sbitmap_zero (blocks
);
2289 bool purged_here
= purge_dead_edges (bb
);
2291 purged
|= purged_here
;
2292 if (purged_here
&& update_life_p
)
2293 SET_BIT (blocks
, bb
->index
);
2296 if (update_life_p
&& purged
)
2297 update_life_info (blocks
, UPDATE_LIFE_GLOBAL
,
2298 PROP_DEATH_NOTES
| PROP_SCAN_DEAD_CODE
2299 | PROP_KILL_DEAD_CODE
);
2302 sbitmap_free (blocks
);