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
);
138 /* If this insn has already been deleted, something is very wrong. */
139 if (INSN_DELETED_P (insn
))
142 INSN_DELETED_P (insn
) = 1;
145 /* If deleting a jump, decrement the use count of the label. Deleting
146 the label itself should happen in the normal course of block merging. */
147 if (GET_CODE (insn
) == JUMP_INSN
149 && GET_CODE (JUMP_LABEL (insn
)) == CODE_LABEL
)
150 LABEL_NUSES (JUMP_LABEL (insn
))--;
152 /* Also if deleting an insn that references a label. */
153 else if ((note
= find_reg_note (insn
, REG_LABEL
, NULL_RTX
)) != NULL_RTX
154 && GET_CODE (XEXP (note
, 0)) == CODE_LABEL
)
155 LABEL_NUSES (XEXP (note
, 0))--;
157 if (GET_CODE (insn
) == JUMP_INSN
158 && (GET_CODE (PATTERN (insn
)) == ADDR_VEC
159 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
))
161 rtx pat
= PATTERN (insn
);
162 int diff_vec_p
= GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
;
163 int len
= XVECLEN (pat
, diff_vec_p
);
166 for (i
= 0; i
< len
; i
++)
168 rtx label
= XEXP (XVECEXP (pat
, diff_vec_p
, i
), 0);
170 /* When deleting code in bulk (e.g. removing many unreachable
171 blocks) we can delete a label that's a target of the vector
172 before deleting the vector itself. */
173 if (GET_CODE (label
) != NOTE
)
174 LABEL_NUSES (label
)--;
181 /* Unlink a chain of insns between START and FINISH, leaving notes
182 that must be paired. */
185 delete_insn_chain (start
, finish
)
190 /* Unchain the insns one by one. It would be quicker to delete all of these
191 with a single unchaining, rather than one at a time, but we need to keep
195 next
= NEXT_INSN (start
);
196 if (GET_CODE (start
) == NOTE
&& !can_delete_note_p (start
))
199 next
= delete_insn (start
);
207 /* Create a new basic block consisting of the instructions between HEAD and END
208 inclusive. This function is designed to allow fast BB construction - reuses
209 the note and basic block struct in BB_NOTE, if any and do not grow
210 BASIC_BLOCK chain and should be used directly only by CFG construction code.
211 END can be NULL in to create new empty basic block before HEAD. Both END
212 and HEAD can be NULL to create basic block at the end of INSN chain. */
215 create_basic_block_structure (index
, head
, end
, bb_note
)
217 rtx head
, end
, bb_note
;
222 && ! RTX_INTEGRATED_P (bb_note
)
223 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
226 /* If we found an existing note, thread it back onto the chain. */
230 if (GET_CODE (head
) == CODE_LABEL
)
234 after
= PREV_INSN (head
);
238 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
239 reorder_insns (bb_note
, bb_note
, after
);
243 /* Otherwise we must create a note and a basic block structure. */
249 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
250 else if (GET_CODE (head
) == CODE_LABEL
&& end
)
252 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
258 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
264 NOTE_BASIC_BLOCK (bb_note
) = bb
;
267 /* Always include the bb note in the block. */
268 if (NEXT_INSN (end
) == bb_note
)
274 BASIC_BLOCK (index
) = bb
;
275 if (basic_block_for_insn
)
276 update_bb_for_insn (bb
);
278 /* Tag the block so that we know it has been used when considering
279 other basic block notes. */
285 /* Create new basic block consisting of instructions in between HEAD and END
286 and place it to the BB chain at position INDEX. END can be NULL in to
287 create new empty basic block before HEAD. Both END and HEAD can be NULL to
288 create basic block at the end of INSN chain. */
291 create_basic_block (index
, head
, end
)
298 /* Place the new block just after the block being split. */
299 VARRAY_GROW (basic_block_info
, ++n_basic_blocks
);
301 /* Some parts of the compiler expect blocks to be number in
302 sequential order so insert the new block immediately after the
303 block being split.. */
304 for (i
= n_basic_blocks
- 1; i
> index
; --i
)
306 basic_block tmp
= BASIC_BLOCK (i
- 1);
308 BASIC_BLOCK (i
) = tmp
;
312 bb
= create_basic_block_structure (index
, head
, end
, NULL
);
317 /* Delete the insns in a (non-live) block. We physically delete every
318 non-deleted-note insn, and update the flow graph appropriately.
320 Return nonzero if we deleted an exception handler. */
322 /* ??? Preserving all such notes strikes me as wrong. It would be nice
323 to post-process the stream to remove empty blocks, loops, ranges, etc. */
326 flow_delete_block (b
)
329 int deleted_handler
= 0;
332 /* If the head of this block is a CODE_LABEL, then it might be the
333 label for an exception handler which can't be reached.
335 We need to remove the label from the exception_handler_label list
336 and remove the associated NOTE_INSN_EH_REGION_BEG and
337 NOTE_INSN_EH_REGION_END notes. */
341 never_reached_warning (insn
);
343 if (GET_CODE (insn
) == CODE_LABEL
)
344 maybe_remove_eh_handler (insn
);
346 /* Include any jump table following the basic block. */
348 if (GET_CODE (end
) == JUMP_INSN
349 && (tmp
= JUMP_LABEL (end
)) != NULL_RTX
350 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
351 && GET_CODE (tmp
) == JUMP_INSN
352 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
353 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
356 /* Include any barrier that may follow the basic block. */
357 tmp
= next_nonnote_insn (end
);
358 if (tmp
&& GET_CODE (tmp
) == BARRIER
)
361 /* Selectively delete the entire chain. */
363 delete_insn_chain (insn
, end
);
365 /* Remove the edges into and out of this block. Note that there may
366 indeed be edges in, if we are removing an unreachable loop. */
367 while (b
->pred
!= NULL
)
368 remove_edge (b
->pred
);
369 while (b
->succ
!= NULL
)
370 remove_edge (b
->succ
);
375 /* Remove the basic block from the array, and compact behind it. */
378 return deleted_handler
;
381 /* Records the basic block struct in BB_FOR_INSN, for every instruction
382 indexed by INSN_UID. MAX is the size of the array. */
385 compute_bb_for_insn (max
)
390 if (basic_block_for_insn
)
391 VARRAY_FREE (basic_block_for_insn
);
393 VARRAY_BB_INIT (basic_block_for_insn
, max
, "basic_block_for_insn");
395 for (i
= 0; i
< n_basic_blocks
; ++i
)
397 basic_block bb
= BASIC_BLOCK (i
);
401 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
403 if (INSN_UID (insn
) < max
)
404 VARRAY_BB (basic_block_for_insn
, INSN_UID (insn
)) = bb
;
412 /* Release the basic_block_for_insn array. */
417 if (basic_block_for_insn
)
418 VARRAY_FREE (basic_block_for_insn
);
420 basic_block_for_insn
= 0;
423 /* Update insns block within BB. */
426 update_bb_for_insn (bb
)
431 if (! basic_block_for_insn
)
434 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
436 set_block_for_insn (insn
, bb
);
442 /* Record INSN's block as BB. */
445 set_block_for_insn (insn
, bb
)
449 size_t uid
= INSN_UID (insn
);
451 if (uid
>= basic_block_for_insn
->num_elements
)
453 /* Add one-eighth the size so we don't keep calling xrealloc. */
454 size_t new_size
= uid
+ (uid
+ 7) / 8;
456 VARRAY_GROW (basic_block_for_insn
, new_size
);
459 VARRAY_BB (basic_block_for_insn
, uid
) = bb
;
462 /* Split a block BB after insn INSN creating a new fallthru edge.
463 Return the new edge. Note that to keep other parts of the compiler happy,
464 this function renumbers all the basic blocks so that the new
465 one has a number one greater than the block split. */
468 split_block (bb
, insn
)
476 /* There is no point splitting the block after its end. */
480 /* Create the new basic block. */
481 new_bb
= create_basic_block (bb
->index
+ 1, NEXT_INSN (insn
), bb
->end
);
482 new_bb
->count
= bb
->count
;
483 new_bb
->frequency
= bb
->frequency
;
484 new_bb
->loop_depth
= bb
->loop_depth
;
487 /* Redirect the outgoing edges. */
488 new_bb
->succ
= bb
->succ
;
490 for (e
= new_bb
->succ
; e
; e
= e
->succ_next
)
493 new_edge
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
495 if (bb
->global_live_at_start
)
497 new_bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
498 new_bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
499 COPY_REG_SET (new_bb
->global_live_at_end
, bb
->global_live_at_end
);
501 /* We now have to calculate which registers are live at the end
502 of the split basic block and at the start of the new basic
503 block. Start with those registers that are known to be live
504 at the end of the original basic block and get
505 propagate_block to determine which registers are live. */
506 COPY_REG_SET (new_bb
->global_live_at_start
, bb
->global_live_at_end
);
507 propagate_block (new_bb
, new_bb
->global_live_at_start
, NULL
, NULL
, 0);
508 COPY_REG_SET (bb
->global_live_at_end
,
509 new_bb
->global_live_at_start
);
515 /* Blocks A and B are to be merged into a single block A. The insns
516 are already contiguous, hence `nomove'. */
519 merge_blocks_nomove (a
, b
)
522 rtx b_head
= b
->head
, b_end
= b
->end
, a_end
= a
->end
;
523 rtx del_first
= NULL_RTX
, del_last
= NULL_RTX
;
527 /* If there was a CODE_LABEL beginning B, delete it. */
528 if (GET_CODE (b_head
) == CODE_LABEL
)
530 /* Detect basic blocks with nothing but a label. This can happen
531 in particular at the end of a function. */
535 del_first
= del_last
= b_head
;
536 b_head
= NEXT_INSN (b_head
);
539 /* Delete the basic block note and handle blocks containing just that
541 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
549 b_head
= NEXT_INSN (b_head
);
552 /* If there was a jump out of A, delete it. */
553 if (GET_CODE (a_end
) == JUMP_INSN
)
557 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
558 if (GET_CODE (prev
) != NOTE
559 || NOTE_LINE_NUMBER (prev
) == NOTE_INSN_BASIC_BLOCK
566 /* If this was a conditional jump, we need to also delete
567 the insn that set cc0. */
568 if (only_sets_cc0_p (prev
))
572 prev
= prev_nonnote_insn (prev
);
579 a_end
= PREV_INSN (del_first
);
581 else if (GET_CODE (NEXT_INSN (a_end
)) == BARRIER
)
582 del_first
= NEXT_INSN (a_end
);
584 /* Normally there should only be one successor of A and that is B, but
585 partway though the merge of blocks for conditional_execution we'll
586 be merging a TEST block with THEN and ELSE successors. Free the
587 whole lot of them and hope the caller knows what they're doing. */
589 remove_edge (a
->succ
);
591 /* Adjust the edges out of B for the new owner. */
592 for (e
= b
->succ
; e
; e
= e
->succ_next
)
596 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
597 b
->pred
= b
->succ
= NULL
;
598 a
->global_live_at_end
= b
->global_live_at_end
;
602 /* Delete everything marked above as well as crap that might be
603 hanging out between the two blocks. */
604 delete_insn_chain (del_first
, del_last
);
606 /* Reassociate the insns of B with A. */
609 if (basic_block_for_insn
)
613 for (x
= a_end
; x
!= b_end
; x
= NEXT_INSN (x
))
614 BLOCK_FOR_INSN (x
) = a
;
616 BLOCK_FOR_INSN (b_end
) = a
;
625 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
632 if (block
== EXIT_BLOCK_PTR
)
635 if (GET_CODE (block
->head
) != CODE_LABEL
)
637 block
->head
= emit_label_before (gen_label_rtx (), block
->head
);
638 if (basic_block_for_insn
)
639 set_block_for_insn (block
->head
, block
);
645 /* Attempt to perform edge redirection by replacing possibly complex jump
646 instruction by unconditional jump or removing jump completely. This can
647 apply only if all edges now point to the same block. The parameters and
648 return values are equivalent to redirect_edge_and_branch. */
651 try_redirect_by_replacing_jump (e
, target
)
655 basic_block src
= e
->src
;
656 rtx insn
= src
->end
, kill_from
;
661 /* Verify that all targets will be TARGET. */
662 for (tmp
= src
->succ
; tmp
; tmp
= tmp
->succ_next
)
663 if (tmp
->dest
!= target
&& tmp
!= e
)
666 if (tmp
|| !onlyjump_p (insn
))
669 /* Avoid removing branch with side effects. */
670 set
= single_set (insn
);
671 if (!set
|| side_effects_p (set
))
674 /* In case we zap a conditional jump, we'll need to kill
675 the cc0 setter too. */
678 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
)))
679 kill_from
= PREV_INSN (insn
);
682 /* See if we can create the fallthru edge. */
683 if (can_fallthru (src
, target
))
686 fprintf (rtl_dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
689 /* Selectively unlink whole insn chain. */
690 delete_insn_chain (kill_from
, PREV_INSN (target
->head
));
693 /* If this already is simplejump, redirect it. */
694 else if (simplejump_p (insn
))
696 if (e
->dest
== target
)
699 fprintf (rtl_dump_file
, "Redirecting jump %i from %i to %i.\n",
700 INSN_UID (insn
), e
->dest
->index
, target
->index
);
701 if (!redirect_jump (insn
, block_label (target
), 0))
703 if (target
== EXIT_BLOCK_PTR
)
709 /* Cannot do anything for target exit block. */
710 else if (target
== EXIT_BLOCK_PTR
)
713 /* Or replace possibly complicated jump insn by simple jump insn. */
716 rtx target_label
= block_label (target
);
719 emit_jump_insn_after (gen_jump (target_label
), insn
);
720 JUMP_LABEL (src
->end
) = target_label
;
721 LABEL_NUSES (target_label
)++;
723 fprintf (rtl_dump_file
, "Replacing insn %i by jump %i\n",
724 INSN_UID (insn
), INSN_UID (src
->end
));
726 delete_insn_chain (kill_from
, insn
);
728 barrier
= next_nonnote_insn (src
->end
);
729 if (!barrier
|| GET_CODE (barrier
) != BARRIER
)
730 emit_barrier_after (src
->end
);
733 /* Keep only one edge out and set proper flags. */
734 while (src
->succ
->succ_next
)
735 remove_edge (src
->succ
);
738 e
->flags
= EDGE_FALLTHRU
;
742 e
->probability
= REG_BR_PROB_BASE
;
743 e
->count
= src
->count
;
745 /* We don't want a block to end on a line-number note since that has
746 the potential of changing the code between -g and not -g. */
747 while (GET_CODE (e
->src
->end
) == NOTE
748 && NOTE_LINE_NUMBER (e
->src
->end
) >= 0)
749 delete_insn (e
->src
->end
);
751 if (e
->dest
!= target
)
752 redirect_edge_succ (e
, target
);
757 /* Return last loop_beg note appearing after INSN, before start of next
758 basic block. Return INSN if there are no such notes.
760 When emitting jump to redirect an fallthru edge, it should always appear
761 after the LOOP_BEG notes, as loop optimizer expect loop to either start by
762 fallthru edge or jump following the LOOP_BEG note jumping to the loop exit
766 last_loop_beg_note (insn
)
771 for (insn
= NEXT_INSN (insn
); insn
&& GET_CODE (insn
) == NOTE
772 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
;
773 insn
= NEXT_INSN (insn
))
774 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
780 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
781 expense of adding new instructions or reordering basic blocks.
783 Function can be also called with edge destination equivalent to the TARGET.
784 Then it should try the simplifications and do nothing if none is possible.
786 Return true if transformation succeeded. We still return false in case E
787 already destinated TARGET and we didn't managed to simplify instruction
791 redirect_edge_and_branch (e
, target
)
796 rtx old_label
= e
->dest
->head
;
797 basic_block src
= e
->src
;
800 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
803 if (try_redirect_by_replacing_jump (e
, target
))
806 /* Do this fast path late, as we want above code to simplify for cases
807 where called on single edge leaving basic block containing nontrivial
809 else if (e
->dest
== target
)
812 /* We can only redirect non-fallthru edges of jump insn. */
813 if (e
->flags
& EDGE_FALLTHRU
)
815 else if (GET_CODE (insn
) != JUMP_INSN
)
818 /* Recognize a tablejump and adjust all matching cases. */
819 if ((tmp
= JUMP_LABEL (insn
)) != NULL_RTX
820 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
821 && GET_CODE (tmp
) == JUMP_INSN
822 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
823 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
827 rtx new_label
= block_label (target
);
829 if (target
== EXIT_BLOCK_PTR
)
831 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
832 vec
= XVEC (PATTERN (tmp
), 0);
834 vec
= XVEC (PATTERN (tmp
), 1);
836 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
837 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
839 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
840 --LABEL_NUSES (old_label
);
841 ++LABEL_NUSES (new_label
);
844 /* Handle casesi dispatch insns */
845 if ((tmp
= single_set (insn
)) != NULL
846 && SET_DEST (tmp
) == pc_rtx
847 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
848 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
849 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
851 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (VOIDmode
,
853 --LABEL_NUSES (old_label
);
854 ++LABEL_NUSES (new_label
);
859 /* ?? We may play the games with moving the named labels from
860 one basic block to the other in case only one computed_jump is
862 if (computed_jump_p (insn
)
863 /* A return instruction can't be redirected. */
864 || returnjump_p (insn
))
867 /* If the insn doesn't go where we think, we're confused. */
868 if (JUMP_LABEL (insn
) != old_label
)
871 /* If the substitution doesn't succeed, die. This can happen
872 if the back end emitted unrecognizable instructions or if
873 target is exit block on some arches. */
874 if (!redirect_jump (insn
, block_label (target
), 0))
876 if (target
== EXIT_BLOCK_PTR
)
883 fprintf (rtl_dump_file
, "Edge %i->%i redirected to %i\n",
884 e
->src
->index
, e
->dest
->index
, target
->index
);
886 if (e
->dest
!= target
)
887 redirect_edge_succ_nodup (e
, target
);
892 /* Like force_nonfallthru below, but additionally performs redirection
893 Used by redirect_edge_and_branch_force. */
896 force_nonfallthru_and_redirect (e
, target
)
900 basic_block jump_block
, new_bb
= NULL
;
904 if (e
->flags
& EDGE_ABNORMAL
)
906 else if (!(e
->flags
& EDGE_FALLTHRU
))
908 else if (e
->src
->succ
->succ_next
)
910 /* Create the new structures. */
911 note
= last_loop_beg_note (e
->src
->end
);
913 = create_basic_block (e
->src
->index
+ 1, NEXT_INSN (note
), NULL
);
914 jump_block
->count
= e
->count
;
915 jump_block
->frequency
= EDGE_FREQUENCY (e
);
916 jump_block
->loop_depth
= target
->loop_depth
;
918 if (target
->global_live_at_start
)
920 jump_block
->global_live_at_start
921 = OBSTACK_ALLOC_REG_SET (&flow_obstack
);
922 jump_block
->global_live_at_end
923 = OBSTACK_ALLOC_REG_SET (&flow_obstack
);
924 COPY_REG_SET (jump_block
->global_live_at_start
,
925 target
->global_live_at_start
);
926 COPY_REG_SET (jump_block
->global_live_at_end
,
927 target
->global_live_at_start
);
931 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
932 new_edge
->probability
= e
->probability
;
933 new_edge
->count
= e
->count
;
935 /* Redirect old edge. */
936 redirect_edge_pred (e
, jump_block
);
937 e
->probability
= REG_BR_PROB_BASE
;
944 e
->flags
&= ~EDGE_FALLTHRU
;
945 if (target
== EXIT_BLOCK_PTR
)
948 emit_jump_insn_after (gen_return (), jump_block
->end
);
954 rtx label
= block_label (target
);
955 emit_jump_insn_after (gen_jump (label
), jump_block
->end
);
956 JUMP_LABEL (jump_block
->end
) = label
;
957 LABEL_NUSES (label
)++;
960 emit_barrier_after (jump_block
->end
);
961 redirect_edge_succ_nodup (e
, target
);
966 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
967 (and possibly create new basic block) to make edge non-fallthru.
968 Return newly created BB or NULL if none. */
971 force_nonfallthru (e
)
974 return force_nonfallthru_and_redirect (e
, e
->dest
);
977 /* Redirect edge even at the expense of creating new jump insn or
978 basic block. Return new basic block if created, NULL otherwise.
979 Abort if conversion is impossible. */
982 redirect_edge_and_branch_force (e
, target
)
986 if (redirect_edge_and_branch (e
, target
)
987 || e
->dest
== target
)
990 /* In case the edge redirection failed, try to force it to be non-fallthru
991 and redirect newly created simplejump. */
992 return force_nonfallthru_and_redirect (e
, target
);
995 /* The given edge should potentially be a fallthru edge. If that is in
996 fact true, delete the jump and barriers that are in the way. */
999 tidy_fallthru_edge (e
, b
, c
)
1005 /* ??? In a late-running flow pass, other folks may have deleted basic
1006 blocks by nopping out blocks, leaving multiple BARRIERs between here
1007 and the target label. They ought to be chastized and fixed.
1009 We can also wind up with a sequence of undeletable labels between
1010 one block and the next.
1012 So search through a sequence of barriers, labels, and notes for
1013 the head of block C and assert that we really do fall through. */
1015 if (next_real_insn (b
->end
) != next_real_insn (PREV_INSN (c
->head
)))
1018 /* Remove what will soon cease being the jump insn from the source block.
1019 If block B consisted only of this single jump, turn it into a deleted
1022 if (GET_CODE (q
) == JUMP_INSN
1024 && (any_uncondjump_p (q
)
1025 || (b
->succ
== e
&& e
->succ_next
== NULL
)))
1028 /* If this was a conditional jump, we need to also delete
1029 the insn that set cc0. */
1030 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1036 /* We don't want a block to end on a line-number note since that has
1037 the potential of changing the code between -g and not -g. */
1038 while (GET_CODE (q
) == NOTE
&& NOTE_LINE_NUMBER (q
) >= 0)
1042 /* Selectively unlink the sequence. */
1043 if (q
!= PREV_INSN (c
->head
))
1044 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (c
->head
));
1046 e
->flags
|= EDGE_FALLTHRU
;
1049 /* Fix up edges that now fall through, or rather should now fall through
1050 but previously required a jump around now deleted blocks. Simplify
1051 the search by only examining blocks numerically adjacent, since this
1052 is how find_basic_blocks created them. */
1055 tidy_fallthru_edges ()
1059 for (i
= 1; i
< n_basic_blocks
; i
++)
1061 basic_block b
= BASIC_BLOCK (i
- 1);
1062 basic_block c
= BASIC_BLOCK (i
);
1065 /* We care about simple conditional or unconditional jumps with
1068 If we had a conditional branch to the next instruction when
1069 find_basic_blocks was called, then there will only be one
1070 out edge for the block which ended with the conditional
1071 branch (since we do not create duplicate edges).
1073 Furthermore, the edge will be marked as a fallthru because we
1074 merge the flags for the duplicate edges. So we do not want to
1075 check that the edge is not a FALLTHRU edge. */
1077 if ((s
= b
->succ
) != NULL
1078 && ! (s
->flags
& EDGE_COMPLEX
)
1079 && s
->succ_next
== NULL
1081 /* If the jump insn has side effects, we can't tidy the edge. */
1082 && (GET_CODE (b
->end
) != JUMP_INSN
1083 || onlyjump_p (b
->end
)))
1084 tidy_fallthru_edge (s
, b
, c
);
1088 /* Helper function for split_edge. Return true in case edge BB2 to BB1
1089 is back edge of syntactic loop. */
1092 back_edge_of_syntactic_loop_p (bb1
, bb2
)
1093 basic_block bb1
, bb2
;
1098 if (bb1
->index
> bb2
->index
)
1100 else if (bb1
->index
== bb2
->index
)
1103 for (insn
= bb1
->end
; insn
!= bb2
->head
&& count
>= 0;
1104 insn
= NEXT_INSN (insn
))
1105 if (GET_CODE (insn
) == NOTE
)
1107 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
1109 else if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
)
1116 /* Split a (typically critical) edge. Return the new block.
1117 Abort on abnormal edges.
1119 ??? The code generally expects to be called on critical edges.
1120 The case of a block ending in an unconditional jump to a
1121 block with multiple predecessors is not handled optimally. */
1124 split_edge (edge_in
)
1131 /* Abnormal edges cannot be split. */
1132 if ((edge_in
->flags
& EDGE_ABNORMAL
) != 0)
1135 /* We are going to place the new block in front of edge destination.
1136 Avoid existence of fallthru predecessors. */
1137 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1141 for (e
= edge_in
->dest
->pred
; e
; e
= e
->pred_next
)
1142 if (e
->flags
& EDGE_FALLTHRU
)
1146 force_nonfallthru (e
);
1149 /* Create the basic block note.
1151 Where we place the note can have a noticeable impact on the generated
1152 code. Consider this cfg:
1162 If we need to insert an insn on the edge from block 0 to block 1,
1163 we want to ensure the instructions we insert are outside of any
1164 loop notes that physically sit between block 0 and block 1. Otherwise
1165 we confuse the loop optimizer into thinking the loop is a phony. */
1167 if (edge_in
->dest
!= EXIT_BLOCK_PTR
1168 && PREV_INSN (edge_in
->dest
->head
)
1169 && GET_CODE (PREV_INSN (edge_in
->dest
->head
)) == NOTE
1170 && (NOTE_LINE_NUMBER (PREV_INSN (edge_in
->dest
->head
))
1171 == NOTE_INSN_LOOP_BEG
)
1172 && !back_edge_of_syntactic_loop_p (edge_in
->dest
, edge_in
->src
))
1173 before
= PREV_INSN (edge_in
->dest
->head
);
1174 else if (edge_in
->dest
!= EXIT_BLOCK_PTR
)
1175 before
= edge_in
->dest
->head
;
1179 bb
= create_basic_block (edge_in
->dest
== EXIT_BLOCK_PTR
? n_basic_blocks
1180 : edge_in
->dest
->index
, before
, NULL
);
1181 bb
->count
= edge_in
->count
;
1182 bb
->frequency
= EDGE_FREQUENCY (edge_in
);
1184 /* ??? This info is likely going to be out of date very soon. */
1185 if (edge_in
->dest
->global_live_at_start
)
1187 bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1188 bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1189 COPY_REG_SET (bb
->global_live_at_start
,
1190 edge_in
->dest
->global_live_at_start
);
1191 COPY_REG_SET (bb
->global_live_at_end
,
1192 edge_in
->dest
->global_live_at_start
);
1195 edge_out
= make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1197 /* For non-fallthry edges, we must adjust the predecessor's
1198 jump instruction to target our new block. */
1199 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1201 if (!redirect_edge_and_branch (edge_in
, bb
))
1205 redirect_edge_succ (edge_in
, bb
);
1210 /* Queue instructions for insertion on an edge between two basic blocks.
1211 The new instructions and basic blocks (if any) will not appear in the
1212 CFG until commit_edge_insertions is called. */
1215 insert_insn_on_edge (pattern
, e
)
1219 /* We cannot insert instructions on an abnormal critical edge.
1220 It will be easier to find the culprit if we die now. */
1221 if ((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
1224 if (e
->insns
== NULL_RTX
)
1227 push_to_sequence (e
->insns
);
1229 emit_insn (pattern
);
1231 e
->insns
= get_insns ();
1235 /* Update the CFG for the instructions queued on edge E. */
1238 commit_one_edge_insertion (e
)
1241 rtx before
= NULL_RTX
, after
= NULL_RTX
, insns
, tmp
, last
;
1244 /* Pull the insns off the edge now since the edge might go away. */
1246 e
->insns
= NULL_RTX
;
1248 /* Figure out where to put these things. If the destination has
1249 one predecessor, insert there. Except for the exit block. */
1250 if (e
->dest
->pred
->pred_next
== NULL
1251 && e
->dest
!= EXIT_BLOCK_PTR
)
1255 /* Get the location correct wrt a code label, and "nice" wrt
1256 a basic block note, and before everything else. */
1258 if (GET_CODE (tmp
) == CODE_LABEL
)
1259 tmp
= NEXT_INSN (tmp
);
1260 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1261 tmp
= NEXT_INSN (tmp
);
1262 if (tmp
== bb
->head
)
1265 after
= PREV_INSN (tmp
);
1268 /* If the source has one successor and the edge is not abnormal,
1269 insert there. Except for the entry block. */
1270 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1271 && e
->src
->succ
->succ_next
== NULL
1272 && e
->src
!= ENTRY_BLOCK_PTR
)
1276 /* It is possible to have a non-simple jump here. Consider a target
1277 where some forms of unconditional jumps clobber a register. This
1278 happens on the fr30 for example.
1280 We know this block has a single successor, so we can just emit
1281 the queued insns before the jump. */
1282 if (GET_CODE (bb
->end
) == JUMP_INSN
)
1283 for (before
= bb
->end
;
1284 GET_CODE (PREV_INSN (before
)) == NOTE
1285 && NOTE_LINE_NUMBER (PREV_INSN (before
)) == NOTE_INSN_LOOP_BEG
;
1286 before
= PREV_INSN (before
))
1290 /* We'd better be fallthru, or we've lost track of what's what. */
1291 if ((e
->flags
& EDGE_FALLTHRU
) == 0)
1298 /* Otherwise we must split the edge. */
1301 bb
= split_edge (e
);
1305 /* Now that we've found the spot, do the insertion. */
1309 emit_insns_before (insns
, before
);
1310 last
= prev_nonnote_insn (before
);
1313 last
= emit_insns_after (insns
, after
);
1315 if (returnjump_p (last
))
1317 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1318 This is not currently a problem because this only happens
1319 for the (single) epilogue, which already has a fallthru edge
1323 if (e
->dest
!= EXIT_BLOCK_PTR
1324 || e
->succ_next
!= NULL
1325 || (e
->flags
& EDGE_FALLTHRU
) == 0)
1328 e
->flags
&= ~EDGE_FALLTHRU
;
1329 emit_barrier_after (last
);
1332 delete_insn (before
);
1334 else if (GET_CODE (last
) == JUMP_INSN
)
1337 find_sub_basic_blocks (bb
);
1340 /* Update the CFG for all queued instructions. */
1343 commit_edge_insertions ()
1348 #ifdef ENABLE_CHECKING
1349 verify_flow_info ();
1353 bb
= ENTRY_BLOCK_PTR
;
1358 for (e
= bb
->succ
; e
; e
= next
)
1360 next
= e
->succ_next
;
1362 commit_one_edge_insertion (e
);
1365 if (++i
>= n_basic_blocks
)
1367 bb
= BASIC_BLOCK (i
);
1371 /* Print out one basic block with live information at start and end. */
1382 fprintf (outf
, ";; Basic block %d, loop depth %d, count ",
1383 bb
->index
, bb
->loop_depth
);
1384 fprintf (outf
, HOST_WIDEST_INT_PRINT_DEC
, (HOST_WIDEST_INT
) bb
->count
);
1387 fputs (";; Predecessors: ", outf
);
1388 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1389 dump_edge_info (outf
, e
, 0);
1392 fputs (";; Registers live at start:", outf
);
1393 dump_regset (bb
->global_live_at_start
, outf
);
1396 for (insn
= bb
->head
, last
= NEXT_INSN (bb
->end
); insn
!= last
;
1397 insn
= NEXT_INSN (insn
))
1398 print_rtl_single (outf
, insn
);
1400 fputs (";; Registers live at end:", outf
);
1401 dump_regset (bb
->global_live_at_end
, outf
);
1404 fputs (";; Successors: ", outf
);
1405 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1406 dump_edge_info (outf
, e
, 1);
1414 dump_bb (bb
, stderr
);
1421 dump_bb (BASIC_BLOCK (n
), stderr
);
1424 /* Like print_rtl, but also print out live information for the start of each
1428 print_rtl_with_bb (outf
, rtx_first
)
1435 fprintf (outf
, "(nil)\n");
1439 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
1440 int max_uid
= get_max_uid ();
1442 = (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1444 = (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1445 enum bb_state
*in_bb_p
1446 = (enum bb_state
*) xcalloc (max_uid
, sizeof (enum bb_state
));
1448 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1450 basic_block bb
= BASIC_BLOCK (i
);
1453 start
[INSN_UID (bb
->head
)] = bb
;
1454 end
[INSN_UID (bb
->end
)] = bb
;
1455 for (x
= bb
->head
; x
!= NULL_RTX
; x
= NEXT_INSN (x
))
1457 enum bb_state state
= IN_MULTIPLE_BB
;
1459 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
1461 in_bb_p
[INSN_UID (x
)] = state
;
1468 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
1473 if ((bb
= start
[INSN_UID (tmp_rtx
)]) != NULL
)
1475 fprintf (outf
, ";; Start of basic block %d, registers live:",
1477 dump_regset (bb
->global_live_at_start
, outf
);
1481 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
1482 && GET_CODE (tmp_rtx
) != NOTE
1483 && GET_CODE (tmp_rtx
) != BARRIER
)
1484 fprintf (outf
, ";; Insn is not within a basic block\n");
1485 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
1486 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
1488 did_output
= print_rtl_single (outf
, tmp_rtx
);
1490 if ((bb
= end
[INSN_UID (tmp_rtx
)]) != NULL
)
1492 fprintf (outf
, ";; End of basic block %d, registers live:\n",
1494 dump_regset (bb
->global_live_at_end
, outf
);
1507 if (current_function_epilogue_delay_list
!= 0)
1509 fprintf (outf
, "\n;; Insns in epilogue delay list:\n\n");
1510 for (tmp_rtx
= current_function_epilogue_delay_list
; tmp_rtx
!= 0;
1511 tmp_rtx
= XEXP (tmp_rtx
, 1))
1512 print_rtl_single (outf
, XEXP (tmp_rtx
, 0));
1517 update_br_prob_note (bb
)
1521 if (GET_CODE (bb
->end
) != JUMP_INSN
)
1523 note
= find_reg_note (bb
->end
, REG_BR_PROB
, NULL_RTX
);
1524 if (!note
|| INTVAL (XEXP (note
, 0)) == BRANCH_EDGE (bb
)->probability
)
1526 XEXP (note
, 0) = GEN_INT (BRANCH_EDGE (bb
)->probability
);
1529 /* Verify the CFG consistency. This function check some CFG invariants and
1530 aborts when something is wrong. Hope that this function will help to
1531 convert many optimization passes to preserve CFG consistent.
1533 Currently it does following checks:
1535 - test head/end pointers
1536 - overlapping of basic blocks
1537 - edge list correctness
1538 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1539 - tails of basic blocks (ensure that boundary is necessary)
1540 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1541 and NOTE_INSN_BASIC_BLOCK
1542 - check that all insns are in the basic blocks
1543 (except the switch handling code, barriers and notes)
1544 - check that all returns are followed by barriers
1546 In future it can be extended check a lot of other stuff as well
1547 (reachability of basic blocks, life information, etc. etc.). */
1552 const int max_uid
= get_max_uid ();
1553 const rtx rtx_first
= get_insns ();
1554 rtx last_head
= get_last_insn ();
1555 basic_block
*bb_info
, *last_visited
;
1556 size_t *edge_checksum
;
1558 int i
, last_bb_num_seen
, num_bb_notes
, err
= 0;
1560 bb_info
= (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1561 last_visited
= (basic_block
*) xcalloc (n_basic_blocks
+ 2,
1562 sizeof (basic_block
));
1563 edge_checksum
= (size_t *) xcalloc (n_basic_blocks
+ 2, sizeof (size_t));
1565 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1567 basic_block bb
= BASIC_BLOCK (i
);
1568 rtx head
= bb
->head
;
1571 /* Verify the end of the basic block is in the INSN chain. */
1572 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1578 error ("end insn %d for block %d not found in the insn stream",
1579 INSN_UID (end
), bb
->index
);
1583 /* Work backwards from the end to the head of the basic block
1584 to verify the head is in the RTL chain. */
1585 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1587 /* While walking over the insn chain, verify insns appear
1588 in only one basic block and initialize the BB_INFO array
1589 used by other passes. */
1590 if (bb_info
[INSN_UID (x
)] != NULL
)
1592 error ("insn %d is in multiple basic blocks (%d and %d)",
1593 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
1597 bb_info
[INSN_UID (x
)] = bb
;
1604 error ("head insn %d for block %d not found in the insn stream",
1605 INSN_UID (head
), bb
->index
);
1612 /* Now check the basic blocks (boundaries etc.) */
1613 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1615 basic_block bb
= BASIC_BLOCK (i
);
1616 int has_fallthru
= 0;
1619 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1621 if (last_visited
[e
->dest
->index
+ 2] == bb
)
1623 error ("verify_flow_info: Duplicate edge %i->%i",
1624 e
->src
->index
, e
->dest
->index
);
1628 last_visited
[e
->dest
->index
+ 2] = bb
;
1630 if (e
->flags
& EDGE_FALLTHRU
)
1633 if ((e
->flags
& EDGE_FALLTHRU
)
1634 && e
->src
!= ENTRY_BLOCK_PTR
1635 && e
->dest
!= EXIT_BLOCK_PTR
)
1639 if (e
->src
->index
+ 1 != e
->dest
->index
)
1642 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
1643 e
->src
->index
, e
->dest
->index
);
1647 for (insn
= NEXT_INSN (e
->src
->end
); insn
!= e
->dest
->head
;
1648 insn
= NEXT_INSN (insn
))
1649 if (GET_CODE (insn
) == BARRIER
1650 #ifndef CASE_DROPS_THROUGH
1653 || (INSN_P (insn
) && ! JUMP_TABLE_DATA_P (insn
))
1657 error ("verify_flow_info: Incorrect fallthru %i->%i",
1658 e
->src
->index
, e
->dest
->index
);
1659 fatal_insn ("wrong insn in the fallthru edge", insn
);
1666 error ("verify_flow_info: Basic block %d succ edge is corrupted",
1668 fprintf (stderr
, "Predecessor: ");
1669 dump_edge_info (stderr
, e
, 0);
1670 fprintf (stderr
, "\nSuccessor: ");
1671 dump_edge_info (stderr
, e
, 1);
1672 fprintf (stderr
, "\n");
1676 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
1683 /* Ensure existence of barrier in BB with no fallthru edges. */
1684 for (insn
= bb
->end
; !insn
|| GET_CODE (insn
) != BARRIER
;
1685 insn
= NEXT_INSN (insn
))
1687 || (GET_CODE (insn
) == NOTE
1688 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BASIC_BLOCK
))
1690 error ("missing barrier after block %i", bb
->index
);
1696 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1700 error ("basic block %d pred edge is corrupted", bb
->index
);
1701 fputs ("Predecessor: ", stderr
);
1702 dump_edge_info (stderr
, e
, 0);
1703 fputs ("\nSuccessor: ", stderr
);
1704 dump_edge_info (stderr
, e
, 1);
1705 fputc ('\n', stderr
);
1708 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
1711 for (x
= bb
->head
; x
!= NEXT_INSN (bb
->end
); x
= NEXT_INSN (x
))
1712 if (basic_block_for_insn
&& BLOCK_FOR_INSN (x
) != bb
)
1715 if (! BLOCK_FOR_INSN (x
))
1717 ("insn %d inside basic block %d but block_for_insn is NULL",
1718 INSN_UID (x
), bb
->index
);
1721 ("insn %d inside basic block %d but block_for_insn is %i",
1722 INSN_UID (x
), bb
->index
, BLOCK_FOR_INSN (x
)->index
);
1727 /* OK pointers are correct. Now check the header of basic
1728 block. It ought to contain optional CODE_LABEL followed
1729 by NOTE_BASIC_BLOCK. */
1731 if (GET_CODE (x
) == CODE_LABEL
)
1735 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1743 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
1745 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1751 /* Do checks for empty blocks her. e */
1754 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
1756 if (NOTE_INSN_BASIC_BLOCK_P (x
))
1758 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
1759 INSN_UID (x
), bb
->index
);
1766 if (GET_CODE (x
) == JUMP_INSN
1767 || GET_CODE (x
) == CODE_LABEL
1768 || GET_CODE (x
) == BARRIER
)
1770 error ("in basic block %d:", bb
->index
);
1771 fatal_insn ("flow control insn inside a basic block", x
);
1776 /* Complete edge checksumming for ENTRY and EXIT. */
1780 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
1781 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
1783 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
1784 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
1787 for (i
= -2; i
< n_basic_blocks
; ++i
)
1788 if (edge_checksum
[i
+ 2])
1790 error ("basic block %i edge lists are corrupted", i
);
1794 last_bb_num_seen
= -1;
1796 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
1798 if (NOTE_INSN_BASIC_BLOCK_P (x
))
1800 basic_block bb
= NOTE_BASIC_BLOCK (x
);
1803 if (bb
->index
!= last_bb_num_seen
+ 1)
1804 internal_error ("basic blocks not numbered consecutively");
1806 last_bb_num_seen
= bb
->index
;
1809 if (!bb_info
[INSN_UID (x
)])
1811 switch (GET_CODE (x
))
1818 /* An addr_vec is placed outside any block block. */
1820 && GET_CODE (NEXT_INSN (x
)) == JUMP_INSN
1821 && (GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_DIFF_VEC
1822 || GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_VEC
))
1825 /* But in any case, non-deletable labels can appear anywhere. */
1829 fatal_insn ("insn outside basic block", x
);
1834 && GET_CODE (x
) == JUMP_INSN
1835 && returnjump_p (x
) && ! condjump_p (x
)
1836 && ! (NEXT_INSN (x
) && GET_CODE (NEXT_INSN (x
)) == BARRIER
))
1837 fatal_insn ("return not followed by barrier", x
);
1840 if (num_bb_notes
!= n_basic_blocks
)
1842 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
1843 num_bb_notes
, n_basic_blocks
);
1846 internal_error ("verify_flow_info failed");
1850 free (last_visited
);
1851 free (edge_checksum
);
1854 /* Assume that the preceding pass has possibly eliminated jump instructions
1855 or converted the unconditional jumps. Eliminate the edges from CFG.
1856 Return true if any edges are eliminated. */
1859 purge_dead_edges (bb
)
1863 rtx insn
= bb
->end
, note
;
1864 bool purged
= false;
1866 /* ??? This makes no sense since the later test includes more cases. */
1867 if (GET_CODE (insn
) == JUMP_INSN
&& !simplejump_p (insn
))
1870 if (GET_CODE (insn
) == JUMP_INSN
)
1875 /* We do care only about conditional jumps and simplejumps. */
1876 if (!any_condjump_p (insn
)
1877 && !returnjump_p (insn
)
1878 && !simplejump_p (insn
))
1881 for (e
= bb
->succ
; e
; e
= next
)
1883 next
= e
->succ_next
;
1885 /* Avoid abnormal flags to leak from computed jumps turned
1886 into simplejumps. */
1888 e
->flags
&= ~EDGE_ABNORMAL
;
1890 /* Check purposes we can have edge. */
1891 if ((e
->flags
& EDGE_FALLTHRU
)
1892 && any_condjump_p (insn
))
1894 else if (e
->dest
!= EXIT_BLOCK_PTR
1895 && e
->dest
->head
== JUMP_LABEL (insn
))
1897 else if (e
->dest
== EXIT_BLOCK_PTR
1898 && returnjump_p (insn
))
1905 if (!bb
->succ
|| !purged
)
1909 fprintf (rtl_dump_file
, "Purged edges from bb %i\n", bb
->index
);
1914 /* Redistribute probabilities. */
1915 if (!bb
->succ
->succ_next
)
1917 bb
->succ
->probability
= REG_BR_PROB_BASE
;
1918 bb
->succ
->count
= bb
->count
;
1922 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
1926 b
= BRANCH_EDGE (bb
);
1927 f
= FALLTHRU_EDGE (bb
);
1928 b
->probability
= INTVAL (XEXP (note
, 0));
1929 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
1930 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
1931 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
1937 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
1938 if (GET_CODE (insn
) == INSN
1939 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
1943 if (! may_trap_p (PATTERN (insn
))
1944 || ((eqnote
= find_reg_equal_equiv_note (insn
))
1945 && ! may_trap_p (XEXP (eqnote
, 0))))
1946 remove_note (insn
, note
);
1949 /* Cleanup abnormal edges caused by throwing insns that have been
1951 if (! can_throw_internal (bb
->end
))
1952 for (e
= bb
->succ
; e
; e
= next
)
1954 next
= e
->succ_next
;
1955 if (e
->flags
& EDGE_EH
)
1962 /* If we don't see a jump insn, we don't know exactly why the block would
1963 have been broken at this point. Look for a simple, non-fallthru edge,
1964 as these are only created by conditional branches. If we find such an
1965 edge we know that there used to be a jump here and can then safely
1966 remove all non-fallthru edges. */
1967 for (e
= bb
->succ
; e
&& (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
));
1974 for (e
= bb
->succ
; e
; e
= next
)
1976 next
= e
->succ_next
;
1977 if (!(e
->flags
& EDGE_FALLTHRU
))
1978 remove_edge (e
), purged
= true;
1981 if (!bb
->succ
|| bb
->succ
->succ_next
)
1984 bb
->succ
->probability
= REG_BR_PROB_BASE
;
1985 bb
->succ
->count
= bb
->count
;
1988 fprintf (rtl_dump_file
, "Purged non-fallthru edges from bb %i\n",
1993 /* Search all basic blocks for potentially dead edges and purge them. Return
1994 true if some edge has been eliminated. */
1997 purge_all_dead_edges (update_life_p
)
2000 int i
, purged
= false;
2005 blocks
= sbitmap_alloc (n_basic_blocks
);
2006 sbitmap_zero (blocks
);
2009 for (i
= 0; i
< n_basic_blocks
; i
++)
2011 bool purged_here
= purge_dead_edges (BASIC_BLOCK (i
));
2013 purged
|= purged_here
;
2014 if (purged_here
&& update_life_p
)
2015 SET_BIT (blocks
, i
);
2018 if (update_life_p
&& purged
)
2019 update_life_info (blocks
, UPDATE_LIFE_GLOBAL
,
2020 PROP_DEATH_NOTES
| PROP_SCAN_DEAD_CODE
2021 | PROP_KILL_DEAD_CODE
);
2024 sbitmap_free (blocks
);