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, b->end);
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));
727 delete_insn_chain (kill_from, insn);
729 /* Recognize a tablejump that we are converting to a
730 simple jump and remove its associated CODE_LABEL
731 and ADDR_VEC or ADDR_DIFF_VEC. */
732 if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
733 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
734 && GET_CODE (tmp) == JUMP_INSN
735 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
736 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
738 delete_insn_chain (JUMP_LABEL (insn), tmp);
741 barrier = next_nonnote_insn (src->end);
742 if (!barrier || GET_CODE (barrier) != BARRIER)
743 emit_barrier_after (src->end);
746 /* Keep only one edge out and set proper flags. */
747 while (src->succ->succ_next)
748 remove_edge (src->succ);
751 e->flags = EDGE_FALLTHRU;
755 e->probability = REG_BR_PROB_BASE;
756 e->count = src->count;
758 /* We don't want a block to end on a line-number note since that has
759 the potential of changing the code between -g and not -g. */
760 while (GET_CODE (e->src->end) == NOTE
761 && NOTE_LINE_NUMBER (e->src->end) >= 0)
762 delete_insn (e->src->end);
764 if (e->dest != target)
765 redirect_edge_succ (e, target);
770 /* Return last loop_beg note appearing after INSN, before start of next
771 basic block. Return INSN if there are no such notes.
773 When emitting jump to redirect an fallthru edge, it should always appear
774 after the LOOP_BEG notes, as loop optimizer expect loop to either start by
775 fallthru edge or jump following the LOOP_BEG note jumping to the loop exit
779 last_loop_beg_note (insn)
784 for (insn = NEXT_INSN (insn); insn && GET_CODE (insn) == NOTE
785 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK;
786 insn = NEXT_INSN (insn))
787 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
793 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
794 expense of adding new instructions or reordering basic blocks.
796 Function can be also called with edge destination equivalent to the TARGET.
797 Then it should try the simplifications and do nothing if none is possible.
799 Return true if transformation succeeded. We still return false in case E
800 already destinated TARGET and we didn't managed to simplify instruction
804 redirect_edge_and_branch (e, target)
809 rtx old_label = e->dest->head;
810 basic_block src = e->src;
813 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
816 if (try_redirect_by_replacing_jump (e, target))
819 /* Do this fast path late, as we want above code to simplify for cases
820 where called on single edge leaving basic block containing nontrivial
822 else if (e->dest == target)
825 /* We can only redirect non-fallthru edges of jump insn. */
826 if (e->flags & EDGE_FALLTHRU)
828 else if (GET_CODE (insn) != JUMP_INSN)
831 /* Recognize a tablejump and adjust all matching cases. */
832 if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
833 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
834 && GET_CODE (tmp) == JUMP_INSN
835 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
836 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
840 rtx new_label = block_label (target);
842 if (target == EXIT_BLOCK_PTR)
844 if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
845 vec = XVEC (PATTERN (tmp), 0);
847 vec = XVEC (PATTERN (tmp), 1);
849 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
850 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
852 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
853 --LABEL_NUSES (old_label);
854 ++LABEL_NUSES (new_label);
857 /* Handle casesi dispatch insns */
858 if ((tmp = single_set (insn)) != NULL
859 && SET_DEST (tmp) == pc_rtx
860 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
861 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
862 && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
864 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (VOIDmode,
866 --LABEL_NUSES (old_label);
867 ++LABEL_NUSES (new_label);
872 /* ?? We may play the games with moving the named labels from
873 one basic block to the other in case only one computed_jump is
875 if (computed_jump_p (insn)
876 /* A return instruction can't be redirected. */
877 || returnjump_p (insn))
880 /* If the insn doesn't go where we think, we're confused. */
881 if (JUMP_LABEL (insn) != old_label)
884 /* If the substitution doesn't succeed, die. This can happen
885 if the back end emitted unrecognizable instructions or if
886 target is exit block on some arches. */
887 if (!redirect_jump (insn, block_label (target), 0))
889 if (target == EXIT_BLOCK_PTR)
896 fprintf (rtl_dump_file, "Edge %i->%i redirected to %i\n",
897 e->src->index, e->dest->index, target->index);
899 if (e->dest != target)
900 redirect_edge_succ_nodup (e, target);
905 /* Like force_nonfallthru below, but additionally performs redirection
906 Used by redirect_edge_and_branch_force. */
909 force_nonfallthru_and_redirect (e, target)
913 basic_block jump_block, new_bb = NULL;
917 if (e->flags & EDGE_ABNORMAL)
919 else if (!(e->flags & EDGE_FALLTHRU))
921 else if (e->src == ENTRY_BLOCK_PTR)
923 /* We can't redirect the entry block. Create an empty block at the
924 start of the function which we use to add the new jump. */
926 basic_block bb = create_basic_block (0, e->dest->head, NULL);
928 /* Change the existing edge's source to be the new block, and add
929 a new edge from the entry block to the new block. */
931 for (pe1 = &ENTRY_BLOCK_PTR->succ; *pe1; pe1 = &(*pe1)->succ_next)
939 make_single_succ_edge (ENTRY_BLOCK_PTR, bb, EDGE_FALLTHRU);
942 if (e->src->succ->succ_next)
944 /* Create the new structures. */
945 note = last_loop_beg_note (e->src->end);
947 = create_basic_block (e->src->index + 1, NEXT_INSN (note), NULL);
948 jump_block->count = e->count;
949 jump_block->frequency = EDGE_FREQUENCY (e);
950 jump_block->loop_depth = target->loop_depth;
952 if (target->global_live_at_start)
954 jump_block->global_live_at_start
955 = OBSTACK_ALLOC_REG_SET (&flow_obstack);
956 jump_block->global_live_at_end
957 = OBSTACK_ALLOC_REG_SET (&flow_obstack);
958 COPY_REG_SET (jump_block->global_live_at_start,
959 target->global_live_at_start);
960 COPY_REG_SET (jump_block->global_live_at_end,
961 target->global_live_at_start);
965 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
966 new_edge->probability = e->probability;
967 new_edge->count = e->count;
969 /* Redirect old edge. */
970 redirect_edge_pred (e, jump_block);
971 e->probability = REG_BR_PROB_BASE;
978 e->flags &= ~EDGE_FALLTHRU;
979 if (target == EXIT_BLOCK_PTR)
982 emit_jump_insn_after (gen_return (), jump_block->end);
988 rtx label = block_label (target);
989 emit_jump_insn_after (gen_jump (label), jump_block->end);
990 JUMP_LABEL (jump_block->end) = label;
991 LABEL_NUSES (label)++;
994 emit_barrier_after (jump_block->end);
995 redirect_edge_succ_nodup (e, target);
1000 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1001 (and possibly create new basic block) to make edge non-fallthru.
1002 Return newly created BB or NULL if none. */
1005 force_nonfallthru (e)
1008 return force_nonfallthru_and_redirect (e, e->dest);
1011 /* Redirect edge even at the expense of creating new jump insn or
1012 basic block. Return new basic block if created, NULL otherwise.
1013 Abort if conversion is impossible. */
1016 redirect_edge_and_branch_force (e, target)
1020 if (redirect_edge_and_branch (e, target)
1021 || e->dest == target)
1024 /* In case the edge redirection failed, try to force it to be non-fallthru
1025 and redirect newly created simplejump. */
1026 return force_nonfallthru_and_redirect (e, target);
1029 /* The given edge should potentially be a fallthru edge. If that is in
1030 fact true, delete the jump and barriers that are in the way. */
1033 tidy_fallthru_edge (e, b, c)
1039 /* ??? In a late-running flow pass, other folks may have deleted basic
1040 blocks by nopping out blocks, leaving multiple BARRIERs between here
1041 and the target label. They ought to be chastized and fixed.
1043 We can also wind up with a sequence of undeletable labels between
1044 one block and the next.
1046 So search through a sequence of barriers, labels, and notes for
1047 the head of block C and assert that we really do fall through. */
1049 if (next_real_insn (b->end) != next_real_insn (PREV_INSN (c->head)))
1052 /* Remove what will soon cease being the jump insn from the source block.
1053 If block B consisted only of this single jump, turn it into a deleted
1056 if (GET_CODE (q) == JUMP_INSN
1058 && (any_uncondjump_p (q)
1059 || (b->succ == e && e->succ_next == NULL)))
1062 /* If this was a conditional jump, we need to also delete
1063 the insn that set cc0. */
1064 if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1070 /* We don't want a block to end on a line-number note since that has
1071 the potential of changing the code between -g and not -g. */
1072 while (GET_CODE (q) == NOTE && NOTE_LINE_NUMBER (q) >= 0)
1076 /* Selectively unlink the sequence. */
1077 if (q != PREV_INSN (c->head))
1078 delete_insn_chain (NEXT_INSN (q), PREV_INSN (c->head));
1080 e->flags |= EDGE_FALLTHRU;
1083 /* Fix up edges that now fall through, or rather should now fall through
1084 but previously required a jump around now deleted blocks. Simplify
1085 the search by only examining blocks numerically adjacent, since this
1086 is how find_basic_blocks created them. */
1089 tidy_fallthru_edges ()
1093 for (i = 1; i < n_basic_blocks; i++)
1095 basic_block b = BASIC_BLOCK (i - 1);
1096 basic_block c = BASIC_BLOCK (i);
1099 /* We care about simple conditional or unconditional jumps with
1102 If we had a conditional branch to the next instruction when
1103 find_basic_blocks was called, then there will only be one
1104 out edge for the block which ended with the conditional
1105 branch (since we do not create duplicate edges).
1107 Furthermore, the edge will be marked as a fallthru because we
1108 merge the flags for the duplicate edges. So we do not want to
1109 check that the edge is not a FALLTHRU edge. */
1111 if ((s = b->succ) != NULL
1112 && ! (s->flags & EDGE_COMPLEX)
1113 && s->succ_next == NULL
1115 /* If the jump insn has side effects, we can't tidy the edge. */
1116 && (GET_CODE (b->end) != JUMP_INSN
1117 || onlyjump_p (b->end)))
1118 tidy_fallthru_edge (s, b, c);
1122 /* Helper function for split_edge. Return true in case edge BB2 to BB1
1123 is back edge of syntactic loop. */
1126 back_edge_of_syntactic_loop_p (bb1, bb2)
1127 basic_block bb1, bb2;
1132 if (bb1->index > bb2->index)
1134 else if (bb1->index == bb2->index)
1137 for (insn = bb1->end; insn != bb2->head && count >= 0;
1138 insn = NEXT_INSN (insn))
1139 if (GET_CODE (insn) == NOTE)
1141 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1143 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1150 /* Split a (typically critical) edge. Return the new block.
1151 Abort on abnormal edges.
1153 ??? The code generally expects to be called on critical edges.
1154 The case of a block ending in an unconditional jump to a
1155 block with multiple predecessors is not handled optimally. */
1158 split_edge (edge_in)
1165 /* Abnormal edges cannot be split. */
1166 if ((edge_in->flags & EDGE_ABNORMAL) != 0)
1169 /* We are going to place the new block in front of edge destination.
1170 Avoid existence of fallthru predecessors. */
1171 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1175 for (e = edge_in->dest->pred; e; e = e->pred_next)
1176 if (e->flags & EDGE_FALLTHRU)
1180 force_nonfallthru (e);
1183 /* Create the basic block note.
1185 Where we place the note can have a noticeable impact on the generated
1186 code. Consider this cfg:
1196 If we need to insert an insn on the edge from block 0 to block 1,
1197 we want to ensure the instructions we insert are outside of any
1198 loop notes that physically sit between block 0 and block 1. Otherwise
1199 we confuse the loop optimizer into thinking the loop is a phony. */
1201 if (edge_in->dest != EXIT_BLOCK_PTR
1202 && PREV_INSN (edge_in->dest->head)
1203 && GET_CODE (PREV_INSN (edge_in->dest->head)) == NOTE
1204 && (NOTE_LINE_NUMBER (PREV_INSN (edge_in->dest->head))
1205 == NOTE_INSN_LOOP_BEG)
1206 && !back_edge_of_syntactic_loop_p (edge_in->dest, edge_in->src))
1207 before = PREV_INSN (edge_in->dest->head);
1208 else if (edge_in->dest != EXIT_BLOCK_PTR)
1209 before = edge_in->dest->head;
1213 bb = create_basic_block (edge_in->dest == EXIT_BLOCK_PTR ? n_basic_blocks
1214 : edge_in->dest->index, before, NULL);
1215 bb->count = edge_in->count;
1216 bb->frequency = EDGE_FREQUENCY (edge_in);
1218 /* ??? This info is likely going to be out of date very soon. */
1219 if (edge_in->dest->global_live_at_start)
1221 bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1222 bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1223 COPY_REG_SET (bb->global_live_at_start,
1224 edge_in->dest->global_live_at_start);
1225 COPY_REG_SET (bb->global_live_at_end,
1226 edge_in->dest->global_live_at_start);
1229 edge_out = make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1231 /* For non-fallthry edges, we must adjust the predecessor's
1232 jump instruction to target our new block. */
1233 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1235 if (!redirect_edge_and_branch (edge_in, bb))
1239 redirect_edge_succ (edge_in, bb);
1244 /* Queue instructions for insertion on an edge between two basic blocks.
1245 The new instructions and basic blocks (if any) will not appear in the
1246 CFG until commit_edge_insertions is called. */
1249 insert_insn_on_edge (pattern, e)
1253 /* We cannot insert instructions on an abnormal critical edge.
1254 It will be easier to find the culprit if we die now. */
1255 if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
1258 if (e->insns == NULL_RTX)
1261 push_to_sequence (e->insns);
1263 emit_insn (pattern);
1265 e->insns = get_insns ();
1269 /* Update the CFG for the instructions queued on edge E. */
1272 commit_one_edge_insertion (e)
1275 rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
1278 /* Pull the insns off the edge now since the edge might go away. */
1280 e->insns = NULL_RTX;
1282 /* Figure out where to put these things. If the destination has
1283 one predecessor, insert there. Except for the exit block. */
1284 if (e->dest->pred->pred_next == NULL
1285 && e->dest != EXIT_BLOCK_PTR)
1289 /* Get the location correct wrt a code label, and "nice" wrt
1290 a basic block note, and before everything else. */
1292 if (GET_CODE (tmp) == CODE_LABEL)
1293 tmp = NEXT_INSN (tmp);
1294 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1295 tmp = NEXT_INSN (tmp);
1296 if (tmp == bb->head)
1299 after = PREV_INSN (tmp);
1302 /* If the source has one successor and the edge is not abnormal,
1303 insert there. Except for the entry block. */
1304 else if ((e->flags & EDGE_ABNORMAL) == 0
1305 && e->src->succ->succ_next == NULL
1306 && e->src != ENTRY_BLOCK_PTR)
1310 /* It is possible to have a non-simple jump here. Consider a target
1311 where some forms of unconditional jumps clobber a register. This
1312 happens on the fr30 for example.
1314 We know this block has a single successor, so we can just emit
1315 the queued insns before the jump. */
1316 if (GET_CODE (bb->end) == JUMP_INSN)
1317 for (before = bb->end;
1318 GET_CODE (PREV_INSN (before)) == NOTE
1319 && NOTE_LINE_NUMBER (PREV_INSN (before)) == NOTE_INSN_LOOP_BEG;
1320 before = PREV_INSN (before))
1324 /* We'd better be fallthru, or we've lost track of what's what. */
1325 if ((e->flags & EDGE_FALLTHRU) == 0)
1332 /* Otherwise we must split the edge. */
1335 bb = split_edge (e);
1339 /* Now that we've found the spot, do the insertion. */
1343 emit_insns_before (insns, before);
1344 last = prev_nonnote_insn (before);
1347 last = emit_insns_after (insns, after);
1349 if (returnjump_p (last))
1351 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1352 This is not currently a problem because this only happens
1353 for the (single) epilogue, which already has a fallthru edge
1357 if (e->dest != EXIT_BLOCK_PTR
1358 || e->succ_next != NULL
1359 || (e->flags & EDGE_FALLTHRU) == 0)
1362 e->flags &= ~EDGE_FALLTHRU;
1363 emit_barrier_after (last);
1366 delete_insn (before);
1368 else if (GET_CODE (last) == JUMP_INSN)
1371 find_sub_basic_blocks (bb);
1374 /* Update the CFG for all queued instructions. */
1377 commit_edge_insertions ()
1382 #ifdef ENABLE_CHECKING
1383 verify_flow_info ();
1387 bb = ENTRY_BLOCK_PTR;
1392 for (e = bb->succ; e; e = next)
1394 next = e->succ_next;
1396 commit_one_edge_insertion (e);
1399 if (++i >= n_basic_blocks)
1401 bb = BASIC_BLOCK (i);
1405 /* Print out one basic block with live information at start and end. */
1416 fprintf (outf, ";; Basic block %d, loop depth %d, count ",
1417 bb->index, bb->loop_depth);
1418 fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
1421 fputs (";; Predecessors: ", outf);
1422 for (e = bb->pred; e; e = e->pred_next)
1423 dump_edge_info (outf, e, 0);
1426 fputs (";; Registers live at start:", outf);
1427 dump_regset (bb->global_live_at_start, outf);
1430 for (insn = bb->head, last = NEXT_INSN (bb->end); insn != last;
1431 insn = NEXT_INSN (insn))
1432 print_rtl_single (outf, insn);
1434 fputs (";; Registers live at end:", outf);
1435 dump_regset (bb->global_live_at_end, outf);
1438 fputs (";; Successors: ", outf);
1439 for (e = bb->succ; e; e = e->succ_next)
1440 dump_edge_info (outf, e, 1);
1448 dump_bb (bb, stderr);
1455 dump_bb (BASIC_BLOCK (n), stderr);
1458 /* Like print_rtl, but also print out live information for the start of each
1462 print_rtl_with_bb (outf, rtx_first)
1469 fprintf (outf, "(nil)\n");
1473 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
1474 int max_uid = get_max_uid ();
1476 = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1478 = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1479 enum bb_state *in_bb_p
1480 = (enum bb_state *) xcalloc (max_uid, sizeof (enum bb_state));
1482 for (i = n_basic_blocks - 1; i >= 0; i--)
1484 basic_block bb = BASIC_BLOCK (i);
1487 start[INSN_UID (bb->head)] = bb;
1488 end[INSN_UID (bb->end)] = bb;
1489 for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x))
1491 enum bb_state state = IN_MULTIPLE_BB;
1493 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
1495 in_bb_p[INSN_UID (x)] = state;
1502 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
1507 if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
1509 fprintf (outf, ";; Start of basic block %d, registers live:",
1511 dump_regset (bb->global_live_at_start, outf);
1515 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
1516 && GET_CODE (tmp_rtx) != NOTE
1517 && GET_CODE (tmp_rtx) != BARRIER)
1518 fprintf (outf, ";; Insn is not within a basic block\n");
1519 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
1520 fprintf (outf, ";; Insn is in multiple basic blocks\n");
1522 did_output = print_rtl_single (outf, tmp_rtx);
1524 if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
1526 fprintf (outf, ";; End of basic block %d, registers live:\n",
1528 dump_regset (bb->global_live_at_end, outf);
1541 if (current_function_epilogue_delay_list != 0)
1543 fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
1544 for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0;
1545 tmp_rtx = XEXP (tmp_rtx, 1))
1546 print_rtl_single (outf, XEXP (tmp_rtx, 0));
1551 update_br_prob_note (bb)
1555 if (GET_CODE (bb->end) != JUMP_INSN)
1557 note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX);
1558 if (!note || INTVAL (XEXP (note, 0)) == BRANCH_EDGE (bb)->probability)
1560 XEXP (note, 0) = GEN_INT (BRANCH_EDGE (bb)->probability);
1563 /* Verify the CFG consistency. This function check some CFG invariants and
1564 aborts when something is wrong. Hope that this function will help to
1565 convert many optimization passes to preserve CFG consistent.
1567 Currently it does following checks:
1569 - test head/end pointers
1570 - overlapping of basic blocks
1571 - edge list correctness
1572 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1573 - tails of basic blocks (ensure that boundary is necessary)
1574 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1575 and NOTE_INSN_BASIC_BLOCK
1576 - check that all insns are in the basic blocks
1577 (except the switch handling code, barriers and notes)
1578 - check that all returns are followed by barriers
1580 In future it can be extended check a lot of other stuff as well
1581 (reachability of basic blocks, life information, etc. etc.). */
1586 const int max_uid = get_max_uid ();
1587 const rtx rtx_first = get_insns ();
1588 rtx last_head = get_last_insn ();
1589 basic_block *bb_info, *last_visited;
1590 size_t *edge_checksum;
1592 int i, last_bb_num_seen, num_bb_notes, err = 0;
1594 bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1595 last_visited = (basic_block *) xcalloc (n_basic_blocks + 2,
1596 sizeof (basic_block));
1597 edge_checksum = (size_t *) xcalloc (n_basic_blocks + 2, sizeof (size_t));
1599 for (i = n_basic_blocks - 1; i >= 0; i--)
1601 basic_block bb = BASIC_BLOCK (i);
1602 rtx head = bb->head;
1605 /* Verify the end of the basic block is in the INSN chain. */
1606 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
1612 error ("end insn %d for block %d not found in the insn stream",
1613 INSN_UID (end), bb->index);
1617 /* Work backwards from the end to the head of the basic block
1618 to verify the head is in the RTL chain. */
1619 for (; x != NULL_RTX; x = PREV_INSN (x))
1621 /* While walking over the insn chain, verify insns appear
1622 in only one basic block and initialize the BB_INFO array
1623 used by other passes. */
1624 if (bb_info[INSN_UID (x)] != NULL)
1626 error ("insn %d is in multiple basic blocks (%d and %d)",
1627 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
1631 bb_info[INSN_UID (x)] = bb;
1638 error ("head insn %d for block %d not found in the insn stream",
1639 INSN_UID (head), bb->index);
1646 /* Now check the basic blocks (boundaries etc.) */
1647 for (i = n_basic_blocks - 1; i >= 0; i--)
1649 basic_block bb = BASIC_BLOCK (i);
1650 int has_fallthru = 0;
1653 for (e = bb->succ; e; e = e->succ_next)
1655 if (last_visited [e->dest->index + 2] == bb)
1657 error ("verify_flow_info: Duplicate edge %i->%i",
1658 e->src->index, e->dest->index);
1662 last_visited [e->dest->index + 2] = bb;
1664 if (e->flags & EDGE_FALLTHRU)
1667 if ((e->flags & EDGE_FALLTHRU)
1668 && e->src != ENTRY_BLOCK_PTR
1669 && e->dest != EXIT_BLOCK_PTR)
1673 if (e->src->index + 1 != e->dest->index)
1676 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
1677 e->src->index, e->dest->index);
1681 for (insn = NEXT_INSN (e->src->end); insn != e->dest->head;
1682 insn = NEXT_INSN (insn))
1683 if (GET_CODE (insn) == BARRIER
1684 #ifndef CASE_DROPS_THROUGH
1687 || (INSN_P (insn) && ! JUMP_TABLE_DATA_P (insn))
1691 error ("verify_flow_info: Incorrect fallthru %i->%i",
1692 e->src->index, e->dest->index);
1693 fatal_insn ("wrong insn in the fallthru edge", insn);
1700 error ("verify_flow_info: Basic block %d succ edge is corrupted",
1702 fprintf (stderr, "Predecessor: ");
1703 dump_edge_info (stderr, e, 0);
1704 fprintf (stderr, "\nSuccessor: ");
1705 dump_edge_info (stderr, e, 1);
1706 fprintf (stderr, "\n");
1710 edge_checksum[e->dest->index + 2] += (size_t) e;
1717 /* Ensure existence of barrier in BB with no fallthru edges. */
1718 for (insn = bb->end; !insn || GET_CODE (insn) != BARRIER;
1719 insn = NEXT_INSN (insn))
1721 || (GET_CODE (insn) == NOTE
1722 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK))
1724 error ("missing barrier after block %i", bb->index);
1730 for (e = bb->pred; e; e = e->pred_next)
1734 error ("basic block %d pred edge is corrupted", bb->index);
1735 fputs ("Predecessor: ", stderr);
1736 dump_edge_info (stderr, e, 0);
1737 fputs ("\nSuccessor: ", stderr);
1738 dump_edge_info (stderr, e, 1);
1739 fputc ('\n', stderr);
1742 edge_checksum[e->dest->index + 2] -= (size_t) e;
1745 for (x = bb->head; x != NEXT_INSN (bb->end); x = NEXT_INSN (x))
1746 if (basic_block_for_insn && BLOCK_FOR_INSN (x) != bb)
1749 if (! BLOCK_FOR_INSN (x))
1751 ("insn %d inside basic block %d but block_for_insn is NULL",
1752 INSN_UID (x), bb->index);
1755 ("insn %d inside basic block %d but block_for_insn is %i",
1756 INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index);
1761 /* OK pointers are correct. Now check the header of basic
1762 block. It ought to contain optional CODE_LABEL followed
1763 by NOTE_BASIC_BLOCK. */
1765 if (GET_CODE (x) == CODE_LABEL)
1769 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1777 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
1779 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1785 /* Do checks for empty blocks her. e */
1788 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
1790 if (NOTE_INSN_BASIC_BLOCK_P (x))
1792 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
1793 INSN_UID (x), bb->index);
1800 if (GET_CODE (x) == JUMP_INSN
1801 || GET_CODE (x) == CODE_LABEL
1802 || GET_CODE (x) == BARRIER)
1804 error ("in basic block %d:", bb->index);
1805 fatal_insn ("flow control insn inside a basic block", x);
1810 /* Complete edge checksumming for ENTRY and EXIT. */
1814 for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
1815 edge_checksum[e->dest->index + 2] += (size_t) e;
1817 for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
1818 edge_checksum[e->dest->index + 2] -= (size_t) e;
1821 for (i = -2; i < n_basic_blocks; ++i)
1822 if (edge_checksum[i + 2])
1824 error ("basic block %i edge lists are corrupted", i);
1828 last_bb_num_seen = -1;
1830 for (x = rtx_first; x; x = NEXT_INSN (x))
1832 if (NOTE_INSN_BASIC_BLOCK_P (x))
1834 basic_block bb = NOTE_BASIC_BLOCK (x);
1837 if (bb->index != last_bb_num_seen + 1)
1838 internal_error ("basic blocks not numbered consecutively");
1840 last_bb_num_seen = bb->index;
1843 if (!bb_info[INSN_UID (x)])
1845 switch (GET_CODE (x))
1852 /* An addr_vec is placed outside any block block. */
1854 && GET_CODE (NEXT_INSN (x)) == JUMP_INSN
1855 && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
1856 || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
1859 /* But in any case, non-deletable labels can appear anywhere. */
1863 fatal_insn ("insn outside basic block", x);
1868 && GET_CODE (x) == JUMP_INSN
1869 && returnjump_p (x) && ! condjump_p (x)
1870 && ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER))
1871 fatal_insn ("return not followed by barrier", x);
1874 if (num_bb_notes != n_basic_blocks)
1876 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
1877 num_bb_notes, n_basic_blocks);
1880 internal_error ("verify_flow_info failed");
1884 free (last_visited);
1885 free (edge_checksum);
1888 /* Assume that the preceding pass has possibly eliminated jump instructions
1889 or converted the unconditional jumps. Eliminate the edges from CFG.
1890 Return true if any edges are eliminated. */
1893 purge_dead_edges (bb)
1897 rtx insn = bb->end, note;
1898 bool purged = false;
1900 /* ??? This makes no sense since the later test includes more cases. */
1901 if (GET_CODE (insn) == JUMP_INSN && !simplejump_p (insn))
1904 if (GET_CODE (insn) == JUMP_INSN)
1909 /* We do care only about conditional jumps and simplejumps. */
1910 if (!any_condjump_p (insn)
1911 && !returnjump_p (insn)
1912 && !simplejump_p (insn))
1915 for (e = bb->succ; e; e = next)
1917 next = e->succ_next;
1919 /* Avoid abnormal flags to leak from computed jumps turned
1920 into simplejumps. */
1922 e->flags &= ~EDGE_ABNORMAL;
1924 /* Check purposes we can have edge. */
1925 if ((e->flags & EDGE_FALLTHRU)
1926 && any_condjump_p (insn))
1928 else if (e->dest != EXIT_BLOCK_PTR
1929 && e->dest->head == JUMP_LABEL (insn))
1931 else if (e->dest == EXIT_BLOCK_PTR
1932 && returnjump_p (insn))
1939 if (!bb->succ || !purged)
1943 fprintf (rtl_dump_file, "Purged edges from bb %i\n", bb->index);
1948 /* Redistribute probabilities. */
1949 if (!bb->succ->succ_next)
1951 bb->succ->probability = REG_BR_PROB_BASE;
1952 bb->succ->count = bb->count;
1956 note = find_reg_note (insn, REG_BR_PROB, NULL);
1960 b = BRANCH_EDGE (bb);
1961 f = FALLTHRU_EDGE (bb);
1962 b->probability = INTVAL (XEXP (note, 0));
1963 f->probability = REG_BR_PROB_BASE - b->probability;
1964 b->count = bb->count * b->probability / REG_BR_PROB_BASE;
1965 f->count = bb->count * f->probability / REG_BR_PROB_BASE;
1971 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
1972 if (GET_CODE (insn) == INSN
1973 && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
1977 if (! may_trap_p (PATTERN (insn))
1978 || ((eqnote = find_reg_equal_equiv_note (insn))
1979 && ! may_trap_p (XEXP (eqnote, 0))))
1980 remove_note (insn, note);
1983 /* Cleanup abnormal edges caused by throwing insns that have been
1985 if (! can_throw_internal (bb->end))
1986 for (e = bb->succ; e; e = next)
1988 next = e->succ_next;
1989 if (e->flags & EDGE_EH)
1996 /* If we don't see a jump insn, we don't know exactly why the block would
1997 have been broken at this point. Look for a simple, non-fallthru edge,
1998 as these are only created by conditional branches. If we find such an
1999 edge we know that there used to be a jump here and can then safely
2000 remove all non-fallthru edges. */
2001 for (e = bb->succ; e && (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU));
2008 for (e = bb->succ; e; e = next)
2010 next = e->succ_next;
2011 if (!(e->flags & EDGE_FALLTHRU))
2012 remove_edge (e), purged = true;
2015 if (!bb->succ || bb->succ->succ_next)
2018 bb->succ->probability = REG_BR_PROB_BASE;
2019 bb->succ->count = bb->count;
2022 fprintf (rtl_dump_file, "Purged non-fallthru edges from bb %i\n",
2027 /* Search all basic blocks for potentially dead edges and purge them. Return
2028 true if some edge has been eliminated. */
2031 purge_all_dead_edges (update_life_p)
2034 int i, purged = false;
2039 blocks = sbitmap_alloc (n_basic_blocks);
2040 sbitmap_zero (blocks);
2043 for (i = 0; i < n_basic_blocks; i++)
2045 bool purged_here = purge_dead_edges (BASIC_BLOCK (i));
2047 purged |= purged_here;
2048 if (purged_here && update_life_p)
2049 SET_BIT (blocks, i);
2052 if (update_life_p && purged)
2053 update_life_info (blocks, UPDATE_LIFE_GLOBAL,
2054 PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
2055 | PROP_KILL_DEAD_CODE);
2058 sbitmap_free (blocks);