1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 /* This file contains low level functions to manipulate the CFG and analyze it
23 that are aware of the RTL intermediate language.
25 Available functionality:
26 - CFG-aware instruction chain manipulation
27 delete_insn, delete_insn_chain
28 - Basic block manipulation
29 create_basic_block, flow_delete_block, split_block,
31 - Infrastructure to determine quickly basic block for insn
32 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
33 - Edge redirection with updating and optimizing of insn chain
34 block_label, redirect_edge_and_branch,
35 redirect_edge_and_branch_force, tidy_fallthru_edge, force_nonfallthru
36 - Edge splitting and commiting to edges
37 split_edge, insert_insn_on_edge, commit_edge_insertions
38 - Dumping and debugging
39 print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
40 - Consistency checking
42 - CFG updating after constant propagation
43 purge_dead_edges, purge_all_dead_edges */
49 #include "hard-reg-set.h"
50 #include "basic-block.h"
60 /* Stubs in case we don't have a return insn. */
63 #define gen_return() NULL_RTX
66 /* The basic block structure for every insn, indexed by uid. */
67 varray_type basic_block_for_insn;
69 /* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */
70 /* ??? Should probably be using LABEL_NUSES instead. It would take a
71 bit of surgery to be able to use or co-opt the routines in jump. */
73 rtx tail_recursion_label_list;
75 static int can_delete_note_p PARAMS ((rtx));
76 static int can_delete_label_p PARAMS ((rtx));
77 static void commit_one_edge_insertion PARAMS ((edge, int));
78 static bool try_redirect_by_replacing_jump PARAMS ((edge, basic_block));
79 static rtx last_loop_beg_note PARAMS ((rtx));
80 static bool back_edge_of_syntactic_loop_p PARAMS ((basic_block, basic_block));
81 static basic_block force_nonfallthru_and_redirect PARAMS ((edge, basic_block));
83 /* Return true if NOTE is not one of the ones that must be kept paired,
84 so that we may simply delete it. */
87 can_delete_note_p (note)
90 return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED
91 || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK);
94 /* True if a given label can be deleted. */
97 can_delete_label_p (label)
100 return (!LABEL_PRESERVE_P (label)
101 /* User declared labels must be preserved. */
102 && LABEL_NAME (label) == 0
103 && !in_expr_list_p (forced_labels, label)
104 && !in_expr_list_p (label_value_list, label)
105 && !in_expr_list_p (exception_handler_labels, label));
108 /* Delete INSN by patching it out. Return the next insn. */
114 rtx next = NEXT_INSN (insn);
116 bool really_delete = true;
118 if (GET_CODE (insn) == CODE_LABEL)
120 /* Some labels can't be directly removed from the INSN chain, as they
121 might be references via variables, constant pool etc.
122 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
123 if (! can_delete_label_p (insn))
125 const char *name = LABEL_NAME (insn);
127 really_delete = false;
128 PUT_CODE (insn, NOTE);
129 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL;
130 NOTE_SOURCE_FILE (insn) = name;
133 remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
138 /* If this insn has already been deleted, something is very wrong. */
139 if (INSN_DELETED_P (insn))
142 INSN_DELETED_P (insn) = 1;
145 /* If deleting a jump, decrement the use count of the label. Deleting
146 the label itself should happen in the normal course of block merging. */
147 if (GET_CODE (insn) == JUMP_INSN
149 && GET_CODE (JUMP_LABEL (insn)) == CODE_LABEL)
150 LABEL_NUSES (JUMP_LABEL (insn))--;
152 /* Also if deleting an insn that references a label. */
153 else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX
154 && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
155 LABEL_NUSES (XEXP (note, 0))--;
157 if (GET_CODE (insn) == JUMP_INSN
158 && (GET_CODE (PATTERN (insn)) == ADDR_VEC
159 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
161 rtx pat = PATTERN (insn);
162 int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC;
163 int len = XVECLEN (pat, diff_vec_p);
166 for (i = 0; i < len; i++)
168 rtx label = XEXP (XVECEXP (pat, diff_vec_p, i), 0);
170 /* When deleting code in bulk (e.g. removing many unreachable
171 blocks) we can delete a label that's a target of the vector
172 before deleting the vector itself. */
173 if (GET_CODE (label) != NOTE)
174 LABEL_NUSES (label)--;
181 /* Like delete_insn but also purge dead edges from BB. */
183 delete_insn_and_edges (insn)
189 if (basic_block_for_insn
191 && (unsigned int)INSN_UID (insn) < basic_block_for_insn->num_elements
192 && BLOCK_FOR_INSN (insn)
193 && BLOCK_FOR_INSN (insn)->end == insn)
195 x = delete_insn (insn);
197 purge_dead_edges (BLOCK_FOR_INSN (insn));
201 /* Unlink a chain of insns between START and FINISH, leaving notes
202 that must be paired. */
205 delete_insn_chain (start, finish)
210 /* Unchain the insns one by one. It would be quicker to delete all of these
211 with a single unchaining, rather than one at a time, but we need to keep
215 next = NEXT_INSN (start);
216 if (GET_CODE (start) == NOTE && !can_delete_note_p (start))
219 next = delete_insn (start);
227 /* Like delete_insn but also purge dead edges from BB. */
229 delete_insn_chain_and_edges (first, last)
234 if (basic_block_for_insn
236 && (unsigned int)INSN_UID (last) < basic_block_for_insn->num_elements
237 && BLOCK_FOR_INSN (last)
238 && BLOCK_FOR_INSN (last)->end == last)
240 delete_insn_chain (first, last);
242 purge_dead_edges (BLOCK_FOR_INSN (last));
245 /* Create a new basic block consisting of the instructions between HEAD and END
246 inclusive. This function is designed to allow fast BB construction - reuses
247 the note and basic block struct in BB_NOTE, if any and do not grow
248 BASIC_BLOCK chain and should be used directly only by CFG construction code.
249 END can be NULL in to create new empty basic block before HEAD. Both END
250 and HEAD can be NULL to create basic block at the end of INSN chain. */
253 create_basic_block_structure (index, head, end, bb_note)
255 rtx head, end, bb_note;
260 && ! RTX_INTEGRATED_P (bb_note)
261 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
264 /* If we found an existing note, thread it back onto the chain. */
268 if (GET_CODE (head) == CODE_LABEL)
272 after = PREV_INSN (head);
276 if (after != bb_note && NEXT_INSN (after) != bb_note)
277 reorder_insns (bb_note, bb_note, after);
281 /* Otherwise we must create a note and a basic block structure. */
287 = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
288 else if (GET_CODE (head) == CODE_LABEL && end)
290 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
296 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
302 NOTE_BASIC_BLOCK (bb_note) = bb;
305 /* Always include the bb note in the block. */
306 if (NEXT_INSN (end) == bb_note)
313 BASIC_BLOCK (index) = bb;
314 if (basic_block_for_insn)
315 update_bb_for_insn (bb);
317 /* Tag the block so that we know it has been used when considering
318 other basic block notes. */
324 /* Create new basic block consisting of instructions in between HEAD and END
325 and place it to the BB chain at position INDEX. END can be NULL in to
326 create new empty basic block before HEAD. Both END and HEAD can be NULL to
327 create basic block at the end of INSN chain. */
330 create_basic_block (index, head, end)
337 /* Place the new block just after the block being split. */
338 VARRAY_GROW (basic_block_info, ++n_basic_blocks);
340 /* Some parts of the compiler expect blocks to be number in
341 sequential order so insert the new block immediately after the
342 block being split.. */
343 for (i = n_basic_blocks - 1; i > index; --i)
345 basic_block tmp = BASIC_BLOCK (i - 1);
347 BASIC_BLOCK (i) = tmp;
351 bb = create_basic_block_structure (index, head, end, NULL);
356 /* Delete the insns in a (non-live) block. We physically delete every
357 non-deleted-note insn, and update the flow graph appropriately.
359 Return nonzero if we deleted an exception handler. */
361 /* ??? Preserving all such notes strikes me as wrong. It would be nice
362 to post-process the stream to remove empty blocks, loops, ranges, etc. */
365 flow_delete_block (b)
368 int deleted_handler = 0;
371 /* If the head of this block is a CODE_LABEL, then it might be the
372 label for an exception handler which can't be reached.
374 We need to remove the label from the exception_handler_label list
375 and remove the associated NOTE_INSN_EH_REGION_BEG and
376 NOTE_INSN_EH_REGION_END notes. */
380 never_reached_warning (insn, b->end);
382 if (GET_CODE (insn) == CODE_LABEL)
383 maybe_remove_eh_handler (insn);
385 /* Include any jump table following the basic block. */
387 if (GET_CODE (end) == JUMP_INSN
388 && (tmp = JUMP_LABEL (end)) != NULL_RTX
389 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
390 && GET_CODE (tmp) == JUMP_INSN
391 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
392 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
395 /* Include any barrier that may follow the basic block. */
396 tmp = next_nonnote_insn (end);
397 if (tmp && GET_CODE (tmp) == BARRIER)
400 /* Selectively delete the entire chain. */
402 delete_insn_chain (insn, end);
404 /* Remove the edges into and out of this block. Note that there may
405 indeed be edges in, if we are removing an unreachable loop. */
406 while (b->pred != NULL)
407 remove_edge (b->pred);
408 while (b->succ != NULL)
409 remove_edge (b->succ);
414 /* Remove the basic block from the array, and compact behind it. */
417 return deleted_handler;
420 /* Records the basic block struct in BB_FOR_INSN, for every instruction
421 indexed by INSN_UID. MAX is the size of the array. */
424 compute_bb_for_insn (max)
429 if (basic_block_for_insn)
430 VARRAY_FREE (basic_block_for_insn);
432 VARRAY_BB_INIT (basic_block_for_insn, max, "basic_block_for_insn");
434 for (i = 0; i < n_basic_blocks; ++i)
436 basic_block bb = BASIC_BLOCK (i);
440 for (insn = bb->head; ; insn = NEXT_INSN (insn))
442 if (INSN_UID (insn) < max)
443 VARRAY_BB (basic_block_for_insn, INSN_UID (insn)) = bb;
451 /* Release the basic_block_for_insn array. */
456 if (basic_block_for_insn)
457 VARRAY_FREE (basic_block_for_insn);
459 basic_block_for_insn = 0;
462 /* Update insns block within BB. */
465 update_bb_for_insn (bb)
470 if (! basic_block_for_insn)
473 for (insn = bb->head; ; insn = NEXT_INSN (insn))
475 set_block_for_insn (insn, bb);
481 /* Record INSN's block as BB. */
484 set_block_for_insn (insn, bb)
488 size_t uid = INSN_UID (insn);
490 if (uid >= basic_block_for_insn->num_elements)
492 /* Add one-eighth the size so we don't keep calling xrealloc. */
493 size_t new_size = uid + (uid + 7) / 8;
495 VARRAY_GROW (basic_block_for_insn, new_size);
498 VARRAY_BB (basic_block_for_insn, uid) = bb;
501 /* Split a block BB after insn INSN creating a new fallthru edge.
502 Return the new edge. Note that to keep other parts of the compiler happy,
503 this function renumbers all the basic blocks so that the new
504 one has a number one greater than the block split. */
507 split_block (bb, insn)
515 /* There is no point splitting the block after its end. */
519 /* Create the new basic block. */
520 new_bb = create_basic_block (bb->index + 1, NEXT_INSN (insn), bb->end);
521 new_bb->count = bb->count;
522 new_bb->frequency = bb->frequency;
523 new_bb->loop_depth = bb->loop_depth;
526 /* Redirect the outgoing edges. */
527 new_bb->succ = bb->succ;
529 for (e = new_bb->succ; e; e = e->succ_next)
532 new_edge = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
534 if (bb->global_live_at_start)
536 new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
537 new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
538 COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
540 /* We now have to calculate which registers are live at the end
541 of the split basic block and at the start of the new basic
542 block. Start with those registers that are known to be live
543 at the end of the original basic block and get
544 propagate_block to determine which registers are live. */
545 COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_end);
546 propagate_block (new_bb, new_bb->global_live_at_start, NULL, NULL, 0);
547 COPY_REG_SET (bb->global_live_at_end,
548 new_bb->global_live_at_start);
554 /* Blocks A and B are to be merged into a single block A. The insns
555 are already contiguous, hence `nomove'. */
558 merge_blocks_nomove (a, b)
561 rtx b_head = b->head, b_end = b->end, a_end = a->end;
562 rtx del_first = NULL_RTX, del_last = NULL_RTX;
566 /* If there was a CODE_LABEL beginning B, delete it. */
567 if (GET_CODE (b_head) == CODE_LABEL)
569 /* Detect basic blocks with nothing but a label. This can happen
570 in particular at the end of a function. */
574 del_first = del_last = b_head;
575 b_head = NEXT_INSN (b_head);
578 /* Delete the basic block note and handle blocks containing just that
580 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
588 b_head = NEXT_INSN (b_head);
591 /* If there was a jump out of A, delete it. */
592 if (GET_CODE (a_end) == JUMP_INSN)
596 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
597 if (GET_CODE (prev) != NOTE
598 || NOTE_LINE_NUMBER (prev) == NOTE_INSN_BASIC_BLOCK
605 /* If this was a conditional jump, we need to also delete
606 the insn that set cc0. */
607 if (only_sets_cc0_p (prev))
611 prev = prev_nonnote_insn (prev);
618 a_end = PREV_INSN (del_first);
620 else if (GET_CODE (NEXT_INSN (a_end)) == BARRIER)
621 del_first = NEXT_INSN (a_end);
623 /* Normally there should only be one successor of A and that is B, but
624 partway though the merge of blocks for conditional_execution we'll
625 be merging a TEST block with THEN and ELSE successors. Free the
626 whole lot of them and hope the caller knows what they're doing. */
628 remove_edge (a->succ);
630 /* Adjust the edges out of B for the new owner. */
631 for (e = b->succ; e; e = e->succ_next)
634 a->flags |= b->flags;
636 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
637 b->pred = b->succ = NULL;
638 a->global_live_at_end = b->global_live_at_end;
642 /* Delete everything marked above as well as crap that might be
643 hanging out between the two blocks. */
644 delete_insn_chain (del_first, del_last);
646 /* Reassociate the insns of B with A. */
649 if (basic_block_for_insn)
653 for (x = a_end; x != b_end; x = NEXT_INSN (x))
654 BLOCK_FOR_INSN (x) = a;
656 BLOCK_FOR_INSN (b_end) = a;
665 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
672 if (block == EXIT_BLOCK_PTR)
675 if (GET_CODE (block->head) != CODE_LABEL)
677 block->head = emit_label_before (gen_label_rtx (), block->head);
678 if (basic_block_for_insn)
679 set_block_for_insn (block->head, block);
685 /* Attempt to perform edge redirection by replacing possibly complex jump
686 instruction by unconditional jump or removing jump completely. This can
687 apply only if all edges now point to the same block. The parameters and
688 return values are equivalent to redirect_edge_and_branch. */
691 try_redirect_by_replacing_jump (e, target)
695 basic_block src = e->src;
696 rtx insn = src->end, kill_from;
701 /* Verify that all targets will be TARGET. */
702 for (tmp = src->succ; tmp; tmp = tmp->succ_next)
703 if (tmp->dest != target && tmp != e)
706 if (tmp || !onlyjump_p (insn))
709 /* Avoid removing branch with side effects. */
710 set = single_set (insn);
711 if (!set || side_effects_p (set))
714 /* In case we zap a conditional jump, we'll need to kill
715 the cc0 setter too. */
718 if (reg_mentioned_p (cc0_rtx, PATTERN (insn)))
719 kill_from = PREV_INSN (insn);
722 /* See if we can create the fallthru edge. */
723 if (can_fallthru (src, target))
726 fprintf (rtl_dump_file, "Removing jump %i.\n", INSN_UID (insn));
729 /* Selectively unlink whole insn chain. */
730 delete_insn_chain (kill_from, PREV_INSN (target->head));
733 /* If this already is simplejump, redirect it. */
734 else if (simplejump_p (insn))
736 if (e->dest == target)
739 fprintf (rtl_dump_file, "Redirecting jump %i from %i to %i.\n",
740 INSN_UID (insn), e->dest->index, target->index);
741 if (!redirect_jump (insn, block_label (target), 0))
743 if (target == EXIT_BLOCK_PTR)
749 /* Cannot do anything for target exit block. */
750 else if (target == EXIT_BLOCK_PTR)
753 /* Or replace possibly complicated jump insn by simple jump insn. */
756 rtx target_label = block_label (target);
759 emit_jump_insn_after (gen_jump (target_label), insn);
760 JUMP_LABEL (src->end) = target_label;
761 LABEL_NUSES (target_label)++;
763 fprintf (rtl_dump_file, "Replacing insn %i by jump %i\n",
764 INSN_UID (insn), INSN_UID (src->end));
767 delete_insn_chain (kill_from, insn);
769 /* Recognize a tablejump that we are converting to a
770 simple jump and remove its associated CODE_LABEL
771 and ADDR_VEC or ADDR_DIFF_VEC. */
772 if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
773 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
774 && GET_CODE (tmp) == JUMP_INSN
775 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
776 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
778 delete_insn_chain (JUMP_LABEL (insn), tmp);
781 barrier = next_nonnote_insn (src->end);
782 if (!barrier || GET_CODE (barrier) != BARRIER)
783 emit_barrier_after (src->end);
786 /* Keep only one edge out and set proper flags. */
787 while (src->succ->succ_next)
788 remove_edge (src->succ);
791 e->flags = EDGE_FALLTHRU;
795 e->probability = REG_BR_PROB_BASE;
796 e->count = src->count;
798 /* We don't want a block to end on a line-number note since that has
799 the potential of changing the code between -g and not -g. */
800 while (GET_CODE (e->src->end) == NOTE
801 && NOTE_LINE_NUMBER (e->src->end) >= 0)
802 delete_insn (e->src->end);
804 if (e->dest != target)
805 redirect_edge_succ (e, target);
810 /* Return last loop_beg note appearing after INSN, before start of next
811 basic block. Return INSN if there are no such notes.
813 When emitting jump to redirect an fallthru edge, it should always appear
814 after the LOOP_BEG notes, as loop optimizer expect loop to either start by
815 fallthru edge or jump following the LOOP_BEG note jumping to the loop exit
819 last_loop_beg_note (insn)
824 for (insn = NEXT_INSN (insn); insn && GET_CODE (insn) == NOTE
825 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK;
826 insn = NEXT_INSN (insn))
827 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
833 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
834 expense of adding new instructions or reordering basic blocks.
836 Function can be also called with edge destination equivalent to the TARGET.
837 Then it should try the simplifications and do nothing if none is possible.
839 Return true if transformation succeeded. We still return false in case E
840 already destinated TARGET and we didn't managed to simplify instruction
844 redirect_edge_and_branch (e, target)
849 rtx old_label = e->dest->head;
850 basic_block src = e->src;
853 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
856 if (try_redirect_by_replacing_jump (e, target))
859 /* Do this fast path late, as we want above code to simplify for cases
860 where called on single edge leaving basic block containing nontrivial
862 else if (e->dest == target)
865 /* We can only redirect non-fallthru edges of jump insn. */
866 if (e->flags & EDGE_FALLTHRU)
868 else if (GET_CODE (insn) != JUMP_INSN)
871 /* Recognize a tablejump and adjust all matching cases. */
872 if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
873 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
874 && GET_CODE (tmp) == JUMP_INSN
875 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
876 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
880 rtx new_label = block_label (target);
882 if (target == EXIT_BLOCK_PTR)
884 if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
885 vec = XVEC (PATTERN (tmp), 0);
887 vec = XVEC (PATTERN (tmp), 1);
889 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
890 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
892 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
893 --LABEL_NUSES (old_label);
894 ++LABEL_NUSES (new_label);
897 /* Handle casesi dispatch insns */
898 if ((tmp = single_set (insn)) != NULL
899 && SET_DEST (tmp) == pc_rtx
900 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
901 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
902 && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
904 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (VOIDmode,
906 --LABEL_NUSES (old_label);
907 ++LABEL_NUSES (new_label);
912 /* ?? We may play the games with moving the named labels from
913 one basic block to the other in case only one computed_jump is
915 if (computed_jump_p (insn)
916 /* A return instruction can't be redirected. */
917 || returnjump_p (insn))
920 /* If the insn doesn't go where we think, we're confused. */
921 if (JUMP_LABEL (insn) != old_label)
924 /* If the substitution doesn't succeed, die. This can happen
925 if the back end emitted unrecognizable instructions or if
926 target is exit block on some arches. */
927 if (!redirect_jump (insn, block_label (target), 0))
929 if (target == EXIT_BLOCK_PTR)
936 fprintf (rtl_dump_file, "Edge %i->%i redirected to %i\n",
937 e->src->index, e->dest->index, target->index);
939 if (e->dest != target)
940 redirect_edge_succ_nodup (e, target);
945 /* Like force_nonfallthru below, but additionally performs redirection
946 Used by redirect_edge_and_branch_force. */
949 force_nonfallthru_and_redirect (e, target)
953 basic_block jump_block, new_bb = NULL;
957 if (e->flags & EDGE_ABNORMAL)
959 else if (!(e->flags & EDGE_FALLTHRU))
961 else if (e->src == ENTRY_BLOCK_PTR)
963 /* We can't redirect the entry block. Create an empty block at the
964 start of the function which we use to add the new jump. */
966 basic_block bb = create_basic_block (0, e->dest->head, NULL);
968 /* Change the existing edge's source to be the new block, and add
969 a new edge from the entry block to the new block. */
971 for (pe1 = &ENTRY_BLOCK_PTR->succ; *pe1; pe1 = &(*pe1)->succ_next)
979 make_single_succ_edge (ENTRY_BLOCK_PTR, bb, EDGE_FALLTHRU);
982 if (e->src->succ->succ_next)
984 /* Create the new structures. */
985 note = last_loop_beg_note (e->src->end);
987 = create_basic_block (e->src->index + 1, NEXT_INSN (note), NULL);
988 jump_block->count = e->count;
989 jump_block->frequency = EDGE_FREQUENCY (e);
990 jump_block->loop_depth = target->loop_depth;
992 if (target->global_live_at_start)
994 jump_block->global_live_at_start
995 = OBSTACK_ALLOC_REG_SET (&flow_obstack);
996 jump_block->global_live_at_end
997 = OBSTACK_ALLOC_REG_SET (&flow_obstack);
998 COPY_REG_SET (jump_block->global_live_at_start,
999 target->global_live_at_start);
1000 COPY_REG_SET (jump_block->global_live_at_end,
1001 target->global_live_at_start);
1005 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1006 new_edge->probability = e->probability;
1007 new_edge->count = e->count;
1009 /* Redirect old edge. */
1010 redirect_edge_pred (e, jump_block);
1011 e->probability = REG_BR_PROB_BASE;
1013 new_bb = jump_block;
1016 jump_block = e->src;
1018 e->flags &= ~EDGE_FALLTHRU;
1019 if (target == EXIT_BLOCK_PTR)
1022 emit_jump_insn_after (gen_return (), jump_block->end);
1028 rtx label = block_label (target);
1029 emit_jump_insn_after (gen_jump (label), jump_block->end);
1030 JUMP_LABEL (jump_block->end) = label;
1031 LABEL_NUSES (label)++;
1034 emit_barrier_after (jump_block->end);
1035 redirect_edge_succ_nodup (e, target);
1040 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1041 (and possibly create new basic block) to make edge non-fallthru.
1042 Return newly created BB or NULL if none. */
1045 force_nonfallthru (e)
1048 return force_nonfallthru_and_redirect (e, e->dest);
1051 /* Redirect edge even at the expense of creating new jump insn or
1052 basic block. Return new basic block if created, NULL otherwise.
1053 Abort if conversion is impossible. */
1056 redirect_edge_and_branch_force (e, target)
1060 if (redirect_edge_and_branch (e, target)
1061 || e->dest == target)
1064 /* In case the edge redirection failed, try to force it to be non-fallthru
1065 and redirect newly created simplejump. */
1066 return force_nonfallthru_and_redirect (e, target);
1069 /* The given edge should potentially be a fallthru edge. If that is in
1070 fact true, delete the jump and barriers that are in the way. */
1073 tidy_fallthru_edge (e, b, c)
1079 /* ??? In a late-running flow pass, other folks may have deleted basic
1080 blocks by nopping out blocks, leaving multiple BARRIERs between here
1081 and the target label. They ought to be chastized and fixed.
1083 We can also wind up with a sequence of undeletable labels between
1084 one block and the next.
1086 So search through a sequence of barriers, labels, and notes for
1087 the head of block C and assert that we really do fall through. */
1089 if (next_real_insn (b->end) != next_real_insn (PREV_INSN (c->head)))
1092 /* Remove what will soon cease being the jump insn from the source block.
1093 If block B consisted only of this single jump, turn it into a deleted
1096 if (GET_CODE (q) == JUMP_INSN
1098 && (any_uncondjump_p (q)
1099 || (b->succ == e && e->succ_next == NULL)))
1102 /* If this was a conditional jump, we need to also delete
1103 the insn that set cc0. */
1104 if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1110 /* We don't want a block to end on a line-number note since that has
1111 the potential of changing the code between -g and not -g. */
1112 while (GET_CODE (q) == NOTE && NOTE_LINE_NUMBER (q) >= 0)
1116 /* Selectively unlink the sequence. */
1117 if (q != PREV_INSN (c->head))
1118 delete_insn_chain (NEXT_INSN (q), PREV_INSN (c->head));
1120 e->flags |= EDGE_FALLTHRU;
1123 /* Fix up edges that now fall through, or rather should now fall through
1124 but previously required a jump around now deleted blocks. Simplify
1125 the search by only examining blocks numerically adjacent, since this
1126 is how find_basic_blocks created them. */
1129 tidy_fallthru_edges ()
1133 for (i = 1; i < n_basic_blocks; i++)
1135 basic_block b = BASIC_BLOCK (i - 1);
1136 basic_block c = BASIC_BLOCK (i);
1139 /* We care about simple conditional or unconditional jumps with
1142 If we had a conditional branch to the next instruction when
1143 find_basic_blocks was called, then there will only be one
1144 out edge for the block which ended with the conditional
1145 branch (since we do not create duplicate edges).
1147 Furthermore, the edge will be marked as a fallthru because we
1148 merge the flags for the duplicate edges. So we do not want to
1149 check that the edge is not a FALLTHRU edge. */
1151 if ((s = b->succ) != NULL
1152 && ! (s->flags & EDGE_COMPLEX)
1153 && s->succ_next == NULL
1155 /* If the jump insn has side effects, we can't tidy the edge. */
1156 && (GET_CODE (b->end) != JUMP_INSN
1157 || onlyjump_p (b->end)))
1158 tidy_fallthru_edge (s, b, c);
1162 /* Helper function for split_edge. Return true in case edge BB2 to BB1
1163 is back edge of syntactic loop. */
1166 back_edge_of_syntactic_loop_p (bb1, bb2)
1167 basic_block bb1, bb2;
1172 if (bb1->index > bb2->index)
1174 else if (bb1->index == bb2->index)
1177 for (insn = bb1->end; insn != bb2->head && count >= 0;
1178 insn = NEXT_INSN (insn))
1179 if (GET_CODE (insn) == NOTE)
1181 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1183 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1190 /* Split a (typically critical) edge. Return the new block.
1191 Abort on abnormal edges.
1193 ??? The code generally expects to be called on critical edges.
1194 The case of a block ending in an unconditional jump to a
1195 block with multiple predecessors is not handled optimally. */
1198 split_edge (edge_in)
1205 /* Abnormal edges cannot be split. */
1206 if ((edge_in->flags & EDGE_ABNORMAL) != 0)
1209 /* We are going to place the new block in front of edge destination.
1210 Avoid existence of fallthru predecessors. */
1211 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1215 for (e = edge_in->dest->pred; e; e = e->pred_next)
1216 if (e->flags & EDGE_FALLTHRU)
1220 force_nonfallthru (e);
1223 /* Create the basic block note.
1225 Where we place the note can have a noticeable impact on the generated
1226 code. Consider this cfg:
1236 If we need to insert an insn on the edge from block 0 to block 1,
1237 we want to ensure the instructions we insert are outside of any
1238 loop notes that physically sit between block 0 and block 1. Otherwise
1239 we confuse the loop optimizer into thinking the loop is a phony. */
1241 if (edge_in->dest != EXIT_BLOCK_PTR
1242 && PREV_INSN (edge_in->dest->head)
1243 && GET_CODE (PREV_INSN (edge_in->dest->head)) == NOTE
1244 && (NOTE_LINE_NUMBER (PREV_INSN (edge_in->dest->head))
1245 == NOTE_INSN_LOOP_BEG)
1246 && !back_edge_of_syntactic_loop_p (edge_in->dest, edge_in->src))
1247 before = PREV_INSN (edge_in->dest->head);
1248 else if (edge_in->dest != EXIT_BLOCK_PTR)
1249 before = edge_in->dest->head;
1253 bb = create_basic_block (edge_in->dest == EXIT_BLOCK_PTR ? n_basic_blocks
1254 : edge_in->dest->index, before, NULL);
1255 bb->count = edge_in->count;
1256 bb->frequency = EDGE_FREQUENCY (edge_in);
1258 /* ??? This info is likely going to be out of date very soon. */
1259 if (edge_in->dest->global_live_at_start)
1261 bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1262 bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1263 COPY_REG_SET (bb->global_live_at_start,
1264 edge_in->dest->global_live_at_start);
1265 COPY_REG_SET (bb->global_live_at_end,
1266 edge_in->dest->global_live_at_start);
1269 edge_out = make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1271 /* For non-fallthry edges, we must adjust the predecessor's
1272 jump instruction to target our new block. */
1273 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1275 if (!redirect_edge_and_branch (edge_in, bb))
1279 redirect_edge_succ (edge_in, bb);
1284 /* Queue instructions for insertion on an edge between two basic blocks.
1285 The new instructions and basic blocks (if any) will not appear in the
1286 CFG until commit_edge_insertions is called. */
1289 insert_insn_on_edge (pattern, e)
1293 /* We cannot insert instructions on an abnormal critical edge.
1294 It will be easier to find the culprit if we die now. */
1295 if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
1298 if (e->insns == NULL_RTX)
1301 push_to_sequence (e->insns);
1303 emit_insn (pattern);
1305 e->insns = get_insns ();
1309 /* Update the CFG for the instructions queued on edge E. */
1312 commit_one_edge_insertion (e, watch_calls)
1316 rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
1319 /* Pull the insns off the edge now since the edge might go away. */
1321 e->insns = NULL_RTX;
1323 /* Special case -- avoid inserting code between call and storing
1324 its return value. */
1325 if (watch_calls && (e->flags & EDGE_FALLTHRU) && !e->dest->pred->pred_next
1326 && e->src != ENTRY_BLOCK_PTR
1327 && GET_CODE (e->src->end) == CALL_INSN)
1329 rtx next = next_nonnote_insn (e->src->end);
1331 after = e->dest->head;
1332 /* The first insn after the call may be a stack pop, skip it. */
1334 && keep_with_call_p (next))
1337 next = next_nonnote_insn (next);
1341 if (!before && !after)
1343 /* Figure out where to put these things. If the destination has
1344 one predecessor, insert there. Except for the exit block. */
1345 if (e->dest->pred->pred_next == NULL && e->dest != EXIT_BLOCK_PTR)
1349 /* Get the location correct wrt a code label, and "nice" wrt
1350 a basic block note, and before everything else. */
1352 if (GET_CODE (tmp) == CODE_LABEL)
1353 tmp = NEXT_INSN (tmp);
1354 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1355 tmp = NEXT_INSN (tmp);
1356 if (tmp == bb->head)
1359 after = PREV_INSN (tmp);
1361 after = get_last_insn ();
1364 /* If the source has one successor and the edge is not abnormal,
1365 insert there. Except for the entry block. */
1366 else if ((e->flags & EDGE_ABNORMAL) == 0
1367 && e->src->succ->succ_next == NULL
1368 && e->src != ENTRY_BLOCK_PTR)
1372 /* It is possible to have a non-simple jump here. Consider a target
1373 where some forms of unconditional jumps clobber a register. This
1374 happens on the fr30 for example.
1376 We know this block has a single successor, so we can just emit
1377 the queued insns before the jump. */
1378 if (GET_CODE (bb->end) == JUMP_INSN)
1379 for (before = bb->end;
1380 GET_CODE (PREV_INSN (before)) == NOTE
1381 && NOTE_LINE_NUMBER (PREV_INSN (before)) ==
1382 NOTE_INSN_LOOP_BEG; before = PREV_INSN (before))
1386 /* We'd better be fallthru, or we've lost track of what's what. */
1387 if ((e->flags & EDGE_FALLTHRU) == 0)
1393 /* Otherwise we must split the edge. */
1396 bb = split_edge (e);
1401 /* Now that we've found the spot, do the insertion. */
1405 emit_insns_before (insns, before);
1406 last = prev_nonnote_insn (before);
1409 last = emit_insns_after (insns, after);
1411 if (returnjump_p (last))
1413 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1414 This is not currently a problem because this only happens
1415 for the (single) epilogue, which already has a fallthru edge
1419 if (e->dest != EXIT_BLOCK_PTR
1420 || e->succ_next != NULL || (e->flags & EDGE_FALLTHRU) == 0)
1423 e->flags &= ~EDGE_FALLTHRU;
1424 emit_barrier_after (last);
1427 delete_insn (before);
1429 else if (GET_CODE (last) == JUMP_INSN)
1432 find_sub_basic_blocks (bb);
1435 /* Update the CFG for all queued instructions. */
1438 commit_edge_insertions ()
1443 #ifdef ENABLE_CHECKING
1444 verify_flow_info ();
1448 bb = ENTRY_BLOCK_PTR;
1453 for (e = bb->succ; e; e = next)
1455 next = e->succ_next;
1457 commit_one_edge_insertion (e, false);
1460 if (++i >= n_basic_blocks)
1462 bb = BASIC_BLOCK (i);
1466 /* Update the CFG for all queued instructions, taking special care of inserting
1467 code on edges between call and storing its return value. */
1470 commit_edge_insertions_watch_calls ()
1475 #ifdef ENABLE_CHECKING
1476 verify_flow_info ();
1480 bb = ENTRY_BLOCK_PTR;
1485 for (e = bb->succ; e; e = next)
1487 next = e->succ_next;
1489 commit_one_edge_insertion (e, true);
1492 if (++i >= n_basic_blocks)
1494 bb = BASIC_BLOCK (i);
1498 /* Print out one basic block with live information at start and end. */
1509 fprintf (outf, ";; Basic block %d, loop depth %d, count ",
1510 bb->index, bb->loop_depth);
1511 fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
1514 fputs (";; Predecessors: ", outf);
1515 for (e = bb->pred; e; e = e->pred_next)
1516 dump_edge_info (outf, e, 0);
1519 fputs (";; Registers live at start:", outf);
1520 dump_regset (bb->global_live_at_start, outf);
1523 for (insn = bb->head, last = NEXT_INSN (bb->end); insn != last;
1524 insn = NEXT_INSN (insn))
1525 print_rtl_single (outf, insn);
1527 fputs (";; Registers live at end:", outf);
1528 dump_regset (bb->global_live_at_end, outf);
1531 fputs (";; Successors: ", outf);
1532 for (e = bb->succ; e; e = e->succ_next)
1533 dump_edge_info (outf, e, 1);
1541 dump_bb (bb, stderr);
1548 dump_bb (BASIC_BLOCK (n), stderr);
1551 /* Like print_rtl, but also print out live information for the start of each
1555 print_rtl_with_bb (outf, rtx_first)
1562 fprintf (outf, "(nil)\n");
1566 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
1567 int max_uid = get_max_uid ();
1569 = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1571 = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1572 enum bb_state *in_bb_p
1573 = (enum bb_state *) xcalloc (max_uid, sizeof (enum bb_state));
1575 for (i = n_basic_blocks - 1; i >= 0; i--)
1577 basic_block bb = BASIC_BLOCK (i);
1580 start[INSN_UID (bb->head)] = bb;
1581 end[INSN_UID (bb->end)] = bb;
1582 for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x))
1584 enum bb_state state = IN_MULTIPLE_BB;
1586 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
1588 in_bb_p[INSN_UID (x)] = state;
1595 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
1600 if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
1602 fprintf (outf, ";; Start of basic block %d, registers live:",
1604 dump_regset (bb->global_live_at_start, outf);
1608 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
1609 && GET_CODE (tmp_rtx) != NOTE
1610 && GET_CODE (tmp_rtx) != BARRIER)
1611 fprintf (outf, ";; Insn is not within a basic block\n");
1612 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
1613 fprintf (outf, ";; Insn is in multiple basic blocks\n");
1615 did_output = print_rtl_single (outf, tmp_rtx);
1617 if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
1619 fprintf (outf, ";; End of basic block %d, registers live:\n",
1621 dump_regset (bb->global_live_at_end, outf);
1634 if (current_function_epilogue_delay_list != 0)
1636 fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
1637 for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0;
1638 tmp_rtx = XEXP (tmp_rtx, 1))
1639 print_rtl_single (outf, XEXP (tmp_rtx, 0));
1644 update_br_prob_note (bb)
1648 if (GET_CODE (bb->end) != JUMP_INSN)
1650 note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX);
1651 if (!note || INTVAL (XEXP (note, 0)) == BRANCH_EDGE (bb)->probability)
1653 XEXP (note, 0) = GEN_INT (BRANCH_EDGE (bb)->probability);
1656 /* Verify the CFG consistency. This function check some CFG invariants and
1657 aborts when something is wrong. Hope that this function will help to
1658 convert many optimization passes to preserve CFG consistent.
1660 Currently it does following checks:
1662 - test head/end pointers
1663 - overlapping of basic blocks
1664 - edge list correctness
1665 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1666 - tails of basic blocks (ensure that boundary is necessary)
1667 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1668 and NOTE_INSN_BASIC_BLOCK
1669 - check that all insns are in the basic blocks
1670 (except the switch handling code, barriers and notes)
1671 - check that all returns are followed by barriers
1673 In future it can be extended check a lot of other stuff as well
1674 (reachability of basic blocks, life information, etc. etc.). */
1679 const int max_uid = get_max_uid ();
1680 const rtx rtx_first = get_insns ();
1681 rtx last_head = get_last_insn ();
1682 basic_block *bb_info, *last_visited;
1683 size_t *edge_checksum;
1685 int i, last_bb_num_seen, num_bb_notes, err = 0;
1687 bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1688 last_visited = (basic_block *) xcalloc (n_basic_blocks + 2,
1689 sizeof (basic_block));
1690 edge_checksum = (size_t *) xcalloc (n_basic_blocks + 2, sizeof (size_t));
1692 for (i = n_basic_blocks - 1; i >= 0; i--)
1694 basic_block bb = BASIC_BLOCK (i);
1695 rtx head = bb->head;
1698 /* Verify the end of the basic block is in the INSN chain. */
1699 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
1705 error ("end insn %d for block %d not found in the insn stream",
1706 INSN_UID (end), bb->index);
1710 /* Work backwards from the end to the head of the basic block
1711 to verify the head is in the RTL chain. */
1712 for (; x != NULL_RTX; x = PREV_INSN (x))
1714 /* While walking over the insn chain, verify insns appear
1715 in only one basic block and initialize the BB_INFO array
1716 used by other passes. */
1717 if (bb_info[INSN_UID (x)] != NULL)
1719 error ("insn %d is in multiple basic blocks (%d and %d)",
1720 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
1724 bb_info[INSN_UID (x)] = bb;
1731 error ("head insn %d for block %d not found in the insn stream",
1732 INSN_UID (head), bb->index);
1739 /* Now check the basic blocks (boundaries etc.) */
1740 for (i = n_basic_blocks - 1; i >= 0; i--)
1742 basic_block bb = BASIC_BLOCK (i);
1743 int n_fallthru = 0, n_eh = 0, n_call = 0, n_abnormal = 0, n_branch = 0;
1747 if (INSN_P (bb->end)
1748 && (note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX))
1749 && any_condjump_p (bb->end))
1751 if (INTVAL (XEXP (note, 0)) != BRANCH_EDGE (bb)->probability)
1753 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
1754 INTVAL (XEXP (note, 0)), BRANCH_EDGE (bb)->probability);
1760 error ("verify_flow_info: Wrong count of block %i %i",
1761 bb->index, (int)bb->count);
1764 if (bb->frequency < 0)
1766 error ("verify_flow_info: Wrong frequency of block %i %i",
1767 bb->index, bb->frequency);
1770 for (e = bb->succ; e; e = e->succ_next)
1772 if (last_visited [e->dest->index + 2] == bb)
1774 error ("verify_flow_info: Duplicate edge %i->%i",
1775 e->src->index, e->dest->index);
1778 if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
1780 error ("verify_flow_info: Wrong probability of edge %i->%i %i",
1781 e->src->index, e->dest->index, e->probability);
1786 error ("verify_flow_info: Wrong count of edge %i->%i %i",
1787 e->src->index, e->dest->index, (int)e->count);
1791 last_visited [e->dest->index + 2] = bb;
1793 if (e->flags & EDGE_FALLTHRU)
1796 if ((e->flags & ~EDGE_DFS_BACK) == 0)
1799 if (e->flags & EDGE_ABNORMAL_CALL)
1802 if (e->flags & EDGE_EH)
1804 else if (e->flags & EDGE_ABNORMAL)
1807 if ((e->flags & EDGE_FALLTHRU)
1808 && e->src != ENTRY_BLOCK_PTR
1809 && e->dest != EXIT_BLOCK_PTR)
1813 if (e->src->index + 1 != e->dest->index)
1816 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
1817 e->src->index, e->dest->index);
1821 for (insn = NEXT_INSN (e->src->end); insn != e->dest->head;
1822 insn = NEXT_INSN (insn))
1823 if (GET_CODE (insn) == BARRIER
1824 #ifndef CASE_DROPS_THROUGH
1827 || (INSN_P (insn) && ! JUMP_TABLE_DATA_P (insn))
1831 error ("verify_flow_info: Incorrect fallthru %i->%i",
1832 e->src->index, e->dest->index);
1833 fatal_insn ("wrong insn in the fallthru edge", insn);
1840 error ("verify_flow_info: Basic block %d succ edge is corrupted",
1842 fprintf (stderr, "Predecessor: ");
1843 dump_edge_info (stderr, e, 0);
1844 fprintf (stderr, "\nSuccessor: ");
1845 dump_edge_info (stderr, e, 1);
1846 fprintf (stderr, "\n");
1850 edge_checksum[e->dest->index + 2] += (size_t) e;
1853 if (n_eh && GET_CODE (PATTERN (bb->end)) != RESX
1854 && !find_reg_note (bb->end, REG_EH_REGION, NULL_RTX))
1856 error ("Missing REG_EH_REGION note in the end of bb %i", bb->index);
1860 && (GET_CODE (bb->end) != JUMP_INSN
1861 || (n_branch > 1 && (any_uncondjump_p (bb->end)
1862 || any_condjump_p (bb->end)))))
1864 error ("Too many outgoing branch edges from bb %i", bb->index);
1867 if (n_fallthru && any_uncondjump_p (bb->end))
1869 error ("Fallthru edge after unconditional jump %i", bb->index);
1872 if (n_branch != 1 && any_uncondjump_p (bb->end))
1874 error ("Wrong amount of branch edges after unconditional jump %i", bb->index);
1877 if (n_branch != 1 && any_condjump_p (bb->end)
1878 && JUMP_LABEL (bb->end) != BASIC_BLOCK (bb->index + 1)->head)
1880 error ("Wrong amount of branch edges after conditional jump %i", bb->index);
1883 if (n_call && GET_CODE (bb->end) != CALL_INSN)
1885 error ("Call edges for non-call insn in bb %i", bb->index);
1889 && (GET_CODE (bb->end) != CALL_INSN && n_call != n_abnormal)
1890 && (GET_CODE (bb->end) != JUMP_INSN
1891 || any_condjump_p (bb->end)
1892 || any_uncondjump_p (bb->end)))
1894 error ("Abnormal edges for no purpose in bb %i", bb->index);
1902 /* Ensure existence of barrier in BB with no fallthru edges. */
1903 for (insn = bb->end; !insn || GET_CODE (insn) != BARRIER;
1904 insn = NEXT_INSN (insn))
1906 || (GET_CODE (insn) == NOTE
1907 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK))
1909 error ("missing barrier after block %i", bb->index);
1915 for (e = bb->pred; e; e = e->pred_next)
1919 error ("basic block %d pred edge is corrupted", bb->index);
1920 fputs ("Predecessor: ", stderr);
1921 dump_edge_info (stderr, e, 0);
1922 fputs ("\nSuccessor: ", stderr);
1923 dump_edge_info (stderr, e, 1);
1924 fputc ('\n', stderr);
1927 edge_checksum[e->dest->index + 2] -= (size_t) e;
1930 for (x = bb->head; x != NEXT_INSN (bb->end); x = NEXT_INSN (x))
1931 if (basic_block_for_insn && BLOCK_FOR_INSN (x) != bb)
1934 if (! BLOCK_FOR_INSN (x))
1936 ("insn %d inside basic block %d but block_for_insn is NULL",
1937 INSN_UID (x), bb->index);
1940 ("insn %d inside basic block %d but block_for_insn is %i",
1941 INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index);
1946 /* OK pointers are correct. Now check the header of basic
1947 block. It ought to contain optional CODE_LABEL followed
1948 by NOTE_BASIC_BLOCK. */
1950 if (GET_CODE (x) == CODE_LABEL)
1954 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1962 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
1964 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1970 /* Do checks for empty blocks her. e */
1973 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
1975 if (NOTE_INSN_BASIC_BLOCK_P (x))
1977 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
1978 INSN_UID (x), bb->index);
1985 if (GET_CODE (x) == JUMP_INSN
1986 || GET_CODE (x) == CODE_LABEL
1987 || GET_CODE (x) == BARRIER)
1989 error ("in basic block %d:", bb->index);
1990 fatal_insn ("flow control insn inside a basic block", x);
1995 /* Complete edge checksumming for ENTRY and EXIT. */
1999 for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
2000 edge_checksum[e->dest->index + 2] += (size_t) e;
2002 for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
2003 edge_checksum[e->dest->index + 2] -= (size_t) e;
2006 for (i = -2; i < n_basic_blocks; ++i)
2007 if (edge_checksum[i + 2])
2009 error ("basic block %i edge lists are corrupted", i);
2013 last_bb_num_seen = -1;
2015 for (x = rtx_first; x; x = NEXT_INSN (x))
2017 if (NOTE_INSN_BASIC_BLOCK_P (x))
2019 basic_block bb = NOTE_BASIC_BLOCK (x);
2022 if (bb->index != last_bb_num_seen + 1)
2023 internal_error ("basic blocks not numbered consecutively");
2025 last_bb_num_seen = bb->index;
2028 if (!bb_info[INSN_UID (x)])
2030 switch (GET_CODE (x))
2037 /* An addr_vec is placed outside any block block. */
2039 && GET_CODE (NEXT_INSN (x)) == JUMP_INSN
2040 && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
2041 || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
2044 /* But in any case, non-deletable labels can appear anywhere. */
2048 fatal_insn ("insn outside basic block", x);
2053 && GET_CODE (x) == JUMP_INSN
2054 && returnjump_p (x) && ! condjump_p (x)
2055 && ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER))
2056 fatal_insn ("return not followed by barrier", x);
2059 if (num_bb_notes != n_basic_blocks)
2061 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2062 num_bb_notes, n_basic_blocks);
2065 internal_error ("verify_flow_info failed");
2069 free (last_visited);
2070 free (edge_checksum);
2073 /* Assume that the preceding pass has possibly eliminated jump instructions
2074 or converted the unconditional jumps. Eliminate the edges from CFG.
2075 Return true if any edges are eliminated. */
2078 purge_dead_edges (bb)
2082 rtx insn = bb->end, note;
2083 bool purged = false;
2085 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2086 if (GET_CODE (insn) == INSN
2087 && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
2091 if (! may_trap_p (PATTERN (insn))
2092 || ((eqnote = find_reg_equal_equiv_note (insn))
2093 && ! may_trap_p (XEXP (eqnote, 0))))
2094 remove_note (insn, note);
2097 /* Cleanup abnormal edges caused by throwing insns that have been
2099 if (! can_throw_internal (bb->end))
2100 for (e = bb->succ; e; e = next)
2102 next = e->succ_next;
2103 if (e->flags & EDGE_EH)
2106 bb->flags |= BB_DIRTY;
2111 if (GET_CODE (insn) == JUMP_INSN)
2116 /* We do care only about conditional jumps and simplejumps. */
2117 if (!any_condjump_p (insn)
2118 && !returnjump_p (insn)
2119 && !simplejump_p (insn))
2122 /* Branch probability/prediction notes are defined only for
2123 condjumps. We've possibly turned condjump into simplejump. */
2124 if (simplejump_p (insn))
2126 note = find_reg_note (insn, REG_BR_PROB, NULL);
2128 remove_note (insn, note);
2129 while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
2130 remove_note (insn, note);
2133 for (e = bb->succ; e; e = next)
2135 next = e->succ_next;
2137 /* Avoid abnormal flags to leak from computed jumps turned
2138 into simplejumps. */
2140 e->flags &= ~EDGE_ABNORMAL;
2142 /* Check purposes we can have edge. */
2143 if ((e->flags & EDGE_FALLTHRU)
2144 && any_condjump_p (insn))
2146 else if (e->dest != EXIT_BLOCK_PTR
2147 && e->dest->head == JUMP_LABEL (insn))
2149 else if (e->dest == EXIT_BLOCK_PTR
2150 && returnjump_p (insn))
2153 bb->flags |= BB_DIRTY;
2158 if (!bb->succ || !purged)
2162 fprintf (rtl_dump_file, "Purged edges from bb %i\n", bb->index);
2167 /* Redistribute probabilities. */
2168 if (!bb->succ->succ_next)
2170 bb->succ->probability = REG_BR_PROB_BASE;
2171 bb->succ->count = bb->count;
2175 note = find_reg_note (insn, REG_BR_PROB, NULL);
2179 b = BRANCH_EDGE (bb);
2180 f = FALLTHRU_EDGE (bb);
2181 b->probability = INTVAL (XEXP (note, 0));
2182 f->probability = REG_BR_PROB_BASE - b->probability;
2183 b->count = bb->count * b->probability / REG_BR_PROB_BASE;
2184 f->count = bb->count * f->probability / REG_BR_PROB_BASE;
2190 /* If we don't see a jump insn, we don't know exactly why the block would
2191 have been broken at this point. Look for a simple, non-fallthru edge,
2192 as these are only created by conditional branches. If we find such an
2193 edge we know that there used to be a jump here and can then safely
2194 remove all non-fallthru edges. */
2195 for (e = bb->succ; e && (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU));
2202 for (e = bb->succ; e; e = next)
2204 next = e->succ_next;
2205 if (!(e->flags & EDGE_FALLTHRU))
2207 bb->flags |= BB_DIRTY;
2213 if (!bb->succ || bb->succ->succ_next)
2216 bb->succ->probability = REG_BR_PROB_BASE;
2217 bb->succ->count = bb->count;
2220 fprintf (rtl_dump_file, "Purged non-fallthru edges from bb %i\n",
2225 /* Search all basic blocks for potentially dead edges and purge them. Return
2226 true if some edge has been eliminated. */
2229 purge_all_dead_edges (update_life_p)
2232 int i, purged = false;
2237 blocks = sbitmap_alloc (n_basic_blocks);
2238 sbitmap_zero (blocks);
2241 for (i = 0; i < n_basic_blocks; i++)
2243 bool purged_here = purge_dead_edges (BASIC_BLOCK (i));
2245 purged |= purged_here;
2246 if (purged_here && update_life_p)
2247 SET_BIT (blocks, i);
2250 if (update_life_p && purged)
2251 update_life_info (blocks, UPDATE_LIFE_GLOBAL,
2252 PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
2253 | PROP_KILL_DEAD_CODE);
2256 sbitmap_free (blocks);