1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2003, 2004, 2005 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 #include "coretypes.h"
27 #include "hard-reg-set.h"
29 #include "basic-block.h"
30 #include "insn-config.h"
33 #include "cfglayout.h"
37 #include "alloc-pool.h"
39 #include "tree-pass.h"
42 /* Holds the interesting trailing notes for the function. */
43 rtx cfg_layout_function_footer
;
44 rtx cfg_layout_function_header
;
46 static rtx
skip_insns_after_block (basic_block
);
47 static void record_effective_endpoints (void);
48 static rtx
label_for_bb (basic_block
);
49 static void fixup_reorder_chain (void);
51 static void set_block_levels (tree
, int);
52 static void change_scope (rtx
, tree
, tree
);
54 void verify_insn_chain (void);
55 static void fixup_fallthru_exit_predecessor (void);
56 static tree
insn_scope (rtx
);
59 unlink_insn_chain (rtx first
, rtx last
)
61 rtx prevfirst
= PREV_INSN (first
);
62 rtx nextlast
= NEXT_INSN (last
);
64 PREV_INSN (first
) = NULL
;
65 NEXT_INSN (last
) = NULL
;
67 NEXT_INSN (prevfirst
) = nextlast
;
69 PREV_INSN (nextlast
) = prevfirst
;
71 set_last_insn (prevfirst
);
73 set_first_insn (nextlast
);
77 /* Skip over inter-block insns occurring after BB which are typically
78 associated with BB (e.g., barriers). If there are any such insns,
79 we return the last one. Otherwise, we return the end of BB. */
82 skip_insns_after_block (basic_block bb
)
84 rtx insn
, last_insn
, next_head
, prev
;
87 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
88 next_head
= BB_HEAD (bb
->next_bb
);
90 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
92 if (insn
== next_head
)
95 switch (GET_CODE (insn
))
102 switch (NOTE_LINE_NUMBER (insn
))
104 case NOTE_INSN_BLOCK_END
:
107 case NOTE_INSN_DELETED
:
108 case NOTE_INSN_DELETED_LABEL
:
119 && JUMP_P (NEXT_INSN (insn
))
120 && (GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_VEC
121 || GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_DIFF_VEC
))
123 insn
= NEXT_INSN (insn
);
136 /* It is possible to hit contradictory sequence. For instance:
142 Where barrier belongs to jump_insn, but the note does not. This can be
143 created by removing the basic block originally following
144 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
146 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
148 prev
= PREV_INSN (insn
);
150 switch (NOTE_LINE_NUMBER (insn
))
152 case NOTE_INSN_BLOCK_END
:
153 case NOTE_INSN_DELETED
:
154 case NOTE_INSN_DELETED_LABEL
:
157 reorder_insns (insn
, insn
, last_insn
);
164 /* Locate or create a label for a given basic block. */
167 label_for_bb (basic_block bb
)
169 rtx label
= BB_HEAD (bb
);
171 if (!LABEL_P (label
))
174 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
176 label
= block_label (bb
);
182 /* Locate the effective beginning and end of the insn chain for each
183 block, as defined by skip_insns_after_block above. */
186 record_effective_endpoints (void)
192 for (insn
= get_insns ();
195 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
;
196 insn
= NEXT_INSN (insn
))
198 /* No basic blocks at all? */
201 if (PREV_INSN (insn
))
202 cfg_layout_function_header
=
203 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
205 cfg_layout_function_header
= NULL_RTX
;
207 next_insn
= get_insns ();
212 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
213 bb
->il
.rtl
->header
= unlink_insn_chain (next_insn
,
214 PREV_INSN (BB_HEAD (bb
)));
215 end
= skip_insns_after_block (bb
);
216 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
217 bb
->il
.rtl
->footer
= unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
218 next_insn
= NEXT_INSN (BB_END (bb
));
221 cfg_layout_function_footer
= next_insn
;
222 if (cfg_layout_function_footer
)
223 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
226 /* Data structures representing mapping of INSN_LOCATOR into scope blocks, line
227 numbers and files. In order to be GGC friendly we need to use separate
228 varrays. This also slightly improve the memory locality in binary search.
229 The _locs array contains locators where the given property change. The
230 block_locators_blocks contains the scope block that is used for all insn
231 locator greater than corresponding block_locators_locs value and smaller
232 than the following one. Similarly for the other properties. */
233 static VEC(int,heap
) *block_locators_locs
;
234 static GTY(()) VEC(tree
,gc
) *block_locators_blocks
;
235 static VEC(int,heap
) *line_locators_locs
;
236 static VEC(int,heap
) *line_locators_lines
;
237 static VEC(int,heap
) *file_locators_locs
;
238 static GTY(()) varray_type file_locators_files
;
239 int prologue_locator
;
240 int epilogue_locator
;
242 /* During the RTL expansion the lexical blocks and line numbers are
243 represented via INSN_NOTEs. Replace them by representation using
247 insn_locators_initialize (void)
250 tree last_block
= NULL
;
253 int line_number
= 0, last_line_number
= 0;
254 const char *file_name
= NULL
, *last_file_name
= NULL
;
256 prologue_locator
= epilogue_locator
= 0;
258 block_locators_locs
= VEC_alloc (int, heap
, 32);
259 block_locators_blocks
= VEC_alloc (tree
, gc
, 32);
260 line_locators_locs
= VEC_alloc (int, heap
, 32);
261 line_locators_lines
= VEC_alloc (int, heap
, 32);
262 file_locators_locs
= VEC_alloc (int, heap
, 32);
263 VARRAY_CHAR_PTR_INIT (file_locators_files
, 32, "file_locators_files");
265 for (insn
= get_insns (); insn
; insn
= next
)
269 next
= NEXT_INSN (insn
);
273 gcc_assert (NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BLOCK_BEG
274 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BLOCK_END
);
275 if (NOTE_LINE_NUMBER (insn
) > 0)
277 expanded_location xloc
;
278 NOTE_EXPANDED_LOCATION (xloc
, insn
);
279 line_number
= xloc
.line
;
280 file_name
= xloc
.file
;
285 active
= (active_insn_p (insn
)
286 && GET_CODE (PATTERN (insn
)) != ADDR_VEC
287 && GET_CODE (PATTERN (insn
)) != ADDR_DIFF_VEC
);
289 check_block_change (insn
, &block
);
293 || (!prologue_locator
&& file_name
))
295 if (last_block
!= block
)
298 VEC_safe_push (int, heap
, block_locators_locs
, loc
);
299 VEC_safe_push (tree
, gc
, block_locators_blocks
, block
);
302 if (last_line_number
!= line_number
)
305 VEC_safe_push (int, heap
, line_locators_locs
, loc
);
306 VEC_safe_push (int, heap
, line_locators_lines
, line_number
);
307 last_line_number
= line_number
;
309 if (last_file_name
!= file_name
)
312 VEC_safe_push (int, heap
, file_locators_locs
, loc
);
313 VARRAY_PUSH_CHAR_PTR (file_locators_files
, (char *) file_name
);
314 last_file_name
= file_name
;
316 if (!prologue_locator
&& file_name
)
317 prologue_locator
= loc
;
319 epilogue_locator
= loc
;
321 INSN_LOCATOR (insn
) = loc
;
325 /* Tag the blocks with a depth number so that change_scope can find
326 the common parent easily. */
327 set_block_levels (DECL_INITIAL (cfun
->decl
), 0);
329 free_block_changes ();
333 struct tree_opt_pass pass_insn_locators_initialize
=
335 "locators", /* name */
337 insn_locators_initialize
, /* execute */
340 0, /* static_pass_number */
342 0, /* properties_required */
343 0, /* properties_provided */
344 0, /* properties_destroyed */
345 0, /* todo_flags_start */
346 TODO_dump_func
, /* todo_flags_finish */
351 into_cfg_layout_mode (void)
353 cfg_layout_initialize (0);
358 outof_cfg_layout_mode (void)
363 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
364 bb
->aux
= bb
->next_bb
;
366 cfg_layout_finalize ();
371 struct tree_opt_pass pass_into_cfg_layout_mode
=
373 "into_cfglayout", /* name */
375 into_cfg_layout_mode
, /* execute */
378 0, /* static_pass_number */
380 0, /* properties_required */
381 0, /* properties_provided */
382 0, /* properties_destroyed */
383 0, /* todo_flags_start */
384 TODO_dump_func
, /* todo_flags_finish */
388 struct tree_opt_pass pass_outof_cfg_layout_mode
=
390 "outof_cfglayout", /* name */
392 outof_cfg_layout_mode
, /* execute */
395 0, /* static_pass_number */
397 0, /* properties_required */
398 0, /* properties_provided */
399 0, /* properties_destroyed */
400 0, /* todo_flags_start */
401 TODO_dump_func
, /* todo_flags_finish */
405 /* For each lexical block, set BLOCK_NUMBER to the depth at which it is
406 found in the block tree. */
409 set_block_levels (tree block
, int level
)
413 BLOCK_NUMBER (block
) = level
;
414 set_block_levels (BLOCK_SUBBLOCKS (block
), level
+ 1);
415 block
= BLOCK_CHAIN (block
);
419 /* Return sope resulting from combination of S1 and S2. */
421 choose_inner_scope (tree s1
, tree s2
)
427 if (BLOCK_NUMBER (s1
) > BLOCK_NUMBER (s2
))
432 /* Emit lexical block notes needed to change scope from S1 to S2. */
435 change_scope (rtx orig_insn
, tree s1
, tree s2
)
437 rtx insn
= orig_insn
;
438 tree com
= NULL_TREE
;
439 tree ts1
= s1
, ts2
= s2
;
444 gcc_assert (ts1
&& ts2
);
445 if (BLOCK_NUMBER (ts1
) > BLOCK_NUMBER (ts2
))
446 ts1
= BLOCK_SUPERCONTEXT (ts1
);
447 else if (BLOCK_NUMBER (ts1
) < BLOCK_NUMBER (ts2
))
448 ts2
= BLOCK_SUPERCONTEXT (ts2
);
451 ts1
= BLOCK_SUPERCONTEXT (ts1
);
452 ts2
= BLOCK_SUPERCONTEXT (ts2
);
461 rtx note
= emit_note_before (NOTE_INSN_BLOCK_END
, insn
);
462 NOTE_BLOCK (note
) = s
;
463 s
= BLOCK_SUPERCONTEXT (s
);
470 insn
= emit_note_before (NOTE_INSN_BLOCK_BEG
, insn
);
471 NOTE_BLOCK (insn
) = s
;
472 s
= BLOCK_SUPERCONTEXT (s
);
476 /* Return lexical scope block insn belong to. */
478 insn_scope (rtx insn
)
480 int max
= VEC_length (int, block_locators_locs
);
482 int loc
= INSN_LOCATOR (insn
);
484 /* When block_locators_locs was initialized, the pro- and epilogue
485 insns didn't exist yet and can therefore not be found this way.
486 But we know that they belong to the outer most block of the
488 Without this test, the prologue would be put inside the block of
489 the first valid instruction in the function and when that first
490 insn is part of an inlined function then the low_pc of that
491 inlined function is messed up. Likewise for the epilogue and
492 the last valid instruction. */
493 if (loc
== prologue_locator
|| loc
== epilogue_locator
)
494 return DECL_INITIAL (cfun
->decl
);
500 int pos
= (min
+ max
) / 2;
501 int tmp
= VEC_index (int, block_locators_locs
, pos
);
503 if (tmp
<= loc
&& min
!= pos
)
505 else if (tmp
> loc
&& max
!= pos
)
513 return VEC_index (tree
, block_locators_blocks
, min
);
516 /* Return line number of the statement specified by the locator. */
518 locator_line (int loc
)
520 int max
= VEC_length (int, line_locators_locs
);
527 int pos
= (min
+ max
) / 2;
528 int tmp
= VEC_index (int, line_locators_locs
, pos
);
530 if (tmp
<= loc
&& min
!= pos
)
532 else if (tmp
> loc
&& max
!= pos
)
540 return VEC_index (int, line_locators_lines
, min
);
543 /* Return line number of the statement that produced this insn. */
547 return locator_line (INSN_LOCATOR (insn
));
550 /* Return source file of the statement specified by LOC. */
552 locator_file (int loc
)
554 int max
= VEC_length (int, file_locators_locs
);
561 int pos
= (min
+ max
) / 2;
562 int tmp
= VEC_index (int, file_locators_locs
, pos
);
564 if (tmp
<= loc
&& min
!= pos
)
566 else if (tmp
> loc
&& max
!= pos
)
574 return VARRAY_CHAR_PTR (file_locators_files
, min
);
577 /* Return source file of the statement that produced this insn. */
581 return locator_file (INSN_LOCATOR (insn
));
584 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
585 on the scope tree and the newly reordered instructions. */
588 reemit_insn_block_notes (void)
590 tree cur_block
= DECL_INITIAL (cfun
->decl
);
594 if (!active_insn_p (insn
))
595 insn
= next_active_insn (insn
);
596 for (; insn
; insn
= next_active_insn (insn
))
600 /* Avoid putting scope notes between jump table and its label. */
602 && (GET_CODE (PATTERN (insn
)) == ADDR_VEC
603 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
))
606 this_block
= insn_scope (insn
);
607 /* For sequences compute scope resulting from merging all scopes
608 of instructions nested inside. */
609 if (GET_CODE (PATTERN (insn
)) == SEQUENCE
)
612 rtx body
= PATTERN (insn
);
615 for (i
= 0; i
< XVECLEN (body
, 0); i
++)
616 this_block
= choose_inner_scope (this_block
,
617 insn_scope (XVECEXP (body
, 0, i
)));
622 if (this_block
!= cur_block
)
624 change_scope (insn
, cur_block
, this_block
);
625 cur_block
= this_block
;
629 /* change_scope emits before the insn, not after. */
630 note
= emit_note (NOTE_INSN_DELETED
);
631 change_scope (note
, cur_block
, DECL_INITIAL (cfun
->decl
));
637 /* Given a reorder chain, rearrange the code to match. */
640 fixup_reorder_chain (void)
642 basic_block bb
, prev_bb
;
646 if (cfg_layout_function_header
)
648 set_first_insn (cfg_layout_function_header
);
649 insn
= cfg_layout_function_header
;
650 while (NEXT_INSN (insn
))
651 insn
= NEXT_INSN (insn
);
654 /* First do the bulk reordering -- rechain the blocks without regard to
655 the needed changes to jumps and labels. */
657 for (bb
= ENTRY_BLOCK_PTR
->next_bb
, index
= NUM_FIXED_BLOCKS
;
659 bb
= bb
->aux
, index
++)
661 if (bb
->il
.rtl
->header
)
664 NEXT_INSN (insn
) = bb
->il
.rtl
->header
;
666 set_first_insn (bb
->il
.rtl
->header
);
667 PREV_INSN (bb
->il
.rtl
->header
) = insn
;
668 insn
= bb
->il
.rtl
->header
;
669 while (NEXT_INSN (insn
))
670 insn
= NEXT_INSN (insn
);
673 NEXT_INSN (insn
) = BB_HEAD (bb
);
675 set_first_insn (BB_HEAD (bb
));
676 PREV_INSN (BB_HEAD (bb
)) = insn
;
678 if (bb
->il
.rtl
->footer
)
680 NEXT_INSN (insn
) = bb
->il
.rtl
->footer
;
681 PREV_INSN (bb
->il
.rtl
->footer
) = insn
;
682 while (NEXT_INSN (insn
))
683 insn
= NEXT_INSN (insn
);
687 gcc_assert (index
== n_basic_blocks
);
689 NEXT_INSN (insn
) = cfg_layout_function_footer
;
690 if (cfg_layout_function_footer
)
691 PREV_INSN (cfg_layout_function_footer
) = insn
;
693 while (NEXT_INSN (insn
))
694 insn
= NEXT_INSN (insn
);
696 set_last_insn (insn
);
697 #ifdef ENABLE_CHECKING
698 verify_insn_chain ();
700 delete_dead_jumptables ();
702 /* Now add jumps and labels as needed to match the blocks new
705 for (bb
= ENTRY_BLOCK_PTR
->next_bb
; bb
; bb
= bb
->aux
)
707 edge e_fall
, e_taken
, e
;
712 if (EDGE_COUNT (bb
->succs
) == 0)
715 /* Find the old fallthru edge, and another non-EH edge for
717 e_taken
= e_fall
= NULL
;
719 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
720 if (e
->flags
& EDGE_FALLTHRU
)
722 else if (! (e
->flags
& EDGE_EH
))
725 bb_end_insn
= BB_END (bb
);
726 if (JUMP_P (bb_end_insn
))
728 if (any_condjump_p (bb_end_insn
))
730 /* If the old fallthru is still next, nothing to do. */
731 if (bb
->aux
== e_fall
->dest
732 || e_fall
->dest
== EXIT_BLOCK_PTR
)
735 /* The degenerated case of conditional jump jumping to the next
736 instruction can happen for jumps with side effects. We need
737 to construct a forwarder block and this will be done just
738 fine by force_nonfallthru below. */
742 /* There is another special case: if *neither* block is next,
743 such as happens at the very end of a function, then we'll
744 need to add a new unconditional jump. Choose the taken
745 edge based on known or assumed probability. */
746 else if (bb
->aux
!= e_taken
->dest
)
748 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
751 && INTVAL (XEXP (note
, 0)) < REG_BR_PROB_BASE
/ 2
752 && invert_jump (bb_end_insn
,
753 (e_fall
->dest
== EXIT_BLOCK_PTR
755 : label_for_bb (e_fall
->dest
)), 0))
757 e_fall
->flags
&= ~EDGE_FALLTHRU
;
758 #ifdef ENABLE_CHECKING
759 gcc_assert (could_fall_through
760 (e_taken
->src
, e_taken
->dest
));
762 e_taken
->flags
|= EDGE_FALLTHRU
;
763 update_br_prob_note (bb
);
764 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
768 /* If the "jumping" edge is a crossing edge, and the fall
769 through edge is non-crossing, leave things as they are. */
770 else if ((e_taken
->flags
& EDGE_CROSSING
)
771 && !(e_fall
->flags
& EDGE_CROSSING
))
774 /* Otherwise we can try to invert the jump. This will
775 basically never fail, however, keep up the pretense. */
776 else if (invert_jump (bb_end_insn
,
777 (e_fall
->dest
== EXIT_BLOCK_PTR
779 : label_for_bb (e_fall
->dest
)), 0))
781 e_fall
->flags
&= ~EDGE_FALLTHRU
;
782 #ifdef ENABLE_CHECKING
783 gcc_assert (could_fall_through
784 (e_taken
->src
, e_taken
->dest
));
786 e_taken
->flags
|= EDGE_FALLTHRU
;
787 update_br_prob_note (bb
);
793 /* Otherwise we have some return, switch or computed
794 jump. In the 99% case, there should not have been a
796 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
802 /* No fallthru implies a noreturn function with EH edges, or
803 something similarly bizarre. In any case, we don't need to
808 /* If the fallthru block is still next, nothing to do. */
809 if (bb
->aux
== e_fall
->dest
)
812 /* A fallthru to exit block. */
813 if (e_fall
->dest
== EXIT_BLOCK_PTR
)
817 /* We got here if we need to add a new jump insn. */
818 nb
= force_nonfallthru (e_fall
);
821 nb
->il
.rtl
->visited
= 1;
824 /* Don't process this new block. */
827 /* Make sure new bb is tagged for correct section (same as
828 fall-thru source, since you cannot fall-throu across
829 section boundaries). */
830 BB_COPY_PARTITION (e_fall
->src
, single_pred (bb
));
831 if (flag_reorder_blocks_and_partition
832 && targetm
.have_named_sections
833 && JUMP_P (BB_END (bb
))
834 && !any_condjump_p (BB_END (bb
))
835 && (EDGE_SUCC (bb
, 0)->flags
& EDGE_CROSSING
))
836 REG_NOTES (BB_END (bb
)) = gen_rtx_EXPR_LIST
837 (REG_CROSSING_JUMP
, NULL_RTX
, REG_NOTES (BB_END (bb
)));
841 /* Put basic_block_info in the new order. */
845 fprintf (dump_file
, "Reordered sequence:\n");
846 for (bb
= ENTRY_BLOCK_PTR
->next_bb
, index
= NUM_FIXED_BLOCKS
;
848 bb
= bb
->aux
, index
++)
850 fprintf (dump_file
, " %i ", index
);
851 if (get_bb_original (bb
))
852 fprintf (dump_file
, "duplicate of %i ",
853 get_bb_original (bb
)->index
);
854 else if (forwarder_block_p (bb
)
855 && !LABEL_P (BB_HEAD (bb
)))
856 fprintf (dump_file
, "compensation ");
858 fprintf (dump_file
, "bb %i ", bb
->index
);
859 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
863 prev_bb
= ENTRY_BLOCK_PTR
;
864 bb
= ENTRY_BLOCK_PTR
->next_bb
;
865 index
= NUM_FIXED_BLOCKS
;
867 for (; bb
; prev_bb
= bb
, bb
= bb
->aux
, index
++)
870 SET_BASIC_BLOCK (index
, bb
);
872 bb
->prev_bb
= prev_bb
;
873 prev_bb
->next_bb
= bb
;
875 prev_bb
->next_bb
= EXIT_BLOCK_PTR
;
876 EXIT_BLOCK_PTR
->prev_bb
= prev_bb
;
878 /* Annoying special case - jump around dead jumptables left in the code. */
884 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
885 if (e
->flags
& EDGE_FALLTHRU
)
888 if (e
&& !can_fallthru (e
->src
, e
->dest
))
889 force_nonfallthru (e
);
893 /* Perform sanity checks on the insn chain.
894 1. Check that next/prev pointers are consistent in both the forward and
896 2. Count insns in chain, going both directions, and check if equal.
897 3. Check that get_last_insn () returns the actual end of chain. */
900 verify_insn_chain (void)
903 int insn_cnt1
, insn_cnt2
;
905 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
907 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
908 gcc_assert (PREV_INSN (x
) == prevx
);
910 gcc_assert (prevx
== get_last_insn ());
912 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
914 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
915 gcc_assert (NEXT_INSN (x
) == nextx
);
917 gcc_assert (insn_cnt1
== insn_cnt2
);
920 /* If we have assembler epilogues, the block falling through to exit must
921 be the last one in the reordered chain when we reach final. Ensure
922 that this condition is met. */
924 fixup_fallthru_exit_predecessor (void)
928 basic_block bb
= NULL
;
930 /* This transformation is not valid before reload, because we might
931 separate a call from the instruction that copies the return
933 gcc_assert (reload_completed
);
935 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
936 if (e
->flags
& EDGE_FALLTHRU
)
941 basic_block c
= ENTRY_BLOCK_PTR
->next_bb
;
943 /* If the very first block is the one with the fall-through exit
944 edge, we have to split that block. */
947 bb
= split_block (bb
, NULL
)->dest
;
950 bb
->il
.rtl
->footer
= c
->il
.rtl
->footer
;
951 c
->il
.rtl
->footer
= NULL
;
966 /* Return true in case it is possible to duplicate the basic block BB. */
968 /* We do not want to declare the function in a header file, since it should
969 only be used through the cfghooks interface, and we do not want to move
970 it to cfgrtl.c since it would require also moving quite a lot of related
972 extern bool cfg_layout_can_duplicate_bb_p (basic_block
);
975 cfg_layout_can_duplicate_bb_p (basic_block bb
)
977 /* Do not attempt to duplicate tablejumps, as we need to unshare
978 the dispatch table. This is difficult to do, as the instructions
979 computing jump destination may be hoisted outside the basic block. */
980 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
983 /* Do not duplicate blocks containing insns that can't be copied. */
984 if (targetm
.cannot_copy_insn_p
)
986 rtx insn
= BB_HEAD (bb
);
989 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
991 if (insn
== BB_END (bb
))
993 insn
= NEXT_INSN (insn
);
1001 duplicate_insn_chain (rtx from
, rtx to
)
1005 /* Avoid updating of boundaries of previous basic block. The
1006 note will get removed from insn stream in fixup. */
1007 last
= emit_note (NOTE_INSN_DELETED
);
1009 /* Create copy at the end of INSN chain. The chain will
1010 be reordered later. */
1011 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
1013 switch (GET_CODE (insn
))
1018 /* Avoid copying of dispatch tables. We never duplicate
1019 tablejumps, so this can hit only in case the table got
1020 moved far from original jump. */
1021 if (GET_CODE (PATTERN (insn
)) == ADDR_VEC
1022 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
)
1024 emit_copy_of_insn_after (insn
, get_last_insn ());
1035 switch (NOTE_LINE_NUMBER (insn
))
1037 /* In case prologue is empty and function contain label
1038 in first BB, we may want to copy the block. */
1039 case NOTE_INSN_PROLOGUE_END
:
1041 case NOTE_INSN_DELETED
:
1042 case NOTE_INSN_DELETED_LABEL
:
1043 /* No problem to strip these. */
1044 case NOTE_INSN_EPILOGUE_BEG
:
1045 /* Debug code expect these notes to exist just once.
1046 Keep them in the master copy.
1047 ??? It probably makes more sense to duplicate them for each
1049 case NOTE_INSN_FUNCTION_BEG
:
1050 /* There is always just single entry to function. */
1051 case NOTE_INSN_BASIC_BLOCK
:
1054 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
1055 emit_note_copy (insn
);
1059 /* All other notes should have already been eliminated.
1061 gcc_assert (NOTE_LINE_NUMBER (insn
) >= 0);
1063 /* It is possible that no_line_number is set and the note
1064 won't be emitted. */
1065 emit_note_copy (insn
);
1072 insn
= NEXT_INSN (last
);
1076 /* Create a duplicate of the basic block BB. */
1078 /* We do not want to declare the function in a header file, since it should
1079 only be used through the cfghooks interface, and we do not want to move
1080 it to cfgrtl.c since it would require also moving quite a lot of related
1082 extern basic_block
cfg_layout_duplicate_bb (basic_block
);
1085 cfg_layout_duplicate_bb (basic_block bb
)
1090 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
1091 new_bb
= create_basic_block (insn
,
1092 insn
? get_last_insn () : NULL
,
1093 EXIT_BLOCK_PTR
->prev_bb
);
1095 BB_COPY_PARTITION (new_bb
, bb
);
1096 if (bb
->il
.rtl
->header
)
1098 insn
= bb
->il
.rtl
->header
;
1099 while (NEXT_INSN (insn
))
1100 insn
= NEXT_INSN (insn
);
1101 insn
= duplicate_insn_chain (bb
->il
.rtl
->header
, insn
);
1103 new_bb
->il
.rtl
->header
= unlink_insn_chain (insn
, get_last_insn ());
1106 if (bb
->il
.rtl
->footer
)
1108 insn
= bb
->il
.rtl
->footer
;
1109 while (NEXT_INSN (insn
))
1110 insn
= NEXT_INSN (insn
);
1111 insn
= duplicate_insn_chain (bb
->il
.rtl
->footer
, insn
);
1113 new_bb
->il
.rtl
->footer
= unlink_insn_chain (insn
, get_last_insn ());
1116 if (bb
->il
.rtl
->global_live_at_start
)
1118 new_bb
->il
.rtl
->global_live_at_start
= ALLOC_REG_SET (®_obstack
);
1119 new_bb
->il
.rtl
->global_live_at_end
= ALLOC_REG_SET (®_obstack
);
1120 COPY_REG_SET (new_bb
->il
.rtl
->global_live_at_start
,
1121 bb
->il
.rtl
->global_live_at_start
);
1122 COPY_REG_SET (new_bb
->il
.rtl
->global_live_at_end
,
1123 bb
->il
.rtl
->global_live_at_end
);
1129 /* Main entry point to this module - initialize the datastructures for
1130 CFG layout changes. It keeps LOOPS up-to-date if not null.
1132 FLAGS is a set of additional flags to pass to cleanup_cfg(). It should
1133 include CLEANUP_UPDATE_LIFE if liveness information must be kept up
1137 cfg_layout_initialize (unsigned int flags
)
1139 initialize_original_copy_tables ();
1141 cfg_layout_rtl_register_cfg_hooks ();
1143 record_effective_endpoints ();
1145 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
1148 /* Splits superblocks. */
1150 break_superblocks (void)
1152 sbitmap superblocks
;
1156 superblocks
= sbitmap_alloc (last_basic_block
);
1157 sbitmap_zero (superblocks
);
1160 if (bb
->flags
& BB_SUPERBLOCK
)
1162 bb
->flags
&= ~BB_SUPERBLOCK
;
1163 SET_BIT (superblocks
, bb
->index
);
1169 rebuild_jump_labels (get_insns ());
1170 find_many_sub_basic_blocks (superblocks
);
1176 /* Finalize the changes: reorder insn list according to the sequence specified
1177 by aux pointers, enter compensation code, rebuild scope forest. */
1180 cfg_layout_finalize (void)
1184 #ifdef ENABLE_CHECKING
1185 verify_flow_info ();
1187 rtl_register_cfg_hooks ();
1188 if (reload_completed
1189 #ifdef HAVE_epilogue
1193 fixup_fallthru_exit_predecessor ();
1194 fixup_reorder_chain ();
1196 #ifdef ENABLE_CHECKING
1197 verify_insn_chain ();
1199 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1201 bb
->il
.rtl
->header
= bb
->il
.rtl
->footer
= NULL
;
1203 bb
->il
.rtl
->visited
= 0;
1206 #ifdef ENABLE_CHECKING
1207 verify_flow_info ();
1210 free_original_copy_tables ();
1213 /* Checks whether all N blocks in BBS array can be copied. */
1215 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1221 for (i
= 0; i
< n
; i
++)
1222 bbs
[i
]->flags
|= BB_DUPLICATED
;
1224 for (i
= 0; i
< n
; i
++)
1226 /* In case we should redirect abnormal edge during duplication, fail. */
1228 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1229 if ((e
->flags
& EDGE_ABNORMAL
)
1230 && (e
->dest
->flags
& BB_DUPLICATED
))
1236 if (!can_duplicate_block_p (bbs
[i
]))
1244 for (i
= 0; i
< n
; i
++)
1245 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1250 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1251 are placed into array NEW_BBS in the same order. Edges from basic blocks
1252 in BBS are also duplicated and copies of those of them
1253 that lead into BBS are redirected to appropriate newly created block. The
1254 function assigns bbs into loops (copy of basic block bb is assigned to
1255 bb->loop_father->copy loop, so this must be set up correctly in advance)
1256 and updates dominators locally (LOOPS structure that contains the information
1257 about dominators is passed to enable this).
1259 BASE is the superloop to that basic block belongs; if its header or latch
1260 is copied, we do not set the new blocks as header or latch.
1262 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1263 also in the same order.
1265 Newly created basic blocks are put after the basic block AFTER in the
1266 instruction stream, and the order of the blocks in BBS array is preserved. */
1269 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1270 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1271 struct loop
*base
, basic_block after
)
1274 basic_block bb
, new_bb
, dom_bb
;
1277 /* Duplicate bbs, update dominators, assign bbs to loops. */
1278 for (i
= 0; i
< n
; i
++)
1282 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
);
1284 bb
->flags
|= BB_DUPLICATED
;
1285 /* Possibly set loop header. */
1286 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1287 new_bb
->loop_father
->header
= new_bb
;
1289 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1290 new_bb
->loop_father
->latch
= new_bb
;
1293 /* Set dominators. */
1294 for (i
= 0; i
< n
; i
++)
1297 new_bb
= new_bbs
[i
];
1299 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1300 if (dom_bb
->flags
& BB_DUPLICATED
)
1302 dom_bb
= get_bb_copy (dom_bb
);
1303 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1307 /* Redirect edges. */
1308 for (j
= 0; j
< num_edges
; j
++)
1309 new_edges
[j
] = NULL
;
1310 for (i
= 0; i
< n
; i
++)
1313 new_bb
= new_bbs
[i
];
1316 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1318 for (j
= 0; j
< num_edges
; j
++)
1319 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1322 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1324 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1328 /* Clear information about duplicates. */
1329 for (i
= 0; i
< n
; i
++)
1330 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1333 #include "gt-cfglayout.h"