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)
275 BASIC_BLOCK (index) = bb;
276 if (basic_block_for_insn)
277 update_bb_for_insn (bb);
279 /* Tag the block so that we know it has been used when considering
280 other basic block notes. */
286 /* Create new basic block consisting of instructions in between HEAD and END
287 and place it to the BB chain at position INDEX. END can be NULL in to
288 create new empty basic block before HEAD. Both END and HEAD can be NULL to
289 create basic block at the end of INSN chain. */
292 create_basic_block (index, head, end)
299 /* Place the new block just after the block being split. */
300 VARRAY_GROW (basic_block_info, ++n_basic_blocks);
302 /* Some parts of the compiler expect blocks to be number in
303 sequential order so insert the new block immediately after the
304 block being split.. */
305 for (i = n_basic_blocks - 1; i > index; --i)
307 basic_block tmp = BASIC_BLOCK (i - 1);
309 BASIC_BLOCK (i) = tmp;
313 bb = create_basic_block_structure (index, head, end, NULL);
318 /* Delete the insns in a (non-live) block. We physically delete every
319 non-deleted-note insn, and update the flow graph appropriately.
321 Return nonzero if we deleted an exception handler. */
323 /* ??? Preserving all such notes strikes me as wrong. It would be nice
324 to post-process the stream to remove empty blocks, loops, ranges, etc. */
327 flow_delete_block (b)
330 int deleted_handler = 0;
333 /* If the head of this block is a CODE_LABEL, then it might be the
334 label for an exception handler which can't be reached.
336 We need to remove the label from the exception_handler_label list
337 and remove the associated NOTE_INSN_EH_REGION_BEG and
338 NOTE_INSN_EH_REGION_END notes. */
342 never_reached_warning (insn, b->end);
344 if (GET_CODE (insn) == CODE_LABEL)
345 maybe_remove_eh_handler (insn);
347 /* Include any jump table following the basic block. */
349 if (GET_CODE (end) == JUMP_INSN
350 && (tmp = JUMP_LABEL (end)) != NULL_RTX
351 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
352 && GET_CODE (tmp) == JUMP_INSN
353 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
354 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
357 /* Include any barrier that may follow the basic block. */
358 tmp = next_nonnote_insn (end);
359 if (tmp && GET_CODE (tmp) == BARRIER)
362 /* Selectively delete the entire chain. */
364 delete_insn_chain (insn, end);
366 /* Remove the edges into and out of this block. Note that there may
367 indeed be edges in, if we are removing an unreachable loop. */
368 while (b->pred != NULL)
369 remove_edge (b->pred);
370 while (b->succ != NULL)
371 remove_edge (b->succ);
376 /* Remove the basic block from the array, and compact behind it. */
379 return deleted_handler;
382 /* Records the basic block struct in BB_FOR_INSN, for every instruction
383 indexed by INSN_UID. MAX is the size of the array. */
386 compute_bb_for_insn (max)
391 if (basic_block_for_insn)
392 VARRAY_FREE (basic_block_for_insn);
394 VARRAY_BB_INIT (basic_block_for_insn, max, "basic_block_for_insn");
396 for (i = 0; i < n_basic_blocks; ++i)
398 basic_block bb = BASIC_BLOCK (i);
402 for (insn = bb->head; ; insn = NEXT_INSN (insn))
404 if (INSN_UID (insn) < max)
405 VARRAY_BB (basic_block_for_insn, INSN_UID (insn)) = bb;
413 /* Release the basic_block_for_insn array. */
418 if (basic_block_for_insn)
419 VARRAY_FREE (basic_block_for_insn);
421 basic_block_for_insn = 0;
424 /* Update insns block within BB. */
427 update_bb_for_insn (bb)
432 if (! basic_block_for_insn)
435 for (insn = bb->head; ; insn = NEXT_INSN (insn))
437 set_block_for_insn (insn, bb);
443 /* Record INSN's block as BB. */
446 set_block_for_insn (insn, bb)
450 size_t uid = INSN_UID (insn);
452 if (uid >= basic_block_for_insn->num_elements)
454 /* Add one-eighth the size so we don't keep calling xrealloc. */
455 size_t new_size = uid + (uid + 7) / 8;
457 VARRAY_GROW (basic_block_for_insn, new_size);
460 VARRAY_BB (basic_block_for_insn, uid) = bb;
463 /* Split a block BB after insn INSN creating a new fallthru edge.
464 Return the new edge. Note that to keep other parts of the compiler happy,
465 this function renumbers all the basic blocks so that the new
466 one has a number one greater than the block split. */
469 split_block (bb, insn)
477 /* There is no point splitting the block after its end. */
481 /* Create the new basic block. */
482 new_bb = create_basic_block (bb->index + 1, NEXT_INSN (insn), bb->end);
483 new_bb->count = bb->count;
484 new_bb->frequency = bb->frequency;
485 new_bb->loop_depth = bb->loop_depth;
488 /* Redirect the outgoing edges. */
489 new_bb->succ = bb->succ;
491 for (e = new_bb->succ; e; e = e->succ_next)
494 new_edge = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
496 if (bb->global_live_at_start)
498 new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
499 new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
500 COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
502 /* We now have to calculate which registers are live at the end
503 of the split basic block and at the start of the new basic
504 block. Start with those registers that are known to be live
505 at the end of the original basic block and get
506 propagate_block to determine which registers are live. */
507 COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_end);
508 propagate_block (new_bb, new_bb->global_live_at_start, NULL, NULL, 0);
509 COPY_REG_SET (bb->global_live_at_end,
510 new_bb->global_live_at_start);
516 /* Blocks A and B are to be merged into a single block A. The insns
517 are already contiguous, hence `nomove'. */
520 merge_blocks_nomove (a, b)
523 rtx b_head = b->head, b_end = b->end, a_end = a->end;
524 rtx del_first = NULL_RTX, del_last = NULL_RTX;
528 /* If there was a CODE_LABEL beginning B, delete it. */
529 if (GET_CODE (b_head) == CODE_LABEL)
531 /* Detect basic blocks with nothing but a label. This can happen
532 in particular at the end of a function. */
536 del_first = del_last = b_head;
537 b_head = NEXT_INSN (b_head);
540 /* Delete the basic block note and handle blocks containing just that
542 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
550 b_head = NEXT_INSN (b_head);
553 /* If there was a jump out of A, delete it. */
554 if (GET_CODE (a_end) == JUMP_INSN)
558 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
559 if (GET_CODE (prev) != NOTE
560 || NOTE_LINE_NUMBER (prev) == NOTE_INSN_BASIC_BLOCK
567 /* If this was a conditional jump, we need to also delete
568 the insn that set cc0. */
569 if (only_sets_cc0_p (prev))
573 prev = prev_nonnote_insn (prev);
580 a_end = PREV_INSN (del_first);
582 else if (GET_CODE (NEXT_INSN (a_end)) == BARRIER)
583 del_first = NEXT_INSN (a_end);
585 /* Normally there should only be one successor of A and that is B, but
586 partway though the merge of blocks for conditional_execution we'll
587 be merging a TEST block with THEN and ELSE successors. Free the
588 whole lot of them and hope the caller knows what they're doing. */
590 remove_edge (a->succ);
592 /* Adjust the edges out of B for the new owner. */
593 for (e = b->succ; e; e = e->succ_next)
596 a->flags |= b->flags;
598 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
599 b->pred = b->succ = NULL;
600 a->global_live_at_end = b->global_live_at_end;
604 /* Delete everything marked above as well as crap that might be
605 hanging out between the two blocks. */
606 delete_insn_chain (del_first, del_last);
608 /* Reassociate the insns of B with A. */
611 if (basic_block_for_insn)
615 for (x = a_end; x != b_end; x = NEXT_INSN (x))
616 BLOCK_FOR_INSN (x) = a;
618 BLOCK_FOR_INSN (b_end) = a;
627 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
634 if (block == EXIT_BLOCK_PTR)
637 if (GET_CODE (block->head) != CODE_LABEL)
639 block->head = emit_label_before (gen_label_rtx (), block->head);
640 if (basic_block_for_insn)
641 set_block_for_insn (block->head, block);
647 /* Attempt to perform edge redirection by replacing possibly complex jump
648 instruction by unconditional jump or removing jump completely. This can
649 apply only if all edges now point to the same block. The parameters and
650 return values are equivalent to redirect_edge_and_branch. */
653 try_redirect_by_replacing_jump (e, target)
657 basic_block src = e->src;
658 rtx insn = src->end, kill_from;
663 /* Verify that all targets will be TARGET. */
664 for (tmp = src->succ; tmp; tmp = tmp->succ_next)
665 if (tmp->dest != target && tmp != e)
668 if (tmp || !onlyjump_p (insn))
671 /* Avoid removing branch with side effects. */
672 set = single_set (insn);
673 if (!set || side_effects_p (set))
676 /* In case we zap a conditional jump, we'll need to kill
677 the cc0 setter too. */
680 if (reg_mentioned_p (cc0_rtx, PATTERN (insn)))
681 kill_from = PREV_INSN (insn);
684 /* See if we can create the fallthru edge. */
685 if (can_fallthru (src, target))
688 fprintf (rtl_dump_file, "Removing jump %i.\n", INSN_UID (insn));
691 /* Selectively unlink whole insn chain. */
692 delete_insn_chain (kill_from, PREV_INSN (target->head));
695 /* If this already is simplejump, redirect it. */
696 else if (simplejump_p (insn))
698 if (e->dest == target)
701 fprintf (rtl_dump_file, "Redirecting jump %i from %i to %i.\n",
702 INSN_UID (insn), e->dest->index, target->index);
703 if (!redirect_jump (insn, block_label (target), 0))
705 if (target == EXIT_BLOCK_PTR)
711 /* Cannot do anything for target exit block. */
712 else if (target == EXIT_BLOCK_PTR)
715 /* Or replace possibly complicated jump insn by simple jump insn. */
718 rtx target_label = block_label (target);
721 emit_jump_insn_after (gen_jump (target_label), insn);
722 JUMP_LABEL (src->end) = target_label;
723 LABEL_NUSES (target_label)++;
725 fprintf (rtl_dump_file, "Replacing insn %i by jump %i\n",
726 INSN_UID (insn), INSN_UID (src->end));
729 delete_insn_chain (kill_from, insn);
731 /* Recognize a tablejump that we are converting to a
732 simple jump and remove its associated CODE_LABEL
733 and ADDR_VEC or ADDR_DIFF_VEC. */
734 if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
735 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
736 && GET_CODE (tmp) == JUMP_INSN
737 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
738 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
740 delete_insn_chain (JUMP_LABEL (insn), tmp);
743 barrier = next_nonnote_insn (src->end);
744 if (!barrier || GET_CODE (barrier) != BARRIER)
745 emit_barrier_after (src->end);
748 /* Keep only one edge out and set proper flags. */
749 while (src->succ->succ_next)
750 remove_edge (src->succ);
753 e->flags = EDGE_FALLTHRU;
757 e->probability = REG_BR_PROB_BASE;
758 e->count = src->count;
760 /* We don't want a block to end on a line-number note since that has
761 the potential of changing the code between -g and not -g. */
762 while (GET_CODE (e->src->end) == NOTE
763 && NOTE_LINE_NUMBER (e->src->end) >= 0)
764 delete_insn (e->src->end);
766 if (e->dest != target)
767 redirect_edge_succ (e, target);
772 /* Return last loop_beg note appearing after INSN, before start of next
773 basic block. Return INSN if there are no such notes.
775 When emitting jump to redirect an fallthru edge, it should always appear
776 after the LOOP_BEG notes, as loop optimizer expect loop to either start by
777 fallthru edge or jump following the LOOP_BEG note jumping to the loop exit
781 last_loop_beg_note (insn)
786 for (insn = NEXT_INSN (insn); insn && GET_CODE (insn) == NOTE
787 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK;
788 insn = NEXT_INSN (insn))
789 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
795 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
796 expense of adding new instructions or reordering basic blocks.
798 Function can be also called with edge destination equivalent to the TARGET.
799 Then it should try the simplifications and do nothing if none is possible.
801 Return true if transformation succeeded. We still return false in case E
802 already destinated TARGET and we didn't managed to simplify instruction
806 redirect_edge_and_branch (e, target)
811 rtx old_label = e->dest->head;
812 basic_block src = e->src;
815 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
818 if (try_redirect_by_replacing_jump (e, target))
821 /* Do this fast path late, as we want above code to simplify for cases
822 where called on single edge leaving basic block containing nontrivial
824 else if (e->dest == target)
827 /* We can only redirect non-fallthru edges of jump insn. */
828 if (e->flags & EDGE_FALLTHRU)
830 else if (GET_CODE (insn) != JUMP_INSN)
833 /* Recognize a tablejump and adjust all matching cases. */
834 if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
835 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
836 && GET_CODE (tmp) == JUMP_INSN
837 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
838 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
842 rtx new_label = block_label (target);
844 if (target == EXIT_BLOCK_PTR)
846 if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
847 vec = XVEC (PATTERN (tmp), 0);
849 vec = XVEC (PATTERN (tmp), 1);
851 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
852 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
854 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
855 --LABEL_NUSES (old_label);
856 ++LABEL_NUSES (new_label);
859 /* Handle casesi dispatch insns */
860 if ((tmp = single_set (insn)) != NULL
861 && SET_DEST (tmp) == pc_rtx
862 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
863 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
864 && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
866 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (VOIDmode,
868 --LABEL_NUSES (old_label);
869 ++LABEL_NUSES (new_label);
874 /* ?? We may play the games with moving the named labels from
875 one basic block to the other in case only one computed_jump is
877 if (computed_jump_p (insn)
878 /* A return instruction can't be redirected. */
879 || returnjump_p (insn))
882 /* If the insn doesn't go where we think, we're confused. */
883 if (JUMP_LABEL (insn) != old_label)
886 /* If the substitution doesn't succeed, die. This can happen
887 if the back end emitted unrecognizable instructions or if
888 target is exit block on some arches. */
889 if (!redirect_jump (insn, block_label (target), 0))
891 if (target == EXIT_BLOCK_PTR)
898 fprintf (rtl_dump_file, "Edge %i->%i redirected to %i\n",
899 e->src->index, e->dest->index, target->index);
901 if (e->dest != target)
902 redirect_edge_succ_nodup (e, target);
907 /* Like force_nonfallthru below, but additionally performs redirection
908 Used by redirect_edge_and_branch_force. */
911 force_nonfallthru_and_redirect (e, target)
915 basic_block jump_block, new_bb = NULL;
919 if (e->flags & EDGE_ABNORMAL)
921 else if (!(e->flags & EDGE_FALLTHRU))
923 else if (e->src == ENTRY_BLOCK_PTR)
925 /* We can't redirect the entry block. Create an empty block at the
926 start of the function which we use to add the new jump. */
928 basic_block bb = create_basic_block (0, e->dest->head, NULL);
930 /* Change the existing edge's source to be the new block, and add
931 a new edge from the entry block to the new block. */
933 for (pe1 = &ENTRY_BLOCK_PTR->succ; *pe1; pe1 = &(*pe1)->succ_next)
941 make_single_succ_edge (ENTRY_BLOCK_PTR, bb, EDGE_FALLTHRU);
944 if (e->src->succ->succ_next)
946 /* Create the new structures. */
947 note = last_loop_beg_note (e->src->end);
949 = create_basic_block (e->src->index + 1, NEXT_INSN (note), NULL);
950 jump_block->count = e->count;
951 jump_block->frequency = EDGE_FREQUENCY (e);
952 jump_block->loop_depth = target->loop_depth;
954 if (target->global_live_at_start)
956 jump_block->global_live_at_start
957 = OBSTACK_ALLOC_REG_SET (&flow_obstack);
958 jump_block->global_live_at_end
959 = OBSTACK_ALLOC_REG_SET (&flow_obstack);
960 COPY_REG_SET (jump_block->global_live_at_start,
961 target->global_live_at_start);
962 COPY_REG_SET (jump_block->global_live_at_end,
963 target->global_live_at_start);
967 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
968 new_edge->probability = e->probability;
969 new_edge->count = e->count;
971 /* Redirect old edge. */
972 redirect_edge_pred (e, jump_block);
973 e->probability = REG_BR_PROB_BASE;
980 e->flags &= ~EDGE_FALLTHRU;
981 if (target == EXIT_BLOCK_PTR)
984 emit_jump_insn_after (gen_return (), jump_block->end);
990 rtx label = block_label (target);
991 emit_jump_insn_after (gen_jump (label), jump_block->end);
992 JUMP_LABEL (jump_block->end) = label;
993 LABEL_NUSES (label)++;
996 emit_barrier_after (jump_block->end);
997 redirect_edge_succ_nodup (e, target);
1002 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1003 (and possibly create new basic block) to make edge non-fallthru.
1004 Return newly created BB or NULL if none. */
1007 force_nonfallthru (e)
1010 return force_nonfallthru_and_redirect (e, e->dest);
1013 /* Redirect edge even at the expense of creating new jump insn or
1014 basic block. Return new basic block if created, NULL otherwise.
1015 Abort if conversion is impossible. */
1018 redirect_edge_and_branch_force (e, target)
1022 if (redirect_edge_and_branch (e, target)
1023 || e->dest == target)
1026 /* In case the edge redirection failed, try to force it to be non-fallthru
1027 and redirect newly created simplejump. */
1028 return force_nonfallthru_and_redirect (e, target);
1031 /* The given edge should potentially be a fallthru edge. If that is in
1032 fact true, delete the jump and barriers that are in the way. */
1035 tidy_fallthru_edge (e, b, c)
1041 /* ??? In a late-running flow pass, other folks may have deleted basic
1042 blocks by nopping out blocks, leaving multiple BARRIERs between here
1043 and the target label. They ought to be chastized and fixed.
1045 We can also wind up with a sequence of undeletable labels between
1046 one block and the next.
1048 So search through a sequence of barriers, labels, and notes for
1049 the head of block C and assert that we really do fall through. */
1051 if (next_real_insn (b->end) != next_real_insn (PREV_INSN (c->head)))
1054 /* Remove what will soon cease being the jump insn from the source block.
1055 If block B consisted only of this single jump, turn it into a deleted
1058 if (GET_CODE (q) == JUMP_INSN
1060 && (any_uncondjump_p (q)
1061 || (b->succ == e && e->succ_next == NULL)))
1064 /* If this was a conditional jump, we need to also delete
1065 the insn that set cc0. */
1066 if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1072 /* We don't want a block to end on a line-number note since that has
1073 the potential of changing the code between -g and not -g. */
1074 while (GET_CODE (q) == NOTE && NOTE_LINE_NUMBER (q) >= 0)
1078 /* Selectively unlink the sequence. */
1079 if (q != PREV_INSN (c->head))
1080 delete_insn_chain (NEXT_INSN (q), PREV_INSN (c->head));
1082 e->flags |= EDGE_FALLTHRU;
1085 /* Fix up edges that now fall through, or rather should now fall through
1086 but previously required a jump around now deleted blocks. Simplify
1087 the search by only examining blocks numerically adjacent, since this
1088 is how find_basic_blocks created them. */
1091 tidy_fallthru_edges ()
1095 for (i = 1; i < n_basic_blocks; i++)
1097 basic_block b = BASIC_BLOCK (i - 1);
1098 basic_block c = BASIC_BLOCK (i);
1101 /* We care about simple conditional or unconditional jumps with
1104 If we had a conditional branch to the next instruction when
1105 find_basic_blocks was called, then there will only be one
1106 out edge for the block which ended with the conditional
1107 branch (since we do not create duplicate edges).
1109 Furthermore, the edge will be marked as a fallthru because we
1110 merge the flags for the duplicate edges. So we do not want to
1111 check that the edge is not a FALLTHRU edge. */
1113 if ((s = b->succ) != NULL
1114 && ! (s->flags & EDGE_COMPLEX)
1115 && s->succ_next == NULL
1117 /* If the jump insn has side effects, we can't tidy the edge. */
1118 && (GET_CODE (b->end) != JUMP_INSN
1119 || onlyjump_p (b->end)))
1120 tidy_fallthru_edge (s, b, c);
1124 /* Helper function for split_edge. Return true in case edge BB2 to BB1
1125 is back edge of syntactic loop. */
1128 back_edge_of_syntactic_loop_p (bb1, bb2)
1129 basic_block bb1, bb2;
1134 if (bb1->index > bb2->index)
1136 else if (bb1->index == bb2->index)
1139 for (insn = bb1->end; insn != bb2->head && count >= 0;
1140 insn = NEXT_INSN (insn))
1141 if (GET_CODE (insn) == NOTE)
1143 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1145 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1152 /* Split a (typically critical) edge. Return the new block.
1153 Abort on abnormal edges.
1155 ??? The code generally expects to be called on critical edges.
1156 The case of a block ending in an unconditional jump to a
1157 block with multiple predecessors is not handled optimally. */
1160 split_edge (edge_in)
1167 /* Abnormal edges cannot be split. */
1168 if ((edge_in->flags & EDGE_ABNORMAL) != 0)
1171 /* We are going to place the new block in front of edge destination.
1172 Avoid existence of fallthru predecessors. */
1173 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1177 for (e = edge_in->dest->pred; e; e = e->pred_next)
1178 if (e->flags & EDGE_FALLTHRU)
1182 force_nonfallthru (e);
1185 /* Create the basic block note.
1187 Where we place the note can have a noticeable impact on the generated
1188 code. Consider this cfg:
1198 If we need to insert an insn on the edge from block 0 to block 1,
1199 we want to ensure the instructions we insert are outside of any
1200 loop notes that physically sit between block 0 and block 1. Otherwise
1201 we confuse the loop optimizer into thinking the loop is a phony. */
1203 if (edge_in->dest != EXIT_BLOCK_PTR
1204 && PREV_INSN (edge_in->dest->head)
1205 && GET_CODE (PREV_INSN (edge_in->dest->head)) == NOTE
1206 && (NOTE_LINE_NUMBER (PREV_INSN (edge_in->dest->head))
1207 == NOTE_INSN_LOOP_BEG)
1208 && !back_edge_of_syntactic_loop_p (edge_in->dest, edge_in->src))
1209 before = PREV_INSN (edge_in->dest->head);
1210 else if (edge_in->dest != EXIT_BLOCK_PTR)
1211 before = edge_in->dest->head;
1215 bb = create_basic_block (edge_in->dest == EXIT_BLOCK_PTR ? n_basic_blocks
1216 : edge_in->dest->index, before, NULL);
1217 bb->count = edge_in->count;
1218 bb->frequency = EDGE_FREQUENCY (edge_in);
1220 /* ??? This info is likely going to be out of date very soon. */
1221 if (edge_in->dest->global_live_at_start)
1223 bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1224 bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1225 COPY_REG_SET (bb->global_live_at_start,
1226 edge_in->dest->global_live_at_start);
1227 COPY_REG_SET (bb->global_live_at_end,
1228 edge_in->dest->global_live_at_start);
1231 edge_out = make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1233 /* For non-fallthry edges, we must adjust the predecessor's
1234 jump instruction to target our new block. */
1235 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1237 if (!redirect_edge_and_branch (edge_in, bb))
1241 redirect_edge_succ (edge_in, bb);
1246 /* Queue instructions for insertion on an edge between two basic blocks.
1247 The new instructions and basic blocks (if any) will not appear in the
1248 CFG until commit_edge_insertions is called. */
1251 insert_insn_on_edge (pattern, e)
1255 /* We cannot insert instructions on an abnormal critical edge.
1256 It will be easier to find the culprit if we die now. */
1257 if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
1260 if (e->insns == NULL_RTX)
1263 push_to_sequence (e->insns);
1265 emit_insn (pattern);
1267 e->insns = get_insns ();
1271 /* Update the CFG for the instructions queued on edge E. */
1274 commit_one_edge_insertion (e)
1277 rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
1280 /* Pull the insns off the edge now since the edge might go away. */
1282 e->insns = NULL_RTX;
1284 /* Figure out where to put these things. If the destination has
1285 one predecessor, insert there. Except for the exit block. */
1286 if (e->dest->pred->pred_next == NULL
1287 && e->dest != EXIT_BLOCK_PTR)
1291 /* Get the location correct wrt a code label, and "nice" wrt
1292 a basic block note, and before everything else. */
1294 if (GET_CODE (tmp) == CODE_LABEL)
1295 tmp = NEXT_INSN (tmp);
1296 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1297 tmp = NEXT_INSN (tmp);
1298 if (tmp == bb->head)
1301 after = PREV_INSN (tmp);
1304 /* If the source has one successor and the edge is not abnormal,
1305 insert there. Except for the entry block. */
1306 else if ((e->flags & EDGE_ABNORMAL) == 0
1307 && e->src->succ->succ_next == NULL
1308 && e->src != ENTRY_BLOCK_PTR)
1312 /* It is possible to have a non-simple jump here. Consider a target
1313 where some forms of unconditional jumps clobber a register. This
1314 happens on the fr30 for example.
1316 We know this block has a single successor, so we can just emit
1317 the queued insns before the jump. */
1318 if (GET_CODE (bb->end) == JUMP_INSN)
1319 for (before = bb->end;
1320 GET_CODE (PREV_INSN (before)) == NOTE
1321 && NOTE_LINE_NUMBER (PREV_INSN (before)) == NOTE_INSN_LOOP_BEG;
1322 before = PREV_INSN (before))
1326 /* We'd better be fallthru, or we've lost track of what's what. */
1327 if ((e->flags & EDGE_FALLTHRU) == 0)
1334 /* Otherwise we must split the edge. */
1337 bb = split_edge (e);
1341 /* Now that we've found the spot, do the insertion. */
1345 emit_insns_before (insns, before);
1346 last = prev_nonnote_insn (before);
1349 last = emit_insns_after (insns, after);
1351 if (returnjump_p (last))
1353 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1354 This is not currently a problem because this only happens
1355 for the (single) epilogue, which already has a fallthru edge
1359 if (e->dest != EXIT_BLOCK_PTR
1360 || e->succ_next != NULL
1361 || (e->flags & EDGE_FALLTHRU) == 0)
1364 e->flags &= ~EDGE_FALLTHRU;
1365 emit_barrier_after (last);
1368 delete_insn (before);
1370 else if (GET_CODE (last) == JUMP_INSN)
1373 find_sub_basic_blocks (bb);
1376 /* Update the CFG for all queued instructions. */
1379 commit_edge_insertions ()
1384 #ifdef ENABLE_CHECKING
1385 verify_flow_info ();
1389 bb = ENTRY_BLOCK_PTR;
1394 for (e = bb->succ; e; e = next)
1396 next = e->succ_next;
1398 commit_one_edge_insertion (e);
1401 if (++i >= n_basic_blocks)
1403 bb = BASIC_BLOCK (i);
1407 /* Print out one basic block with live information at start and end. */
1418 fprintf (outf, ";; Basic block %d, loop depth %d, count ",
1419 bb->index, bb->loop_depth);
1420 fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
1423 fputs (";; Predecessors: ", outf);
1424 for (e = bb->pred; e; e = e->pred_next)
1425 dump_edge_info (outf, e, 0);
1428 fputs (";; Registers live at start:", outf);
1429 dump_regset (bb->global_live_at_start, outf);
1432 for (insn = bb->head, last = NEXT_INSN (bb->end); insn != last;
1433 insn = NEXT_INSN (insn))
1434 print_rtl_single (outf, insn);
1436 fputs (";; Registers live at end:", outf);
1437 dump_regset (bb->global_live_at_end, outf);
1440 fputs (";; Successors: ", outf);
1441 for (e = bb->succ; e; e = e->succ_next)
1442 dump_edge_info (outf, e, 1);
1450 dump_bb (bb, stderr);
1457 dump_bb (BASIC_BLOCK (n), stderr);
1460 /* Like print_rtl, but also print out live information for the start of each
1464 print_rtl_with_bb (outf, rtx_first)
1471 fprintf (outf, "(nil)\n");
1475 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
1476 int max_uid = get_max_uid ();
1478 = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1480 = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1481 enum bb_state *in_bb_p
1482 = (enum bb_state *) xcalloc (max_uid, sizeof (enum bb_state));
1484 for (i = n_basic_blocks - 1; i >= 0; i--)
1486 basic_block bb = BASIC_BLOCK (i);
1489 start[INSN_UID (bb->head)] = bb;
1490 end[INSN_UID (bb->end)] = bb;
1491 for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x))
1493 enum bb_state state = IN_MULTIPLE_BB;
1495 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
1497 in_bb_p[INSN_UID (x)] = state;
1504 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
1509 if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
1511 fprintf (outf, ";; Start of basic block %d, registers live:",
1513 dump_regset (bb->global_live_at_start, outf);
1517 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
1518 && GET_CODE (tmp_rtx) != NOTE
1519 && GET_CODE (tmp_rtx) != BARRIER)
1520 fprintf (outf, ";; Insn is not within a basic block\n");
1521 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
1522 fprintf (outf, ";; Insn is in multiple basic blocks\n");
1524 did_output = print_rtl_single (outf, tmp_rtx);
1526 if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
1528 fprintf (outf, ";; End of basic block %d, registers live:\n",
1530 dump_regset (bb->global_live_at_end, outf);
1543 if (current_function_epilogue_delay_list != 0)
1545 fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
1546 for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0;
1547 tmp_rtx = XEXP (tmp_rtx, 1))
1548 print_rtl_single (outf, XEXP (tmp_rtx, 0));
1553 update_br_prob_note (bb)
1557 if (GET_CODE (bb->end) != JUMP_INSN)
1559 note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX);
1560 if (!note || INTVAL (XEXP (note, 0)) == BRANCH_EDGE (bb)->probability)
1562 XEXP (note, 0) = GEN_INT (BRANCH_EDGE (bb)->probability);
1565 /* Verify the CFG consistency. This function check some CFG invariants and
1566 aborts when something is wrong. Hope that this function will help to
1567 convert many optimization passes to preserve CFG consistent.
1569 Currently it does following checks:
1571 - test head/end pointers
1572 - overlapping of basic blocks
1573 - edge list correctness
1574 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1575 - tails of basic blocks (ensure that boundary is necessary)
1576 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1577 and NOTE_INSN_BASIC_BLOCK
1578 - check that all insns are in the basic blocks
1579 (except the switch handling code, barriers and notes)
1580 - check that all returns are followed by barriers
1582 In future it can be extended check a lot of other stuff as well
1583 (reachability of basic blocks, life information, etc. etc.). */
1588 const int max_uid = get_max_uid ();
1589 const rtx rtx_first = get_insns ();
1590 rtx last_head = get_last_insn ();
1591 basic_block *bb_info, *last_visited;
1592 size_t *edge_checksum;
1594 int i, last_bb_num_seen, num_bb_notes, err = 0;
1596 bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1597 last_visited = (basic_block *) xcalloc (n_basic_blocks + 2,
1598 sizeof (basic_block));
1599 edge_checksum = (size_t *) xcalloc (n_basic_blocks + 2, sizeof (size_t));
1601 for (i = n_basic_blocks - 1; i >= 0; i--)
1603 basic_block bb = BASIC_BLOCK (i);
1604 rtx head = bb->head;
1607 /* Verify the end of the basic block is in the INSN chain. */
1608 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
1614 error ("end insn %d for block %d not found in the insn stream",
1615 INSN_UID (end), bb->index);
1619 /* Work backwards from the end to the head of the basic block
1620 to verify the head is in the RTL chain. */
1621 for (; x != NULL_RTX; x = PREV_INSN (x))
1623 /* While walking over the insn chain, verify insns appear
1624 in only one basic block and initialize the BB_INFO array
1625 used by other passes. */
1626 if (bb_info[INSN_UID (x)] != NULL)
1628 error ("insn %d is in multiple basic blocks (%d and %d)",
1629 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
1633 bb_info[INSN_UID (x)] = bb;
1640 error ("head insn %d for block %d not found in the insn stream",
1641 INSN_UID (head), bb->index);
1648 /* Now check the basic blocks (boundaries etc.) */
1649 for (i = n_basic_blocks - 1; i >= 0; i--)
1651 basic_block bb = BASIC_BLOCK (i);
1652 int has_fallthru = 0;
1656 if (INSN_P (bb->end)
1657 && (note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX)))
1659 if (!any_condjump_p (bb->end))
1661 error ("verify_flow_info: REG_BR_PROB on non-condjump",
1665 if (INTVAL (XEXP (note, 0)) != BRANCH_EDGE (bb)->probability)
1667 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
1668 INTVAL (XEXP (note, 0)), BRANCH_EDGE (bb)->probability);
1674 error ("verify_flow_info: Wrong count of block %i %i",
1675 bb->index, (int)bb->count);
1678 if (bb->frequency < 0)
1680 error ("verify_flow_info: Wrong frequency of block %i %i",
1681 bb->index, bb->frequency);
1684 for (e = bb->succ; e; e = e->succ_next)
1686 if (last_visited [e->dest->index + 2] == bb)
1688 error ("verify_flow_info: Duplicate edge %i->%i",
1689 e->src->index, e->dest->index);
1692 if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
1694 error ("verify_flow_info: Wrong probability of edge %i->%i %i",
1695 e->src->index, e->dest->index, e->probability);
1700 error ("verify_flow_info: Wrong count of edge %i->%i %i",
1701 e->src->index, e->dest->index, (int)e->count);
1705 last_visited [e->dest->index + 2] = bb;
1707 if (e->flags & EDGE_FALLTHRU)
1710 if ((e->flags & EDGE_FALLTHRU)
1711 && e->src != ENTRY_BLOCK_PTR
1712 && e->dest != EXIT_BLOCK_PTR)
1716 if (e->src->index + 1 != e->dest->index)
1719 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
1720 e->src->index, e->dest->index);
1724 for (insn = NEXT_INSN (e->src->end); insn != e->dest->head;
1725 insn = NEXT_INSN (insn))
1726 if (GET_CODE (insn) == BARRIER
1727 #ifndef CASE_DROPS_THROUGH
1730 || (INSN_P (insn) && ! JUMP_TABLE_DATA_P (insn))
1734 error ("verify_flow_info: Incorrect fallthru %i->%i",
1735 e->src->index, e->dest->index);
1736 fatal_insn ("wrong insn in the fallthru edge", insn);
1743 error ("verify_flow_info: Basic block %d succ edge is corrupted",
1745 fprintf (stderr, "Predecessor: ");
1746 dump_edge_info (stderr, e, 0);
1747 fprintf (stderr, "\nSuccessor: ");
1748 dump_edge_info (stderr, e, 1);
1749 fprintf (stderr, "\n");
1753 edge_checksum[e->dest->index + 2] += (size_t) e;
1760 /* Ensure existence of barrier in BB with no fallthru edges. */
1761 for (insn = bb->end; !insn || GET_CODE (insn) != BARRIER;
1762 insn = NEXT_INSN (insn))
1764 || (GET_CODE (insn) == NOTE
1765 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK))
1767 error ("missing barrier after block %i", bb->index);
1773 for (e = bb->pred; e; e = e->pred_next)
1777 error ("basic block %d pred edge is corrupted", bb->index);
1778 fputs ("Predecessor: ", stderr);
1779 dump_edge_info (stderr, e, 0);
1780 fputs ("\nSuccessor: ", stderr);
1781 dump_edge_info (stderr, e, 1);
1782 fputc ('\n', stderr);
1785 edge_checksum[e->dest->index + 2] -= (size_t) e;
1788 for (x = bb->head; x != NEXT_INSN (bb->end); x = NEXT_INSN (x))
1789 if (basic_block_for_insn && BLOCK_FOR_INSN (x) != bb)
1792 if (! BLOCK_FOR_INSN (x))
1794 ("insn %d inside basic block %d but block_for_insn is NULL",
1795 INSN_UID (x), bb->index);
1798 ("insn %d inside basic block %d but block_for_insn is %i",
1799 INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index);
1804 /* OK pointers are correct. Now check the header of basic
1805 block. It ought to contain optional CODE_LABEL followed
1806 by NOTE_BASIC_BLOCK. */
1808 if (GET_CODE (x) == CODE_LABEL)
1812 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1820 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
1822 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1828 /* Do checks for empty blocks her. e */
1831 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
1833 if (NOTE_INSN_BASIC_BLOCK_P (x))
1835 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
1836 INSN_UID (x), bb->index);
1843 if (GET_CODE (x) == JUMP_INSN
1844 || GET_CODE (x) == CODE_LABEL
1845 || GET_CODE (x) == BARRIER)
1847 error ("in basic block %d:", bb->index);
1848 fatal_insn ("flow control insn inside a basic block", x);
1853 /* Complete edge checksumming for ENTRY and EXIT. */
1857 for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
1858 edge_checksum[e->dest->index + 2] += (size_t) e;
1860 for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
1861 edge_checksum[e->dest->index + 2] -= (size_t) e;
1864 for (i = -2; i < n_basic_blocks; ++i)
1865 if (edge_checksum[i + 2])
1867 error ("basic block %i edge lists are corrupted", i);
1871 last_bb_num_seen = -1;
1873 for (x = rtx_first; x; x = NEXT_INSN (x))
1875 if (NOTE_INSN_BASIC_BLOCK_P (x))
1877 basic_block bb = NOTE_BASIC_BLOCK (x);
1880 if (bb->index != last_bb_num_seen + 1)
1881 internal_error ("basic blocks not numbered consecutively");
1883 last_bb_num_seen = bb->index;
1886 if (!bb_info[INSN_UID (x)])
1888 switch (GET_CODE (x))
1895 /* An addr_vec is placed outside any block block. */
1897 && GET_CODE (NEXT_INSN (x)) == JUMP_INSN
1898 && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
1899 || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
1902 /* But in any case, non-deletable labels can appear anywhere. */
1906 fatal_insn ("insn outside basic block", x);
1911 && GET_CODE (x) == JUMP_INSN
1912 && returnjump_p (x) && ! condjump_p (x)
1913 && ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER))
1914 fatal_insn ("return not followed by barrier", x);
1917 if (num_bb_notes != n_basic_blocks)
1919 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
1920 num_bb_notes, n_basic_blocks);
1923 internal_error ("verify_flow_info failed");
1927 free (last_visited);
1928 free (edge_checksum);
1931 /* Assume that the preceding pass has possibly eliminated jump instructions
1932 or converted the unconditional jumps. Eliminate the edges from CFG.
1933 Return true if any edges are eliminated. */
1936 purge_dead_edges (bb)
1940 rtx insn = bb->end, note;
1941 bool purged = false;
1943 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
1944 if (GET_CODE (insn) == INSN
1945 && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
1949 if (! may_trap_p (PATTERN (insn))
1950 || ((eqnote = find_reg_equal_equiv_note (insn))
1951 && ! may_trap_p (XEXP (eqnote, 0))))
1952 remove_note (insn, note);
1955 /* Cleanup abnormal edges caused by throwing insns that have been
1957 if (! can_throw_internal (bb->end))
1958 for (e = bb->succ; e; e = next)
1960 next = e->succ_next;
1961 if (e->flags & EDGE_EH)
1968 if (GET_CODE (insn) == JUMP_INSN)
1973 /* We do care only about conditional jumps and simplejumps. */
1974 if (!any_condjump_p (insn)
1975 && !returnjump_p (insn)
1976 && !simplejump_p (insn))
1979 /* Branch probability/prediction notes are defined only for
1980 condjumps. We've possibly turned condjump into simplejump. */
1981 if (simplejump_p (insn))
1983 note = find_reg_note (insn, REG_BR_PROB, NULL);
1985 remove_note (insn, note);
1986 while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
1987 remove_note (insn, note);
1990 for (e = bb->succ; e; e = next)
1992 next = e->succ_next;
1994 /* Avoid abnormal flags to leak from computed jumps turned
1995 into simplejumps. */
1997 e->flags &= ~EDGE_ABNORMAL;
1999 /* Check purposes we can have edge. */
2000 if ((e->flags & EDGE_FALLTHRU)
2001 && any_condjump_p (insn))
2003 else if (e->dest != EXIT_BLOCK_PTR
2004 && e->dest->head == JUMP_LABEL (insn))
2006 else if (e->dest == EXIT_BLOCK_PTR
2007 && returnjump_p (insn))
2014 if (!bb->succ || !purged)
2018 fprintf (rtl_dump_file, "Purged edges from bb %i\n", bb->index);
2023 /* Redistribute probabilities. */
2024 if (!bb->succ->succ_next)
2026 bb->succ->probability = REG_BR_PROB_BASE;
2027 bb->succ->count = bb->count;
2031 note = find_reg_note (insn, REG_BR_PROB, NULL);
2035 b = BRANCH_EDGE (bb);
2036 f = FALLTHRU_EDGE (bb);
2037 b->probability = INTVAL (XEXP (note, 0));
2038 f->probability = REG_BR_PROB_BASE - b->probability;
2039 b->count = bb->count * b->probability / REG_BR_PROB_BASE;
2040 f->count = bb->count * f->probability / REG_BR_PROB_BASE;
2046 /* If we don't see a jump insn, we don't know exactly why the block would
2047 have been broken at this point. Look for a simple, non-fallthru edge,
2048 as these are only created by conditional branches. If we find such an
2049 edge we know that there used to be a jump here and can then safely
2050 remove all non-fallthru edges. */
2051 for (e = bb->succ; e && (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU));
2058 for (e = bb->succ; e; e = next)
2060 next = e->succ_next;
2061 if (!(e->flags & EDGE_FALLTHRU))
2062 remove_edge (e), purged = true;
2065 if (!bb->succ || bb->succ->succ_next)
2068 bb->succ->probability = REG_BR_PROB_BASE;
2069 bb->succ->count = bb->count;
2072 fprintf (rtl_dump_file, "Purged non-fallthru edges from bb %i\n",
2077 /* Search all basic blocks for potentially dead edges and purge them. Return
2078 true if some edge has been eliminated. */
2081 purge_all_dead_edges (update_life_p)
2084 int i, purged = false;
2089 blocks = sbitmap_alloc (n_basic_blocks);
2090 sbitmap_zero (blocks);
2093 for (i = 0; i < n_basic_blocks; i++)
2095 bool purged_here = purge_dead_edges (BASIC_BLOCK (i));
2097 purged |= purged_here;
2098 if (purged_here && update_life_p)
2099 SET_BIT (blocks, i);
2102 if (update_life_p && purged)
2103 update_life_info (blocks, UPDATE_LIFE_GLOBAL,
2104 PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
2105 | PROP_KILL_DEAD_CODE);
2108 sbitmap_free (blocks);