1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 /* This file contains low level functions to manipulate the CFG and analyze it
23 that are aware of the RTL intermediate language.
25 Available functionality:
26 - CFG-aware instruction chain manipulation
27 delete_insn, delete_insn_chain
28 - Basic block manipulation
29 create_basic_block, flow_delete_block, split_block,
31 - Infrastructure to determine quickly basic block for insn
32 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
33 - Edge redirection with updating and optimizing of insn chain
34 block_label, redirect_edge_and_branch,
35 redirect_edge_and_branch_force, tidy_fallthru_edge, force_nonfallthru
36 - Edge splitting and commiting to edges
37 split_edge, insert_insn_on_edge, commit_edge_insertions
38 - Dumping and debugging
39 print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
40 - Consistency checking
42 - CFG updating after constant propagation
43 purge_dead_edges, purge_all_dead_edges */
49 #include "hard-reg-set.h"
50 #include "basic-block.h"
59 #include "insn-config.h"
61 /* Stubs in case we don't have a return insn. */
64 #define gen_return() NULL_RTX
67 /* 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. */
74 rtx tail_recursion_label_list
;
76 static int can_delete_note_p
PARAMS ((rtx
));
77 static int can_delete_label_p
PARAMS ((rtx
));
78 static void commit_one_edge_insertion
PARAMS ((edge
, int));
79 static bool try_redirect_by_replacing_jump
PARAMS ((edge
, basic_block
));
80 static rtx last_loop_beg_note
PARAMS ((rtx
));
81 static bool back_edge_of_syntactic_loop_p
PARAMS ((basic_block
, basic_block
));
82 static basic_block force_nonfallthru_and_redirect
PARAMS ((edge
, basic_block
));
84 /* Return true if NOTE is not one of the ones that must be kept paired,
85 so that we may simply delete it. */
88 can_delete_note_p (note
)
91 return (NOTE_LINE_NUMBER (note
) == NOTE_INSN_DELETED
92 || NOTE_LINE_NUMBER (note
) == NOTE_INSN_BASIC_BLOCK
);
95 /* True if a given label can be deleted. */
98 can_delete_label_p (label
)
101 return (!LABEL_PRESERVE_P (label
)
102 /* User declared labels must be preserved. */
103 && LABEL_NAME (label
) == 0
104 && !in_expr_list_p (forced_labels
, label
)
105 && !in_expr_list_p (label_value_list
, label
)
106 && !in_expr_list_p (exception_handler_labels
, label
));
109 /* Delete INSN by patching it out. Return the next insn. */
115 rtx next
= NEXT_INSN (insn
);
117 bool really_delete
= true;
119 if (GET_CODE (insn
) == CODE_LABEL
)
121 /* Some labels can't be directly removed from the INSN chain, as they
122 might be references via variables, constant pool etc.
123 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
124 if (! can_delete_label_p (insn
))
126 const char *name
= LABEL_NAME (insn
);
128 really_delete
= false;
129 PUT_CODE (insn
, NOTE
);
130 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED_LABEL
;
131 NOTE_SOURCE_FILE (insn
) = name
;
134 remove_node_from_expr_list (insn
, &nonlocal_goto_handler_labels
);
139 /* If this insn has already been deleted, something is very wrong. */
140 if (INSN_DELETED_P (insn
))
143 INSN_DELETED_P (insn
) = 1;
146 /* If deleting a jump, decrement the use count of the label. Deleting
147 the label itself should happen in the normal course of block merging. */
148 if (GET_CODE (insn
) == JUMP_INSN
150 && GET_CODE (JUMP_LABEL (insn
)) == CODE_LABEL
)
151 LABEL_NUSES (JUMP_LABEL (insn
))--;
153 /* Also if deleting an insn that references a label. */
154 else if ((note
= find_reg_note (insn
, REG_LABEL
, NULL_RTX
)) != NULL_RTX
155 && GET_CODE (XEXP (note
, 0)) == CODE_LABEL
)
156 LABEL_NUSES (XEXP (note
, 0))--;
158 if (GET_CODE (insn
) == JUMP_INSN
159 && (GET_CODE (PATTERN (insn
)) == ADDR_VEC
160 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
))
162 rtx pat
= PATTERN (insn
);
163 int diff_vec_p
= GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
;
164 int len
= XVECLEN (pat
, diff_vec_p
);
167 for (i
= 0; i
< len
; i
++)
169 rtx label
= XEXP (XVECEXP (pat
, diff_vec_p
, i
), 0);
171 /* When deleting code in bulk (e.g. removing many unreachable
172 blocks) we can delete a label that's a target of the vector
173 before deleting the vector itself. */
174 if (GET_CODE (label
) != NOTE
)
175 LABEL_NUSES (label
)--;
182 /* Like delete_insn but also purge dead edges from BB. */
184 delete_insn_and_edges (insn
)
190 if (basic_block_for_insn
192 && (unsigned int)INSN_UID (insn
) < basic_block_for_insn
->num_elements
193 && BLOCK_FOR_INSN (insn
)
194 && BLOCK_FOR_INSN (insn
)->end
== insn
)
196 x
= delete_insn (insn
);
198 purge_dead_edges (BLOCK_FOR_INSN (insn
));
202 /* Unlink a chain of insns between START and FINISH, leaving notes
203 that must be paired. */
206 delete_insn_chain (start
, finish
)
211 /* Unchain the insns one by one. It would be quicker to delete all of these
212 with a single unchaining, rather than one at a time, but we need to keep
216 next
= NEXT_INSN (start
);
217 if (GET_CODE (start
) == NOTE
&& !can_delete_note_p (start
))
220 next
= delete_insn (start
);
228 /* Like delete_insn but also purge dead edges from BB. */
230 delete_insn_chain_and_edges (first
, last
)
235 if (basic_block_for_insn
237 && (unsigned int)INSN_UID (last
) < basic_block_for_insn
->num_elements
238 && BLOCK_FOR_INSN (last
)
239 && BLOCK_FOR_INSN (last
)->end
== last
)
241 delete_insn_chain (first
, last
);
243 purge_dead_edges (BLOCK_FOR_INSN (last
));
246 /* Create a new basic block consisting of the instructions between HEAD and END
247 inclusive. This function is designed to allow fast BB construction - reuses
248 the note and basic block struct in BB_NOTE, if any and do not grow
249 BASIC_BLOCK chain and should be used directly only by CFG construction code.
250 END can be NULL in to create new empty basic block before HEAD. Both END
251 and HEAD can be NULL to create basic block at the end of INSN chain. */
254 create_basic_block_structure (index
, head
, end
, bb_note
)
256 rtx head
, end
, bb_note
;
261 && ! RTX_INTEGRATED_P (bb_note
)
262 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
265 /* If we found an existing note, thread it back onto the chain. */
269 if (GET_CODE (head
) == CODE_LABEL
)
273 after
= PREV_INSN (head
);
277 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
278 reorder_insns (bb_note
, bb_note
, after
);
282 /* Otherwise we must create a note and a basic block structure. */
288 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
289 else if (GET_CODE (head
) == CODE_LABEL
&& end
)
291 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
297 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
303 NOTE_BASIC_BLOCK (bb_note
) = bb
;
306 /* Always include the bb note in the block. */
307 if (NEXT_INSN (end
) == bb_note
)
314 BASIC_BLOCK (index
) = bb
;
315 if (basic_block_for_insn
)
316 update_bb_for_insn (bb
);
318 /* Tag the block so that we know it has been used when considering
319 other basic block notes. */
325 /* Create new basic block consisting of instructions in between HEAD and END
326 and place it to the BB chain at position INDEX. END can be NULL in to
327 create new empty basic block before HEAD. Both END and HEAD can be NULL to
328 create basic block at the end of INSN chain. */
331 create_basic_block (index
, head
, end
)
338 /* Place the new block just after the block being split. */
339 VARRAY_GROW (basic_block_info
, ++n_basic_blocks
);
341 /* Some parts of the compiler expect blocks to be number in
342 sequential order so insert the new block immediately after the
343 block being split.. */
344 for (i
= n_basic_blocks
- 1; i
> index
; --i
)
346 basic_block tmp
= BASIC_BLOCK (i
- 1);
348 BASIC_BLOCK (i
) = tmp
;
352 bb
= create_basic_block_structure (index
, head
, end
, NULL
);
357 /* Delete the insns in a (non-live) block. We physically delete every
358 non-deleted-note insn, and update the flow graph appropriately.
360 Return nonzero if we deleted an exception handler. */
362 /* ??? Preserving all such notes strikes me as wrong. It would be nice
363 to post-process the stream to remove empty blocks, loops, ranges, etc. */
366 flow_delete_block (b
)
369 int deleted_handler
= 0;
372 /* If the head of this block is a CODE_LABEL, then it might be the
373 label for an exception handler which can't be reached.
375 We need to remove the label from the exception_handler_label list
376 and remove the associated NOTE_INSN_EH_REGION_BEG and
377 NOTE_INSN_EH_REGION_END notes. */
381 never_reached_warning (insn
, b
->end
);
383 if (GET_CODE (insn
) == CODE_LABEL
)
384 maybe_remove_eh_handler (insn
);
386 /* Include any jump table following the basic block. */
388 if (GET_CODE (end
) == JUMP_INSN
389 && (tmp
= JUMP_LABEL (end
)) != NULL_RTX
390 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
391 && GET_CODE (tmp
) == JUMP_INSN
392 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
393 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
396 /* Include any barrier that may follow the basic block. */
397 tmp
= next_nonnote_insn (end
);
398 if (tmp
&& GET_CODE (tmp
) == BARRIER
)
401 /* Selectively delete the entire chain. */
403 delete_insn_chain (insn
, end
);
405 /* Remove the edges into and out of this block. Note that there may
406 indeed be edges in, if we are removing an unreachable loop. */
407 while (b
->pred
!= NULL
)
408 remove_edge (b
->pred
);
409 while (b
->succ
!= NULL
)
410 remove_edge (b
->succ
);
415 /* Remove the basic block from the array, and compact behind it. */
418 return deleted_handler
;
421 /* Records the basic block struct in BB_FOR_INSN, for every instruction
422 indexed by INSN_UID. MAX is the size of the array. */
425 compute_bb_for_insn (max
)
430 if (basic_block_for_insn
)
431 VARRAY_FREE (basic_block_for_insn
);
433 VARRAY_BB_INIT (basic_block_for_insn
, max
, "basic_block_for_insn");
435 for (i
= 0; i
< n_basic_blocks
; ++i
)
437 basic_block bb
= BASIC_BLOCK (i
);
441 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
443 if (INSN_UID (insn
) < max
)
444 VARRAY_BB (basic_block_for_insn
, INSN_UID (insn
)) = bb
;
452 /* Release the basic_block_for_insn array. */
457 if (basic_block_for_insn
)
458 VARRAY_FREE (basic_block_for_insn
);
460 basic_block_for_insn
= 0;
463 /* Update insns block within BB. */
466 update_bb_for_insn (bb
)
471 if (! basic_block_for_insn
)
474 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
476 set_block_for_insn (insn
, bb
);
482 /* Record INSN's block as BB. */
485 set_block_for_insn (insn
, bb
)
489 size_t uid
= INSN_UID (insn
);
491 if (uid
>= basic_block_for_insn
->num_elements
)
493 /* Add one-eighth the size so we don't keep calling xrealloc. */
494 size_t new_size
= uid
+ (uid
+ 7) / 8;
496 VARRAY_GROW (basic_block_for_insn
, new_size
);
499 VARRAY_BB (basic_block_for_insn
, uid
) = bb
;
502 /* Split a block BB after insn INSN creating a new fallthru edge.
503 Return the new edge. Note that to keep other parts of the compiler happy,
504 this function renumbers all the basic blocks so that the new
505 one has a number one greater than the block split. */
508 split_block (bb
, insn
)
516 /* There is no point splitting the block after its end. */
520 /* Create the new basic block. */
521 new_bb
= create_basic_block (bb
->index
+ 1, NEXT_INSN (insn
), bb
->end
);
522 new_bb
->count
= bb
->count
;
523 new_bb
->frequency
= bb
->frequency
;
524 new_bb
->loop_depth
= bb
->loop_depth
;
527 /* Redirect the outgoing edges. */
528 new_bb
->succ
= bb
->succ
;
530 for (e
= new_bb
->succ
; e
; e
= e
->succ_next
)
533 new_edge
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
535 if (bb
->global_live_at_start
)
537 new_bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
538 new_bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
539 COPY_REG_SET (new_bb
->global_live_at_end
, bb
->global_live_at_end
);
541 /* We now have to calculate which registers are live at the end
542 of the split basic block and at the start of the new basic
543 block. Start with those registers that are known to be live
544 at the end of the original basic block and get
545 propagate_block to determine which registers are live. */
546 COPY_REG_SET (new_bb
->global_live_at_start
, bb
->global_live_at_end
);
547 propagate_block (new_bb
, new_bb
->global_live_at_start
, NULL
, NULL
, 0);
548 COPY_REG_SET (bb
->global_live_at_end
,
549 new_bb
->global_live_at_start
);
550 #ifdef HAVE_conditional_execution
551 /* In the presence of conditional execution we are not able to update
552 liveness precisely. */
553 if (reload_completed
)
555 bb
->flags
|= BB_DIRTY
;
556 new_bb
->flags
|= BB_DIRTY
;
564 /* Blocks A and B are to be merged into a single block A. The insns
565 are already contiguous, hence `nomove'. */
568 merge_blocks_nomove (a
, b
)
571 rtx b_head
= b
->head
, b_end
= b
->end
, a_end
= a
->end
;
572 rtx del_first
= NULL_RTX
, del_last
= NULL_RTX
;
576 /* If there was a CODE_LABEL beginning B, delete it. */
577 if (GET_CODE (b_head
) == CODE_LABEL
)
579 /* Detect basic blocks with nothing but a label. This can happen
580 in particular at the end of a function. */
584 del_first
= del_last
= b_head
;
585 b_head
= NEXT_INSN (b_head
);
588 /* Delete the basic block note and handle blocks containing just that
590 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
598 b_head
= NEXT_INSN (b_head
);
601 /* If there was a jump out of A, delete it. */
602 if (GET_CODE (a_end
) == JUMP_INSN
)
606 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
607 if (GET_CODE (prev
) != NOTE
608 || NOTE_LINE_NUMBER (prev
) == NOTE_INSN_BASIC_BLOCK
615 /* If this was a conditional jump, we need to also delete
616 the insn that set cc0. */
617 if (only_sets_cc0_p (prev
))
621 prev
= prev_nonnote_insn (prev
);
628 a_end
= PREV_INSN (del_first
);
630 else if (GET_CODE (NEXT_INSN (a_end
)) == BARRIER
)
631 del_first
= NEXT_INSN (a_end
);
633 /* Normally there should only be one successor of A and that is B, but
634 partway though the merge of blocks for conditional_execution we'll
635 be merging a TEST block with THEN and ELSE successors. Free the
636 whole lot of them and hope the caller knows what they're doing. */
638 remove_edge (a
->succ
);
640 /* Adjust the edges out of B for the new owner. */
641 for (e
= b
->succ
; e
; e
= e
->succ_next
)
644 a
->flags
|= b
->flags
;
646 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
647 b
->pred
= b
->succ
= NULL
;
648 a
->global_live_at_end
= b
->global_live_at_end
;
652 /* Delete everything marked above as well as crap that might be
653 hanging out between the two blocks. */
654 delete_insn_chain (del_first
, del_last
);
656 /* Reassociate the insns of B with A. */
659 if (basic_block_for_insn
)
663 for (x
= a_end
; x
!= b_end
; x
= NEXT_INSN (x
))
664 BLOCK_FOR_INSN (x
) = a
;
666 BLOCK_FOR_INSN (b_end
) = a
;
675 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
682 if (block
== EXIT_BLOCK_PTR
)
685 if (GET_CODE (block
->head
) != CODE_LABEL
)
687 block
->head
= emit_label_before (gen_label_rtx (), block
->head
);
688 if (basic_block_for_insn
)
689 set_block_for_insn (block
->head
, block
);
695 /* Attempt to perform edge redirection by replacing possibly complex jump
696 instruction by unconditional jump or removing jump completely. This can
697 apply only if all edges now point to the same block. The parameters and
698 return values are equivalent to redirect_edge_and_branch. */
701 try_redirect_by_replacing_jump (e
, target
)
705 basic_block src
= e
->src
;
706 rtx insn
= src
->end
, kill_from
;
711 /* Verify that all targets will be TARGET. */
712 for (tmp
= src
->succ
; tmp
; tmp
= tmp
->succ_next
)
713 if (tmp
->dest
!= target
&& tmp
!= e
)
716 if (tmp
|| !onlyjump_p (insn
))
719 /* Avoid removing branch with side effects. */
720 set
= single_set (insn
);
721 if (!set
|| side_effects_p (set
))
724 /* In case we zap a conditional jump, we'll need to kill
725 the cc0 setter too. */
728 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
)))
729 kill_from
= PREV_INSN (insn
);
732 /* See if we can create the fallthru edge. */
733 if (can_fallthru (src
, target
))
736 fprintf (rtl_dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
739 /* Selectively unlink whole insn chain. */
740 delete_insn_chain (kill_from
, PREV_INSN (target
->head
));
743 /* If this already is simplejump, redirect it. */
744 else if (simplejump_p (insn
))
746 if (e
->dest
== target
)
749 fprintf (rtl_dump_file
, "Redirecting jump %i from %i to %i.\n",
750 INSN_UID (insn
), e
->dest
->index
, target
->index
);
751 if (!redirect_jump (insn
, block_label (target
), 0))
753 if (target
== EXIT_BLOCK_PTR
)
759 /* Cannot do anything for target exit block. */
760 else if (target
== EXIT_BLOCK_PTR
)
763 /* Or replace possibly complicated jump insn by simple jump insn. */
766 rtx target_label
= block_label (target
);
769 emit_jump_insn_after (gen_jump (target_label
), insn
);
770 JUMP_LABEL (src
->end
) = target_label
;
771 LABEL_NUSES (target_label
)++;
773 fprintf (rtl_dump_file
, "Replacing insn %i by jump %i\n",
774 INSN_UID (insn
), INSN_UID (src
->end
));
777 delete_insn_chain (kill_from
, insn
);
779 /* Recognize a tablejump that we are converting to a
780 simple jump and remove its associated CODE_LABEL
781 and ADDR_VEC or ADDR_DIFF_VEC. */
782 if ((tmp
= JUMP_LABEL (insn
)) != NULL_RTX
783 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
784 && GET_CODE (tmp
) == JUMP_INSN
785 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
786 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
788 delete_insn_chain (JUMP_LABEL (insn
), tmp
);
791 barrier
= next_nonnote_insn (src
->end
);
792 if (!barrier
|| GET_CODE (barrier
) != BARRIER
)
793 emit_barrier_after (src
->end
);
796 /* Keep only one edge out and set proper flags. */
797 while (src
->succ
->succ_next
)
798 remove_edge (src
->succ
);
801 e
->flags
= EDGE_FALLTHRU
;
805 e
->probability
= REG_BR_PROB_BASE
;
806 e
->count
= src
->count
;
808 /* We don't want a block to end on a line-number note since that has
809 the potential of changing the code between -g and not -g. */
810 while (GET_CODE (e
->src
->end
) == NOTE
811 && NOTE_LINE_NUMBER (e
->src
->end
) >= 0)
812 delete_insn (e
->src
->end
);
814 if (e
->dest
!= target
)
815 redirect_edge_succ (e
, target
);
820 /* Return last loop_beg note appearing after INSN, before start of next
821 basic block. Return INSN if there are no such notes.
823 When emitting jump to redirect an fallthru edge, it should always appear
824 after the LOOP_BEG notes, as loop optimizer expect loop to either start by
825 fallthru edge or jump following the LOOP_BEG note jumping to the loop exit
829 last_loop_beg_note (insn
)
834 for (insn
= NEXT_INSN (insn
); insn
&& GET_CODE (insn
) == NOTE
835 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
;
836 insn
= NEXT_INSN (insn
))
837 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
843 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
844 expense of adding new instructions or reordering basic blocks.
846 Function can be also called with edge destination equivalent to the TARGET.
847 Then it should try the simplifications and do nothing if none is possible.
849 Return true if transformation succeeded. We still return false in case E
850 already destinated TARGET and we didn't managed to simplify instruction
854 redirect_edge_and_branch (e
, target
)
859 rtx old_label
= e
->dest
->head
;
860 basic_block src
= e
->src
;
863 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
866 if (try_redirect_by_replacing_jump (e
, target
))
869 /* Do this fast path late, as we want above code to simplify for cases
870 where called on single edge leaving basic block containing nontrivial
872 else if (e
->dest
== target
)
875 /* We can only redirect non-fallthru edges of jump insn. */
876 if (e
->flags
& EDGE_FALLTHRU
)
878 else if (GET_CODE (insn
) != JUMP_INSN
)
881 /* Recognize a tablejump and adjust all matching cases. */
882 if ((tmp
= JUMP_LABEL (insn
)) != NULL_RTX
883 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
884 && GET_CODE (tmp
) == JUMP_INSN
885 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
886 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
890 rtx new_label
= block_label (target
);
892 if (target
== EXIT_BLOCK_PTR
)
894 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
895 vec
= XVEC (PATTERN (tmp
), 0);
897 vec
= XVEC (PATTERN (tmp
), 1);
899 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
900 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
902 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
903 --LABEL_NUSES (old_label
);
904 ++LABEL_NUSES (new_label
);
907 /* Handle casesi dispatch insns */
908 if ((tmp
= single_set (insn
)) != NULL
909 && SET_DEST (tmp
) == pc_rtx
910 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
911 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
912 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
914 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (VOIDmode
,
916 --LABEL_NUSES (old_label
);
917 ++LABEL_NUSES (new_label
);
922 /* ?? We may play the games with moving the named labels from
923 one basic block to the other in case only one computed_jump is
925 if (computed_jump_p (insn
)
926 /* A return instruction can't be redirected. */
927 || returnjump_p (insn
))
930 /* If the insn doesn't go where we think, we're confused. */
931 if (JUMP_LABEL (insn
) != old_label
)
934 /* If the substitution doesn't succeed, die. This can happen
935 if the back end emitted unrecognizable instructions or if
936 target is exit block on some arches. */
937 if (!redirect_jump (insn
, block_label (target
), 0))
939 if (target
== EXIT_BLOCK_PTR
)
946 fprintf (rtl_dump_file
, "Edge %i->%i redirected to %i\n",
947 e
->src
->index
, e
->dest
->index
, target
->index
);
949 if (e
->dest
!= target
)
950 redirect_edge_succ_nodup (e
, target
);
955 /* Like force_nonfallthru below, but additionally performs redirection
956 Used by redirect_edge_and_branch_force. */
959 force_nonfallthru_and_redirect (e
, target
)
963 basic_block jump_block
, new_bb
= NULL
;
967 if (e
->flags
& EDGE_ABNORMAL
)
969 else if (!(e
->flags
& EDGE_FALLTHRU
))
971 else if (e
->src
== ENTRY_BLOCK_PTR
)
973 /* We can't redirect the entry block. Create an empty block at the
974 start of the function which we use to add the new jump. */
976 basic_block bb
= create_basic_block (0, e
->dest
->head
, NULL
);
978 /* Change the existing edge's source to be the new block, and add
979 a new edge from the entry block to the new block. */
981 for (pe1
= &ENTRY_BLOCK_PTR
->succ
; *pe1
; pe1
= &(*pe1
)->succ_next
)
989 make_single_succ_edge (ENTRY_BLOCK_PTR
, bb
, EDGE_FALLTHRU
);
992 if (e
->src
->succ
->succ_next
)
994 /* Create the new structures. */
995 note
= last_loop_beg_note (e
->src
->end
);
997 = create_basic_block (e
->src
->index
+ 1, NEXT_INSN (note
), NULL
);
998 jump_block
->count
= e
->count
;
999 jump_block
->frequency
= EDGE_FREQUENCY (e
);
1000 jump_block
->loop_depth
= target
->loop_depth
;
1002 if (target
->global_live_at_start
)
1004 jump_block
->global_live_at_start
1005 = OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1006 jump_block
->global_live_at_end
1007 = OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1008 COPY_REG_SET (jump_block
->global_live_at_start
,
1009 target
->global_live_at_start
);
1010 COPY_REG_SET (jump_block
->global_live_at_end
,
1011 target
->global_live_at_start
);
1015 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1016 new_edge
->probability
= e
->probability
;
1017 new_edge
->count
= e
->count
;
1019 /* Redirect old edge. */
1020 redirect_edge_pred (e
, jump_block
);
1021 e
->probability
= REG_BR_PROB_BASE
;
1023 new_bb
= jump_block
;
1026 jump_block
= e
->src
;
1028 e
->flags
&= ~EDGE_FALLTHRU
;
1029 if (target
== EXIT_BLOCK_PTR
)
1032 emit_jump_insn_after (gen_return (), jump_block
->end
);
1038 rtx label
= block_label (target
);
1039 emit_jump_insn_after (gen_jump (label
), jump_block
->end
);
1040 JUMP_LABEL (jump_block
->end
) = label
;
1041 LABEL_NUSES (label
)++;
1044 emit_barrier_after (jump_block
->end
);
1045 redirect_edge_succ_nodup (e
, target
);
1050 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1051 (and possibly create new basic block) to make edge non-fallthru.
1052 Return newly created BB or NULL if none. */
1055 force_nonfallthru (e
)
1058 return force_nonfallthru_and_redirect (e
, e
->dest
);
1061 /* Redirect edge even at the expense of creating new jump insn or
1062 basic block. Return new basic block if created, NULL otherwise.
1063 Abort if conversion is impossible. */
1066 redirect_edge_and_branch_force (e
, target
)
1070 if (redirect_edge_and_branch (e
, target
)
1071 || e
->dest
== target
)
1074 /* In case the edge redirection failed, try to force it to be non-fallthru
1075 and redirect newly created simplejump. */
1076 return force_nonfallthru_and_redirect (e
, target
);
1079 /* The given edge should potentially be a fallthru edge. If that is in
1080 fact true, delete the jump and barriers that are in the way. */
1083 tidy_fallthru_edge (e
, b
, c
)
1089 /* ??? In a late-running flow pass, other folks may have deleted basic
1090 blocks by nopping out blocks, leaving multiple BARRIERs between here
1091 and the target label. They ought to be chastized and fixed.
1093 We can also wind up with a sequence of undeletable labels between
1094 one block and the next.
1096 So search through a sequence of barriers, labels, and notes for
1097 the head of block C and assert that we really do fall through. */
1099 if (next_real_insn (b
->end
) != next_real_insn (PREV_INSN (c
->head
)))
1102 /* Remove what will soon cease being the jump insn from the source block.
1103 If block B consisted only of this single jump, turn it into a deleted
1106 if (GET_CODE (q
) == JUMP_INSN
1108 && (any_uncondjump_p (q
)
1109 || (b
->succ
== e
&& e
->succ_next
== NULL
)))
1112 /* If this was a conditional jump, we need to also delete
1113 the insn that set cc0. */
1114 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1120 /* We don't want a block to end on a line-number note since that has
1121 the potential of changing the code between -g and not -g. */
1122 while (GET_CODE (q
) == NOTE
&& NOTE_LINE_NUMBER (q
) >= 0)
1126 /* Selectively unlink the sequence. */
1127 if (q
!= PREV_INSN (c
->head
))
1128 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (c
->head
));
1130 e
->flags
|= EDGE_FALLTHRU
;
1133 /* Fix up edges that now fall through, or rather should now fall through
1134 but previously required a jump around now deleted blocks. Simplify
1135 the search by only examining blocks numerically adjacent, since this
1136 is how find_basic_blocks created them. */
1139 tidy_fallthru_edges ()
1143 for (i
= 1; i
< n_basic_blocks
; i
++)
1145 basic_block b
= BASIC_BLOCK (i
- 1);
1146 basic_block c
= BASIC_BLOCK (i
);
1149 /* We care about simple conditional or unconditional jumps with
1152 If we had a conditional branch to the next instruction when
1153 find_basic_blocks was called, then there will only be one
1154 out edge for the block which ended with the conditional
1155 branch (since we do not create duplicate edges).
1157 Furthermore, the edge will be marked as a fallthru because we
1158 merge the flags for the duplicate edges. So we do not want to
1159 check that the edge is not a FALLTHRU edge. */
1161 if ((s
= b
->succ
) != NULL
1162 && ! (s
->flags
& EDGE_COMPLEX
)
1163 && s
->succ_next
== NULL
1165 /* If the jump insn has side effects, we can't tidy the edge. */
1166 && (GET_CODE (b
->end
) != JUMP_INSN
1167 || onlyjump_p (b
->end
)))
1168 tidy_fallthru_edge (s
, b
, c
);
1172 /* Helper function for split_edge. Return true in case edge BB2 to BB1
1173 is back edge of syntactic loop. */
1176 back_edge_of_syntactic_loop_p (bb1
, bb2
)
1177 basic_block bb1
, bb2
;
1182 if (bb1
->index
> bb2
->index
)
1184 else if (bb1
->index
== bb2
->index
)
1187 for (insn
= bb1
->end
; insn
!= bb2
->head
&& count
>= 0;
1188 insn
= NEXT_INSN (insn
))
1189 if (GET_CODE (insn
) == NOTE
)
1191 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
1193 else if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
)
1200 /* Split a (typically critical) edge. Return the new block.
1201 Abort on abnormal edges.
1203 ??? The code generally expects to be called on critical edges.
1204 The case of a block ending in an unconditional jump to a
1205 block with multiple predecessors is not handled optimally. */
1208 split_edge (edge_in
)
1215 /* Abnormal edges cannot be split. */
1216 if ((edge_in
->flags
& EDGE_ABNORMAL
) != 0)
1219 /* We are going to place the new block in front of edge destination.
1220 Avoid existence of fallthru predecessors. */
1221 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1225 for (e
= edge_in
->dest
->pred
; e
; e
= e
->pred_next
)
1226 if (e
->flags
& EDGE_FALLTHRU
)
1230 force_nonfallthru (e
);
1233 /* Create the basic block note.
1235 Where we place the note can have a noticeable impact on the generated
1236 code. Consider this cfg:
1246 If we need to insert an insn on the edge from block 0 to block 1,
1247 we want to ensure the instructions we insert are outside of any
1248 loop notes that physically sit between block 0 and block 1. Otherwise
1249 we confuse the loop optimizer into thinking the loop is a phony. */
1251 if (edge_in
->dest
!= EXIT_BLOCK_PTR
1252 && PREV_INSN (edge_in
->dest
->head
)
1253 && GET_CODE (PREV_INSN (edge_in
->dest
->head
)) == NOTE
1254 && (NOTE_LINE_NUMBER (PREV_INSN (edge_in
->dest
->head
))
1255 == NOTE_INSN_LOOP_BEG
)
1256 && !back_edge_of_syntactic_loop_p (edge_in
->dest
, edge_in
->src
))
1257 before
= PREV_INSN (edge_in
->dest
->head
);
1258 else if (edge_in
->dest
!= EXIT_BLOCK_PTR
)
1259 before
= edge_in
->dest
->head
;
1263 bb
= create_basic_block (edge_in
->dest
== EXIT_BLOCK_PTR
? n_basic_blocks
1264 : edge_in
->dest
->index
, before
, NULL
);
1265 bb
->count
= edge_in
->count
;
1266 bb
->frequency
= EDGE_FREQUENCY (edge_in
);
1268 /* ??? This info is likely going to be out of date very soon. */
1269 if (edge_in
->dest
->global_live_at_start
)
1271 bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1272 bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1273 COPY_REG_SET (bb
->global_live_at_start
,
1274 edge_in
->dest
->global_live_at_start
);
1275 COPY_REG_SET (bb
->global_live_at_end
,
1276 edge_in
->dest
->global_live_at_start
);
1279 edge_out
= make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1281 /* For non-fallthry edges, we must adjust the predecessor's
1282 jump instruction to target our new block. */
1283 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1285 if (!redirect_edge_and_branch (edge_in
, bb
))
1289 redirect_edge_succ (edge_in
, bb
);
1294 /* Queue instructions for insertion on an edge between two basic blocks.
1295 The new instructions and basic blocks (if any) will not appear in the
1296 CFG until commit_edge_insertions is called. */
1299 insert_insn_on_edge (pattern
, e
)
1303 /* We cannot insert instructions on an abnormal critical edge.
1304 It will be easier to find the culprit if we die now. */
1305 if ((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
1308 if (e
->insns
== NULL_RTX
)
1311 push_to_sequence (e
->insns
);
1313 emit_insn (pattern
);
1315 e
->insns
= get_insns ();
1319 /* Update the CFG for the instructions queued on edge E. */
1322 commit_one_edge_insertion (e
, watch_calls
)
1326 rtx before
= NULL_RTX
, after
= NULL_RTX
, insns
, tmp
, last
;
1329 /* Pull the insns off the edge now since the edge might go away. */
1331 e
->insns
= NULL_RTX
;
1333 /* Special case -- avoid inserting code between call and storing
1334 its return value. */
1335 if (watch_calls
&& (e
->flags
& EDGE_FALLTHRU
) && !e
->dest
->pred
->pred_next
1336 && e
->src
!= ENTRY_BLOCK_PTR
1337 && GET_CODE (e
->src
->end
) == CALL_INSN
)
1339 rtx next
= next_nonnote_insn (e
->src
->end
);
1341 after
= e
->dest
->head
;
1342 /* The first insn after the call may be a stack pop, skip it. */
1344 && keep_with_call_p (next
))
1347 next
= next_nonnote_insn (next
);
1351 if (!before
&& !after
)
1353 /* Figure out where to put these things. If the destination has
1354 one predecessor, insert there. Except for the exit block. */
1355 if (e
->dest
->pred
->pred_next
== NULL
&& e
->dest
!= EXIT_BLOCK_PTR
)
1359 /* Get the location correct wrt a code label, and "nice" wrt
1360 a basic block note, and before everything else. */
1362 if (GET_CODE (tmp
) == CODE_LABEL
)
1363 tmp
= NEXT_INSN (tmp
);
1364 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1365 tmp
= NEXT_INSN (tmp
);
1366 if (tmp
== bb
->head
)
1369 after
= PREV_INSN (tmp
);
1371 after
= get_last_insn ();
1374 /* If the source has one successor and the edge is not abnormal,
1375 insert there. Except for the entry block. */
1376 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1377 && e
->src
->succ
->succ_next
== NULL
1378 && e
->src
!= ENTRY_BLOCK_PTR
)
1382 /* It is possible to have a non-simple jump here. Consider a target
1383 where some forms of unconditional jumps clobber a register. This
1384 happens on the fr30 for example.
1386 We know this block has a single successor, so we can just emit
1387 the queued insns before the jump. */
1388 if (GET_CODE (bb
->end
) == JUMP_INSN
)
1389 for (before
= bb
->end
;
1390 GET_CODE (PREV_INSN (before
)) == NOTE
1391 && NOTE_LINE_NUMBER (PREV_INSN (before
)) ==
1392 NOTE_INSN_LOOP_BEG
; before
= PREV_INSN (before
))
1396 /* We'd better be fallthru, or we've lost track of what's what. */
1397 if ((e
->flags
& EDGE_FALLTHRU
) == 0)
1403 /* Otherwise we must split the edge. */
1406 bb
= split_edge (e
);
1411 /* Now that we've found the spot, do the insertion. */
1415 emit_insns_before (insns
, before
);
1416 last
= prev_nonnote_insn (before
);
1419 last
= emit_insns_after (insns
, after
);
1421 if (returnjump_p (last
))
1423 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1424 This is not currently a problem because this only happens
1425 for the (single) epilogue, which already has a fallthru edge
1429 if (e
->dest
!= EXIT_BLOCK_PTR
1430 || e
->succ_next
!= NULL
|| (e
->flags
& EDGE_FALLTHRU
) == 0)
1433 e
->flags
&= ~EDGE_FALLTHRU
;
1434 emit_barrier_after (last
);
1437 delete_insn (before
);
1439 else if (GET_CODE (last
) == JUMP_INSN
)
1442 find_sub_basic_blocks (bb
);
1445 /* Update the CFG for all queued instructions. */
1448 commit_edge_insertions ()
1453 #ifdef ENABLE_CHECKING
1454 verify_flow_info ();
1458 bb
= ENTRY_BLOCK_PTR
;
1463 for (e
= bb
->succ
; e
; e
= next
)
1465 next
= e
->succ_next
;
1467 commit_one_edge_insertion (e
, false);
1470 if (++i
>= n_basic_blocks
)
1472 bb
= BASIC_BLOCK (i
);
1476 /* Update the CFG for all queued instructions, taking special care of inserting
1477 code on edges between call and storing its return value. */
1480 commit_edge_insertions_watch_calls ()
1485 #ifdef ENABLE_CHECKING
1486 verify_flow_info ();
1490 bb
= ENTRY_BLOCK_PTR
;
1495 for (e
= bb
->succ
; e
; e
= next
)
1497 next
= e
->succ_next
;
1499 commit_one_edge_insertion (e
, true);
1502 if (++i
>= n_basic_blocks
)
1504 bb
= BASIC_BLOCK (i
);
1508 /* Print out one basic block with live information at start and end. */
1519 fprintf (outf
, ";; Basic block %d, loop depth %d, count ",
1520 bb
->index
, bb
->loop_depth
);
1521 fprintf (outf
, HOST_WIDEST_INT_PRINT_DEC
, (HOST_WIDEST_INT
) bb
->count
);
1524 fputs (";; Predecessors: ", outf
);
1525 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1526 dump_edge_info (outf
, e
, 0);
1529 fputs (";; Registers live at start:", outf
);
1530 dump_regset (bb
->global_live_at_start
, outf
);
1533 for (insn
= bb
->head
, last
= NEXT_INSN (bb
->end
); insn
!= last
;
1534 insn
= NEXT_INSN (insn
))
1535 print_rtl_single (outf
, insn
);
1537 fputs (";; Registers live at end:", outf
);
1538 dump_regset (bb
->global_live_at_end
, outf
);
1541 fputs (";; Successors: ", outf
);
1542 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1543 dump_edge_info (outf
, e
, 1);
1551 dump_bb (bb
, stderr
);
1558 dump_bb (BASIC_BLOCK (n
), stderr
);
1561 /* Like print_rtl, but also print out live information for the start of each
1565 print_rtl_with_bb (outf
, rtx_first
)
1572 fprintf (outf
, "(nil)\n");
1576 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
1577 int max_uid
= get_max_uid ();
1579 = (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1581 = (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1582 enum bb_state
*in_bb_p
1583 = (enum bb_state
*) xcalloc (max_uid
, sizeof (enum bb_state
));
1585 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1587 basic_block bb
= BASIC_BLOCK (i
);
1590 start
[INSN_UID (bb
->head
)] = bb
;
1591 end
[INSN_UID (bb
->end
)] = bb
;
1592 for (x
= bb
->head
; x
!= NULL_RTX
; x
= NEXT_INSN (x
))
1594 enum bb_state state
= IN_MULTIPLE_BB
;
1596 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
1598 in_bb_p
[INSN_UID (x
)] = state
;
1605 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
1610 if ((bb
= start
[INSN_UID (tmp_rtx
)]) != NULL
)
1612 fprintf (outf
, ";; Start of basic block %d, registers live:",
1614 dump_regset (bb
->global_live_at_start
, outf
);
1618 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
1619 && GET_CODE (tmp_rtx
) != NOTE
1620 && GET_CODE (tmp_rtx
) != BARRIER
)
1621 fprintf (outf
, ";; Insn is not within a basic block\n");
1622 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
1623 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
1625 did_output
= print_rtl_single (outf
, tmp_rtx
);
1627 if ((bb
= end
[INSN_UID (tmp_rtx
)]) != NULL
)
1629 fprintf (outf
, ";; End of basic block %d, registers live:\n",
1631 dump_regset (bb
->global_live_at_end
, outf
);
1644 if (current_function_epilogue_delay_list
!= 0)
1646 fprintf (outf
, "\n;; Insns in epilogue delay list:\n\n");
1647 for (tmp_rtx
= current_function_epilogue_delay_list
; tmp_rtx
!= 0;
1648 tmp_rtx
= XEXP (tmp_rtx
, 1))
1649 print_rtl_single (outf
, XEXP (tmp_rtx
, 0));
1654 update_br_prob_note (bb
)
1658 if (GET_CODE (bb
->end
) != JUMP_INSN
)
1660 note
= find_reg_note (bb
->end
, REG_BR_PROB
, NULL_RTX
);
1661 if (!note
|| INTVAL (XEXP (note
, 0)) == BRANCH_EDGE (bb
)->probability
)
1663 XEXP (note
, 0) = GEN_INT (BRANCH_EDGE (bb
)->probability
);
1666 /* Verify the CFG consistency. This function check some CFG invariants and
1667 aborts when something is wrong. Hope that this function will help to
1668 convert many optimization passes to preserve CFG consistent.
1670 Currently it does following checks:
1672 - test head/end pointers
1673 - overlapping of basic blocks
1674 - edge list correctness
1675 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1676 - tails of basic blocks (ensure that boundary is necessary)
1677 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1678 and NOTE_INSN_BASIC_BLOCK
1679 - check that all insns are in the basic blocks
1680 (except the switch handling code, barriers and notes)
1681 - check that all returns are followed by barriers
1683 In future it can be extended check a lot of other stuff as well
1684 (reachability of basic blocks, life information, etc. etc.). */
1689 const int max_uid
= get_max_uid ();
1690 const rtx rtx_first
= get_insns ();
1691 rtx last_head
= get_last_insn ();
1692 basic_block
*bb_info
, *last_visited
;
1693 size_t *edge_checksum
;
1695 int i
, last_bb_num_seen
, num_bb_notes
, err
= 0;
1697 bb_info
= (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1698 last_visited
= (basic_block
*) xcalloc (n_basic_blocks
+ 2,
1699 sizeof (basic_block
));
1700 edge_checksum
= (size_t *) xcalloc (n_basic_blocks
+ 2, sizeof (size_t));
1702 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1704 basic_block bb
= BASIC_BLOCK (i
);
1705 rtx head
= bb
->head
;
1708 /* Verify the end of the basic block is in the INSN chain. */
1709 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1715 error ("end insn %d for block %d not found in the insn stream",
1716 INSN_UID (end
), bb
->index
);
1720 /* Work backwards from the end to the head of the basic block
1721 to verify the head is in the RTL chain. */
1722 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1724 /* While walking over the insn chain, verify insns appear
1725 in only one basic block and initialize the BB_INFO array
1726 used by other passes. */
1727 if (bb_info
[INSN_UID (x
)] != NULL
)
1729 error ("insn %d is in multiple basic blocks (%d and %d)",
1730 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
1734 bb_info
[INSN_UID (x
)] = bb
;
1741 error ("head insn %d for block %d not found in the insn stream",
1742 INSN_UID (head
), bb
->index
);
1749 /* Now check the basic blocks (boundaries etc.) */
1750 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1752 basic_block bb
= BASIC_BLOCK (i
);
1753 int n_fallthru
= 0, n_eh
= 0, n_call
= 0, n_abnormal
= 0, n_branch
= 0;
1757 if (INSN_P (bb
->end
)
1758 && (note
= find_reg_note (bb
->end
, REG_BR_PROB
, NULL_RTX
))
1759 && any_condjump_p (bb
->end
))
1761 if (INTVAL (XEXP (note
, 0)) != BRANCH_EDGE (bb
)->probability
)
1763 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
1764 INTVAL (XEXP (note
, 0)), BRANCH_EDGE (bb
)->probability
);
1770 error ("verify_flow_info: Wrong count of block %i %i",
1771 bb
->index
, (int)bb
->count
);
1774 if (bb
->frequency
< 0)
1776 error ("verify_flow_info: Wrong frequency of block %i %i",
1777 bb
->index
, bb
->frequency
);
1780 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1782 if (last_visited
[e
->dest
->index
+ 2] == bb
)
1784 error ("verify_flow_info: Duplicate edge %i->%i",
1785 e
->src
->index
, e
->dest
->index
);
1788 if (e
->probability
< 0 || e
->probability
> REG_BR_PROB_BASE
)
1790 error ("verify_flow_info: Wrong probability of edge %i->%i %i",
1791 e
->src
->index
, e
->dest
->index
, e
->probability
);
1796 error ("verify_flow_info: Wrong count of edge %i->%i %i",
1797 e
->src
->index
, e
->dest
->index
, (int)e
->count
);
1801 last_visited
[e
->dest
->index
+ 2] = bb
;
1803 if (e
->flags
& EDGE_FALLTHRU
)
1806 if ((e
->flags
& ~EDGE_DFS_BACK
) == 0)
1809 if (e
->flags
& EDGE_ABNORMAL_CALL
)
1812 if (e
->flags
& EDGE_EH
)
1814 else if (e
->flags
& EDGE_ABNORMAL
)
1817 if ((e
->flags
& EDGE_FALLTHRU
)
1818 && e
->src
!= ENTRY_BLOCK_PTR
1819 && e
->dest
!= EXIT_BLOCK_PTR
)
1823 if (e
->src
->index
+ 1 != e
->dest
->index
)
1826 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
1827 e
->src
->index
, e
->dest
->index
);
1831 for (insn
= NEXT_INSN (e
->src
->end
); insn
!= e
->dest
->head
;
1832 insn
= NEXT_INSN (insn
))
1833 if (GET_CODE (insn
) == BARRIER
1834 #ifndef CASE_DROPS_THROUGH
1837 || (INSN_P (insn
) && ! JUMP_TABLE_DATA_P (insn
))
1841 error ("verify_flow_info: Incorrect fallthru %i->%i",
1842 e
->src
->index
, e
->dest
->index
);
1843 fatal_insn ("wrong insn in the fallthru edge", insn
);
1850 error ("verify_flow_info: Basic block %d succ edge is corrupted",
1852 fprintf (stderr
, "Predecessor: ");
1853 dump_edge_info (stderr
, e
, 0);
1854 fprintf (stderr
, "\nSuccessor: ");
1855 dump_edge_info (stderr
, e
, 1);
1856 fprintf (stderr
, "\n");
1860 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
1863 if (n_eh
&& GET_CODE (PATTERN (bb
->end
)) != RESX
1864 && !find_reg_note (bb
->end
, REG_EH_REGION
, NULL_RTX
))
1866 error ("Missing REG_EH_REGION note in the end of bb %i", bb
->index
);
1870 && (GET_CODE (bb
->end
) != JUMP_INSN
1871 || (n_branch
> 1 && (any_uncondjump_p (bb
->end
)
1872 || any_condjump_p (bb
->end
)))))
1874 error ("Too many outgoing branch edges from bb %i", bb
->index
);
1877 if (n_fallthru
&& any_uncondjump_p (bb
->end
))
1879 error ("Fallthru edge after unconditional jump %i", bb
->index
);
1882 if (n_branch
!= 1 && any_uncondjump_p (bb
->end
))
1884 error ("Wrong amount of branch edges after unconditional jump %i", bb
->index
);
1887 if (n_branch
!= 1 && any_condjump_p (bb
->end
)
1888 && JUMP_LABEL (bb
->end
) != BASIC_BLOCK (bb
->index
+ 1)->head
)
1890 error ("Wrong amount of branch edges after conditional jump %i", bb
->index
);
1893 if (n_call
&& GET_CODE (bb
->end
) != CALL_INSN
)
1895 error ("Call edges for non-call insn in bb %i", bb
->index
);
1899 && (GET_CODE (bb
->end
) != CALL_INSN
&& n_call
!= n_abnormal
)
1900 && (GET_CODE (bb
->end
) != JUMP_INSN
1901 || any_condjump_p (bb
->end
)
1902 || any_uncondjump_p (bb
->end
)))
1904 error ("Abnormal edges for no purpose in bb %i", bb
->index
);
1912 /* Ensure existence of barrier in BB with no fallthru edges. */
1913 for (insn
= bb
->end
; !insn
|| GET_CODE (insn
) != BARRIER
;
1914 insn
= NEXT_INSN (insn
))
1916 || (GET_CODE (insn
) == NOTE
1917 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BASIC_BLOCK
))
1919 error ("missing barrier after block %i", bb
->index
);
1925 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1929 error ("basic block %d pred edge is corrupted", bb
->index
);
1930 fputs ("Predecessor: ", stderr
);
1931 dump_edge_info (stderr
, e
, 0);
1932 fputs ("\nSuccessor: ", stderr
);
1933 dump_edge_info (stderr
, e
, 1);
1934 fputc ('\n', stderr
);
1937 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
1940 for (x
= bb
->head
; x
!= NEXT_INSN (bb
->end
); x
= NEXT_INSN (x
))
1941 if (basic_block_for_insn
&& BLOCK_FOR_INSN (x
) != bb
)
1944 if (! BLOCK_FOR_INSN (x
))
1946 ("insn %d inside basic block %d but block_for_insn is NULL",
1947 INSN_UID (x
), bb
->index
);
1950 ("insn %d inside basic block %d but block_for_insn is %i",
1951 INSN_UID (x
), bb
->index
, BLOCK_FOR_INSN (x
)->index
);
1956 /* OK pointers are correct. Now check the header of basic
1957 block. It ought to contain optional CODE_LABEL followed
1958 by NOTE_BASIC_BLOCK. */
1960 if (GET_CODE (x
) == CODE_LABEL
)
1964 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1972 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
1974 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1980 /* Do checks for empty blocks her. e */
1983 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
1985 if (NOTE_INSN_BASIC_BLOCK_P (x
))
1987 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
1988 INSN_UID (x
), bb
->index
);
1995 if (GET_CODE (x
) == JUMP_INSN
1996 || GET_CODE (x
) == CODE_LABEL
1997 || GET_CODE (x
) == BARRIER
)
1999 error ("in basic block %d:", bb
->index
);
2000 fatal_insn ("flow control insn inside a basic block", x
);
2005 /* Complete edge checksumming for ENTRY and EXIT. */
2009 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
2010 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
2012 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
2013 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
2016 for (i
= -2; i
< n_basic_blocks
; ++i
)
2017 if (edge_checksum
[i
+ 2])
2019 error ("basic block %i edge lists are corrupted", i
);
2023 last_bb_num_seen
= -1;
2025 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2027 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2029 basic_block bb
= NOTE_BASIC_BLOCK (x
);
2032 if (bb
->index
!= last_bb_num_seen
+ 1)
2033 internal_error ("basic blocks not numbered consecutively");
2035 last_bb_num_seen
= bb
->index
;
2038 if (!bb_info
[INSN_UID (x
)])
2040 switch (GET_CODE (x
))
2047 /* An addr_vec is placed outside any block block. */
2049 && GET_CODE (NEXT_INSN (x
)) == JUMP_INSN
2050 && (GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_DIFF_VEC
2051 || GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_VEC
))
2054 /* But in any case, non-deletable labels can appear anywhere. */
2058 fatal_insn ("insn outside basic block", x
);
2063 && GET_CODE (x
) == JUMP_INSN
2064 && returnjump_p (x
) && ! condjump_p (x
)
2065 && ! (NEXT_INSN (x
) && GET_CODE (NEXT_INSN (x
)) == BARRIER
))
2066 fatal_insn ("return not followed by barrier", x
);
2069 if (num_bb_notes
!= n_basic_blocks
)
2071 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2072 num_bb_notes
, n_basic_blocks
);
2075 internal_error ("verify_flow_info failed");
2079 free (last_visited
);
2080 free (edge_checksum
);
2083 /* Assume that the preceding pass has possibly eliminated jump instructions
2084 or converted the unconditional jumps. Eliminate the edges from CFG.
2085 Return true if any edges are eliminated. */
2088 purge_dead_edges (bb
)
2092 rtx insn
= bb
->end
, note
;
2093 bool purged
= false;
2095 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2096 if (GET_CODE (insn
) == INSN
2097 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
2101 if (! may_trap_p (PATTERN (insn
))
2102 || ((eqnote
= find_reg_equal_equiv_note (insn
))
2103 && ! may_trap_p (XEXP (eqnote
, 0))))
2104 remove_note (insn
, note
);
2107 /* Cleanup abnormal edges caused by throwing insns that have been
2109 if (! can_throw_internal (bb
->end
))
2110 for (e
= bb
->succ
; e
; e
= next
)
2112 next
= e
->succ_next
;
2113 if (e
->flags
& EDGE_EH
)
2116 bb
->flags
|= BB_DIRTY
;
2121 if (GET_CODE (insn
) == JUMP_INSN
)
2126 /* We do care only about conditional jumps and simplejumps. */
2127 if (!any_condjump_p (insn
)
2128 && !returnjump_p (insn
)
2129 && !simplejump_p (insn
))
2132 /* Branch probability/prediction notes are defined only for
2133 condjumps. We've possibly turned condjump into simplejump. */
2134 if (simplejump_p (insn
))
2136 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2138 remove_note (insn
, note
);
2139 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
2140 remove_note (insn
, note
);
2143 for (e
= bb
->succ
; e
; e
= next
)
2145 next
= e
->succ_next
;
2147 /* Avoid abnormal flags to leak from computed jumps turned
2148 into simplejumps. */
2150 e
->flags
&= ~EDGE_ABNORMAL
;
2152 /* Check purposes we can have edge. */
2153 if ((e
->flags
& EDGE_FALLTHRU
)
2154 && any_condjump_p (insn
))
2156 else if (e
->dest
!= EXIT_BLOCK_PTR
2157 && e
->dest
->head
== JUMP_LABEL (insn
))
2159 else if (e
->dest
== EXIT_BLOCK_PTR
2160 && returnjump_p (insn
))
2163 bb
->flags
|= BB_DIRTY
;
2168 if (!bb
->succ
|| !purged
)
2172 fprintf (rtl_dump_file
, "Purged edges from bb %i\n", bb
->index
);
2177 /* Redistribute probabilities. */
2178 if (!bb
->succ
->succ_next
)
2180 bb
->succ
->probability
= REG_BR_PROB_BASE
;
2181 bb
->succ
->count
= bb
->count
;
2185 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2189 b
= BRANCH_EDGE (bb
);
2190 f
= FALLTHRU_EDGE (bb
);
2191 b
->probability
= INTVAL (XEXP (note
, 0));
2192 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
2193 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
2194 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
2200 /* If we don't see a jump insn, we don't know exactly why the block would
2201 have been broken at this point. Look for a simple, non-fallthru edge,
2202 as these are only created by conditional branches. If we find such an
2203 edge we know that there used to be a jump here and can then safely
2204 remove all non-fallthru edges. */
2205 for (e
= bb
->succ
; e
&& (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
));
2212 for (e
= bb
->succ
; e
; e
= next
)
2214 next
= e
->succ_next
;
2215 if (!(e
->flags
& EDGE_FALLTHRU
))
2217 bb
->flags
|= BB_DIRTY
;
2223 if (!bb
->succ
|| bb
->succ
->succ_next
)
2226 bb
->succ
->probability
= REG_BR_PROB_BASE
;
2227 bb
->succ
->count
= bb
->count
;
2230 fprintf (rtl_dump_file
, "Purged non-fallthru edges from bb %i\n",
2235 /* Search all basic blocks for potentially dead edges and purge them. Return
2236 true if some edge has been eliminated. */
2239 purge_all_dead_edges (update_life_p
)
2242 int i
, purged
= false;
2247 blocks
= sbitmap_alloc (n_basic_blocks
);
2248 sbitmap_zero (blocks
);
2251 for (i
= 0; i
< n_basic_blocks
; i
++)
2253 bool purged_here
= purge_dead_edges (BASIC_BLOCK (i
));
2255 purged
|= purged_here
;
2256 if (purged_here
&& update_life_p
)
2257 SET_BIT (blocks
, i
);
2260 if (update_life_p
&& purged
)
2261 update_life_info (blocks
, UPDATE_LIFE_GLOBAL
,
2262 PROP_DEATH_NOTES
| PROP_SCAN_DEAD_CODE
2263 | PROP_KILL_DEAD_CODE
);
2266 sbitmap_free (blocks
);