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.
252 AFTER is the basic block we should be put after. */
255 create_basic_block_structure (index, head, end, bb_note, after)
257 rtx head, end, bb_note;
263 && ! RTX_INTEGRATED_P (bb_note)
264 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
267 /* If we found an existing note, thread it back onto the chain. */
271 if (GET_CODE (head) == CODE_LABEL)
275 after = PREV_INSN (head);
279 if (after != bb_note && NEXT_INSN (after) != bb_note)
280 reorder_insns (bb_note, bb_note, after);
284 /* Otherwise we must create a note and a basic block structure. */
290 = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
291 else if (GET_CODE (head) == CODE_LABEL && end)
293 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
299 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
305 NOTE_BASIC_BLOCK (bb_note) = bb;
308 /* Always include the bb note in the block. */
309 if (NEXT_INSN (end) == bb_note)
316 link_block (bb, after);
317 BASIC_BLOCK (index) = bb;
318 if (basic_block_for_insn)
319 update_bb_for_insn (bb);
321 /* Tag the block so that we know it has been used when considering
322 other basic block notes. */
328 /* Create new basic block consisting of instructions in between HEAD and END
329 and place it to the BB chain after block AFTER. END can be NULL in to
330 create new empty basic block before HEAD. Both END and HEAD can be NULL to
331 create basic block at the end of INSN chain. */
334 create_basic_block (head, end, after)
340 int index = after->index + 1;
342 /* Place the new block just after the block being split. */
343 VARRAY_GROW (basic_block_info, ++n_basic_blocks);
345 /* Some parts of the compiler expect blocks to be number in
346 sequential order so insert the new block immediately after the
347 block being split.. */
348 for (i = n_basic_blocks - 1; i > index; --i)
350 basic_block tmp = BASIC_BLOCK (i - 1);
352 BASIC_BLOCK (i) = tmp;
356 bb = create_basic_block_structure (index, head, end, NULL, after);
361 /* Delete the insns in a (non-live) block. We physically delete every
362 non-deleted-note insn, and update the flow graph appropriately.
364 Return nonzero if we deleted an exception handler. */
366 /* ??? Preserving all such notes strikes me as wrong. It would be nice
367 to post-process the stream to remove empty blocks, loops, ranges, etc. */
370 flow_delete_block_noexpunge (b)
373 int deleted_handler = 0;
376 /* If the head of this block is a CODE_LABEL, then it might be the
377 label for an exception handler which can't be reached.
379 We need to remove the label from the exception_handler_label list
380 and remove the associated NOTE_INSN_EH_REGION_BEG and
381 NOTE_INSN_EH_REGION_END notes. */
383 /* Get rid of all NOTE_INSN_PREDICTIONs hanging before the block. */
385 for (insn = PREV_INSN (b->head); insn; insn = PREV_INSN (insn))
387 if (GET_CODE (insn) != NOTE)
389 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_PREDICTION)
390 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
395 never_reached_warning (insn, b->end);
397 if (GET_CODE (insn) == CODE_LABEL)
398 maybe_remove_eh_handler (insn);
400 /* Include any jump table following the basic block. */
402 if (GET_CODE (end) == JUMP_INSN
403 && (tmp = JUMP_LABEL (end)) != NULL_RTX
404 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
405 && GET_CODE (tmp) == JUMP_INSN
406 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
407 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
410 /* Include any barrier that may follow the basic block. */
411 tmp = next_nonnote_insn (end);
412 if (tmp && GET_CODE (tmp) == BARRIER)
415 /* Selectively delete the entire chain. */
417 delete_insn_chain (insn, end);
419 /* Remove the edges into and out of this block. Note that there may
420 indeed be edges in, if we are removing an unreachable loop. */
421 while (b->pred != NULL)
422 remove_edge (b->pred);
423 while (b->succ != NULL)
424 remove_edge (b->succ);
429 return deleted_handler;
433 flow_delete_block (b)
436 int deleted_handler = flow_delete_block_noexpunge (b);
438 /* Remove the basic block from the array, and compact behind it. */
441 return deleted_handler;
444 /* Records the basic block struct in BB_FOR_INSN, for every instruction
445 indexed by INSN_UID. MAX is the size of the array. */
448 compute_bb_for_insn (max)
453 if (basic_block_for_insn)
454 VARRAY_FREE (basic_block_for_insn);
456 VARRAY_BB_INIT (basic_block_for_insn, max, "basic_block_for_insn");
463 for (insn = bb->head; ; insn = NEXT_INSN (insn))
465 if (INSN_UID (insn) < max)
466 VARRAY_BB (basic_block_for_insn, INSN_UID (insn)) = bb;
474 /* Release the basic_block_for_insn array. */
479 if (basic_block_for_insn)
480 VARRAY_FREE (basic_block_for_insn);
482 basic_block_for_insn = 0;
485 /* Update insns block within BB. */
488 update_bb_for_insn (bb)
493 if (! basic_block_for_insn)
496 for (insn = bb->head; ; insn = NEXT_INSN (insn))
498 set_block_for_insn (insn, bb);
504 /* Record INSN's block as BB. */
507 set_block_for_insn (insn, bb)
511 size_t uid = INSN_UID (insn);
513 if (uid >= basic_block_for_insn->num_elements)
515 /* Add one-eighth the size so we don't keep calling xrealloc. */
516 size_t new_size = uid + (uid + 7) / 8;
518 VARRAY_GROW (basic_block_for_insn, new_size);
521 VARRAY_BB (basic_block_for_insn, uid) = bb;
524 /* Split a block BB after insn INSN creating a new fallthru edge.
525 Return the new edge. Note that to keep other parts of the compiler happy,
526 this function renumbers all the basic blocks so that the new
527 one has a number one greater than the block split. */
530 split_block (bb, insn)
538 /* There is no point splitting the block after its end. */
542 /* Create the new basic block. */
543 new_bb = create_basic_block (NEXT_INSN (insn), bb->end, bb);
544 new_bb->count = bb->count;
545 new_bb->frequency = bb->frequency;
546 new_bb->loop_depth = bb->loop_depth;
549 /* Redirect the outgoing edges. */
550 new_bb->succ = bb->succ;
552 for (e = new_bb->succ; e; e = e->succ_next)
555 new_edge = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
557 if (bb->global_live_at_start)
559 new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
560 new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
561 COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
563 /* We now have to calculate which registers are live at the end
564 of the split basic block and at the start of the new basic
565 block. Start with those registers that are known to be live
566 at the end of the original basic block and get
567 propagate_block to determine which registers are live. */
568 COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_end);
569 propagate_block (new_bb, new_bb->global_live_at_start, NULL, NULL, 0);
570 COPY_REG_SET (bb->global_live_at_end,
571 new_bb->global_live_at_start);
572 #ifdef HAVE_conditional_execution
573 /* In the presence of conditional execution we are not able to update
574 liveness precisely. */
575 if (reload_completed)
577 bb->flags |= BB_DIRTY;
578 new_bb->flags |= BB_DIRTY;
586 /* Blocks A and B are to be merged into a single block A. The insns
587 are already contiguous, hence `nomove'. */
590 merge_blocks_nomove (a, b)
593 rtx b_head = b->head, b_end = b->end, a_end = a->end;
594 rtx del_first = NULL_RTX, del_last = NULL_RTX;
598 /* If there was a CODE_LABEL beginning B, delete it. */
599 if (GET_CODE (b_head) == CODE_LABEL)
601 /* Detect basic blocks with nothing but a label. This can happen
602 in particular at the end of a function. */
606 del_first = del_last = b_head;
607 b_head = NEXT_INSN (b_head);
610 /* Delete the basic block note and handle blocks containing just that
612 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
620 b_head = NEXT_INSN (b_head);
623 /* If there was a jump out of A, delete it. */
624 if (GET_CODE (a_end) == JUMP_INSN)
628 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
629 if (GET_CODE (prev) != NOTE
630 || NOTE_LINE_NUMBER (prev) == NOTE_INSN_BASIC_BLOCK
637 /* If this was a conditional jump, we need to also delete
638 the insn that set cc0. */
639 if (only_sets_cc0_p (prev))
643 prev = prev_nonnote_insn (prev);
650 a_end = PREV_INSN (del_first);
652 else if (GET_CODE (NEXT_INSN (a_end)) == BARRIER)
653 del_first = NEXT_INSN (a_end);
655 /* Normally there should only be one successor of A and that is B, but
656 partway though the merge of blocks for conditional_execution we'll
657 be merging a TEST block with THEN and ELSE successors. Free the
658 whole lot of them and hope the caller knows what they're doing. */
660 remove_edge (a->succ);
662 /* Adjust the edges out of B for the new owner. */
663 for (e = b->succ; e; e = e->succ_next)
666 a->flags |= b->flags;
668 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
669 b->pred = b->succ = NULL;
670 a->global_live_at_end = b->global_live_at_end;
674 /* Delete everything marked above as well as crap that might be
675 hanging out between the two blocks. */
676 delete_insn_chain (del_first, del_last);
678 /* Reassociate the insns of B with A. */
681 if (basic_block_for_insn)
685 for (x = a_end; x != b_end; x = NEXT_INSN (x))
686 set_block_for_insn (x, a);
688 set_block_for_insn (b_end, a);
697 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
704 if (block == EXIT_BLOCK_PTR)
707 if (GET_CODE (block->head) != CODE_LABEL)
709 block->head = emit_label_before (gen_label_rtx (), block->head);
710 if (basic_block_for_insn)
711 set_block_for_insn (block->head, block);
717 /* Attempt to perform edge redirection by replacing possibly complex jump
718 instruction by unconditional jump or removing jump completely. This can
719 apply only if all edges now point to the same block. The parameters and
720 return values are equivalent to redirect_edge_and_branch. */
723 try_redirect_by_replacing_jump (e, target)
727 basic_block src = e->src;
728 rtx insn = src->end, kill_from;
733 /* Verify that all targets will be TARGET. */
734 for (tmp = src->succ; tmp; tmp = tmp->succ_next)
735 if (tmp->dest != target && tmp != e)
738 if (tmp || !onlyjump_p (insn))
740 if (reload_completed && JUMP_LABEL (insn)
741 && (table = NEXT_INSN (JUMP_LABEL (insn))) != NULL_RTX
742 && GET_CODE (table) == JUMP_INSN
743 && (GET_CODE (PATTERN (table)) == ADDR_VEC
744 || GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC))
747 /* Avoid removing branch with side effects. */
748 set = single_set (insn);
749 if (!set || side_effects_p (set))
752 /* In case we zap a conditional jump, we'll need to kill
753 the cc0 setter too. */
756 if (reg_mentioned_p (cc0_rtx, PATTERN (insn)))
757 kill_from = PREV_INSN (insn);
760 /* See if we can create the fallthru edge. */
761 if (can_fallthru (src, target))
764 fprintf (rtl_dump_file, "Removing jump %i.\n", INSN_UID (insn));
767 /* Selectively unlink whole insn chain. */
768 delete_insn_chain (kill_from, PREV_INSN (target->head));
771 /* If this already is simplejump, redirect it. */
772 else if (simplejump_p (insn))
774 if (e->dest == target)
777 fprintf (rtl_dump_file, "Redirecting jump %i from %i to %i.\n",
778 INSN_UID (insn), e->dest->index, target->index);
779 if (!redirect_jump (insn, block_label (target), 0))
781 if (target == EXIT_BLOCK_PTR)
787 /* Cannot do anything for target exit block. */
788 else if (target == EXIT_BLOCK_PTR)
791 /* Or replace possibly complicated jump insn by simple jump insn. */
794 rtx target_label = block_label (target);
797 emit_jump_insn_after (gen_jump (target_label), insn);
798 JUMP_LABEL (src->end) = target_label;
799 LABEL_NUSES (target_label)++;
801 fprintf (rtl_dump_file, "Replacing insn %i by jump %i\n",
802 INSN_UID (insn), INSN_UID (src->end));
805 delete_insn_chain (kill_from, insn);
807 /* Recognize a tablejump that we are converting to a
808 simple jump and remove its associated CODE_LABEL
809 and ADDR_VEC or ADDR_DIFF_VEC. */
810 if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
811 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
812 && GET_CODE (tmp) == JUMP_INSN
813 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
814 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
816 delete_insn_chain (JUMP_LABEL (insn), tmp);
819 barrier = next_nonnote_insn (src->end);
820 if (!barrier || GET_CODE (barrier) != BARRIER)
821 emit_barrier_after (src->end);
824 /* Keep only one edge out and set proper flags. */
825 while (src->succ->succ_next)
826 remove_edge (src->succ);
829 e->flags = EDGE_FALLTHRU;
833 e->probability = REG_BR_PROB_BASE;
834 e->count = src->count;
836 /* We don't want a block to end on a line-number note since that has
837 the potential of changing the code between -g and not -g. */
838 while (GET_CODE (e->src->end) == NOTE
839 && NOTE_LINE_NUMBER (e->src->end) >= 0)
840 delete_insn (e->src->end);
842 if (e->dest != target)
843 redirect_edge_succ (e, target);
848 /* Return last loop_beg note appearing after INSN, before start of next
849 basic block. Return INSN if there are no such notes.
851 When emitting jump to redirect an fallthru edge, it should always appear
852 after the LOOP_BEG notes, as loop optimizer expect loop to either start by
853 fallthru edge or jump following the LOOP_BEG note jumping to the loop exit
857 last_loop_beg_note (insn)
862 for (insn = NEXT_INSN (insn); insn && GET_CODE (insn) == NOTE
863 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK;
864 insn = NEXT_INSN (insn))
865 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
871 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
872 expense of adding new instructions or reordering basic blocks.
874 Function can be also called with edge destination equivalent to the TARGET.
875 Then it should try the simplifications and do nothing if none is possible.
877 Return true if transformation succeeded. We still return false in case E
878 already destinated TARGET and we didn't managed to simplify instruction
882 redirect_edge_and_branch (e, target)
887 rtx old_label = e->dest->head;
888 basic_block src = e->src;
891 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
894 if (try_redirect_by_replacing_jump (e, target))
897 /* Do this fast path late, as we want above code to simplify for cases
898 where called on single edge leaving basic block containing nontrivial
900 else if (e->dest == target)
903 /* We can only redirect non-fallthru edges of jump insn. */
904 if (e->flags & EDGE_FALLTHRU)
906 else if (GET_CODE (insn) != JUMP_INSN)
909 /* Recognize a tablejump and adjust all matching cases. */
910 if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
911 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
912 && GET_CODE (tmp) == JUMP_INSN
913 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
914 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
918 rtx new_label = block_label (target);
920 if (target == EXIT_BLOCK_PTR)
922 if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
923 vec = XVEC (PATTERN (tmp), 0);
925 vec = XVEC (PATTERN (tmp), 1);
927 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
928 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
930 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
931 --LABEL_NUSES (old_label);
932 ++LABEL_NUSES (new_label);
935 /* Handle casesi dispatch insns */
936 if ((tmp = single_set (insn)) != NULL
937 && SET_DEST (tmp) == pc_rtx
938 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
939 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
940 && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
942 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (VOIDmode,
944 --LABEL_NUSES (old_label);
945 ++LABEL_NUSES (new_label);
950 /* ?? We may play the games with moving the named labels from
951 one basic block to the other in case only one computed_jump is
953 if (computed_jump_p (insn)
954 /* A return instruction can't be redirected. */
955 || returnjump_p (insn))
958 /* If the insn doesn't go where we think, we're confused. */
959 if (JUMP_LABEL (insn) != old_label)
962 /* If the substitution doesn't succeed, die. This can happen
963 if the back end emitted unrecognizable instructions or if
964 target is exit block on some arches. */
965 if (!redirect_jump (insn, block_label (target), 0))
967 if (target == EXIT_BLOCK_PTR)
974 fprintf (rtl_dump_file, "Edge %i->%i redirected to %i\n",
975 e->src->index, e->dest->index, target->index);
977 if (e->dest != target)
978 redirect_edge_succ_nodup (e, target);
983 /* Like force_nonfallthru below, but additionally performs redirection
984 Used by redirect_edge_and_branch_force. */
987 force_nonfallthru_and_redirect (e, target)
991 basic_block jump_block, new_bb = NULL;
995 if (e->flags & EDGE_ABNORMAL)
997 else if (!(e->flags & EDGE_FALLTHRU))
999 else if (e->src == ENTRY_BLOCK_PTR)
1001 /* We can't redirect the entry block. Create an empty block at the
1002 start of the function which we use to add the new jump. */
1004 basic_block bb = create_basic_block (e->dest->head, NULL, ENTRY_BLOCK_PTR);
1006 /* Change the existing edge's source to be the new block, and add
1007 a new edge from the entry block to the new block. */
1009 for (pe1 = &ENTRY_BLOCK_PTR->succ; *pe1; pe1 = &(*pe1)->succ_next)
1012 *pe1 = e->succ_next;
1017 make_single_succ_edge (ENTRY_BLOCK_PTR, bb, EDGE_FALLTHRU);
1020 if (e->src->succ->succ_next)
1022 /* Create the new structures. */
1023 note = last_loop_beg_note (e->src->end);
1025 = create_basic_block (NEXT_INSN (note), NULL, e->src);
1026 jump_block->count = e->count;
1027 jump_block->frequency = EDGE_FREQUENCY (e);
1028 jump_block->loop_depth = target->loop_depth;
1030 if (target->global_live_at_start)
1032 jump_block->global_live_at_start
1033 = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1034 jump_block->global_live_at_end
1035 = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1036 COPY_REG_SET (jump_block->global_live_at_start,
1037 target->global_live_at_start);
1038 COPY_REG_SET (jump_block->global_live_at_end,
1039 target->global_live_at_start);
1043 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1044 new_edge->probability = e->probability;
1045 new_edge->count = e->count;
1047 /* Redirect old edge. */
1048 redirect_edge_pred (e, jump_block);
1049 e->probability = REG_BR_PROB_BASE;
1051 new_bb = jump_block;
1054 jump_block = e->src;
1056 e->flags &= ~EDGE_FALLTHRU;
1057 if (target == EXIT_BLOCK_PTR)
1060 emit_jump_insn_after (gen_return (), jump_block->end);
1066 rtx label = block_label (target);
1067 emit_jump_insn_after (gen_jump (label), jump_block->end);
1068 JUMP_LABEL (jump_block->end) = label;
1069 LABEL_NUSES (label)++;
1072 emit_barrier_after (jump_block->end);
1073 redirect_edge_succ_nodup (e, target);
1078 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1079 (and possibly create new basic block) to make edge non-fallthru.
1080 Return newly created BB or NULL if none. */
1083 force_nonfallthru (e)
1086 return force_nonfallthru_and_redirect (e, e->dest);
1089 /* Redirect edge even at the expense of creating new jump insn or
1090 basic block. Return new basic block if created, NULL otherwise.
1091 Abort if conversion is impossible. */
1094 redirect_edge_and_branch_force (e, target)
1098 if (redirect_edge_and_branch (e, target)
1099 || e->dest == target)
1102 /* In case the edge redirection failed, try to force it to be non-fallthru
1103 and redirect newly created simplejump. */
1104 return force_nonfallthru_and_redirect (e, target);
1107 /* The given edge should potentially be a fallthru edge. If that is in
1108 fact true, delete the jump and barriers that are in the way. */
1111 tidy_fallthru_edge (e, b, c)
1117 /* ??? In a late-running flow pass, other folks may have deleted basic
1118 blocks by nopping out blocks, leaving multiple BARRIERs between here
1119 and the target label. They ought to be chastized and fixed.
1121 We can also wind up with a sequence of undeletable labels between
1122 one block and the next.
1124 So search through a sequence of barriers, labels, and notes for
1125 the head of block C and assert that we really do fall through. */
1127 for (q = NEXT_INSN (b->end); q != c->head; q = NEXT_INSN (q))
1131 /* Remove what will soon cease being the jump insn from the source block.
1132 If block B consisted only of this single jump, turn it into a deleted
1135 if (GET_CODE (q) == JUMP_INSN
1137 && (any_uncondjump_p (q)
1138 || (b->succ == e && e->succ_next == NULL)))
1141 /* If this was a conditional jump, we need to also delete
1142 the insn that set cc0. */
1143 if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1149 /* We don't want a block to end on a line-number note since that has
1150 the potential of changing the code between -g and not -g. */
1151 while (GET_CODE (q) == NOTE && NOTE_LINE_NUMBER (q) >= 0)
1155 /* Selectively unlink the sequence. */
1156 if (q != PREV_INSN (c->head))
1157 delete_insn_chain (NEXT_INSN (q), PREV_INSN (c->head));
1159 e->flags |= EDGE_FALLTHRU;
1162 /* Fix up edges that now fall through, or rather should now fall through
1163 but previously required a jump around now deleted blocks. Simplify
1164 the search by only examining blocks numerically adjacent, since this
1165 is how find_basic_blocks created them. */
1168 tidy_fallthru_edges ()
1172 if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
1175 FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb)
1181 /* We care about simple conditional or unconditional jumps with
1184 If we had a conditional branch to the next instruction when
1185 find_basic_blocks was called, then there will only be one
1186 out edge for the block which ended with the conditional
1187 branch (since we do not create duplicate edges).
1189 Furthermore, the edge will be marked as a fallthru because we
1190 merge the flags for the duplicate edges. So we do not want to
1191 check that the edge is not a FALLTHRU edge. */
1193 if ((s = b->succ) != NULL
1194 && ! (s->flags & EDGE_COMPLEX)
1195 && s->succ_next == NULL
1197 /* If the jump insn has side effects, we can't tidy the edge. */
1198 && (GET_CODE (b->end) != JUMP_INSN
1199 || onlyjump_p (b->end)))
1200 tidy_fallthru_edge (s, b, c);
1204 /* Helper function for split_edge. Return true in case edge BB2 to BB1
1205 is back edge of syntactic loop. */
1208 back_edge_of_syntactic_loop_p (bb1, bb2)
1209 basic_block bb1, bb2;
1214 if (bb1->index > bb2->index)
1216 else if (bb1->index == bb2->index)
1219 for (insn = bb1->end; insn != bb2->head && count >= 0;
1220 insn = NEXT_INSN (insn))
1221 if (GET_CODE (insn) == NOTE)
1223 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1225 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1232 /* Split a (typically critical) edge. Return the new block.
1233 Abort on abnormal edges.
1235 ??? The code generally expects to be called on critical edges.
1236 The case of a block ending in an unconditional jump to a
1237 block with multiple predecessors is not handled optimally. */
1240 split_edge (edge_in)
1247 /* Abnormal edges cannot be split. */
1248 if ((edge_in->flags & EDGE_ABNORMAL) != 0)
1251 /* We are going to place the new block in front of edge destination.
1252 Avoid existence of fallthru predecessors. */
1253 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1257 for (e = edge_in->dest->pred; e; e = e->pred_next)
1258 if (e->flags & EDGE_FALLTHRU)
1262 force_nonfallthru (e);
1265 /* Create the basic block note.
1267 Where we place the note can have a noticeable impact on the generated
1268 code. Consider this cfg:
1278 If we need to insert an insn on the edge from block 0 to block 1,
1279 we want to ensure the instructions we insert are outside of any
1280 loop notes that physically sit between block 0 and block 1. Otherwise
1281 we confuse the loop optimizer into thinking the loop is a phony. */
1283 if (edge_in->dest != EXIT_BLOCK_PTR
1284 && PREV_INSN (edge_in->dest->head)
1285 && GET_CODE (PREV_INSN (edge_in->dest->head)) == NOTE
1286 && (NOTE_LINE_NUMBER (PREV_INSN (edge_in->dest->head))
1287 == NOTE_INSN_LOOP_BEG)
1288 && !back_edge_of_syntactic_loop_p (edge_in->dest, edge_in->src))
1289 before = PREV_INSN (edge_in->dest->head);
1290 else if (edge_in->dest != EXIT_BLOCK_PTR)
1291 before = edge_in->dest->head;
1295 bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
1296 bb->count = edge_in->count;
1297 bb->frequency = EDGE_FREQUENCY (edge_in);
1299 /* ??? This info is likely going to be out of date very soon. */
1300 if (edge_in->dest->global_live_at_start)
1302 bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1303 bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1304 COPY_REG_SET (bb->global_live_at_start,
1305 edge_in->dest->global_live_at_start);
1306 COPY_REG_SET (bb->global_live_at_end,
1307 edge_in->dest->global_live_at_start);
1310 edge_out = make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1312 /* For non-fallthry edges, we must adjust the predecessor's
1313 jump instruction to target our new block. */
1314 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1316 if (!redirect_edge_and_branch (edge_in, bb))
1320 redirect_edge_succ (edge_in, bb);
1325 /* Queue instructions for insertion on an edge between two basic blocks.
1326 The new instructions and basic blocks (if any) will not appear in the
1327 CFG until commit_edge_insertions is called. */
1330 insert_insn_on_edge (pattern, e)
1334 /* We cannot insert instructions on an abnormal critical edge.
1335 It will be easier to find the culprit if we die now. */
1336 if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
1339 if (e->insns == NULL_RTX)
1342 push_to_sequence (e->insns);
1344 emit_insn (pattern);
1346 e->insns = get_insns ();
1350 /* Update the CFG for the instructions queued on edge E. */
1353 commit_one_edge_insertion (e, watch_calls)
1357 rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
1360 /* Pull the insns off the edge now since the edge might go away. */
1362 e->insns = NULL_RTX;
1364 /* Special case -- avoid inserting code between call and storing
1365 its return value. */
1366 if (watch_calls && (e->flags & EDGE_FALLTHRU) && !e->dest->pred->pred_next
1367 && e->src != ENTRY_BLOCK_PTR
1368 && GET_CODE (e->src->end) == CALL_INSN)
1370 rtx next = next_nonnote_insn (e->src->end);
1372 after = e->dest->head;
1373 /* The first insn after the call may be a stack pop, skip it. */
1375 && keep_with_call_p (next))
1378 next = next_nonnote_insn (next);
1382 if (!before && !after)
1384 /* Figure out where to put these things. If the destination has
1385 one predecessor, insert there. Except for the exit block. */
1386 if (e->dest->pred->pred_next == NULL && e->dest != EXIT_BLOCK_PTR)
1390 /* Get the location correct wrt a code label, and "nice" wrt
1391 a basic block note, and before everything else. */
1393 if (GET_CODE (tmp) == CODE_LABEL)
1394 tmp = NEXT_INSN (tmp);
1395 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1396 tmp = NEXT_INSN (tmp);
1397 if (tmp == bb->head)
1400 after = PREV_INSN (tmp);
1402 after = get_last_insn ();
1405 /* If the source has one successor and the edge is not abnormal,
1406 insert there. Except for the entry block. */
1407 else if ((e->flags & EDGE_ABNORMAL) == 0
1408 && e->src->succ->succ_next == NULL
1409 && e->src != ENTRY_BLOCK_PTR)
1413 /* It is possible to have a non-simple jump here. Consider a target
1414 where some forms of unconditional jumps clobber a register. This
1415 happens on the fr30 for example.
1417 We know this block has a single successor, so we can just emit
1418 the queued insns before the jump. */
1419 if (GET_CODE (bb->end) == JUMP_INSN)
1420 for (before = bb->end;
1421 GET_CODE (PREV_INSN (before)) == NOTE
1422 && NOTE_LINE_NUMBER (PREV_INSN (before)) ==
1423 NOTE_INSN_LOOP_BEG; before = PREV_INSN (before))
1427 /* We'd better be fallthru, or we've lost track of what's what. */
1428 if ((e->flags & EDGE_FALLTHRU) == 0)
1434 /* Otherwise we must split the edge. */
1437 bb = split_edge (e);
1442 /* Now that we've found the spot, do the insertion. */
1446 emit_insns_before (insns, before);
1447 last = prev_nonnote_insn (before);
1450 last = emit_insns_after (insns, after);
1452 if (returnjump_p (last))
1454 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1455 This is not currently a problem because this only happens
1456 for the (single) epilogue, which already has a fallthru edge
1460 if (e->dest != EXIT_BLOCK_PTR
1461 || e->succ_next != NULL || (e->flags & EDGE_FALLTHRU) == 0)
1464 e->flags &= ~EDGE_FALLTHRU;
1465 emit_barrier_after (last);
1468 delete_insn (before);
1470 else if (GET_CODE (last) == JUMP_INSN)
1473 find_sub_basic_blocks (bb);
1476 /* Update the CFG for all queued instructions. */
1479 commit_edge_insertions ()
1483 #ifdef ENABLE_CHECKING
1484 verify_flow_info ();
1487 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1491 for (e = bb->succ; e; e = next)
1493 next = e->succ_next;
1495 commit_one_edge_insertion (e, false);
1500 /* Update the CFG for all queued instructions, taking special care of inserting
1501 code on edges between call and storing its return value. */
1504 commit_edge_insertions_watch_calls ()
1508 #ifdef ENABLE_CHECKING
1509 verify_flow_info ();
1512 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1516 for (e = bb->succ; e; e = next)
1518 next = e->succ_next;
1520 commit_one_edge_insertion (e, true);
1525 /* Print out one basic block with live information at start and end. */
1536 fprintf (outf, ";; Basic block %d, loop depth %d, count ",
1537 bb->index, bb->loop_depth);
1538 fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
1541 fputs (";; Predecessors: ", outf);
1542 for (e = bb->pred; e; e = e->pred_next)
1543 dump_edge_info (outf, e, 0);
1546 fputs (";; Registers live at start:", outf);
1547 dump_regset (bb->global_live_at_start, outf);
1550 for (insn = bb->head, last = NEXT_INSN (bb->end); insn != last;
1551 insn = NEXT_INSN (insn))
1552 print_rtl_single (outf, insn);
1554 fputs (";; Registers live at end:", outf);
1555 dump_regset (bb->global_live_at_end, outf);
1558 fputs (";; Successors: ", outf);
1559 for (e = bb->succ; e; e = e->succ_next)
1560 dump_edge_info (outf, e, 1);
1568 dump_bb (bb, stderr);
1575 dump_bb (BASIC_BLOCK (n), stderr);
1578 /* Like print_rtl, but also print out live information for the start of each
1582 print_rtl_with_bb (outf, rtx_first)
1589 fprintf (outf, "(nil)\n");
1592 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
1593 int max_uid = get_max_uid ();
1595 = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1597 = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1598 enum bb_state *in_bb_p
1599 = (enum bb_state *) xcalloc (max_uid, sizeof (enum bb_state));
1603 FOR_EACH_BB_REVERSE (bb)
1607 start[INSN_UID (bb->head)] = bb;
1608 end[INSN_UID (bb->end)] = bb;
1609 for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x))
1611 enum bb_state state = IN_MULTIPLE_BB;
1613 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
1615 in_bb_p[INSN_UID (x)] = state;
1622 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
1626 if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
1628 fprintf (outf, ";; Start of basic block %d, registers live:",
1630 dump_regset (bb->global_live_at_start, outf);
1634 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
1635 && GET_CODE (tmp_rtx) != NOTE
1636 && GET_CODE (tmp_rtx) != BARRIER)
1637 fprintf (outf, ";; Insn is not within a basic block\n");
1638 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
1639 fprintf (outf, ";; Insn is in multiple basic blocks\n");
1641 did_output = print_rtl_single (outf, tmp_rtx);
1643 if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
1645 fprintf (outf, ";; End of basic block %d, registers live:\n",
1647 dump_regset (bb->global_live_at_end, outf);
1660 if (current_function_epilogue_delay_list != 0)
1662 fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
1663 for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0;
1664 tmp_rtx = XEXP (tmp_rtx, 1))
1665 print_rtl_single (outf, XEXP (tmp_rtx, 0));
1670 update_br_prob_note (bb)
1674 if (GET_CODE (bb->end) != JUMP_INSN)
1676 note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX);
1677 if (!note || INTVAL (XEXP (note, 0)) == BRANCH_EDGE (bb)->probability)
1679 XEXP (note, 0) = GEN_INT (BRANCH_EDGE (bb)->probability);
1682 /* Verify the CFG consistency. This function check some CFG invariants and
1683 aborts when something is wrong. Hope that this function will help to
1684 convert many optimization passes to preserve CFG consistent.
1686 Currently it does following checks:
1688 - test head/end pointers
1689 - overlapping of basic blocks
1690 - edge list correctness
1691 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1692 - tails of basic blocks (ensure that boundary is necessary)
1693 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1694 and NOTE_INSN_BASIC_BLOCK
1695 - check that all insns are in the basic blocks
1696 (except the switch handling code, barriers and notes)
1697 - check that all returns are followed by barriers
1699 In future it can be extended check a lot of other stuff as well
1700 (reachability of basic blocks, life information, etc. etc.). */
1705 const int max_uid = get_max_uid ();
1706 const rtx rtx_first = get_insns ();
1707 rtx last_head = get_last_insn ();
1708 basic_block *bb_info, *last_visited;
1709 size_t *edge_checksum;
1711 int i, num_bb_notes, err = 0;
1712 basic_block bb, last_bb_seen;
1714 bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1715 last_visited = (basic_block *) xcalloc (last_basic_block + 2,
1716 sizeof (basic_block));
1717 edge_checksum = (size_t *) xcalloc (last_basic_block + 2, sizeof (size_t));
1719 /* Check bb chain & numbers. */
1720 last_bb_seen = ENTRY_BLOCK_PTR;
1721 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
1723 if (bb != EXIT_BLOCK_PTR
1724 && bb != BASIC_BLOCK (bb->index))
1726 error ("bb %d on wrong place", bb->index);
1730 if (bb->prev_bb != last_bb_seen)
1732 error ("prev_bb of %d should be %d, not %d",
1733 bb->index, last_bb_seen->index, bb->prev_bb->index);
1737 /* For now, also check that we didn't change the order. */
1738 if (bb != EXIT_BLOCK_PTR && bb->index != last_bb_seen->index + 1)
1740 error ("Wrong order of blocks %d and %d",
1741 last_bb_seen->index, bb->index);
1745 if (bb == EXIT_BLOCK_PTR && last_bb_seen->index != n_basic_blocks - 1)
1747 error ("Only %d of %d blocks in chain",
1748 last_bb_seen->index + 1, n_basic_blocks);
1755 FOR_EACH_BB_REVERSE (bb)
1757 rtx head = bb->head;
1760 /* Verify the end of the basic block is in the INSN chain. */
1761 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
1767 error ("end insn %d for block %d not found in the insn stream",
1768 INSN_UID (end), bb->index);
1772 /* Work backwards from the end to the head of the basic block
1773 to verify the head is in the RTL chain. */
1774 for (; x != NULL_RTX; x = PREV_INSN (x))
1776 /* While walking over the insn chain, verify insns appear
1777 in only one basic block and initialize the BB_INFO array
1778 used by other passes. */
1779 if (bb_info[INSN_UID (x)] != NULL)
1781 error ("insn %d is in multiple basic blocks (%d and %d)",
1782 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
1786 bb_info[INSN_UID (x)] = bb;
1793 error ("head insn %d for block %d not found in the insn stream",
1794 INSN_UID (head), bb->index);
1801 /* Now check the basic blocks (boundaries etc.) */
1802 FOR_EACH_BB_REVERSE (bb)
1804 int n_fallthru = 0, n_eh = 0, n_call = 0, n_abnormal = 0, n_branch = 0;
1808 if (INSN_P (bb->end)
1809 && (note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX))
1810 && bb->succ && bb->succ->succ_next
1811 && any_condjump_p (bb->end))
1813 if (INTVAL (XEXP (note, 0)) != BRANCH_EDGE (bb)->probability)
1815 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
1816 INTVAL (XEXP (note, 0)), BRANCH_EDGE (bb)->probability);
1822 error ("verify_flow_info: Wrong count of block %i %i",
1823 bb->index, (int)bb->count);
1826 if (bb->frequency < 0)
1828 error ("verify_flow_info: Wrong frequency of block %i %i",
1829 bb->index, bb->frequency);
1832 for (e = bb->succ; e; e = e->succ_next)
1834 if (last_visited [e->dest->index + 2] == bb)
1836 error ("verify_flow_info: Duplicate edge %i->%i",
1837 e->src->index, e->dest->index);
1840 if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
1842 error ("verify_flow_info: Wrong probability of edge %i->%i %i",
1843 e->src->index, e->dest->index, e->probability);
1848 error ("verify_flow_info: Wrong count of edge %i->%i %i",
1849 e->src->index, e->dest->index, (int)e->count);
1853 last_visited [e->dest->index + 2] = bb;
1855 if (e->flags & EDGE_FALLTHRU)
1858 if ((e->flags & ~EDGE_DFS_BACK) == 0)
1861 if (e->flags & EDGE_ABNORMAL_CALL)
1864 if (e->flags & EDGE_EH)
1866 else if (e->flags & EDGE_ABNORMAL)
1869 if ((e->flags & EDGE_FALLTHRU)
1870 && e->src != ENTRY_BLOCK_PTR
1871 && e->dest != EXIT_BLOCK_PTR)
1875 if (e->src->next_bb != e->dest)
1878 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
1879 e->src->index, e->dest->index);
1883 for (insn = NEXT_INSN (e->src->end); insn != e->dest->head;
1884 insn = NEXT_INSN (insn))
1885 if (GET_CODE (insn) == BARRIER
1886 #ifndef CASE_DROPS_THROUGH
1889 || (INSN_P (insn) && ! JUMP_TABLE_DATA_P (insn))
1893 error ("verify_flow_info: Incorrect fallthru %i->%i",
1894 e->src->index, e->dest->index);
1895 fatal_insn ("wrong insn in the fallthru edge", insn);
1902 error ("verify_flow_info: Basic block %d succ edge is corrupted",
1904 fprintf (stderr, "Predecessor: ");
1905 dump_edge_info (stderr, e, 0);
1906 fprintf (stderr, "\nSuccessor: ");
1907 dump_edge_info (stderr, e, 1);
1908 fprintf (stderr, "\n");
1912 edge_checksum[e->dest->index + 2] += (size_t) e;
1915 if (n_eh && GET_CODE (PATTERN (bb->end)) != RESX
1916 && !find_reg_note (bb->end, REG_EH_REGION, NULL_RTX))
1918 error ("Missing REG_EH_REGION note in the end of bb %i", bb->index);
1922 && (GET_CODE (bb->end) != JUMP_INSN
1923 || (n_branch > 1 && (any_uncondjump_p (bb->end)
1924 || any_condjump_p (bb->end)))))
1926 error ("Too many outgoing branch edges from bb %i", bb->index);
1929 if (n_fallthru && any_uncondjump_p (bb->end))
1931 error ("Fallthru edge after unconditional jump %i", bb->index);
1934 if (n_branch != 1 && any_uncondjump_p (bb->end))
1936 error ("Wrong amount of branch edges after unconditional jump %i", bb->index);
1939 if (n_branch != 1 && any_condjump_p (bb->end)
1940 && JUMP_LABEL (bb->end) != bb->next_bb->head)
1942 error ("Wrong amount of branch edges after conditional jump %i", bb->index);
1945 if (n_call && GET_CODE (bb->end) != CALL_INSN)
1947 error ("Call edges for non-call insn in bb %i", bb->index);
1951 && (GET_CODE (bb->end) != CALL_INSN && n_call != n_abnormal)
1952 && (GET_CODE (bb->end) != JUMP_INSN
1953 || any_condjump_p (bb->end)
1954 || any_uncondjump_p (bb->end)))
1956 error ("Abnormal edges for no purpose in bb %i", bb->index);
1964 /* Ensure existence of barrier in BB with no fallthru edges. */
1965 for (insn = bb->end; !insn || GET_CODE (insn) != BARRIER;
1966 insn = NEXT_INSN (insn))
1968 || (GET_CODE (insn) == NOTE
1969 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK))
1971 error ("missing barrier after block %i", bb->index);
1977 for (e = bb->pred; e; e = e->pred_next)
1981 error ("basic block %d pred edge is corrupted", bb->index);
1982 fputs ("Predecessor: ", stderr);
1983 dump_edge_info (stderr, e, 0);
1984 fputs ("\nSuccessor: ", stderr);
1985 dump_edge_info (stderr, e, 1);
1986 fputc ('\n', stderr);
1989 edge_checksum[e->dest->index + 2] -= (size_t) e;
1992 for (x = bb->head; x != NEXT_INSN (bb->end); x = NEXT_INSN (x))
1993 if (basic_block_for_insn && BLOCK_FOR_INSN (x) != bb)
1996 if (! BLOCK_FOR_INSN (x))
1998 ("insn %d inside basic block %d but block_for_insn is NULL",
1999 INSN_UID (x), bb->index);
2002 ("insn %d inside basic block %d but block_for_insn is %i",
2003 INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index);
2008 /* OK pointers are correct. Now check the header of basic
2009 block. It ought to contain optional CODE_LABEL followed
2010 by NOTE_BASIC_BLOCK. */
2012 if (GET_CODE (x) == CODE_LABEL)
2016 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2024 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
2026 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2032 /* Do checks for empty blocks her. e */
2035 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
2037 if (NOTE_INSN_BASIC_BLOCK_P (x))
2039 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2040 INSN_UID (x), bb->index);
2047 if (GET_CODE (x) == JUMP_INSN
2048 || GET_CODE (x) == CODE_LABEL
2049 || GET_CODE (x) == BARRIER)
2051 error ("in basic block %d:", bb->index);
2052 fatal_insn ("flow control insn inside a basic block", x);
2057 /* Complete edge checksumming for ENTRY and EXIT. */
2061 for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
2062 edge_checksum[e->dest->index + 2] += (size_t) e;
2064 for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
2065 edge_checksum[e->dest->index + 2] -= (size_t) e;
2068 for (i = -2; i < n_basic_blocks; ++i)
2069 if (edge_checksum[i + 2])
2071 error ("basic block %i edge lists are corrupted", i);
2076 last_bb_seen = ENTRY_BLOCK_PTR;
2078 for (x = rtx_first; x; x = NEXT_INSN (x))
2080 if (NOTE_INSN_BASIC_BLOCK_P (x))
2082 basic_block bb = NOTE_BASIC_BLOCK (x);
2085 if (bb != last_bb_seen->next_bb)
2086 internal_error ("basic blocks not numbered consecutively");
2091 if (!bb_info[INSN_UID (x)])
2093 switch (GET_CODE (x))
2100 /* An addr_vec is placed outside any block block. */
2102 && GET_CODE (NEXT_INSN (x)) == JUMP_INSN
2103 && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
2104 || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
2107 /* But in any case, non-deletable labels can appear anywhere. */
2111 fatal_insn ("insn outside basic block", x);
2116 && GET_CODE (x) == JUMP_INSN
2117 && returnjump_p (x) && ! condjump_p (x)
2118 && ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER))
2119 fatal_insn ("return not followed by barrier", x);
2122 if (num_bb_notes != n_basic_blocks)
2124 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2125 num_bb_notes, n_basic_blocks);
2128 internal_error ("verify_flow_info failed");
2132 free (last_visited);
2133 free (edge_checksum);
2136 /* Assume that the preceding pass has possibly eliminated jump instructions
2137 or converted the unconditional jumps. Eliminate the edges from CFG.
2138 Return true if any edges are eliminated. */
2141 purge_dead_edges (bb)
2145 rtx insn = bb->end, note;
2146 bool purged = false;
2148 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2149 if (GET_CODE (insn) == INSN
2150 && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
2154 if (! may_trap_p (PATTERN (insn))
2155 || ((eqnote = find_reg_equal_equiv_note (insn))
2156 && ! may_trap_p (XEXP (eqnote, 0))))
2157 remove_note (insn, note);
2160 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
2161 for (e = bb->succ; e; e = next)
2163 next = e->succ_next;
2164 if (e->flags & EDGE_EH)
2166 if (can_throw_internal (bb->end))
2169 else if (e->flags & EDGE_ABNORMAL_CALL)
2171 if (GET_CODE (bb->end) == CALL_INSN
2172 && (! (note = find_reg_note (insn, REG_EH_REGION, NULL))
2173 || INTVAL (XEXP (note, 0)) >= 0))
2180 bb->flags |= BB_DIRTY;
2184 if (GET_CODE (insn) == JUMP_INSN)
2189 /* We do care only about conditional jumps and simplejumps. */
2190 if (!any_condjump_p (insn)
2191 && !returnjump_p (insn)
2192 && !simplejump_p (insn))
2195 /* Branch probability/prediction notes are defined only for
2196 condjumps. We've possibly turned condjump into simplejump. */
2197 if (simplejump_p (insn))
2199 note = find_reg_note (insn, REG_BR_PROB, NULL);
2201 remove_note (insn, note);
2202 while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
2203 remove_note (insn, note);
2206 for (e = bb->succ; e; e = next)
2208 next = e->succ_next;
2210 /* Avoid abnormal flags to leak from computed jumps turned
2211 into simplejumps. */
2213 e->flags &= ~EDGE_ABNORMAL;
2215 /* See if this edge is one we should keep. */
2216 if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
2217 /* A conditional jump can fall through into the next
2218 block, so we should keep the edge. */
2220 else if (e->dest != EXIT_BLOCK_PTR
2221 && e->dest->head == JUMP_LABEL (insn))
2222 /* If the destination block is the target of the jump,
2225 else if (e->dest == EXIT_BLOCK_PTR && returnjump_p (insn))
2226 /* If the destination block is the exit block, and this
2227 instruction is a return, then keep the edge. */
2229 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
2230 /* Keep the edges that correspond to exceptions thrown by
2231 this instruction. */
2234 /* We do not need this edge. */
2235 bb->flags |= BB_DIRTY;
2240 if (!bb->succ || !purged)
2244 fprintf (rtl_dump_file, "Purged edges from bb %i\n", bb->index);
2249 /* Redistribute probabilities. */
2250 if (!bb->succ->succ_next)
2252 bb->succ->probability = REG_BR_PROB_BASE;
2253 bb->succ->count = bb->count;
2257 note = find_reg_note (insn, REG_BR_PROB, NULL);
2261 b = BRANCH_EDGE (bb);
2262 f = FALLTHRU_EDGE (bb);
2263 b->probability = INTVAL (XEXP (note, 0));
2264 f->probability = REG_BR_PROB_BASE - b->probability;
2265 b->count = bb->count * b->probability / REG_BR_PROB_BASE;
2266 f->count = bb->count * f->probability / REG_BR_PROB_BASE;
2272 /* If we don't see a jump insn, we don't know exactly why the block would
2273 have been broken at this point. Look for a simple, non-fallthru edge,
2274 as these are only created by conditional branches. If we find such an
2275 edge we know that there used to be a jump here and can then safely
2276 remove all non-fallthru edges. */
2277 for (e = bb->succ; e && (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU));
2284 for (e = bb->succ; e; e = next)
2286 next = e->succ_next;
2287 if (!(e->flags & EDGE_FALLTHRU))
2289 bb->flags |= BB_DIRTY;
2295 if (!bb->succ || bb->succ->succ_next)
2298 bb->succ->probability = REG_BR_PROB_BASE;
2299 bb->succ->count = bb->count;
2302 fprintf (rtl_dump_file, "Purged non-fallthru edges from bb %i\n",
2307 /* Search all basic blocks for potentially dead edges and purge them. Return
2308 true if some edge has been eliminated. */
2311 purge_all_dead_edges (update_life_p)
2320 blocks = sbitmap_alloc (last_basic_block);
2321 sbitmap_zero (blocks);
2326 bool purged_here = purge_dead_edges (bb);
2328 purged |= purged_here;
2329 if (purged_here && update_life_p)
2330 SET_BIT (blocks, bb->index);
2333 if (update_life_p && purged)
2334 update_life_info (blocks, UPDATE_LIFE_GLOBAL,
2335 PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
2336 | PROP_KILL_DEAD_CODE);
2339 sbitmap_free (blocks);