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
;
609 /* Delete everything marked above as well as crap that might be
610 hanging out between the two blocks. */
611 delete_insn_chain (del_first
, del_last
);
613 /* Reassociate the insns of B with A. */
617 if (basic_block_for_insn
)
619 BLOCK_FOR_INSN (x
) = a
;
623 BLOCK_FOR_INSN (x
) = a
;
631 /* Return label in the head of basic block. Create one if it doesn't exist. */
637 if (block
== EXIT_BLOCK_PTR
)
639 if (GET_CODE (block
->head
) != CODE_LABEL
)
641 block
->head
= emit_label_before (gen_label_rtx (), block
->head
);
642 if (basic_block_for_insn
)
643 set_block_for_insn (block
->head
, block
);
648 /* Attempt to perform edge redirection by replacing possibly complex jump
649 instruction by unconditional jump or removing jump completely.
650 This can apply only if all edges now point to the same block.
652 The parameters and return values are equivalent to redirect_edge_and_branch.
656 try_redirect_by_replacing_jump (e
, target
)
660 basic_block src
= e
->src
;
661 rtx insn
= src
->end
, kill_from
;
666 /* Verify that all targets will be TARGET. */
667 for (tmp
= src
->succ
; tmp
; tmp
= tmp
->succ_next
)
668 if (tmp
->dest
!= target
&& tmp
!= e
)
670 if (tmp
|| !onlyjump_p (insn
))
673 /* Avoid removing branch with side effects. */
674 set
= single_set (insn
);
675 if (!set
|| side_effects_p (set
))
678 /* In case we zap a conditional jump, we'll need to kill
679 the cc0 setter too. */
682 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
)))
683 kill_from
= PREV_INSN (insn
);
686 /* See if we can create the fallthru edge. */
687 if (can_fallthru (src
, target
))
690 fprintf (rtl_dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
693 /* Selectivly unlink whole insn chain. */
694 delete_insn_chain (kill_from
, PREV_INSN (target
->head
));
696 /* If this already is simplejump, redirect it. */
697 else if (simplejump_p (insn
))
699 if (e
->dest
== target
)
702 fprintf (rtl_dump_file
, "Redirecting jump %i from %i to %i.\n",
703 INSN_UID (insn
), e
->dest
->index
, target
->index
);
704 redirect_jump (insn
, block_label (target
), 0);
706 /* Or replace possibly complicated jump insn by simple jump insn. */
709 rtx target_label
= block_label (target
);
712 emit_jump_insn_after (gen_jump (target_label
), kill_from
);
713 JUMP_LABEL (src
->end
) = target_label
;
714 LABEL_NUSES (target_label
)++;
716 fprintf (rtl_dump_file
, "Replacing insn %i by jump %i\n",
717 INSN_UID (insn
), INSN_UID (src
->end
));
719 delete_insn_chain (kill_from
, insn
);
721 barrier
= next_nonnote_insn (src
->end
);
722 if (!barrier
|| GET_CODE (barrier
) != BARRIER
)
723 emit_barrier_after (src
->end
);
726 /* Keep only one edge out and set proper flags. */
727 while (src
->succ
->succ_next
)
728 remove_edge (src
->succ
);
731 e
->flags
= EDGE_FALLTHRU
;
734 e
->probability
= REG_BR_PROB_BASE
;
735 e
->count
= src
->count
;
737 /* We don't want a block to end on a line-number note since that has
738 the potential of changing the code between -g and not -g. */
739 while (GET_CODE (e
->src
->end
) == NOTE
740 && NOTE_LINE_NUMBER (e
->src
->end
) >= 0)
741 delete_insn (e
->src
->end
);
743 if (e
->dest
!= target
)
744 redirect_edge_succ (e
, target
);
748 /* Return last loop_beg note appearing after INSN, before start of next
749 basic block. Return INSN if there are no such notes.
751 When emmiting jump to redirect an fallthru edge, it should always
752 appear after the LOOP_BEG notes, as loop optimizer expect loop to
753 eighter start by fallthru edge or jump following the LOOP_BEG note
754 jumping to the loop exit test. */
757 last_loop_beg_note (insn
)
761 insn
= NEXT_INSN (insn
);
762 while (insn
&& GET_CODE (insn
) == NOTE
763 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
)
765 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
767 insn
= NEXT_INSN (insn
);
772 /* Attempt to change code to redirect edge E to TARGET.
773 Don't do that on expense of adding new instructions or reordering
776 Function can be also called with edge destionation equivalent to the
777 TARGET. Then it should try the simplifications and do nothing if
780 Return true if transformation suceeded. We still return flase in case
781 E already destinated TARGET and we didn't managed to simplify instruction
785 redirect_edge_and_branch (e
, target
)
790 rtx old_label
= e
->dest
->head
;
791 basic_block src
= e
->src
;
794 if (e
->flags
& EDGE_COMPLEX
)
797 if (try_redirect_by_replacing_jump (e
, target
))
799 /* Do this fast path late, as we want above code to simplify for cases
800 where called on single edge leaving basic block containing nontrivial
802 else if (e
->dest
== target
)
805 /* We can only redirect non-fallthru edges of jump insn. */
806 if (e
->flags
& EDGE_FALLTHRU
)
808 if (GET_CODE (insn
) != JUMP_INSN
)
811 /* Recognize a tablejump and adjust all matching cases. */
812 if ((tmp
= JUMP_LABEL (insn
)) != NULL_RTX
813 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
814 && GET_CODE (tmp
) == JUMP_INSN
815 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
816 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
820 rtx new_label
= block_label (target
);
822 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
823 vec
= XVEC (PATTERN (tmp
), 0);
825 vec
= XVEC (PATTERN (tmp
), 1);
827 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
828 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
830 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
831 --LABEL_NUSES (old_label
);
832 ++LABEL_NUSES (new_label
);
835 /* Handle casesi dispatch insns */
836 if ((tmp
= single_set (insn
)) != NULL
837 && SET_DEST (tmp
) == pc_rtx
838 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
839 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
840 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
842 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (VOIDmode
,
844 --LABEL_NUSES (old_label
);
845 ++LABEL_NUSES (new_label
);
850 /* ?? We may play the games with moving the named labels from
851 one basic block to the other in case only one computed_jump is
853 if (computed_jump_p (insn
))
856 /* A return instruction can't be redirected. */
857 if (returnjump_p (insn
))
860 /* If the insn doesn't go where we think, we're confused. */
861 if (JUMP_LABEL (insn
) != old_label
)
863 /* If the substitution doesn't succeed, die. This can happen
864 if the back end emitted unrecognizable instructions. */
865 if (! redirect_jump (insn
, block_label (target
), 0))
870 fprintf (rtl_dump_file
, "Edge %i->%i redirected to %i\n",
871 e
->src
->index
, e
->dest
->index
, target
->index
);
872 if (e
->dest
!= target
)
873 redirect_edge_succ_nodup (e
, target
);
877 /* Like force_nonfallthru below, but additionally performs redirection
878 Used by redirect_edge_and_branch_force. */
881 force_nonfallthru_and_redirect (e
, target
)
885 basic_block jump_block
, new_bb
= NULL
;
889 if (e
->flags
& EDGE_ABNORMAL
)
891 if (!(e
->flags
& EDGE_FALLTHRU
))
893 if (e
->src
->succ
->succ_next
)
895 /* Create the new structures. */
896 note
= last_loop_beg_note (e
->src
->end
);
897 jump_block
= create_basic_block (e
->src
->index
+ 1, NEXT_INSN (note
), NULL
);
898 jump_block
->count
= e
->count
;
899 jump_block
->frequency
= EDGE_FREQUENCY (e
);
900 jump_block
->loop_depth
= target
->loop_depth
;
902 if (target
->global_live_at_start
)
904 jump_block
->global_live_at_start
=
905 OBSTACK_ALLOC_REG_SET (&flow_obstack
);
906 jump_block
->global_live_at_end
=
907 OBSTACK_ALLOC_REG_SET (&flow_obstack
);
908 COPY_REG_SET (jump_block
->global_live_at_start
,
909 target
->global_live_at_start
);
910 COPY_REG_SET (jump_block
->global_live_at_end
,
911 target
->global_live_at_start
);
915 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
916 new_edge
->probability
= e
->probability
;
917 new_edge
->count
= e
->count
;
919 /* Redirect old edge. */
920 redirect_edge_pred (e
, jump_block
);
921 e
->probability
= REG_BR_PROB_BASE
;
927 e
->flags
&= ~EDGE_FALLTHRU
;
928 if (target
== EXIT_BLOCK_PTR
)
931 emit_jump_insn_after (gen_return (), jump_block
->end
);
937 rtx label
= block_label (target
);
938 emit_jump_insn_after (gen_jump (label
), jump_block
->end
);
939 JUMP_LABEL (jump_block
->end
) = label
;
940 LABEL_NUSES (label
)++;
942 emit_barrier_after (jump_block
->end
);
943 redirect_edge_succ_nodup (e
, target
);
948 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
949 (and possibly create new basic block) to make edge non-fallthru.
950 Return newly created BB or NULL if none. */
952 force_nonfallthru (e
)
955 return force_nonfallthru_and_redirect (e
, e
->dest
);
958 /* Redirect edge even at the expense of creating new jump insn or
959 basic block. Return new basic block if created, NULL otherwise.
960 Abort if converison is impossible. */
963 redirect_edge_and_branch_force (e
, target
)
969 if (redirect_edge_and_branch (e
, target
))
971 if (e
->dest
== target
)
974 /* In case the edge redirection failed, try to force it to be non-fallthru
975 and redirect newly created simplejump. */
976 new_bb
= force_nonfallthru_and_redirect (e
, target
);
980 /* The given edge should potentially be a fallthru edge. If that is in
981 fact true, delete the jump and barriers that are in the way. */
984 tidy_fallthru_edge (e
, b
, c
)
990 /* ??? In a late-running flow pass, other folks may have deleted basic
991 blocks by nopping out blocks, leaving multiple BARRIERs between here
992 and the target label. They ought to be chastized and fixed.
994 We can also wind up with a sequence of undeletable labels between
995 one block and the next.
997 So search through a sequence of barriers, labels, and notes for
998 the head of block C and assert that we really do fall through. */
1000 if (next_real_insn (b
->end
) != next_real_insn (PREV_INSN (c
->head
)))
1003 /* Remove what will soon cease being the jump insn from the source block.
1004 If block B consisted only of this single jump, turn it into a deleted
1007 if (GET_CODE (q
) == JUMP_INSN
1009 && (any_uncondjump_p (q
)
1010 || (b
->succ
== e
&& e
->succ_next
== NULL
)))
1013 /* If this was a conditional jump, we need to also delete
1014 the insn that set cc0. */
1015 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1021 /* We don't want a block to end on a line-number note since that has
1022 the potential of changing the code between -g and not -g. */
1023 while (GET_CODE (q
) == NOTE
&& NOTE_LINE_NUMBER (q
) >= 0)
1027 /* Selectively unlink the sequence. */
1028 if (q
!= PREV_INSN (c
->head
))
1029 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (c
->head
));
1031 e
->flags
|= EDGE_FALLTHRU
;
1034 /* Fix up edges that now fall through, or rather should now fall through
1035 but previously required a jump around now deleted blocks. Simplify
1036 the search by only examining blocks numerically adjacent, since this
1037 is how find_basic_blocks created them. */
1040 tidy_fallthru_edges ()
1044 for (i
= 1; i
< n_basic_blocks
; ++i
)
1046 basic_block b
= BASIC_BLOCK (i
- 1);
1047 basic_block c
= BASIC_BLOCK (i
);
1050 /* We care about simple conditional or unconditional jumps with
1053 If we had a conditional branch to the next instruction when
1054 find_basic_blocks was called, then there will only be one
1055 out edge for the block which ended with the conditional
1056 branch (since we do not create duplicate edges).
1058 Furthermore, the edge will be marked as a fallthru because we
1059 merge the flags for the duplicate edges. So we do not want to
1060 check that the edge is not a FALLTHRU edge. */
1061 if ((s
= b
->succ
) != NULL
1062 && ! (s
->flags
& EDGE_COMPLEX
)
1063 && s
->succ_next
== NULL
1065 /* If the jump insn has side effects, we can't tidy the edge. */
1066 && (GET_CODE (b
->end
) != JUMP_INSN
1067 || onlyjump_p (b
->end
)))
1068 tidy_fallthru_edge (s
, b
, c
);
1072 /* Helper function for split_edge. Return true in case edge BB2 to BB1
1073 is back edge of syntactic loop. */
1076 back_edge_of_syntactic_loop_p (bb1
, bb2
)
1077 basic_block bb1
, bb2
;
1082 if (bb1
->index
> bb2
->index
)
1085 if (bb1
->index
== bb2
->index
)
1088 for (insn
= bb1
->end
; insn
!= bb2
->head
&& count
>= 0;
1089 insn
= NEXT_INSN (insn
))
1090 if (GET_CODE (insn
) == NOTE
)
1092 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
1094 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
)
1101 /* Split a (typically critical) edge. Return the new block.
1102 Abort on abnormal edges.
1104 ??? The code generally expects to be called on critical edges.
1105 The case of a block ending in an unconditional jump to a
1106 block with multiple predecessors is not handled optimally. */
1109 split_edge (edge_in
)
1116 /* Abnormal edges cannot be split. */
1117 if ((edge_in
->flags
& EDGE_ABNORMAL
) != 0)
1120 /* We are going to place the new block in front of edge destination.
1121 Avoid existence of fallthru predecesors. */
1122 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1125 for (e
= edge_in
->dest
->pred
; e
; e
= e
->pred_next
)
1126 if (e
->flags
& EDGE_FALLTHRU
)
1130 force_nonfallthru (e
);
1133 /* Create the basic block note.
1135 Where we place the note can have a noticable impact on the generated
1136 code. Consider this cfg:
1146 If we need to insert an insn on the edge from block 0 to block 1,
1147 we want to ensure the instructions we insert are outside of any
1148 loop notes that physically sit between block 0 and block 1. Otherwise
1149 we confuse the loop optimizer into thinking the loop is a phony. */
1151 if (edge_in
->dest
!= EXIT_BLOCK_PTR
1152 && PREV_INSN (edge_in
->dest
->head
)
1153 && GET_CODE (PREV_INSN (edge_in
->dest
->head
)) == NOTE
1154 && NOTE_LINE_NUMBER (PREV_INSN (edge_in
->dest
->head
)) == NOTE_INSN_LOOP_BEG
1155 && !back_edge_of_syntactic_loop_p (edge_in
->dest
, edge_in
->src
))
1156 before
= PREV_INSN (edge_in
->dest
->head
);
1157 else if (edge_in
->dest
!= EXIT_BLOCK_PTR
)
1158 before
= edge_in
->dest
->head
;
1162 bb
= create_basic_block (edge_in
->dest
== EXIT_BLOCK_PTR
? n_basic_blocks
1163 : edge_in
->dest
->index
, before
, NULL
);
1164 bb
->count
= edge_in
->count
;
1165 bb
->frequency
= EDGE_FREQUENCY (edge_in
);
1167 /* ??? This info is likely going to be out of date very soon. */
1168 if (edge_in
->dest
->global_live_at_start
)
1170 bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1171 bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1172 COPY_REG_SET (bb
->global_live_at_start
, edge_in
->dest
->global_live_at_start
);
1173 COPY_REG_SET (bb
->global_live_at_end
, edge_in
->dest
->global_live_at_start
);
1176 edge_out
= make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1178 /* For non-fallthry edges, we must adjust the predecessor's
1179 jump instruction to target our new block. */
1180 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1182 if (!redirect_edge_and_branch (edge_in
, bb
))
1186 redirect_edge_succ (edge_in
, bb
);
1191 /* Queue instructions for insertion on an edge between two basic blocks.
1192 The new instructions and basic blocks (if any) will not appear in the
1193 CFG until commit_edge_insertions is called. */
1196 insert_insn_on_edge (pattern
, e
)
1200 /* We cannot insert instructions on an abnormal critical edge.
1201 It will be easier to find the culprit if we die now. */
1202 if ((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
1205 if (e
->insns
== NULL_RTX
)
1208 push_to_sequence (e
->insns
);
1210 emit_insn (pattern
);
1212 e
->insns
= get_insns ();
1216 /* Update the CFG for the instructions queued on edge E. */
1219 commit_one_edge_insertion (e
)
1222 rtx before
= NULL_RTX
, after
= NULL_RTX
, insns
, tmp
, last
;
1225 /* Pull the insns off the edge now since the edge might go away. */
1227 e
->insns
= NULL_RTX
;
1229 /* Figure out where to put these things. If the destination has
1230 one predecessor, insert there. Except for the exit block. */
1231 if (e
->dest
->pred
->pred_next
== NULL
1232 && e
->dest
!= EXIT_BLOCK_PTR
)
1236 /* Get the location correct wrt a code label, and "nice" wrt
1237 a basic block note, and before everything else. */
1239 if (GET_CODE (tmp
) == CODE_LABEL
)
1240 tmp
= NEXT_INSN (tmp
);
1241 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1242 tmp
= NEXT_INSN (tmp
);
1243 if (tmp
== bb
->head
)
1246 after
= PREV_INSN (tmp
);
1249 /* If the source has one successor and the edge is not abnormal,
1250 insert there. Except for the entry block. */
1251 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1252 && e
->src
->succ
->succ_next
== NULL
1253 && e
->src
!= ENTRY_BLOCK_PTR
)
1256 /* It is possible to have a non-simple jump here. Consider a target
1257 where some forms of unconditional jumps clobber a register. This
1258 happens on the fr30 for example.
1260 We know this block has a single successor, so we can just emit
1261 the queued insns before the jump. */
1262 if (GET_CODE (bb
->end
) == JUMP_INSN
)
1265 while (GET_CODE (PREV_INSN (before
)) == NOTE
1266 && NOTE_LINE_NUMBER (PREV_INSN (before
)) == NOTE_INSN_LOOP_BEG
)
1267 before
= PREV_INSN (before
);
1271 /* We'd better be fallthru, or we've lost track of what's what. */
1272 if ((e
->flags
& EDGE_FALLTHRU
) == 0)
1279 /* Otherwise we must split the edge. */
1282 bb
= split_edge (e
);
1286 /* Now that we've found the spot, do the insertion. */
1290 emit_insns_before (insns
, before
);
1291 last
= prev_nonnote_insn (before
);
1294 last
= emit_insns_after (insns
, after
);
1296 if (returnjump_p (last
))
1298 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1299 This is not currently a problem because this only happens
1300 for the (single) epilogue, which already has a fallthru edge
1304 if (e
->dest
!= EXIT_BLOCK_PTR
1305 || e
->succ_next
!= NULL
1306 || (e
->flags
& EDGE_FALLTHRU
) == 0)
1308 e
->flags
&= ~EDGE_FALLTHRU
;
1310 emit_barrier_after (last
);
1313 delete_insn (before
);
1315 else if (GET_CODE (last
) == JUMP_INSN
)
1317 find_sub_basic_blocks (bb
);
1320 /* Update the CFG for all queued instructions. */
1323 commit_edge_insertions ()
1328 #ifdef ENABLE_CHECKING
1329 verify_flow_info ();
1333 bb
= ENTRY_BLOCK_PTR
;
1338 for (e
= bb
->succ
; e
; e
= next
)
1340 next
= e
->succ_next
;
1342 commit_one_edge_insertion (e
);
1345 if (++i
>= n_basic_blocks
)
1347 bb
= BASIC_BLOCK (i
);
1351 /* Print out one basic block with live information at start and end. */
1362 fprintf (outf
, ";; Basic block %d, loop depth %d, count ",
1363 bb
->index
, bb
->loop_depth
);
1364 fprintf (outf
, HOST_WIDEST_INT_PRINT_DEC
, (HOST_WIDEST_INT
) bb
->count
);
1367 fputs (";; Predecessors: ", outf
);
1368 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1369 dump_edge_info (outf
, e
, 0);
1372 fputs (";; Registers live at start:", outf
);
1373 dump_regset (bb
->global_live_at_start
, outf
);
1376 for (insn
= bb
->head
, last
= NEXT_INSN (bb
->end
);
1378 insn
= NEXT_INSN (insn
))
1379 print_rtl_single (outf
, insn
);
1381 fputs (";; Registers live at end:", outf
);
1382 dump_regset (bb
->global_live_at_end
, outf
);
1385 fputs (";; Successors: ", outf
);
1386 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1387 dump_edge_info (outf
, e
, 1);
1395 dump_bb (bb
, stderr
);
1402 dump_bb (BASIC_BLOCK (n
), stderr
);
1405 /* Like print_rtl, but also print out live information for the start of each
1409 print_rtl_with_bb (outf
, rtx_first
)
1416 fprintf (outf
, "(nil)\n");
1420 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
1421 int max_uid
= get_max_uid ();
1422 basic_block
*start
= (basic_block
*)
1423 xcalloc (max_uid
, sizeof (basic_block
));
1424 basic_block
*end
= (basic_block
*)
1425 xcalloc (max_uid
, sizeof (basic_block
));
1426 enum bb_state
*in_bb_p
= (enum bb_state
*)
1427 xcalloc (max_uid
, sizeof (enum bb_state
));
1429 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1431 basic_block bb
= BASIC_BLOCK (i
);
1434 start
[INSN_UID (bb
->head
)] = bb
;
1435 end
[INSN_UID (bb
->end
)] = bb
;
1436 for (x
= bb
->head
; x
!= NULL_RTX
; x
= NEXT_INSN (x
))
1438 enum bb_state state
= IN_MULTIPLE_BB
;
1439 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
1441 in_bb_p
[INSN_UID (x
)] = state
;
1448 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
1453 if ((bb
= start
[INSN_UID (tmp_rtx
)]) != NULL
)
1455 fprintf (outf
, ";; Start of basic block %d, registers live:",
1457 dump_regset (bb
->global_live_at_start
, outf
);
1461 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
1462 && GET_CODE (tmp_rtx
) != NOTE
1463 && GET_CODE (tmp_rtx
) != BARRIER
)
1464 fprintf (outf
, ";; Insn is not within a basic block\n");
1465 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
1466 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
1468 did_output
= print_rtl_single (outf
, tmp_rtx
);
1470 if ((bb
= end
[INSN_UID (tmp_rtx
)]) != NULL
)
1472 fprintf (outf
, ";; End of basic block %d, registers live:\n",
1474 dump_regset (bb
->global_live_at_end
, outf
);
1487 if (current_function_epilogue_delay_list
!= 0)
1489 fprintf (outf
, "\n;; Insns in epilogue delay list:\n\n");
1490 for (tmp_rtx
= current_function_epilogue_delay_list
; tmp_rtx
!= 0;
1491 tmp_rtx
= XEXP (tmp_rtx
, 1))
1492 print_rtl_single (outf
, XEXP (tmp_rtx
, 0));
1496 /* Verify the CFG consistency. This function check some CFG invariants and
1497 aborts when something is wrong. Hope that this function will help to
1498 convert many optimization passes to preserve CFG consistent.
1500 Currently it does following checks:
1502 - test head/end pointers
1503 - overlapping of basic blocks
1504 - edge list correctness
1505 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1506 - tails of basic blocks (ensure that boundary is necesary)
1507 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1508 and NOTE_INSN_BASIC_BLOCK
1509 - check that all insns are in the basic blocks
1510 (except the switch handling code, barriers and notes)
1511 - check that all returns are followed by barriers
1513 In future it can be extended check a lot of other stuff as well
1514 (reachability of basic blocks, life information, etc. etc.). */
1519 const int max_uid
= get_max_uid ();
1520 const rtx rtx_first
= get_insns ();
1521 rtx last_head
= get_last_insn ();
1522 basic_block
*bb_info
, *last_visited
;
1523 size_t *edge_checksum
;
1525 int i
, last_bb_num_seen
, num_bb_notes
, err
= 0;
1527 bb_info
= (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1528 last_visited
= (basic_block
*) xcalloc (n_basic_blocks
+ 2,
1529 sizeof (basic_block
));
1530 edge_checksum
= (size_t *) xcalloc (n_basic_blocks
+ 2, sizeof (size_t));
1532 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1534 basic_block bb
= BASIC_BLOCK (i
);
1535 rtx head
= bb
->head
;
1538 /* Verify the end of the basic block is in the INSN chain. */
1539 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1544 error ("End insn %d for block %d not found in the insn stream.",
1545 INSN_UID (end
), bb
->index
);
1549 /* Work backwards from the end to the head of the basic block
1550 to verify the head is in the RTL chain. */
1551 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1553 /* While walking over the insn chain, verify insns appear
1554 in only one basic block and initialize the BB_INFO array
1555 used by other passes. */
1556 if (bb_info
[INSN_UID (x
)] != NULL
)
1558 error ("Insn %d is in multiple basic blocks (%d and %d)",
1559 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
1562 bb_info
[INSN_UID (x
)] = bb
;
1569 error ("Head insn %d for block %d not found in the insn stream.",
1570 INSN_UID (head
), bb
->index
);
1577 /* Now check the basic blocks (boundaries etc.) */
1578 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1580 basic_block bb
= BASIC_BLOCK (i
);
1581 int has_fallthru
= 0;
1587 if (last_visited
[e
->dest
->index
+ 2] == bb
)
1589 error ("verify_flow_info: Duplicate edge %i->%i",
1590 e
->src
->index
, e
->dest
->index
);
1593 last_visited
[e
->dest
->index
+ 2] = bb
;
1595 if (e
->flags
& EDGE_FALLTHRU
)
1598 if ((e
->flags
& EDGE_FALLTHRU
)
1599 && e
->src
!= ENTRY_BLOCK_PTR
1600 && e
->dest
!= EXIT_BLOCK_PTR
)
1603 if (e
->src
->index
+ 1 != e
->dest
->index
)
1605 error ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
1606 e
->src
->index
, e
->dest
->index
);
1610 for (insn
= NEXT_INSN (e
->src
->end
); insn
!= e
->dest
->head
;
1611 insn
= NEXT_INSN (insn
))
1612 if (GET_CODE (insn
) == BARRIER
|| INSN_P (insn
))
1614 error ("verify_flow_info: Incorrect fallthru %i->%i",
1615 e
->src
->index
, e
->dest
->index
);
1616 fatal_insn ("Wrong insn in the fallthru edge", insn
);
1622 error ("verify_flow_info: Basic block %d succ edge is corrupted",
1624 fprintf (stderr
, "Predecessor: ");
1625 dump_edge_info (stderr
, e
, 0);
1626 fprintf (stderr
, "\nSuccessor: ");
1627 dump_edge_info (stderr
, e
, 1);
1628 fprintf (stderr
, "\n");
1631 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
1638 /* Ensure existence of barrier in BB with no fallthru edges. */
1639 for (insn
= bb
->end
; GET_CODE (insn
) != BARRIER
;
1640 insn
= NEXT_INSN (insn
))
1642 || (GET_CODE (insn
) == NOTE
1643 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BASIC_BLOCK
))
1645 error ("Missing barrier after block %i", bb
->index
);
1655 error ("Basic block %d pred edge is corrupted", bb
->index
);
1656 fputs ("Predecessor: ", stderr
);
1657 dump_edge_info (stderr
, e
, 0);
1658 fputs ("\nSuccessor: ", stderr
);
1659 dump_edge_info (stderr
, e
, 1);
1660 fputc ('\n', stderr
);
1663 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
1666 for (x
= bb
->head
; x
!= NEXT_INSN (bb
->end
); x
= NEXT_INSN (x
))
1667 if (basic_block_for_insn
&& BLOCK_FOR_INSN (x
) != bb
)
1670 if (! BLOCK_FOR_INSN (x
))
1671 error ("Insn %d is inside basic block %d but block_for_insn is NULL",
1672 INSN_UID (x
), bb
->index
);
1674 error ("Insn %d is inside basic block %d but block_for_insn is %i",
1675 INSN_UID (x
), bb
->index
, BLOCK_FOR_INSN (x
)->index
);
1679 /* OK pointers are correct. Now check the header of basic
1680 block. It ought to contain optional CODE_LABEL followed
1681 by NOTE_BASIC_BLOCK. */
1683 if (GET_CODE (x
) == CODE_LABEL
)
1687 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1693 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
1695 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1702 /* Do checks for empty blocks here */
1709 if (NOTE_INSN_BASIC_BLOCK_P (x
))
1711 error ("NOTE_INSN_BASIC_BLOCK %d in the middle of basic block %d",
1712 INSN_UID (x
), bb
->index
);
1719 if (GET_CODE (x
) == JUMP_INSN
1720 || GET_CODE (x
) == CODE_LABEL
1721 || GET_CODE (x
) == BARRIER
)
1723 error ("In basic block %d:", bb
->index
);
1724 fatal_insn ("Flow control insn inside a basic block", x
);
1732 /* Complete edge checksumming for ENTRY and EXIT. */
1735 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
1736 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
1737 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
1738 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
1741 for (i
= -2; i
< n_basic_blocks
; ++i
)
1742 if (edge_checksum
[i
+ 2])
1744 error ("Basic block %i edge lists are corrupted", i
);
1748 last_bb_num_seen
= -1;
1753 if (NOTE_INSN_BASIC_BLOCK_P (x
))
1755 basic_block bb
= NOTE_BASIC_BLOCK (x
);
1757 if (bb
->index
!= last_bb_num_seen
+ 1)
1758 internal_error ("Basic blocks not numbered consecutively.");
1760 last_bb_num_seen
= bb
->index
;
1763 if (!bb_info
[INSN_UID (x
)])
1765 switch (GET_CODE (x
))
1772 /* An addr_vec is placed outside any block block. */
1774 && GET_CODE (NEXT_INSN (x
)) == JUMP_INSN
1775 && (GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_DIFF_VEC
1776 || GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_VEC
))
1781 /* But in any case, non-deletable labels can appear anywhere. */
1785 fatal_insn ("Insn outside basic block", x
);
1790 && GET_CODE (x
) == JUMP_INSN
1791 && returnjump_p (x
) && ! condjump_p (x
)
1792 && ! (NEXT_INSN (x
) && GET_CODE (NEXT_INSN (x
)) == BARRIER
))
1793 fatal_insn ("Return not followed by barrier", x
);
1798 if (num_bb_notes
!= n_basic_blocks
)
1800 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
1801 num_bb_notes
, n_basic_blocks
);
1804 internal_error ("verify_flow_info failed.");
1808 free (last_visited
);
1809 free (edge_checksum
);
1812 /* Assume that the preceeding pass has possibly eliminated jump instructions
1813 or converted the unconditional jumps. Eliminate the edges from CFG.
1814 Return true if any edges are eliminated. */
1817 purge_dead_edges (bb
)
1822 bool purged
= false;
1824 if (GET_CODE (insn
) == JUMP_INSN
&& !simplejump_p (insn
))
1826 if (GET_CODE (insn
) == JUMP_INSN
)
1830 /* We do care only about conditional jumps and simplejumps. */
1831 if (!any_condjump_p (insn
)
1832 && !returnjump_p (insn
)
1833 && !simplejump_p (insn
))
1835 for (e
= bb
->succ
; e
; e
= next
)
1837 next
= e
->succ_next
;
1839 /* Check purposes we can have edge. */
1840 if ((e
->flags
& EDGE_FALLTHRU
)
1841 && any_condjump_p (insn
))
1843 if (e
->dest
!= EXIT_BLOCK_PTR
1844 && e
->dest
->head
== JUMP_LABEL (insn
))
1846 if (e
->dest
== EXIT_BLOCK_PTR
1847 && returnjump_p (insn
))
1852 if (!bb
->succ
|| !purged
)
1855 fprintf (rtl_dump_file
, "Purged edges from bb %i\n", bb
->index
);
1859 /* Redistribute probabilities. */
1860 if (!bb
->succ
->succ_next
)
1862 bb
->succ
->probability
= REG_BR_PROB_BASE
;
1863 bb
->succ
->count
= bb
->count
;
1867 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
1870 b
= BRANCH_EDGE (bb
);
1871 f
= FALLTHRU_EDGE (bb
);
1872 b
->probability
= INTVAL (XEXP (note
, 0));
1873 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
1874 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
1875 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
1880 /* Cleanup abnormal edges caused by throwing insns that have been
1882 if (! can_throw_internal (bb
->end
))
1883 for (e
= bb
->succ
; e
; e
= next
)
1885 next
= e
->succ_next
;
1886 if (e
->flags
& EDGE_EH
)
1893 /* If we don't see a jump insn, we don't know exactly why the block would
1894 have been broken at this point. Look for a simple, non-fallthru edge,
1895 as these are only created by conditional branches. If we find such an
1896 edge we know that there used to be a jump here and can then safely
1897 remove all non-fallthru edges. */
1898 for (e
= bb
->succ
; e
&& (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
));
1902 for (e
= bb
->succ
; e
; e
= next
)
1904 next
= e
->succ_next
;
1905 if (!(e
->flags
& EDGE_FALLTHRU
))
1906 remove_edge (e
), purged
= true;
1908 if (!bb
->succ
|| bb
->succ
->succ_next
)
1910 bb
->succ
->probability
= REG_BR_PROB_BASE
;
1911 bb
->succ
->count
= bb
->count
;
1914 fprintf (rtl_dump_file
, "Purged non-fallthru edges from bb %i\n",
1919 /* Search all basic blocks for potentionally dead edges and purge them.
1921 Return true ifif some edge has been elliminated.
1925 purge_all_dead_edges ()
1927 int i
, purged
= false;
1928 for (i
= 0; i
< n_basic_blocks
; i
++)
1929 purged
|= purge_dead_edges (BASIC_BLOCK (i
));