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 with CFG and analyze it.
23 All other modules should not transform the datastructure directly and use
24 abstraction instead. The file is supposed to be ordered bottom-up.
26 Available functionality:
27 - Initialization/deallocation
28 init_flow, clear_edges
29 - CFG aware instruction chain manipulation
30 delete_insn, delete_insn_chain
31 - Basic block manipulation
32 create_basic_block, flow_delete_block, split_block, merge_blocks_nomove
33 - Infrastructure to determine quickly basic block for instruction.
34 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
35 set_block_for_new_insns
37 make_edge, make_single_succ_edge, cached_make_edge, remove_edge
38 - Low level edge redirection (without updating instruction chain)
39 redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred
40 - High level edge redirection (with updating and optimizing instruction
42 block_label, redirect_edge_and_branch,
43 redirect_edge_and_branch_force, tidy_fallthru_edge, force_nonfallthru
44 - Edge splitting and commiting to edges
45 split_edge, insert_insn_on_edge, commit_edge_insertions
46 - Dumpipng and debugging
47 dump_flow_info, debug_flow_info, dump_edge_info, dump_bb, debug_bb,
48 debug_bb_n, print_rtl_with_bb
49 - Consistency checking
51 - CFG updating after constant propagation
52 purge_dead_edges, purge_all_dead_edges
59 #include "hard-reg-set.h"
60 #include "basic-block.h"
71 /* Stubs in case we haven't got a return insn. */
74 #define gen_return() NULL_RTX
77 /* The obstack on which the flow graph components are allocated. */
79 struct obstack flow_obstack;
80 static char *flow_firstobj;
82 /* Number of basic blocks in the current function. */
86 /* Number of edges in the current function. */
90 /* First edge in the deleted edges chain. */
92 edge first_deleted_edge;
94 /* The basic block array. */
96 varray_type basic_block_info;
98 /* The special entry and exit blocks. */
100 struct basic_block_def entry_exit_blocks[2]
103 NULL, /* head_tree */
107 NULL, /* local_set */
108 NULL, /* cond_local_set */
109 NULL, /* global_live_at_start */
110 NULL, /* global_live_at_end */
112 ENTRY_BLOCK, /* index */
121 NULL, /* head_tree */
125 NULL, /* local_set */
126 NULL, /* cond_local_set */
127 NULL, /* global_live_at_start */
128 NULL, /* global_live_at_end */
130 EXIT_BLOCK, /* index */
138 /* The basic block structure for every insn, indexed by uid. */
140 varray_type basic_block_for_insn;
142 /* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */
143 /* ??? Should probably be using LABEL_NUSES instead. It would take a
144 bit of surgery to be able to use or co-opt the routines in jump. */
146 rtx label_value_list;
147 rtx tail_recursion_label_list;
149 void debug_flow_info PARAMS ((void));
150 static int can_delete_note_p PARAMS ((rtx));
151 static int can_delete_label_p PARAMS ((rtx));
152 static void commit_one_edge_insertion PARAMS ((edge));
153 static bool try_redirect_by_replacing_jump PARAMS ((edge, basic_block));
154 static rtx last_loop_beg_note PARAMS ((rtx));
155 static bool back_edge_of_syntactic_loop_p PARAMS ((basic_block, basic_block));
156 static basic_block force_nonfallthru_and_redirect PARAMS ((edge, basic_block));
158 /* Called once at intialization time. */
163 static int initialized;
165 first_deleted_edge = 0;
170 gcc_obstack_init (&flow_obstack);
171 flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
176 obstack_free (&flow_obstack, flow_firstobj);
177 flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
181 /* Free the memory associated with the edge structures. */
188 for (i = 0; i < n_basic_blocks; ++i)
190 basic_block bb = BASIC_BLOCK (i);
193 remove_edge (bb->succ);
196 while (ENTRY_BLOCK_PTR->succ)
197 remove_edge (ENTRY_BLOCK_PTR->succ);
203 /* Return true if NOTE is not one of the ones that must be kept paired,
204 so that we may simply delete them. */
207 can_delete_note_p (note)
210 return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED
211 || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK);
214 /* True if a given label can be deleted. */
217 can_delete_label_p (label)
222 if (LABEL_PRESERVE_P (label))
225 for (x = forced_labels; x; x = XEXP (x, 1))
226 if (label == XEXP (x, 0))
228 for (x = label_value_list; x; x = XEXP (x, 1))
229 if (label == XEXP (x, 0))
231 for (x = exception_handler_labels; x; x = XEXP (x, 1))
232 if (label == XEXP (x, 0))
235 /* User declared labels must be preserved. */
236 if (LABEL_NAME (label) != 0)
242 /* Delete INSN by patching it out. Return the next insn. */
248 rtx next = NEXT_INSN (insn);
250 bool really_delete = true;
252 if (GET_CODE (insn) == CODE_LABEL)
254 /* Some labels can't be directly removed from the INSN chain, as they
255 might be references via variables, constant pool etc.
256 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
257 if (! can_delete_label_p (insn))
259 const char *name = LABEL_NAME (insn);
261 really_delete = false;
262 PUT_CODE (insn, NOTE);
263 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL;
264 NOTE_SOURCE_FILE (insn) = name;
266 remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
272 INSN_DELETED_P (insn) = 1;
275 /* If deleting a jump, decrement the use count of the label. Deleting
276 the label itself should happen in the normal course of block merging. */
277 if (GET_CODE (insn) == JUMP_INSN
279 && GET_CODE (JUMP_LABEL (insn)) == CODE_LABEL)
280 LABEL_NUSES (JUMP_LABEL (insn))--;
282 /* Also if deleting an insn that references a label. */
283 else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX
284 && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
285 LABEL_NUSES (XEXP (note, 0))--;
287 if (GET_CODE (insn) == JUMP_INSN
288 && (GET_CODE (PATTERN (insn)) == ADDR_VEC
289 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
291 rtx pat = PATTERN (insn);
292 int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC;
293 int len = XVECLEN (pat, diff_vec_p);
296 for (i = 0; i < len; i++)
297 LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
303 /* Unlink a chain of insns between START and FINISH, leaving notes
304 that must be paired. */
307 delete_insn_chain (start, finish)
310 /* Unchain the insns one by one. It would be quicker to delete all
311 of these with a single unchaining, rather than one at a time, but
312 we need to keep the NOTE's. */
318 next = NEXT_INSN (start);
319 if (GET_CODE (start) == NOTE && !can_delete_note_p (start))
322 next = delete_insn (start);
330 /* Create a new basic block consisting of the instructions between
331 HEAD and END inclusive. This function is designed to allow fast
332 BB construction - reuses the note and basic block struct
333 in BB_NOTE, if any and do not grow BASIC_BLOCK chain and should
334 be used directly only by CFG construction code.
335 END can be NULL in to create new empty basic block before HEAD.
336 Both END and HEAD can be NULL to create basic block at the end of
340 create_basic_block_structure (index, head, end, bb_note)
342 rtx head, end, bb_note;
347 && ! RTX_INTEGRATED_P (bb_note)
348 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
351 /* If we found an existing note, thread it back onto the chain. */
355 if (GET_CODE (head) == CODE_LABEL)
359 after = PREV_INSN (head);
363 if (after != bb_note && NEXT_INSN (after) != bb_note)
364 reorder_insns (bb_note, bb_note, after);
368 /* Otherwise we must create a note and a basic block structure.
369 Since we allow basic block structs in rtl, give the struct
370 the same lifetime by allocating it off the function obstack
371 rather than using malloc. */
373 bb = (basic_block) obstack_alloc (&flow_obstack, sizeof (*bb));
374 memset (bb, 0, sizeof (*bb));
378 head = end = bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK,
381 else if (GET_CODE (head) == CODE_LABEL && end)
383 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
389 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
394 NOTE_BASIC_BLOCK (bb_note) = bb;
397 /* Always include the bb note in the block. */
398 if (NEXT_INSN (end) == bb_note)
404 BASIC_BLOCK (index) = bb;
405 if (basic_block_for_insn)
406 update_bb_for_insn (bb);
408 /* Tag the block so that we know it has been used when considering
409 other basic block notes. */
415 /* Create new basic block consisting of instructions in between HEAD and
416 END and place it to the BB chain at possition INDEX.
417 END can be NULL in to create new empty basic block before HEAD.
418 Both END and HEAD can be NULL to create basic block at the end of
422 create_basic_block (index, head, end)
429 /* Place the new block just after the block being split. */
430 VARRAY_GROW (basic_block_info, ++n_basic_blocks);
432 /* Some parts of the compiler expect blocks to be number in
433 sequential order so insert the new block immediately after the
434 block being split.. */
435 for (i = n_basic_blocks - 1; i > index; --i)
437 basic_block tmp = BASIC_BLOCK (i - 1);
438 BASIC_BLOCK (i) = tmp;
442 bb = create_basic_block_structure (index, head, end, NULL);
447 /* Remove block B from the basic block array and compact behind it. */
453 int i, n = n_basic_blocks;
455 for (i = b->index; i + 1 < n; ++i)
457 basic_block x = BASIC_BLOCK (i + 1);
462 /* Invalidate data to make bughunting easier. */
463 memset (b, 0, sizeof (*b));
465 basic_block_info->num_elements--;
469 /* Delete the insns in a (non-live) block. We physically delete every
470 non-deleted-note insn, and update the flow graph appropriately.
472 Return nonzero if we deleted an exception handler. */
474 /* ??? Preserving all such notes strikes me as wrong. It would be nice
475 to post-process the stream to remove empty blocks, loops, ranges, etc. */
478 flow_delete_block (b)
481 int deleted_handler = 0;
484 /* If the head of this block is a CODE_LABEL, then it might be the
485 label for an exception handler which can't be reached.
487 We need to remove the label from the exception_handler_label list
488 and remove the associated NOTE_INSN_EH_REGION_BEG and
489 NOTE_INSN_EH_REGION_END notes. */
493 never_reached_warning (insn);
495 if (GET_CODE (insn) == CODE_LABEL)
496 maybe_remove_eh_handler (insn);
498 /* Include any jump table following the basic block. */
500 if (GET_CODE (end) == JUMP_INSN
501 && (tmp = JUMP_LABEL (end)) != NULL_RTX
502 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
503 && GET_CODE (tmp) == JUMP_INSN
504 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
505 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
508 /* Include any barrier that may follow the basic block. */
509 tmp = next_nonnote_insn (end);
510 if (tmp && GET_CODE (tmp) == BARRIER)
513 /* Selectively delete the entire chain. */
515 delete_insn_chain (insn, end);
517 /* Remove the edges into and out of this block. Note that there may
518 indeed be edges in, if we are removing an unreachable loop. */
519 while (b->pred != NULL)
520 remove_edge (b->pred);
521 while (b->succ != NULL)
522 remove_edge (b->succ);
527 /* Remove the basic block from the array, and compact behind it. */
530 return deleted_handler;
533 /* Records the basic block struct in BB_FOR_INSN, for every instruction
534 indexed by INSN_UID. MAX is the size of the array. */
537 compute_bb_for_insn (max)
542 if (basic_block_for_insn)
543 VARRAY_FREE (basic_block_for_insn);
544 VARRAY_BB_INIT (basic_block_for_insn, max, "basic_block_for_insn");
546 for (i = 0; i < n_basic_blocks; ++i)
548 basic_block bb = BASIC_BLOCK (i);
555 int uid = INSN_UID (insn);
557 VARRAY_BB (basic_block_for_insn, uid) = bb;
560 insn = NEXT_INSN (insn);
565 /* Release the basic_block_for_insn array. */
570 if (basic_block_for_insn)
571 VARRAY_FREE (basic_block_for_insn);
572 basic_block_for_insn = 0;
575 /* Update insns block within BB. */
578 update_bb_for_insn (bb)
583 if (! basic_block_for_insn)
586 for (insn = bb->head; ; insn = NEXT_INSN (insn))
588 set_block_for_insn (insn, bb);
595 /* Record INSN's block as BB. */
598 set_block_for_insn (insn, bb)
602 size_t uid = INSN_UID (insn);
603 if (uid >= basic_block_for_insn->num_elements)
607 /* Add one-eighth the size so we don't keep calling xrealloc. */
608 new_size = uid + (uid + 7) / 8;
610 VARRAY_GROW (basic_block_for_insn, new_size);
612 VARRAY_BB (basic_block_for_insn, uid) = bb;
615 /* When a new insn has been inserted into an existing block, it will
616 sometimes emit more than a single insn. This routine will set the
617 block number for the specified insn, and look backwards in the insn
618 chain to see if there are any other uninitialized insns immediately
619 previous to this one, and set the block number for them too. */
622 set_block_for_new_insns (insn, bb)
626 set_block_for_insn (insn, bb);
628 /* Scan the previous instructions setting the block number until we find
629 an instruction that has the block number set, or we find a note
631 for (insn = PREV_INSN (insn); insn != NULL_RTX; insn = PREV_INSN (insn))
633 if (GET_CODE (insn) == NOTE)
635 if ((unsigned) INSN_UID (insn) >= basic_block_for_insn->num_elements
636 || BLOCK_FOR_INSN (insn) == 0)
637 set_block_for_insn (insn, bb);
643 /* Create an edge connecting SRC and DST with FLAGS optionally using
644 edge cache CACHE. Return the new edge, NULL if already exist. */
647 cached_make_edge (edge_cache, src, dst, flags)
649 basic_block src, dst;
655 /* Don't bother with edge cache for ENTRY or EXIT; there aren't that
656 many edges to them, and we didn't allocate memory for it. */
657 use_edge_cache = (edge_cache
658 && src != ENTRY_BLOCK_PTR
659 && dst != EXIT_BLOCK_PTR);
661 /* Make sure we don't add duplicate edges. */
662 switch (use_edge_cache)
665 /* Quick test for non-existance of the edge. */
666 if (! TEST_BIT (edge_cache[src->index], dst->index))
669 /* The edge exists; early exit if no work to do. */
675 for (e = src->succ; e; e = e->succ_next)
684 if (first_deleted_edge)
686 e = first_deleted_edge;
687 first_deleted_edge = e->succ_next;
691 e = (edge) obstack_alloc (&flow_obstack, sizeof (*e));
692 memset (e, 0, sizeof (*e));
696 e->succ_next = src->succ;
697 e->pred_next = dst->pred;
706 SET_BIT (edge_cache[src->index], dst->index);
711 /* Create an edge connecting SRC and DEST with flags FLAGS. Return newly
712 created edge or NULL if already exist. */
715 make_edge (src, dest, flags)
716 basic_block src, dest;
719 return cached_make_edge (NULL, src, dest, flags);
722 /* Create an edge connecting SRC to DEST and set probability by knowling
723 that it is the single edge leaving SRC. */
726 make_single_succ_edge (src, dest, flags)
727 basic_block src, dest;
730 edge e = make_edge (src, dest, flags);
732 e->probability = REG_BR_PROB_BASE;
733 e->count = src->count;
737 /* This function will remove an edge from the flow graph. */
743 edge last_pred = NULL;
744 edge last_succ = NULL;
746 basic_block src, dest;
749 for (tmp = src->succ; tmp && tmp != e; tmp = tmp->succ_next)
755 last_succ->succ_next = e->succ_next;
757 src->succ = e->succ_next;
759 for (tmp = dest->pred; tmp && tmp != e; tmp = tmp->pred_next)
765 last_pred->pred_next = e->pred_next;
767 dest->pred = e->pred_next;
770 memset (e, 0, sizeof (*e));
771 e->succ_next = first_deleted_edge;
772 first_deleted_edge = e;
775 /* Redirect an edge's successor from one block to another. */
778 redirect_edge_succ (e, new_succ)
780 basic_block new_succ;
784 /* Disconnect the edge from the old successor block. */
785 for (pe = &e->dest->pred; *pe != e; pe = &(*pe)->pred_next)
787 *pe = (*pe)->pred_next;
789 /* Reconnect the edge to the new successor block. */
790 e->pred_next = new_succ->pred;
795 /* Like previous but avoid possible dupplicate edge. */
798 redirect_edge_succ_nodup (e, new_succ)
800 basic_block new_succ;
803 /* Check whether the edge is already present. */
804 for (s = e->src->succ; s; s = s->succ_next)
805 if (s->dest == new_succ && s != e)
809 s->flags |= e->flags;
810 s->probability += e->probability;
811 s->count += e->count;
816 redirect_edge_succ (e, new_succ);
820 /* Redirect an edge's predecessor from one block to another. */
823 redirect_edge_pred (e, new_pred)
825 basic_block new_pred;
829 /* Disconnect the edge from the old predecessor block. */
830 for (pe = &e->src->succ; *pe != e; pe = &(*pe)->succ_next)
832 *pe = (*pe)->succ_next;
834 /* Reconnect the edge to the new predecessor block. */
835 e->succ_next = new_pred->succ;
840 /* Split a block BB after insn INSN creating a new fallthru edge.
841 Return the new edge. Note that to keep other parts of the compiler happy,
842 this function renumbers all the basic blocks so that the new
843 one has a number one greater than the block split. */
846 split_block (bb, insn)
854 /* There is no point splitting the block after its end. */
858 /* Create the new basic block. */
859 new_bb = create_basic_block (bb->index + 1, NEXT_INSN (insn), bb->end);
860 new_bb->count = bb->count;
861 new_bb->frequency = bb->frequency;
862 new_bb->loop_depth = bb->loop_depth;
865 /* Redirect the outgoing edges. */
866 new_bb->succ = bb->succ;
868 for (e = new_bb->succ; e; e = e->succ_next)
871 new_edge = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
873 if (bb->global_live_at_start)
875 new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
876 new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
877 COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
879 /* We now have to calculate which registers are live at the end
880 of the split basic block and at the start of the new basic
881 block. Start with those registers that are known to be live
882 at the end of the original basic block and get
883 propagate_block to determine which registers are live. */
884 COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_end);
885 propagate_block (new_bb, new_bb->global_live_at_start, NULL, NULL, 0);
886 COPY_REG_SET (bb->global_live_at_end,
887 new_bb->global_live_at_start);
893 /* Blocks A and B are to be merged into a single block A. The insns
894 are already contiguous, hence `nomove'. */
897 merge_blocks_nomove (a, b)
901 rtx b_head, b_end, a_end;
902 rtx del_first = NULL_RTX, del_last = NULL_RTX;
905 /* If there was a CODE_LABEL beginning B, delete it. */
908 if (GET_CODE (b_head) == CODE_LABEL)
910 /* Detect basic blocks with nothing but a label. This can happen
911 in particular at the end of a function. */
914 del_first = del_last = b_head;
915 b_head = NEXT_INSN (b_head);
918 /* Delete the basic block note. */
919 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
926 b_head = NEXT_INSN (b_head);
929 /* If there was a jump out of A, delete it. */
931 if (GET_CODE (a_end) == JUMP_INSN)
935 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
936 if (GET_CODE (prev) != NOTE
937 || NOTE_LINE_NUMBER (prev) == NOTE_INSN_BASIC_BLOCK
944 /* If this was a conditional jump, we need to also delete
945 the insn that set cc0. */
946 if (only_sets_cc0_p (prev))
949 prev = prev_nonnote_insn (prev);
956 a_end = PREV_INSN (del_first);
958 else if (GET_CODE (NEXT_INSN (a_end)) == BARRIER)
959 del_first = NEXT_INSN (a_end);
961 /* Normally there should only be one successor of A and that is B, but
962 partway though the merge of blocks for conditional_execution we'll
963 be merging a TEST block with THEN and ELSE successors. Free the
964 whole lot of them and hope the caller knows what they're doing. */
966 remove_edge (a->succ);
968 /* Adjust the edges out of B for the new owner. */
969 for (e = b->succ; e; e = e->succ_next)
973 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
974 b->pred = b->succ = NULL;
978 /* Delete everything marked above as well as crap that might be
979 hanging out between the two blocks. */
980 delete_insn_chain (del_first, del_last);
982 /* Reassociate the insns of B with A. */
986 if (basic_block_for_insn)
988 BLOCK_FOR_INSN (x) = a;
992 BLOCK_FOR_INSN (x) = a;
1000 /* Return label in the head of basic block. Create one if it doesn't exist. */
1006 if (block == EXIT_BLOCK_PTR)
1008 if (GET_CODE (block->head) != CODE_LABEL)
1010 block->head = emit_label_before (gen_label_rtx (), block->head);
1011 if (basic_block_for_insn)
1012 set_block_for_insn (block->head, block);
1017 /* Attempt to perform edge redirection by replacing possibly complex jump
1018 instruction by unconditional jump or removing jump completely.
1019 This can apply only if all edges now point to the same block.
1021 The parameters and return values are equivalent to redirect_edge_and_branch.
1025 try_redirect_by_replacing_jump (e, target)
1029 basic_block src = e->src;
1030 rtx insn = src->end, kill_from;
1035 /* Verify that all targets will be TARGET. */
1036 for (tmp = src->succ; tmp; tmp = tmp->succ_next)
1037 if (tmp->dest != target && tmp != e)
1039 if (tmp || !onlyjump_p (insn))
1042 /* Avoid removing branch with side effects. */
1043 set = single_set (insn);
1044 if (!set || side_effects_p (set))
1047 /* In case we zap a conditional jump, we'll need to kill
1048 the cc0 setter too. */
1051 if (reg_mentioned_p (cc0_rtx, PATTERN (insn)))
1052 kill_from = PREV_INSN (insn);
1055 /* See if we can create the fallthru edge. */
1056 if (can_fallthru (src, target))
1059 fprintf (rtl_dump_file, "Removing jump %i.\n", INSN_UID (insn));
1062 /* Selectivly unlink whole insn chain. */
1063 delete_insn_chain (kill_from, PREV_INSN (target->head));
1065 /* If this already is simplejump, redirect it. */
1066 else if (simplejump_p (insn))
1068 if (e->dest == target)
1071 fprintf (rtl_dump_file, "Redirecting jump %i from %i to %i.\n",
1072 INSN_UID (insn), e->dest->index, target->index);
1073 redirect_jump (insn, block_label (target), 0);
1075 /* Or replace possibly complicated jump insn by simple jump insn. */
1078 rtx target_label = block_label (target);
1081 emit_jump_insn_after (gen_jump (target_label), kill_from);
1082 JUMP_LABEL (src->end) = target_label;
1083 LABEL_NUSES (target_label)++;
1085 fprintf (rtl_dump_file, "Replacing insn %i by jump %i\n",
1086 INSN_UID (insn), INSN_UID (src->end));
1088 delete_insn_chain (kill_from, insn);
1090 barrier = next_nonnote_insn (src->end);
1091 if (!barrier || GET_CODE (barrier) != BARRIER)
1092 emit_barrier_after (src->end);
1095 /* Keep only one edge out and set proper flags. */
1096 while (src->succ->succ_next)
1097 remove_edge (src->succ);
1100 e->flags = EDGE_FALLTHRU;
1103 e->probability = REG_BR_PROB_BASE;
1104 e->count = src->count;
1106 /* We don't want a block to end on a line-number note since that has
1107 the potential of changing the code between -g and not -g. */
1108 while (GET_CODE (e->src->end) == NOTE
1109 && NOTE_LINE_NUMBER (e->src->end) >= 0)
1110 delete_insn (e->src->end);
1112 if (e->dest != target)
1113 redirect_edge_succ (e, target);
1117 /* Return last loop_beg note appearing after INSN, before start of next
1118 basic block. Return INSN if there are no such notes.
1120 When emmiting jump to redirect an fallthru edge, it should always
1121 appear after the LOOP_BEG notes, as loop optimizer expect loop to
1122 eighter start by fallthru edge or jump following the LOOP_BEG note
1123 jumping to the loop exit test. */
1126 last_loop_beg_note (insn)
1130 insn = NEXT_INSN (insn);
1131 while (insn && GET_CODE (insn) == NOTE
1132 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK)
1134 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1136 insn = NEXT_INSN (insn);
1141 /* Attempt to change code to redirect edge E to TARGET.
1142 Don't do that on expense of adding new instructions or reordering
1145 Function can be also called with edge destionation equivalent to the
1146 TARGET. Then it should try the simplifications and do nothing if
1149 Return true if transformation suceeded. We still return flase in case
1150 E already destinated TARGET and we didn't managed to simplify instruction
1154 redirect_edge_and_branch (e, target)
1159 rtx old_label = e->dest->head;
1160 basic_block src = e->src;
1161 rtx insn = src->end;
1163 if (e->flags & EDGE_COMPLEX)
1166 if (try_redirect_by_replacing_jump (e, target))
1168 /* Do this fast path late, as we want above code to simplify for cases
1169 where called on single edge leaving basic block containing nontrivial
1171 else if (e->dest == target)
1174 /* We can only redirect non-fallthru edges of jump insn. */
1175 if (e->flags & EDGE_FALLTHRU)
1177 if (GET_CODE (insn) != JUMP_INSN)
1180 /* Recognize a tablejump and adjust all matching cases. */
1181 if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
1182 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
1183 && GET_CODE (tmp) == JUMP_INSN
1184 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
1185 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
1189 rtx new_label = block_label (target);
1191 if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
1192 vec = XVEC (PATTERN (tmp), 0);
1194 vec = XVEC (PATTERN (tmp), 1);
1196 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1197 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1199 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
1200 --LABEL_NUSES (old_label);
1201 ++LABEL_NUSES (new_label);
1204 /* Handle casesi dispatch insns */
1205 if ((tmp = single_set (insn)) != NULL
1206 && SET_DEST (tmp) == pc_rtx
1207 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1208 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
1209 && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
1211 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (VOIDmode,
1213 --LABEL_NUSES (old_label);
1214 ++LABEL_NUSES (new_label);
1219 /* ?? We may play the games with moving the named labels from
1220 one basic block to the other in case only one computed_jump is
1222 if (computed_jump_p (insn))
1225 /* A return instruction can't be redirected. */
1226 if (returnjump_p (insn))
1229 /* If the insn doesn't go where we think, we're confused. */
1230 if (JUMP_LABEL (insn) != old_label)
1232 redirect_jump (insn, block_label (target), 0);
1236 fprintf (rtl_dump_file, "Edge %i->%i redirected to %i\n",
1237 e->src->index, e->dest->index, target->index);
1238 if (e->dest != target)
1239 redirect_edge_succ_nodup (e, target);
1243 /* Like force_nonfallthru bellow, but additionally performs redirection
1244 Used by redirect_edge_and_branch_force. */
1247 force_nonfallthru_and_redirect (e, target)
1251 basic_block jump_block, new_bb = NULL;
1255 if (e->flags & EDGE_ABNORMAL)
1257 if (!(e->flags & EDGE_FALLTHRU))
1259 if (e->src->succ->succ_next)
1261 /* Create the new structures. */
1262 note = last_loop_beg_note (e->src->end);
1263 jump_block = create_basic_block (e->src->index + 1, NEXT_INSN (note), NULL);
1264 jump_block->count = e->count;
1265 jump_block->frequency = EDGE_FREQUENCY (e);
1266 jump_block->loop_depth = target->loop_depth;
1268 if (target->global_live_at_start)
1270 jump_block->global_live_at_start =
1271 OBSTACK_ALLOC_REG_SET (&flow_obstack);
1272 jump_block->global_live_at_end =
1273 OBSTACK_ALLOC_REG_SET (&flow_obstack);
1274 COPY_REG_SET (jump_block->global_live_at_start,
1275 target->global_live_at_start);
1276 COPY_REG_SET (jump_block->global_live_at_end,
1277 target->global_live_at_start);
1281 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1282 new_edge->probability = e->probability;
1283 new_edge->count = e->count;
1285 /* Redirect old edge. */
1286 redirect_edge_pred (e, jump_block);
1287 e->probability = REG_BR_PROB_BASE;
1289 new_bb = jump_block;
1292 jump_block = e->src;
1293 e->flags &= ~EDGE_FALLTHRU;
1294 if (target == EXIT_BLOCK_PTR)
1297 emit_jump_insn_after (gen_return (), jump_block->end);
1303 rtx label = block_label (target);
1304 emit_jump_insn_after (gen_jump (label), jump_block->end);
1305 JUMP_LABEL (jump_block->end) = label;
1306 LABEL_NUSES (label)++;
1308 emit_barrier_after (jump_block->end);
1309 redirect_edge_succ_nodup (e, target);
1314 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1315 (and possibly create new basic block) to make edge non-fallthru.
1316 Return newly created BB or NULL if none. */
1318 force_nonfallthru (e)
1321 return force_nonfallthru_and_redirect (e, e->dest);
1324 /* Redirect edge even at the expense of creating new jump insn or
1325 basic block. Return new basic block if created, NULL otherwise.
1326 Abort if converison is impossible. */
1329 redirect_edge_and_branch_force (e, target)
1335 if (redirect_edge_and_branch (e, target))
1337 if (e->dest == target)
1340 /* In case the edge redirection failed, try to force it to be non-fallthru
1341 and redirect newly created simplejump. */
1342 new_bb = force_nonfallthru_and_redirect (e, target);
1346 /* The given edge should potentially be a fallthru edge. If that is in
1347 fact true, delete the jump and barriers that are in the way. */
1350 tidy_fallthru_edge (e, b, c)
1356 /* ??? In a late-running flow pass, other folks may have deleted basic
1357 blocks by nopping out blocks, leaving multiple BARRIERs between here
1358 and the target label. They ought to be chastized and fixed.
1360 We can also wind up with a sequence of undeletable labels between
1361 one block and the next.
1363 So search through a sequence of barriers, labels, and notes for
1364 the head of block C and assert that we really do fall through. */
1366 if (next_real_insn (b->end) != next_real_insn (PREV_INSN (c->head)))
1369 /* Remove what will soon cease being the jump insn from the source block.
1370 If block B consisted only of this single jump, turn it into a deleted
1373 if (GET_CODE (q) == JUMP_INSN
1375 && (any_uncondjump_p (q)
1376 || (b->succ == e && e->succ_next == NULL)))
1379 /* If this was a conditional jump, we need to also delete
1380 the insn that set cc0. */
1381 if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1387 /* We don't want a block to end on a line-number note since that has
1388 the potential of changing the code between -g and not -g. */
1389 while (GET_CODE (q) == NOTE && NOTE_LINE_NUMBER (q) >= 0)
1393 /* Selectively unlink the sequence. */
1394 if (q != PREV_INSN (c->head))
1395 delete_insn_chain (NEXT_INSN (q), PREV_INSN (c->head));
1397 e->flags |= EDGE_FALLTHRU;
1400 /* Fix up edges that now fall through, or rather should now fall through
1401 but previously required a jump around now deleted blocks. Simplify
1402 the search by only examining blocks numerically adjacent, since this
1403 is how find_basic_blocks created them. */
1406 tidy_fallthru_edges ()
1410 for (i = 1; i < n_basic_blocks; ++i)
1412 basic_block b = BASIC_BLOCK (i - 1);
1413 basic_block c = BASIC_BLOCK (i);
1416 /* We care about simple conditional or unconditional jumps with
1419 If we had a conditional branch to the next instruction when
1420 find_basic_blocks was called, then there will only be one
1421 out edge for the block which ended with the conditional
1422 branch (since we do not create duplicate edges).
1424 Furthermore, the edge will be marked as a fallthru because we
1425 merge the flags for the duplicate edges. So we do not want to
1426 check that the edge is not a FALLTHRU edge. */
1427 if ((s = b->succ) != NULL
1428 && ! (s->flags & EDGE_COMPLEX)
1429 && s->succ_next == NULL
1431 /* If the jump insn has side effects, we can't tidy the edge. */
1432 && (GET_CODE (b->end) != JUMP_INSN
1433 || onlyjump_p (b->end)))
1434 tidy_fallthru_edge (s, b, c);
1438 /* Helper function for split_edge. Return true in case edge BB2 to BB1
1439 is back edge of syntactic loop. */
1442 back_edge_of_syntactic_loop_p (bb1, bb2)
1443 basic_block bb1, bb2;
1448 if (bb1->index > bb2->index)
1451 if (bb1->index == bb2->index)
1454 for (insn = bb1->end; insn != bb2->head && count >= 0;
1455 insn = NEXT_INSN (insn))
1456 if (GET_CODE (insn) == NOTE)
1458 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1460 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1467 /* Split a (typically critical) edge. Return the new block.
1468 Abort on abnormal edges.
1470 ??? The code generally expects to be called on critical edges.
1471 The case of a block ending in an unconditional jump to a
1472 block with multiple predecessors is not handled optimally. */
1475 split_edge (edge_in)
1482 /* Abnormal edges cannot be split. */
1483 if ((edge_in->flags & EDGE_ABNORMAL) != 0)
1486 /* We are going to place the new block in front of edge destination.
1487 Avoid existence of fallthru predecesors. */
1488 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1491 for (e = edge_in->dest->pred; e; e = e->pred_next)
1492 if (e->flags & EDGE_FALLTHRU)
1496 force_nonfallthru (e);
1499 /* Create the basic block note.
1501 Where we place the note can have a noticable impact on the generated
1502 code. Consider this cfg:
1512 If we need to insert an insn on the edge from block 0 to block 1,
1513 we want to ensure the instructions we insert are outside of any
1514 loop notes that physically sit between block 0 and block 1. Otherwise
1515 we confuse the loop optimizer into thinking the loop is a phony. */
1517 if (edge_in->dest != EXIT_BLOCK_PTR
1518 && PREV_INSN (edge_in->dest->head)
1519 && GET_CODE (PREV_INSN (edge_in->dest->head)) == NOTE
1520 && NOTE_LINE_NUMBER (PREV_INSN (edge_in->dest->head)) == NOTE_INSN_LOOP_BEG
1521 && !back_edge_of_syntactic_loop_p (edge_in->dest, edge_in->src))
1522 before = PREV_INSN (edge_in->dest->head);
1523 else if (edge_in->dest != EXIT_BLOCK_PTR)
1524 before = edge_in->dest->head;
1528 bb = create_basic_block (edge_in->dest == EXIT_BLOCK_PTR ? n_basic_blocks
1529 : edge_in->dest->index, before, NULL);
1530 bb->count = edge_in->count;
1531 bb->frequency = EDGE_FREQUENCY (edge_in);
1533 /* ??? This info is likely going to be out of date very soon. */
1534 if (edge_in->dest->global_live_at_start)
1536 bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1537 bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1538 COPY_REG_SET (bb->global_live_at_start, edge_in->dest->global_live_at_start);
1539 COPY_REG_SET (bb->global_live_at_end, edge_in->dest->global_live_at_start);
1542 edge_out = make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1544 /* For non-fallthry edges, we must adjust the predecessor's
1545 jump instruction to target our new block. */
1546 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1548 if (!redirect_edge_and_branch (edge_in, bb))
1552 redirect_edge_succ (edge_in, bb);
1557 /* Queue instructions for insertion on an edge between two basic blocks.
1558 The new instructions and basic blocks (if any) will not appear in the
1559 CFG until commit_edge_insertions is called. */
1562 insert_insn_on_edge (pattern, e)
1566 /* We cannot insert instructions on an abnormal critical edge.
1567 It will be easier to find the culprit if we die now. */
1568 if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
1571 if (e->insns == NULL_RTX)
1574 push_to_sequence (e->insns);
1576 emit_insn (pattern);
1578 e->insns = get_insns ();
1582 /* Update the CFG for the instructions queued on edge E. */
1585 commit_one_edge_insertion (e)
1588 rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
1591 /* Pull the insns off the edge now since the edge might go away. */
1593 e->insns = NULL_RTX;
1595 /* Figure out where to put these things. If the destination has
1596 one predecessor, insert there. Except for the exit block. */
1597 if (e->dest->pred->pred_next == NULL
1598 && e->dest != EXIT_BLOCK_PTR)
1602 /* Get the location correct wrt a code label, and "nice" wrt
1603 a basic block note, and before everything else. */
1605 if (GET_CODE (tmp) == CODE_LABEL)
1606 tmp = NEXT_INSN (tmp);
1607 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1608 tmp = NEXT_INSN (tmp);
1609 if (tmp == bb->head)
1612 after = PREV_INSN (tmp);
1615 /* If the source has one successor and the edge is not abnormal,
1616 insert there. Except for the entry block. */
1617 else if ((e->flags & EDGE_ABNORMAL) == 0
1618 && e->src->succ->succ_next == NULL
1619 && e->src != ENTRY_BLOCK_PTR)
1622 /* It is possible to have a non-simple jump here. Consider a target
1623 where some forms of unconditional jumps clobber a register. This
1624 happens on the fr30 for example.
1626 We know this block has a single successor, so we can just emit
1627 the queued insns before the jump. */
1628 if (GET_CODE (bb->end) == JUMP_INSN)
1631 while (GET_CODE (PREV_INSN (before)) == NOTE
1632 && NOTE_LINE_NUMBER (PREV_INSN (before)) == NOTE_INSN_LOOP_BEG)
1633 before = PREV_INSN (before);
1637 /* We'd better be fallthru, or we've lost track of what's what. */
1638 if ((e->flags & EDGE_FALLTHRU) == 0)
1645 /* Otherwise we must split the edge. */
1648 bb = split_edge (e);
1652 /* Now that we've found the spot, do the insertion. */
1656 emit_insns_before (insns, before);
1657 last = prev_nonnote_insn (before);
1660 last = emit_insns_after (insns, after);
1662 if (returnjump_p (last))
1664 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1665 This is not currently a problem because this only happens
1666 for the (single) epilogue, which already has a fallthru edge
1670 if (e->dest != EXIT_BLOCK_PTR
1671 || e->succ_next != NULL
1672 || (e->flags & EDGE_FALLTHRU) == 0)
1674 e->flags &= ~EDGE_FALLTHRU;
1676 emit_barrier_after (last);
1679 delete_insn (before);
1681 else if (GET_CODE (last) == JUMP_INSN)
1683 find_sub_basic_blocks (bb);
1686 /* Update the CFG for all queued instructions. */
1689 commit_edge_insertions ()
1694 #ifdef ENABLE_CHECKING
1695 verify_flow_info ();
1699 bb = ENTRY_BLOCK_PTR;
1704 for (e = bb->succ; e; e = next)
1706 next = e->succ_next;
1708 commit_one_edge_insertion (e);
1711 if (++i >= n_basic_blocks)
1713 bb = BASIC_BLOCK (i);
1718 dump_flow_info (file)
1722 static const char * const reg_class_names[] = REG_CLASS_NAMES;
1724 fprintf (file, "%d registers.\n", max_regno);
1725 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1728 enum reg_class class, altclass;
1729 fprintf (file, "\nRegister %d used %d times across %d insns",
1730 i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
1731 if (REG_BASIC_BLOCK (i) >= 0)
1732 fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
1734 fprintf (file, "; set %d time%s", REG_N_SETS (i),
1735 (REG_N_SETS (i) == 1) ? "" : "s");
1736 if (REG_USERVAR_P (regno_reg_rtx[i]))
1737 fprintf (file, "; user var");
1738 if (REG_N_DEATHS (i) != 1)
1739 fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
1740 if (REG_N_CALLS_CROSSED (i) == 1)
1741 fprintf (file, "; crosses 1 call");
1742 else if (REG_N_CALLS_CROSSED (i))
1743 fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
1744 if (PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
1745 fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
1746 class = reg_preferred_class (i);
1747 altclass = reg_alternate_class (i);
1748 if (class != GENERAL_REGS || altclass != ALL_REGS)
1750 if (altclass == ALL_REGS || class == ALL_REGS)
1751 fprintf (file, "; pref %s", reg_class_names[(int) class]);
1752 else if (altclass == NO_REGS)
1753 fprintf (file, "; %s or none", reg_class_names[(int) class]);
1755 fprintf (file, "; pref %s, else %s",
1756 reg_class_names[(int) class],
1757 reg_class_names[(int) altclass]);
1759 if (REG_POINTER (regno_reg_rtx[i]))
1760 fprintf (file, "; pointer");
1761 fprintf (file, ".\n");
1764 fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
1765 for (i = 0; i < n_basic_blocks; i++)
1767 register basic_block bb = BASIC_BLOCK (i);
1770 fprintf (file, "\nBasic block %d: first insn %d, last %d, loop_depth %d, count ",
1771 i, INSN_UID (bb->head), INSN_UID (bb->end), bb->loop_depth);
1772 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
1773 fprintf (file, ", freq %i.\n", bb->frequency);
1775 fprintf (file, "Predecessors: ");
1776 for (e = bb->pred; e; e = e->pred_next)
1777 dump_edge_info (file, e, 0);
1779 fprintf (file, "\nSuccessors: ");
1780 for (e = bb->succ; e; e = e->succ_next)
1781 dump_edge_info (file, e, 1);
1783 fprintf (file, "\nRegisters live at start:");
1784 dump_regset (bb->global_live_at_start, file);
1786 fprintf (file, "\nRegisters live at end:");
1787 dump_regset (bb->global_live_at_end, file);
1798 dump_flow_info (stderr);
1802 dump_edge_info (file, e, do_succ)
1807 basic_block side = (do_succ ? e->dest : e->src);
1809 if (side == ENTRY_BLOCK_PTR)
1810 fputs (" ENTRY", file);
1811 else if (side == EXIT_BLOCK_PTR)
1812 fputs (" EXIT", file);
1814 fprintf (file, " %d", side->index);
1817 fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
1821 fprintf (file, " count:");
1822 fprintf (file, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) e->count);
1827 static const char * const bitnames[] = {
1828 "fallthru", "ab", "abcall", "eh", "fake", "dfs_back"
1831 int i, flags = e->flags;
1835 for (i = 0; flags; i++)
1836 if (flags & (1 << i))
1842 if (i < (int) ARRAY_SIZE (bitnames))
1843 fputs (bitnames[i], file);
1845 fprintf (file, "%d", i);
1852 /* Print out one basic block with live information at start and end. */
1863 fprintf (outf, ";; Basic block %d, loop depth %d, count ",
1864 bb->index, bb->loop_depth);
1865 fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
1868 fputs (";; Predecessors: ", outf);
1869 for (e = bb->pred; e; e = e->pred_next)
1870 dump_edge_info (outf, e, 0);
1873 fputs (";; Registers live at start:", outf);
1874 dump_regset (bb->global_live_at_start, outf);
1877 for (insn = bb->head, last = NEXT_INSN (bb->end);
1879 insn = NEXT_INSN (insn))
1880 print_rtl_single (outf, insn);
1882 fputs (";; Registers live at end:", outf);
1883 dump_regset (bb->global_live_at_end, outf);
1886 fputs (";; Successors: ", outf);
1887 for (e = bb->succ; e; e = e->succ_next)
1888 dump_edge_info (outf, e, 1);
1896 dump_bb (bb, stderr);
1903 dump_bb (BASIC_BLOCK (n), stderr);
1906 /* Like print_rtl, but also print out live information for the start of each
1910 print_rtl_with_bb (outf, rtx_first)
1914 register rtx tmp_rtx;
1917 fprintf (outf, "(nil)\n");
1921 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
1922 int max_uid = get_max_uid ();
1923 basic_block *start = (basic_block *)
1924 xcalloc (max_uid, sizeof (basic_block));
1925 basic_block *end = (basic_block *)
1926 xcalloc (max_uid, sizeof (basic_block));
1927 enum bb_state *in_bb_p = (enum bb_state *)
1928 xcalloc (max_uid, sizeof (enum bb_state));
1930 for (i = n_basic_blocks - 1; i >= 0; i--)
1932 basic_block bb = BASIC_BLOCK (i);
1935 start[INSN_UID (bb->head)] = bb;
1936 end[INSN_UID (bb->end)] = bb;
1937 for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x))
1939 enum bb_state state = IN_MULTIPLE_BB;
1940 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
1942 in_bb_p[INSN_UID (x)] = state;
1949 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
1954 if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
1956 fprintf (outf, ";; Start of basic block %d, registers live:",
1958 dump_regset (bb->global_live_at_start, outf);
1962 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
1963 && GET_CODE (tmp_rtx) != NOTE
1964 && GET_CODE (tmp_rtx) != BARRIER)
1965 fprintf (outf, ";; Insn is not within a basic block\n");
1966 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
1967 fprintf (outf, ";; Insn is in multiple basic blocks\n");
1969 did_output = print_rtl_single (outf, tmp_rtx);
1971 if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
1973 fprintf (outf, ";; End of basic block %d, registers live:\n",
1975 dump_regset (bb->global_live_at_end, outf);
1988 if (current_function_epilogue_delay_list != 0)
1990 fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
1991 for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0;
1992 tmp_rtx = XEXP (tmp_rtx, 1))
1993 print_rtl_single (outf, XEXP (tmp_rtx, 0));
1997 /* Verify the CFG consistency. This function check some CFG invariants and
1998 aborts when something is wrong. Hope that this function will help to
1999 convert many optimization passes to preserve CFG consistent.
2001 Currently it does following checks:
2003 - test head/end pointers
2004 - overlapping of basic blocks
2005 - edge list correctness
2006 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2007 - tails of basic blocks (ensure that boundary is necesary)
2008 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2009 and NOTE_INSN_BASIC_BLOCK
2010 - check that all insns are in the basic blocks
2011 (except the switch handling code, barriers and notes)
2012 - check that all returns are followed by barriers
2014 In future it can be extended check a lot of other stuff as well
2015 (reachability of basic blocks, life information, etc. etc.). */
2020 const int max_uid = get_max_uid ();
2021 const rtx rtx_first = get_insns ();
2022 rtx last_head = get_last_insn ();
2023 basic_block *bb_info, *last_visited;
2024 size_t *edge_checksum;
2026 int i, last_bb_num_seen, num_bb_notes, err = 0;
2028 bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
2029 last_visited = (basic_block *) xcalloc (n_basic_blocks + 2,
2030 sizeof (basic_block));
2031 edge_checksum = (size_t *) xcalloc (n_basic_blocks + 2, sizeof (size_t));
2033 for (i = n_basic_blocks - 1; i >= 0; i--)
2035 basic_block bb = BASIC_BLOCK (i);
2036 rtx head = bb->head;
2039 /* Verify the end of the basic block is in the INSN chain. */
2040 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2045 error ("End insn %d for block %d not found in the insn stream.",
2046 INSN_UID (end), bb->index);
2050 /* Work backwards from the end to the head of the basic block
2051 to verify the head is in the RTL chain. */
2052 for (; x != NULL_RTX; x = PREV_INSN (x))
2054 /* While walking over the insn chain, verify insns appear
2055 in only one basic block and initialize the BB_INFO array
2056 used by other passes. */
2057 if (bb_info[INSN_UID (x)] != NULL)
2059 error ("Insn %d is in multiple basic blocks (%d and %d)",
2060 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
2063 bb_info[INSN_UID (x)] = bb;
2070 error ("Head insn %d for block %d not found in the insn stream.",
2071 INSN_UID (head), bb->index);
2078 /* Now check the basic blocks (boundaries etc.) */
2079 for (i = n_basic_blocks - 1; i >= 0; i--)
2081 basic_block bb = BASIC_BLOCK (i);
2082 int has_fallthru = 0;
2088 if (last_visited [e->dest->index + 2] == bb)
2090 error ("verify_flow_info: Duplicate edge %i->%i",
2091 e->src->index, e->dest->index);
2094 last_visited [e->dest->index + 2] = bb;
2096 if (e->flags & EDGE_FALLTHRU)
2099 if ((e->flags & EDGE_FALLTHRU)
2100 && e->src != ENTRY_BLOCK_PTR
2101 && e->dest != EXIT_BLOCK_PTR)
2104 if (e->src->index + 1 != e->dest->index)
2106 error ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2107 e->src->index, e->dest->index);
2111 for (insn = NEXT_INSN (e->src->end); insn != e->dest->head;
2112 insn = NEXT_INSN (insn))
2113 if (GET_CODE (insn) == BARRIER || INSN_P (insn))
2115 error ("verify_flow_info: Incorrect fallthru %i->%i",
2116 e->src->index, e->dest->index);
2117 fatal_insn ("Wrong insn in the fallthru edge", insn);
2123 error ("verify_flow_info: Basic block %d succ edge is corrupted",
2125 fprintf (stderr, "Predecessor: ");
2126 dump_edge_info (stderr, e, 0);
2127 fprintf (stderr, "\nSuccessor: ");
2128 dump_edge_info (stderr, e, 1);
2129 fprintf (stderr, "\n");
2132 edge_checksum[e->dest->index + 2] += (size_t) e;
2139 /* Ensure existence of barrier in BB with no fallthru edges. */
2140 for (insn = bb->end; GET_CODE (insn) != BARRIER;
2141 insn = NEXT_INSN (insn))
2143 || (GET_CODE (insn) == NOTE
2144 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK))
2146 error ("Missing barrier after block %i", bb->index);
2156 error ("Basic block %d pred edge is corrupted", bb->index);
2157 fputs ("Predecessor: ", stderr);
2158 dump_edge_info (stderr, e, 0);
2159 fputs ("\nSuccessor: ", stderr);
2160 dump_edge_info (stderr, e, 1);
2161 fputc ('\n', stderr);
2164 edge_checksum[e->dest->index + 2] -= (size_t) e;
2167 for (x = bb->head; x != NEXT_INSN (bb->end); x = NEXT_INSN (x))
2168 if (basic_block_for_insn && BLOCK_FOR_INSN (x) != bb)
2171 if (! BLOCK_FOR_INSN (x))
2172 error ("Insn %d is inside basic block %d but block_for_insn is NULL",
2173 INSN_UID (x), bb->index);
2175 error ("Insn %d is inside basic block %d but block_for_insn is %i",
2176 INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index);
2180 /* OK pointers are correct. Now check the header of basic
2181 block. It ought to contain optional CODE_LABEL followed
2182 by NOTE_BASIC_BLOCK. */
2184 if (GET_CODE (x) == CODE_LABEL)
2188 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2194 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
2196 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2203 /* Do checks for empty blocks here */
2210 if (NOTE_INSN_BASIC_BLOCK_P (x))
2212 error ("NOTE_INSN_BASIC_BLOCK %d in the middle of basic block %d",
2213 INSN_UID (x), bb->index);
2220 if (GET_CODE (x) == JUMP_INSN
2221 || GET_CODE (x) == CODE_LABEL
2222 || GET_CODE (x) == BARRIER)
2224 error ("In basic block %d:", bb->index);
2225 fatal_insn ("Flow control insn inside a basic block", x);
2233 /* Complete edge checksumming for ENTRY and EXIT. */
2236 for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
2237 edge_checksum[e->dest->index + 2] += (size_t) e;
2238 for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
2239 edge_checksum[e->dest->index + 2] -= (size_t) e;
2242 for (i = -2; i < n_basic_blocks; ++i)
2243 if (edge_checksum[i + 2])
2245 error ("Basic block %i edge lists are corrupted", i);
2249 last_bb_num_seen = -1;
2254 if (NOTE_INSN_BASIC_BLOCK_P (x))
2256 basic_block bb = NOTE_BASIC_BLOCK (x);
2258 if (bb->index != last_bb_num_seen + 1)
2259 internal_error ("Basic blocks not numbered consecutively.");
2261 last_bb_num_seen = bb->index;
2264 if (!bb_info[INSN_UID (x)])
2266 switch (GET_CODE (x))
2273 /* An addr_vec is placed outside any block block. */
2275 && GET_CODE (NEXT_INSN (x)) == JUMP_INSN
2276 && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
2277 || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
2282 /* But in any case, non-deletable labels can appear anywhere. */
2286 fatal_insn ("Insn outside basic block", x);
2291 && GET_CODE (x) == JUMP_INSN
2292 && returnjump_p (x) && ! condjump_p (x)
2293 && ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER))
2294 fatal_insn ("Return not followed by barrier", x);
2299 if (num_bb_notes != n_basic_blocks)
2301 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2302 num_bb_notes, n_basic_blocks);
2305 internal_error ("verify_flow_info failed.");
2309 free (last_visited);
2310 free (edge_checksum);
2313 /* Assume that the preceeding pass has possibly eliminated jump instructions
2314 or converted the unconditional jumps. Eliminate the edges from CFG.
2315 Return true if any edges are eliminated. */
2318 purge_dead_edges (bb)
2323 bool purged = false;
2325 if (GET_CODE (insn) == JUMP_INSN && !simplejump_p (insn))
2327 if (GET_CODE (insn) == JUMP_INSN)
2331 /* We do care only about conditional jumps and simplejumps. */
2332 if (!any_condjump_p (insn)
2333 && !returnjump_p (insn)
2334 && !simplejump_p (insn))
2336 for (e = bb->succ; e; e = next)
2338 next = e->succ_next;
2340 /* Check purposes we can have edge. */
2341 if ((e->flags & EDGE_FALLTHRU)
2342 && any_condjump_p (insn))
2344 if (e->dest != EXIT_BLOCK_PTR
2345 && e->dest->head == JUMP_LABEL (insn))
2347 if (e->dest == EXIT_BLOCK_PTR
2348 && returnjump_p (insn))
2353 if (!bb->succ || !purged)
2356 fprintf (rtl_dump_file, "Purged edges from bb %i\n", bb->index);
2360 /* Redistribute probabilities. */
2361 if (!bb->succ->succ_next)
2363 bb->succ->probability = REG_BR_PROB_BASE;
2364 bb->succ->count = bb->count;
2368 note = find_reg_note (insn, REG_BR_PROB, NULL);
2371 b = BRANCH_EDGE (bb);
2372 f = FALLTHRU_EDGE (bb);
2373 b->probability = INTVAL (XEXP (note, 0));
2374 f->probability = REG_BR_PROB_BASE - b->probability;
2375 b->count = bb->count * b->probability / REG_BR_PROB_BASE;
2376 f->count = bb->count * f->probability / REG_BR_PROB_BASE;
2381 /* Cleanup abnormal edges caused by throwing insns that have been
2383 if (! can_throw_internal (bb->end))
2384 for (e = bb->succ; e; e = next)
2386 next = e->succ_next;
2387 if (e->flags & EDGE_EH)
2394 /* If we don't see a jump insn, we don't know exactly why the block would
2395 have been broken at this point. Look for a simple, non-fallthru edge,
2396 as these are only created by conditional branches. If we find such an
2397 edge we know that there used to be a jump here and can then safely
2398 remove all non-fallthru edges. */
2399 for (e = bb->succ; e && (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU));
2403 for (e = bb->succ; e; e = next)
2405 next = e->succ_next;
2406 if (!(e->flags & EDGE_FALLTHRU))
2407 remove_edge (e), purged = true;
2409 if (!bb->succ || bb->succ->succ_next)
2411 bb->succ->probability = REG_BR_PROB_BASE;
2412 bb->succ->count = bb->count;
2415 fprintf (rtl_dump_file, "Purged non-fallthru edges from bb %i\n",
2420 /* Search all basic blocks for potentionally dead edges and purge them.
2422 Return true ifif some edge has been elliminated.
2426 purge_all_dead_edges ()
2428 int i, purged = false;
2429 for (i = 0; i < n_basic_blocks; i++)
2430 purged |= purge_dead_edges (BASIC_BLOCK (i));