1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 /* This file contains low level functions to manipulate the CFG and analyze it
23 that are aware of the RTL intermediate language.
25 Available functionality:
26 - CFG-aware instruction chain manipulation
27 delete_insn, delete_insn_chain
28 - Basic block manipulation
29 create_basic_block, flow_delete_block, split_block,
31 - Infrastructure to determine quickly basic block for insn
32 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
33 - Edge redirection with updating and optimizing of insn chain
34 block_label, redirect_edge_and_branch,
35 redirect_edge_and_branch_force, tidy_fallthru_edge, force_nonfallthru
36 - Edge splitting and commiting to edges
37 split_edge, insert_insn_on_edge, commit_edge_insertions
38 - Dumping and debugging
39 print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
40 - Consistency checking
42 - CFG updating after constant propagation
43 purge_dead_edges, purge_all_dead_edges */
49 #include "hard-reg-set.h"
50 #include "basic-block.h"
59 #include "insn-config.h"
61 /* Stubs in case we don't have a return insn. */
64 #define gen_return() NULL_RTX
67 /* The basic block structure for every insn, indexed by uid. */
68 varray_type basic_block_for_insn;
70 /* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */
71 /* ??? Should probably be using LABEL_NUSES instead. It would take a
72 bit of surgery to be able to use or co-opt the routines in jump. */
74 rtx tail_recursion_label_list;
76 static int can_delete_note_p PARAMS ((rtx));
77 static int can_delete_label_p PARAMS ((rtx));
78 static void commit_one_edge_insertion PARAMS ((edge, int));
79 static bool try_redirect_by_replacing_jump PARAMS ((edge, basic_block));
80 static rtx last_loop_beg_note PARAMS ((rtx));
81 static bool back_edge_of_syntactic_loop_p PARAMS ((basic_block, basic_block));
82 static basic_block force_nonfallthru_and_redirect PARAMS ((edge, basic_block));
84 /* Return true if NOTE is not one of the ones that must be kept paired,
85 so that we may simply delete it. */
88 can_delete_note_p (note)
91 return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED
92 || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK
93 || NOTE_LINE_NUMBER (note) == NOTE_INSN_PREDICTION);
96 /* True if a given label can be deleted. */
99 can_delete_label_p (label)
102 return (!LABEL_PRESERVE_P (label)
103 /* User declared labels must be preserved. */
104 && LABEL_NAME (label) == 0
105 && !in_expr_list_p (forced_labels, label)
106 && !in_expr_list_p (label_value_list, label));
109 /* Delete INSN by patching it out. Return the next insn. */
115 rtx next = NEXT_INSN (insn);
117 bool really_delete = true;
119 if (GET_CODE (insn) == CODE_LABEL)
121 /* Some labels can't be directly removed from the INSN chain, as they
122 might be references via variables, constant pool etc.
123 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
124 if (! can_delete_label_p (insn))
126 const char *name = LABEL_NAME (insn);
128 really_delete = false;
129 PUT_CODE (insn, NOTE);
130 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL;
131 NOTE_SOURCE_FILE (insn) = name;
134 remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
139 /* If this insn has already been deleted, something is very wrong. */
140 if (INSN_DELETED_P (insn))
143 INSN_DELETED_P (insn) = 1;
146 /* If deleting a jump, decrement the use count of the label. Deleting
147 the label itself should happen in the normal course of block merging. */
148 if (GET_CODE (insn) == JUMP_INSN
150 && GET_CODE (JUMP_LABEL (insn)) == CODE_LABEL)
151 LABEL_NUSES (JUMP_LABEL (insn))--;
153 /* Also if deleting an insn that references a label. */
154 else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX
155 && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
156 LABEL_NUSES (XEXP (note, 0))--;
158 if (GET_CODE (insn) == JUMP_INSN
159 && (GET_CODE (PATTERN (insn)) == ADDR_VEC
160 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
162 rtx pat = PATTERN (insn);
163 int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC;
164 int len = XVECLEN (pat, diff_vec_p);
167 for (i = 0; i < len; i++)
169 rtx label = XEXP (XVECEXP (pat, diff_vec_p, i), 0);
171 /* When deleting code in bulk (e.g. removing many unreachable
172 blocks) we can delete a label that's a target of the vector
173 before deleting the vector itself. */
174 if (GET_CODE (label) != NOTE)
175 LABEL_NUSES (label)--;
182 /* Like delete_insn but also purge dead edges from BB. */
184 delete_insn_and_edges (insn)
190 if (basic_block_for_insn
192 && (unsigned int)INSN_UID (insn) < basic_block_for_insn->num_elements
193 && BLOCK_FOR_INSN (insn)
194 && BLOCK_FOR_INSN (insn)->end == insn)
196 x = delete_insn (insn);
198 purge_dead_edges (BLOCK_FOR_INSN (insn));
202 /* Unlink a chain of insns between START and FINISH, leaving notes
203 that must be paired. */
206 delete_insn_chain (start, finish)
211 /* Unchain the insns one by one. It would be quicker to delete all of these
212 with a single unchaining, rather than one at a time, but we need to keep
216 next = NEXT_INSN (start);
217 if (GET_CODE (start) == NOTE && !can_delete_note_p (start))
220 next = delete_insn (start);
228 /* Like delete_insn but also purge dead edges from BB. */
230 delete_insn_chain_and_edges (first, last)
235 if (basic_block_for_insn
237 && (unsigned int)INSN_UID (last) < basic_block_for_insn->num_elements
238 && BLOCK_FOR_INSN (last)
239 && BLOCK_FOR_INSN (last)->end == last)
241 delete_insn_chain (first, last);
243 purge_dead_edges (BLOCK_FOR_INSN (last));
246 /* Create a new basic block consisting of the instructions between HEAD and END
247 inclusive. This function is designed to allow fast BB construction - reuses
248 the note and basic block struct in BB_NOTE, if any and do not grow
249 BASIC_BLOCK chain and should be used directly only by CFG construction code.
250 END can be NULL in to create new empty basic block before HEAD. Both END
251 and HEAD can be NULL to create basic block at the end of INSN chain. */
254 create_basic_block_structure (index, head, end, bb_note)
256 rtx head, end, bb_note;
261 && ! RTX_INTEGRATED_P (bb_note)
262 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
265 /* If we found an existing note, thread it back onto the chain. */
269 if (GET_CODE (head) == CODE_LABEL)
273 after = PREV_INSN (head);
277 if (after != bb_note && NEXT_INSN (after) != bb_note)
278 reorder_insns (bb_note, bb_note, after);
282 /* Otherwise we must create a note and a basic block structure. */
288 = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
289 else if (GET_CODE (head) == CODE_LABEL && end)
291 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
297 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
303 NOTE_BASIC_BLOCK (bb_note) = bb;
306 /* Always include the bb note in the block. */
307 if (NEXT_INSN (end) == bb_note)
314 BASIC_BLOCK (index) = bb;
315 if (basic_block_for_insn)
316 update_bb_for_insn (bb);
318 /* Tag the block so that we know it has been used when considering
319 other basic block notes. */
325 /* Create new basic block consisting of instructions in between HEAD and END
326 and place it to the BB chain at position INDEX. END can be NULL in to
327 create new empty basic block before HEAD. Both END and HEAD can be NULL to
328 create basic block at the end of INSN chain. */
331 create_basic_block (index, head, end)
338 /* Place the new block just after the block being split. */
339 VARRAY_GROW (basic_block_info, ++n_basic_blocks);
341 /* Some parts of the compiler expect blocks to be number in
342 sequential order so insert the new block immediately after the
343 block being split.. */
344 for (i = n_basic_blocks - 1; i > index; --i)
346 basic_block tmp = BASIC_BLOCK (i - 1);
348 BASIC_BLOCK (i) = tmp;
352 bb = create_basic_block_structure (index, head, end, NULL);
357 /* Delete the insns in a (non-live) block. We physically delete every
358 non-deleted-note insn, and update the flow graph appropriately.
360 Return nonzero if we deleted an exception handler. */
362 /* ??? Preserving all such notes strikes me as wrong. It would be nice
363 to post-process the stream to remove empty blocks, loops, ranges, etc. */
366 flow_delete_block_noexpunge (b)
369 int deleted_handler = 0;
372 /* If the head of this block is a CODE_LABEL, then it might be the
373 label for an exception handler which can't be reached.
375 We need to remove the label from the exception_handler_label list
376 and remove the associated NOTE_INSN_EH_REGION_BEG and
377 NOTE_INSN_EH_REGION_END notes. */
379 /* Get rid of all NOTE_INSN_PREDICTIONs hanging before the block. */
381 for (insn = PREV_INSN (b->head); insn; insn = PREV_INSN (insn))
383 if (GET_CODE (insn) != NOTE)
385 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_PREDICTION)
386 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
391 never_reached_warning (insn, b->end);
393 if (GET_CODE (insn) == CODE_LABEL)
394 maybe_remove_eh_handler (insn);
396 /* Include any jump table following the basic block. */
398 if (GET_CODE (end) == JUMP_INSN
399 && (tmp = JUMP_LABEL (end)) != NULL_RTX
400 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
401 && GET_CODE (tmp) == JUMP_INSN
402 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
403 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
406 /* Include any barrier that may follow the basic block. */
407 tmp = next_nonnote_insn (end);
408 if (tmp && GET_CODE (tmp) == BARRIER)
411 /* Selectively delete the entire chain. */
413 delete_insn_chain (insn, end);
415 /* Remove the edges into and out of this block. Note that there may
416 indeed be edges in, if we are removing an unreachable loop. */
417 while (b->pred != NULL)
418 remove_edge (b->pred);
419 while (b->succ != NULL)
420 remove_edge (b->succ);
425 return deleted_handler;
429 flow_delete_block (b)
432 int deleted_handler = flow_delete_block_noexpunge (b);
434 /* Remove the basic block from the array, and compact behind it. */
437 return deleted_handler;
440 /* Records the basic block struct in BB_FOR_INSN, for every instruction
441 indexed by INSN_UID. MAX is the size of the array. */
444 compute_bb_for_insn (max)
449 if (basic_block_for_insn)
450 VARRAY_FREE (basic_block_for_insn);
452 VARRAY_BB_INIT (basic_block_for_insn, max, "basic_block_for_insn");
454 for (i = 0; i < n_basic_blocks; ++i)
456 basic_block bb = BASIC_BLOCK (i);
460 for (insn = bb->head; ; insn = NEXT_INSN (insn))
462 if (INSN_UID (insn) < max)
463 VARRAY_BB (basic_block_for_insn, INSN_UID (insn)) = bb;
471 /* Release the basic_block_for_insn array. */
476 if (basic_block_for_insn)
477 VARRAY_FREE (basic_block_for_insn);
479 basic_block_for_insn = 0;
482 /* Update insns block within BB. */
485 update_bb_for_insn (bb)
490 if (! basic_block_for_insn)
493 for (insn = bb->head; ; insn = NEXT_INSN (insn))
495 set_block_for_insn (insn, bb);
501 /* Record INSN's block as BB. */
504 set_block_for_insn (insn, bb)
508 size_t uid = INSN_UID (insn);
510 if (uid >= basic_block_for_insn->num_elements)
512 /* Add one-eighth the size so we don't keep calling xrealloc. */
513 size_t new_size = uid + (uid + 7) / 8;
515 VARRAY_GROW (basic_block_for_insn, new_size);
518 VARRAY_BB (basic_block_for_insn, uid) = bb;
521 /* Split a block BB after insn INSN creating a new fallthru edge.
522 Return the new edge. Note that to keep other parts of the compiler happy,
523 this function renumbers all the basic blocks so that the new
524 one has a number one greater than the block split. */
527 split_block (bb, insn)
535 /* There is no point splitting the block after its end. */
539 /* Create the new basic block. */
540 new_bb = create_basic_block (bb->index + 1, NEXT_INSN (insn), bb->end);
541 new_bb->count = bb->count;
542 new_bb->frequency = bb->frequency;
543 new_bb->loop_depth = bb->loop_depth;
546 /* Redirect the outgoing edges. */
547 new_bb->succ = bb->succ;
549 for (e = new_bb->succ; e; e = e->succ_next)
552 new_edge = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
554 if (bb->global_live_at_start)
556 new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
557 new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
558 COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
560 /* We now have to calculate which registers are live at the end
561 of the split basic block and at the start of the new basic
562 block. Start with those registers that are known to be live
563 at the end of the original basic block and get
564 propagate_block to determine which registers are live. */
565 COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_end);
566 propagate_block (new_bb, new_bb->global_live_at_start, NULL, NULL, 0);
567 COPY_REG_SET (bb->global_live_at_end,
568 new_bb->global_live_at_start);
569 #ifdef HAVE_conditional_execution
570 /* In the presence of conditional execution we are not able to update
571 liveness precisely. */
572 if (reload_completed)
574 bb->flags |= BB_DIRTY;
575 new_bb->flags |= BB_DIRTY;
583 /* Blocks A and B are to be merged into a single block A. The insns
584 are already contiguous, hence `nomove'. */
587 merge_blocks_nomove (a, b)
590 rtx b_head = b->head, b_end = b->end, a_end = a->end;
591 rtx del_first = NULL_RTX, del_last = NULL_RTX;
595 /* If there was a CODE_LABEL beginning B, delete it. */
596 if (GET_CODE (b_head) == CODE_LABEL)
598 /* Detect basic blocks with nothing but a label. This can happen
599 in particular at the end of a function. */
603 del_first = del_last = b_head;
604 b_head = NEXT_INSN (b_head);
607 /* Delete the basic block note and handle blocks containing just that
609 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
617 b_head = NEXT_INSN (b_head);
620 /* If there was a jump out of A, delete it. */
621 if (GET_CODE (a_end) == JUMP_INSN)
625 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
626 if (GET_CODE (prev) != NOTE
627 || NOTE_LINE_NUMBER (prev) == NOTE_INSN_BASIC_BLOCK
634 /* If this was a conditional jump, we need to also delete
635 the insn that set cc0. */
636 if (only_sets_cc0_p (prev))
640 prev = prev_nonnote_insn (prev);
647 a_end = PREV_INSN (del_first);
649 else if (GET_CODE (NEXT_INSN (a_end)) == BARRIER)
650 del_first = NEXT_INSN (a_end);
652 /* Normally there should only be one successor of A and that is B, but
653 partway though the merge of blocks for conditional_execution we'll
654 be merging a TEST block with THEN and ELSE successors. Free the
655 whole lot of them and hope the caller knows what they're doing. */
657 remove_edge (a->succ);
659 /* Adjust the edges out of B for the new owner. */
660 for (e = b->succ; e; e = e->succ_next)
663 a->flags |= b->flags;
665 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
666 b->pred = b->succ = NULL;
667 a->global_live_at_end = b->global_live_at_end;
671 /* Delete everything marked above as well as crap that might be
672 hanging out between the two blocks. */
673 delete_insn_chain (del_first, del_last);
675 /* Reassociate the insns of B with A. */
678 if (basic_block_for_insn)
682 for (x = a_end; x != b_end; x = NEXT_INSN (x))
683 set_block_for_insn (x, a);
685 set_block_for_insn (b_end, a);
694 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
701 if (block == EXIT_BLOCK_PTR)
704 if (GET_CODE (block->head) != CODE_LABEL)
706 block->head = emit_label_before (gen_label_rtx (), block->head);
707 if (basic_block_for_insn)
708 set_block_for_insn (block->head, block);
714 /* Attempt to perform edge redirection by replacing possibly complex jump
715 instruction by unconditional jump or removing jump completely. This can
716 apply only if all edges now point to the same block. The parameters and
717 return values are equivalent to redirect_edge_and_branch. */
720 try_redirect_by_replacing_jump (e, target)
724 basic_block src = e->src;
725 rtx insn = src->end, kill_from;
730 /* Verify that all targets will be TARGET. */
731 for (tmp = src->succ; tmp; tmp = tmp->succ_next)
732 if (tmp->dest != target && tmp != e)
735 if (tmp || !onlyjump_p (insn))
737 if (reload_completed && JUMP_LABEL (insn)
738 && (table = NEXT_INSN (JUMP_LABEL (insn))) != NULL_RTX
739 && GET_CODE (table) == JUMP_INSN
740 && (GET_CODE (PATTERN (table)) == ADDR_VEC
741 || GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC))
744 /* Avoid removing branch with side effects. */
745 set = single_set (insn);
746 if (!set || side_effects_p (set))
749 /* In case we zap a conditional jump, we'll need to kill
750 the cc0 setter too. */
753 if (reg_mentioned_p (cc0_rtx, PATTERN (insn)))
754 kill_from = PREV_INSN (insn);
757 /* See if we can create the fallthru edge. */
758 if (can_fallthru (src, target))
761 fprintf (rtl_dump_file, "Removing jump %i.\n", INSN_UID (insn));
764 /* Selectively unlink whole insn chain. */
765 delete_insn_chain (kill_from, PREV_INSN (target->head));
768 /* If this already is simplejump, redirect it. */
769 else if (simplejump_p (insn))
771 if (e->dest == target)
774 fprintf (rtl_dump_file, "Redirecting jump %i from %i to %i.\n",
775 INSN_UID (insn), e->dest->index, target->index);
776 if (!redirect_jump (insn, block_label (target), 0))
778 if (target == EXIT_BLOCK_PTR)
784 /* Cannot do anything for target exit block. */
785 else if (target == EXIT_BLOCK_PTR)
788 /* Or replace possibly complicated jump insn by simple jump insn. */
791 rtx target_label = block_label (target);
794 emit_jump_insn_after (gen_jump (target_label), insn);
795 JUMP_LABEL (src->end) = target_label;
796 LABEL_NUSES (target_label)++;
798 fprintf (rtl_dump_file, "Replacing insn %i by jump %i\n",
799 INSN_UID (insn), INSN_UID (src->end));
802 delete_insn_chain (kill_from, insn);
804 /* Recognize a tablejump that we are converting to a
805 simple jump and remove its associated CODE_LABEL
806 and ADDR_VEC or ADDR_DIFF_VEC. */
807 if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
808 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
809 && GET_CODE (tmp) == JUMP_INSN
810 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
811 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
813 delete_insn_chain (JUMP_LABEL (insn), tmp);
816 barrier = next_nonnote_insn (src->end);
817 if (!barrier || GET_CODE (barrier) != BARRIER)
818 emit_barrier_after (src->end);
821 /* Keep only one edge out and set proper flags. */
822 while (src->succ->succ_next)
823 remove_edge (src->succ);
826 e->flags = EDGE_FALLTHRU;
830 e->probability = REG_BR_PROB_BASE;
831 e->count = src->count;
833 /* We don't want a block to end on a line-number note since that has
834 the potential of changing the code between -g and not -g. */
835 while (GET_CODE (e->src->end) == NOTE
836 && NOTE_LINE_NUMBER (e->src->end) >= 0)
837 delete_insn (e->src->end);
839 if (e->dest != target)
840 redirect_edge_succ (e, target);
845 /* Return last loop_beg note appearing after INSN, before start of next
846 basic block. Return INSN if there are no such notes.
848 When emitting jump to redirect an fallthru edge, it should always appear
849 after the LOOP_BEG notes, as loop optimizer expect loop to either start by
850 fallthru edge or jump following the LOOP_BEG note jumping to the loop exit
854 last_loop_beg_note (insn)
859 for (insn = NEXT_INSN (insn); insn && GET_CODE (insn) == NOTE
860 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK;
861 insn = NEXT_INSN (insn))
862 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
868 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
869 expense of adding new instructions or reordering basic blocks.
871 Function can be also called with edge destination equivalent to the TARGET.
872 Then it should try the simplifications and do nothing if none is possible.
874 Return true if transformation succeeded. We still return false in case E
875 already destinated TARGET and we didn't managed to simplify instruction
879 redirect_edge_and_branch (e, target)
884 rtx old_label = e->dest->head;
885 basic_block src = e->src;
888 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
891 if (try_redirect_by_replacing_jump (e, target))
894 /* Do this fast path late, as we want above code to simplify for cases
895 where called on single edge leaving basic block containing nontrivial
897 else if (e->dest == target)
900 /* We can only redirect non-fallthru edges of jump insn. */
901 if (e->flags & EDGE_FALLTHRU)
903 else if (GET_CODE (insn) != JUMP_INSN)
906 /* Recognize a tablejump and adjust all matching cases. */
907 if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
908 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
909 && GET_CODE (tmp) == JUMP_INSN
910 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
911 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
915 rtx new_label = block_label (target);
917 if (target == EXIT_BLOCK_PTR)
919 if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
920 vec = XVEC (PATTERN (tmp), 0);
922 vec = XVEC (PATTERN (tmp), 1);
924 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
925 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
927 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
928 --LABEL_NUSES (old_label);
929 ++LABEL_NUSES (new_label);
932 /* Handle casesi dispatch insns */
933 if ((tmp = single_set (insn)) != NULL
934 && SET_DEST (tmp) == pc_rtx
935 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
936 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
937 && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
939 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (VOIDmode,
941 --LABEL_NUSES (old_label);
942 ++LABEL_NUSES (new_label);
947 /* ?? We may play the games with moving the named labels from
948 one basic block to the other in case only one computed_jump is
950 if (computed_jump_p (insn)
951 /* A return instruction can't be redirected. */
952 || returnjump_p (insn))
955 /* If the insn doesn't go where we think, we're confused. */
956 if (JUMP_LABEL (insn) != old_label)
959 /* If the substitution doesn't succeed, die. This can happen
960 if the back end emitted unrecognizable instructions or if
961 target is exit block on some arches. */
962 if (!redirect_jump (insn, block_label (target), 0))
964 if (target == EXIT_BLOCK_PTR)
971 fprintf (rtl_dump_file, "Edge %i->%i redirected to %i\n",
972 e->src->index, e->dest->index, target->index);
974 if (e->dest != target)
975 redirect_edge_succ_nodup (e, target);
980 /* Like force_nonfallthru below, but additionally performs redirection
981 Used by redirect_edge_and_branch_force. */
984 force_nonfallthru_and_redirect (e, target)
988 basic_block jump_block, new_bb = NULL;
992 if (e->flags & EDGE_ABNORMAL)
994 else if (!(e->flags & EDGE_FALLTHRU))
996 else if (e->src == ENTRY_BLOCK_PTR)
998 /* We can't redirect the entry block. Create an empty block at the
999 start of the function which we use to add the new jump. */
1001 basic_block bb = create_basic_block (0, e->dest->head, NULL);
1003 /* Change the existing edge's source to be the new block, and add
1004 a new edge from the entry block to the new block. */
1006 for (pe1 = &ENTRY_BLOCK_PTR->succ; *pe1; pe1 = &(*pe1)->succ_next)
1009 *pe1 = e->succ_next;
1014 make_single_succ_edge (ENTRY_BLOCK_PTR, bb, EDGE_FALLTHRU);
1017 if (e->src->succ->succ_next)
1019 /* Create the new structures. */
1020 note = last_loop_beg_note (e->src->end);
1022 = create_basic_block (e->src->index + 1, NEXT_INSN (note), NULL);
1023 jump_block->count = e->count;
1024 jump_block->frequency = EDGE_FREQUENCY (e);
1025 jump_block->loop_depth = target->loop_depth;
1027 if (target->global_live_at_start)
1029 jump_block->global_live_at_start
1030 = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1031 jump_block->global_live_at_end
1032 = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1033 COPY_REG_SET (jump_block->global_live_at_start,
1034 target->global_live_at_start);
1035 COPY_REG_SET (jump_block->global_live_at_end,
1036 target->global_live_at_start);
1040 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1041 new_edge->probability = e->probability;
1042 new_edge->count = e->count;
1044 /* Redirect old edge. */
1045 redirect_edge_pred (e, jump_block);
1046 e->probability = REG_BR_PROB_BASE;
1048 new_bb = jump_block;
1051 jump_block = e->src;
1053 e->flags &= ~EDGE_FALLTHRU;
1054 if (target == EXIT_BLOCK_PTR)
1057 emit_jump_insn_after (gen_return (), jump_block->end);
1063 rtx label = block_label (target);
1064 emit_jump_insn_after (gen_jump (label), jump_block->end);
1065 JUMP_LABEL (jump_block->end) = label;
1066 LABEL_NUSES (label)++;
1069 emit_barrier_after (jump_block->end);
1070 redirect_edge_succ_nodup (e, target);
1075 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1076 (and possibly create new basic block) to make edge non-fallthru.
1077 Return newly created BB or NULL if none. */
1080 force_nonfallthru (e)
1083 return force_nonfallthru_and_redirect (e, e->dest);
1086 /* Redirect edge even at the expense of creating new jump insn or
1087 basic block. Return new basic block if created, NULL otherwise.
1088 Abort if conversion is impossible. */
1091 redirect_edge_and_branch_force (e, target)
1095 if (redirect_edge_and_branch (e, target)
1096 || e->dest == target)
1099 /* In case the edge redirection failed, try to force it to be non-fallthru
1100 and redirect newly created simplejump. */
1101 return force_nonfallthru_and_redirect (e, target);
1104 /* The given edge should potentially be a fallthru edge. If that is in
1105 fact true, delete the jump and barriers that are in the way. */
1108 tidy_fallthru_edge (e, b, c)
1114 /* ??? In a late-running flow pass, other folks may have deleted basic
1115 blocks by nopping out blocks, leaving multiple BARRIERs between here
1116 and the target label. They ought to be chastized and fixed.
1118 We can also wind up with a sequence of undeletable labels between
1119 one block and the next.
1121 So search through a sequence of barriers, labels, and notes for
1122 the head of block C and assert that we really do fall through. */
1124 for (q = NEXT_INSN (b->end); q != c->head; q = NEXT_INSN (q))
1128 /* Remove what will soon cease being the jump insn from the source block.
1129 If block B consisted only of this single jump, turn it into a deleted
1132 if (GET_CODE (q) == JUMP_INSN
1134 && (any_uncondjump_p (q)
1135 || (b->succ == e && e->succ_next == NULL)))
1138 /* If this was a conditional jump, we need to also delete
1139 the insn that set cc0. */
1140 if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1146 /* We don't want a block to end on a line-number note since that has
1147 the potential of changing the code between -g and not -g. */
1148 while (GET_CODE (q) == NOTE && NOTE_LINE_NUMBER (q) >= 0)
1152 /* Selectively unlink the sequence. */
1153 if (q != PREV_INSN (c->head))
1154 delete_insn_chain (NEXT_INSN (q), PREV_INSN (c->head));
1156 e->flags |= EDGE_FALLTHRU;
1159 /* Fix up edges that now fall through, or rather should now fall through
1160 but previously required a jump around now deleted blocks. Simplify
1161 the search by only examining blocks numerically adjacent, since this
1162 is how find_basic_blocks created them. */
1165 tidy_fallthru_edges ()
1169 for (i = 1; i < n_basic_blocks; i++)
1171 basic_block b = BASIC_BLOCK (i - 1);
1172 basic_block c = BASIC_BLOCK (i);
1175 /* We care about simple conditional or unconditional jumps with
1178 If we had a conditional branch to the next instruction when
1179 find_basic_blocks was called, then there will only be one
1180 out edge for the block which ended with the conditional
1181 branch (since we do not create duplicate edges).
1183 Furthermore, the edge will be marked as a fallthru because we
1184 merge the flags for the duplicate edges. So we do not want to
1185 check that the edge is not a FALLTHRU edge. */
1187 if ((s = b->succ) != NULL
1188 && ! (s->flags & EDGE_COMPLEX)
1189 && s->succ_next == NULL
1191 /* If the jump insn has side effects, we can't tidy the edge. */
1192 && (GET_CODE (b->end) != JUMP_INSN
1193 || onlyjump_p (b->end)))
1194 tidy_fallthru_edge (s, b, c);
1198 /* Helper function for split_edge. Return true in case edge BB2 to BB1
1199 is back edge of syntactic loop. */
1202 back_edge_of_syntactic_loop_p (bb1, bb2)
1203 basic_block bb1, bb2;
1208 if (bb1->index > bb2->index)
1210 else if (bb1->index == bb2->index)
1213 for (insn = bb1->end; insn != bb2->head && count >= 0;
1214 insn = NEXT_INSN (insn))
1215 if (GET_CODE (insn) == NOTE)
1217 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1219 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1226 /* Split a (typically critical) edge. Return the new block.
1227 Abort on abnormal edges.
1229 ??? The code generally expects to be called on critical edges.
1230 The case of a block ending in an unconditional jump to a
1231 block with multiple predecessors is not handled optimally. */
1234 split_edge (edge_in)
1241 /* Abnormal edges cannot be split. */
1242 if ((edge_in->flags & EDGE_ABNORMAL) != 0)
1245 /* We are going to place the new block in front of edge destination.
1246 Avoid existence of fallthru predecessors. */
1247 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1251 for (e = edge_in->dest->pred; e; e = e->pred_next)
1252 if (e->flags & EDGE_FALLTHRU)
1256 force_nonfallthru (e);
1259 /* Create the basic block note.
1261 Where we place the note can have a noticeable impact on the generated
1262 code. Consider this cfg:
1272 If we need to insert an insn on the edge from block 0 to block 1,
1273 we want to ensure the instructions we insert are outside of any
1274 loop notes that physically sit between block 0 and block 1. Otherwise
1275 we confuse the loop optimizer into thinking the loop is a phony. */
1277 if (edge_in->dest != EXIT_BLOCK_PTR
1278 && PREV_INSN (edge_in->dest->head)
1279 && GET_CODE (PREV_INSN (edge_in->dest->head)) == NOTE
1280 && (NOTE_LINE_NUMBER (PREV_INSN (edge_in->dest->head))
1281 == NOTE_INSN_LOOP_BEG)
1282 && !back_edge_of_syntactic_loop_p (edge_in->dest, edge_in->src))
1283 before = PREV_INSN (edge_in->dest->head);
1284 else if (edge_in->dest != EXIT_BLOCK_PTR)
1285 before = edge_in->dest->head;
1289 bb = create_basic_block (edge_in->dest == EXIT_BLOCK_PTR ? n_basic_blocks
1290 : edge_in->dest->index, before, NULL);
1291 bb->count = edge_in->count;
1292 bb->frequency = EDGE_FREQUENCY (edge_in);
1294 /* ??? This info is likely going to be out of date very soon. */
1295 if (edge_in->dest->global_live_at_start)
1297 bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1298 bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1299 COPY_REG_SET (bb->global_live_at_start,
1300 edge_in->dest->global_live_at_start);
1301 COPY_REG_SET (bb->global_live_at_end,
1302 edge_in->dest->global_live_at_start);
1305 edge_out = make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1307 /* For non-fallthry edges, we must adjust the predecessor's
1308 jump instruction to target our new block. */
1309 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1311 if (!redirect_edge_and_branch (edge_in, bb))
1315 redirect_edge_succ (edge_in, bb);
1320 /* Queue instructions for insertion on an edge between two basic blocks.
1321 The new instructions and basic blocks (if any) will not appear in the
1322 CFG until commit_edge_insertions is called. */
1325 insert_insn_on_edge (pattern, e)
1329 /* We cannot insert instructions on an abnormal critical edge.
1330 It will be easier to find the culprit if we die now. */
1331 if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
1334 if (e->insns == NULL_RTX)
1337 push_to_sequence (e->insns);
1339 emit_insn (pattern);
1341 e->insns = get_insns ();
1345 /* Update the CFG for the instructions queued on edge E. */
1348 commit_one_edge_insertion (e, watch_calls)
1352 rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
1355 /* Pull the insns off the edge now since the edge might go away. */
1357 e->insns = NULL_RTX;
1359 /* Special case -- avoid inserting code between call and storing
1360 its return value. */
1361 if (watch_calls && (e->flags & EDGE_FALLTHRU) && !e->dest->pred->pred_next
1362 && e->src != ENTRY_BLOCK_PTR
1363 && GET_CODE (e->src->end) == CALL_INSN)
1365 rtx next = next_nonnote_insn (e->src->end);
1367 after = e->dest->head;
1368 /* The first insn after the call may be a stack pop, skip it. */
1370 && keep_with_call_p (next))
1373 next = next_nonnote_insn (next);
1377 if (!before && !after)
1379 /* Figure out where to put these things. If the destination has
1380 one predecessor, insert there. Except for the exit block. */
1381 if (e->dest->pred->pred_next == NULL && e->dest != EXIT_BLOCK_PTR)
1385 /* Get the location correct wrt a code label, and "nice" wrt
1386 a basic block note, and before everything else. */
1388 if (GET_CODE (tmp) == CODE_LABEL)
1389 tmp = NEXT_INSN (tmp);
1390 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1391 tmp = NEXT_INSN (tmp);
1392 if (tmp == bb->head)
1395 after = PREV_INSN (tmp);
1397 after = get_last_insn ();
1400 /* If the source has one successor and the edge is not abnormal,
1401 insert there. Except for the entry block. */
1402 else if ((e->flags & EDGE_ABNORMAL) == 0
1403 && e->src->succ->succ_next == NULL
1404 && e->src != ENTRY_BLOCK_PTR)
1408 /* It is possible to have a non-simple jump here. Consider a target
1409 where some forms of unconditional jumps clobber a register. This
1410 happens on the fr30 for example.
1412 We know this block has a single successor, so we can just emit
1413 the queued insns before the jump. */
1414 if (GET_CODE (bb->end) == JUMP_INSN)
1415 for (before = bb->end;
1416 GET_CODE (PREV_INSN (before)) == NOTE
1417 && NOTE_LINE_NUMBER (PREV_INSN (before)) ==
1418 NOTE_INSN_LOOP_BEG; before = PREV_INSN (before))
1422 /* We'd better be fallthru, or we've lost track of what's what. */
1423 if ((e->flags & EDGE_FALLTHRU) == 0)
1429 /* Otherwise we must split the edge. */
1432 bb = split_edge (e);
1437 /* Now that we've found the spot, do the insertion. */
1441 emit_insns_before (insns, before);
1442 last = prev_nonnote_insn (before);
1445 last = emit_insns_after (insns, after);
1447 if (returnjump_p (last))
1449 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1450 This is not currently a problem because this only happens
1451 for the (single) epilogue, which already has a fallthru edge
1455 if (e->dest != EXIT_BLOCK_PTR
1456 || e->succ_next != NULL || (e->flags & EDGE_FALLTHRU) == 0)
1459 e->flags &= ~EDGE_FALLTHRU;
1460 emit_barrier_after (last);
1463 delete_insn (before);
1465 else if (GET_CODE (last) == JUMP_INSN)
1468 find_sub_basic_blocks (bb);
1471 /* Update the CFG for all queued instructions. */
1474 commit_edge_insertions ()
1479 #ifdef ENABLE_CHECKING
1480 verify_flow_info ();
1484 bb = ENTRY_BLOCK_PTR;
1489 for (e = bb->succ; e; e = next)
1491 next = e->succ_next;
1493 commit_one_edge_insertion (e, false);
1496 if (++i >= n_basic_blocks)
1498 bb = BASIC_BLOCK (i);
1502 /* Update the CFG for all queued instructions, taking special care of inserting
1503 code on edges between call and storing its return value. */
1506 commit_edge_insertions_watch_calls ()
1511 #ifdef ENABLE_CHECKING
1512 verify_flow_info ();
1516 bb = ENTRY_BLOCK_PTR;
1521 for (e = bb->succ; e; e = next)
1523 next = e->succ_next;
1525 commit_one_edge_insertion (e, true);
1528 if (++i >= n_basic_blocks)
1530 bb = BASIC_BLOCK (i);
1534 /* Print out one basic block with live information at start and end. */
1545 fprintf (outf, ";; Basic block %d, loop depth %d, count ",
1546 bb->index, bb->loop_depth);
1547 fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
1550 fputs (";; Predecessors: ", outf);
1551 for (e = bb->pred; e; e = e->pred_next)
1552 dump_edge_info (outf, e, 0);
1555 fputs (";; Registers live at start:", outf);
1556 dump_regset (bb->global_live_at_start, outf);
1559 for (insn = bb->head, last = NEXT_INSN (bb->end); insn != last;
1560 insn = NEXT_INSN (insn))
1561 print_rtl_single (outf, insn);
1563 fputs (";; Registers live at end:", outf);
1564 dump_regset (bb->global_live_at_end, outf);
1567 fputs (";; Successors: ", outf);
1568 for (e = bb->succ; e; e = e->succ_next)
1569 dump_edge_info (outf, e, 1);
1577 dump_bb (bb, stderr);
1584 dump_bb (BASIC_BLOCK (n), stderr);
1587 /* Like print_rtl, but also print out live information for the start of each
1591 print_rtl_with_bb (outf, rtx_first)
1598 fprintf (outf, "(nil)\n");
1602 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
1603 int max_uid = get_max_uid ();
1605 = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1607 = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1608 enum bb_state *in_bb_p
1609 = (enum bb_state *) xcalloc (max_uid, sizeof (enum bb_state));
1611 for (i = n_basic_blocks - 1; i >= 0; i--)
1613 basic_block bb = BASIC_BLOCK (i);
1616 start[INSN_UID (bb->head)] = bb;
1617 end[INSN_UID (bb->end)] = bb;
1618 for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x))
1620 enum bb_state state = IN_MULTIPLE_BB;
1622 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
1624 in_bb_p[INSN_UID (x)] = state;
1631 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
1636 if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
1638 fprintf (outf, ";; Start of basic block %d, registers live:",
1640 dump_regset (bb->global_live_at_start, outf);
1644 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
1645 && GET_CODE (tmp_rtx) != NOTE
1646 && GET_CODE (tmp_rtx) != BARRIER)
1647 fprintf (outf, ";; Insn is not within a basic block\n");
1648 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
1649 fprintf (outf, ";; Insn is in multiple basic blocks\n");
1651 did_output = print_rtl_single (outf, tmp_rtx);
1653 if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
1655 fprintf (outf, ";; End of basic block %d, registers live:\n",
1657 dump_regset (bb->global_live_at_end, outf);
1670 if (current_function_epilogue_delay_list != 0)
1672 fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
1673 for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0;
1674 tmp_rtx = XEXP (tmp_rtx, 1))
1675 print_rtl_single (outf, XEXP (tmp_rtx, 0));
1680 update_br_prob_note (bb)
1684 if (GET_CODE (bb->end) != JUMP_INSN)
1686 note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX);
1687 if (!note || INTVAL (XEXP (note, 0)) == BRANCH_EDGE (bb)->probability)
1689 XEXP (note, 0) = GEN_INT (BRANCH_EDGE (bb)->probability);
1692 /* Verify the CFG consistency. This function check some CFG invariants and
1693 aborts when something is wrong. Hope that this function will help to
1694 convert many optimization passes to preserve CFG consistent.
1696 Currently it does following checks:
1698 - test head/end pointers
1699 - overlapping of basic blocks
1700 - edge list correctness
1701 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1702 - tails of basic blocks (ensure that boundary is necessary)
1703 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1704 and NOTE_INSN_BASIC_BLOCK
1705 - check that all insns are in the basic blocks
1706 (except the switch handling code, barriers and notes)
1707 - check that all returns are followed by barriers
1709 In future it can be extended check a lot of other stuff as well
1710 (reachability of basic blocks, life information, etc. etc.). */
1715 const int max_uid = get_max_uid ();
1716 const rtx rtx_first = get_insns ();
1717 rtx last_head = get_last_insn ();
1718 basic_block *bb_info, *last_visited;
1719 size_t *edge_checksum;
1721 int i, last_bb_num_seen, num_bb_notes, err = 0;
1723 bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1724 last_visited = (basic_block *) xcalloc (n_basic_blocks + 2,
1725 sizeof (basic_block));
1726 edge_checksum = (size_t *) xcalloc (n_basic_blocks + 2, sizeof (size_t));
1728 for (i = n_basic_blocks - 1; i >= 0; i--)
1730 basic_block bb = BASIC_BLOCK (i);
1731 rtx head = bb->head;
1734 /* Verify the end of the basic block is in the INSN chain. */
1735 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
1741 error ("end insn %d for block %d not found in the insn stream",
1742 INSN_UID (end), bb->index);
1746 /* Work backwards from the end to the head of the basic block
1747 to verify the head is in the RTL chain. */
1748 for (; x != NULL_RTX; x = PREV_INSN (x))
1750 /* While walking over the insn chain, verify insns appear
1751 in only one basic block and initialize the BB_INFO array
1752 used by other passes. */
1753 if (bb_info[INSN_UID (x)] != NULL)
1755 error ("insn %d is in multiple basic blocks (%d and %d)",
1756 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
1760 bb_info[INSN_UID (x)] = bb;
1767 error ("head insn %d for block %d not found in the insn stream",
1768 INSN_UID (head), bb->index);
1775 /* Now check the basic blocks (boundaries etc.) */
1776 for (i = n_basic_blocks - 1; i >= 0; i--)
1778 basic_block bb = BASIC_BLOCK (i);
1779 int n_fallthru = 0, n_eh = 0, n_call = 0, n_abnormal = 0, n_branch = 0;
1783 if (INSN_P (bb->end)
1784 && (note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX))
1785 && bb->succ && bb->succ->succ_next
1786 && any_condjump_p (bb->end))
1788 if (INTVAL (XEXP (note, 0)) != BRANCH_EDGE (bb)->probability)
1790 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
1791 INTVAL (XEXP (note, 0)), BRANCH_EDGE (bb)->probability);
1797 error ("verify_flow_info: Wrong count of block %i %i",
1798 bb->index, (int)bb->count);
1801 if (bb->frequency < 0)
1803 error ("verify_flow_info: Wrong frequency of block %i %i",
1804 bb->index, bb->frequency);
1807 for (e = bb->succ; e; e = e->succ_next)
1809 if (last_visited [e->dest->index + 2] == bb)
1811 error ("verify_flow_info: Duplicate edge %i->%i",
1812 e->src->index, e->dest->index);
1815 if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
1817 error ("verify_flow_info: Wrong probability of edge %i->%i %i",
1818 e->src->index, e->dest->index, e->probability);
1823 error ("verify_flow_info: Wrong count of edge %i->%i %i",
1824 e->src->index, e->dest->index, (int)e->count);
1828 last_visited [e->dest->index + 2] = bb;
1830 if (e->flags & EDGE_FALLTHRU)
1833 if ((e->flags & ~EDGE_DFS_BACK) == 0)
1836 if (e->flags & EDGE_ABNORMAL_CALL)
1839 if (e->flags & EDGE_EH)
1841 else if (e->flags & EDGE_ABNORMAL)
1844 if ((e->flags & EDGE_FALLTHRU)
1845 && e->src != ENTRY_BLOCK_PTR
1846 && e->dest != EXIT_BLOCK_PTR)
1850 if (e->src->index + 1 != e->dest->index)
1853 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
1854 e->src->index, e->dest->index);
1858 for (insn = NEXT_INSN (e->src->end); insn != e->dest->head;
1859 insn = NEXT_INSN (insn))
1860 if (GET_CODE (insn) == BARRIER
1861 #ifndef CASE_DROPS_THROUGH
1864 || (INSN_P (insn) && ! JUMP_TABLE_DATA_P (insn))
1868 error ("verify_flow_info: Incorrect fallthru %i->%i",
1869 e->src->index, e->dest->index);
1870 fatal_insn ("wrong insn in the fallthru edge", insn);
1877 error ("verify_flow_info: Basic block %d succ edge is corrupted",
1879 fprintf (stderr, "Predecessor: ");
1880 dump_edge_info (stderr, e, 0);
1881 fprintf (stderr, "\nSuccessor: ");
1882 dump_edge_info (stderr, e, 1);
1883 fprintf (stderr, "\n");
1887 edge_checksum[e->dest->index + 2] += (size_t) e;
1890 if (n_eh && GET_CODE (PATTERN (bb->end)) != RESX
1891 && !find_reg_note (bb->end, REG_EH_REGION, NULL_RTX))
1893 error ("Missing REG_EH_REGION note in the end of bb %i", bb->index);
1897 && (GET_CODE (bb->end) != JUMP_INSN
1898 || (n_branch > 1 && (any_uncondjump_p (bb->end)
1899 || any_condjump_p (bb->end)))))
1901 error ("Too many outgoing branch edges from bb %i", bb->index);
1904 if (n_fallthru && any_uncondjump_p (bb->end))
1906 error ("Fallthru edge after unconditional jump %i", bb->index);
1909 if (n_branch != 1 && any_uncondjump_p (bb->end))
1911 error ("Wrong amount of branch edges after unconditional jump %i", bb->index);
1914 if (n_branch != 1 && any_condjump_p (bb->end)
1915 && JUMP_LABEL (bb->end) != BASIC_BLOCK (bb->index + 1)->head)
1917 error ("Wrong amount of branch edges after conditional jump %i", bb->index);
1920 if (n_call && GET_CODE (bb->end) != CALL_INSN)
1922 error ("Call edges for non-call insn in bb %i", bb->index);
1926 && (GET_CODE (bb->end) != CALL_INSN && n_call != n_abnormal)
1927 && (GET_CODE (bb->end) != JUMP_INSN
1928 || any_condjump_p (bb->end)
1929 || any_uncondjump_p (bb->end)))
1931 error ("Abnormal edges for no purpose in bb %i", bb->index);
1939 /* Ensure existence of barrier in BB with no fallthru edges. */
1940 for (insn = bb->end; !insn || GET_CODE (insn) != BARRIER;
1941 insn = NEXT_INSN (insn))
1943 || (GET_CODE (insn) == NOTE
1944 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK))
1946 error ("missing barrier after block %i", bb->index);
1952 for (e = bb->pred; e; e = e->pred_next)
1956 error ("basic block %d pred edge is corrupted", bb->index);
1957 fputs ("Predecessor: ", stderr);
1958 dump_edge_info (stderr, e, 0);
1959 fputs ("\nSuccessor: ", stderr);
1960 dump_edge_info (stderr, e, 1);
1961 fputc ('\n', stderr);
1964 edge_checksum[e->dest->index + 2] -= (size_t) e;
1967 for (x = bb->head; x != NEXT_INSN (bb->end); x = NEXT_INSN (x))
1968 if (basic_block_for_insn && BLOCK_FOR_INSN (x) != bb)
1971 if (! BLOCK_FOR_INSN (x))
1973 ("insn %d inside basic block %d but block_for_insn is NULL",
1974 INSN_UID (x), bb->index);
1977 ("insn %d inside basic block %d but block_for_insn is %i",
1978 INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index);
1983 /* OK pointers are correct. Now check the header of basic
1984 block. It ought to contain optional CODE_LABEL followed
1985 by NOTE_BASIC_BLOCK. */
1987 if (GET_CODE (x) == CODE_LABEL)
1991 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1999 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
2001 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2007 /* Do checks for empty blocks her. e */
2010 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
2012 if (NOTE_INSN_BASIC_BLOCK_P (x))
2014 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2015 INSN_UID (x), bb->index);
2022 if (GET_CODE (x) == JUMP_INSN
2023 || GET_CODE (x) == CODE_LABEL
2024 || GET_CODE (x) == BARRIER)
2026 error ("in basic block %d:", bb->index);
2027 fatal_insn ("flow control insn inside a basic block", x);
2032 /* Complete edge checksumming for ENTRY and EXIT. */
2036 for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
2037 edge_checksum[e->dest->index + 2] += (size_t) e;
2039 for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
2040 edge_checksum[e->dest->index + 2] -= (size_t) e;
2043 for (i = -2; i < n_basic_blocks; ++i)
2044 if (edge_checksum[i + 2])
2046 error ("basic block %i edge lists are corrupted", i);
2050 last_bb_num_seen = -1;
2052 for (x = rtx_first; x; x = NEXT_INSN (x))
2054 if (NOTE_INSN_BASIC_BLOCK_P (x))
2056 basic_block bb = NOTE_BASIC_BLOCK (x);
2059 if (bb->index != last_bb_num_seen + 1)
2060 internal_error ("basic blocks not numbered consecutively");
2062 last_bb_num_seen = bb->index;
2065 if (!bb_info[INSN_UID (x)])
2067 switch (GET_CODE (x))
2074 /* An addr_vec is placed outside any block block. */
2076 && GET_CODE (NEXT_INSN (x)) == JUMP_INSN
2077 && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
2078 || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
2081 /* But in any case, non-deletable labels can appear anywhere. */
2085 fatal_insn ("insn outside basic block", x);
2090 && GET_CODE (x) == JUMP_INSN
2091 && returnjump_p (x) && ! condjump_p (x)
2092 && ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER))
2093 fatal_insn ("return not followed by barrier", x);
2096 if (num_bb_notes != n_basic_blocks)
2098 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2099 num_bb_notes, n_basic_blocks);
2102 internal_error ("verify_flow_info failed");
2106 free (last_visited);
2107 free (edge_checksum);
2110 /* Assume that the preceding pass has possibly eliminated jump instructions
2111 or converted the unconditional jumps. Eliminate the edges from CFG.
2112 Return true if any edges are eliminated. */
2115 purge_dead_edges (bb)
2119 rtx insn = bb->end, note;
2120 bool purged = false;
2122 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2123 if (GET_CODE (insn) == INSN
2124 && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
2128 if (! may_trap_p (PATTERN (insn))
2129 || ((eqnote = find_reg_equal_equiv_note (insn))
2130 && ! may_trap_p (XEXP (eqnote, 0))))
2131 remove_note (insn, note);
2134 /* Cleanup abnormal edges caused by throwing insns that have been
2136 if (! can_throw_internal (bb->end))
2137 for (e = bb->succ; e; e = next)
2139 next = e->succ_next;
2140 if (e->flags & EDGE_EH)
2143 bb->flags |= BB_DIRTY;
2148 if (GET_CODE (insn) == JUMP_INSN)
2153 /* We do care only about conditional jumps and simplejumps. */
2154 if (!any_condjump_p (insn)
2155 && !returnjump_p (insn)
2156 && !simplejump_p (insn))
2159 /* Branch probability/prediction notes are defined only for
2160 condjumps. We've possibly turned condjump into simplejump. */
2161 if (simplejump_p (insn))
2163 note = find_reg_note (insn, REG_BR_PROB, NULL);
2165 remove_note (insn, note);
2166 while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
2167 remove_note (insn, note);
2170 for (e = bb->succ; e; e = next)
2172 next = e->succ_next;
2174 /* Avoid abnormal flags to leak from computed jumps turned
2175 into simplejumps. */
2177 e->flags &= ~EDGE_ABNORMAL;
2179 /* Check purposes we can have edge. */
2180 if ((e->flags & EDGE_FALLTHRU)
2181 && any_condjump_p (insn))
2183 else if (e->dest != EXIT_BLOCK_PTR
2184 && e->dest->head == JUMP_LABEL (insn))
2186 else if (e->dest == EXIT_BLOCK_PTR
2187 && returnjump_p (insn))
2190 bb->flags |= BB_DIRTY;
2195 if (!bb->succ || !purged)
2199 fprintf (rtl_dump_file, "Purged edges from bb %i\n", bb->index);
2204 /* Redistribute probabilities. */
2205 if (!bb->succ->succ_next)
2207 bb->succ->probability = REG_BR_PROB_BASE;
2208 bb->succ->count = bb->count;
2212 note = find_reg_note (insn, REG_BR_PROB, NULL);
2216 b = BRANCH_EDGE (bb);
2217 f = FALLTHRU_EDGE (bb);
2218 b->probability = INTVAL (XEXP (note, 0));
2219 f->probability = REG_BR_PROB_BASE - b->probability;
2220 b->count = bb->count * b->probability / REG_BR_PROB_BASE;
2221 f->count = bb->count * f->probability / REG_BR_PROB_BASE;
2227 /* If we don't see a jump insn, we don't know exactly why the block would
2228 have been broken at this point. Look for a simple, non-fallthru edge,
2229 as these are only created by conditional branches. If we find such an
2230 edge we know that there used to be a jump here and can then safely
2231 remove all non-fallthru edges. */
2232 for (e = bb->succ; e && (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU));
2239 for (e = bb->succ; e; e = next)
2241 next = e->succ_next;
2242 if (!(e->flags & EDGE_FALLTHRU))
2244 bb->flags |= BB_DIRTY;
2250 if (!bb->succ || bb->succ->succ_next)
2253 bb->succ->probability = REG_BR_PROB_BASE;
2254 bb->succ->count = bb->count;
2257 fprintf (rtl_dump_file, "Purged non-fallthru edges from bb %i\n",
2262 /* Search all basic blocks for potentially dead edges and purge them. Return
2263 true if some edge has been eliminated. */
2266 purge_all_dead_edges (update_life_p)
2269 int i, purged = false;
2274 blocks = sbitmap_alloc (n_basic_blocks);
2275 sbitmap_zero (blocks);
2278 for (i = 0; i < n_basic_blocks; i++)
2280 bool purged_here = purge_dead_edges (BASIC_BLOCK (i));
2282 purged |= purged_here;
2283 if (purged_here && update_life_p)
2284 SET_BIT (blocks, i);
2287 if (update_life_p && purged)
2288 update_life_info (blocks, UPDATE_LIFE_GLOBAL,
2289 PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
2290 | PROP_KILL_DEAD_CODE);
2293 sbitmap_free (blocks);