1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 /* This file contains low level functions to manipulate the CFG and analyze it
23 that are aware of the RTL intermediate language.
25 Available functionality:
26 - CFG-aware instruction chain manipulation
27 delete_insn, delete_insn_chain
28 - Basic block manipulation
29 create_basic_block, flow_delete_block, split_block,
31 - Infrastructure to determine quickly basic block for insn
32 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
33 - Edge redirection with updating and optimizing of insn chain
34 block_label, redirect_edge_and_branch,
35 redirect_edge_and_branch_force, tidy_fallthru_edge, force_nonfallthru
36 - Edge splitting and commiting to edges
37 split_edge, insert_insn_on_edge, commit_edge_insertions
38 - Dumping and debugging
39 print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
40 - Consistency checking
42 - CFG updating after constant propagation
43 purge_dead_edges, purge_all_dead_edges */
49 #include "hard-reg-set.h"
50 #include "basic-block.h"
60 /* Stubs in case we don't have a return insn. */
63 #define gen_return() NULL_RTX
66 /* The basic block structure for every insn, indexed by uid. */
67 varray_type basic_block_for_insn
;
69 /* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */
70 /* ??? Should probably be using LABEL_NUSES instead. It would take a
71 bit of surgery to be able to use or co-opt the routines in jump. */
73 rtx tail_recursion_label_list
;
75 static int can_delete_note_p
PARAMS ((rtx
));
76 static int can_delete_label_p
PARAMS ((rtx
));
77 static void commit_one_edge_insertion
PARAMS ((edge
));
78 static bool try_redirect_by_replacing_jump
PARAMS ((edge
, basic_block
));
79 static rtx last_loop_beg_note
PARAMS ((rtx
));
80 static bool back_edge_of_syntactic_loop_p
PARAMS ((basic_block
, basic_block
));
81 static basic_block force_nonfallthru_and_redirect
PARAMS ((edge
, basic_block
));
83 /* Return true if NOTE is not one of the ones that must be kept paired,
84 so that we may simply delete it. */
87 can_delete_note_p (note
)
90 return (NOTE_LINE_NUMBER (note
) == NOTE_INSN_DELETED
91 || NOTE_LINE_NUMBER (note
) == NOTE_INSN_BASIC_BLOCK
);
94 /* True if a given label can be deleted. */
97 can_delete_label_p (label
)
100 return (!LABEL_PRESERVE_P (label
)
101 /* User declared labels must be preserved. */
102 && LABEL_NAME (label
) == 0
103 && !in_expr_list_p (forced_labels
, label
)
104 && !in_expr_list_p (label_value_list
, label
));
107 /* Delete INSN by patching it out. Return the next insn. */
113 rtx next
= NEXT_INSN (insn
);
115 bool really_delete
= true;
117 if (GET_CODE (insn
) == CODE_LABEL
)
119 /* Some labels can't be directly removed from the INSN chain, as they
120 might be references via variables, constant pool etc.
121 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
122 if (! can_delete_label_p (insn
))
124 const char *name
= LABEL_NAME (insn
);
126 really_delete
= false;
127 PUT_CODE (insn
, NOTE
);
128 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED_LABEL
;
129 NOTE_SOURCE_FILE (insn
) = name
;
132 remove_node_from_expr_list (insn
, &nonlocal_goto_handler_labels
);
137 /* If this insn has already been deleted, something is very wrong. */
138 if (INSN_DELETED_P (insn
))
141 INSN_DELETED_P (insn
) = 1;
144 /* If deleting a jump, decrement the use count of the label. Deleting
145 the label itself should happen in the normal course of block merging. */
146 if (GET_CODE (insn
) == JUMP_INSN
148 && GET_CODE (JUMP_LABEL (insn
)) == CODE_LABEL
)
149 LABEL_NUSES (JUMP_LABEL (insn
))--;
151 /* Also if deleting an insn that references a label. */
152 else if ((note
= find_reg_note (insn
, REG_LABEL
, NULL_RTX
)) != NULL_RTX
153 && GET_CODE (XEXP (note
, 0)) == CODE_LABEL
)
154 LABEL_NUSES (XEXP (note
, 0))--;
156 if (GET_CODE (insn
) == JUMP_INSN
157 && (GET_CODE (PATTERN (insn
)) == ADDR_VEC
158 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
))
160 rtx pat
= PATTERN (insn
);
161 int diff_vec_p
= GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
;
162 int len
= XVECLEN (pat
, diff_vec_p
);
165 for (i
= 0; i
< len
; i
++)
167 rtx label
= XEXP (XVECEXP (pat
, diff_vec_p
, i
), 0);
169 /* When deleting code in bulk (e.g. removing many unreachable
170 blocks) we can delete a label that's a target of the vector
171 before deleting the vector itself. */
172 if (GET_CODE (label
) != NOTE
)
173 LABEL_NUSES (label
)--;
180 /* Unlink a chain of insns between START and FINISH, leaving notes
181 that must be paired. */
184 delete_insn_chain (start
, finish
)
189 /* Unchain the insns one by one. It would be quicker to delete all of these
190 with a single unchaining, rather than one at a time, but we need to keep
194 next
= NEXT_INSN (start
);
195 if (GET_CODE (start
) == NOTE
&& !can_delete_note_p (start
))
198 next
= delete_insn (start
);
206 /* Create a new basic block consisting of the instructions between HEAD and END
207 inclusive. This function is designed to allow fast BB construction - reuses
208 the note and basic block struct in BB_NOTE, if any and do not grow
209 BASIC_BLOCK chain and should be used directly only by CFG construction code.
210 END can be NULL in to create new empty basic block before HEAD. Both END
211 and HEAD can be NULL to create basic block at the end of INSN chain. */
214 create_basic_block_structure (index
, head
, end
, bb_note
)
216 rtx head
, end
, bb_note
;
221 && ! RTX_INTEGRATED_P (bb_note
)
222 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
225 /* If we found an existing note, thread it back onto the chain. */
229 if (GET_CODE (head
) == CODE_LABEL
)
233 after
= PREV_INSN (head
);
237 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
238 reorder_insns (bb_note
, bb_note
, after
);
242 /* Otherwise we must create a note and a basic block structure. */
248 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
249 else if (GET_CODE (head
) == CODE_LABEL
&& end
)
251 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
257 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
263 NOTE_BASIC_BLOCK (bb_note
) = bb
;
266 /* Always include the bb note in the block. */
267 if (NEXT_INSN (end
) == bb_note
)
273 BASIC_BLOCK (index
) = bb
;
274 if (basic_block_for_insn
)
275 update_bb_for_insn (bb
);
277 /* Tag the block so that we know it has been used when considering
278 other basic block notes. */
284 /* Create new basic block consisting of instructions in between HEAD and END
285 and place it to the BB chain at position INDEX. END can be NULL in to
286 create new empty basic block before HEAD. Both END and HEAD can be NULL to
287 create basic block at the end of INSN chain. */
290 create_basic_block (index
, head
, end
)
297 /* Place the new block just after the block being split. */
298 VARRAY_GROW (basic_block_info
, ++n_basic_blocks
);
300 /* Some parts of the compiler expect blocks to be number in
301 sequential order so insert the new block immediately after the
302 block being split.. */
303 for (i
= n_basic_blocks
- 1; i
> index
; --i
)
305 basic_block tmp
= BASIC_BLOCK (i
- 1);
307 BASIC_BLOCK (i
) = tmp
;
311 bb
= create_basic_block_structure (index
, head
, end
, NULL
);
316 /* Delete the insns in a (non-live) block. We physically delete every
317 non-deleted-note insn, and update the flow graph appropriately.
319 Return nonzero if we deleted an exception handler. */
321 /* ??? Preserving all such notes strikes me as wrong. It would be nice
322 to post-process the stream to remove empty blocks, loops, ranges, etc. */
325 flow_delete_block_noexpunge (b
)
328 int deleted_handler
= 0;
331 /* If the head of this block is a CODE_LABEL, then it might be the
332 label for an exception handler which can't be reached.
334 We need to remove the label from the exception_handler_label list
335 and remove the associated NOTE_INSN_EH_REGION_BEG and
336 NOTE_INSN_EH_REGION_END notes. */
340 never_reached_warning (insn
, b
->end
);
342 if (GET_CODE (insn
) == CODE_LABEL
)
343 maybe_remove_eh_handler (insn
);
345 /* Include any jump table following the basic block. */
347 if (GET_CODE (end
) == JUMP_INSN
348 && (tmp
= JUMP_LABEL (end
)) != NULL_RTX
349 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
350 && GET_CODE (tmp
) == JUMP_INSN
351 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
352 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
355 /* Include any barrier that may follow the basic block. */
356 tmp
= next_nonnote_insn (end
);
357 if (tmp
&& GET_CODE (tmp
) == BARRIER
)
360 /* Selectively delete the entire chain. */
362 delete_insn_chain (insn
, end
);
364 /* Remove the edges into and out of this block. Note that there may
365 indeed be edges in, if we are removing an unreachable loop. */
366 while (b
->pred
!= NULL
)
367 remove_edge (b
->pred
);
368 while (b
->succ
!= NULL
)
369 remove_edge (b
->succ
);
374 return deleted_handler
;
378 flow_delete_block (b
)
381 int deleted_handler
= flow_delete_block_noexpunge (b
);
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
);
401 VARRAY_BB_INIT (basic_block_for_insn
, max
, "basic_block_for_insn");
403 for (i
= 0; i
< n_basic_blocks
; ++i
)
405 basic_block bb
= BASIC_BLOCK (i
);
409 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
411 if (INSN_UID (insn
) < max
)
412 VARRAY_BB (basic_block_for_insn
, INSN_UID (insn
)) = bb
;
420 /* Release the basic_block_for_insn array. */
425 if (basic_block_for_insn
)
426 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
);
450 /* Record INSN's block as BB. */
453 set_block_for_insn (insn
, bb
)
457 size_t uid
= INSN_UID (insn
);
459 if (uid
>= basic_block_for_insn
->num_elements
)
461 /* Add one-eighth the size so we don't keep calling xrealloc. */
462 size_t new_size
= uid
+ (uid
+ 7) / 8;
464 VARRAY_GROW (basic_block_for_insn
, new_size
);
467 VARRAY_BB (basic_block_for_insn
, uid
) = bb
;
470 /* Split a block BB after insn INSN creating a new fallthru edge.
471 Return the new edge. Note that to keep other parts of the compiler happy,
472 this function renumbers all the basic blocks so that the new
473 one has a number one greater than the block split. */
476 split_block (bb
, insn
)
484 /* There is no point splitting the block after its end. */
488 /* Create the new basic block. */
489 new_bb
= create_basic_block (bb
->index
+ 1, NEXT_INSN (insn
), bb
->end
);
490 new_bb
->count
= bb
->count
;
491 new_bb
->frequency
= bb
->frequency
;
492 new_bb
->loop_depth
= bb
->loop_depth
;
495 /* Redirect the outgoing edges. */
496 new_bb
->succ
= bb
->succ
;
498 for (e
= new_bb
->succ
; e
; e
= e
->succ_next
)
501 new_edge
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
503 if (bb
->global_live_at_start
)
505 new_bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
506 new_bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
507 COPY_REG_SET (new_bb
->global_live_at_end
, bb
->global_live_at_end
);
509 /* We now have to calculate which registers are live at the end
510 of the split basic block and at the start of the new basic
511 block. Start with those registers that are known to be live
512 at the end of the original basic block and get
513 propagate_block to determine which registers are live. */
514 COPY_REG_SET (new_bb
->global_live_at_start
, bb
->global_live_at_end
);
515 propagate_block (new_bb
, new_bb
->global_live_at_start
, NULL
, NULL
, 0);
516 COPY_REG_SET (bb
->global_live_at_end
,
517 new_bb
->global_live_at_start
);
523 /* Blocks A and B are to be merged into a single block A. The insns
524 are already contiguous, hence `nomove'. */
527 merge_blocks_nomove (a
, b
)
530 rtx b_head
= b
->head
, b_end
= b
->end
, a_end
= a
->end
;
531 rtx del_first
= NULL_RTX
, del_last
= NULL_RTX
;
535 /* If there was a CODE_LABEL beginning B, delete it. */
536 if (GET_CODE (b_head
) == CODE_LABEL
)
538 /* Detect basic blocks with nothing but a label. This can happen
539 in particular at the end of a function. */
543 del_first
= del_last
= b_head
;
544 b_head
= NEXT_INSN (b_head
);
547 /* Delete the basic block note and handle blocks containing just that
549 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. */
561 if (GET_CODE (a_end
) == JUMP_INSN
)
565 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
566 if (GET_CODE (prev
) != NOTE
567 || NOTE_LINE_NUMBER (prev
) == NOTE_INSN_BASIC_BLOCK
574 /* If this was a conditional jump, we need to also delete
575 the insn that set cc0. */
576 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. */
617 if (basic_block_for_insn
)
621 for (x
= a_end
; x
!= b_end
; x
= NEXT_INSN (x
))
622 set_block_for_insn (x
, a
);
624 set_block_for_insn (b_end
, a
);
633 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
640 if (block
== EXIT_BLOCK_PTR
)
643 if (GET_CODE (block
->head
) != CODE_LABEL
)
645 block
->head
= emit_label_before (gen_label_rtx (), block
->head
);
646 if (basic_block_for_insn
)
647 set_block_for_insn (block
->head
, block
);
653 /* Attempt to perform edge redirection by replacing possibly complex jump
654 instruction by unconditional jump or removing jump completely. This can
655 apply only if all edges now point to the same block. The parameters and
656 return values are equivalent to redirect_edge_and_branch. */
659 try_redirect_by_replacing_jump (e
, target
)
663 basic_block src
= e
->src
;
664 rtx insn
= src
->end
, kill_from
;
669 /* Verify that all targets will be TARGET. */
670 for (tmp
= src
->succ
; tmp
; tmp
= tmp
->succ_next
)
671 if (tmp
->dest
!= target
&& tmp
!= e
)
674 if (tmp
|| !onlyjump_p (insn
))
677 /* Avoid removing branch with side effects. */
678 set
= single_set (insn
);
679 if (!set
|| side_effects_p (set
))
682 /* In case we zap a conditional jump, we'll need to kill
683 the cc0 setter too. */
686 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
)))
687 kill_from
= PREV_INSN (insn
);
690 /* See if we can create the fallthru edge. */
691 if (can_fallthru (src
, target
))
694 fprintf (rtl_dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
697 /* Selectively unlink whole insn chain. */
698 delete_insn_chain (kill_from
, PREV_INSN (target
->head
));
701 /* If this already is simplejump, redirect it. */
702 else if (simplejump_p (insn
))
704 if (e
->dest
== target
)
707 fprintf (rtl_dump_file
, "Redirecting jump %i from %i to %i.\n",
708 INSN_UID (insn
), e
->dest
->index
, target
->index
);
709 if (!redirect_jump (insn
, block_label (target
), 0))
711 if (target
== EXIT_BLOCK_PTR
)
717 /* Cannot do anything for target exit block. */
718 else if (target
== EXIT_BLOCK_PTR
)
721 /* Or replace possibly complicated jump insn by simple jump insn. */
724 rtx target_label
= block_label (target
);
727 emit_jump_insn_after (gen_jump (target_label
), insn
);
728 JUMP_LABEL (src
->end
) = target_label
;
729 LABEL_NUSES (target_label
)++;
731 fprintf (rtl_dump_file
, "Replacing insn %i by jump %i\n",
732 INSN_UID (insn
), INSN_UID (src
->end
));
735 delete_insn_chain (kill_from
, insn
);
737 /* Recognize a tablejump that we are converting to a
738 simple jump and remove its associated CODE_LABEL
739 and ADDR_VEC or ADDR_DIFF_VEC. */
740 if ((tmp
= JUMP_LABEL (insn
)) != NULL_RTX
741 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
742 && GET_CODE (tmp
) == JUMP_INSN
743 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
744 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
746 delete_insn_chain (JUMP_LABEL (insn
), tmp
);
749 barrier
= next_nonnote_insn (src
->end
);
750 if (!barrier
|| GET_CODE (barrier
) != BARRIER
)
751 emit_barrier_after (src
->end
);
754 /* Keep only one edge out and set proper flags. */
755 while (src
->succ
->succ_next
)
756 remove_edge (src
->succ
);
759 e
->flags
= EDGE_FALLTHRU
;
763 e
->probability
= REG_BR_PROB_BASE
;
764 e
->count
= src
->count
;
766 /* We don't want a block to end on a line-number note since that has
767 the potential of changing the code between -g and not -g. */
768 while (GET_CODE (e
->src
->end
) == NOTE
769 && NOTE_LINE_NUMBER (e
->src
->end
) >= 0)
770 delete_insn (e
->src
->end
);
772 if (e
->dest
!= target
)
773 redirect_edge_succ (e
, target
);
778 /* Return last loop_beg note appearing after INSN, before start of next
779 basic block. Return INSN if there are no such notes.
781 When emitting jump to redirect an fallthru edge, it should always appear
782 after the LOOP_BEG notes, as loop optimizer expect loop to either start by
783 fallthru edge or jump following the LOOP_BEG note jumping to the loop exit
787 last_loop_beg_note (insn
)
792 for (insn
= NEXT_INSN (insn
); insn
&& GET_CODE (insn
) == NOTE
793 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
;
794 insn
= NEXT_INSN (insn
))
795 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
801 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
802 expense of adding new instructions or reordering basic blocks.
804 Function can be also called with edge destination equivalent to the TARGET.
805 Then it should try the simplifications and do nothing if none is possible.
807 Return true if transformation succeeded. We still return false in case E
808 already destinated TARGET and we didn't managed to simplify instruction
812 redirect_edge_and_branch (e
, target
)
817 rtx old_label
= e
->dest
->head
;
818 basic_block src
= e
->src
;
821 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
824 if (try_redirect_by_replacing_jump (e
, target
))
827 /* Do this fast path late, as we want above code to simplify for cases
828 where called on single edge leaving basic block containing nontrivial
830 else if (e
->dest
== target
)
833 /* We can only redirect non-fallthru edges of jump insn. */
834 if (e
->flags
& EDGE_FALLTHRU
)
836 else if (GET_CODE (insn
) != JUMP_INSN
)
839 /* Recognize a tablejump and adjust all matching cases. */
840 if ((tmp
= JUMP_LABEL (insn
)) != NULL_RTX
841 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
842 && GET_CODE (tmp
) == JUMP_INSN
843 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
844 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
848 rtx new_label
= block_label (target
);
850 if (target
== EXIT_BLOCK_PTR
)
852 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
853 vec
= XVEC (PATTERN (tmp
), 0);
855 vec
= XVEC (PATTERN (tmp
), 1);
857 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
858 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
860 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
861 --LABEL_NUSES (old_label
);
862 ++LABEL_NUSES (new_label
);
865 /* Handle casesi dispatch insns */
866 if ((tmp
= single_set (insn
)) != NULL
867 && SET_DEST (tmp
) == pc_rtx
868 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
869 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
870 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
872 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (VOIDmode
,
874 --LABEL_NUSES (old_label
);
875 ++LABEL_NUSES (new_label
);
880 /* ?? We may play the games with moving the named labels from
881 one basic block to the other in case only one computed_jump is
883 if (computed_jump_p (insn
)
884 /* A return instruction can't be redirected. */
885 || returnjump_p (insn
))
888 /* If the insn doesn't go where we think, we're confused. */
889 if (JUMP_LABEL (insn
) != old_label
)
892 /* If the substitution doesn't succeed, die. This can happen
893 if the back end emitted unrecognizable instructions or if
894 target is exit block on some arches. */
895 if (!redirect_jump (insn
, block_label (target
), 0))
897 if (target
== EXIT_BLOCK_PTR
)
904 fprintf (rtl_dump_file
, "Edge %i->%i redirected to %i\n",
905 e
->src
->index
, e
->dest
->index
, target
->index
);
907 if (e
->dest
!= target
)
908 redirect_edge_succ_nodup (e
, target
);
913 /* Like force_nonfallthru below, but additionally performs redirection
914 Used by redirect_edge_and_branch_force. */
917 force_nonfallthru_and_redirect (e
, target
)
921 basic_block jump_block
, new_bb
= NULL
;
925 if (e
->flags
& EDGE_ABNORMAL
)
927 else if (!(e
->flags
& EDGE_FALLTHRU
))
929 else if (e
->src
== ENTRY_BLOCK_PTR
)
931 /* We can't redirect the entry block. Create an empty block at the
932 start of the function which we use to add the new jump. */
934 basic_block bb
= create_basic_block (0, e
->dest
->head
, NULL
);
936 /* Change the existing edge's source to be the new block, and add
937 a new edge from the entry block to the new block. */
939 bb
->count
= e
->count
;
940 bb
->frequency
= EDGE_FREQUENCY (e
);
942 for (pe1
= &ENTRY_BLOCK_PTR
->succ
; *pe1
; pe1
= &(*pe1
)->succ_next
)
950 make_single_succ_edge (ENTRY_BLOCK_PTR
, bb
, EDGE_FALLTHRU
);
953 if (e
->src
->succ
->succ_next
)
955 /* Create the new structures. */
957 /* Position the new block correctly relative to loop notes. */
958 note
= last_loop_beg_note (e
->src
->end
);
959 note
= NEXT_INSN (note
);
961 /* ... and ADDR_VECs. */
963 && GET_CODE (note
) == CODE_LABEL
965 && GET_CODE (NEXT_INSN (note
)) == JUMP_INSN
966 && (GET_CODE (PATTERN (NEXT_INSN (note
))) == ADDR_DIFF_VEC
967 || GET_CODE (PATTERN (NEXT_INSN (note
))) == ADDR_VEC
))
968 note
= NEXT_INSN (NEXT_INSN (note
));
970 jump_block
= create_basic_block (e
->src
->index
+ 1, note
, NULL
);
971 jump_block
->count
= e
->count
;
972 jump_block
->frequency
= EDGE_FREQUENCY (e
);
973 jump_block
->loop_depth
= target
->loop_depth
;
975 if (target
->global_live_at_start
)
977 jump_block
->global_live_at_start
978 = OBSTACK_ALLOC_REG_SET (&flow_obstack
);
979 jump_block
->global_live_at_end
980 = OBSTACK_ALLOC_REG_SET (&flow_obstack
);
981 COPY_REG_SET (jump_block
->global_live_at_start
,
982 target
->global_live_at_start
);
983 COPY_REG_SET (jump_block
->global_live_at_end
,
984 target
->global_live_at_start
);
988 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
989 new_edge
->probability
= e
->probability
;
990 new_edge
->count
= e
->count
;
992 /* Redirect old edge. */
993 redirect_edge_pred (e
, jump_block
);
994 e
->probability
= REG_BR_PROB_BASE
;
1001 e
->flags
&= ~EDGE_FALLTHRU
;
1002 if (target
== EXIT_BLOCK_PTR
)
1005 emit_jump_insn_after (gen_return (), jump_block
->end
);
1011 rtx label
= block_label (target
);
1012 emit_jump_insn_after (gen_jump (label
), jump_block
->end
);
1013 JUMP_LABEL (jump_block
->end
) = label
;
1014 LABEL_NUSES (label
)++;
1017 emit_barrier_after (jump_block
->end
);
1018 redirect_edge_succ_nodup (e
, target
);
1023 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1024 (and possibly create new basic block) to make edge non-fallthru.
1025 Return newly created BB or NULL if none. */
1028 force_nonfallthru (e
)
1031 return force_nonfallthru_and_redirect (e
, e
->dest
);
1034 /* Redirect edge even at the expense of creating new jump insn or
1035 basic block. Return new basic block if created, NULL otherwise.
1036 Abort if conversion is impossible. */
1039 redirect_edge_and_branch_force (e
, target
)
1043 if (redirect_edge_and_branch (e
, target
)
1044 || e
->dest
== target
)
1047 /* In case the edge redirection failed, try to force it to be non-fallthru
1048 and redirect newly created simplejump. */
1049 return force_nonfallthru_and_redirect (e
, target
);
1052 /* The given edge should potentially be a fallthru edge. If that is in
1053 fact true, delete the jump and barriers that are in the way. */
1056 tidy_fallthru_edge (e
, b
, c
)
1062 /* ??? In a late-running flow pass, other folks may have deleted basic
1063 blocks by nopping out blocks, leaving multiple BARRIERs between here
1064 and the target label. They ought to be chastized and fixed.
1066 We can also wind up with a sequence of undeletable labels between
1067 one block and the next.
1069 So search through a sequence of barriers, labels, and notes for
1070 the head of block C and assert that we really do fall through. */
1072 if (next_real_insn (b
->end
) != next_real_insn (PREV_INSN (c
->head
)))
1075 /* Remove what will soon cease being the jump insn from the source block.
1076 If block B consisted only of this single jump, turn it into a deleted
1079 if (GET_CODE (q
) == JUMP_INSN
1081 && (any_uncondjump_p (q
)
1082 || (b
->succ
== e
&& e
->succ_next
== NULL
)))
1085 /* If this was a conditional jump, we need to also delete
1086 the insn that set cc0. */
1087 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1093 /* We don't want a block to end on a line-number note since that has
1094 the potential of changing the code between -g and not -g. */
1095 while (GET_CODE (q
) == NOTE
&& NOTE_LINE_NUMBER (q
) >= 0)
1099 /* Selectively unlink the sequence. */
1100 if (q
!= PREV_INSN (c
->head
))
1101 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (c
->head
));
1103 e
->flags
|= EDGE_FALLTHRU
;
1106 /* Fix up edges that now fall through, or rather should now fall through
1107 but previously required a jump around now deleted blocks. Simplify
1108 the search by only examining blocks numerically adjacent, since this
1109 is how find_basic_blocks created them. */
1112 tidy_fallthru_edges ()
1116 for (i
= 1; i
< n_basic_blocks
; i
++)
1118 basic_block b
= BASIC_BLOCK (i
- 1);
1119 basic_block c
= BASIC_BLOCK (i
);
1122 /* We care about simple conditional or unconditional jumps with
1125 If we had a conditional branch to the next instruction when
1126 find_basic_blocks was called, then there will only be one
1127 out edge for the block which ended with the conditional
1128 branch (since we do not create duplicate edges).
1130 Furthermore, the edge will be marked as a fallthru because we
1131 merge the flags for the duplicate edges. So we do not want to
1132 check that the edge is not a FALLTHRU edge. */
1134 if ((s
= b
->succ
) != NULL
1135 && ! (s
->flags
& EDGE_COMPLEX
)
1136 && s
->succ_next
== NULL
1138 /* If the jump insn has side effects, we can't tidy the edge. */
1139 && (GET_CODE (b
->end
) != JUMP_INSN
1140 || onlyjump_p (b
->end
)))
1141 tidy_fallthru_edge (s
, b
, c
);
1145 /* Helper function for split_edge. Return true in case edge BB2 to BB1
1146 is back edge of syntactic loop. */
1149 back_edge_of_syntactic_loop_p (bb1
, bb2
)
1150 basic_block bb1
, bb2
;
1155 if (bb1
->index
> bb2
->index
)
1157 else if (bb1
->index
== bb2
->index
)
1160 for (insn
= bb1
->end
; insn
!= bb2
->head
&& count
>= 0;
1161 insn
= NEXT_INSN (insn
))
1162 if (GET_CODE (insn
) == NOTE
)
1164 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
1166 else if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
)
1173 /* Split a (typically critical) edge. Return the new block.
1174 Abort on abnormal edges.
1176 ??? The code generally expects to be called on critical edges.
1177 The case of a block ending in an unconditional jump to a
1178 block with multiple predecessors is not handled optimally. */
1181 split_edge (edge_in
)
1188 /* Abnormal edges cannot be split. */
1189 if ((edge_in
->flags
& EDGE_ABNORMAL
) != 0)
1192 /* We are going to place the new block in front of edge destination.
1193 Avoid existence of fallthru predecessors. */
1194 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1198 for (e
= edge_in
->dest
->pred
; e
; e
= e
->pred_next
)
1199 if (e
->flags
& EDGE_FALLTHRU
)
1203 force_nonfallthru (e
);
1206 /* Create the basic block note.
1208 Where we place the note can have a noticeable impact on the generated
1209 code. Consider this cfg:
1219 If we need to insert an insn on the edge from block 0 to block 1,
1220 we want to ensure the instructions we insert are outside of any
1221 loop notes that physically sit between block 0 and block 1. Otherwise
1222 we confuse the loop optimizer into thinking the loop is a phony. */
1224 if (edge_in
->dest
!= EXIT_BLOCK_PTR
1225 && PREV_INSN (edge_in
->dest
->head
)
1226 && GET_CODE (PREV_INSN (edge_in
->dest
->head
)) == NOTE
1227 && (NOTE_LINE_NUMBER (PREV_INSN (edge_in
->dest
->head
))
1228 == NOTE_INSN_LOOP_BEG
)
1229 && !back_edge_of_syntactic_loop_p (edge_in
->dest
, edge_in
->src
))
1230 before
= PREV_INSN (edge_in
->dest
->head
);
1231 else if (edge_in
->dest
!= EXIT_BLOCK_PTR
)
1232 before
= edge_in
->dest
->head
;
1236 bb
= create_basic_block (edge_in
->dest
== EXIT_BLOCK_PTR
? n_basic_blocks
1237 : edge_in
->dest
->index
, before
, NULL
);
1238 bb
->count
= edge_in
->count
;
1239 bb
->frequency
= EDGE_FREQUENCY (edge_in
);
1240 bb
->loop_depth
= edge_in
->dest
->loop_depth
;
1242 /* ??? This info is likely going to be out of date very soon. */
1243 if (edge_in
->dest
->global_live_at_start
)
1245 bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1246 bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1247 COPY_REG_SET (bb
->global_live_at_start
,
1248 edge_in
->dest
->global_live_at_start
);
1249 COPY_REG_SET (bb
->global_live_at_end
,
1250 edge_in
->dest
->global_live_at_start
);
1253 edge_out
= make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1255 /* For non-fallthry edges, we must adjust the predecessor's
1256 jump instruction to target our new block. */
1257 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1259 if (!redirect_edge_and_branch (edge_in
, bb
))
1263 redirect_edge_succ (edge_in
, bb
);
1268 /* Queue instructions for insertion on an edge between two basic blocks.
1269 The new instructions and basic blocks (if any) will not appear in the
1270 CFG until commit_edge_insertions is called. */
1273 insert_insn_on_edge (pattern
, e
)
1277 /* We cannot insert instructions on an abnormal critical edge.
1278 It will be easier to find the culprit if we die now. */
1279 if ((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
1282 if (e
->insns
== NULL_RTX
)
1285 push_to_sequence (e
->insns
);
1287 emit_insn (pattern
);
1289 e
->insns
= get_insns ();
1293 /* Update the CFG for the instructions queued on edge E. */
1296 commit_one_edge_insertion (e
)
1299 rtx before
= NULL_RTX
, after
= NULL_RTX
, insns
, tmp
, last
;
1302 /* Pull the insns off the edge now since the edge might go away. */
1304 e
->insns
= NULL_RTX
;
1306 /* Figure out where to put these things. If the destination has
1307 one predecessor, insert there. Except for the exit block. */
1308 if (e
->dest
->pred
->pred_next
== NULL
1309 && e
->dest
!= EXIT_BLOCK_PTR
)
1313 /* Get the location correct wrt a code label, and "nice" wrt
1314 a basic block note, and before everything else. */
1316 if (GET_CODE (tmp
) == CODE_LABEL
)
1317 tmp
= NEXT_INSN (tmp
);
1318 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1319 tmp
= NEXT_INSN (tmp
);
1320 if (tmp
== bb
->head
)
1323 after
= PREV_INSN (tmp
);
1326 /* If the source has one successor and the edge is not abnormal,
1327 insert there. Except for the entry block. */
1328 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1329 && e
->src
->succ
->succ_next
== NULL
1330 && e
->src
!= ENTRY_BLOCK_PTR
)
1334 /* It is possible to have a non-simple jump here. Consider a target
1335 where some forms of unconditional jumps clobber a register. This
1336 happens on the fr30 for example.
1338 We know this block has a single successor, so we can just emit
1339 the queued insns before the jump. */
1340 if (GET_CODE (bb
->end
) == JUMP_INSN
)
1341 for (before
= bb
->end
;
1342 GET_CODE (PREV_INSN (before
)) == NOTE
1343 && NOTE_LINE_NUMBER (PREV_INSN (before
)) == NOTE_INSN_LOOP_BEG
;
1344 before
= PREV_INSN (before
))
1348 /* We'd better be fallthru, or we've lost track of what's what. */
1349 if ((e
->flags
& EDGE_FALLTHRU
) == 0)
1356 /* Otherwise we must split the edge. */
1359 bb
= split_edge (e
);
1363 /* Now that we've found the spot, do the insertion. */
1367 emit_insns_before (insns
, before
);
1368 last
= prev_nonnote_insn (before
);
1371 last
= emit_insns_after (insns
, after
);
1373 if (returnjump_p (last
))
1375 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1376 This is not currently a problem because this only happens
1377 for the (single) epilogue, which already has a fallthru edge
1381 if (e
->dest
!= EXIT_BLOCK_PTR
1382 || e
->succ_next
!= NULL
1383 || (e
->flags
& EDGE_FALLTHRU
) == 0)
1386 e
->flags
&= ~EDGE_FALLTHRU
;
1387 emit_barrier_after (last
);
1390 delete_insn (before
);
1392 else if (GET_CODE (last
) == JUMP_INSN
)
1395 find_sub_basic_blocks (bb
);
1398 /* Update the CFG for all queued instructions. */
1401 commit_edge_insertions ()
1406 #ifdef ENABLE_CHECKING
1407 verify_flow_info ();
1411 bb
= ENTRY_BLOCK_PTR
;
1416 for (e
= bb
->succ
; e
; e
= next
)
1418 next
= e
->succ_next
;
1420 commit_one_edge_insertion (e
);
1423 if (++i
>= n_basic_blocks
)
1425 bb
= BASIC_BLOCK (i
);
1429 /* Print out one basic block with live information at start and end. */
1440 fprintf (outf
, ";; Basic block %d, loop depth %d, count ",
1441 bb
->index
, bb
->loop_depth
);
1442 fprintf (outf
, HOST_WIDEST_INT_PRINT_DEC
, (HOST_WIDEST_INT
) bb
->count
);
1445 fputs (";; Predecessors: ", outf
);
1446 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1447 dump_edge_info (outf
, e
, 0);
1450 fputs (";; Registers live at start:", outf
);
1451 dump_regset (bb
->global_live_at_start
, outf
);
1454 for (insn
= bb
->head
, last
= NEXT_INSN (bb
->end
); insn
!= last
;
1455 insn
= NEXT_INSN (insn
))
1456 print_rtl_single (outf
, insn
);
1458 fputs (";; Registers live at end:", outf
);
1459 dump_regset (bb
->global_live_at_end
, outf
);
1462 fputs (";; Successors: ", outf
);
1463 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1464 dump_edge_info (outf
, e
, 1);
1472 dump_bb (bb
, stderr
);
1479 dump_bb (BASIC_BLOCK (n
), stderr
);
1482 /* Like print_rtl, but also print out live information for the start of each
1486 print_rtl_with_bb (outf
, rtx_first
)
1493 fprintf (outf
, "(nil)\n");
1497 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
1498 int max_uid
= get_max_uid ();
1500 = (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1502 = (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1503 enum bb_state
*in_bb_p
1504 = (enum bb_state
*) xcalloc (max_uid
, sizeof (enum bb_state
));
1506 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1508 basic_block bb
= BASIC_BLOCK (i
);
1511 start
[INSN_UID (bb
->head
)] = bb
;
1512 end
[INSN_UID (bb
->end
)] = bb
;
1513 for (x
= bb
->head
; x
!= NULL_RTX
; x
= NEXT_INSN (x
))
1515 enum bb_state state
= IN_MULTIPLE_BB
;
1517 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
1519 in_bb_p
[INSN_UID (x
)] = state
;
1526 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
1531 if ((bb
= start
[INSN_UID (tmp_rtx
)]) != NULL
)
1533 fprintf (outf
, ";; Start of basic block %d, registers live:",
1535 dump_regset (bb
->global_live_at_start
, outf
);
1539 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
1540 && GET_CODE (tmp_rtx
) != NOTE
1541 && GET_CODE (tmp_rtx
) != BARRIER
)
1542 fprintf (outf
, ";; Insn is not within a basic block\n");
1543 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
1544 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
1546 did_output
= print_rtl_single (outf
, tmp_rtx
);
1548 if ((bb
= end
[INSN_UID (tmp_rtx
)]) != NULL
)
1550 fprintf (outf
, ";; End of basic block %d, registers live:\n",
1552 dump_regset (bb
->global_live_at_end
, outf
);
1565 if (current_function_epilogue_delay_list
!= 0)
1567 fprintf (outf
, "\n;; Insns in epilogue delay list:\n\n");
1568 for (tmp_rtx
= current_function_epilogue_delay_list
; tmp_rtx
!= 0;
1569 tmp_rtx
= XEXP (tmp_rtx
, 1))
1570 print_rtl_single (outf
, XEXP (tmp_rtx
, 0));
1575 update_br_prob_note (bb
)
1579 if (GET_CODE (bb
->end
) != JUMP_INSN
)
1581 note
= find_reg_note (bb
->end
, REG_BR_PROB
, NULL_RTX
);
1582 if (!note
|| INTVAL (XEXP (note
, 0)) == BRANCH_EDGE (bb
)->probability
)
1584 XEXP (note
, 0) = GEN_INT (BRANCH_EDGE (bb
)->probability
);
1587 /* Verify the CFG consistency. This function check some CFG invariants and
1588 aborts when something is wrong. Hope that this function will help to
1589 convert many optimization passes to preserve CFG consistent.
1591 Currently it does following checks:
1593 - test head/end pointers
1594 - overlapping of basic blocks
1595 - edge list correctness
1596 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1597 - tails of basic blocks (ensure that boundary is necessary)
1598 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1599 and NOTE_INSN_BASIC_BLOCK
1600 - check that all insns are in the basic blocks
1601 (except the switch handling code, barriers and notes)
1602 - check that all returns are followed by barriers
1604 In future it can be extended check a lot of other stuff as well
1605 (reachability of basic blocks, life information, etc. etc.). */
1610 const int max_uid
= get_max_uid ();
1611 const rtx rtx_first
= get_insns ();
1612 rtx last_head
= get_last_insn ();
1613 basic_block
*bb_info
, *last_visited
;
1614 size_t *edge_checksum
;
1616 int i
, last_bb_num_seen
, num_bb_notes
, err
= 0;
1618 bb_info
= (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1619 last_visited
= (basic_block
*) xcalloc (n_basic_blocks
+ 2,
1620 sizeof (basic_block
));
1621 edge_checksum
= (size_t *) xcalloc (n_basic_blocks
+ 2, sizeof (size_t));
1623 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1625 basic_block bb
= BASIC_BLOCK (i
);
1626 rtx head
= bb
->head
;
1629 /* Verify the end of the basic block is in the INSN chain. */
1630 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1636 error ("end insn %d for block %d not found in the insn stream",
1637 INSN_UID (end
), bb
->index
);
1641 /* Work backwards from the end to the head of the basic block
1642 to verify the head is in the RTL chain. */
1643 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1645 /* While walking over the insn chain, verify insns appear
1646 in only one basic block and initialize the BB_INFO array
1647 used by other passes. */
1648 if (bb_info
[INSN_UID (x
)] != NULL
)
1650 error ("insn %d is in multiple basic blocks (%d and %d)",
1651 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
1655 bb_info
[INSN_UID (x
)] = bb
;
1662 error ("head insn %d for block %d not found in the insn stream",
1663 INSN_UID (head
), bb
->index
);
1670 /* Now check the basic blocks (boundaries etc.) */
1671 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1673 basic_block bb
= BASIC_BLOCK (i
);
1674 int has_fallthru
= 0;
1677 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1679 if (last_visited
[e
->dest
->index
+ 2] == bb
)
1681 error ("verify_flow_info: Duplicate edge %i->%i",
1682 e
->src
->index
, e
->dest
->index
);
1686 last_visited
[e
->dest
->index
+ 2] = bb
;
1688 if (e
->flags
& EDGE_FALLTHRU
)
1691 if ((e
->flags
& EDGE_FALLTHRU
)
1692 && e
->src
!= ENTRY_BLOCK_PTR
1693 && e
->dest
!= EXIT_BLOCK_PTR
)
1697 if (e
->src
->index
+ 1 != e
->dest
->index
)
1700 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
1701 e
->src
->index
, e
->dest
->index
);
1705 for (insn
= NEXT_INSN (e
->src
->end
); insn
!= e
->dest
->head
;
1706 insn
= NEXT_INSN (insn
))
1707 if (GET_CODE (insn
) == BARRIER
1708 #ifndef CASE_DROPS_THROUGH
1711 || (INSN_P (insn
) && ! JUMP_TABLE_DATA_P (insn
))
1715 error ("verify_flow_info: Incorrect fallthru %i->%i",
1716 e
->src
->index
, e
->dest
->index
);
1717 fatal_insn ("wrong insn in the fallthru edge", insn
);
1724 error ("verify_flow_info: Basic block %d succ edge is corrupted",
1726 fprintf (stderr
, "Predecessor: ");
1727 dump_edge_info (stderr
, e
, 0);
1728 fprintf (stderr
, "\nSuccessor: ");
1729 dump_edge_info (stderr
, e
, 1);
1730 fprintf (stderr
, "\n");
1734 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
1741 /* Ensure existence of barrier in BB with no fallthru edges. */
1742 for (insn
= bb
->end
; !insn
|| GET_CODE (insn
) != BARRIER
;
1743 insn
= NEXT_INSN (insn
))
1745 || (GET_CODE (insn
) == NOTE
1746 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BASIC_BLOCK
))
1748 error ("missing barrier after block %i", bb
->index
);
1754 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1758 error ("basic block %d pred edge is corrupted", bb
->index
);
1759 fputs ("Predecessor: ", stderr
);
1760 dump_edge_info (stderr
, e
, 0);
1761 fputs ("\nSuccessor: ", stderr
);
1762 dump_edge_info (stderr
, e
, 1);
1763 fputc ('\n', stderr
);
1766 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
1769 for (x
= bb
->head
; x
!= NEXT_INSN (bb
->end
); x
= NEXT_INSN (x
))
1770 if (basic_block_for_insn
&& BLOCK_FOR_INSN (x
) != bb
)
1773 if (! BLOCK_FOR_INSN (x
))
1775 ("insn %d inside basic block %d but block_for_insn is NULL",
1776 INSN_UID (x
), bb
->index
);
1779 ("insn %d inside basic block %d but block_for_insn is %i",
1780 INSN_UID (x
), bb
->index
, BLOCK_FOR_INSN (x
)->index
);
1785 /* OK pointers are correct. Now check the header of basic
1786 block. It ought to contain optional CODE_LABEL followed
1787 by NOTE_BASIC_BLOCK. */
1789 if (GET_CODE (x
) == CODE_LABEL
)
1793 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1801 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
1803 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1809 /* Do checks for empty blocks her. e */
1812 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
1814 if (NOTE_INSN_BASIC_BLOCK_P (x
))
1816 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
1817 INSN_UID (x
), bb
->index
);
1824 if (GET_CODE (x
) == JUMP_INSN
1825 || GET_CODE (x
) == CODE_LABEL
1826 || GET_CODE (x
) == BARRIER
)
1828 error ("in basic block %d:", bb
->index
);
1829 fatal_insn ("flow control insn inside a basic block", x
);
1834 /* Complete edge checksumming for ENTRY and EXIT. */
1838 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
1839 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
1841 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
1842 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
1845 for (i
= -2; i
< n_basic_blocks
; ++i
)
1846 if (edge_checksum
[i
+ 2])
1848 error ("basic block %i edge lists are corrupted", i
);
1852 last_bb_num_seen
= -1;
1854 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
1856 if (NOTE_INSN_BASIC_BLOCK_P (x
))
1858 basic_block bb
= NOTE_BASIC_BLOCK (x
);
1861 if (bb
->index
!= last_bb_num_seen
+ 1)
1862 internal_error ("basic blocks not numbered consecutively");
1864 last_bb_num_seen
= bb
->index
;
1867 if (!bb_info
[INSN_UID (x
)])
1869 switch (GET_CODE (x
))
1876 /* An addr_vec is placed outside any block block. */
1878 && GET_CODE (NEXT_INSN (x
)) == JUMP_INSN
1879 && (GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_DIFF_VEC
1880 || GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_VEC
))
1883 /* But in any case, non-deletable labels can appear anywhere. */
1887 fatal_insn ("insn outside basic block", x
);
1892 && GET_CODE (x
) == JUMP_INSN
1893 && returnjump_p (x
) && ! condjump_p (x
)
1894 && ! (NEXT_INSN (x
) && GET_CODE (NEXT_INSN (x
)) == BARRIER
))
1895 fatal_insn ("return not followed by barrier", x
);
1898 if (num_bb_notes
!= n_basic_blocks
)
1900 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
1901 num_bb_notes
, n_basic_blocks
);
1904 internal_error ("verify_flow_info failed");
1908 free (last_visited
);
1909 free (edge_checksum
);
1912 /* Assume that the preceding pass has possibly eliminated jump instructions
1913 or converted the unconditional jumps. Eliminate the edges from CFG.
1914 Return true if any edges are eliminated. */
1917 purge_dead_edges (bb
)
1921 rtx insn
= bb
->end
, note
;
1922 bool purged
= false;
1924 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
1925 if (GET_CODE (insn
) == INSN
1926 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
1930 if (! may_trap_p (PATTERN (insn
))
1931 || ((eqnote
= find_reg_equal_equiv_note (insn
))
1932 && ! may_trap_p (XEXP (eqnote
, 0))))
1933 remove_note (insn
, note
);
1936 /* Cleanup abnormal edges caused by throwing insns that have been
1938 if (! can_throw_internal (bb
->end
))
1939 for (e
= bb
->succ
; e
; e
= next
)
1941 next
= e
->succ_next
;
1942 if (e
->flags
& EDGE_EH
)
1949 if (GET_CODE (insn
) == JUMP_INSN
)
1954 /* We do care only about conditional jumps and simplejumps. */
1955 if (!any_condjump_p (insn
)
1956 && !returnjump_p (insn
)
1957 && !simplejump_p (insn
))
1960 for (e
= bb
->succ
; e
; e
= next
)
1962 next
= e
->succ_next
;
1964 /* Avoid abnormal flags to leak from computed jumps turned
1965 into simplejumps. */
1967 e
->flags
&= ~EDGE_ABNORMAL
;
1969 /* See if this edge is one we should keep. */
1970 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
1971 /* A conditional jump can fall through into the next
1972 block, so we should keep the edge. */
1974 else if (e
->dest
!= EXIT_BLOCK_PTR
1975 && e
->dest
->head
== JUMP_LABEL (insn
))
1976 /* If the destination block is the target of the jump,
1979 else if (e
->dest
== EXIT_BLOCK_PTR
&& returnjump_p (insn
))
1980 /* If the destination block is the exit block, and this
1981 instruction is a return, then keep the edge. */
1983 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
1984 /* Keep the edges that correspond to exceptions thrown by
1985 this instruction. */
1988 /* We do not need this edge. */
1993 if (!bb
->succ
|| !purged
)
1997 fprintf (rtl_dump_file
, "Purged edges from bb %i\n", bb
->index
);
2002 /* Redistribute probabilities. */
2003 if (!bb
->succ
->succ_next
)
2005 bb
->succ
->probability
= REG_BR_PROB_BASE
;
2006 bb
->succ
->count
= bb
->count
;
2010 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2014 b
= BRANCH_EDGE (bb
);
2015 f
= FALLTHRU_EDGE (bb
);
2016 b
->probability
= INTVAL (XEXP (note
, 0));
2017 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
2018 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
2019 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
2025 /* If we don't see a jump insn, we don't know exactly why the block would
2026 have been broken at this point. Look for a simple, non-fallthru edge,
2027 as these are only created by conditional branches. If we find such an
2028 edge we know that there used to be a jump here and can then safely
2029 remove all non-fallthru edges. */
2030 for (e
= bb
->succ
; e
&& (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
));
2037 for (e
= bb
->succ
; e
; e
= next
)
2039 next
= e
->succ_next
;
2040 if (!(e
->flags
& EDGE_FALLTHRU
))
2041 remove_edge (e
), purged
= true;
2044 if (!bb
->succ
|| bb
->succ
->succ_next
)
2047 bb
->succ
->probability
= REG_BR_PROB_BASE
;
2048 bb
->succ
->count
= bb
->count
;
2051 fprintf (rtl_dump_file
, "Purged non-fallthru edges from bb %i\n",
2056 /* Search all basic blocks for potentially dead edges and purge them. Return
2057 true if some edge has been eliminated. */
2060 purge_all_dead_edges (update_life_p
)
2063 int i
, purged
= false;
2068 blocks
= sbitmap_alloc (n_basic_blocks
);
2069 sbitmap_zero (blocks
);
2072 for (i
= 0; i
< n_basic_blocks
; i
++)
2074 bool purged_here
= purge_dead_edges (BASIC_BLOCK (i
));
2076 purged
|= purged_here
;
2077 if (purged_here
&& update_life_p
)
2078 SET_BIT (blocks
, i
);
2081 if (update_life_p
&& purged
)
2082 update_life_info (blocks
, UPDATE_LIFE_GLOBAL
,
2083 PROP_DEATH_NOTES
| PROP_SCAN_DEAD_CODE
2084 | PROP_KILL_DEAD_CODE
);
2087 sbitmap_free (blocks
);