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 committing 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 */
47 #include "coretypes.h"
51 #include "hard-reg-set.h"
52 #include "basic-block.h"
61 #include "insn-config.h"
63 /* Stubs in case we don't have a return insn. */
66 #define gen_return() NULL_RTX
69 /* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */
70 /* ??? Should probably be using LABEL_NUSES instead. It would take a
71 bit of surgery to be able to use or co-opt the routines in jump. */
73 rtx tail_recursion_label_list
;
75 static int can_delete_note_p
PARAMS ((rtx
));
76 static int can_delete_label_p
PARAMS ((rtx
));
77 static void commit_one_edge_insertion
PARAMS ((edge
, int));
78 static bool try_redirect_by_replacing_jump
PARAMS ((edge
, basic_block
));
79 static rtx last_loop_beg_note
PARAMS ((rtx
));
80 static bool back_edge_of_syntactic_loop_p
PARAMS ((basic_block
, basic_block
));
81 basic_block force_nonfallthru_and_redirect
PARAMS ((edge
, basic_block
));
83 /* Return true if NOTE is not one of the ones that must be kept paired,
84 so that we may simply delete it. */
87 can_delete_note_p (note
)
90 return (NOTE_LINE_NUMBER (note
) == NOTE_INSN_DELETED
91 || NOTE_LINE_NUMBER (note
) == NOTE_INSN_BASIC_BLOCK
92 || NOTE_LINE_NUMBER (note
) == NOTE_INSN_PREDICTION
);
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
));
108 /* Delete INSN by patching it out. Return the next insn. */
114 rtx next
= NEXT_INSN (insn
);
116 bool really_delete
= true;
118 if (GET_CODE (insn
) == CODE_LABEL
)
120 /* Some labels can't be directly removed from the INSN chain, as they
121 might be references via variables, constant pool etc.
122 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
123 if (! can_delete_label_p (insn
))
125 const char *name
= LABEL_NAME (insn
);
127 really_delete
= false;
128 PUT_CODE (insn
, NOTE
);
129 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED_LABEL
;
130 NOTE_SOURCE_FILE (insn
) = name
;
133 remove_node_from_expr_list (insn
, &nonlocal_goto_handler_labels
);
138 /* If this insn has already been deleted, something is very wrong. */
139 if (INSN_DELETED_P (insn
))
142 INSN_DELETED_P (insn
) = 1;
145 /* If deleting a jump, decrement the use count of the label. Deleting
146 the label itself should happen in the normal course of block merging. */
147 if (GET_CODE (insn
) == JUMP_INSN
149 && GET_CODE (JUMP_LABEL (insn
)) == CODE_LABEL
)
150 LABEL_NUSES (JUMP_LABEL (insn
))--;
152 /* Also if deleting an insn that references a label. */
153 else if ((note
= find_reg_note (insn
, REG_LABEL
, NULL_RTX
)) != NULL_RTX
154 && GET_CODE (XEXP (note
, 0)) == CODE_LABEL
)
155 LABEL_NUSES (XEXP (note
, 0))--;
157 if (GET_CODE (insn
) == JUMP_INSN
158 && (GET_CODE (PATTERN (insn
)) == ADDR_VEC
159 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
))
161 rtx pat
= PATTERN (insn
);
162 int diff_vec_p
= GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
;
163 int len
= XVECLEN (pat
, diff_vec_p
);
166 for (i
= 0; i
< len
; i
++)
168 rtx label
= XEXP (XVECEXP (pat
, diff_vec_p
, i
), 0);
170 /* When deleting code in bulk (e.g. removing many unreachable
171 blocks) we can delete a label that's a target of the vector
172 before deleting the vector itself. */
173 if (GET_CODE (label
) != NOTE
)
174 LABEL_NUSES (label
)--;
181 /* Like delete_insn but also purge dead edges from BB. */
183 delete_insn_and_edges (insn
)
190 && BLOCK_FOR_INSN (insn
)
191 && BLOCK_FOR_INSN (insn
)->end
== insn
)
193 x
= delete_insn (insn
);
195 purge_dead_edges (BLOCK_FOR_INSN (insn
));
199 /* Unlink a chain of insns between START and FINISH, leaving notes
200 that must be paired. */
203 delete_insn_chain (start
, finish
)
208 /* Unchain the insns one by one. It would be quicker to delete all of these
209 with a single unchaining, rather than one at a time, but we need to keep
213 next
= NEXT_INSN (start
);
214 if (GET_CODE (start
) == NOTE
&& !can_delete_note_p (start
))
217 next
= delete_insn (start
);
225 /* Like delete_insn but also purge dead edges from BB. */
227 delete_insn_chain_and_edges (first
, last
)
233 && BLOCK_FOR_INSN (last
)
234 && BLOCK_FOR_INSN (last
)->end
== last
)
236 delete_insn_chain (first
, last
);
238 purge_dead_edges (BLOCK_FOR_INSN (last
));
241 /* Create a new basic block consisting of the instructions between HEAD and END
242 inclusive. This function is designed to allow fast BB construction - reuses
243 the note and basic block struct in BB_NOTE, if any and do not grow
244 BASIC_BLOCK chain and should be used directly only by CFG construction code.
245 END can be NULL in to create new empty basic block before HEAD. Both END
246 and HEAD can be NULL to create basic block at the end of INSN chain.
247 AFTER is the basic block we should be put after. */
250 create_basic_block_structure (head
, end
, bb_note
, after
)
251 rtx head
, end
, bb_note
;
257 && ! RTX_INTEGRATED_P (bb_note
)
258 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
261 /* If we found an existing note, thread it back onto the chain. */
265 if (GET_CODE (head
) == CODE_LABEL
)
269 after
= PREV_INSN (head
);
273 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
274 reorder_insns_nobb (bb_note
, bb_note
, after
);
278 /* Otherwise we must create a note and a basic block structure. */
284 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
285 else if (GET_CODE (head
) == CODE_LABEL
&& end
)
287 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
293 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
299 NOTE_BASIC_BLOCK (bb_note
) = bb
;
302 /* Always include the bb note in the block. */
303 if (NEXT_INSN (end
) == bb_note
)
308 bb
->index
= last_basic_block
++;
310 link_block (bb
, after
);
311 BASIC_BLOCK (bb
->index
) = bb
;
312 update_bb_for_insn (bb
);
314 /* Tag the block so that we know it has been used when considering
315 other basic block notes. */
321 /* Create new basic block consisting of instructions in between HEAD and END
322 and place it to the BB chain after block AFTER. END can be NULL in to
323 create new empty basic block before HEAD. Both END and HEAD can be NULL to
324 create basic block at the end of INSN chain. */
327 create_basic_block (head
, end
, after
)
333 /* Place the new block just after the end. */
334 VARRAY_GROW (basic_block_info
, last_basic_block
+1);
338 bb
= create_basic_block_structure (head
, end
, NULL
, after
);
343 /* Delete the insns in a (non-live) block. We physically delete every
344 non-deleted-note insn, and update the flow graph appropriately.
346 Return nonzero if we deleted an exception handler. */
348 /* ??? Preserving all such notes strikes me as wrong. It would be nice
349 to post-process the stream to remove empty blocks, loops, ranges, etc. */
352 flow_delete_block_noexpunge (b
)
355 int deleted_handler
= 0;
358 /* If the head of this block is a CODE_LABEL, then it might be the
359 label for an exception handler which can't be reached.
361 We need to remove the label from the exception_handler_label list
362 and remove the associated NOTE_INSN_EH_REGION_BEG and
363 NOTE_INSN_EH_REGION_END notes. */
365 /* Get rid of all NOTE_INSN_PREDICTIONs and NOTE_INSN_LOOP_CONTs
366 hanging before the block. */
368 for (insn
= PREV_INSN (b
->head
); insn
; insn
= PREV_INSN (insn
))
370 if (GET_CODE (insn
) != NOTE
)
372 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_PREDICTION
373 || NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_CONT
)
374 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
379 never_reached_warning (insn
, b
->end
);
381 if (GET_CODE (insn
) == CODE_LABEL
)
382 maybe_remove_eh_handler (insn
);
384 /* Include any jump table following the basic block. */
386 if (tablejump_p (end
, NULL
, &tmp
))
389 /* Include any barrier that may follow the basic block. */
390 tmp
= next_nonnote_insn (end
);
391 if (tmp
&& GET_CODE (tmp
) == BARRIER
)
394 /* Selectively delete the entire chain. */
396 delete_insn_chain (insn
, end
);
398 /* Remove the edges into and out of this block. Note that there may
399 indeed be edges in, if we are removing an unreachable loop. */
400 while (b
->pred
!= NULL
)
401 remove_edge (b
->pred
);
402 while (b
->succ
!= NULL
)
403 remove_edge (b
->succ
);
408 return deleted_handler
;
412 flow_delete_block (b
)
415 int deleted_handler
= flow_delete_block_noexpunge (b
);
417 /* Remove the basic block from the array. */
420 return deleted_handler
;
423 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
426 compute_bb_for_insn ()
435 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
437 BLOCK_FOR_INSN (insn
) = bb
;
444 /* Release the basic_block_for_insn array. */
450 for (insn
= get_insns (); insn
; insn
= NEXT_INSN (insn
))
451 if (GET_CODE (insn
) != BARRIER
)
452 BLOCK_FOR_INSN (insn
) = NULL
;
455 /* Update insns block within BB. */
458 update_bb_for_insn (bb
)
463 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
465 if (GET_CODE (insn
) != BARRIER
)
466 set_block_for_insn (insn
, bb
);
472 /* Split a block BB after insn INSN creating a new fallthru edge.
473 Return the new edge. Note that to keep other parts of the compiler happy,
474 this function renumbers all the basic blocks so that the new
475 one has a number one greater than the block split. */
478 split_block (bb
, insn
)
486 /* There is no point splitting the block after its end. */
490 /* Create the new basic block. */
491 new_bb
= create_basic_block (NEXT_INSN (insn
), bb
->end
, bb
);
492 new_bb
->count
= bb
->count
;
493 new_bb
->frequency
= bb
->frequency
;
494 new_bb
->loop_depth
= bb
->loop_depth
;
497 /* Redirect the outgoing edges. */
498 new_bb
->succ
= bb
->succ
;
500 for (e
= new_bb
->succ
; e
; e
= e
->succ_next
)
503 new_edge
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
505 if (bb
->global_live_at_start
)
507 new_bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
508 new_bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
509 COPY_REG_SET (new_bb
->global_live_at_end
, bb
->global_live_at_end
);
511 /* We now have to calculate which registers are live at the end
512 of the split basic block and at the start of the new basic
513 block. Start with those registers that are known to be live
514 at the end of the original basic block and get
515 propagate_block to determine which registers are live. */
516 COPY_REG_SET (new_bb
->global_live_at_start
, bb
->global_live_at_end
);
517 propagate_block (new_bb
, new_bb
->global_live_at_start
, NULL
, NULL
, 0);
518 COPY_REG_SET (bb
->global_live_at_end
,
519 new_bb
->global_live_at_start
);
520 #ifdef HAVE_conditional_execution
521 /* In the presence of conditional execution we are not able to update
522 liveness precisely. */
523 if (reload_completed
)
525 bb
->flags
|= BB_DIRTY
;
526 new_bb
->flags
|= BB_DIRTY
;
534 /* Blocks A and B are to be merged into a single block A. The insns
535 are already contiguous, hence `nomove'. */
538 merge_blocks_nomove (a
, b
)
541 rtx b_head
= b
->head
, b_end
= b
->end
, a_end
= a
->end
;
542 rtx del_first
= NULL_RTX
, del_last
= NULL_RTX
;
546 /* If there was a CODE_LABEL beginning B, delete it. */
547 if (GET_CODE (b_head
) == CODE_LABEL
)
549 /* Detect basic blocks with nothing but a label. This can happen
550 in particular at the end of a function. */
554 del_first
= del_last
= b_head
;
555 b_head
= NEXT_INSN (b_head
);
558 /* Delete the basic block note and handle blocks containing just that
560 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
568 b_head
= NEXT_INSN (b_head
);
571 /* If there was a jump out of A, delete it. */
572 if (GET_CODE (a_end
) == JUMP_INSN
)
576 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
577 if (GET_CODE (prev
) != NOTE
578 || NOTE_LINE_NUMBER (prev
) == NOTE_INSN_BASIC_BLOCK
585 /* If this was a conditional jump, we need to also delete
586 the insn that set cc0. */
587 if (only_sets_cc0_p (prev
))
591 prev
= prev_nonnote_insn (prev
);
598 a_end
= PREV_INSN (del_first
);
600 else if (GET_CODE (NEXT_INSN (a_end
)) == BARRIER
)
601 del_first
= NEXT_INSN (a_end
);
603 /* Normally there should only be one successor of A and that is B, but
604 partway though the merge of blocks for conditional_execution we'll
605 be merging a TEST block with THEN and ELSE successors. Free the
606 whole lot of them and hope the caller knows what they're doing. */
608 remove_edge (a
->succ
);
610 /* Adjust the edges out of B for the new owner. */
611 for (e
= b
->succ
; e
; e
= e
->succ_next
)
614 a
->flags
|= b
->flags
;
616 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
617 b
->pred
= b
->succ
= NULL
;
618 a
->global_live_at_end
= b
->global_live_at_end
;
622 /* Delete everything marked above as well as crap that might be
623 hanging out between the two blocks. */
624 delete_insn_chain (del_first
, del_last
);
626 /* Reassociate the insns of B with A. */
631 for (x
= a_end
; x
!= b_end
; x
= NEXT_INSN (x
))
632 set_block_for_insn (x
, a
);
634 set_block_for_insn (b_end
, a
);
642 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
649 if (block
== EXIT_BLOCK_PTR
)
652 if (GET_CODE (block
->head
) != CODE_LABEL
)
654 block
->head
= emit_label_before (gen_label_rtx (), block
->head
);
660 /* Attempt to perform edge redirection by replacing possibly complex jump
661 instruction by unconditional jump or removing jump completely. This can
662 apply only if all edges now point to the same block. The parameters and
663 return values are equivalent to redirect_edge_and_branch. */
666 try_redirect_by_replacing_jump (e
, target
)
670 basic_block src
= e
->src
;
671 rtx insn
= src
->end
, kill_from
;
676 /* Verify that all targets will be TARGET. */
677 for (tmp
= src
->succ
; tmp
; tmp
= tmp
->succ_next
)
678 if (tmp
->dest
!= target
&& tmp
!= e
)
681 if (tmp
|| !onlyjump_p (insn
))
683 if ((!optimize
|| flow2_completed
) && tablejump_p (insn
, NULL
, NULL
))
686 /* Avoid removing branch with side effects. */
687 set
= single_set (insn
);
688 if (!set
|| side_effects_p (set
))
691 /* In case we zap a conditional jump, we'll need to kill
692 the cc0 setter too. */
695 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
)))
696 kill_from
= PREV_INSN (insn
);
699 /* See if we can create the fallthru edge. */
700 if (can_fallthru (src
, target
))
703 fprintf (rtl_dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
706 /* Selectively unlink whole insn chain. */
707 delete_insn_chain (kill_from
, PREV_INSN (target
->head
));
710 /* If this already is simplejump, redirect it. */
711 else if (simplejump_p (insn
))
713 if (e
->dest
== target
)
716 fprintf (rtl_dump_file
, "Redirecting jump %i from %i to %i.\n",
717 INSN_UID (insn
), e
->dest
->index
, target
->index
);
718 if (!redirect_jump (insn
, block_label (target
), 0))
720 if (target
== EXIT_BLOCK_PTR
)
726 /* Cannot do anything for target exit block. */
727 else if (target
== EXIT_BLOCK_PTR
)
730 /* Or replace possibly complicated jump insn by simple jump insn. */
733 rtx target_label
= block_label (target
);
734 rtx barrier
, label
, table
;
736 emit_jump_insn_after (gen_jump (target_label
), insn
);
737 JUMP_LABEL (src
->end
) = target_label
;
738 LABEL_NUSES (target_label
)++;
740 fprintf (rtl_dump_file
, "Replacing insn %i by jump %i\n",
741 INSN_UID (insn
), INSN_UID (src
->end
));
744 delete_insn_chain (kill_from
, insn
);
746 /* Recognize a tablejump that we are converting to a
747 simple jump and remove its associated CODE_LABEL
748 and ADDR_VEC or ADDR_DIFF_VEC. */
749 if (tablejump_p (insn
, &label
, &table
))
750 delete_insn_chain (label
, table
);
752 barrier
= next_nonnote_insn (src
->end
);
753 if (!barrier
|| GET_CODE (barrier
) != BARRIER
)
754 emit_barrier_after (src
->end
);
757 /* Keep only one edge out and set proper flags. */
758 while (src
->succ
->succ_next
)
759 remove_edge (src
->succ
);
762 e
->flags
= EDGE_FALLTHRU
;
766 e
->probability
= REG_BR_PROB_BASE
;
767 e
->count
= src
->count
;
769 /* We don't want a block to end on a line-number note since that has
770 the potential of changing the code between -g and not -g. */
771 while (GET_CODE (e
->src
->end
) == NOTE
772 && NOTE_LINE_NUMBER (e
->src
->end
) >= 0)
773 delete_insn (e
->src
->end
);
775 if (e
->dest
!= target
)
776 redirect_edge_succ (e
, target
);
781 /* Return last loop_beg note appearing after INSN, before start of next
782 basic block. Return INSN if there are no such notes.
784 When emitting jump to redirect a fallthru edge, it should always appear
785 after the LOOP_BEG notes, as loop optimizer expect loop to either start by
786 fallthru edge or jump following the LOOP_BEG note jumping to the loop exit
790 last_loop_beg_note (insn
)
795 for (insn
= NEXT_INSN (insn
); insn
&& GET_CODE (insn
) == NOTE
796 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
;
797 insn
= NEXT_INSN (insn
))
798 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
804 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
805 expense of adding new instructions or reordering basic blocks.
807 Function can be also called with edge destination equivalent to the TARGET.
808 Then it should try the simplifications and do nothing if none is possible.
810 Return true if transformation succeeded. We still return false in case E
811 already destinated TARGET and we didn't managed to simplify instruction
815 redirect_edge_and_branch (e
, target
)
820 rtx old_label
= e
->dest
->head
;
821 basic_block src
= e
->src
;
824 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
827 if (try_redirect_by_replacing_jump (e
, target
))
830 /* Do this fast path late, as we want above code to simplify for cases
831 where called on single edge leaving basic block containing nontrivial
833 else if (e
->dest
== target
)
836 /* We can only redirect non-fallthru edges of jump insn. */
837 if (e
->flags
& EDGE_FALLTHRU
)
839 else if (GET_CODE (insn
) != JUMP_INSN
)
842 /* Recognize a tablejump and adjust all matching cases. */
843 if (tablejump_p (insn
, NULL
, &tmp
))
847 rtx new_label
= block_label (target
);
849 if (target
== EXIT_BLOCK_PTR
)
851 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
852 vec
= XVEC (PATTERN (tmp
), 0);
854 vec
= XVEC (PATTERN (tmp
), 1);
856 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
857 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
859 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
860 --LABEL_NUSES (old_label
);
861 ++LABEL_NUSES (new_label
);
864 /* Handle casesi dispatch insns */
865 if ((tmp
= single_set (insn
)) != NULL
866 && SET_DEST (tmp
) == pc_rtx
867 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
868 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
869 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
871 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (VOIDmode
,
873 --LABEL_NUSES (old_label
);
874 ++LABEL_NUSES (new_label
);
879 /* ?? We may play the games with moving the named labels from
880 one basic block to the other in case only one computed_jump is
882 if (computed_jump_p (insn
)
883 /* A return instruction can't be redirected. */
884 || returnjump_p (insn
))
887 /* If the insn doesn't go where we think, we're confused. */
888 if (JUMP_LABEL (insn
) != old_label
)
891 /* If the substitution doesn't succeed, die. This can happen
892 if the back end emitted unrecognizable instructions or if
893 target is exit block on some arches. */
894 if (!redirect_jump (insn
, block_label (target
), 0))
896 if (target
== EXIT_BLOCK_PTR
)
903 fprintf (rtl_dump_file
, "Edge %i->%i redirected to %i\n",
904 e
->src
->index
, e
->dest
->index
, target
->index
);
906 if (e
->dest
!= target
)
907 redirect_edge_succ_nodup (e
, target
);
912 /* Like force_nonfallthru below, but additionally performs redirection
913 Used by redirect_edge_and_branch_force. */
916 force_nonfallthru_and_redirect (e
, target
)
920 basic_block jump_block
, new_bb
= NULL
, src
= e
->src
;
923 int abnormal_edge_flags
= 0;
925 /* In the case the last instruction is conditional jump to the next
926 instruction, first redirect the jump itself and then continue
927 by creating an basic block afterwards to redirect fallthru edge. */
928 if (e
->src
!= ENTRY_BLOCK_PTR
&& e
->dest
!= EXIT_BLOCK_PTR
929 && any_condjump_p (e
->src
->end
)
930 /* When called from cfglayout, fallthru edges do not
931 neccessarily go to the next block. */
932 && e
->src
->next_bb
== e
->dest
933 && JUMP_LABEL (e
->src
->end
) == e
->dest
->head
)
936 edge b
= make_edge (e
->src
, target
, 0);
938 if (!redirect_jump (e
->src
->end
, block_label (target
), 0))
940 note
= find_reg_note (e
->src
->end
, REG_BR_PROB
, NULL_RTX
);
943 int prob
= INTVAL (XEXP (note
, 0));
945 b
->probability
= prob
;
946 b
->count
= e
->count
* prob
/ REG_BR_PROB_BASE
;
947 e
->probability
-= e
->probability
;
948 e
->count
-= b
->count
;
949 if (e
->probability
< 0)
956 if (e
->flags
& EDGE_ABNORMAL
)
958 /* Irritating special case - fallthru edge to the same block as abnormal
960 We can't redirect abnormal edge, but we still can split the fallthru
961 one and create separate abnormal edge to original destination.
962 This allows bb-reorder to make such edge non-fallthru. */
963 if (e
->dest
!= target
)
965 abnormal_edge_flags
= e
->flags
& ~(EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
);
966 e
->flags
&= EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
;
968 else if (!(e
->flags
& EDGE_FALLTHRU
))
970 else if (e
->src
== ENTRY_BLOCK_PTR
)
972 /* We can't redirect the entry block. Create an empty block at the
973 start of the function which we use to add the new jump. */
975 basic_block bb
= create_basic_block (e
->dest
->head
, NULL
, ENTRY_BLOCK_PTR
);
977 /* Change the existing edge's source to be the new block, and add
978 a new edge from the entry block to the new block. */
980 for (pe1
= &ENTRY_BLOCK_PTR
->succ
; *pe1
; pe1
= &(*pe1
)->succ_next
)
988 make_single_succ_edge (ENTRY_BLOCK_PTR
, bb
, EDGE_FALLTHRU
);
991 if (e
->src
->succ
->succ_next
|| abnormal_edge_flags
)
993 /* Create the new structures. */
995 /* Position the new block correctly relative to loop notes. */
996 note
= last_loop_beg_note (e
->src
->end
);
997 note
= NEXT_INSN (note
);
999 /* ... and ADDR_VECs. */
1001 && GET_CODE (note
) == CODE_LABEL
1003 && GET_CODE (NEXT_INSN (note
)) == JUMP_INSN
1004 && (GET_CODE (PATTERN (NEXT_INSN (note
))) == ADDR_DIFF_VEC
1005 || GET_CODE (PATTERN (NEXT_INSN (note
))) == ADDR_VEC
))
1006 note
= NEXT_INSN (NEXT_INSN (note
));
1008 jump_block
= create_basic_block (note
, NULL
, e
->src
);
1009 jump_block
->count
= e
->count
;
1010 jump_block
->frequency
= EDGE_FREQUENCY (e
);
1011 jump_block
->loop_depth
= target
->loop_depth
;
1013 if (target
->global_live_at_start
)
1015 jump_block
->global_live_at_start
1016 = OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1017 jump_block
->global_live_at_end
1018 = OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1019 COPY_REG_SET (jump_block
->global_live_at_start
,
1020 target
->global_live_at_start
);
1021 COPY_REG_SET (jump_block
->global_live_at_end
,
1022 target
->global_live_at_start
);
1026 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1027 new_edge
->probability
= e
->probability
;
1028 new_edge
->count
= e
->count
;
1030 /* Redirect old edge. */
1031 redirect_edge_pred (e
, jump_block
);
1032 e
->probability
= REG_BR_PROB_BASE
;
1034 new_bb
= jump_block
;
1037 jump_block
= e
->src
;
1039 e
->flags
&= ~EDGE_FALLTHRU
;
1040 if (target
== EXIT_BLOCK_PTR
)
1043 emit_jump_insn_after (gen_return (), jump_block
->end
);
1049 rtx label
= block_label (target
);
1050 emit_jump_insn_after (gen_jump (label
), jump_block
->end
);
1051 JUMP_LABEL (jump_block
->end
) = label
;
1052 LABEL_NUSES (label
)++;
1055 emit_barrier_after (jump_block
->end
);
1056 redirect_edge_succ_nodup (e
, target
);
1058 if (abnormal_edge_flags
)
1059 make_edge (src
, target
, abnormal_edge_flags
);
1064 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1065 (and possibly create new basic block) to make edge non-fallthru.
1066 Return newly created BB or NULL if none. */
1069 force_nonfallthru (e
)
1072 return force_nonfallthru_and_redirect (e
, e
->dest
);
1075 /* Redirect edge even at the expense of creating new jump insn or
1076 basic block. Return new basic block if created, NULL otherwise.
1077 Abort if conversion is impossible. */
1080 redirect_edge_and_branch_force (e
, target
)
1084 if (redirect_edge_and_branch (e
, target
)
1085 || e
->dest
== target
)
1088 /* In case the edge redirection failed, try to force it to be non-fallthru
1089 and redirect newly created simplejump. */
1090 return force_nonfallthru_and_redirect (e
, target
);
1093 /* The given edge should potentially be a fallthru edge. If that is in
1094 fact true, delete the jump and barriers that are in the way. */
1097 tidy_fallthru_edge (e
, b
, c
)
1103 /* ??? In a late-running flow pass, other folks may have deleted basic
1104 blocks by nopping out blocks, leaving multiple BARRIERs between here
1105 and the target label. They ought to be chastized and fixed.
1107 We can also wind up with a sequence of undeletable labels between
1108 one block and the next.
1110 So search through a sequence of barriers, labels, and notes for
1111 the head of block C and assert that we really do fall through. */
1113 for (q
= NEXT_INSN (b
->end
); q
!= c
->head
; q
= NEXT_INSN (q
))
1117 /* Remove what will soon cease being the jump insn from the source block.
1118 If block B consisted only of this single jump, turn it into a deleted
1121 if (GET_CODE (q
) == JUMP_INSN
1123 && (any_uncondjump_p (q
)
1124 || (b
->succ
== e
&& e
->succ_next
== NULL
)))
1127 /* If this was a conditional jump, we need to also delete
1128 the insn that set cc0. */
1129 if (any_condjump_p (q
) && only_sets_cc0_p (PREV_INSN (q
)))
1135 /* We don't want a block to end on a line-number note since that has
1136 the potential of changing the code between -g and not -g. */
1137 while (GET_CODE (q
) == NOTE
&& NOTE_LINE_NUMBER (q
) >= 0)
1141 /* Selectively unlink the sequence. */
1142 if (q
!= PREV_INSN (c
->head
))
1143 delete_insn_chain (NEXT_INSN (q
), PREV_INSN (c
->head
));
1145 e
->flags
|= EDGE_FALLTHRU
;
1148 /* Fix up edges that now fall through, or rather should now fall through
1149 but previously required a jump around now deleted blocks. Simplify
1150 the search by only examining blocks numerically adjacent, since this
1151 is how find_basic_blocks created them. */
1154 tidy_fallthru_edges ()
1158 if (ENTRY_BLOCK_PTR
->next_bb
== EXIT_BLOCK_PTR
)
1161 FOR_BB_BETWEEN (b
, ENTRY_BLOCK_PTR
->next_bb
, EXIT_BLOCK_PTR
->prev_bb
, next_bb
)
1167 /* We care about simple conditional or unconditional jumps with
1170 If we had a conditional branch to the next instruction when
1171 find_basic_blocks was called, then there will only be one
1172 out edge for the block which ended with the conditional
1173 branch (since we do not create duplicate edges).
1175 Furthermore, the edge will be marked as a fallthru because we
1176 merge the flags for the duplicate edges. So we do not want to
1177 check that the edge is not a FALLTHRU edge. */
1179 if ((s
= b
->succ
) != NULL
1180 && ! (s
->flags
& EDGE_COMPLEX
)
1181 && s
->succ_next
== NULL
1183 /* If the jump insn has side effects, we can't tidy the edge. */
1184 && (GET_CODE (b
->end
) != JUMP_INSN
1185 || onlyjump_p (b
->end
)))
1186 tidy_fallthru_edge (s
, b
, c
);
1190 /* Helper function for split_edge. Return true in case edge BB2 to BB1
1191 is back edge of syntactic loop. */
1194 back_edge_of_syntactic_loop_p (bb1
, bb2
)
1195 basic_block bb1
, bb2
;
1204 /* ??? Could we guarantee that bb indices are monotone, so that we could
1205 just compare them? */
1206 for (bb
= bb1
; bb
&& bb
!= bb2
; bb
= bb
->next_bb
)
1212 for (insn
= bb1
->end
; insn
!= bb2
->head
&& count
>= 0;
1213 insn
= NEXT_INSN (insn
))
1214 if (GET_CODE (insn
) == NOTE
)
1216 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
1218 else if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
)
1225 /* Split a (typically critical) edge. Return the new block.
1226 Abort on abnormal edges.
1228 ??? The code generally expects to be called on critical edges.
1229 The case of a block ending in an unconditional jump to a
1230 block with multiple predecessors is not handled optimally. */
1233 split_edge (edge_in
)
1239 /* Abnormal edges cannot be split. */
1240 if ((edge_in
->flags
& EDGE_ABNORMAL
) != 0)
1243 /* We are going to place the new block in front of edge destination.
1244 Avoid existence of fallthru predecessors. */
1245 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1249 for (e
= edge_in
->dest
->pred
; e
; e
= e
->pred_next
)
1250 if (e
->flags
& EDGE_FALLTHRU
)
1254 force_nonfallthru (e
);
1257 /* Create the basic block note.
1259 Where we place the note can have a noticeable impact on the generated
1260 code. Consider this cfg:
1270 If we need to insert an insn on the edge from block 0 to block 1,
1271 we want to ensure the instructions we insert are outside of any
1272 loop notes that physically sit between block 0 and block 1. Otherwise
1273 we confuse the loop optimizer into thinking the loop is a phony. */
1275 if (edge_in
->dest
!= EXIT_BLOCK_PTR
1276 && PREV_INSN (edge_in
->dest
->head
)
1277 && GET_CODE (PREV_INSN (edge_in
->dest
->head
)) == NOTE
1278 && (NOTE_LINE_NUMBER (PREV_INSN (edge_in
->dest
->head
))
1279 == NOTE_INSN_LOOP_BEG
)
1280 && !back_edge_of_syntactic_loop_p (edge_in
->dest
, edge_in
->src
))
1281 before
= PREV_INSN (edge_in
->dest
->head
);
1282 else if (edge_in
->dest
!= EXIT_BLOCK_PTR
)
1283 before
= edge_in
->dest
->head
;
1287 bb
= create_basic_block (before
, NULL
, edge_in
->dest
->prev_bb
);
1288 bb
->count
= edge_in
->count
;
1289 bb
->frequency
= EDGE_FREQUENCY (edge_in
);
1291 /* ??? This info is likely going to be out of date very soon. */
1292 if (edge_in
->dest
->global_live_at_start
)
1294 bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1295 bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1296 COPY_REG_SET (bb
->global_live_at_start
,
1297 edge_in
->dest
->global_live_at_start
);
1298 COPY_REG_SET (bb
->global_live_at_end
,
1299 edge_in
->dest
->global_live_at_start
);
1302 make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1304 /* For non-fallthry edges, we must adjust the predecessor's
1305 jump instruction to target our new block. */
1306 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1308 if (!redirect_edge_and_branch (edge_in
, bb
))
1312 redirect_edge_succ (edge_in
, bb
);
1317 /* Queue instructions for insertion on an edge between two basic blocks.
1318 The new instructions and basic blocks (if any) will not appear in the
1319 CFG until commit_edge_insertions is called. */
1322 insert_insn_on_edge (pattern
, e
)
1326 /* We cannot insert instructions on an abnormal critical edge.
1327 It will be easier to find the culprit if we die now. */
1328 if ((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
1331 if (e
->insns
== NULL_RTX
)
1334 push_to_sequence (e
->insns
);
1336 emit_insn (pattern
);
1338 e
->insns
= get_insns ();
1342 /* Update the CFG for the instructions queued on edge E. */
1345 commit_one_edge_insertion (e
, watch_calls
)
1349 rtx before
= NULL_RTX
, after
= NULL_RTX
, insns
, tmp
, last
;
1350 basic_block bb
= NULL
;
1352 /* Pull the insns off the edge now since the edge might go away. */
1354 e
->insns
= NULL_RTX
;
1356 /* Special case -- avoid inserting code between call and storing
1357 its return value. */
1358 if (watch_calls
&& (e
->flags
& EDGE_FALLTHRU
) && !e
->dest
->pred
->pred_next
1359 && e
->src
!= ENTRY_BLOCK_PTR
1360 && GET_CODE (e
->src
->end
) == CALL_INSN
)
1362 rtx next
= next_nonnote_insn (e
->src
->end
);
1364 after
= e
->dest
->head
;
1365 /* The first insn after the call may be a stack pop, skip it. */
1367 && keep_with_call_p (next
))
1370 next
= next_nonnote_insn (next
);
1374 if (!before
&& !after
)
1376 /* Figure out where to put these things. If the destination has
1377 one predecessor, insert there. Except for the exit block. */
1378 if (e
->dest
->pred
->pred_next
== NULL
&& e
->dest
!= EXIT_BLOCK_PTR
)
1382 /* Get the location correct wrt a code label, and "nice" wrt
1383 a basic block note, and before everything else. */
1385 if (GET_CODE (tmp
) == CODE_LABEL
)
1386 tmp
= NEXT_INSN (tmp
);
1387 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1388 tmp
= NEXT_INSN (tmp
);
1389 if (tmp
== bb
->head
)
1392 after
= PREV_INSN (tmp
);
1394 after
= get_last_insn ();
1397 /* If the source has one successor and the edge is not abnormal,
1398 insert there. Except for the entry block. */
1399 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1400 && e
->src
->succ
->succ_next
== NULL
1401 && e
->src
!= ENTRY_BLOCK_PTR
)
1405 /* It is possible to have a non-simple jump here. Consider a target
1406 where some forms of unconditional jumps clobber a register. This
1407 happens on the fr30 for example.
1409 We know this block has a single successor, so we can just emit
1410 the queued insns before the jump. */
1411 if (GET_CODE (bb
->end
) == JUMP_INSN
)
1412 for (before
= bb
->end
;
1413 GET_CODE (PREV_INSN (before
)) == NOTE
1414 && NOTE_LINE_NUMBER (PREV_INSN (before
)) ==
1415 NOTE_INSN_LOOP_BEG
; before
= PREV_INSN (before
))
1419 /* We'd better be fallthru, or we've lost track of what's what. */
1420 if ((e
->flags
& EDGE_FALLTHRU
) == 0)
1426 /* Otherwise we must split the edge. */
1429 bb
= split_edge (e
);
1434 /* Now that we've found the spot, do the insertion. */
1438 emit_insn_before (insns
, before
);
1439 last
= prev_nonnote_insn (before
);
1442 last
= emit_insn_after (insns
, after
);
1444 if (returnjump_p (last
))
1446 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1447 This is not currently a problem because this only happens
1448 for the (single) epilogue, which already has a fallthru edge
1452 if (e
->dest
!= EXIT_BLOCK_PTR
1453 || e
->succ_next
!= NULL
|| (e
->flags
& EDGE_FALLTHRU
) == 0)
1456 e
->flags
&= ~EDGE_FALLTHRU
;
1457 emit_barrier_after (last
);
1460 delete_insn (before
);
1462 else if (GET_CODE (last
) == JUMP_INSN
)
1465 /* Mark the basic block for find_sub_basic_blocks. */
1469 /* Update the CFG for all queued instructions. */
1472 commit_edge_insertions ()
1476 bool changed
= false;
1478 #ifdef ENABLE_CHECKING
1479 verify_flow_info ();
1482 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
1486 for (e
= bb
->succ
; e
; e
= next
)
1488 next
= e
->succ_next
;
1492 commit_one_edge_insertion (e
, false);
1500 blocks
= sbitmap_alloc (last_basic_block
);
1501 sbitmap_zero (blocks
);
1505 SET_BIT (blocks
, bb
->index
);
1506 /* Check for forgotten bb->aux values before commit_edge_insertions
1508 if (bb
->aux
!= &bb
->aux
)
1512 find_many_sub_basic_blocks (blocks
);
1513 sbitmap_free (blocks
);
1516 /* Update the CFG for all queued instructions, taking special care of inserting
1517 code on edges between call and storing its return value. */
1520 commit_edge_insertions_watch_calls ()
1524 bool changed
= false;
1526 #ifdef ENABLE_CHECKING
1527 verify_flow_info ();
1530 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
1534 for (e
= bb
->succ
; e
; e
= next
)
1536 next
= e
->succ_next
;
1540 commit_one_edge_insertion (e
, true);
1548 blocks
= sbitmap_alloc (last_basic_block
);
1549 sbitmap_zero (blocks
);
1553 SET_BIT (blocks
, bb
->index
);
1554 /* Check for forgotten bb->aux values before commit_edge_insertions
1556 if (bb
->aux
!= &bb
->aux
)
1560 find_many_sub_basic_blocks (blocks
);
1561 sbitmap_free (blocks
);
1564 /* Print out one basic block with live information at start and end. */
1575 fprintf (outf
, ";; Basic block %d, loop depth %d, count ",
1576 bb
->index
, bb
->loop_depth
);
1577 fprintf (outf
, HOST_WIDEST_INT_PRINT_DEC
, (HOST_WIDEST_INT
) bb
->count
);
1580 fputs (";; Predecessors: ", outf
);
1581 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1582 dump_edge_info (outf
, e
, 0);
1585 fputs (";; Registers live at start:", outf
);
1586 dump_regset (bb
->global_live_at_start
, outf
);
1589 for (insn
= bb
->head
, last
= NEXT_INSN (bb
->end
); insn
!= last
;
1590 insn
= NEXT_INSN (insn
))
1591 print_rtl_single (outf
, insn
);
1593 fputs (";; Registers live at end:", outf
);
1594 dump_regset (bb
->global_live_at_end
, outf
);
1597 fputs (";; Successors: ", outf
);
1598 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1599 dump_edge_info (outf
, e
, 1);
1607 dump_bb (bb
, stderr
);
1614 basic_block bb
= BASIC_BLOCK (n
);
1615 dump_bb (bb
, stderr
);
1619 /* Like print_rtl, but also print out live information for the start of each
1623 print_rtl_with_bb (outf
, rtx_first
)
1630 fprintf (outf
, "(nil)\n");
1633 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
1634 int max_uid
= get_max_uid ();
1636 = (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1638 = (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1639 enum bb_state
*in_bb_p
1640 = (enum bb_state
*) xcalloc (max_uid
, sizeof (enum bb_state
));
1644 FOR_EACH_BB_REVERSE (bb
)
1648 start
[INSN_UID (bb
->head
)] = bb
;
1649 end
[INSN_UID (bb
->end
)] = bb
;
1650 for (x
= bb
->head
; x
!= NULL_RTX
; x
= NEXT_INSN (x
))
1652 enum bb_state state
= IN_MULTIPLE_BB
;
1654 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
1656 in_bb_p
[INSN_UID (x
)] = state
;
1663 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
1667 if ((bb
= start
[INSN_UID (tmp_rtx
)]) != NULL
)
1669 fprintf (outf
, ";; Start of basic block %d, registers live:",
1671 dump_regset (bb
->global_live_at_start
, outf
);
1675 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
1676 && GET_CODE (tmp_rtx
) != NOTE
1677 && GET_CODE (tmp_rtx
) != BARRIER
)
1678 fprintf (outf
, ";; Insn is not within a basic block\n");
1679 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
1680 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
1682 did_output
= print_rtl_single (outf
, tmp_rtx
);
1684 if ((bb
= end
[INSN_UID (tmp_rtx
)]) != NULL
)
1686 fprintf (outf
, ";; End of basic block %d, registers live:\n",
1688 dump_regset (bb
->global_live_at_end
, outf
);
1701 if (current_function_epilogue_delay_list
!= 0)
1703 fprintf (outf
, "\n;; Insns in epilogue delay list:\n\n");
1704 for (tmp_rtx
= current_function_epilogue_delay_list
; tmp_rtx
!= 0;
1705 tmp_rtx
= XEXP (tmp_rtx
, 1))
1706 print_rtl_single (outf
, XEXP (tmp_rtx
, 0));
1711 update_br_prob_note (bb
)
1715 if (GET_CODE (bb
->end
) != JUMP_INSN
)
1717 note
= find_reg_note (bb
->end
, REG_BR_PROB
, NULL_RTX
);
1718 if (!note
|| INTVAL (XEXP (note
, 0)) == BRANCH_EDGE (bb
)->probability
)
1720 XEXP (note
, 0) = GEN_INT (BRANCH_EDGE (bb
)->probability
);
1723 /* Verify the CFG consistency. This function check some CFG invariants and
1724 aborts when something is wrong. Hope that this function will help to
1725 convert many optimization passes to preserve CFG consistent.
1727 Currently it does following checks:
1729 - test head/end pointers
1730 - overlapping of basic blocks
1731 - edge list correctness
1732 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1733 - tails of basic blocks (ensure that boundary is necessary)
1734 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1735 and NOTE_INSN_BASIC_BLOCK
1736 - check that all insns are in the basic blocks
1737 (except the switch handling code, barriers and notes)
1738 - check that all returns are followed by barriers
1740 In future it can be extended check a lot of other stuff as well
1741 (reachability of basic blocks, life information, etc. etc.). */
1746 const int max_uid
= get_max_uid ();
1747 const rtx rtx_first
= get_insns ();
1748 rtx last_head
= get_last_insn ();
1749 basic_block
*bb_info
, *last_visited
;
1750 size_t *edge_checksum
;
1752 int num_bb_notes
, err
= 0;
1753 basic_block bb
, last_bb_seen
;
1755 bb_info
= (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1756 last_visited
= (basic_block
*) xcalloc (last_basic_block
+ 2,
1757 sizeof (basic_block
));
1758 edge_checksum
= (size_t *) xcalloc (last_basic_block
+ 2, sizeof (size_t));
1760 /* Check bb chain & numbers. */
1761 last_bb_seen
= ENTRY_BLOCK_PTR
;
1762 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
->next_bb
, NULL
, next_bb
)
1764 if (bb
!= EXIT_BLOCK_PTR
1765 && bb
!= BASIC_BLOCK (bb
->index
))
1767 error ("bb %d on wrong place", bb
->index
);
1771 if (bb
->prev_bb
!= last_bb_seen
)
1773 error ("prev_bb of %d should be %d, not %d",
1774 bb
->index
, last_bb_seen
->index
, bb
->prev_bb
->index
);
1781 FOR_EACH_BB_REVERSE (bb
)
1783 rtx head
= bb
->head
;
1786 /* Verify the end of the basic block is in the INSN chain. */
1787 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1793 error ("end insn %d for block %d not found in the insn stream",
1794 INSN_UID (end
), bb
->index
);
1798 /* Work backwards from the end to the head of the basic block
1799 to verify the head is in the RTL chain. */
1800 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1802 /* While walking over the insn chain, verify insns appear
1803 in only one basic block and initialize the BB_INFO array
1804 used by other passes. */
1805 if (bb_info
[INSN_UID (x
)] != NULL
)
1807 error ("insn %d is in multiple basic blocks (%d and %d)",
1808 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
1812 bb_info
[INSN_UID (x
)] = bb
;
1819 error ("head insn %d for block %d not found in the insn stream",
1820 INSN_UID (head
), bb
->index
);
1827 /* Now check the basic blocks (boundaries etc.) */
1828 FOR_EACH_BB_REVERSE (bb
)
1830 int n_fallthru
= 0, n_eh
= 0, n_call
= 0, n_abnormal
= 0, n_branch
= 0;
1834 if (INSN_P (bb
->end
)
1835 && (note
= find_reg_note (bb
->end
, REG_BR_PROB
, NULL_RTX
))
1836 && bb
->succ
&& bb
->succ
->succ_next
1837 && any_condjump_p (bb
->end
))
1839 if (INTVAL (XEXP (note
, 0)) != BRANCH_EDGE (bb
)->probability
)
1841 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
1842 INTVAL (XEXP (note
, 0)), BRANCH_EDGE (bb
)->probability
);
1848 error ("verify_flow_info: Wrong count of block %i %i",
1849 bb
->index
, (int)bb
->count
);
1852 if (bb
->frequency
< 0)
1854 error ("verify_flow_info: Wrong frequency of block %i %i",
1855 bb
->index
, bb
->frequency
);
1858 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1860 if (last_visited
[e
->dest
->index
+ 2] == bb
)
1862 error ("verify_flow_info: Duplicate edge %i->%i",
1863 e
->src
->index
, e
->dest
->index
);
1866 if (e
->probability
< 0 || e
->probability
> REG_BR_PROB_BASE
)
1868 error ("verify_flow_info: Wrong probability of edge %i->%i %i",
1869 e
->src
->index
, e
->dest
->index
, e
->probability
);
1874 error ("verify_flow_info: Wrong count of edge %i->%i %i",
1875 e
->src
->index
, e
->dest
->index
, (int)e
->count
);
1879 last_visited
[e
->dest
->index
+ 2] = bb
;
1881 if (e
->flags
& EDGE_FALLTHRU
)
1884 if ((e
->flags
& ~(EDGE_DFS_BACK
| EDGE_CAN_FALLTHRU
| EDGE_IRREDUCIBLE_LOOP
)) == 0)
1887 if (e
->flags
& EDGE_ABNORMAL_CALL
)
1890 if (e
->flags
& EDGE_EH
)
1892 else if (e
->flags
& EDGE_ABNORMAL
)
1895 if ((e
->flags
& EDGE_FALLTHRU
)
1896 && e
->src
!= ENTRY_BLOCK_PTR
1897 && e
->dest
!= EXIT_BLOCK_PTR
)
1901 if (e
->src
->next_bb
!= e
->dest
)
1904 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
1905 e
->src
->index
, e
->dest
->index
);
1909 for (insn
= NEXT_INSN (e
->src
->end
); insn
!= e
->dest
->head
;
1910 insn
= NEXT_INSN (insn
))
1911 if (GET_CODE (insn
) == BARRIER
1912 #ifndef CASE_DROPS_THROUGH
1915 || (INSN_P (insn
) && ! JUMP_TABLE_DATA_P (insn
))
1919 error ("verify_flow_info: Incorrect fallthru %i->%i",
1920 e
->src
->index
, e
->dest
->index
);
1921 fatal_insn ("wrong insn in the fallthru edge", insn
);
1928 error ("verify_flow_info: Basic block %d succ edge is corrupted",
1930 fprintf (stderr
, "Predecessor: ");
1931 dump_edge_info (stderr
, e
, 0);
1932 fprintf (stderr
, "\nSuccessor: ");
1933 dump_edge_info (stderr
, e
, 1);
1934 fprintf (stderr
, "\n");
1938 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
1941 if (n_eh
&& GET_CODE (PATTERN (bb
->end
)) != RESX
1942 && !find_reg_note (bb
->end
, REG_EH_REGION
, NULL_RTX
))
1944 error ("Missing REG_EH_REGION note in the end of bb %i", bb
->index
);
1948 && (GET_CODE (bb
->end
) != JUMP_INSN
1949 || (n_branch
> 1 && (any_uncondjump_p (bb
->end
)
1950 || any_condjump_p (bb
->end
)))))
1952 error ("Too many outgoing branch edges from bb %i", bb
->index
);
1955 if (n_fallthru
&& any_uncondjump_p (bb
->end
))
1957 error ("Fallthru edge after unconditional jump %i", bb
->index
);
1960 if (n_branch
!= 1 && any_uncondjump_p (bb
->end
))
1962 error ("Wrong amount of branch edges after unconditional jump %i", bb
->index
);
1965 if (n_branch
!= 1 && any_condjump_p (bb
->end
)
1966 && JUMP_LABEL (bb
->end
) != bb
->next_bb
->head
)
1968 error ("Wrong amount of branch edges after conditional jump %i", bb
->index
);
1971 if (n_call
&& GET_CODE (bb
->end
) != CALL_INSN
)
1973 error ("Call edges for non-call insn in bb %i", bb
->index
);
1977 && (GET_CODE (bb
->end
) != CALL_INSN
&& n_call
!= n_abnormal
)
1978 && (GET_CODE (bb
->end
) != JUMP_INSN
1979 || any_condjump_p (bb
->end
)
1980 || any_uncondjump_p (bb
->end
)))
1982 error ("Abnormal edges for no purpose in bb %i", bb
->index
);
1990 /* Ensure existence of barrier in BB with no fallthru edges. */
1991 for (insn
= bb
->end
; !insn
|| GET_CODE (insn
) != BARRIER
;
1992 insn
= NEXT_INSN (insn
))
1994 || (GET_CODE (insn
) == NOTE
1995 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BASIC_BLOCK
))
1997 error ("missing barrier after block %i", bb
->index
);
2003 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
2007 error ("basic block %d pred edge is corrupted", bb
->index
);
2008 fputs ("Predecessor: ", stderr
);
2009 dump_edge_info (stderr
, e
, 0);
2010 fputs ("\nSuccessor: ", stderr
);
2011 dump_edge_info (stderr
, e
, 1);
2012 fputc ('\n', stderr
);
2015 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
2018 for (x
= bb
->head
; x
!= NEXT_INSN (bb
->end
); x
= NEXT_INSN (x
))
2019 if (BLOCK_FOR_INSN (x
) != bb
)
2022 if (! BLOCK_FOR_INSN (x
))
2024 ("insn %d inside basic block %d but block_for_insn is NULL",
2025 INSN_UID (x
), bb
->index
);
2028 ("insn %d inside basic block %d but block_for_insn is %i",
2029 INSN_UID (x
), bb
->index
, BLOCK_FOR_INSN (x
)->index
);
2034 /* OK pointers are correct. Now check the header of basic
2035 block. It ought to contain optional CODE_LABEL followed
2036 by NOTE_BASIC_BLOCK. */
2038 if (GET_CODE (x
) == CODE_LABEL
)
2042 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2050 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
2052 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2058 /* Do checks for empty blocks her. e */
2061 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2063 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2065 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2066 INSN_UID (x
), bb
->index
);
2073 if (control_flow_insn_p (x
))
2075 error ("in basic block %d:", bb
->index
);
2076 fatal_insn ("flow control insn inside a basic block", x
);
2081 /* Complete edge checksumming for ENTRY and EXIT. */
2085 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
2086 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
2088 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
2089 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
2092 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
2093 if (edge_checksum
[bb
->index
+ 2])
2095 error ("basic block %i edge lists are corrupted", bb
->index
);
2100 last_bb_seen
= ENTRY_BLOCK_PTR
;
2102 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2104 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2106 bb
= NOTE_BASIC_BLOCK (x
);
2109 if (bb
!= last_bb_seen
->next_bb
)
2110 internal_error ("basic blocks not numbered consecutively");
2115 if (!bb_info
[INSN_UID (x
)])
2117 switch (GET_CODE (x
))
2124 /* An addr_vec is placed outside any block block. */
2126 && GET_CODE (NEXT_INSN (x
)) == JUMP_INSN
2127 && (GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_DIFF_VEC
2128 || GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_VEC
))
2131 /* But in any case, non-deletable labels can appear anywhere. */
2135 fatal_insn ("insn outside basic block", x
);
2140 && GET_CODE (x
) == JUMP_INSN
2141 && returnjump_p (x
) && ! condjump_p (x
)
2142 && ! (NEXT_INSN (x
) && GET_CODE (NEXT_INSN (x
)) == BARRIER
))
2143 fatal_insn ("return not followed by barrier", x
);
2146 if (num_bb_notes
!= n_basic_blocks
)
2148 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2149 num_bb_notes
, n_basic_blocks
);
2152 internal_error ("verify_flow_info failed");
2156 free (last_visited
);
2157 free (edge_checksum
);
2160 /* Assume that the preceding pass has possibly eliminated jump instructions
2161 or converted the unconditional jumps. Eliminate the edges from CFG.
2162 Return true if any edges are eliminated. */
2165 purge_dead_edges (bb
)
2169 rtx insn
= bb
->end
, note
;
2170 bool purged
= false;
2172 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2173 if (GET_CODE (insn
) == INSN
2174 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
2178 if (! may_trap_p (PATTERN (insn
))
2179 || ((eqnote
= find_reg_equal_equiv_note (insn
))
2180 && ! may_trap_p (XEXP (eqnote
, 0))))
2181 remove_note (insn
, note
);
2184 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
2185 for (e
= bb
->succ
; e
; e
= next
)
2187 next
= e
->succ_next
;
2188 if (e
->flags
& EDGE_EH
)
2190 if (can_throw_internal (bb
->end
))
2193 else if (e
->flags
& EDGE_ABNORMAL_CALL
)
2195 if (GET_CODE (bb
->end
) == CALL_INSN
2196 && (! (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
))
2197 || INTVAL (XEXP (note
, 0)) >= 0))
2204 bb
->flags
|= BB_DIRTY
;
2208 if (GET_CODE (insn
) == JUMP_INSN
)
2213 /* We do care only about conditional jumps and simplejumps. */
2214 if (!any_condjump_p (insn
)
2215 && !returnjump_p (insn
)
2216 && !simplejump_p (insn
))
2219 /* Branch probability/prediction notes are defined only for
2220 condjumps. We've possibly turned condjump into simplejump. */
2221 if (simplejump_p (insn
))
2223 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2225 remove_note (insn
, note
);
2226 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
2227 remove_note (insn
, note
);
2230 for (e
= bb
->succ
; e
; e
= next
)
2232 next
= e
->succ_next
;
2234 /* Avoid abnormal flags to leak from computed jumps turned
2235 into simplejumps. */
2237 e
->flags
&= ~EDGE_ABNORMAL
;
2239 /* See if this edge is one we should keep. */
2240 if ((e
->flags
& EDGE_FALLTHRU
) && any_condjump_p (insn
))
2241 /* A conditional jump can fall through into the next
2242 block, so we should keep the edge. */
2244 else if (e
->dest
!= EXIT_BLOCK_PTR
2245 && e
->dest
->head
== JUMP_LABEL (insn
))
2246 /* If the destination block is the target of the jump,
2249 else if (e
->dest
== EXIT_BLOCK_PTR
&& returnjump_p (insn
))
2250 /* If the destination block is the exit block, and this
2251 instruction is a return, then keep the edge. */
2253 else if ((e
->flags
& EDGE_EH
) && can_throw_internal (insn
))
2254 /* Keep the edges that correspond to exceptions thrown by
2255 this instruction. */
2258 /* We do not need this edge. */
2259 bb
->flags
|= BB_DIRTY
;
2264 if (!bb
->succ
|| !purged
)
2268 fprintf (rtl_dump_file
, "Purged edges from bb %i\n", bb
->index
);
2273 /* Redistribute probabilities. */
2274 if (!bb
->succ
->succ_next
)
2276 bb
->succ
->probability
= REG_BR_PROB_BASE
;
2277 bb
->succ
->count
= bb
->count
;
2281 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2285 b
= BRANCH_EDGE (bb
);
2286 f
= FALLTHRU_EDGE (bb
);
2287 b
->probability
= INTVAL (XEXP (note
, 0));
2288 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
2289 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
2290 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
2296 /* If we don't see a jump insn, we don't know exactly why the block would
2297 have been broken at this point. Look for a simple, non-fallthru edge,
2298 as these are only created by conditional branches. If we find such an
2299 edge we know that there used to be a jump here and can then safely
2300 remove all non-fallthru edges. */
2301 for (e
= bb
->succ
; e
&& (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
));
2308 for (e
= bb
->succ
; e
; e
= next
)
2310 next
= e
->succ_next
;
2311 if (!(e
->flags
& EDGE_FALLTHRU
))
2313 bb
->flags
|= BB_DIRTY
;
2319 if (!bb
->succ
|| bb
->succ
->succ_next
)
2322 bb
->succ
->probability
= REG_BR_PROB_BASE
;
2323 bb
->succ
->count
= bb
->count
;
2326 fprintf (rtl_dump_file
, "Purged non-fallthru edges from bb %i\n",
2331 /* Search all basic blocks for potentially dead edges and purge them. Return
2332 true if some edge has been eliminated. */
2335 purge_all_dead_edges (update_life_p
)
2344 blocks
= sbitmap_alloc (last_basic_block
);
2345 sbitmap_zero (blocks
);
2350 bool purged_here
= purge_dead_edges (bb
);
2352 purged
|= purged_here
;
2353 if (purged_here
&& update_life_p
)
2354 SET_BIT (blocks
, bb
->index
);
2357 if (update_life_p
&& purged
)
2358 update_life_info (blocks
, UPDATE_LIFE_GLOBAL
,
2359 PROP_DEATH_NOTES
| PROP_SCAN_DEAD_CODE
2360 | PROP_KILL_DEAD_CODE
);
2363 sbitmap_free (blocks
);