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
);
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
)
189 if (basic_block_for_insn
191 && (unsigned int)INSN_UID (insn
) < basic_block_for_insn
->num_elements
192 && BLOCK_FOR_INSN (insn
)
193 && BLOCK_FOR_INSN (insn
)->end
== insn
)
195 x
= delete_insn (insn
);
197 purge_dead_edges (BLOCK_FOR_INSN (insn
));
201 /* Unlink a chain of insns between START and FINISH, leaving notes
202 that must be paired. */
205 delete_insn_chain (start
, finish
)
210 /* Unchain the insns one by one. It would be quicker to delete all of these
211 with a single unchaining, rather than one at a time, but we need to keep
215 next
= NEXT_INSN (start
);
216 if (GET_CODE (start
) == NOTE
&& !can_delete_note_p (start
))
219 next
= delete_insn (start
);
227 /* Like delete_insn but also purge dead edges from BB. */
229 delete_insn_chain_and_edges (first
, last
)
234 if (basic_block_for_insn
236 && (unsigned int)INSN_UID (last
) < basic_block_for_insn
->num_elements
237 && BLOCK_FOR_INSN (last
)
238 && BLOCK_FOR_INSN (last
)->end
== last
)
240 delete_insn_chain (first
, last
);
242 purge_dead_edges (BLOCK_FOR_INSN (last
));
245 /* Create a new basic block consisting of the instructions between HEAD and END
246 inclusive. This function is designed to allow fast BB construction - reuses
247 the note and basic block struct in BB_NOTE, if any and do not grow
248 BASIC_BLOCK chain and should be used directly only by CFG construction code.
249 END can be NULL in to create new empty basic block before HEAD. Both END
250 and HEAD can be NULL to create basic block at the end of INSN chain. */
253 create_basic_block_structure (index
, head
, end
, bb_note
)
255 rtx head
, end
, bb_note
;
260 && ! RTX_INTEGRATED_P (bb_note
)
261 && (bb
= NOTE_BASIC_BLOCK (bb_note
)) != NULL
264 /* If we found an existing note, thread it back onto the chain. */
268 if (GET_CODE (head
) == CODE_LABEL
)
272 after
= PREV_INSN (head
);
276 if (after
!= bb_note
&& NEXT_INSN (after
) != bb_note
)
277 reorder_insns (bb_note
, bb_note
, after
);
281 /* Otherwise we must create a note and a basic block structure. */
287 = emit_note_after (NOTE_INSN_BASIC_BLOCK
, get_last_insn ());
288 else if (GET_CODE (head
) == CODE_LABEL
&& end
)
290 bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK
, head
);
296 bb_note
= emit_note_before (NOTE_INSN_BASIC_BLOCK
, head
);
302 NOTE_BASIC_BLOCK (bb_note
) = bb
;
305 /* Always include the bb note in the block. */
306 if (NEXT_INSN (end
) == bb_note
)
313 BASIC_BLOCK (index
) = bb
;
314 if (basic_block_for_insn
)
315 update_bb_for_insn (bb
);
317 /* Tag the block so that we know it has been used when considering
318 other basic block notes. */
324 /* Create new basic block consisting of instructions in between HEAD and END
325 and place it to the BB chain at position INDEX. END can be NULL in to
326 create new empty basic block before HEAD. Both END and HEAD can be NULL to
327 create basic block at the end of INSN chain. */
330 create_basic_block (index
, head
, end
)
337 /* Place the new block just after the block being split. */
338 VARRAY_GROW (basic_block_info
, ++n_basic_blocks
);
340 /* Some parts of the compiler expect blocks to be number in
341 sequential order so insert the new block immediately after the
342 block being split.. */
343 for (i
= n_basic_blocks
- 1; i
> index
; --i
)
345 basic_block tmp
= BASIC_BLOCK (i
- 1);
347 BASIC_BLOCK (i
) = tmp
;
351 bb
= create_basic_block_structure (index
, head
, end
, NULL
);
356 /* Delete the insns in a (non-live) block. We physically delete every
357 non-deleted-note insn, and update the flow graph appropriately.
359 Return nonzero if we deleted an exception handler. */
361 /* ??? Preserving all such notes strikes me as wrong. It would be nice
362 to post-process the stream to remove empty blocks, loops, ranges, etc. */
365 flow_delete_block_noexpunge (b
)
368 int deleted_handler
= 0;
371 /* If the head of this block is a CODE_LABEL, then it might be the
372 label for an exception handler which can't be reached.
374 We need to remove the label from the exception_handler_label list
375 and remove the associated NOTE_INSN_EH_REGION_BEG and
376 NOTE_INSN_EH_REGION_END notes. */
380 never_reached_warning (insn
, b
->end
);
382 if (GET_CODE (insn
) == CODE_LABEL
)
383 maybe_remove_eh_handler (insn
);
385 /* Include any jump table following the basic block. */
387 if (GET_CODE (end
) == JUMP_INSN
388 && (tmp
= JUMP_LABEL (end
)) != NULL_RTX
389 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
390 && GET_CODE (tmp
) == JUMP_INSN
391 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
392 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
395 /* Include any barrier that may follow the basic block. */
396 tmp
= next_nonnote_insn (end
);
397 if (tmp
&& GET_CODE (tmp
) == BARRIER
)
400 /* Selectively delete the entire chain. */
402 delete_insn_chain (insn
, end
);
404 /* Remove the edges into and out of this block. Note that there may
405 indeed be edges in, if we are removing an unreachable loop. */
406 while (b
->pred
!= NULL
)
407 remove_edge (b
->pred
);
408 while (b
->succ
!= NULL
)
409 remove_edge (b
->succ
);
414 return deleted_handler
;
418 flow_delete_block (b
)
421 int deleted_handler
= flow_delete_block_noexpunge (b
);
423 /* Remove the basic block from the array, and compact behind it. */
426 return deleted_handler
;
429 /* Records the basic block struct in BB_FOR_INSN, for every instruction
430 indexed by INSN_UID. MAX is the size of the array. */
433 compute_bb_for_insn (max
)
438 if (basic_block_for_insn
)
439 VARRAY_FREE (basic_block_for_insn
);
441 VARRAY_BB_INIT (basic_block_for_insn
, max
, "basic_block_for_insn");
443 for (i
= 0; i
< n_basic_blocks
; ++i
)
445 basic_block bb
= BASIC_BLOCK (i
);
449 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
451 if (INSN_UID (insn
) < max
)
452 VARRAY_BB (basic_block_for_insn
, INSN_UID (insn
)) = bb
;
460 /* Release the basic_block_for_insn array. */
465 if (basic_block_for_insn
)
466 VARRAY_FREE (basic_block_for_insn
);
468 basic_block_for_insn
= 0;
471 /* Update insns block within BB. */
474 update_bb_for_insn (bb
)
479 if (! basic_block_for_insn
)
482 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
484 set_block_for_insn (insn
, bb
);
490 /* Record INSN's block as BB. */
493 set_block_for_insn (insn
, bb
)
497 size_t uid
= INSN_UID (insn
);
499 if (uid
>= basic_block_for_insn
->num_elements
)
501 /* Add one-eighth the size so we don't keep calling xrealloc. */
502 size_t new_size
= uid
+ (uid
+ 7) / 8;
504 VARRAY_GROW (basic_block_for_insn
, new_size
);
507 VARRAY_BB (basic_block_for_insn
, uid
) = bb
;
510 /* Split a block BB after insn INSN creating a new fallthru edge.
511 Return the new edge. Note that to keep other parts of the compiler happy,
512 this function renumbers all the basic blocks so that the new
513 one has a number one greater than the block split. */
516 split_block (bb
, insn
)
524 /* There is no point splitting the block after its end. */
528 /* Create the new basic block. */
529 new_bb
= create_basic_block (bb
->index
+ 1, NEXT_INSN (insn
), bb
->end
);
530 new_bb
->count
= bb
->count
;
531 new_bb
->frequency
= bb
->frequency
;
532 new_bb
->loop_depth
= bb
->loop_depth
;
535 /* Redirect the outgoing edges. */
536 new_bb
->succ
= bb
->succ
;
538 for (e
= new_bb
->succ
; e
; e
= e
->succ_next
)
541 new_edge
= make_single_succ_edge (bb
, new_bb
, EDGE_FALLTHRU
);
543 if (bb
->global_live_at_start
)
545 new_bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
546 new_bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
547 COPY_REG_SET (new_bb
->global_live_at_end
, bb
->global_live_at_end
);
549 /* We now have to calculate which registers are live at the end
550 of the split basic block and at the start of the new basic
551 block. Start with those registers that are known to be live
552 at the end of the original basic block and get
553 propagate_block to determine which registers are live. */
554 COPY_REG_SET (new_bb
->global_live_at_start
, bb
->global_live_at_end
);
555 propagate_block (new_bb
, new_bb
->global_live_at_start
, NULL
, NULL
, 0);
556 COPY_REG_SET (bb
->global_live_at_end
,
557 new_bb
->global_live_at_start
);
558 #ifdef HAVE_conditional_execution
559 /* In the presence of conditional execution we are not able to update
560 liveness precisely. */
561 if (reload_completed
)
563 bb
->flags
|= BB_DIRTY
;
564 new_bb
->flags
|= BB_DIRTY
;
572 /* Blocks A and B are to be merged into a single block A. The insns
573 are already contiguous, hence `nomove'. */
576 merge_blocks_nomove (a
, b
)
579 rtx b_head
= b
->head
, b_end
= b
->end
, a_end
= a
->end
;
580 rtx del_first
= NULL_RTX
, del_last
= NULL_RTX
;
584 /* If there was a CODE_LABEL beginning B, delete it. */
585 if (GET_CODE (b_head
) == CODE_LABEL
)
587 /* Detect basic blocks with nothing but a label. This can happen
588 in particular at the end of a function. */
592 del_first
= del_last
= b_head
;
593 b_head
= NEXT_INSN (b_head
);
596 /* Delete the basic block note and handle blocks containing just that
598 if (NOTE_INSN_BASIC_BLOCK_P (b_head
))
606 b_head
= NEXT_INSN (b_head
);
609 /* If there was a jump out of A, delete it. */
610 if (GET_CODE (a_end
) == JUMP_INSN
)
614 for (prev
= PREV_INSN (a_end
); ; prev
= PREV_INSN (prev
))
615 if (GET_CODE (prev
) != NOTE
616 || NOTE_LINE_NUMBER (prev
) == NOTE_INSN_BASIC_BLOCK
623 /* If this was a conditional jump, we need to also delete
624 the insn that set cc0. */
625 if (only_sets_cc0_p (prev
))
629 prev
= prev_nonnote_insn (prev
);
636 a_end
= PREV_INSN (del_first
);
638 else if (GET_CODE (NEXT_INSN (a_end
)) == BARRIER
)
639 del_first
= NEXT_INSN (a_end
);
641 /* Normally there should only be one successor of A and that is B, but
642 partway though the merge of blocks for conditional_execution we'll
643 be merging a TEST block with THEN and ELSE successors. Free the
644 whole lot of them and hope the caller knows what they're doing. */
646 remove_edge (a
->succ
);
648 /* Adjust the edges out of B for the new owner. */
649 for (e
= b
->succ
; e
; e
= e
->succ_next
)
652 a
->flags
|= b
->flags
;
654 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
655 b
->pred
= b
->succ
= NULL
;
656 a
->global_live_at_end
= b
->global_live_at_end
;
660 /* Delete everything marked above as well as crap that might be
661 hanging out between the two blocks. */
662 delete_insn_chain (del_first
, del_last
);
664 /* Reassociate the insns of B with A. */
667 if (basic_block_for_insn
)
671 for (x
= a_end
; x
!= b_end
; x
= NEXT_INSN (x
))
672 set_block_for_insn (x
, a
);
674 set_block_for_insn (b_end
, a
);
683 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
690 if (block
== EXIT_BLOCK_PTR
)
693 if (GET_CODE (block
->head
) != CODE_LABEL
)
695 block
->head
= emit_label_before (gen_label_rtx (), block
->head
);
696 if (basic_block_for_insn
)
697 set_block_for_insn (block
->head
, block
);
703 /* Attempt to perform edge redirection by replacing possibly complex jump
704 instruction by unconditional jump or removing jump completely. This can
705 apply only if all edges now point to the same block. The parameters and
706 return values are equivalent to redirect_edge_and_branch. */
709 try_redirect_by_replacing_jump (e
, target
)
713 basic_block src
= e
->src
;
714 rtx insn
= src
->end
, kill_from
;
719 /* Verify that all targets will be TARGET. */
720 for (tmp
= src
->succ
; tmp
; tmp
= tmp
->succ_next
)
721 if (tmp
->dest
!= target
&& tmp
!= e
)
724 if (tmp
|| !onlyjump_p (insn
))
726 if (reload_completed
&& JUMP_LABEL (insn
)
727 && (table
= NEXT_INSN (JUMP_LABEL (insn
))) != NULL_RTX
728 && GET_CODE (table
) == JUMP_INSN
729 && (GET_CODE (PATTERN (table
)) == ADDR_VEC
730 || GET_CODE (PATTERN (table
)) == ADDR_DIFF_VEC
))
733 /* Avoid removing branch with side effects. */
734 set
= single_set (insn
);
735 if (!set
|| side_effects_p (set
))
738 /* In case we zap a conditional jump, we'll need to kill
739 the cc0 setter too. */
742 if (reg_mentioned_p (cc0_rtx
, PATTERN (insn
)))
743 kill_from
= PREV_INSN (insn
);
746 /* See if we can create the fallthru edge. */
747 if (can_fallthru (src
, target
))
750 fprintf (rtl_dump_file
, "Removing jump %i.\n", INSN_UID (insn
));
753 /* Selectively unlink whole insn chain. */
754 delete_insn_chain (kill_from
, PREV_INSN (target
->head
));
757 /* If this already is simplejump, redirect it. */
758 else if (simplejump_p (insn
))
760 if (e
->dest
== target
)
763 fprintf (rtl_dump_file
, "Redirecting jump %i from %i to %i.\n",
764 INSN_UID (insn
), e
->dest
->index
, target
->index
);
765 if (!redirect_jump (insn
, block_label (target
), 0))
767 if (target
== EXIT_BLOCK_PTR
)
773 /* Cannot do anything for target exit block. */
774 else if (target
== EXIT_BLOCK_PTR
)
777 /* Or replace possibly complicated jump insn by simple jump insn. */
780 rtx target_label
= block_label (target
);
783 emit_jump_insn_after (gen_jump (target_label
), insn
);
784 JUMP_LABEL (src
->end
) = target_label
;
785 LABEL_NUSES (target_label
)++;
787 fprintf (rtl_dump_file
, "Replacing insn %i by jump %i\n",
788 INSN_UID (insn
), INSN_UID (src
->end
));
791 delete_insn_chain (kill_from
, insn
);
793 /* Recognize a tablejump that we are converting to a
794 simple jump and remove its associated CODE_LABEL
795 and ADDR_VEC or ADDR_DIFF_VEC. */
796 if ((tmp
= JUMP_LABEL (insn
)) != NULL_RTX
797 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
798 && GET_CODE (tmp
) == JUMP_INSN
799 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
800 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
802 delete_insn_chain (JUMP_LABEL (insn
), tmp
);
805 barrier
= next_nonnote_insn (src
->end
);
806 if (!barrier
|| GET_CODE (barrier
) != BARRIER
)
807 emit_barrier_after (src
->end
);
810 /* Keep only one edge out and set proper flags. */
811 while (src
->succ
->succ_next
)
812 remove_edge (src
->succ
);
815 e
->flags
= EDGE_FALLTHRU
;
819 e
->probability
= REG_BR_PROB_BASE
;
820 e
->count
= src
->count
;
822 /* We don't want a block to end on a line-number note since that has
823 the potential of changing the code between -g and not -g. */
824 while (GET_CODE (e
->src
->end
) == NOTE
825 && NOTE_LINE_NUMBER (e
->src
->end
) >= 0)
826 delete_insn (e
->src
->end
);
828 if (e
->dest
!= target
)
829 redirect_edge_succ (e
, target
);
834 /* Return last loop_beg note appearing after INSN, before start of next
835 basic block. Return INSN if there are no such notes.
837 When emitting jump to redirect an fallthru edge, it should always appear
838 after the LOOP_BEG notes, as loop optimizer expect loop to either start by
839 fallthru edge or jump following the LOOP_BEG note jumping to the loop exit
843 last_loop_beg_note (insn
)
848 for (insn
= NEXT_INSN (insn
); insn
&& GET_CODE (insn
) == NOTE
849 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
;
850 insn
= NEXT_INSN (insn
))
851 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
857 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
858 expense of adding new instructions or reordering basic blocks.
860 Function can be also called with edge destination equivalent to the TARGET.
861 Then it should try the simplifications and do nothing if none is possible.
863 Return true if transformation succeeded. We still return false in case E
864 already destinated TARGET and we didn't managed to simplify instruction
868 redirect_edge_and_branch (e
, target
)
873 rtx old_label
= e
->dest
->head
;
874 basic_block src
= e
->src
;
877 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
880 if (try_redirect_by_replacing_jump (e
, target
))
883 /* Do this fast path late, as we want above code to simplify for cases
884 where called on single edge leaving basic block containing nontrivial
886 else if (e
->dest
== target
)
889 /* We can only redirect non-fallthru edges of jump insn. */
890 if (e
->flags
& EDGE_FALLTHRU
)
892 else if (GET_CODE (insn
) != JUMP_INSN
)
895 /* Recognize a tablejump and adjust all matching cases. */
896 if ((tmp
= JUMP_LABEL (insn
)) != NULL_RTX
897 && (tmp
= NEXT_INSN (tmp
)) != NULL_RTX
898 && GET_CODE (tmp
) == JUMP_INSN
899 && (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
900 || GET_CODE (PATTERN (tmp
)) == ADDR_DIFF_VEC
))
904 rtx new_label
= block_label (target
);
906 if (target
== EXIT_BLOCK_PTR
)
908 if (GET_CODE (PATTERN (tmp
)) == ADDR_VEC
)
909 vec
= XVEC (PATTERN (tmp
), 0);
911 vec
= XVEC (PATTERN (tmp
), 1);
913 for (j
= GET_NUM_ELEM (vec
) - 1; j
>= 0; --j
)
914 if (XEXP (RTVEC_ELT (vec
, j
), 0) == old_label
)
916 RTVEC_ELT (vec
, j
) = gen_rtx_LABEL_REF (Pmode
, new_label
);
917 --LABEL_NUSES (old_label
);
918 ++LABEL_NUSES (new_label
);
921 /* Handle casesi dispatch insns */
922 if ((tmp
= single_set (insn
)) != NULL
923 && SET_DEST (tmp
) == pc_rtx
924 && GET_CODE (SET_SRC (tmp
)) == IF_THEN_ELSE
925 && GET_CODE (XEXP (SET_SRC (tmp
), 2)) == LABEL_REF
926 && XEXP (XEXP (SET_SRC (tmp
), 2), 0) == old_label
)
928 XEXP (SET_SRC (tmp
), 2) = gen_rtx_LABEL_REF (VOIDmode
,
930 --LABEL_NUSES (old_label
);
931 ++LABEL_NUSES (new_label
);
936 /* ?? We may play the games with moving the named labels from
937 one basic block to the other in case only one computed_jump is
939 if (computed_jump_p (insn
)
940 /* A return instruction can't be redirected. */
941 || returnjump_p (insn
))
944 /* If the insn doesn't go where we think, we're confused. */
945 if (JUMP_LABEL (insn
) != old_label
)
948 /* If the substitution doesn't succeed, die. This can happen
949 if the back end emitted unrecognizable instructions or if
950 target is exit block on some arches. */
951 if (!redirect_jump (insn
, block_label (target
), 0))
953 if (target
== EXIT_BLOCK_PTR
)
960 fprintf (rtl_dump_file
, "Edge %i->%i redirected to %i\n",
961 e
->src
->index
, e
->dest
->index
, target
->index
);
963 if (e
->dest
!= target
)
964 redirect_edge_succ_nodup (e
, target
);
969 /* Like force_nonfallthru below, but additionally performs redirection
970 Used by redirect_edge_and_branch_force. */
973 force_nonfallthru_and_redirect (e
, target
)
977 basic_block jump_block
, new_bb
= NULL
;
981 if (e
->flags
& EDGE_ABNORMAL
)
983 else if (!(e
->flags
& EDGE_FALLTHRU
))
985 else if (e
->src
== ENTRY_BLOCK_PTR
)
987 /* We can't redirect the entry block. Create an empty block at the
988 start of the function which we use to add the new jump. */
990 basic_block bb
= create_basic_block (0, e
->dest
->head
, NULL
);
992 /* Change the existing edge's source to be the new block, and add
993 a new edge from the entry block to the new block. */
995 for (pe1
= &ENTRY_BLOCK_PTR
->succ
; *pe1
; pe1
= &(*pe1
)->succ_next
)
1003 make_single_succ_edge (ENTRY_BLOCK_PTR
, bb
, EDGE_FALLTHRU
);
1006 if (e
->src
->succ
->succ_next
)
1008 /* Create the new structures. */
1009 note
= last_loop_beg_note (e
->src
->end
);
1011 = create_basic_block (e
->src
->index
+ 1, NEXT_INSN (note
), NULL
);
1012 jump_block
->count
= e
->count
;
1013 jump_block
->frequency
= EDGE_FREQUENCY (e
);
1014 jump_block
->loop_depth
= target
->loop_depth
;
1016 if (target
->global_live_at_start
)
1018 jump_block
->global_live_at_start
1019 = OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1020 jump_block
->global_live_at_end
1021 = OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1022 COPY_REG_SET (jump_block
->global_live_at_start
,
1023 target
->global_live_at_start
);
1024 COPY_REG_SET (jump_block
->global_live_at_end
,
1025 target
->global_live_at_start
);
1029 new_edge
= make_edge (e
->src
, jump_block
, EDGE_FALLTHRU
);
1030 new_edge
->probability
= e
->probability
;
1031 new_edge
->count
= e
->count
;
1033 /* Redirect old edge. */
1034 redirect_edge_pred (e
, jump_block
);
1035 e
->probability
= REG_BR_PROB_BASE
;
1037 new_bb
= jump_block
;
1040 jump_block
= e
->src
;
1042 e
->flags
&= ~EDGE_FALLTHRU
;
1043 if (target
== EXIT_BLOCK_PTR
)
1046 emit_jump_insn_after (gen_return (), jump_block
->end
);
1052 rtx label
= block_label (target
);
1053 emit_jump_insn_after (gen_jump (label
), jump_block
->end
);
1054 JUMP_LABEL (jump_block
->end
) = label
;
1055 LABEL_NUSES (label
)++;
1058 emit_barrier_after (jump_block
->end
);
1059 redirect_edge_succ_nodup (e
, target
);
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 for (i
= 1; i
< n_basic_blocks
; i
++)
1160 basic_block b
= BASIC_BLOCK (i
- 1);
1161 basic_block c
= BASIC_BLOCK (i
);
1164 /* We care about simple conditional or unconditional jumps with
1167 If we had a conditional branch to the next instruction when
1168 find_basic_blocks was called, then there will only be one
1169 out edge for the block which ended with the conditional
1170 branch (since we do not create duplicate edges).
1172 Furthermore, the edge will be marked as a fallthru because we
1173 merge the flags for the duplicate edges. So we do not want to
1174 check that the edge is not a FALLTHRU edge. */
1176 if ((s
= b
->succ
) != NULL
1177 && ! (s
->flags
& EDGE_COMPLEX
)
1178 && s
->succ_next
== NULL
1180 /* If the jump insn has side effects, we can't tidy the edge. */
1181 && (GET_CODE (b
->end
) != JUMP_INSN
1182 || onlyjump_p (b
->end
)))
1183 tidy_fallthru_edge (s
, b
, c
);
1187 /* Helper function for split_edge. Return true in case edge BB2 to BB1
1188 is back edge of syntactic loop. */
1191 back_edge_of_syntactic_loop_p (bb1
, bb2
)
1192 basic_block bb1
, bb2
;
1197 if (bb1
->index
> bb2
->index
)
1199 else if (bb1
->index
== bb2
->index
)
1202 for (insn
= bb1
->end
; insn
!= bb2
->head
&& count
>= 0;
1203 insn
= NEXT_INSN (insn
))
1204 if (GET_CODE (insn
) == NOTE
)
1206 if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_BEG
)
1208 else if (NOTE_LINE_NUMBER (insn
) == NOTE_INSN_LOOP_END
)
1215 /* Split a (typically critical) edge. Return the new block.
1216 Abort on abnormal edges.
1218 ??? The code generally expects to be called on critical edges.
1219 The case of a block ending in an unconditional jump to a
1220 block with multiple predecessors is not handled optimally. */
1223 split_edge (edge_in
)
1230 /* Abnormal edges cannot be split. */
1231 if ((edge_in
->flags
& EDGE_ABNORMAL
) != 0)
1234 /* We are going to place the new block in front of edge destination.
1235 Avoid existence of fallthru predecessors. */
1236 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1240 for (e
= edge_in
->dest
->pred
; e
; e
= e
->pred_next
)
1241 if (e
->flags
& EDGE_FALLTHRU
)
1245 force_nonfallthru (e
);
1248 /* Create the basic block note.
1250 Where we place the note can have a noticeable impact on the generated
1251 code. Consider this cfg:
1261 If we need to insert an insn on the edge from block 0 to block 1,
1262 we want to ensure the instructions we insert are outside of any
1263 loop notes that physically sit between block 0 and block 1. Otherwise
1264 we confuse the loop optimizer into thinking the loop is a phony. */
1266 if (edge_in
->dest
!= EXIT_BLOCK_PTR
1267 && PREV_INSN (edge_in
->dest
->head
)
1268 && GET_CODE (PREV_INSN (edge_in
->dest
->head
)) == NOTE
1269 && (NOTE_LINE_NUMBER (PREV_INSN (edge_in
->dest
->head
))
1270 == NOTE_INSN_LOOP_BEG
)
1271 && !back_edge_of_syntactic_loop_p (edge_in
->dest
, edge_in
->src
))
1272 before
= PREV_INSN (edge_in
->dest
->head
);
1273 else if (edge_in
->dest
!= EXIT_BLOCK_PTR
)
1274 before
= edge_in
->dest
->head
;
1278 bb
= create_basic_block (edge_in
->dest
== EXIT_BLOCK_PTR
? n_basic_blocks
1279 : edge_in
->dest
->index
, before
, NULL
);
1280 bb
->count
= edge_in
->count
;
1281 bb
->frequency
= EDGE_FREQUENCY (edge_in
);
1283 /* ??? This info is likely going to be out of date very soon. */
1284 if (edge_in
->dest
->global_live_at_start
)
1286 bb
->global_live_at_start
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1287 bb
->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_obstack
);
1288 COPY_REG_SET (bb
->global_live_at_start
,
1289 edge_in
->dest
->global_live_at_start
);
1290 COPY_REG_SET (bb
->global_live_at_end
,
1291 edge_in
->dest
->global_live_at_start
);
1294 edge_out
= make_single_succ_edge (bb
, edge_in
->dest
, EDGE_FALLTHRU
);
1296 /* For non-fallthry edges, we must adjust the predecessor's
1297 jump instruction to target our new block. */
1298 if ((edge_in
->flags
& EDGE_FALLTHRU
) == 0)
1300 if (!redirect_edge_and_branch (edge_in
, bb
))
1304 redirect_edge_succ (edge_in
, bb
);
1309 /* Queue instructions for insertion on an edge between two basic blocks.
1310 The new instructions and basic blocks (if any) will not appear in the
1311 CFG until commit_edge_insertions is called. */
1314 insert_insn_on_edge (pattern
, e
)
1318 /* We cannot insert instructions on an abnormal critical edge.
1319 It will be easier to find the culprit if we die now. */
1320 if ((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
1323 if (e
->insns
== NULL_RTX
)
1326 push_to_sequence (e
->insns
);
1328 emit_insn (pattern
);
1330 e
->insns
= get_insns ();
1334 /* Update the CFG for the instructions queued on edge E. */
1337 commit_one_edge_insertion (e
, watch_calls
)
1341 rtx before
= NULL_RTX
, after
= NULL_RTX
, insns
, tmp
, last
;
1344 /* Pull the insns off the edge now since the edge might go away. */
1346 e
->insns
= NULL_RTX
;
1348 /* Special case -- avoid inserting code between call and storing
1349 its return value. */
1350 if (watch_calls
&& (e
->flags
& EDGE_FALLTHRU
) && !e
->dest
->pred
->pred_next
1351 && e
->src
!= ENTRY_BLOCK_PTR
1352 && GET_CODE (e
->src
->end
) == CALL_INSN
)
1354 rtx next
= next_nonnote_insn (e
->src
->end
);
1356 after
= e
->dest
->head
;
1357 /* The first insn after the call may be a stack pop, skip it. */
1359 && keep_with_call_p (next
))
1362 next
= next_nonnote_insn (next
);
1366 if (!before
&& !after
)
1368 /* Figure out where to put these things. If the destination has
1369 one predecessor, insert there. Except for the exit block. */
1370 if (e
->dest
->pred
->pred_next
== NULL
&& e
->dest
!= EXIT_BLOCK_PTR
)
1374 /* Get the location correct wrt a code label, and "nice" wrt
1375 a basic block note, and before everything else. */
1377 if (GET_CODE (tmp
) == CODE_LABEL
)
1378 tmp
= NEXT_INSN (tmp
);
1379 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1380 tmp
= NEXT_INSN (tmp
);
1381 if (tmp
== bb
->head
)
1384 after
= PREV_INSN (tmp
);
1386 after
= get_last_insn ();
1389 /* If the source has one successor and the edge is not abnormal,
1390 insert there. Except for the entry block. */
1391 else if ((e
->flags
& EDGE_ABNORMAL
) == 0
1392 && e
->src
->succ
->succ_next
== NULL
1393 && e
->src
!= ENTRY_BLOCK_PTR
)
1397 /* It is possible to have a non-simple jump here. Consider a target
1398 where some forms of unconditional jumps clobber a register. This
1399 happens on the fr30 for example.
1401 We know this block has a single successor, so we can just emit
1402 the queued insns before the jump. */
1403 if (GET_CODE (bb
->end
) == JUMP_INSN
)
1404 for (before
= bb
->end
;
1405 GET_CODE (PREV_INSN (before
)) == NOTE
1406 && NOTE_LINE_NUMBER (PREV_INSN (before
)) ==
1407 NOTE_INSN_LOOP_BEG
; before
= PREV_INSN (before
))
1411 /* We'd better be fallthru, or we've lost track of what's what. */
1412 if ((e
->flags
& EDGE_FALLTHRU
) == 0)
1418 /* Otherwise we must split the edge. */
1421 bb
= split_edge (e
);
1426 /* Now that we've found the spot, do the insertion. */
1430 emit_insns_before (insns
, before
);
1431 last
= prev_nonnote_insn (before
);
1434 last
= emit_insns_after (insns
, after
);
1436 if (returnjump_p (last
))
1438 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1439 This is not currently a problem because this only happens
1440 for the (single) epilogue, which already has a fallthru edge
1444 if (e
->dest
!= EXIT_BLOCK_PTR
1445 || e
->succ_next
!= NULL
|| (e
->flags
& EDGE_FALLTHRU
) == 0)
1448 e
->flags
&= ~EDGE_FALLTHRU
;
1449 emit_barrier_after (last
);
1452 delete_insn (before
);
1454 else if (GET_CODE (last
) == JUMP_INSN
)
1457 find_sub_basic_blocks (bb
);
1460 /* Update the CFG for all queued instructions. */
1463 commit_edge_insertions ()
1468 #ifdef ENABLE_CHECKING
1469 verify_flow_info ();
1473 bb
= ENTRY_BLOCK_PTR
;
1478 for (e
= bb
->succ
; e
; e
= next
)
1480 next
= e
->succ_next
;
1482 commit_one_edge_insertion (e
, false);
1485 if (++i
>= n_basic_blocks
)
1487 bb
= BASIC_BLOCK (i
);
1491 /* Update the CFG for all queued instructions, taking special care of inserting
1492 code on edges between call and storing its return value. */
1495 commit_edge_insertions_watch_calls ()
1500 #ifdef ENABLE_CHECKING
1501 verify_flow_info ();
1505 bb
= ENTRY_BLOCK_PTR
;
1510 for (e
= bb
->succ
; e
; e
= next
)
1512 next
= e
->succ_next
;
1514 commit_one_edge_insertion (e
, true);
1517 if (++i
>= n_basic_blocks
)
1519 bb
= BASIC_BLOCK (i
);
1523 /* Print out one basic block with live information at start and end. */
1534 fprintf (outf
, ";; Basic block %d, loop depth %d, count ",
1535 bb
->index
, bb
->loop_depth
);
1536 fprintf (outf
, HOST_WIDEST_INT_PRINT_DEC
, (HOST_WIDEST_INT
) bb
->count
);
1539 fputs (";; Predecessors: ", outf
);
1540 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1541 dump_edge_info (outf
, e
, 0);
1544 fputs (";; Registers live at start:", outf
);
1545 dump_regset (bb
->global_live_at_start
, outf
);
1548 for (insn
= bb
->head
, last
= NEXT_INSN (bb
->end
); insn
!= last
;
1549 insn
= NEXT_INSN (insn
))
1550 print_rtl_single (outf
, insn
);
1552 fputs (";; Registers live at end:", outf
);
1553 dump_regset (bb
->global_live_at_end
, outf
);
1556 fputs (";; Successors: ", outf
);
1557 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1558 dump_edge_info (outf
, e
, 1);
1566 dump_bb (bb
, stderr
);
1573 dump_bb (BASIC_BLOCK (n
), stderr
);
1576 /* Like print_rtl, but also print out live information for the start of each
1580 print_rtl_with_bb (outf
, rtx_first
)
1587 fprintf (outf
, "(nil)\n");
1591 enum bb_state
{ NOT_IN_BB
, IN_ONE_BB
, IN_MULTIPLE_BB
};
1592 int max_uid
= get_max_uid ();
1594 = (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1596 = (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1597 enum bb_state
*in_bb_p
1598 = (enum bb_state
*) xcalloc (max_uid
, sizeof (enum bb_state
));
1600 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1602 basic_block bb
= BASIC_BLOCK (i
);
1605 start
[INSN_UID (bb
->head
)] = bb
;
1606 end
[INSN_UID (bb
->end
)] = bb
;
1607 for (x
= bb
->head
; x
!= NULL_RTX
; x
= NEXT_INSN (x
))
1609 enum bb_state state
= IN_MULTIPLE_BB
;
1611 if (in_bb_p
[INSN_UID (x
)] == NOT_IN_BB
)
1613 in_bb_p
[INSN_UID (x
)] = state
;
1620 for (tmp_rtx
= rtx_first
; NULL
!= tmp_rtx
; tmp_rtx
= NEXT_INSN (tmp_rtx
))
1625 if ((bb
= start
[INSN_UID (tmp_rtx
)]) != NULL
)
1627 fprintf (outf
, ";; Start of basic block %d, registers live:",
1629 dump_regset (bb
->global_live_at_start
, outf
);
1633 if (in_bb_p
[INSN_UID (tmp_rtx
)] == NOT_IN_BB
1634 && GET_CODE (tmp_rtx
) != NOTE
1635 && GET_CODE (tmp_rtx
) != BARRIER
)
1636 fprintf (outf
, ";; Insn is not within a basic block\n");
1637 else if (in_bb_p
[INSN_UID (tmp_rtx
)] == IN_MULTIPLE_BB
)
1638 fprintf (outf
, ";; Insn is in multiple basic blocks\n");
1640 did_output
= print_rtl_single (outf
, tmp_rtx
);
1642 if ((bb
= end
[INSN_UID (tmp_rtx
)]) != NULL
)
1644 fprintf (outf
, ";; End of basic block %d, registers live:\n",
1646 dump_regset (bb
->global_live_at_end
, outf
);
1659 if (current_function_epilogue_delay_list
!= 0)
1661 fprintf (outf
, "\n;; Insns in epilogue delay list:\n\n");
1662 for (tmp_rtx
= current_function_epilogue_delay_list
; tmp_rtx
!= 0;
1663 tmp_rtx
= XEXP (tmp_rtx
, 1))
1664 print_rtl_single (outf
, XEXP (tmp_rtx
, 0));
1669 update_br_prob_note (bb
)
1673 if (GET_CODE (bb
->end
) != JUMP_INSN
)
1675 note
= find_reg_note (bb
->end
, REG_BR_PROB
, NULL_RTX
);
1676 if (!note
|| INTVAL (XEXP (note
, 0)) == BRANCH_EDGE (bb
)->probability
)
1678 XEXP (note
, 0) = GEN_INT (BRANCH_EDGE (bb
)->probability
);
1681 /* Verify the CFG consistency. This function check some CFG invariants and
1682 aborts when something is wrong. Hope that this function will help to
1683 convert many optimization passes to preserve CFG consistent.
1685 Currently it does following checks:
1687 - test head/end pointers
1688 - overlapping of basic blocks
1689 - edge list correctness
1690 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1691 - tails of basic blocks (ensure that boundary is necessary)
1692 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1693 and NOTE_INSN_BASIC_BLOCK
1694 - check that all insns are in the basic blocks
1695 (except the switch handling code, barriers and notes)
1696 - check that all returns are followed by barriers
1698 In future it can be extended check a lot of other stuff as well
1699 (reachability of basic blocks, life information, etc. etc.). */
1704 const int max_uid
= get_max_uid ();
1705 const rtx rtx_first
= get_insns ();
1706 rtx last_head
= get_last_insn ();
1707 basic_block
*bb_info
, *last_visited
;
1708 size_t *edge_checksum
;
1710 int i
, last_bb_num_seen
, num_bb_notes
, err
= 0;
1712 bb_info
= (basic_block
*) xcalloc (max_uid
, sizeof (basic_block
));
1713 last_visited
= (basic_block
*) xcalloc (n_basic_blocks
+ 2,
1714 sizeof (basic_block
));
1715 edge_checksum
= (size_t *) xcalloc (n_basic_blocks
+ 2, sizeof (size_t));
1717 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1719 basic_block bb
= BASIC_BLOCK (i
);
1720 rtx head
= bb
->head
;
1723 /* Verify the end of the basic block is in the INSN chain. */
1724 for (x
= last_head
; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1730 error ("end insn %d for block %d not found in the insn stream",
1731 INSN_UID (end
), bb
->index
);
1735 /* Work backwards from the end to the head of the basic block
1736 to verify the head is in the RTL chain. */
1737 for (; x
!= NULL_RTX
; x
= PREV_INSN (x
))
1739 /* While walking over the insn chain, verify insns appear
1740 in only one basic block and initialize the BB_INFO array
1741 used by other passes. */
1742 if (bb_info
[INSN_UID (x
)] != NULL
)
1744 error ("insn %d is in multiple basic blocks (%d and %d)",
1745 INSN_UID (x
), bb
->index
, bb_info
[INSN_UID (x
)]->index
);
1749 bb_info
[INSN_UID (x
)] = bb
;
1756 error ("head insn %d for block %d not found in the insn stream",
1757 INSN_UID (head
), bb
->index
);
1764 /* Now check the basic blocks (boundaries etc.) */
1765 for (i
= n_basic_blocks
- 1; i
>= 0; i
--)
1767 basic_block bb
= BASIC_BLOCK (i
);
1768 int n_fallthru
= 0, n_eh
= 0, n_call
= 0, n_abnormal
= 0, n_branch
= 0;
1772 if (INSN_P (bb
->end
)
1773 && (note
= find_reg_note (bb
->end
, REG_BR_PROB
, NULL_RTX
))
1774 && any_condjump_p (bb
->end
))
1776 if (INTVAL (XEXP (note
, 0)) != BRANCH_EDGE (bb
)->probability
)
1778 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
1779 INTVAL (XEXP (note
, 0)), BRANCH_EDGE (bb
)->probability
);
1785 error ("verify_flow_info: Wrong count of block %i %i",
1786 bb
->index
, (int)bb
->count
);
1789 if (bb
->frequency
< 0)
1791 error ("verify_flow_info: Wrong frequency of block %i %i",
1792 bb
->index
, bb
->frequency
);
1795 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1797 if (last_visited
[e
->dest
->index
+ 2] == bb
)
1799 error ("verify_flow_info: Duplicate edge %i->%i",
1800 e
->src
->index
, e
->dest
->index
);
1803 if (e
->probability
< 0 || e
->probability
> REG_BR_PROB_BASE
)
1805 error ("verify_flow_info: Wrong probability of edge %i->%i %i",
1806 e
->src
->index
, e
->dest
->index
, e
->probability
);
1811 error ("verify_flow_info: Wrong count of edge %i->%i %i",
1812 e
->src
->index
, e
->dest
->index
, (int)e
->count
);
1816 last_visited
[e
->dest
->index
+ 2] = bb
;
1818 if (e
->flags
& EDGE_FALLTHRU
)
1821 if ((e
->flags
& ~EDGE_DFS_BACK
) == 0)
1824 if (e
->flags
& EDGE_ABNORMAL_CALL
)
1827 if (e
->flags
& EDGE_EH
)
1829 else if (e
->flags
& EDGE_ABNORMAL
)
1832 if ((e
->flags
& EDGE_FALLTHRU
)
1833 && e
->src
!= ENTRY_BLOCK_PTR
1834 && e
->dest
!= EXIT_BLOCK_PTR
)
1838 if (e
->src
->index
+ 1 != e
->dest
->index
)
1841 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
1842 e
->src
->index
, e
->dest
->index
);
1846 for (insn
= NEXT_INSN (e
->src
->end
); insn
!= e
->dest
->head
;
1847 insn
= NEXT_INSN (insn
))
1848 if (GET_CODE (insn
) == BARRIER
1849 #ifndef CASE_DROPS_THROUGH
1852 || (INSN_P (insn
) && ! JUMP_TABLE_DATA_P (insn
))
1856 error ("verify_flow_info: Incorrect fallthru %i->%i",
1857 e
->src
->index
, e
->dest
->index
);
1858 fatal_insn ("wrong insn in the fallthru edge", insn
);
1865 error ("verify_flow_info: Basic block %d succ edge is corrupted",
1867 fprintf (stderr
, "Predecessor: ");
1868 dump_edge_info (stderr
, e
, 0);
1869 fprintf (stderr
, "\nSuccessor: ");
1870 dump_edge_info (stderr
, e
, 1);
1871 fprintf (stderr
, "\n");
1875 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
1878 if (n_eh
&& GET_CODE (PATTERN (bb
->end
)) != RESX
1879 && !find_reg_note (bb
->end
, REG_EH_REGION
, NULL_RTX
))
1881 error ("Missing REG_EH_REGION note in the end of bb %i", bb
->index
);
1885 && (GET_CODE (bb
->end
) != JUMP_INSN
1886 || (n_branch
> 1 && (any_uncondjump_p (bb
->end
)
1887 || any_condjump_p (bb
->end
)))))
1889 error ("Too many outgoing branch edges from bb %i", bb
->index
);
1892 if (n_fallthru
&& any_uncondjump_p (bb
->end
))
1894 error ("Fallthru edge after unconditional jump %i", bb
->index
);
1897 if (n_branch
!= 1 && any_uncondjump_p (bb
->end
))
1899 error ("Wrong amount of branch edges after unconditional jump %i", bb
->index
);
1902 if (n_branch
!= 1 && any_condjump_p (bb
->end
)
1903 && JUMP_LABEL (bb
->end
) != BASIC_BLOCK (bb
->index
+ 1)->head
)
1905 error ("Wrong amount of branch edges after conditional jump %i", bb
->index
);
1908 if (n_call
&& GET_CODE (bb
->end
) != CALL_INSN
)
1910 error ("Call edges for non-call insn in bb %i", bb
->index
);
1914 && (GET_CODE (bb
->end
) != CALL_INSN
&& n_call
!= n_abnormal
)
1915 && (GET_CODE (bb
->end
) != JUMP_INSN
1916 || any_condjump_p (bb
->end
)
1917 || any_uncondjump_p (bb
->end
)))
1919 error ("Abnormal edges for no purpose in bb %i", bb
->index
);
1927 /* Ensure existence of barrier in BB with no fallthru edges. */
1928 for (insn
= bb
->end
; !insn
|| GET_CODE (insn
) != BARRIER
;
1929 insn
= NEXT_INSN (insn
))
1931 || (GET_CODE (insn
) == NOTE
1932 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_BASIC_BLOCK
))
1934 error ("missing barrier after block %i", bb
->index
);
1940 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1944 error ("basic block %d pred edge is corrupted", bb
->index
);
1945 fputs ("Predecessor: ", stderr
);
1946 dump_edge_info (stderr
, e
, 0);
1947 fputs ("\nSuccessor: ", stderr
);
1948 dump_edge_info (stderr
, e
, 1);
1949 fputc ('\n', stderr
);
1952 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
1955 for (x
= bb
->head
; x
!= NEXT_INSN (bb
->end
); x
= NEXT_INSN (x
))
1956 if (basic_block_for_insn
&& BLOCK_FOR_INSN (x
) != bb
)
1959 if (! BLOCK_FOR_INSN (x
))
1961 ("insn %d inside basic block %d but block_for_insn is NULL",
1962 INSN_UID (x
), bb
->index
);
1965 ("insn %d inside basic block %d but block_for_insn is %i",
1966 INSN_UID (x
), bb
->index
, BLOCK_FOR_INSN (x
)->index
);
1971 /* OK pointers are correct. Now check the header of basic
1972 block. It ought to contain optional CODE_LABEL followed
1973 by NOTE_BASIC_BLOCK. */
1975 if (GET_CODE (x
) == CODE_LABEL
)
1979 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1987 if (!NOTE_INSN_BASIC_BLOCK_P (x
) || NOTE_BASIC_BLOCK (x
) != bb
)
1989 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1995 /* Do checks for empty blocks her. e */
1998 for (x
= NEXT_INSN (x
); x
; x
= NEXT_INSN (x
))
2000 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2002 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2003 INSN_UID (x
), bb
->index
);
2010 if (GET_CODE (x
) == JUMP_INSN
2011 || GET_CODE (x
) == CODE_LABEL
2012 || GET_CODE (x
) == BARRIER
)
2014 error ("in basic block %d:", bb
->index
);
2015 fatal_insn ("flow control insn inside a basic block", x
);
2020 /* Complete edge checksumming for ENTRY and EXIT. */
2024 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
2025 edge_checksum
[e
->dest
->index
+ 2] += (size_t) e
;
2027 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
2028 edge_checksum
[e
->dest
->index
+ 2] -= (size_t) e
;
2031 for (i
= -2; i
< n_basic_blocks
; ++i
)
2032 if (edge_checksum
[i
+ 2])
2034 error ("basic block %i edge lists are corrupted", i
);
2038 last_bb_num_seen
= -1;
2040 for (x
= rtx_first
; x
; x
= NEXT_INSN (x
))
2042 if (NOTE_INSN_BASIC_BLOCK_P (x
))
2044 basic_block bb
= NOTE_BASIC_BLOCK (x
);
2047 if (bb
->index
!= last_bb_num_seen
+ 1)
2048 internal_error ("basic blocks not numbered consecutively");
2050 last_bb_num_seen
= bb
->index
;
2053 if (!bb_info
[INSN_UID (x
)])
2055 switch (GET_CODE (x
))
2062 /* An addr_vec is placed outside any block block. */
2064 && GET_CODE (NEXT_INSN (x
)) == JUMP_INSN
2065 && (GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_DIFF_VEC
2066 || GET_CODE (PATTERN (NEXT_INSN (x
))) == ADDR_VEC
))
2069 /* But in any case, non-deletable labels can appear anywhere. */
2073 fatal_insn ("insn outside basic block", x
);
2078 && GET_CODE (x
) == JUMP_INSN
2079 && returnjump_p (x
) && ! condjump_p (x
)
2080 && ! (NEXT_INSN (x
) && GET_CODE (NEXT_INSN (x
)) == BARRIER
))
2081 fatal_insn ("return not followed by barrier", x
);
2084 if (num_bb_notes
!= n_basic_blocks
)
2086 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2087 num_bb_notes
, n_basic_blocks
);
2090 internal_error ("verify_flow_info failed");
2094 free (last_visited
);
2095 free (edge_checksum
);
2098 /* Assume that the preceding pass has possibly eliminated jump instructions
2099 or converted the unconditional jumps. Eliminate the edges from CFG.
2100 Return true if any edges are eliminated. */
2103 purge_dead_edges (bb
)
2107 rtx insn
= bb
->end
, note
;
2108 bool purged
= false;
2110 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2111 if (GET_CODE (insn
) == INSN
2112 && (note
= find_reg_note (insn
, REG_EH_REGION
, NULL
)))
2116 if (! may_trap_p (PATTERN (insn
))
2117 || ((eqnote
= find_reg_equal_equiv_note (insn
))
2118 && ! may_trap_p (XEXP (eqnote
, 0))))
2119 remove_note (insn
, note
);
2122 /* Cleanup abnormal edges caused by throwing insns that have been
2124 if (! can_throw_internal (bb
->end
))
2125 for (e
= bb
->succ
; e
; e
= next
)
2127 next
= e
->succ_next
;
2128 if (e
->flags
& EDGE_EH
)
2131 bb
->flags
|= BB_DIRTY
;
2136 if (GET_CODE (insn
) == JUMP_INSN
)
2141 /* We do care only about conditional jumps and simplejumps. */
2142 if (!any_condjump_p (insn
)
2143 && !returnjump_p (insn
)
2144 && !simplejump_p (insn
))
2147 /* Branch probability/prediction notes are defined only for
2148 condjumps. We've possibly turned condjump into simplejump. */
2149 if (simplejump_p (insn
))
2151 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2153 remove_note (insn
, note
);
2154 while ((note
= find_reg_note (insn
, REG_BR_PRED
, NULL
)))
2155 remove_note (insn
, note
);
2158 for (e
= bb
->succ
; e
; e
= next
)
2160 next
= e
->succ_next
;
2162 /* Avoid abnormal flags to leak from computed jumps turned
2163 into simplejumps. */
2165 e
->flags
&= ~EDGE_ABNORMAL
;
2167 /* Check purposes we can have edge. */
2168 if ((e
->flags
& EDGE_FALLTHRU
)
2169 && any_condjump_p (insn
))
2171 else if (e
->dest
!= EXIT_BLOCK_PTR
2172 && e
->dest
->head
== JUMP_LABEL (insn
))
2174 else if (e
->dest
== EXIT_BLOCK_PTR
2175 && returnjump_p (insn
))
2178 bb
->flags
|= BB_DIRTY
;
2183 if (!bb
->succ
|| !purged
)
2187 fprintf (rtl_dump_file
, "Purged edges from bb %i\n", bb
->index
);
2192 /* Redistribute probabilities. */
2193 if (!bb
->succ
->succ_next
)
2195 bb
->succ
->probability
= REG_BR_PROB_BASE
;
2196 bb
->succ
->count
= bb
->count
;
2200 note
= find_reg_note (insn
, REG_BR_PROB
, NULL
);
2204 b
= BRANCH_EDGE (bb
);
2205 f
= FALLTHRU_EDGE (bb
);
2206 b
->probability
= INTVAL (XEXP (note
, 0));
2207 f
->probability
= REG_BR_PROB_BASE
- b
->probability
;
2208 b
->count
= bb
->count
* b
->probability
/ REG_BR_PROB_BASE
;
2209 f
->count
= bb
->count
* f
->probability
/ REG_BR_PROB_BASE
;
2215 /* If we don't see a jump insn, we don't know exactly why the block would
2216 have been broken at this point. Look for a simple, non-fallthru edge,
2217 as these are only created by conditional branches. If we find such an
2218 edge we know that there used to be a jump here and can then safely
2219 remove all non-fallthru edges. */
2220 for (e
= bb
->succ
; e
&& (e
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
));
2227 for (e
= bb
->succ
; e
; e
= next
)
2229 next
= e
->succ_next
;
2230 if (!(e
->flags
& EDGE_FALLTHRU
))
2232 bb
->flags
|= BB_DIRTY
;
2238 if (!bb
->succ
|| bb
->succ
->succ_next
)
2241 bb
->succ
->probability
= REG_BR_PROB_BASE
;
2242 bb
->succ
->count
= bb
->count
;
2245 fprintf (rtl_dump_file
, "Purged non-fallthru edges from bb %i\n",
2250 /* Search all basic blocks for potentially dead edges and purge them. Return
2251 true if some edge has been eliminated. */
2254 purge_all_dead_edges (update_life_p
)
2257 int i
, purged
= false;
2262 blocks
= sbitmap_alloc (n_basic_blocks
);
2263 sbitmap_zero (blocks
);
2266 for (i
= 0; i
< n_basic_blocks
; i
++)
2268 bool purged_here
= purge_dead_edges (BASIC_BLOCK (i
));
2270 purged
|= purged_here
;
2271 if (purged_here
&& update_life_p
)
2272 SET_BIT (blocks
, i
);
2275 if (update_life_p
&& purged
)
2276 update_life_info (blocks
, UPDATE_LIFE_GLOBAL
,
2277 PROP_DEATH_NOTES
| PROP_SCAN_DEAD_CODE
2278 | PROP_KILL_DEAD_CODE
);
2281 sbitmap_free (blocks
);