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"
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
93 || NOTE_LINE_NUMBER (note
) == NOTE_INSN_PREDICTION
);
96 /* True if a given label can be deleted. */
99 can_delete_label_p (label
)
102 return (!LABEL_PRESERVE_P (label
)
103 /* User declared labels must be preserved. */
104 && LABEL_NAME (label
) == 0
105 && !in_expr_list_p (forced_labels
, label
)
106 && !in_expr_list_p (label_value_list
, 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.
252 AFTER is the basic block we should be put after. */
255 create_basic_block_structure (index
, head
, end
, bb_note
, after
)
257 rtx head
, end
, bb_note
;
263 && ! RTX_INTEGRATED_P (bb_note
)
264 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
267 /* If we found an existing note, thread it back onto the chain. */
271 if (GET_CODE (head
) == CODE_LABEL
)
275 after
= PREV_INSN (head
);
279 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
280 reorder_insns (bb_note
, bb_note
, after
);
284 /* Otherwise we must create a note and a basic block structure. */
290 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
291 else if (GET_CODE (head
) == CODE_LABEL
&& end
)
293 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
299 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
305 NOTE_BASIC_BLOCK (bb_note
) = bb
;
308 /* Always include the bb note in the block. */
309 if (NEXT_INSN (end
) == bb_note
)
316 link_block (bb
, after
);
317 BASIC_BLOCK (index
) = bb
;
318 if (basic_block_for_insn
)
319 update_bb_for_insn (bb
);
321 /* Tag the block so that we know it has been used when considering
322 other basic block notes. */
328 /* Create new basic block consisting of instructions in between HEAD and END
329 and place it to the BB chain after block AFTER. END can be NULL in to
330 create new empty basic block before HEAD. Both END and HEAD can be NULL to
331 create basic block at the end of INSN chain. */
334 create_basic_block (head
, end
, after
)
340 int index
= after
->index
+ 1;
342 /* Place the new block just after the block being split. */
343 VARRAY_GROW (basic_block_info
, ++n_basic_blocks
);
345 /* Some parts of the compiler expect blocks to be number in
346 sequential order so insert the new block immediately after the
347 block being split.. */
348 for (i
= n_basic_blocks
- 1; i
> index
; --i
)
350 basic_block tmp
= BASIC_BLOCK (i
- 1);
352 BASIC_BLOCK (i
) = tmp
;
356 bb
= create_basic_block_structure (index
, head
, end
, NULL
, after
);
361 /* Delete the insns in a (non-live) block. We physically delete every
362 non-deleted-note insn, and update the flow graph appropriately.
364 Return nonzero if we deleted an exception handler. */
366 /* ??? Preserving all such notes strikes me as wrong. It would be nice
367 to post-process the stream to remove empty blocks, loops, ranges, etc. */
370 flow_delete_block_noexpunge (b
)
373 int deleted_handler
= 0;
376 /* If the head of this block is a CODE_LABEL, then it might be the
377 label for an exception handler which can't be reached.
379 We need to remove the label from the exception_handler_label list
380 and remove the associated NOTE_INSN_EH_REGION_BEG and
381 NOTE_INSN_EH_REGION_END notes. */
383 /* Get rid of all NOTE_INSN_PREDICTIONs hanging before the block. */
385 for (insn
= PREV_INSN (b
->head
); insn
; insn
= PREV_INSN (insn
))
387 if (GET_CODE (insn
) != NOTE
)
389 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_PREDICTION
)
390 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
395 never_reached_warning (insn
, b
->end
);
397 if (GET_CODE (insn
) == CODE_LABEL
)
398 maybe_remove_eh_handler (insn
);
400 /* Include any jump table following the basic block. */
402 if (GET_CODE (end
) == JUMP_INSN
403 && (tmp
= JUMP_LABEL (end
)) != NULL_RTX
404 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
405 && GET_CODE (tmp
) == JUMP_INSN
406 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
407 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
410 /* Include any barrier that may follow the basic block. */
411 tmp
= next_nonnote_insn (end
);
412 if (tmp
&& GET_CODE (tmp
) == BARRIER
)
415 /* Selectively delete the entire chain. */
417 delete_insn_chain (insn
, end
);
419 /* Remove the edges into and out of this block. Note that there may
420 indeed be edges in, if we are removing an unreachable loop. */
421 while (b
->pred
!= NULL
)
422 remove_edge (b
->pred
);
423 while (b
->succ
!= NULL
)
424 remove_edge (b
->succ
);
429 return deleted_handler
;
433 flow_delete_block (b
)
436 int deleted_handler
= flow_delete_block_noexpunge (b
);
438 /* Remove the basic block from the array, and compact behind it. */
441 return deleted_handler
;
444 /* Records the basic block struct in BB_FOR_INSN, for every instruction
445 indexed by INSN_UID. MAX is the size of the array. */
448 compute_bb_for_insn (max
)
453 if (basic_block_for_insn
)
454 VARRAY_FREE (basic_block_for_insn
);
456 VARRAY_BB_INIT (basic_block_for_insn
, max
, "basic_block_for_insn");
458 for (i
= 0; i
< n_basic_blocks
; ++i
)
460 basic_block bb
= BASIC_BLOCK (i
);
464 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
466 if (INSN_UID (insn
) < max
)
467 VARRAY_BB (basic_block_for_insn
, INSN_UID (insn
)) = bb
;
475 /* Release the basic_block_for_insn array. */
480 if (basic_block_for_insn
)
481 VARRAY_FREE (basic_block_for_insn
);
483 basic_block_for_insn
= 0;
486 /* Update insns block within BB. */
489 update_bb_for_insn (bb
)
494 if (! basic_block_for_insn
)
497 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
499 set_block_for_insn (insn
, bb
);
505 /* Record INSN's block as BB. */
508 set_block_for_insn (insn
, bb
)
512 size_t uid
= INSN_UID (insn
);
514 if (uid
>= basic_block_for_insn
->num_elements
)
516 /* Add one-eighth the size so we don't keep calling xrealloc. */
517 size_t new_size
= uid
+ (uid
+ 7) / 8;
519 VARRAY_GROW (basic_block_for_insn
, new_size
);
522 VARRAY_BB (basic_block_for_insn
, uid
) = bb
;
525 /* Split a block BB after insn INSN creating a new fallthru edge.
526 Return the new edge. Note that to keep other parts of the compiler happy,
527 this function renumbers all the basic blocks so that the new
528 one has a number one greater than the block split. */
531 split_block (bb
, insn
)
539 /* There is no point splitting the block after its end. */
543 /* Create the new basic block. */
544 new_bb
= create_basic_block (NEXT_INSN (insn
), bb
->end
, bb
);
545 new_bb
->count
= bb
->count
;
546 new_bb
->frequency
= bb
->frequency
;
547 new_bb
->loop_depth
= bb
->loop_depth
;
550 /* Redirect the outgoing edges. */
551 new_bb
->succ
= bb
->succ
;
553 for (e
= new_bb
->succ
; e
; e
= e
->succ_next
)
556 new_edge
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
558 if (bb
->global_live_at_start
)
560 new_bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
561 new_bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
562 COPY_REG_SET (new_bb
->global_live_at_end
, bb
->global_live_at_end
);
564 /* We now have to calculate which registers are live at the end
565 of the split basic block and at the start of the new basic
566 block. Start with those registers that are known to be live
567 at the end of the original basic block and get
568 propagate_block to determine which registers are live. */
569 COPY_REG_SET (new_bb
->global_live_at_start
, bb
->global_live_at_end
);
570 propagate_block (new_bb
, new_bb
->global_live_at_start
, NULL
, NULL
, 0);
571 COPY_REG_SET (bb
->global_live_at_end
,
572 new_bb
->global_live_at_start
);
573 #ifdef HAVE_conditional_execution
574 /* In the presence of conditional execution we are not able to update
575 liveness precisely. */
576 if (reload_completed
)
578 bb
->flags
|= BB_DIRTY
;
579 new_bb
->flags
|= BB_DIRTY
;
587 /* Blocks A and B are to be merged into a single block A. The insns
588 are already contiguous, hence `nomove'. */
591 merge_blocks_nomove (a
, b
)
594 rtx b_head
= b
->head
, b_end
= b
->end
, a_end
= a
->end
;
595 rtx del_first
= NULL_RTX
, del_last
= NULL_RTX
;
599 /* If there was a CODE_LABEL beginning B, delete it. */
600 if (GET_CODE (b_head
) == CODE_LABEL
)
602 /* Detect basic blocks with nothing but a label. This can happen
603 in particular at the end of a function. */
607 del_first
= del_last
= b_head
;
608 b_head
= NEXT_INSN (b_head
);
611 /* Delete the basic block note and handle blocks containing just that
613 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
621 b_head
= NEXT_INSN (b_head
);
624 /* If there was a jump out of A, delete it. */
625 if (GET_CODE (a_end
) == JUMP_INSN
)
629 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
630 if (GET_CODE (prev
) != NOTE
631 || NOTE_LINE_NUMBER (prev
) == NOTE_INSN_BASIC_BLOCK
638 /* If this was a conditional jump, we need to also delete
639 the insn that set cc0. */
640 if (only_sets_cc0_p (prev
))
644 prev
= prev_nonnote_insn (prev
);
651 a_end
= PREV_INSN (del_first
);
653 else if (GET_CODE (NEXT_INSN (a_end
)) == BARRIER
)
654 del_first
= NEXT_INSN (a_end
);
656 /* Normally there should only be one successor of A and that is B, but
657 partway though the merge of blocks for conditional_execution we'll
658 be merging a TEST block with THEN and ELSE successors. Free the
659 whole lot of them and hope the caller knows what they're doing. */
661 remove_edge (a
->succ
);
663 /* Adjust the edges out of B for the new owner. */
664 for (e
= b
->succ
; e
; e
= e
->succ_next
)
667 a
->flags
|= b
->flags
;
669 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
670 b
->pred
= b
->succ
= NULL
;
671 a
->global_live_at_end
= b
->global_live_at_end
;
675 /* Delete everything marked above as well as crap that might be
676 hanging out between the two blocks. */
677 delete_insn_chain (del_first
, del_last
);
679 /* Reassociate the insns of B with A. */
682 if (basic_block_for_insn
)
686 for (x
= a_end
; x
!= b_end
; x
= NEXT_INSN (x
))
687 set_block_for_insn (x
, a
);
689 set_block_for_insn (b_end
, a
);
698 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
705 if (block
== EXIT_BLOCK_PTR
)
708 if (GET_CODE (block
->head
) != CODE_LABEL
)
710 block
->head
= emit_label_before (gen_label_rtx (), block
->head
);
711 if (basic_block_for_insn
)
712 set_block_for_insn (block
->head
, block
);
718 /* Attempt to perform edge redirection by replacing possibly complex jump
719 instruction by unconditional jump or removing jump completely. This can
720 apply only if all edges now point to the same block. The parameters and
721 return values are equivalent to redirect_edge_and_branch. */
724 try_redirect_by_replacing_jump (e
, target
)
728 basic_block src
= e
->src
;
729 rtx insn
= src
->end
, kill_from
;
734 /* Verify that all targets will be TARGET. */
735 for (tmp
= src
->succ
; tmp
; tmp
= tmp
->succ_next
)
736 if (tmp
->dest
!= target
&& tmp
!= e
)
739 if (tmp
|| !onlyjump_p (insn
))
741 if (reload_completed
&& JUMP_LABEL (insn
)
742 && (table
= NEXT_INSN (JUMP_LABEL (insn
))) != NULL_RTX
743 && GET_CODE (table
) == JUMP_INSN
744 && (GET_CODE (PATTERN (table
)) == ADDR_VEC
745 || GET_CODE (PATTERN (table
)) == ADDR_DIFF_VEC
))
748 /* Avoid removing branch with side effects. */
749 set
= single_set (insn
);
750 if (!set
|| side_effects_p (set
))
753 /* In case we zap a conditional jump, we'll need to kill
754 the cc0 setter too. */
757 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
)))
758 kill_from
= PREV_INSN (insn
);
761 /* See if we can create the fallthru edge. */
762 if (can_fallthru (src
, target
))
765 fprintf (rtl_dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
768 /* Selectively unlink whole insn chain. */
769 delete_insn_chain (kill_from
, PREV_INSN (target
->head
));
772 /* If this already is simplejump, redirect it. */
773 else if (simplejump_p (insn
))
775 if (e
->dest
== target
)
778 fprintf (rtl_dump_file
, "Redirecting jump %i from %i to %i.\n",
779 INSN_UID (insn
), e
->dest
->index
, target
->index
);
780 if (!redirect_jump (insn
, block_label (target
), 0))
782 if (target
== EXIT_BLOCK_PTR
)
788 /* Cannot do anything for target exit block. */
789 else if (target
== EXIT_BLOCK_PTR
)
792 /* Or replace possibly complicated jump insn by simple jump insn. */
795 rtx target_label
= block_label (target
);
798 emit_jump_insn_after (gen_jump (target_label
), insn
);
799 JUMP_LABEL (src
->end
) = target_label
;
800 LABEL_NUSES (target_label
)++;
802 fprintf (rtl_dump_file
, "Replacing insn %i by jump %i\n",
803 INSN_UID (insn
), INSN_UID (src
->end
));
806 delete_insn_chain (kill_from
, insn
);
808 /* Recognize a tablejump that we are converting to a
809 simple jump and remove its associated CODE_LABEL
810 and ADDR_VEC or ADDR_DIFF_VEC. */
811 if ((tmp
= JUMP_LABEL (insn
)) != NULL_RTX
812 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
813 && GET_CODE (tmp
) == JUMP_INSN
814 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
815 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
817 delete_insn_chain (JUMP_LABEL (insn
), tmp
);
820 barrier
= next_nonnote_insn (src
->end
);
821 if (!barrier
|| GET_CODE (barrier
) != BARRIER
)
822 emit_barrier_after (src
->end
);
825 /* Keep only one edge out and set proper flags. */
826 while (src
->succ
->succ_next
)
827 remove_edge (src
->succ
);
830 e
->flags
= EDGE_FALLTHRU
;
834 e
->probability
= REG_BR_PROB_BASE
;
835 e
->count
= src
->count
;
837 /* We don't want a block to end on a line-number note since that has
838 the potential of changing the code between -g and not -g. */
839 while (GET_CODE (e
->src
->end
) == NOTE
840 && NOTE_LINE_NUMBER (e
->src
->end
) >= 0)
841 delete_insn (e
->src
->end
);
843 if (e
->dest
!= target
)
844 redirect_edge_succ (e
, target
);
849 /* Return last loop_beg note appearing after INSN, before start of next
850 basic block. Return INSN if there are no such notes.
852 When emitting jump to redirect an fallthru edge, it should always appear
853 after the LOOP_BEG notes, as loop optimizer expect loop to either start by
854 fallthru edge or jump following the LOOP_BEG note jumping to the loop exit
858 last_loop_beg_note (insn
)
863 for (insn
= NEXT_INSN (insn
); insn
&& GET_CODE (insn
) == NOTE
864 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
;
865 insn
= NEXT_INSN (insn
))
866 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
872 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
873 expense of adding new instructions or reordering basic blocks.
875 Function can be also called with edge destination equivalent to the TARGET.
876 Then it should try the simplifications and do nothing if none is possible.
878 Return true if transformation succeeded. We still return false in case E
879 already destinated TARGET and we didn't managed to simplify instruction
883 redirect_edge_and_branch (e
, target
)
888 rtx old_label
= e
->dest
->head
;
889 basic_block src
= e
->src
;
892 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
895 if (try_redirect_by_replacing_jump (e
, target
))
898 /* Do this fast path late, as we want above code to simplify for cases
899 where called on single edge leaving basic block containing nontrivial
901 else if (e
->dest
== target
)
904 /* We can only redirect non-fallthru edges of jump insn. */
905 if (e
->flags
& EDGE_FALLTHRU
)
907 else if (GET_CODE (insn
) != JUMP_INSN
)
910 /* Recognize a tablejump and adjust all matching cases. */
911 if ((tmp
= JUMP_LABEL (insn
)) != NULL_RTX
912 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
913 && GET_CODE (tmp
) == JUMP_INSN
914 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
915 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
919 rtx new_label
= block_label (target
);
921 if (target
== EXIT_BLOCK_PTR
)
923 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
924 vec
= XVEC (PATTERN (tmp
), 0);
926 vec
= XVEC (PATTERN (tmp
), 1);
928 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
929 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
931 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
932 --LABEL_NUSES (old_label
);
933 ++LABEL_NUSES (new_label
);
936 /* Handle casesi dispatch insns */
937 if ((tmp
= single_set (insn
)) != NULL
938 && SET_DEST (tmp
) == pc_rtx
939 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
940 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
941 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
943 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (VOIDmode
,
945 --LABEL_NUSES (old_label
);
946 ++LABEL_NUSES (new_label
);
951 /* ?? We may play the games with moving the named labels from
952 one basic block to the other in case only one computed_jump is
954 if (computed_jump_p (insn
)
955 /* A return instruction can't be redirected. */
956 || returnjump_p (insn
))
959 /* If the insn doesn't go where we think, we're confused. */
960 if (JUMP_LABEL (insn
) != old_label
)
963 /* If the substitution doesn't succeed, die. This can happen
964 if the back end emitted unrecognizable instructions or if
965 target is exit block on some arches. */
966 if (!redirect_jump (insn
, block_label (target
), 0))
968 if (target
== EXIT_BLOCK_PTR
)
975 fprintf (rtl_dump_file
, "Edge %i->%i redirected to %i\n",
976 e
->src
->index
, e
->dest
->index
, target
->index
);
978 if (e
->dest
!= target
)
979 redirect_edge_succ_nodup (e
, target
);
984 /* Like force_nonfallthru below, but additionally performs redirection
985 Used by redirect_edge_and_branch_force. */
988 force_nonfallthru_and_redirect (e
, target
)
992 basic_block jump_block
, new_bb
= NULL
;
996 if (e
->flags
& EDGE_ABNORMAL
)
998 else if (!(e
->flags
& EDGE_FALLTHRU
))
1000 else if (e
->src
== ENTRY_BLOCK_PTR
)
1002 /* We can't redirect the entry block. Create an empty block at the
1003 start of the function which we use to add the new jump. */
1005 basic_block bb
= create_basic_block (e
->dest
->head
, NULL
, ENTRY_BLOCK_PTR
);
1007 /* Change the existing edge's source to be the new block, and add
1008 a new edge from the entry block to the new block. */
1010 for (pe1
= &ENTRY_BLOCK_PTR
->succ
; *pe1
; pe1
= &(*pe1
)->succ_next
)
1013 *pe1
= e
->succ_next
;
1018 make_single_succ_edge (ENTRY_BLOCK_PTR
, bb
, EDGE_FALLTHRU
);
1021 if (e
->src
->succ
->succ_next
)
1023 /* Create the new structures. */
1024 note
= last_loop_beg_note (e
->src
->end
);
1026 = create_basic_block (NEXT_INSN (note
), NULL
, e
->src
);
1027 jump_block
->count
= e
->count
;
1028 jump_block
->frequency
= EDGE_FREQUENCY (e
);
1029 jump_block
->loop_depth
= target
->loop_depth
;
1031 if (target
->global_live_at_start
)
1033 jump_block
->global_live_at_start
1034 = OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1035 jump_block
->global_live_at_end
1036 = OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1037 COPY_REG_SET (jump_block
->global_live_at_start
,
1038 target
->global_live_at_start
);
1039 COPY_REG_SET (jump_block
->global_live_at_end
,
1040 target
->global_live_at_start
);
1044 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1045 new_edge
->probability
= e
->probability
;
1046 new_edge
->count
= e
->count
;
1048 /* Redirect old edge. */
1049 redirect_edge_pred (e
, jump_block
);
1050 e
->probability
= REG_BR_PROB_BASE
;
1052 new_bb
= jump_block
;
1055 jump_block
= e
->src
;
1057 e
->flags
&= ~EDGE_FALLTHRU
;
1058 if (target
== EXIT_BLOCK_PTR
)
1061 emit_jump_insn_after (gen_return (), jump_block
->end
);
1067 rtx label
= block_label (target
);
1068 emit_jump_insn_after (gen_jump (label
), jump_block
->end
);
1069 JUMP_LABEL (jump_block
->end
) = label
;
1070 LABEL_NUSES (label
)++;
1073 emit_barrier_after (jump_block
->end
);
1074 redirect_edge_succ_nodup (e
, target
);
1079 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1080 (and possibly create new basic block) to make edge non-fallthru.
1081 Return newly created BB or NULL if none. */
1084 force_nonfallthru (e
)
1087 return force_nonfallthru_and_redirect (e
, e
->dest
);
1090 /* Redirect edge even at the expense of creating new jump insn or
1091 basic block. Return new basic block if created, NULL otherwise.
1092 Abort if conversion is impossible. */
1095 redirect_edge_and_branch_force (e
, target
)
1099 if (redirect_edge_and_branch (e
, target
)
1100 || e
->dest
== target
)
1103 /* In case the edge redirection failed, try to force it to be non-fallthru
1104 and redirect newly created simplejump. */
1105 return force_nonfallthru_and_redirect (e
, target
);
1108 /* The given edge should potentially be a fallthru edge. If that is in
1109 fact true, delete the jump and barriers that are in the way. */
1112 tidy_fallthru_edge (e
, b
, c
)
1118 /* ??? In a late-running flow pass, other folks may have deleted basic
1119 blocks by nopping out blocks, leaving multiple BARRIERs between here
1120 and the target label. They ought to be chastized and fixed.
1122 We can also wind up with a sequence of undeletable labels between
1123 one block and the next.
1125 So search through a sequence of barriers, labels, and notes for
1126 the head of block C and assert that we really do fall through. */
1128 for (q
= NEXT_INSN (b
->end
); q
!= c
->head
; q
= NEXT_INSN (q
))
1132 /* Remove what will soon cease being the jump insn from the source block.
1133 If block B consisted only of this single jump, turn it into a deleted
1136 if (GET_CODE (q
) == JUMP_INSN
1138 && (any_uncondjump_p (q
)
1139 || (b
->succ
== e
&& e
->succ_next
== NULL
)))
1142 /* If this was a conditional jump, we need to also delete
1143 the insn that set cc0. */
1144 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1150 /* We don't want a block to end on a line-number note since that has
1151 the potential of changing the code between -g and not -g. */
1152 while (GET_CODE (q
) == NOTE
&& NOTE_LINE_NUMBER (q
) >= 0)
1156 /* Selectively unlink the sequence. */
1157 if (q
!= PREV_INSN (c
->head
))
1158 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (c
->head
));
1160 e
->flags
|= EDGE_FALLTHRU
;
1163 /* Fix up edges that now fall through, or rather should now fall through
1164 but previously required a jump around now deleted blocks. Simplify
1165 the search by only examining blocks numerically adjacent, since this
1166 is how find_basic_blocks created them. */
1169 tidy_fallthru_edges ()
1173 for (i
= 1; i
< n_basic_blocks
; i
++)
1175 basic_block c
= BASIC_BLOCK (i
);
1176 basic_block b
= c
->prev_bb
;
1179 /* We care about simple conditional or unconditional jumps with
1182 If we had a conditional branch to the next instruction when
1183 find_basic_blocks was called, then there will only be one
1184 out edge for the block which ended with the conditional
1185 branch (since we do not create duplicate edges).
1187 Furthermore, the edge will be marked as a fallthru because we
1188 merge the flags for the duplicate edges. So we do not want to
1189 check that the edge is not a FALLTHRU edge. */
1191 if ((s
= b
->succ
) != NULL
1192 && ! (s
->flags
& EDGE_COMPLEX
)
1193 && s
->succ_next
== NULL
1195 /* If the jump insn has side effects, we can't tidy the edge. */
1196 && (GET_CODE (b
->end
) != JUMP_INSN
1197 || onlyjump_p (b
->end
)))
1198 tidy_fallthru_edge (s
, b
, c
);
1202 /* Helper function for split_edge. Return true in case edge BB2 to BB1
1203 is back edge of syntactic loop. */
1206 back_edge_of_syntactic_loop_p (bb1
, bb2
)
1207 basic_block bb1
, bb2
;
1212 if (bb1
->index
> bb2
->index
)
1214 else if (bb1
->index
== bb2
->index
)
1217 for (insn
= bb1
->end
; insn
!= bb2
->head
&& count
>= 0;
1218 insn
= NEXT_INSN (insn
))
1219 if (GET_CODE (insn
) == NOTE
)
1221 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
1223 else if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
)
1230 /* Split a (typically critical) edge. Return the new block.
1231 Abort on abnormal edges.
1233 ??? The code generally expects to be called on critical edges.
1234 The case of a block ending in an unconditional jump to a
1235 block with multiple predecessors is not handled optimally. */
1238 split_edge (edge_in
)
1245 /* Abnormal edges cannot be split. */
1246 if ((edge_in
->flags
& EDGE_ABNORMAL
) != 0)
1249 /* We are going to place the new block in front of edge destination.
1250 Avoid existence of fallthru predecessors. */
1251 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1255 for (e
= edge_in
->dest
->pred
; e
; e
= e
->pred_next
)
1256 if (e
->flags
& EDGE_FALLTHRU
)
1260 force_nonfallthru (e
);
1263 /* Create the basic block note.
1265 Where we place the note can have a noticeable impact on the generated
1266 code. Consider this cfg:
1276 If we need to insert an insn on the edge from block 0 to block 1,
1277 we want to ensure the instructions we insert are outside of any
1278 loop notes that physically sit between block 0 and block 1. Otherwise
1279 we confuse the loop optimizer into thinking the loop is a phony. */
1281 if (edge_in
->dest
!= EXIT_BLOCK_PTR
1282 && PREV_INSN (edge_in
->dest
->head
)
1283 && GET_CODE (PREV_INSN (edge_in
->dest
->head
)) == NOTE
1284 && (NOTE_LINE_NUMBER (PREV_INSN (edge_in
->dest
->head
))
1285 == NOTE_INSN_LOOP_BEG
)
1286 && !back_edge_of_syntactic_loop_p (edge_in
->dest
, edge_in
->src
))
1287 before
= PREV_INSN (edge_in
->dest
->head
);
1288 else if (edge_in
->dest
!= EXIT_BLOCK_PTR
)
1289 before
= edge_in
->dest
->head
;
1293 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1294 bb
->count
= edge_in
->count
;
1295 bb
->frequency
= EDGE_FREQUENCY (edge_in
);
1297 /* ??? This info is likely going to be out of date very soon. */
1298 if (edge_in
->dest
->global_live_at_start
)
1300 bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1301 bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1302 COPY_REG_SET (bb
->global_live_at_start
,
1303 edge_in
->dest
->global_live_at_start
);
1304 COPY_REG_SET (bb
->global_live_at_end
,
1305 edge_in
->dest
->global_live_at_start
);
1308 edge_out
= make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1310 /* For non-fallthry edges, we must adjust the predecessor's
1311 jump instruction to target our new block. */
1312 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1314 if (!redirect_edge_and_branch (edge_in
, bb
))
1318 redirect_edge_succ (edge_in
, bb
);
1323 /* Queue instructions for insertion on an edge between two basic blocks.
1324 The new instructions and basic blocks (if any) will not appear in the
1325 CFG until commit_edge_insertions is called. */
1328 insert_insn_on_edge (pattern
, e
)
1332 /* We cannot insert instructions on an abnormal critical edge.
1333 It will be easier to find the culprit if we die now. */
1334 if ((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
1337 if (e
->insns
== NULL_RTX
)
1340 push_to_sequence (e
->insns
);
1342 emit_insn (pattern
);
1344 e
->insns
= get_insns ();
1348 /* Update the CFG for the instructions queued on edge E. */
1351 commit_one_edge_insertion (e
, watch_calls
)
1355 rtx before
= NULL_RTX
, after
= NULL_RTX
, insns
, tmp
, last
;
1358 /* Pull the insns off the edge now since the edge might go away. */
1360 e
->insns
= NULL_RTX
;
1362 /* Special case -- avoid inserting code between call and storing
1363 its return value. */
1364 if (watch_calls
&& (e
->flags
& EDGE_FALLTHRU
) && !e
->dest
->pred
->pred_next
1365 && e
->src
!= ENTRY_BLOCK_PTR
1366 && GET_CODE (e
->src
->end
) == CALL_INSN
)
1368 rtx next
= next_nonnote_insn (e
->src
->end
);
1370 after
= e
->dest
->head
;
1371 /* The first insn after the call may be a stack pop, skip it. */
1373 && keep_with_call_p (next
))
1376 next
= next_nonnote_insn (next
);
1380 if (!before
&& !after
)
1382 /* Figure out where to put these things. If the destination has
1383 one predecessor, insert there. Except for the exit block. */
1384 if (e
->dest
->pred
->pred_next
== NULL
&& e
->dest
!= EXIT_BLOCK_PTR
)
1388 /* Get the location correct wrt a code label, and "nice" wrt
1389 a basic block note, and before everything else. */
1391 if (GET_CODE (tmp
) == CODE_LABEL
)
1392 tmp
= NEXT_INSN (tmp
);
1393 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1394 tmp
= NEXT_INSN (tmp
);
1395 if (tmp
== bb
->head
)
1398 after
= PREV_INSN (tmp
);
1400 after
= get_last_insn ();
1403 /* If the source has one successor and the edge is not abnormal,
1404 insert there. Except for the entry block. */
1405 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1406 && e
->src
->succ
->succ_next
== NULL
1407 && e
->src
!= ENTRY_BLOCK_PTR
)
1411 /* It is possible to have a non-simple jump here. Consider a target
1412 where some forms of unconditional jumps clobber a register. This
1413 happens on the fr30 for example.
1415 We know this block has a single successor, so we can just emit
1416 the queued insns before the jump. */
1417 if (GET_CODE (bb
->end
) == JUMP_INSN
)
1418 for (before
= bb
->end
;
1419 GET_CODE (PREV_INSN (before
)) == NOTE
1420 && NOTE_LINE_NUMBER (PREV_INSN (before
)) ==
1421 NOTE_INSN_LOOP_BEG
; before
= PREV_INSN (before
))
1425 /* We'd better be fallthru, or we've lost track of what's what. */
1426 if ((e
->flags
& EDGE_FALLTHRU
) == 0)
1432 /* Otherwise we must split the edge. */
1435 bb
= split_edge (e
);
1440 /* Now that we've found the spot, do the insertion. */
1444 emit_insns_before (insns
, before
);
1445 last
= prev_nonnote_insn (before
);
1448 last
= emit_insns_after (insns
, after
);
1450 if (returnjump_p (last
))
1452 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1453 This is not currently a problem because this only happens
1454 for the (single) epilogue, which already has a fallthru edge
1458 if (e
->dest
!= EXIT_BLOCK_PTR
1459 || e
->succ_next
!= NULL
|| (e
->flags
& EDGE_FALLTHRU
) == 0)
1462 e
->flags
&= ~EDGE_FALLTHRU
;
1463 emit_barrier_after (last
);
1466 delete_insn (before
);
1468 else if (GET_CODE (last
) == JUMP_INSN
)
1471 find_sub_basic_blocks (bb
);
1474 /* Update the CFG for all queued instructions. */
1477 commit_edge_insertions ()
1482 #ifdef ENABLE_CHECKING
1483 verify_flow_info ();
1487 bb
= ENTRY_BLOCK_PTR
;
1492 for (e
= bb
->succ
; e
; e
= next
)
1494 next
= e
->succ_next
;
1496 commit_one_edge_insertion (e
, false);
1499 if (++i
>= n_basic_blocks
)
1501 bb
= BASIC_BLOCK (i
);
1505 /* Update the CFG for all queued instructions, taking special care of inserting
1506 code on edges between call and storing its return value. */
1509 commit_edge_insertions_watch_calls ()
1514 #ifdef ENABLE_CHECKING
1515 verify_flow_info ();
1519 bb
= ENTRY_BLOCK_PTR
;
1524 for (e
= bb
->succ
; e
; e
= next
)
1526 next
= e
->succ_next
;
1528 commit_one_edge_insertion (e
, true);
1531 if (++i
>= n_basic_blocks
)
1533 bb
= BASIC_BLOCK (i
);
1537 /* Print out one basic block with live information at start and end. */
1548 fprintf (outf
, ";; Basic block %d, loop depth %d, count ",
1549 bb
->index
, bb
->loop_depth
);
1550 fprintf (outf
, HOST_WIDEST_INT_PRINT_DEC
, (HOST_WIDEST_INT
) bb
->count
);
1553 fputs (";; Predecessors: ", outf
);
1554 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1555 dump_edge_info (outf
, e
, 0);
1558 fputs (";; Registers live at start:", outf
);
1559 dump_regset (bb
->global_live_at_start
, outf
);
1562 for (insn
= bb
->head
, last
= NEXT_INSN (bb
->end
); insn
!= last
;
1563 insn
= NEXT_INSN (insn
))
1564 print_rtl_single (outf
, insn
);
1566 fputs (";; Registers live at end:", outf
);
1567 dump_regset (bb
->global_live_at_end
, outf
);
1570 fputs (";; Successors: ", outf
);
1571 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1572 dump_edge_info (outf
, e
, 1);
1580 dump_bb (bb
, stderr
);
1587 dump_bb (BASIC_BLOCK (n
), stderr
);
1590 /* Like print_rtl, but also print out live information for the start of each
1594 print_rtl_with_bb (outf
, rtx_first
)
1601 fprintf (outf
, "(nil)\n");
1605 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
1606 int max_uid
= get_max_uid ();
1608 = (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1610 = (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1611 enum bb_state
*in_bb_p
1612 = (enum bb_state
*) xcalloc (max_uid
, sizeof (enum bb_state
));
1614 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1616 basic_block bb
= BASIC_BLOCK (i
);
1619 start
[INSN_UID (bb
->head
)] = bb
;
1620 end
[INSN_UID (bb
->end
)] = bb
;
1621 for (x
= bb
->head
; x
!= NULL_RTX
; x
= NEXT_INSN (x
))
1623 enum bb_state state
= IN_MULTIPLE_BB
;
1625 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
1627 in_bb_p
[INSN_UID (x
)] = state
;
1634 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
1639 if ((bb
= start
[INSN_UID (tmp_rtx
)]) != NULL
)
1641 fprintf (outf
, ";; Start of basic block %d, registers live:",
1643 dump_regset (bb
->global_live_at_start
, outf
);
1647 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
1648 && GET_CODE (tmp_rtx
) != NOTE
1649 && GET_CODE (tmp_rtx
) != BARRIER
)
1650 fprintf (outf
, ";; Insn is not within a basic block\n");
1651 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
1652 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
1654 did_output
= print_rtl_single (outf
, tmp_rtx
);
1656 if ((bb
= end
[INSN_UID (tmp_rtx
)]) != NULL
)
1658 fprintf (outf
, ";; End of basic block %d, registers live:\n",
1660 dump_regset (bb
->global_live_at_end
, outf
);
1673 if (current_function_epilogue_delay_list
!= 0)
1675 fprintf (outf
, "\n;; Insns in epilogue delay list:\n\n");
1676 for (tmp_rtx
= current_function_epilogue_delay_list
; tmp_rtx
!= 0;
1677 tmp_rtx
= XEXP (tmp_rtx
, 1))
1678 print_rtl_single (outf
, XEXP (tmp_rtx
, 0));
1683 update_br_prob_note (bb
)
1687 if (GET_CODE (bb
->end
) != JUMP_INSN
)
1689 note
= find_reg_note (bb
->end
, REG_BR_PROB
, NULL_RTX
);
1690 if (!note
|| INTVAL (XEXP (note
, 0)) == BRANCH_EDGE (bb
)->probability
)
1692 XEXP (note
, 0) = GEN_INT (BRANCH_EDGE (bb
)->probability
);
1695 /* Verify the CFG consistency. This function check some CFG invariants and
1696 aborts when something is wrong. Hope that this function will help to
1697 convert many optimization passes to preserve CFG consistent.
1699 Currently it does following checks:
1701 - test head/end pointers
1702 - overlapping of basic blocks
1703 - edge list correctness
1704 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1705 - tails of basic blocks (ensure that boundary is necessary)
1706 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1707 and NOTE_INSN_BASIC_BLOCK
1708 - check that all insns are in the basic blocks
1709 (except the switch handling code, barriers and notes)
1710 - check that all returns are followed by barriers
1712 In future it can be extended check a lot of other stuff as well
1713 (reachability of basic blocks, life information, etc. etc.). */
1718 const int max_uid
= get_max_uid ();
1719 const rtx rtx_first
= get_insns ();
1720 rtx last_head
= get_last_insn ();
1721 basic_block
*bb_info
, *last_visited
;
1722 size_t *edge_checksum
;
1724 int i
, last_bb_num_seen
, num_bb_notes
, err
= 0;
1725 basic_block bb
, last_bb_seen
;
1727 bb_info
= (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1728 last_visited
= (basic_block
*) xcalloc (n_basic_blocks
+ 2,
1729 sizeof (basic_block
));
1730 edge_checksum
= (size_t *) xcalloc (n_basic_blocks
+ 2, sizeof (size_t));
1732 /* Check bb chain & numbers. */
1733 last_bb_seen
= ENTRY_BLOCK_PTR
;
1734 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
, NULL
, next_bb
)
1736 if (bb
!= EXIT_BLOCK_PTR
1737 && bb
!= BASIC_BLOCK (bb
->index
))
1739 error ("bb %d on wrong place", bb
->index
);
1743 if (bb
->prev_bb
!= last_bb_seen
)
1745 error ("prev_bb of %d should be %d, not %d",
1746 bb
->index
, last_bb_seen
->index
, bb
->prev_bb
->index
);
1750 /* For now, also check that we didn't change the order. */
1751 if (bb
!= EXIT_BLOCK_PTR
&& bb
->index
!= last_bb_seen
->index
+ 1)
1753 error ("Wrong order of blocks %d and %d",
1754 last_bb_seen
->index
, bb
->index
);
1758 if (bb
== EXIT_BLOCK_PTR
&& last_bb_seen
->index
!= n_basic_blocks
- 1)
1760 error ("Only %d of %d blocks in chain",
1761 last_bb_seen
->index
+ 1, n_basic_blocks
);
1768 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1770 basic_block bb
= BASIC_BLOCK (i
);
1771 rtx head
= bb
->head
;
1774 /* Verify the end of the basic block is in the INSN chain. */
1775 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1781 error ("end insn %d for block %d not found in the insn stream",
1782 INSN_UID (end
), bb
->index
);
1786 /* Work backwards from the end to the head of the basic block
1787 to verify the head is in the RTL chain. */
1788 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1790 /* While walking over the insn chain, verify insns appear
1791 in only one basic block and initialize the BB_INFO array
1792 used by other passes. */
1793 if (bb_info
[INSN_UID (x
)] != NULL
)
1795 error ("insn %d is in multiple basic blocks (%d and %d)",
1796 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
1800 bb_info
[INSN_UID (x
)] = bb
;
1807 error ("head insn %d for block %d not found in the insn stream",
1808 INSN_UID (head
), bb
->index
);
1815 /* Now check the basic blocks (boundaries etc.) */
1816 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1818 basic_block bb
= BASIC_BLOCK (i
);
1819 int n_fallthru
= 0, n_eh
= 0, n_call
= 0, n_abnormal
= 0, n_branch
= 0;
1823 if (INSN_P (bb
->end
)
1824 && (note
= find_reg_note (bb
->end
, REG_BR_PROB
, NULL_RTX
))
1825 && bb
->succ
&& bb
->succ
->succ_next
1826 && any_condjump_p (bb
->end
))
1828 if (INTVAL (XEXP (note
, 0)) != BRANCH_EDGE (bb
)->probability
)
1830 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
1831 INTVAL (XEXP (note
, 0)), BRANCH_EDGE (bb
)->probability
);
1837 error ("verify_flow_info: Wrong count of block %i %i",
1838 bb
->index
, (int)bb
->count
);
1841 if (bb
->frequency
< 0)
1843 error ("verify_flow_info: Wrong frequency of block %i %i",
1844 bb
->index
, bb
->frequency
);
1847 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1849 if (last_visited
[e
->dest
->index
+ 2] == bb
)
1851 error ("verify_flow_info: Duplicate edge %i->%i",
1852 e
->src
->index
, e
->dest
->index
);
1855 if (e
->probability
< 0 || e
->probability
> REG_BR_PROB_BASE
)
1857 error ("verify_flow_info: Wrong probability of edge %i->%i %i",
1858 e
->src
->index
, e
->dest
->index
, e
->probability
);
1863 error ("verify_flow_info: Wrong count of edge %i->%i %i",
1864 e
->src
->index
, e
->dest
->index
, (int)e
->count
);
1868 last_visited
[e
->dest
->index
+ 2] = bb
;
1870 if (e
->flags
& EDGE_FALLTHRU
)
1873 if ((e
->flags
& ~EDGE_DFS_BACK
) == 0)
1876 if (e
->flags
& EDGE_ABNORMAL_CALL
)
1879 if (e
->flags
& EDGE_EH
)
1881 else if (e
->flags
& EDGE_ABNORMAL
)
1884 if ((e
->flags
& EDGE_FALLTHRU
)
1885 && e
->src
!= ENTRY_BLOCK_PTR
1886 && e
->dest
!= EXIT_BLOCK_PTR
)
1890 if (e
->src
->next_bb
!= e
->dest
)
1893 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
1894 e
->src
->index
, e
->dest
->index
);
1898 for (insn
= NEXT_INSN (e
->src
->end
); insn
!= e
->dest
->head
;
1899 insn
= NEXT_INSN (insn
))
1900 if (GET_CODE (insn
) == BARRIER
1901 #ifndef CASE_DROPS_THROUGH
1904 || (INSN_P (insn
) && ! JUMP_TABLE_DATA_P (insn
))
1908 error ("verify_flow_info: Incorrect fallthru %i->%i",
1909 e
->src
->index
, e
->dest
->index
);
1910 fatal_insn ("wrong insn in the fallthru edge", insn
);
1917 error ("verify_flow_info: Basic block %d succ edge is corrupted",
1919 fprintf (stderr
, "Predecessor: ");
1920 dump_edge_info (stderr
, e
, 0);
1921 fprintf (stderr
, "\nSuccessor: ");
1922 dump_edge_info (stderr
, e
, 1);
1923 fprintf (stderr
, "\n");
1927 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
1930 if (n_eh
&& GET_CODE (PATTERN (bb
->end
)) != RESX
1931 && !find_reg_note (bb
->end
, REG_EH_REGION
, NULL_RTX
))
1933 error ("Missing REG_EH_REGION note in the end of bb %i", bb
->index
);
1937 && (GET_CODE (bb
->end
) != JUMP_INSN
1938 || (n_branch
> 1 && (any_uncondjump_p (bb
->end
)
1939 || any_condjump_p (bb
->end
)))))
1941 error ("Too many outgoing branch edges from bb %i", bb
->index
);
1944 if (n_fallthru
&& any_uncondjump_p (bb
->end
))
1946 error ("Fallthru edge after unconditional jump %i", bb
->index
);
1949 if (n_branch
!= 1 && any_uncondjump_p (bb
->end
))
1951 error ("Wrong amount of branch edges after unconditional jump %i", bb
->index
);
1954 if (n_branch
!= 1 && any_condjump_p (bb
->end
)
1955 && JUMP_LABEL (bb
->end
) != bb
->next_bb
->head
)
1957 error ("Wrong amount of branch edges after conditional jump %i", bb
->index
);
1960 if (n_call
&& GET_CODE (bb
->end
) != CALL_INSN
)
1962 error ("Call edges for non-call insn in bb %i", bb
->index
);
1966 && (GET_CODE (bb
->end
) != CALL_INSN
&& n_call
!= n_abnormal
)
1967 && (GET_CODE (bb
->end
) != JUMP_INSN
1968 || any_condjump_p (bb
->end
)
1969 || any_uncondjump_p (bb
->end
)))
1971 error ("Abnormal edges for no purpose in bb %i", bb
->index
);
1979 /* Ensure existence of barrier in BB with no fallthru edges. */
1980 for (insn
= bb
->end
; !insn
|| GET_CODE (insn
) != BARRIER
;
1981 insn
= NEXT_INSN (insn
))
1983 || (GET_CODE (insn
) == NOTE
1984 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BASIC_BLOCK
))
1986 error ("missing barrier after block %i", bb
->index
);
1992 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1996 error ("basic block %d pred edge is corrupted", bb
->index
);
1997 fputs ("Predecessor: ", stderr
);
1998 dump_edge_info (stderr
, e
, 0);
1999 fputs ("\nSuccessor: ", stderr
);
2000 dump_edge_info (stderr
, e
, 1);
2001 fputc ('\n', stderr
);
2004 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
2007 for (x
= bb
->head
; x
!= NEXT_INSN (bb
->end
); x
= NEXT_INSN (x
))
2008 if (basic_block_for_insn
&& BLOCK_FOR_INSN (x
) != bb
)
2011 if (! BLOCK_FOR_INSN (x
))
2013 ("insn %d inside basic block %d but block_for_insn is NULL",
2014 INSN_UID (x
), bb
->index
);
2017 ("insn %d inside basic block %d but block_for_insn is %i",
2018 INSN_UID (x
), bb
->index
, BLOCK_FOR_INSN (x
)->index
);
2023 /* OK pointers are correct. Now check the header of basic
2024 block. It ought to contain optional CODE_LABEL followed
2025 by NOTE_BASIC_BLOCK. */
2027 if (GET_CODE (x
) == CODE_LABEL
)
2031 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2039 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2041 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2047 /* Do checks for empty blocks her. e */
2050 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2052 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2054 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2055 INSN_UID (x
), bb
->index
);
2062 if (GET_CODE (x
) == JUMP_INSN
2063 || GET_CODE (x
) == CODE_LABEL
2064 || GET_CODE (x
) == BARRIER
)
2066 error ("in basic block %d:", bb
->index
);
2067 fatal_insn ("flow control insn inside a basic block", x
);
2072 /* Complete edge checksumming for ENTRY and EXIT. */
2076 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
2077 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
2079 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
2080 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
2083 for (i
= -2; i
< n_basic_blocks
; ++i
)
2084 if (edge_checksum
[i
+ 2])
2086 error ("basic block %i edge lists are corrupted", i
);
2090 last_bb_num_seen
= -1;
2092 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2094 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2096 basic_block bb
= NOTE_BASIC_BLOCK (x
);
2099 if (bb
->index
!= last_bb_num_seen
+ 1)
2100 internal_error ("basic blocks not numbered consecutively");
2102 last_bb_num_seen
= bb
->index
;
2105 if (!bb_info
[INSN_UID (x
)])
2107 switch (GET_CODE (x
))
2114 /* An addr_vec is placed outside any block block. */
2116 && GET_CODE (NEXT_INSN (x
)) == JUMP_INSN
2117 && (GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_DIFF_VEC
2118 || GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_VEC
))
2121 /* But in any case, non-deletable labels can appear anywhere. */
2125 fatal_insn ("insn outside basic block", x
);
2130 && GET_CODE (x
) == JUMP_INSN
2131 && returnjump_p (x
) && ! condjump_p (x
)
2132 && ! (NEXT_INSN (x
) && GET_CODE (NEXT_INSN (x
)) == BARRIER
))
2133 fatal_insn ("return not followed by barrier", x
);
2136 if (num_bb_notes
!= n_basic_blocks
)
2138 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2139 num_bb_notes
, n_basic_blocks
);
2142 internal_error ("verify_flow_info failed");
2146 free (last_visited
);
2147 free (edge_checksum
);
2150 /* Assume that the preceding pass has possibly eliminated jump instructions
2151 or converted the unconditional jumps. Eliminate the edges from CFG.
2152 Return true if any edges are eliminated. */
2155 purge_dead_edges (bb
)
2159 rtx insn
= bb
->end
, note
;
2160 bool purged
= false;
2162 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2163 if (GET_CODE (insn
) == INSN
2164 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
2168 if (! may_trap_p (PATTERN (insn
))
2169 || ((eqnote
= find_reg_equal_equiv_note (insn
))
2170 && ! may_trap_p (XEXP (eqnote
, 0))))
2171 remove_note (insn
, note
);
2174 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
2175 for (e
= bb
->succ
; e
; e
= next
)
2177 next
= e
->succ_next
;
2178 if (e
->flags
& EDGE_EH
)
2180 if (can_throw_internal (bb
->end
))
2183 else if (e
->flags
& EDGE_ABNORMAL_CALL
)
2185 if (GET_CODE (bb
->end
) == CALL_INSN
2186 && (! (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
))
2187 || INTVAL (XEXP (note
, 0)) >= 0))
2194 bb
->flags
|= BB_DIRTY
;
2198 if (GET_CODE (insn
) == JUMP_INSN
)
2203 /* We do care only about conditional jumps and simplejumps. */
2204 if (!any_condjump_p (insn
)
2205 && !returnjump_p (insn
)
2206 && !simplejump_p (insn
))
2209 /* Branch probability/prediction notes are defined only for
2210 condjumps. We've possibly turned condjump into simplejump. */
2211 if (simplejump_p (insn
))
2213 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2215 remove_note (insn
, note
);
2216 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
2217 remove_note (insn
, note
);
2220 for (e
= bb
->succ
; e
; e
= next
)
2222 next
= e
->succ_next
;
2224 /* Avoid abnormal flags to leak from computed jumps turned
2225 into simplejumps. */
2227 e
->flags
&= ~EDGE_ABNORMAL
;
2229 /* See if this edge is one we should keep. */
2230 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
2231 /* A conditional jump can fall through into the next
2232 block, so we should keep the edge. */
2234 else if (e
->dest
!= EXIT_BLOCK_PTR
2235 && e
->dest
->head
== JUMP_LABEL (insn
))
2236 /* If the destination block is the target of the jump,
2239 else if (e
->dest
== EXIT_BLOCK_PTR
&& returnjump_p (insn
))
2240 /* If the destination block is the exit block, and this
2241 instruction is a return, then keep the edge. */
2243 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
2244 /* Keep the edges that correspond to exceptions thrown by
2245 this instruction. */
2248 /* We do not need this edge. */
2249 bb
->flags
|= BB_DIRTY
;
2254 if (!bb
->succ
|| !purged
)
2258 fprintf (rtl_dump_file
, "Purged edges from bb %i\n", bb
->index
);
2263 /* Redistribute probabilities. */
2264 if (!bb
->succ
->succ_next
)
2266 bb
->succ
->probability
= REG_BR_PROB_BASE
;
2267 bb
->succ
->count
= bb
->count
;
2271 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2275 b
= BRANCH_EDGE (bb
);
2276 f
= FALLTHRU_EDGE (bb
);
2277 b
->probability
= INTVAL (XEXP (note
, 0));
2278 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
2279 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
2280 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
2286 /* If we don't see a jump insn, we don't know exactly why the block would
2287 have been broken at this point. Look for a simple, non-fallthru edge,
2288 as these are only created by conditional branches. If we find such an
2289 edge we know that there used to be a jump here and can then safely
2290 remove all non-fallthru edges. */
2291 for (e
= bb
->succ
; e
&& (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
));
2298 for (e
= bb
->succ
; e
; e
= next
)
2300 next
= e
->succ_next
;
2301 if (!(e
->flags
& EDGE_FALLTHRU
))
2303 bb
->flags
|= BB_DIRTY
;
2309 if (!bb
->succ
|| bb
->succ
->succ_next
)
2312 bb
->succ
->probability
= REG_BR_PROB_BASE
;
2313 bb
->succ
->count
= bb
->count
;
2316 fprintf (rtl_dump_file
, "Purged non-fallthru edges from bb %i\n",
2321 /* Search all basic blocks for potentially dead edges and purge them. Return
2322 true if some edge has been eliminated. */
2325 purge_all_dead_edges (update_life_p
)
2328 int i
, purged
= false;
2333 blocks
= sbitmap_alloc (n_basic_blocks
);
2334 sbitmap_zero (blocks
);
2337 for (i
= 0; i
< n_basic_blocks
; i
++)
2339 bool purged_here
= purge_dead_edges (BASIC_BLOCK (i
));
2341 purged
|= purged_here
;
2342 if (purged_here
&& update_life_p
)
2343 SET_BIT (blocks
, i
);
2346 if (update_life_p
&& purged
)
2347 update_life_info (blocks
, UPDATE_LIFE_GLOBAL
,
2348 PROP_DEATH_NOTES
| PROP_SCAN_DEAD_CODE
2349 | PROP_KILL_DEAD_CODE
);
2352 sbitmap_free (blocks
);