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 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"
60 /* Stubs in case we don't have a return insn. */
63 #define gen_return() NULL_RTX
66 /* The basic block structure for every insn, indexed by uid. */
67 varray_type basic_block_for_insn
;
69 /* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */
70 /* ??? Should probably be using LABEL_NUSES instead. It would take a
71 bit of surgery to be able to use or co-opt the routines in jump. */
73 rtx tail_recursion_label_list
;
75 static int can_delete_note_p
PARAMS ((rtx
));
76 static int can_delete_label_p
PARAMS ((rtx
));
77 static void commit_one_edge_insertion
PARAMS ((edge
));
78 static bool try_redirect_by_replacing_jump
PARAMS ((edge
, basic_block
));
79 static rtx last_loop_beg_note
PARAMS ((rtx
));
80 static bool back_edge_of_syntactic_loop_p
PARAMS ((basic_block
, basic_block
));
81 static basic_block force_nonfallthru_and_redirect
PARAMS ((edge
, basic_block
));
83 /* Return true if NOTE is not one of the ones that must be kept paired,
84 so that we may simply delete it. */
87 can_delete_note_p (note
)
90 return (NOTE_LINE_NUMBER (note
) == NOTE_INSN_DELETED
91 || NOTE_LINE_NUMBER (note
) == NOTE_INSN_BASIC_BLOCK
);
94 /* True if a given label can be deleted. */
97 can_delete_label_p (label
)
100 return (!LABEL_PRESERVE_P (label
)
101 /* User declared labels must be preserved. */
102 && LABEL_NAME (label
) == 0
103 && !in_expr_list_p (forced_labels
, label
)
104 && !in_expr_list_p (label_value_list
, label
)
105 && !in_expr_list_p (exception_handler_labels
, label
));
108 /* Delete INSN by patching it out. Return the next insn. */
114 rtx next
= NEXT_INSN (insn
);
116 bool really_delete
= true;
118 if (GET_CODE (insn
) == CODE_LABEL
)
120 /* Some labels can't be directly removed from the INSN chain, as they
121 might be references via variables, constant pool etc.
122 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
123 if (! can_delete_label_p (insn
))
125 const char *name
= LABEL_NAME (insn
);
127 really_delete
= false;
128 PUT_CODE (insn
, NOTE
);
129 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED_LABEL
;
130 NOTE_SOURCE_FILE (insn
) = name
;
133 remove_node_from_expr_list (insn
, &nonlocal_goto_handler_labels
);
139 INSN_DELETED_P (insn
) = 1;
142 /* If deleting a jump, decrement the use count of the label. Deleting
143 the label itself should happen in the normal course of block merging. */
144 if (GET_CODE (insn
) == JUMP_INSN
146 && GET_CODE (JUMP_LABEL (insn
)) == CODE_LABEL
)
147 LABEL_NUSES (JUMP_LABEL (insn
))--;
149 /* Also if deleting an insn that references a label. */
150 else if ((note
= find_reg_note (insn
, REG_LABEL
, NULL_RTX
)) != NULL_RTX
151 && GET_CODE (XEXP (note
, 0)) == CODE_LABEL
)
152 LABEL_NUSES (XEXP (note
, 0))--;
154 if (GET_CODE (insn
) == JUMP_INSN
155 && (GET_CODE (PATTERN (insn
)) == ADDR_VEC
156 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
))
158 rtx pat
= PATTERN (insn
);
159 int diff_vec_p
= GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
;
160 int len
= XVECLEN (pat
, diff_vec_p
);
163 for (i
= 0; i
< len
; i
++)
164 LABEL_NUSES (XEXP (XVECEXP (pat
, diff_vec_p
, i
), 0))--;
170 /* Unlink a chain of insns between START and FINISH, leaving notes
171 that must be paired. */
174 delete_insn_chain (start
, finish
)
179 /* Unchain the insns one by one. It would be quicker to delete all of these
180 with a single unchaining, rather than one at a time, but we need to keep
184 next
= NEXT_INSN (start
);
185 if (GET_CODE (start
) == NOTE
&& !can_delete_note_p (start
))
188 next
= delete_insn (start
);
196 /* Create a new basic block consisting of the instructions between HEAD and END
197 inclusive. This function is designed to allow fast BB construction - reuses
198 the note and basic block struct in BB_NOTE, if any and do not grow
199 BASIC_BLOCK chain and should be used directly only by CFG construction code.
200 END can be NULL in to create new empty basic block before HEAD. Both END
201 and HEAD can be NULL to create basic block at the end of INSN chain. */
204 create_basic_block_structure (index
, head
, end
, bb_note
)
206 rtx head
, end
, bb_note
;
211 && ! RTX_INTEGRATED_P (bb_note
)
212 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
215 /* If we found an existing note, thread it back onto the chain. */
219 if (GET_CODE (head
) == CODE_LABEL
)
223 after
= PREV_INSN (head
);
227 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
228 reorder_insns (bb_note
, bb_note
, after
);
232 /* Otherwise we must create a note and a basic block structure. */
238 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
239 else if (GET_CODE (head
) == CODE_LABEL
&& end
)
241 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
247 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
253 NOTE_BASIC_BLOCK (bb_note
) = bb
;
256 /* Always include the bb note in the block. */
257 if (NEXT_INSN (end
) == bb_note
)
263 BASIC_BLOCK (index
) = bb
;
264 if (basic_block_for_insn
)
265 update_bb_for_insn (bb
);
267 /* Tag the block so that we know it has been used when considering
268 other basic block notes. */
274 /* Create new basic block consisting of instructions in between HEAD and END
275 and place it to the BB chain at position INDEX. END can be NULL in to
276 create new empty basic block before HEAD. Both END and HEAD can be NULL to
277 create basic block at the end of INSN chain. */
280 create_basic_block (index
, head
, end
)
287 /* Place the new block just after the block being split. */
288 VARRAY_GROW (basic_block_info
, ++n_basic_blocks
);
290 /* Some parts of the compiler expect blocks to be number in
291 sequential order so insert the new block immediately after the
292 block being split.. */
293 for (i
= n_basic_blocks
- 1; i
> index
; --i
)
295 basic_block tmp
= BASIC_BLOCK (i
- 1);
297 BASIC_BLOCK (i
) = tmp
;
301 bb
= create_basic_block_structure (index
, head
, end
, NULL
);
306 /* Delete the insns in a (non-live) block. We physically delete every
307 non-deleted-note insn, and update the flow graph appropriately.
309 Return nonzero if we deleted an exception handler. */
311 /* ??? Preserving all such notes strikes me as wrong. It would be nice
312 to post-process the stream to remove empty blocks, loops, ranges, etc. */
315 flow_delete_block (b
)
318 int deleted_handler
= 0;
321 /* If the head of this block is a CODE_LABEL, then it might be the
322 label for an exception handler which can't be reached.
324 We need to remove the label from the exception_handler_label list
325 and remove the associated NOTE_INSN_EH_REGION_BEG and
326 NOTE_INSN_EH_REGION_END notes. */
330 never_reached_warning (insn
);
332 if (GET_CODE (insn
) == CODE_LABEL
)
333 maybe_remove_eh_handler (insn
);
335 /* Include any jump table following the basic block. */
337 if (GET_CODE (end
) == JUMP_INSN
338 && (tmp
= JUMP_LABEL (end
)) != NULL_RTX
339 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
340 && GET_CODE (tmp
) == JUMP_INSN
341 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
342 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
345 /* Include any barrier that may follow the basic block. */
346 tmp
= next_nonnote_insn (end
);
347 if (tmp
&& GET_CODE (tmp
) == BARRIER
)
350 /* Selectively delete the entire chain. */
352 delete_insn_chain (insn
, end
);
354 /* Remove the edges into and out of this block. Note that there may
355 indeed be edges in, if we are removing an unreachable loop. */
356 while (b
->pred
!= NULL
)
357 remove_edge (b
->pred
);
358 while (b
->succ
!= NULL
)
359 remove_edge (b
->succ
);
364 /* Remove the basic block from the array, and compact behind it. */
367 return deleted_handler
;
370 /* Records the basic block struct in BB_FOR_INSN, for every instruction
371 indexed by INSN_UID. MAX is the size of the array. */
374 compute_bb_for_insn (max
)
379 if (basic_block_for_insn
)
380 VARRAY_FREE (basic_block_for_insn
);
382 VARRAY_BB_INIT (basic_block_for_insn
, max
, "basic_block_for_insn");
384 for (i
= 0; i
< n_basic_blocks
; ++i
)
386 basic_block bb
= BASIC_BLOCK (i
);
390 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
392 if (INSN_UID (insn
) < max
)
393 VARRAY_BB (basic_block_for_insn
, INSN_UID (insn
)) = bb
;
401 /* Release the basic_block_for_insn array. */
406 if (basic_block_for_insn
)
407 VARRAY_FREE (basic_block_for_insn
);
409 basic_block_for_insn
= 0;
412 /* Update insns block within BB. */
415 update_bb_for_insn (bb
)
420 if (! basic_block_for_insn
)
423 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
425 set_block_for_insn (insn
, bb
);
431 /* Record INSN's block as BB. */
434 set_block_for_insn (insn
, bb
)
438 size_t uid
= INSN_UID (insn
);
440 if (uid
>= basic_block_for_insn
->num_elements
)
442 /* Add one-eighth the size so we don't keep calling xrealloc. */
443 size_t new_size
= uid
+ (uid
+ 7) / 8;
445 VARRAY_GROW (basic_block_for_insn
, new_size
);
448 VARRAY_BB (basic_block_for_insn
, uid
) = bb
;
451 /* Split a block BB after insn INSN creating a new fallthru edge.
452 Return the new edge. Note that to keep other parts of the compiler happy,
453 this function renumbers all the basic blocks so that the new
454 one has a number one greater than the block split. */
457 split_block (bb
, insn
)
465 /* There is no point splitting the block after its end. */
469 /* Create the new basic block. */
470 new_bb
= create_basic_block (bb
->index
+ 1, NEXT_INSN (insn
), bb
->end
);
471 new_bb
->count
= bb
->count
;
472 new_bb
->frequency
= bb
->frequency
;
473 new_bb
->loop_depth
= bb
->loop_depth
;
476 /* Redirect the outgoing edges. */
477 new_bb
->succ
= bb
->succ
;
479 for (e
= new_bb
->succ
; e
; e
= e
->succ_next
)
482 new_edge
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
484 if (bb
->global_live_at_start
)
486 new_bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
487 new_bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
488 COPY_REG_SET (new_bb
->global_live_at_end
, bb
->global_live_at_end
);
490 /* We now have to calculate which registers are live at the end
491 of the split basic block and at the start of the new basic
492 block. Start with those registers that are known to be live
493 at the end of the original basic block and get
494 propagate_block to determine which registers are live. */
495 COPY_REG_SET (new_bb
->global_live_at_start
, bb
->global_live_at_end
);
496 propagate_block (new_bb
, new_bb
->global_live_at_start
, NULL
, NULL
, 0);
497 COPY_REG_SET (bb
->global_live_at_end
,
498 new_bb
->global_live_at_start
);
504 /* Blocks A and B are to be merged into a single block A. The insns
505 are already contiguous, hence `nomove'. */
508 merge_blocks_nomove (a
, b
)
511 rtx b_head
= b
->head
, b_end
= b
->end
, a_end
= a
->end
;
512 rtx del_first
= NULL_RTX
, del_last
= NULL_RTX
;
516 /* If there was a CODE_LABEL beginning B, delete it. */
517 if (GET_CODE (b_head
) == CODE_LABEL
)
519 /* Detect basic blocks with nothing but a label. This can happen
520 in particular at the end of a function. */
524 del_first
= del_last
= b_head
;
525 b_head
= NEXT_INSN (b_head
);
528 /* Delete the basic block note and handle blocks containing just that
530 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
538 b_head
= NEXT_INSN (b_head
);
541 /* If there was a jump out of A, delete it. */
542 if (GET_CODE (a_end
) == JUMP_INSN
)
546 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
547 if (GET_CODE (prev
) != NOTE
548 || NOTE_LINE_NUMBER (prev
) == NOTE_INSN_BASIC_BLOCK
555 /* If this was a conditional jump, we need to also delete
556 the insn that set cc0. */
557 if (only_sets_cc0_p (prev
))
561 prev
= prev_nonnote_insn (prev
);
568 a_end
= PREV_INSN (del_first
);
570 else if (GET_CODE (NEXT_INSN (a_end
)) == BARRIER
)
571 del_first
= NEXT_INSN (a_end
);
573 /* Normally there should only be one successor of A and that is B, but
574 partway though the merge of blocks for conditional_execution we'll
575 be merging a TEST block with THEN and ELSE successors. Free the
576 whole lot of them and hope the caller knows what they're doing. */
578 remove_edge (a
->succ
);
580 /* Adjust the edges out of B for the new owner. */
581 for (e
= b
->succ
; e
; e
= e
->succ_next
)
585 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
586 b
->pred
= b
->succ
= NULL
;
587 a
->global_live_at_end
= b
->global_live_at_end
;
591 /* Delete everything marked above as well as crap that might be
592 hanging out between the two blocks. */
593 delete_insn_chain (del_first
, del_last
);
595 /* Reassociate the insns of B with A. */
598 if (basic_block_for_insn
)
602 for (x
= a_end
; x
!= b_end
; x
= NEXT_INSN (x
))
603 BLOCK_FOR_INSN (x
) = a
;
605 BLOCK_FOR_INSN (b_end
) = a
;
614 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
621 if (block
== EXIT_BLOCK_PTR
)
624 if (GET_CODE (block
->head
) != CODE_LABEL
)
626 block
->head
= emit_label_before (gen_label_rtx (), block
->head
);
627 if (basic_block_for_insn
)
628 set_block_for_insn (block
->head
, block
);
634 /* Attempt to perform edge redirection by replacing possibly complex jump
635 instruction by unconditional jump or removing jump completely. This can
636 apply only if all edges now point to the same block. The parameters and
637 return values are equivalent to redirect_edge_and_branch. */
640 try_redirect_by_replacing_jump (e
, target
)
644 basic_block src
= e
->src
;
645 rtx insn
= src
->end
, kill_from
;
650 /* Verify that all targets will be TARGET. */
651 for (tmp
= src
->succ
; tmp
; tmp
= tmp
->succ_next
)
652 if (tmp
->dest
!= target
&& tmp
!= e
)
655 if (tmp
|| !onlyjump_p (insn
))
658 /* Avoid removing branch with side effects. */
659 set
= single_set (insn
);
660 if (!set
|| side_effects_p (set
))
663 /* In case we zap a conditional jump, we'll need to kill
664 the cc0 setter too. */
667 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
)))
668 kill_from
= PREV_INSN (insn
);
671 /* See if we can create the fallthru edge. */
672 if (can_fallthru (src
, target
))
675 fprintf (rtl_dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
678 /* Selectively unlink whole insn chain. */
679 delete_insn_chain (kill_from
, PREV_INSN (target
->head
));
682 /* If this already is simplejump, redirect it. */
683 else if (simplejump_p (insn
))
685 if (e
->dest
== target
)
688 fprintf (rtl_dump_file
, "Redirecting jump %i from %i to %i.\n",
689 INSN_UID (insn
), e
->dest
->index
, target
->index
);
690 redirect_jump (insn
, block_label (target
), 0);
693 /* Or replace possibly complicated jump insn by simple jump insn. */
696 rtx target_label
= block_label (target
);
699 emit_jump_insn_after (gen_jump (target_label
), insn
);
700 JUMP_LABEL (src
->end
) = target_label
;
701 LABEL_NUSES (target_label
)++;
703 fprintf (rtl_dump_file
, "Replacing insn %i by jump %i\n",
704 INSN_UID (insn
), INSN_UID (src
->end
));
706 delete_insn_chain (kill_from
, insn
);
708 barrier
= next_nonnote_insn (src
->end
);
709 if (!barrier
|| GET_CODE (barrier
) != BARRIER
)
710 emit_barrier_after (src
->end
);
713 /* Keep only one edge out and set proper flags. */
714 while (src
->succ
->succ_next
)
715 remove_edge (src
->succ
);
718 e
->flags
= EDGE_FALLTHRU
;
722 e
->probability
= REG_BR_PROB_BASE
;
723 e
->count
= src
->count
;
725 /* We don't want a block to end on a line-number note since that has
726 the potential of changing the code between -g and not -g. */
727 while (GET_CODE (e
->src
->end
) == NOTE
728 && NOTE_LINE_NUMBER (e
->src
->end
) >= 0)
729 delete_insn (e
->src
->end
);
731 if (e
->dest
!= target
)
732 redirect_edge_succ (e
, target
);
737 /* Return last loop_beg note appearing after INSN, before start of next
738 basic block. Return INSN if there are no such notes.
740 When emitting jump to redirect an fallthru edge, it should always appear
741 after the LOOP_BEG notes, as loop optimizer expect loop to either start by
742 fallthru edge or jump following the LOOP_BEG note jumping to the loop exit
746 last_loop_beg_note (insn
)
751 for (insn
= NEXT_INSN (insn
); insn
&& GET_CODE (insn
) == NOTE
752 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
;
753 insn
= NEXT_INSN (insn
))
754 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
760 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
761 expense of adding new instructions or reordering basic blocks.
763 Function can be also called with edge destination equivalent to the TARGET.
764 Then it should try the simplifications and do nothing if none is possible.
766 Return true if transformation succeeded. We still return false in case E
767 already destinated TARGET and we didn't managed to simplify instruction
771 redirect_edge_and_branch (e
, target
)
776 rtx old_label
= e
->dest
->head
;
777 basic_block src
= e
->src
;
780 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
783 if (try_redirect_by_replacing_jump (e
, target
))
786 /* Do this fast path late, as we want above code to simplify for cases
787 where called on single edge leaving basic block containing nontrivial
789 else if (e
->dest
== target
)
792 /* We can only redirect non-fallthru edges of jump insn. */
793 if (e
->flags
& EDGE_FALLTHRU
)
795 else if (GET_CODE (insn
) != JUMP_INSN
)
798 /* Recognize a tablejump and adjust all matching cases. */
799 if ((tmp
= JUMP_LABEL (insn
)) != NULL_RTX
800 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
801 && GET_CODE (tmp
) == JUMP_INSN
802 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
803 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
807 rtx new_label
= block_label (target
);
809 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
810 vec
= XVEC (PATTERN (tmp
), 0);
812 vec
= XVEC (PATTERN (tmp
), 1);
814 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
815 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
817 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
818 --LABEL_NUSES (old_label
);
819 ++LABEL_NUSES (new_label
);
822 /* Handle casesi dispatch insns */
823 if ((tmp
= single_set (insn
)) != NULL
824 && SET_DEST (tmp
) == pc_rtx
825 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
826 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
827 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
829 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (VOIDmode
,
831 --LABEL_NUSES (old_label
);
832 ++LABEL_NUSES (new_label
);
837 /* ?? We may play the games with moving the named labels from
838 one basic block to the other in case only one computed_jump is
840 if (computed_jump_p (insn
)
841 /* A return instruction can't be redirected. */
842 || returnjump_p (insn
))
845 /* If the insn doesn't go where we think, we're confused. */
846 if (JUMP_LABEL (insn
) != old_label
847 /* If the substitution doesn't succeed, die. This can happen
848 if the back end emitted unrecognizable instructions. */
849 || !redirect_jump (insn
, block_label (target
), 0))
854 fprintf (rtl_dump_file
, "Edge %i->%i redirected to %i\n",
855 e
->src
->index
, e
->dest
->index
, target
->index
);
857 if (e
->dest
!= target
)
858 redirect_edge_succ_nodup (e
, target
);
863 /* Like force_nonfallthru below, but additionally performs redirection
864 Used by redirect_edge_and_branch_force. */
867 force_nonfallthru_and_redirect (e
, target
)
871 basic_block jump_block
, new_bb
= NULL
;
875 if (e
->flags
& EDGE_ABNORMAL
)
877 else if (!(e
->flags
& EDGE_FALLTHRU
))
879 else if (e
->src
->succ
->succ_next
)
881 /* Create the new structures. */
882 note
= last_loop_beg_note (e
->src
->end
);
884 = create_basic_block (e
->src
->index
+ 1, NEXT_INSN (note
), NULL
);
885 jump_block
->count
= e
->count
;
886 jump_block
->frequency
= EDGE_FREQUENCY (e
);
887 jump_block
->loop_depth
= target
->loop_depth
;
889 if (target
->global_live_at_start
)
891 jump_block
->global_live_at_start
892 = OBSTACK_ALLOC_REG_SET (&flow_obstack
);
893 jump_block
->global_live_at_end
894 = OBSTACK_ALLOC_REG_SET (&flow_obstack
);
895 COPY_REG_SET (jump_block
->global_live_at_start
,
896 target
->global_live_at_start
);
897 COPY_REG_SET (jump_block
->global_live_at_end
,
898 target
->global_live_at_start
);
902 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
903 new_edge
->probability
= e
->probability
;
904 new_edge
->count
= e
->count
;
906 /* Redirect old edge. */
907 redirect_edge_pred (e
, jump_block
);
908 e
->probability
= REG_BR_PROB_BASE
;
915 e
->flags
&= ~EDGE_FALLTHRU
;
916 if (target
== EXIT_BLOCK_PTR
)
919 emit_jump_insn_after (gen_return (), jump_block
->end
);
925 rtx label
= block_label (target
);
926 emit_jump_insn_after (gen_jump (label
), jump_block
->end
);
927 JUMP_LABEL (jump_block
->end
) = label
;
928 LABEL_NUSES (label
)++;
931 emit_barrier_after (jump_block
->end
);
932 redirect_edge_succ_nodup (e
, target
);
937 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
938 (and possibly create new basic block) to make edge non-fallthru.
939 Return newly created BB or NULL if none. */
942 force_nonfallthru (e
)
945 return force_nonfallthru_and_redirect (e
, e
->dest
);
948 /* Redirect edge even at the expense of creating new jump insn or
949 basic block. Return new basic block if created, NULL otherwise.
950 Abort if conversion is impossible. */
953 redirect_edge_and_branch_force (e
, target
)
957 if (redirect_edge_and_branch (e
, target
)
958 || e
->dest
== target
)
961 /* In case the edge redirection failed, try to force it to be non-fallthru
962 and redirect newly created simplejump. */
963 return force_nonfallthru_and_redirect (e
, target
);
966 /* The given edge should potentially be a fallthru edge. If that is in
967 fact true, delete the jump and barriers that are in the way. */
970 tidy_fallthru_edge (e
, b
, c
)
976 /* ??? In a late-running flow pass, other folks may have deleted basic
977 blocks by nopping out blocks, leaving multiple BARRIERs between here
978 and the target label. They ought to be chastized and fixed.
980 We can also wind up with a sequence of undeletable labels between
981 one block and the next.
983 So search through a sequence of barriers, labels, and notes for
984 the head of block C and assert that we really do fall through. */
986 if (next_real_insn (b
->end
) != next_real_insn (PREV_INSN (c
->head
)))
989 /* Remove what will soon cease being the jump insn from the source block.
990 If block B consisted only of this single jump, turn it into a deleted
993 if (GET_CODE (q
) == JUMP_INSN
995 && (any_uncondjump_p (q
)
996 || (b
->succ
== e
&& e
->succ_next
== NULL
)))
999 /* If this was a conditional jump, we need to also delete
1000 the insn that set cc0. */
1001 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1007 /* We don't want a block to end on a line-number note since that has
1008 the potential of changing the code between -g and not -g. */
1009 while (GET_CODE (q
) == NOTE
&& NOTE_LINE_NUMBER (q
) >= 0)
1013 /* Selectively unlink the sequence. */
1014 if (q
!= PREV_INSN (c
->head
))
1015 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (c
->head
));
1017 e
->flags
|= EDGE_FALLTHRU
;
1020 /* Fix up edges that now fall through, or rather should now fall through
1021 but previously required a jump around now deleted blocks. Simplify
1022 the search by only examining blocks numerically adjacent, since this
1023 is how find_basic_blocks created them. */
1026 tidy_fallthru_edges ()
1030 for (i
= 1; i
< n_basic_blocks
; i
++)
1032 basic_block b
= BASIC_BLOCK (i
- 1);
1033 basic_block c
= BASIC_BLOCK (i
);
1036 /* We care about simple conditional or unconditional jumps with
1039 If we had a conditional branch to the next instruction when
1040 find_basic_blocks was called, then there will only be one
1041 out edge for the block which ended with the conditional
1042 branch (since we do not create duplicate edges).
1044 Furthermore, the edge will be marked as a fallthru because we
1045 merge the flags for the duplicate edges. So we do not want to
1046 check that the edge is not a FALLTHRU edge. */
1048 if ((s
= b
->succ
) != NULL
1049 && ! (s
->flags
& EDGE_COMPLEX
)
1050 && s
->succ_next
== NULL
1052 /* If the jump insn has side effects, we can't tidy the edge. */
1053 && (GET_CODE (b
->end
) != JUMP_INSN
1054 || onlyjump_p (b
->end
)))
1055 tidy_fallthru_edge (s
, b
, c
);
1059 /* Helper function for split_edge. Return true in case edge BB2 to BB1
1060 is back edge of syntactic loop. */
1063 back_edge_of_syntactic_loop_p (bb1
, bb2
)
1064 basic_block bb1
, bb2
;
1069 if (bb1
->index
> bb2
->index
)
1071 else if (bb1
->index
== bb2
->index
)
1074 for (insn
= bb1
->end
; insn
!= bb2
->head
&& count
>= 0;
1075 insn
= NEXT_INSN (insn
))
1076 if (GET_CODE (insn
) == NOTE
)
1078 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
1080 else if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
)
1087 /* Split a (typically critical) edge. Return the new block.
1088 Abort on abnormal edges.
1090 ??? The code generally expects to be called on critical edges.
1091 The case of a block ending in an unconditional jump to a
1092 block with multiple predecessors is not handled optimally. */
1095 split_edge (edge_in
)
1102 /* Abnormal edges cannot be split. */
1103 if ((edge_in
->flags
& EDGE_ABNORMAL
) != 0)
1106 /* We are going to place the new block in front of edge destination.
1107 Avoid existence of fallthru predecessors. */
1108 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1112 for (e
= edge_in
->dest
->pred
; e
; e
= e
->pred_next
)
1113 if (e
->flags
& EDGE_FALLTHRU
)
1117 force_nonfallthru (e
);
1120 /* Create the basic block note.
1122 Where we place the note can have a noticeable impact on the generated
1123 code. Consider this cfg:
1133 If we need to insert an insn on the edge from block 0 to block 1,
1134 we want to ensure the instructions we insert are outside of any
1135 loop notes that physically sit between block 0 and block 1. Otherwise
1136 we confuse the loop optimizer into thinking the loop is a phony. */
1138 if (edge_in
->dest
!= EXIT_BLOCK_PTR
1139 && PREV_INSN (edge_in
->dest
->head
)
1140 && GET_CODE (PREV_INSN (edge_in
->dest
->head
)) == NOTE
1141 && (NOTE_LINE_NUMBER (PREV_INSN (edge_in
->dest
->head
))
1142 == NOTE_INSN_LOOP_BEG
)
1143 && !back_edge_of_syntactic_loop_p (edge_in
->dest
, edge_in
->src
))
1144 before
= PREV_INSN (edge_in
->dest
->head
);
1145 else if (edge_in
->dest
!= EXIT_BLOCK_PTR
)
1146 before
= edge_in
->dest
->head
;
1150 bb
= create_basic_block (edge_in
->dest
== EXIT_BLOCK_PTR
? n_basic_blocks
1151 : edge_in
->dest
->index
, before
, NULL
);
1152 bb
->count
= edge_in
->count
;
1153 bb
->frequency
= EDGE_FREQUENCY (edge_in
);
1155 /* ??? This info is likely going to be out of date very soon. */
1156 if (edge_in
->dest
->global_live_at_start
)
1158 bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1159 bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1160 COPY_REG_SET (bb
->global_live_at_start
,
1161 edge_in
->dest
->global_live_at_start
);
1162 COPY_REG_SET (bb
->global_live_at_end
,
1163 edge_in
->dest
->global_live_at_start
);
1166 edge_out
= make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1168 /* For non-fallthry edges, we must adjust the predecessor's
1169 jump instruction to target our new block. */
1170 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1172 if (!redirect_edge_and_branch (edge_in
, bb
))
1176 redirect_edge_succ (edge_in
, bb
);
1181 /* Queue instructions for insertion on an edge between two basic blocks.
1182 The new instructions and basic blocks (if any) will not appear in the
1183 CFG until commit_edge_insertions is called. */
1186 insert_insn_on_edge (pattern
, e
)
1190 /* We cannot insert instructions on an abnormal critical edge.
1191 It will be easier to find the culprit if we die now. */
1192 if ((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
1195 if (e
->insns
== NULL_RTX
)
1198 push_to_sequence (e
->insns
);
1200 emit_insn (pattern
);
1202 e
->insns
= get_insns ();
1206 /* Update the CFG for the instructions queued on edge E. */
1209 commit_one_edge_insertion (e
)
1212 rtx before
= NULL_RTX
, after
= NULL_RTX
, insns
, tmp
, last
;
1215 /* Pull the insns off the edge now since the edge might go away. */
1217 e
->insns
= NULL_RTX
;
1219 /* Figure out where to put these things. If the destination has
1220 one predecessor, insert there. Except for the exit block. */
1221 if (e
->dest
->pred
->pred_next
== NULL
1222 && e
->dest
!= EXIT_BLOCK_PTR
)
1226 /* Get the location correct wrt a code label, and "nice" wrt
1227 a basic block note, and before everything else. */
1229 if (GET_CODE (tmp
) == CODE_LABEL
)
1230 tmp
= NEXT_INSN (tmp
);
1231 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1232 tmp
= NEXT_INSN (tmp
);
1233 if (tmp
== bb
->head
)
1236 after
= PREV_INSN (tmp
);
1239 /* If the source has one successor and the edge is not abnormal,
1240 insert there. Except for the entry block. */
1241 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1242 && e
->src
->succ
->succ_next
== NULL
1243 && e
->src
!= ENTRY_BLOCK_PTR
)
1247 /* It is possible to have a non-simple jump here. Consider a target
1248 where some forms of unconditional jumps clobber a register. This
1249 happens on the fr30 for example.
1251 We know this block has a single successor, so we can just emit
1252 the queued insns before the jump. */
1253 if (GET_CODE (bb
->end
) == JUMP_INSN
)
1254 for (before
= bb
->end
;
1255 GET_CODE (PREV_INSN (before
)) == NOTE
1256 && NOTE_LINE_NUMBER (PREV_INSN (before
)) == NOTE_INSN_LOOP_BEG
;
1257 before
= PREV_INSN (before
))
1261 /* We'd better be fallthru, or we've lost track of what's what. */
1262 if ((e
->flags
& EDGE_FALLTHRU
) == 0)
1269 /* Otherwise we must split the edge. */
1272 bb
= split_edge (e
);
1276 /* Now that we've found the spot, do the insertion. */
1280 emit_insns_before (insns
, before
);
1281 last
= prev_nonnote_insn (before
);
1284 last
= emit_insns_after (insns
, after
);
1286 if (returnjump_p (last
))
1288 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1289 This is not currently a problem because this only happens
1290 for the (single) epilogue, which already has a fallthru edge
1294 if (e
->dest
!= EXIT_BLOCK_PTR
1295 || e
->succ_next
!= NULL
1296 || (e
->flags
& EDGE_FALLTHRU
) == 0)
1299 e
->flags
&= ~EDGE_FALLTHRU
;
1300 emit_barrier_after (last
);
1303 delete_insn (before
);
1305 else if (GET_CODE (last
) == JUMP_INSN
)
1308 find_sub_basic_blocks (bb
);
1311 /* Update the CFG for all queued instructions. */
1314 commit_edge_insertions ()
1319 #ifdef ENABLE_CHECKING
1320 verify_flow_info ();
1324 bb
= ENTRY_BLOCK_PTR
;
1329 for (e
= bb
->succ
; e
; e
= next
)
1331 next
= e
->succ_next
;
1333 commit_one_edge_insertion (e
);
1336 if (++i
>= n_basic_blocks
)
1338 bb
= BASIC_BLOCK (i
);
1342 /* Print out one basic block with live information at start and end. */
1353 fprintf (outf
, ";; Basic block %d, loop depth %d, count ",
1354 bb
->index
, bb
->loop_depth
);
1355 fprintf (outf
, HOST_WIDEST_INT_PRINT_DEC
, (HOST_WIDEST_INT
) bb
->count
);
1358 fputs (";; Predecessors: ", outf
);
1359 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1360 dump_edge_info (outf
, e
, 0);
1363 fputs (";; Registers live at start:", outf
);
1364 dump_regset (bb
->global_live_at_start
, outf
);
1367 for (insn
= bb
->head
, last
= NEXT_INSN (bb
->end
); insn
!= last
;
1368 insn
= NEXT_INSN (insn
))
1369 print_rtl_single (outf
, insn
);
1371 fputs (";; Registers live at end:", outf
);
1372 dump_regset (bb
->global_live_at_end
, outf
);
1375 fputs (";; Successors: ", outf
);
1376 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1377 dump_edge_info (outf
, e
, 1);
1385 dump_bb (bb
, stderr
);
1392 dump_bb (BASIC_BLOCK (n
), stderr
);
1395 /* Like print_rtl, but also print out live information for the start of each
1399 print_rtl_with_bb (outf
, rtx_first
)
1406 fprintf (outf
, "(nil)\n");
1410 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
1411 int max_uid
= get_max_uid ();
1413 = (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1415 = (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1416 enum bb_state
*in_bb_p
1417 = (enum bb_state
*) xcalloc (max_uid
, sizeof (enum bb_state
));
1419 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1421 basic_block bb
= BASIC_BLOCK (i
);
1424 start
[INSN_UID (bb
->head
)] = bb
;
1425 end
[INSN_UID (bb
->end
)] = bb
;
1426 for (x
= bb
->head
; x
!= NULL_RTX
; x
= NEXT_INSN (x
))
1428 enum bb_state state
= IN_MULTIPLE_BB
;
1430 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
1432 in_bb_p
[INSN_UID (x
)] = state
;
1439 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
1444 if ((bb
= start
[INSN_UID (tmp_rtx
)]) != NULL
)
1446 fprintf (outf
, ";; Start of basic block %d, registers live:",
1448 dump_regset (bb
->global_live_at_start
, outf
);
1452 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
1453 && GET_CODE (tmp_rtx
) != NOTE
1454 && GET_CODE (tmp_rtx
) != BARRIER
)
1455 fprintf (outf
, ";; Insn is not within a basic block\n");
1456 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
1457 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
1459 did_output
= print_rtl_single (outf
, tmp_rtx
);
1461 if ((bb
= end
[INSN_UID (tmp_rtx
)]) != NULL
)
1463 fprintf (outf
, ";; End of basic block %d, registers live:\n",
1465 dump_regset (bb
->global_live_at_end
, outf
);
1478 if (current_function_epilogue_delay_list
!= 0)
1480 fprintf (outf
, "\n;; Insns in epilogue delay list:\n\n");
1481 for (tmp_rtx
= current_function_epilogue_delay_list
; tmp_rtx
!= 0;
1482 tmp_rtx
= XEXP (tmp_rtx
, 1))
1483 print_rtl_single (outf
, XEXP (tmp_rtx
, 0));
1487 /* Verify the CFG consistency. This function check some CFG invariants and
1488 aborts when something is wrong. Hope that this function will help to
1489 convert many optimization passes to preserve CFG consistent.
1491 Currently it does following checks:
1493 - test head/end pointers
1494 - overlapping of basic blocks
1495 - edge list correctness
1496 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1497 - tails of basic blocks (ensure that boundary is necessary)
1498 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1499 and NOTE_INSN_BASIC_BLOCK
1500 - check that all insns are in the basic blocks
1501 (except the switch handling code, barriers and notes)
1502 - check that all returns are followed by barriers
1504 In future it can be extended check a lot of other stuff as well
1505 (reachability of basic blocks, life information, etc. etc.). */
1510 const int max_uid
= get_max_uid ();
1511 const rtx rtx_first
= get_insns ();
1512 rtx last_head
= get_last_insn ();
1513 basic_block
*bb_info
, *last_visited
;
1514 size_t *edge_checksum
;
1516 int i
, last_bb_num_seen
, num_bb_notes
, err
= 0;
1518 bb_info
= (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1519 last_visited
= (basic_block
*) xcalloc (n_basic_blocks
+ 2,
1520 sizeof (basic_block
));
1521 edge_checksum
= (size_t *) xcalloc (n_basic_blocks
+ 2, sizeof (size_t));
1523 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1525 basic_block bb
= BASIC_BLOCK (i
);
1526 rtx head
= bb
->head
;
1529 /* Verify the end of the basic block is in the INSN chain. */
1530 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1536 error ("end insn %d for block %d not found in the insn stream",
1537 INSN_UID (end
), bb
->index
);
1541 /* Work backwards from the end to the head of the basic block
1542 to verify the head is in the RTL chain. */
1543 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1545 /* While walking over the insn chain, verify insns appear
1546 in only one basic block and initialize the BB_INFO array
1547 used by other passes. */
1548 if (bb_info
[INSN_UID (x
)] != NULL
)
1550 error ("insn %d is in multiple basic blocks (%d and %d)",
1551 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
1555 bb_info
[INSN_UID (x
)] = bb
;
1562 error ("head insn %d for block %d not found in the insn stream",
1563 INSN_UID (head
), bb
->index
);
1570 /* Now check the basic blocks (boundaries etc.) */
1571 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1573 basic_block bb
= BASIC_BLOCK (i
);
1574 int has_fallthru
= 0;
1577 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1579 if (last_visited
[e
->dest
->index
+ 2] == bb
)
1581 error ("verify_flow_info: Duplicate edge %i->%i",
1582 e
->src
->index
, e
->dest
->index
);
1586 last_visited
[e
->dest
->index
+ 2] = bb
;
1588 if (e
->flags
& EDGE_FALLTHRU
)
1591 if ((e
->flags
& EDGE_FALLTHRU
)
1592 && e
->src
!= ENTRY_BLOCK_PTR
1593 && e
->dest
!= EXIT_BLOCK_PTR
)
1597 if (e
->src
->index
+ 1 != e
->dest
->index
)
1600 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
1601 e
->src
->index
, e
->dest
->index
);
1605 for (insn
= NEXT_INSN (e
->src
->end
); insn
!= e
->dest
->head
;
1606 insn
= NEXT_INSN (insn
))
1607 if (GET_CODE (insn
) == BARRIER
1608 #ifndef CASE_DROPS_THROUGH
1611 || (INSN_P (insn
) && ! JUMP_TABLE_DATA_P (insn
))
1615 error ("verify_flow_info: Incorrect fallthru %i->%i",
1616 e
->src
->index
, e
->dest
->index
);
1617 fatal_insn ("wrong insn in the fallthru edge", insn
);
1624 error ("verify_flow_info: Basic block %d succ edge is corrupted",
1626 fprintf (stderr
, "Predecessor: ");
1627 dump_edge_info (stderr
, e
, 0);
1628 fprintf (stderr
, "\nSuccessor: ");
1629 dump_edge_info (stderr
, e
, 1);
1630 fprintf (stderr
, "\n");
1634 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
1641 /* Ensure existence of barrier in BB with no fallthru edges. */
1642 for (insn
= bb
->end
; !insn
|| GET_CODE (insn
) != BARRIER
;
1643 insn
= NEXT_INSN (insn
))
1645 || (GET_CODE (insn
) == NOTE
1646 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BASIC_BLOCK
))
1648 error ("missing barrier after block %i", bb
->index
);
1654 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1658 error ("basic block %d pred edge is corrupted", bb
->index
);
1659 fputs ("Predecessor: ", stderr
);
1660 dump_edge_info (stderr
, e
, 0);
1661 fputs ("\nSuccessor: ", stderr
);
1662 dump_edge_info (stderr
, e
, 1);
1663 fputc ('\n', stderr
);
1666 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
1669 for (x
= bb
->head
; x
!= NEXT_INSN (bb
->end
); x
= NEXT_INSN (x
))
1670 if (basic_block_for_insn
&& BLOCK_FOR_INSN (x
) != bb
)
1673 if (! BLOCK_FOR_INSN (x
))
1675 ("insn %d inside basic block %d but block_for_insn is NULL",
1676 INSN_UID (x
), bb
->index
);
1679 ("insn %d inside basic block %d but block_for_insn is %i",
1680 INSN_UID (x
), bb
->index
, BLOCK_FOR_INSN (x
)->index
);
1685 /* OK pointers are correct. Now check the header of basic
1686 block. It ought to contain optional CODE_LABEL followed
1687 by NOTE_BASIC_BLOCK. */
1689 if (GET_CODE (x
) == CODE_LABEL
)
1693 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1701 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
1703 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1709 /* Do checks for empty blocks her. e */
1712 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
1714 if (NOTE_INSN_BASIC_BLOCK_P (x
))
1716 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
1717 INSN_UID (x
), bb
->index
);
1724 if (GET_CODE (x
) == JUMP_INSN
1725 || GET_CODE (x
) == CODE_LABEL
1726 || GET_CODE (x
) == BARRIER
)
1728 error ("in basic block %d:", bb
->index
);
1729 fatal_insn ("flow control insn inside a basic block", x
);
1734 /* Complete edge checksumming for ENTRY and EXIT. */
1738 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
1739 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
1741 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
1742 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
1745 for (i
= -2; i
< n_basic_blocks
; ++i
)
1746 if (edge_checksum
[i
+ 2])
1748 error ("basic block %i edge lists are corrupted", i
);
1752 last_bb_num_seen
= -1;
1754 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
1756 if (NOTE_INSN_BASIC_BLOCK_P (x
))
1758 basic_block bb
= NOTE_BASIC_BLOCK (x
);
1761 if (bb
->index
!= last_bb_num_seen
+ 1)
1762 internal_error ("basic blocks not numbered consecutively");
1764 last_bb_num_seen
= bb
->index
;
1767 if (!bb_info
[INSN_UID (x
)])
1769 switch (GET_CODE (x
))
1776 /* An addr_vec is placed outside any block block. */
1778 && GET_CODE (NEXT_INSN (x
)) == JUMP_INSN
1779 && (GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_DIFF_VEC
1780 || GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_VEC
))
1783 /* But in any case, non-deletable labels can appear anywhere. */
1787 fatal_insn ("insn outside basic block", x
);
1792 && GET_CODE (x
) == JUMP_INSN
1793 && returnjump_p (x
) && ! condjump_p (x
)
1794 && ! (NEXT_INSN (x
) && GET_CODE (NEXT_INSN (x
)) == BARRIER
))
1795 fatal_insn ("return not followed by barrier", x
);
1798 if (num_bb_notes
!= n_basic_blocks
)
1800 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
1801 num_bb_notes
, n_basic_blocks
);
1804 internal_error ("verify_flow_info failed");
1808 free (last_visited
);
1809 free (edge_checksum
);
1812 /* Assume that the preceding pass has possibly eliminated jump instructions
1813 or converted the unconditional jumps. Eliminate the edges from CFG.
1814 Return true if any edges are eliminated. */
1817 purge_dead_edges (bb
)
1821 rtx insn
= bb
->end
, note
;
1822 bool purged
= false;
1824 /* ??? This makes no sense since the later test includes more cases. */
1825 if (GET_CODE (insn
) == JUMP_INSN
&& !simplejump_p (insn
))
1828 if (GET_CODE (insn
) == JUMP_INSN
)
1833 /* We do care only about conditional jumps and simplejumps. */
1834 if (!any_condjump_p (insn
)
1835 && !returnjump_p (insn
)
1836 && !simplejump_p (insn
))
1839 for (e
= bb
->succ
; e
; e
= next
)
1841 next
= e
->succ_next
;
1843 /* Avoid abnormal flags to leak from computed jumps turned
1844 into simplejumps. */
1846 e
->flags
&= ~EDGE_ABNORMAL
;
1848 /* Check purposes we can have edge. */
1849 if ((e
->flags
& EDGE_FALLTHRU
)
1850 && any_condjump_p (insn
))
1852 else if (e
->dest
!= EXIT_BLOCK_PTR
1853 && e
->dest
->head
== JUMP_LABEL (insn
))
1855 else if (e
->dest
== EXIT_BLOCK_PTR
1856 && returnjump_p (insn
))
1863 if (!bb
->succ
|| !purged
)
1867 fprintf (rtl_dump_file
, "Purged edges from bb %i\n", bb
->index
);
1872 /* Redistribute probabilities. */
1873 if (!bb
->succ
->succ_next
)
1875 bb
->succ
->probability
= REG_BR_PROB_BASE
;
1876 bb
->succ
->count
= bb
->count
;
1880 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
1884 b
= BRANCH_EDGE (bb
);
1885 f
= FALLTHRU_EDGE (bb
);
1886 b
->probability
= INTVAL (XEXP (note
, 0));
1887 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
1888 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
1889 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
1895 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
1896 if (GET_CODE (insn
) == INSN
1897 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
1901 if (! may_trap_p (PATTERN (insn
))
1902 || ((eqnote
= find_reg_equal_equiv_note (insn
))
1903 && ! may_trap_p (XEXP (eqnote
, 0))))
1904 remove_note (insn
, note
);
1907 /* Cleanup abnormal edges caused by throwing insns that have been
1909 if (! can_throw_internal (bb
->end
))
1910 for (e
= bb
->succ
; e
; e
= next
)
1912 next
= e
->succ_next
;
1913 if (e
->flags
& EDGE_EH
)
1920 /* If we don't see a jump insn, we don't know exactly why the block would
1921 have been broken at this point. Look for a simple, non-fallthru edge,
1922 as these are only created by conditional branches. If we find such an
1923 edge we know that there used to be a jump here and can then safely
1924 remove all non-fallthru edges. */
1925 for (e
= bb
->succ
; e
&& (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
));
1932 for (e
= bb
->succ
; e
; e
= next
)
1934 next
= e
->succ_next
;
1935 if (!(e
->flags
& EDGE_FALLTHRU
))
1936 remove_edge (e
), purged
= true;
1939 if (!bb
->succ
|| bb
->succ
->succ_next
)
1942 bb
->succ
->probability
= REG_BR_PROB_BASE
;
1943 bb
->succ
->count
= bb
->count
;
1946 fprintf (rtl_dump_file
, "Purged non-fallthru edges from bb %i\n",
1951 /* Search all basic blocks for potentially dead edges and purge them. Return
1952 true if some edge has been eliminated. */
1955 purge_all_dead_edges (update_life_p
)
1958 int i
, purged
= false;
1963 blocks
= sbitmap_alloc (n_basic_blocks
);
1964 sbitmap_zero (blocks
);
1967 for (i
= 0; i
< n_basic_blocks
; i
++)
1969 bool purged_here
= purge_dead_edges (BASIC_BLOCK (i
));
1971 purged
|= purged_here
;
1972 if (purged_here
&& update_life_p
)
1973 SET_BIT (blocks
, i
);
1976 if (update_life_p
&& purged
)
1977 update_life_info (blocks
, UPDATE_LIFE_GLOBAL
,
1978 PROP_DEATH_NOTES
| PROP_SCAN_DEAD_CODE
1979 | PROP_KILL_DEAD_CODE
);
1982 sbitmap_free (blocks
);