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 that are aware of 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, merge_blocks_nomove
30 - Infrastructure to determine quickly basic block for instruction.
31 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
32 - Edge redirection with updating and optimizing instruction chain
33 block_label, redirect_edge_and_branch,
34 redirect_edge_and_branch_force, tidy_fallthru_edge, force_nonfallthru
35 - Edge splitting and commiting to edges
36 split_edge, insert_insn_on_edge, commit_edge_insertions
37 - Dumpipng and debugging
38 print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
39 - Consistency checking
41 - CFG updating after constant propagation
42 purge_dead_edges, purge_all_dead_edges
49 #include "hard-reg-set.h"
50 #include "basic-block.h"
60 /* Stubs in case we haven't got a return insn. */
63 #define gen_return() NULL_RTX
66 /* The basic block structure for every insn, indexed by uid. */
68 varray_type basic_block_for_insn;
70 /* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */
71 /* ??? Should probably be using LABEL_NUSES instead. It would take a
72 bit of surgery to be able to use or co-opt the routines in jump. */
75 rtx tail_recursion_label_list;
77 static int can_delete_note_p PARAMS ((rtx));
78 static int can_delete_label_p PARAMS ((rtx));
79 static void commit_one_edge_insertion PARAMS ((edge));
80 static bool try_redirect_by_replacing_jump PARAMS ((edge, basic_block));
81 static rtx last_loop_beg_note PARAMS ((rtx));
82 static bool back_edge_of_syntactic_loop_p PARAMS ((basic_block, basic_block));
83 static basic_block force_nonfallthru_and_redirect PARAMS ((edge, basic_block));
85 /* Return true if NOTE is not one of the ones that must be kept paired,
86 so that we may simply delete them. */
89 can_delete_note_p (note)
92 return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED
93 || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK);
96 /* True if a given label can be deleted. */
99 can_delete_label_p (label)
104 if (LABEL_PRESERVE_P (label))
107 for (x = forced_labels; x; x = XEXP (x, 1))
108 if (label == XEXP (x, 0))
110 for (x = label_value_list; x; x = XEXP (x, 1))
111 if (label == XEXP (x, 0))
113 for (x = exception_handler_labels; x; x = XEXP (x, 1))
114 if (label == XEXP (x, 0))
117 /* User declared labels must be preserved. */
118 if (LABEL_NAME (label) != 0)
124 /* Delete INSN by patching it out. Return the next insn. */
130 rtx next = NEXT_INSN (insn);
132 bool really_delete = true;
134 if (GET_CODE (insn) == CODE_LABEL)
136 /* Some labels can't be directly removed from the INSN chain, as they
137 might be references via variables, constant pool etc.
138 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
139 if (! can_delete_label_p (insn))
141 const char *name = LABEL_NAME (insn);
143 really_delete = false;
144 PUT_CODE (insn, NOTE);
145 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL;
146 NOTE_SOURCE_FILE (insn) = name;
148 remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
154 INSN_DELETED_P (insn) = 1;
157 /* If deleting a jump, decrement the use count of the label. Deleting
158 the label itself should happen in the normal course of block merging. */
159 if (GET_CODE (insn) == JUMP_INSN
161 && GET_CODE (JUMP_LABEL (insn)) == CODE_LABEL)
162 LABEL_NUSES (JUMP_LABEL (insn))--;
164 /* Also if deleting an insn that references a label. */
165 else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX
166 && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
167 LABEL_NUSES (XEXP (note, 0))--;
169 if (GET_CODE (insn) == JUMP_INSN
170 && (GET_CODE (PATTERN (insn)) == ADDR_VEC
171 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
173 rtx pat = PATTERN (insn);
174 int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC;
175 int len = XVECLEN (pat, diff_vec_p);
178 for (i = 0; i < len; i++)
179 LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
185 /* Unlink a chain of insns between START and FINISH, leaving notes
186 that must be paired. */
189 delete_insn_chain (start, finish)
192 /* Unchain the insns one by one. It would be quicker to delete all
193 of these with a single unchaining, rather than one at a time, but
194 we need to keep the NOTE's. */
200 next = NEXT_INSN (start);
201 if (GET_CODE (start) == NOTE && !can_delete_note_p (start))
204 next = delete_insn (start);
212 /* Create a new basic block consisting of the instructions between
213 HEAD and END inclusive. This function is designed to allow fast
214 BB construction - reuses the note and basic block struct
215 in BB_NOTE, if any and do not grow BASIC_BLOCK chain and should
216 be used directly only by CFG construction code.
217 END can be NULL in to create new empty basic block before HEAD.
218 Both END and HEAD can be NULL to create basic block at the end of
222 create_basic_block_structure (index, head, end, bb_note)
224 rtx head, end, bb_note;
229 && ! RTX_INTEGRATED_P (bb_note)
230 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
233 /* If we found an existing note, thread it back onto the chain. */
237 if (GET_CODE (head) == CODE_LABEL)
241 after = PREV_INSN (head);
245 if (after != bb_note && NEXT_INSN (after) != bb_note)
246 reorder_insns (bb_note, bb_note, after);
250 /* Otherwise we must create a note and a basic block structure. */
256 head = end = bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK,
259 else if (GET_CODE (head) == CODE_LABEL && end)
261 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
267 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
272 NOTE_BASIC_BLOCK (bb_note) = bb;
275 /* Always include the bb note in the block. */
276 if (NEXT_INSN (end) == bb_note)
282 BASIC_BLOCK (index) = bb;
283 if (basic_block_for_insn)
284 update_bb_for_insn (bb);
286 /* Tag the block so that we know it has been used when considering
287 other basic block notes. */
293 /* Create new basic block consisting of instructions in between HEAD and
294 END and place it to the BB chain at possition INDEX.
295 END can be NULL in to create new empty basic block before HEAD.
296 Both END and HEAD can be NULL to create basic block at the end of
300 create_basic_block (index, head, end)
307 /* Place the new block just after the block being split. */
308 VARRAY_GROW (basic_block_info, ++n_basic_blocks);
310 /* Some parts of the compiler expect blocks to be number in
311 sequential order so insert the new block immediately after the
312 block being split.. */
313 for (i = n_basic_blocks - 1; i > index; --i)
315 basic_block tmp = BASIC_BLOCK (i - 1);
316 BASIC_BLOCK (i) = tmp;
320 bb = create_basic_block_structure (index, head, end, NULL);
325 /* Delete the insns in a (non-live) block. We physically delete every
326 non-deleted-note insn, and update the flow graph appropriately.
328 Return nonzero if we deleted an exception handler. */
330 /* ??? Preserving all such notes strikes me as wrong. It would be nice
331 to post-process the stream to remove empty blocks, loops, ranges, etc. */
334 flow_delete_block (b)
337 int deleted_handler = 0;
340 /* If the head of this block is a CODE_LABEL, then it might be the
341 label for an exception handler which can't be reached.
343 We need to remove the label from the exception_handler_label list
344 and remove the associated NOTE_INSN_EH_REGION_BEG and
345 NOTE_INSN_EH_REGION_END notes. */
349 never_reached_warning (insn);
351 if (GET_CODE (insn) == CODE_LABEL)
352 maybe_remove_eh_handler (insn);
354 /* Include any jump table following the basic block. */
356 if (GET_CODE (end) == JUMP_INSN
357 && (tmp = JUMP_LABEL (end)) != NULL_RTX
358 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
359 && GET_CODE (tmp) == JUMP_INSN
360 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
361 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
364 /* Include any barrier that may follow the basic block. */
365 tmp = next_nonnote_insn (end);
366 if (tmp && GET_CODE (tmp) == BARRIER)
369 /* Selectively delete the entire chain. */
371 delete_insn_chain (insn, end);
373 /* Remove the edges into and out of this block. Note that there may
374 indeed be edges in, if we are removing an unreachable loop. */
375 while (b->pred != NULL)
376 remove_edge (b->pred);
377 while (b->succ != NULL)
378 remove_edge (b->succ);
383 /* Remove the basic block from the array, and compact behind it. */
386 return deleted_handler;
389 /* Records the basic block struct in BB_FOR_INSN, for every instruction
390 indexed by INSN_UID. MAX is the size of the array. */
393 compute_bb_for_insn (max)
398 if (basic_block_for_insn)
399 VARRAY_FREE (basic_block_for_insn);
400 VARRAY_BB_INIT (basic_block_for_insn, max, "basic_block_for_insn");
402 for (i = 0; i < n_basic_blocks; ++i)
404 basic_block bb = BASIC_BLOCK (i);
411 int uid = INSN_UID (insn);
413 VARRAY_BB (basic_block_for_insn, uid) = bb;
416 insn = NEXT_INSN (insn);
421 /* Release the basic_block_for_insn array. */
426 if (basic_block_for_insn)
427 VARRAY_FREE (basic_block_for_insn);
428 basic_block_for_insn = 0;
431 /* Update insns block within BB. */
434 update_bb_for_insn (bb)
439 if (! basic_block_for_insn)
442 for (insn = bb->head; ; insn = NEXT_INSN (insn))
444 set_block_for_insn (insn, bb);
451 /* Record INSN's block as BB. */
454 set_block_for_insn (insn, bb)
458 size_t uid = INSN_UID (insn);
459 if (uid >= basic_block_for_insn->num_elements)
463 /* Add one-eighth the size so we don't keep calling xrealloc. */
464 new_size = uid + (uid + 7) / 8;
466 VARRAY_GROW (basic_block_for_insn, new_size);
468 VARRAY_BB (basic_block_for_insn, uid) = bb;
471 /* Split a block BB after insn INSN creating a new fallthru edge.
472 Return the new edge. Note that to keep other parts of the compiler happy,
473 this function renumbers all the basic blocks so that the new
474 one has a number one greater than the block split. */
477 split_block (bb, insn)
485 /* There is no point splitting the block after its end. */
489 /* Create the new basic block. */
490 new_bb = create_basic_block (bb->index + 1, NEXT_INSN (insn), bb->end);
491 new_bb->count = bb->count;
492 new_bb->frequency = bb->frequency;
493 new_bb->loop_depth = bb->loop_depth;
496 /* Redirect the outgoing edges. */
497 new_bb->succ = bb->succ;
499 for (e = new_bb->succ; e; e = e->succ_next)
502 new_edge = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
504 if (bb->global_live_at_start)
506 new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
507 new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
508 COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
510 /* We now have to calculate which registers are live at the end
511 of the split basic block and at the start of the new basic
512 block. Start with those registers that are known to be live
513 at the end of the original basic block and get
514 propagate_block to determine which registers are live. */
515 COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_end);
516 propagate_block (new_bb, new_bb->global_live_at_start, NULL, NULL, 0);
517 COPY_REG_SET (bb->global_live_at_end,
518 new_bb->global_live_at_start);
524 /* Blocks A and B are to be merged into a single block A. The insns
525 are already contiguous, hence `nomove'. */
528 merge_blocks_nomove (a, b)
532 rtx b_head, b_end, a_end;
533 rtx del_first = NULL_RTX, del_last = NULL_RTX;
536 /* If there was a CODE_LABEL beginning B, delete it. */
539 if (GET_CODE (b_head) == CODE_LABEL)
541 /* Detect basic blocks with nothing but a label. This can happen
542 in particular at the end of a function. */
545 del_first = del_last = b_head;
546 b_head = NEXT_INSN (b_head);
549 /* Delete the basic block note. */
550 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
557 b_head = NEXT_INSN (b_head);
560 /* If there was a jump out of A, delete it. */
562 if (GET_CODE (a_end) == JUMP_INSN)
566 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
567 if (GET_CODE (prev) != NOTE
568 || NOTE_LINE_NUMBER (prev) == NOTE_INSN_BASIC_BLOCK
575 /* If this was a conditional jump, we need to also delete
576 the insn that set cc0. */
577 if (only_sets_cc0_p (prev))
580 prev = prev_nonnote_insn (prev);
587 a_end = PREV_INSN (del_first);
589 else if (GET_CODE (NEXT_INSN (a_end)) == BARRIER)
590 del_first = NEXT_INSN (a_end);
592 /* Normally there should only be one successor of A and that is B, but
593 partway though the merge of blocks for conditional_execution we'll
594 be merging a TEST block with THEN and ELSE successors. Free the
595 whole lot of them and hope the caller knows what they're doing. */
597 remove_edge (a->succ);
599 /* Adjust the edges out of B for the new owner. */
600 for (e = b->succ; e; e = e->succ_next)
604 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
605 b->pred = b->succ = NULL;
606 a->global_live_at_end = b->global_live_at_end;
610 /* Delete everything marked above as well as crap that might be
611 hanging out between the two blocks. */
612 delete_insn_chain (del_first, del_last);
614 /* Reassociate the insns of B with A. */
618 if (basic_block_for_insn)
620 BLOCK_FOR_INSN (x) = a;
624 BLOCK_FOR_INSN (x) = a;
632 /* Return label in the head of basic block. Create one if it doesn't exist. */
638 if (block == EXIT_BLOCK_PTR)
640 if (GET_CODE (block->head) != CODE_LABEL)
642 block->head = emit_label_before (gen_label_rtx (), block->head);
643 if (basic_block_for_insn)
644 set_block_for_insn (block->head, block);
649 /* Attempt to perform edge redirection by replacing possibly complex jump
650 instruction by unconditional jump or removing jump completely.
651 This can apply only if all edges now point to the same block.
653 The parameters and return values are equivalent to redirect_edge_and_branch.
657 try_redirect_by_replacing_jump (e, target)
661 basic_block src = e->src;
662 rtx insn = src->end, kill_from;
667 /* Verify that all targets will be TARGET. */
668 for (tmp = src->succ; tmp; tmp = tmp->succ_next)
669 if (tmp->dest != target && tmp != e)
671 if (tmp || !onlyjump_p (insn))
674 /* Avoid removing branch with side effects. */
675 set = single_set (insn);
676 if (!set || side_effects_p (set))
679 /* In case we zap a conditional jump, we'll need to kill
680 the cc0 setter too. */
683 if (reg_mentioned_p (cc0_rtx, PATTERN (insn)))
684 kill_from = PREV_INSN (insn);
687 /* See if we can create the fallthru edge. */
688 if (can_fallthru (src, target))
691 fprintf (rtl_dump_file, "Removing jump %i.\n", INSN_UID (insn));
694 /* Selectivly unlink whole insn chain. */
695 delete_insn_chain (kill_from, PREV_INSN (target->head));
697 /* If this already is simplejump, redirect it. */
698 else if (simplejump_p (insn))
700 if (e->dest == target)
703 fprintf (rtl_dump_file, "Redirecting jump %i from %i to %i.\n",
704 INSN_UID (insn), e->dest->index, target->index);
705 redirect_jump (insn, block_label (target), 0);
707 /* Or replace possibly complicated jump insn by simple jump insn. */
710 rtx target_label = block_label (target);
713 emit_jump_insn_after (gen_jump (target_label), kill_from);
714 JUMP_LABEL (src->end) = target_label;
715 LABEL_NUSES (target_label)++;
717 fprintf (rtl_dump_file, "Replacing insn %i by jump %i\n",
718 INSN_UID (insn), INSN_UID (src->end));
720 delete_insn_chain (kill_from, insn);
722 barrier = next_nonnote_insn (src->end);
723 if (!barrier || GET_CODE (barrier) != BARRIER)
724 emit_barrier_after (src->end);
727 /* Keep only one edge out and set proper flags. */
728 while (src->succ->succ_next)
729 remove_edge (src->succ);
732 e->flags = EDGE_FALLTHRU;
735 e->probability = REG_BR_PROB_BASE;
736 e->count = src->count;
738 /* We don't want a block to end on a line-number note since that has
739 the potential of changing the code between -g and not -g. */
740 while (GET_CODE (e->src->end) == NOTE
741 && NOTE_LINE_NUMBER (e->src->end) >= 0)
742 delete_insn (e->src->end);
744 if (e->dest != target)
745 redirect_edge_succ (e, target);
749 /* Return last loop_beg note appearing after INSN, before start of next
750 basic block. Return INSN if there are no such notes.
752 When emmiting jump to redirect an fallthru edge, it should always
753 appear after the LOOP_BEG notes, as loop optimizer expect loop to
754 eighter start by fallthru edge or jump following the LOOP_BEG note
755 jumping to the loop exit test. */
758 last_loop_beg_note (insn)
762 insn = NEXT_INSN (insn);
763 while (insn && GET_CODE (insn) == NOTE
764 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK)
766 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
768 insn = NEXT_INSN (insn);
773 /* Attempt to change code to redirect edge E to TARGET.
774 Don't do that on expense of adding new instructions or reordering
777 Function can be also called with edge destionation equivalent to the
778 TARGET. Then it should try the simplifications and do nothing if
781 Return true if transformation suceeded. We still return flase in case
782 E already destinated TARGET and we didn't managed to simplify instruction
786 redirect_edge_and_branch (e, target)
791 rtx old_label = e->dest->head;
792 basic_block src = e->src;
795 if (e->flags & EDGE_COMPLEX)
798 if (try_redirect_by_replacing_jump (e, target))
800 /* Do this fast path late, as we want above code to simplify for cases
801 where called on single edge leaving basic block containing nontrivial
803 else if (e->dest == target)
806 /* We can only redirect non-fallthru edges of jump insn. */
807 if (e->flags & EDGE_FALLTHRU)
809 if (GET_CODE (insn) != JUMP_INSN)
812 /* Recognize a tablejump and adjust all matching cases. */
813 if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
814 && (tmp = NEXT_INSN (tmp)) != NULL_RTX
815 && GET_CODE (tmp) == JUMP_INSN
816 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC
817 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
821 rtx new_label = block_label (target);
823 if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
824 vec = XVEC (PATTERN (tmp), 0);
826 vec = XVEC (PATTERN (tmp), 1);
828 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
829 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
831 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
832 --LABEL_NUSES (old_label);
833 ++LABEL_NUSES (new_label);
836 /* Handle casesi dispatch insns */
837 if ((tmp = single_set (insn)) != NULL
838 && SET_DEST (tmp) == pc_rtx
839 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
840 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
841 && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
843 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (VOIDmode,
845 --LABEL_NUSES (old_label);
846 ++LABEL_NUSES (new_label);
851 /* ?? We may play the games with moving the named labels from
852 one basic block to the other in case only one computed_jump is
854 if (computed_jump_p (insn))
857 /* A return instruction can't be redirected. */
858 if (returnjump_p (insn))
861 /* If the insn doesn't go where we think, we're confused. */
862 if (JUMP_LABEL (insn) != old_label)
864 /* If the substitution doesn't succeed, die. This can happen
865 if the back end emitted unrecognizable instructions. */
866 if (! redirect_jump (insn, block_label (target), 0))
871 fprintf (rtl_dump_file, "Edge %i->%i redirected to %i\n",
872 e->src->index, e->dest->index, target->index);
873 if (e->dest != target)
874 redirect_edge_succ_nodup (e, target);
878 /* Like force_nonfallthru below, but additionally performs redirection
879 Used by redirect_edge_and_branch_force. */
882 force_nonfallthru_and_redirect (e, target)
886 basic_block jump_block, new_bb = NULL;
890 if (e->flags & EDGE_ABNORMAL)
892 if (!(e->flags & EDGE_FALLTHRU))
894 if (e->src->succ->succ_next)
896 /* Create the new structures. */
897 note = last_loop_beg_note (e->src->end);
898 jump_block = create_basic_block (e->src->index + 1, NEXT_INSN (note), NULL);
899 jump_block->count = e->count;
900 jump_block->frequency = EDGE_FREQUENCY (e);
901 jump_block->loop_depth = target->loop_depth;
903 if (target->global_live_at_start)
905 jump_block->global_live_at_start =
906 OBSTACK_ALLOC_REG_SET (&flow_obstack);
907 jump_block->global_live_at_end =
908 OBSTACK_ALLOC_REG_SET (&flow_obstack);
909 COPY_REG_SET (jump_block->global_live_at_start,
910 target->global_live_at_start);
911 COPY_REG_SET (jump_block->global_live_at_end,
912 target->global_live_at_start);
916 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
917 new_edge->probability = e->probability;
918 new_edge->count = e->count;
920 /* Redirect old edge. */
921 redirect_edge_pred (e, jump_block);
922 e->probability = REG_BR_PROB_BASE;
928 e->flags &= ~EDGE_FALLTHRU;
929 if (target == EXIT_BLOCK_PTR)
932 emit_jump_insn_after (gen_return (), jump_block->end);
938 rtx label = block_label (target);
939 emit_jump_insn_after (gen_jump (label), jump_block->end);
940 JUMP_LABEL (jump_block->end) = label;
941 LABEL_NUSES (label)++;
943 emit_barrier_after (jump_block->end);
944 redirect_edge_succ_nodup (e, target);
949 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
950 (and possibly create new basic block) to make edge non-fallthru.
951 Return newly created BB or NULL if none. */
953 force_nonfallthru (e)
956 return force_nonfallthru_and_redirect (e, e->dest);
959 /* Redirect edge even at the expense of creating new jump insn or
960 basic block. Return new basic block if created, NULL otherwise.
961 Abort if converison is impossible. */
964 redirect_edge_and_branch_force (e, target)
970 if (redirect_edge_and_branch (e, target))
972 if (e->dest == target)
975 /* In case the edge redirection failed, try to force it to be non-fallthru
976 and redirect newly created simplejump. */
977 new_bb = force_nonfallthru_and_redirect (e, target);
981 /* The given edge should potentially be a fallthru edge. If that is in
982 fact true, delete the jump and barriers that are in the way. */
985 tidy_fallthru_edge (e, b, c)
991 /* ??? In a late-running flow pass, other folks may have deleted basic
992 blocks by nopping out blocks, leaving multiple BARRIERs between here
993 and the target label. They ought to be chastized and fixed.
995 We can also wind up with a sequence of undeletable labels between
996 one block and the next.
998 So search through a sequence of barriers, labels, and notes for
999 the head of block C and assert that we really do fall through. */
1001 if (next_real_insn (b->end) != next_real_insn (PREV_INSN (c->head)))
1004 /* Remove what will soon cease being the jump insn from the source block.
1005 If block B consisted only of this single jump, turn it into a deleted
1008 if (GET_CODE (q) == JUMP_INSN
1010 && (any_uncondjump_p (q)
1011 || (b->succ == e && e->succ_next == NULL)))
1014 /* If this was a conditional jump, we need to also delete
1015 the insn that set cc0. */
1016 if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1022 /* We don't want a block to end on a line-number note since that has
1023 the potential of changing the code between -g and not -g. */
1024 while (GET_CODE (q) == NOTE && NOTE_LINE_NUMBER (q) >= 0)
1028 /* Selectively unlink the sequence. */
1029 if (q != PREV_INSN (c->head))
1030 delete_insn_chain (NEXT_INSN (q), PREV_INSN (c->head));
1032 e->flags |= EDGE_FALLTHRU;
1035 /* Fix up edges that now fall through, or rather should now fall through
1036 but previously required a jump around now deleted blocks. Simplify
1037 the search by only examining blocks numerically adjacent, since this
1038 is how find_basic_blocks created them. */
1041 tidy_fallthru_edges ()
1045 for (i = 1; i < n_basic_blocks; ++i)
1047 basic_block b = BASIC_BLOCK (i - 1);
1048 basic_block c = BASIC_BLOCK (i);
1051 /* We care about simple conditional or unconditional jumps with
1054 If we had a conditional branch to the next instruction when
1055 find_basic_blocks was called, then there will only be one
1056 out edge for the block which ended with the conditional
1057 branch (since we do not create duplicate edges).
1059 Furthermore, the edge will be marked as a fallthru because we
1060 merge the flags for the duplicate edges. So we do not want to
1061 check that the edge is not a FALLTHRU edge. */
1062 if ((s = b->succ) != NULL
1063 && ! (s->flags & EDGE_COMPLEX)
1064 && s->succ_next == NULL
1066 /* If the jump insn has side effects, we can't tidy the edge. */
1067 && (GET_CODE (b->end) != JUMP_INSN
1068 || onlyjump_p (b->end)))
1069 tidy_fallthru_edge (s, b, c);
1073 /* Helper function for split_edge. Return true in case edge BB2 to BB1
1074 is back edge of syntactic loop. */
1077 back_edge_of_syntactic_loop_p (bb1, bb2)
1078 basic_block bb1, bb2;
1083 if (bb1->index > bb2->index)
1086 if (bb1->index == bb2->index)
1089 for (insn = bb1->end; insn != bb2->head && count >= 0;
1090 insn = NEXT_INSN (insn))
1091 if (GET_CODE (insn) == NOTE)
1093 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1095 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1102 /* Split a (typically critical) edge. Return the new block.
1103 Abort on abnormal edges.
1105 ??? The code generally expects to be called on critical edges.
1106 The case of a block ending in an unconditional jump to a
1107 block with multiple predecessors is not handled optimally. */
1110 split_edge (edge_in)
1117 /* Abnormal edges cannot be split. */
1118 if ((edge_in->flags & EDGE_ABNORMAL) != 0)
1121 /* We are going to place the new block in front of edge destination.
1122 Avoid existence of fallthru predecesors. */
1123 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1126 for (e = edge_in->dest->pred; e; e = e->pred_next)
1127 if (e->flags & EDGE_FALLTHRU)
1131 force_nonfallthru (e);
1134 /* Create the basic block note.
1136 Where we place the note can have a noticeable impact on the generated
1137 code. Consider this cfg:
1147 If we need to insert an insn on the edge from block 0 to block 1,
1148 we want to ensure the instructions we insert are outside of any
1149 loop notes that physically sit between block 0 and block 1. Otherwise
1150 we confuse the loop optimizer into thinking the loop is a phony. */
1152 if (edge_in->dest != EXIT_BLOCK_PTR
1153 && PREV_INSN (edge_in->dest->head)
1154 && GET_CODE (PREV_INSN (edge_in->dest->head)) == NOTE
1155 && NOTE_LINE_NUMBER (PREV_INSN (edge_in->dest->head)) == NOTE_INSN_LOOP_BEG
1156 && !back_edge_of_syntactic_loop_p (edge_in->dest, edge_in->src))
1157 before = PREV_INSN (edge_in->dest->head);
1158 else if (edge_in->dest != EXIT_BLOCK_PTR)
1159 before = edge_in->dest->head;
1163 bb = create_basic_block (edge_in->dest == EXIT_BLOCK_PTR ? n_basic_blocks
1164 : edge_in->dest->index, before, NULL);
1165 bb->count = edge_in->count;
1166 bb->frequency = EDGE_FREQUENCY (edge_in);
1168 /* ??? This info is likely going to be out of date very soon. */
1169 if (edge_in->dest->global_live_at_start)
1171 bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1172 bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1173 COPY_REG_SET (bb->global_live_at_start, edge_in->dest->global_live_at_start);
1174 COPY_REG_SET (bb->global_live_at_end, edge_in->dest->global_live_at_start);
1177 edge_out = make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1179 /* For non-fallthry edges, we must adjust the predecessor's
1180 jump instruction to target our new block. */
1181 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1183 if (!redirect_edge_and_branch (edge_in, bb))
1187 redirect_edge_succ (edge_in, bb);
1192 /* Queue instructions for insertion on an edge between two basic blocks.
1193 The new instructions and basic blocks (if any) will not appear in the
1194 CFG until commit_edge_insertions is called. */
1197 insert_insn_on_edge (pattern, e)
1201 /* We cannot insert instructions on an abnormal critical edge.
1202 It will be easier to find the culprit if we die now. */
1203 if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
1206 if (e->insns == NULL_RTX)
1209 push_to_sequence (e->insns);
1211 emit_insn (pattern);
1213 e->insns = get_insns ();
1217 /* Update the CFG for the instructions queued on edge E. */
1220 commit_one_edge_insertion (e)
1223 rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
1226 /* Pull the insns off the edge now since the edge might go away. */
1228 e->insns = NULL_RTX;
1230 /* Figure out where to put these things. If the destination has
1231 one predecessor, insert there. Except for the exit block. */
1232 if (e->dest->pred->pred_next == NULL
1233 && e->dest != EXIT_BLOCK_PTR)
1237 /* Get the location correct wrt a code label, and "nice" wrt
1238 a basic block note, and before everything else. */
1240 if (GET_CODE (tmp) == CODE_LABEL)
1241 tmp = NEXT_INSN (tmp);
1242 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1243 tmp = NEXT_INSN (tmp);
1244 if (tmp == bb->head)
1247 after = PREV_INSN (tmp);
1250 /* If the source has one successor and the edge is not abnormal,
1251 insert there. Except for the entry block. */
1252 else if ((e->flags & EDGE_ABNORMAL) == 0
1253 && e->src->succ->succ_next == NULL
1254 && e->src != ENTRY_BLOCK_PTR)
1257 /* It is possible to have a non-simple jump here. Consider a target
1258 where some forms of unconditional jumps clobber a register. This
1259 happens on the fr30 for example.
1261 We know this block has a single successor, so we can just emit
1262 the queued insns before the jump. */
1263 if (GET_CODE (bb->end) == JUMP_INSN)
1266 while (GET_CODE (PREV_INSN (before)) == NOTE
1267 && NOTE_LINE_NUMBER (PREV_INSN (before)) == NOTE_INSN_LOOP_BEG)
1268 before = PREV_INSN (before);
1272 /* We'd better be fallthru, or we've lost track of what's what. */
1273 if ((e->flags & EDGE_FALLTHRU) == 0)
1280 /* Otherwise we must split the edge. */
1283 bb = split_edge (e);
1287 /* Now that we've found the spot, do the insertion. */
1291 emit_insns_before (insns, before);
1292 last = prev_nonnote_insn (before);
1295 last = emit_insns_after (insns, after);
1297 if (returnjump_p (last))
1299 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1300 This is not currently a problem because this only happens
1301 for the (single) epilogue, which already has a fallthru edge
1305 if (e->dest != EXIT_BLOCK_PTR
1306 || e->succ_next != NULL
1307 || (e->flags & EDGE_FALLTHRU) == 0)
1309 e->flags &= ~EDGE_FALLTHRU;
1311 emit_barrier_after (last);
1314 delete_insn (before);
1316 else if (GET_CODE (last) == JUMP_INSN)
1318 find_sub_basic_blocks (bb);
1321 /* Update the CFG for all queued instructions. */
1324 commit_edge_insertions ()
1329 #ifdef ENABLE_CHECKING
1330 verify_flow_info ();
1334 bb = ENTRY_BLOCK_PTR;
1339 for (e = bb->succ; e; e = next)
1341 next = e->succ_next;
1343 commit_one_edge_insertion (e);
1346 if (++i >= n_basic_blocks)
1348 bb = BASIC_BLOCK (i);
1352 /* Print out one basic block with live information at start and end. */
1363 fprintf (outf, ";; Basic block %d, loop depth %d, count ",
1364 bb->index, bb->loop_depth);
1365 fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
1368 fputs (";; Predecessors: ", outf);
1369 for (e = bb->pred; e; e = e->pred_next)
1370 dump_edge_info (outf, e, 0);
1373 fputs (";; Registers live at start:", outf);
1374 dump_regset (bb->global_live_at_start, outf);
1377 for (insn = bb->head, last = NEXT_INSN (bb->end);
1379 insn = NEXT_INSN (insn))
1380 print_rtl_single (outf, insn);
1382 fputs (";; Registers live at end:", outf);
1383 dump_regset (bb->global_live_at_end, outf);
1386 fputs (";; Successors: ", outf);
1387 for (e = bb->succ; e; e = e->succ_next)
1388 dump_edge_info (outf, e, 1);
1396 dump_bb (bb, stderr);
1403 dump_bb (BASIC_BLOCK (n), stderr);
1406 /* Like print_rtl, but also print out live information for the start of each
1410 print_rtl_with_bb (outf, rtx_first)
1417 fprintf (outf, "(nil)\n");
1421 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
1422 int max_uid = get_max_uid ();
1423 basic_block *start = (basic_block *)
1424 xcalloc (max_uid, sizeof (basic_block));
1425 basic_block *end = (basic_block *)
1426 xcalloc (max_uid, sizeof (basic_block));
1427 enum bb_state *in_bb_p = (enum bb_state *)
1428 xcalloc (max_uid, sizeof (enum bb_state));
1430 for (i = n_basic_blocks - 1; i >= 0; i--)
1432 basic_block bb = BASIC_BLOCK (i);
1435 start[INSN_UID (bb->head)] = bb;
1436 end[INSN_UID (bb->end)] = bb;
1437 for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x))
1439 enum bb_state state = IN_MULTIPLE_BB;
1440 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
1442 in_bb_p[INSN_UID (x)] = state;
1449 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
1454 if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
1456 fprintf (outf, ";; Start of basic block %d, registers live:",
1458 dump_regset (bb->global_live_at_start, outf);
1462 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
1463 && GET_CODE (tmp_rtx) != NOTE
1464 && GET_CODE (tmp_rtx) != BARRIER)
1465 fprintf (outf, ";; Insn is not within a basic block\n");
1466 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
1467 fprintf (outf, ";; Insn is in multiple basic blocks\n");
1469 did_output = print_rtl_single (outf, tmp_rtx);
1471 if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
1473 fprintf (outf, ";; End of basic block %d, registers live:\n",
1475 dump_regset (bb->global_live_at_end, outf);
1488 if (current_function_epilogue_delay_list != 0)
1490 fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
1491 for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0;
1492 tmp_rtx = XEXP (tmp_rtx, 1))
1493 print_rtl_single (outf, XEXP (tmp_rtx, 0));
1497 /* Verify the CFG consistency. This function check some CFG invariants and
1498 aborts when something is wrong. Hope that this function will help to
1499 convert many optimization passes to preserve CFG consistent.
1501 Currently it does following checks:
1503 - test head/end pointers
1504 - overlapping of basic blocks
1505 - edge list correctness
1506 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1507 - tails of basic blocks (ensure that boundary is necessary)
1508 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1509 and NOTE_INSN_BASIC_BLOCK
1510 - check that all insns are in the basic blocks
1511 (except the switch handling code, barriers and notes)
1512 - check that all returns are followed by barriers
1514 In future it can be extended check a lot of other stuff as well
1515 (reachability of basic blocks, life information, etc. etc.). */
1520 const int max_uid = get_max_uid ();
1521 const rtx rtx_first = get_insns ();
1522 rtx last_head = get_last_insn ();
1523 basic_block *bb_info, *last_visited;
1524 size_t *edge_checksum;
1526 int i, last_bb_num_seen, num_bb_notes, err = 0;
1528 bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
1529 last_visited = (basic_block *) xcalloc (n_basic_blocks + 2,
1530 sizeof (basic_block));
1531 edge_checksum = (size_t *) xcalloc (n_basic_blocks + 2, sizeof (size_t));
1533 for (i = n_basic_blocks - 1; i >= 0; i--)
1535 basic_block bb = BASIC_BLOCK (i);
1536 rtx head = bb->head;
1539 /* Verify the end of the basic block is in the INSN chain. */
1540 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
1545 error ("End insn %d for block %d not found in the insn stream.",
1546 INSN_UID (end), bb->index);
1550 /* Work backwards from the end to the head of the basic block
1551 to verify the head is in the RTL chain. */
1552 for (; x != NULL_RTX; x = PREV_INSN (x))
1554 /* While walking over the insn chain, verify insns appear
1555 in only one basic block and initialize the BB_INFO array
1556 used by other passes. */
1557 if (bb_info[INSN_UID (x)] != NULL)
1559 error ("Insn %d is in multiple basic blocks (%d and %d)",
1560 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
1563 bb_info[INSN_UID (x)] = bb;
1570 error ("Head insn %d for block %d not found in the insn stream.",
1571 INSN_UID (head), bb->index);
1578 /* Now check the basic blocks (boundaries etc.) */
1579 for (i = n_basic_blocks - 1; i >= 0; i--)
1581 basic_block bb = BASIC_BLOCK (i);
1582 int has_fallthru = 0;
1588 if (last_visited [e->dest->index + 2] == bb)
1590 error ("verify_flow_info: Duplicate edge %i->%i",
1591 e->src->index, e->dest->index);
1594 last_visited [e->dest->index + 2] = bb;
1596 if (e->flags & EDGE_FALLTHRU)
1599 if ((e->flags & EDGE_FALLTHRU)
1600 && e->src != ENTRY_BLOCK_PTR
1601 && e->dest != EXIT_BLOCK_PTR)
1604 if (e->src->index + 1 != e->dest->index)
1606 error ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
1607 e->src->index, e->dest->index);
1611 for (insn = NEXT_INSN (e->src->end); insn != e->dest->head;
1612 insn = NEXT_INSN (insn))
1613 if (GET_CODE (insn) == BARRIER || INSN_P (insn))
1615 error ("verify_flow_info: Incorrect fallthru %i->%i",
1616 e->src->index, e->dest->index);
1617 fatal_insn ("Wrong insn in the fallthru edge", insn);
1623 error ("verify_flow_info: Basic block %d succ edge is corrupted",
1625 fprintf (stderr, "Predecessor: ");
1626 dump_edge_info (stderr, e, 0);
1627 fprintf (stderr, "\nSuccessor: ");
1628 dump_edge_info (stderr, e, 1);
1629 fprintf (stderr, "\n");
1632 edge_checksum[e->dest->index + 2] += (size_t) e;
1639 /* Ensure existence of barrier in BB with no fallthru edges. */
1640 for (insn = bb->end; GET_CODE (insn) != BARRIER;
1641 insn = NEXT_INSN (insn))
1643 || (GET_CODE (insn) == NOTE
1644 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK))
1646 error ("Missing barrier after block %i", bb->index);
1656 error ("Basic block %d pred edge is corrupted", bb->index);
1657 fputs ("Predecessor: ", stderr);
1658 dump_edge_info (stderr, e, 0);
1659 fputs ("\nSuccessor: ", stderr);
1660 dump_edge_info (stderr, e, 1);
1661 fputc ('\n', stderr);
1664 edge_checksum[e->dest->index + 2] -= (size_t) e;
1667 for (x = bb->head; x != NEXT_INSN (bb->end); x = NEXT_INSN (x))
1668 if (basic_block_for_insn && BLOCK_FOR_INSN (x) != bb)
1671 if (! BLOCK_FOR_INSN (x))
1672 error ("Insn %d is inside basic block %d but block_for_insn is NULL",
1673 INSN_UID (x), bb->index);
1675 error ("Insn %d is inside basic block %d but block_for_insn is %i",
1676 INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index);
1680 /* OK pointers are correct. Now check the header of basic
1681 block. It ought to contain optional CODE_LABEL followed
1682 by NOTE_BASIC_BLOCK. */
1684 if (GET_CODE (x) == CODE_LABEL)
1688 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1694 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
1696 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1703 /* Do checks for empty blocks here */
1710 if (NOTE_INSN_BASIC_BLOCK_P (x))
1712 error ("NOTE_INSN_BASIC_BLOCK %d in the middle of basic block %d",
1713 INSN_UID (x), bb->index);
1720 if (GET_CODE (x) == JUMP_INSN
1721 || GET_CODE (x) == CODE_LABEL
1722 || GET_CODE (x) == BARRIER)
1724 error ("In basic block %d:", bb->index);
1725 fatal_insn ("Flow control insn inside a basic block", x);
1733 /* Complete edge checksumming for ENTRY and EXIT. */
1736 for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
1737 edge_checksum[e->dest->index + 2] += (size_t) e;
1738 for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
1739 edge_checksum[e->dest->index + 2] -= (size_t) e;
1742 for (i = -2; i < n_basic_blocks; ++i)
1743 if (edge_checksum[i + 2])
1745 error ("Basic block %i edge lists are corrupted", i);
1749 last_bb_num_seen = -1;
1754 if (NOTE_INSN_BASIC_BLOCK_P (x))
1756 basic_block bb = NOTE_BASIC_BLOCK (x);
1758 if (bb->index != last_bb_num_seen + 1)
1759 internal_error ("Basic blocks not numbered consecutively.");
1761 last_bb_num_seen = bb->index;
1764 if (!bb_info[INSN_UID (x)])
1766 switch (GET_CODE (x))
1773 /* An addr_vec is placed outside any block block. */
1775 && GET_CODE (NEXT_INSN (x)) == JUMP_INSN
1776 && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
1777 || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
1782 /* But in any case, non-deletable labels can appear anywhere. */
1786 fatal_insn ("Insn outside basic block", x);
1791 && GET_CODE (x) == JUMP_INSN
1792 && returnjump_p (x) && ! condjump_p (x)
1793 && ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER))
1794 fatal_insn ("Return not followed by barrier", x);
1799 if (num_bb_notes != n_basic_blocks)
1801 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
1802 num_bb_notes, n_basic_blocks);
1805 internal_error ("verify_flow_info failed.");
1809 free (last_visited);
1810 free (edge_checksum);
1813 /* Assume that the preceeding pass has possibly eliminated jump instructions
1814 or converted the unconditional jumps. Eliminate the edges from CFG.
1815 Return true if any edges are eliminated. */
1818 purge_dead_edges (bb)
1823 bool purged = false;
1825 if (GET_CODE (insn) == JUMP_INSN && !simplejump_p (insn))
1827 if (GET_CODE (insn) == JUMP_INSN)
1831 /* We do care only about conditional jumps and simplejumps. */
1832 if (!any_condjump_p (insn)
1833 && !returnjump_p (insn)
1834 && !simplejump_p (insn))
1836 for (e = bb->succ; e; e = next)
1838 next = e->succ_next;
1840 /* Check purposes we can have edge. */
1841 if ((e->flags & EDGE_FALLTHRU)
1842 && any_condjump_p (insn))
1844 if (e->dest != EXIT_BLOCK_PTR
1845 && e->dest->head == JUMP_LABEL (insn))
1847 if (e->dest == EXIT_BLOCK_PTR
1848 && returnjump_p (insn))
1853 if (!bb->succ || !purged)
1856 fprintf (rtl_dump_file, "Purged edges from bb %i\n", bb->index);
1860 /* Redistribute probabilities. */
1861 if (!bb->succ->succ_next)
1863 bb->succ->probability = REG_BR_PROB_BASE;
1864 bb->succ->count = bb->count;
1868 note = find_reg_note (insn, REG_BR_PROB, NULL);
1871 b = BRANCH_EDGE (bb);
1872 f = FALLTHRU_EDGE (bb);
1873 b->probability = INTVAL (XEXP (note, 0));
1874 f->probability = REG_BR_PROB_BASE - b->probability;
1875 b->count = bb->count * b->probability / REG_BR_PROB_BASE;
1876 f->count = bb->count * f->probability / REG_BR_PROB_BASE;
1881 /* Cleanup abnormal edges caused by throwing insns that have been
1883 if (! can_throw_internal (bb->end))
1884 for (e = bb->succ; e; e = next)
1886 next = e->succ_next;
1887 if (e->flags & EDGE_EH)
1894 /* If we don't see a jump insn, we don't know exactly why the block would
1895 have been broken at this point. Look for a simple, non-fallthru edge,
1896 as these are only created by conditional branches. If we find such an
1897 edge we know that there used to be a jump here and can then safely
1898 remove all non-fallthru edges. */
1899 for (e = bb->succ; e && (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU));
1903 for (e = bb->succ; e; e = next)
1905 next = e->succ_next;
1906 if (!(e->flags & EDGE_FALLTHRU))
1907 remove_edge (e), purged = true;
1909 if (!bb->succ || bb->succ->succ_next)
1911 bb->succ->probability = REG_BR_PROB_BASE;
1912 bb->succ->count = bb->count;
1915 fprintf (rtl_dump_file, "Purged non-fallthru edges from bb %i\n",
1920 /* Search all basic blocks for potentionally dead edges and purge them.
1922 Return true ifif some edge has been elliminated.
1926 purge_all_dead_edges ()
1928 int i, purged = false;
1929 for (i = 0; i < n_basic_blocks; i++)
1930 purged |= purge_dead_edges (BASIC_BLOCK (i));