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 ();
701 /* Now add jumps and labels as needed to match the blocks new
704 for (bb
= ENTRY_BLOCK_PTR
->next_bb
; bb
; bb
= bb
->aux
)
706 edge e_fall
, e_taken
, e
;
711 if (EDGE_COUNT (bb
->succs
) == 0)
714 /* Find the old fallthru edge, and another non-EH edge for
716 e_taken
= e_fall
= NULL
;
718 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
719 if (e
->flags
& EDGE_FALLTHRU
)
721 else if (! (e
->flags
& EDGE_EH
))
724 bb_end_insn
= BB_END (bb
);
725 if (JUMP_P (bb_end_insn
))
727 if (any_condjump_p (bb_end_insn
))
729 /* If the old fallthru is still next, nothing to do. */
730 if (bb
->aux
== e_fall
->dest
731 || e_fall
->dest
== EXIT_BLOCK_PTR
)
734 /* The degenerated case of conditional jump jumping to the next
735 instruction can happen for jumps with side effects. We need
736 to construct a forwarder block and this will be done just
737 fine by force_nonfallthru below. */
741 /* There is another special case: if *neither* block is next,
742 such as happens at the very end of a function, then we'll
743 need to add a new unconditional jump. Choose the taken
744 edge based on known or assumed probability. */
745 else if (bb
->aux
!= e_taken
->dest
)
747 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
750 && INTVAL (XEXP (note
, 0)) < REG_BR_PROB_BASE
/ 2
751 && invert_jump (bb_end_insn
,
752 (e_fall
->dest
== EXIT_BLOCK_PTR
754 : label_for_bb (e_fall
->dest
)), 0))
756 e_fall
->flags
&= ~EDGE_FALLTHRU
;
757 #ifdef ENABLE_CHECKING
758 gcc_assert (could_fall_through
759 (e_taken
->src
, e_taken
->dest
));
761 e_taken
->flags
|= EDGE_FALLTHRU
;
762 update_br_prob_note (bb
);
763 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
767 /* If the "jumping" edge is a crossing edge, and the fall
768 through edge is non-crossing, leave things as they are. */
769 else if ((e_taken
->flags
& EDGE_CROSSING
)
770 && !(e_fall
->flags
& EDGE_CROSSING
))
773 /* Otherwise we can try to invert the jump. This will
774 basically never fail, however, keep up the pretense. */
775 else if (invert_jump (bb_end_insn
,
776 (e_fall
->dest
== EXIT_BLOCK_PTR
778 : label_for_bb (e_fall
->dest
)), 0))
780 e_fall
->flags
&= ~EDGE_FALLTHRU
;
781 #ifdef ENABLE_CHECKING
782 gcc_assert (could_fall_through
783 (e_taken
->src
, e_taken
->dest
));
785 e_taken
->flags
|= EDGE_FALLTHRU
;
786 update_br_prob_note (bb
);
792 /* Otherwise we have some return, switch or computed
793 jump. In the 99% case, there should not have been a
795 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
801 /* No fallthru implies a noreturn function with EH edges, or
802 something similarly bizarre. In any case, we don't need to
807 /* If the fallthru block is still next, nothing to do. */
808 if (bb
->aux
== e_fall
->dest
)
811 /* A fallthru to exit block. */
812 if (e_fall
->dest
== EXIT_BLOCK_PTR
)
816 /* We got here if we need to add a new jump insn. */
817 nb
= force_nonfallthru (e_fall
);
820 nb
->il
.rtl
->visited
= 1;
823 /* Don't process this new block. */
826 /* Make sure new bb is tagged for correct section (same as
827 fall-thru source, since you cannot fall-throu across
828 section boundaries). */
829 BB_COPY_PARTITION (e_fall
->src
, single_pred (bb
));
830 if (flag_reorder_blocks_and_partition
831 && targetm
.have_named_sections
832 && JUMP_P (BB_END (bb
))
833 && !any_condjump_p (BB_END (bb
))
834 && (EDGE_SUCC (bb
, 0)->flags
& EDGE_CROSSING
))
835 REG_NOTES (BB_END (bb
)) = gen_rtx_EXPR_LIST
836 (REG_CROSSING_JUMP
, NULL_RTX
, REG_NOTES (BB_END (bb
)));
840 /* Put basic_block_info in the new order. */
844 fprintf (dump_file
, "Reordered sequence:\n");
845 for (bb
= ENTRY_BLOCK_PTR
->next_bb
, index
= NUM_FIXED_BLOCKS
;
847 bb
= bb
->aux
, index
++)
849 fprintf (dump_file
, " %i ", index
);
850 if (get_bb_original (bb
))
851 fprintf (dump_file
, "duplicate of %i ",
852 get_bb_original (bb
)->index
);
853 else if (forwarder_block_p (bb
)
854 && !LABEL_P (BB_HEAD (bb
)))
855 fprintf (dump_file
, "compensation ");
857 fprintf (dump_file
, "bb %i ", bb
->index
);
858 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
862 prev_bb
= ENTRY_BLOCK_PTR
;
863 bb
= ENTRY_BLOCK_PTR
->next_bb
;
864 index
= NUM_FIXED_BLOCKS
;
866 for (; bb
; prev_bb
= bb
, bb
= bb
->aux
, index
++)
869 SET_BASIC_BLOCK (index
, bb
);
871 bb
->prev_bb
= prev_bb
;
872 prev_bb
->next_bb
= bb
;
874 prev_bb
->next_bb
= EXIT_BLOCK_PTR
;
875 EXIT_BLOCK_PTR
->prev_bb
= prev_bb
;
877 /* Annoying special case - jump around dead jumptables left in the code. */
883 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
884 if (e
->flags
& EDGE_FALLTHRU
)
887 if (e
&& !can_fallthru (e
->src
, e
->dest
))
888 force_nonfallthru (e
);
892 /* Perform sanity checks on the insn chain.
893 1. Check that next/prev pointers are consistent in both the forward and
895 2. Count insns in chain, going both directions, and check if equal.
896 3. Check that get_last_insn () returns the actual end of chain. */
899 verify_insn_chain (void)
902 int insn_cnt1
, insn_cnt2
;
904 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
906 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
907 gcc_assert (PREV_INSN (x
) == prevx
);
909 gcc_assert (prevx
== get_last_insn ());
911 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
913 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
914 gcc_assert (NEXT_INSN (x
) == nextx
);
916 gcc_assert (insn_cnt1
== insn_cnt2
);
919 /* If we have assembler epilogues, the block falling through to exit must
920 be the last one in the reordered chain when we reach final. Ensure
921 that this condition is met. */
923 fixup_fallthru_exit_predecessor (void)
927 basic_block bb
= NULL
;
929 /* This transformation is not valid before reload, because we might
930 separate a call from the instruction that copies the return
932 gcc_assert (reload_completed
);
934 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
935 if (e
->flags
& EDGE_FALLTHRU
)
940 basic_block c
= ENTRY_BLOCK_PTR
->next_bb
;
942 /* If the very first block is the one with the fall-through exit
943 edge, we have to split that block. */
946 bb
= split_block (bb
, NULL
)->dest
;
949 bb
->il
.rtl
->footer
= c
->il
.rtl
->footer
;
950 c
->il
.rtl
->footer
= NULL
;
965 /* Return true in case it is possible to duplicate the basic block BB. */
967 /* We do not want to declare the function in a header file, since it should
968 only be used through the cfghooks interface, and we do not want to move
969 it to cfgrtl.c since it would require also moving quite a lot of related
971 extern bool cfg_layout_can_duplicate_bb_p (basic_block
);
974 cfg_layout_can_duplicate_bb_p (basic_block bb
)
976 /* Do not attempt to duplicate tablejumps, as we need to unshare
977 the dispatch table. This is difficult to do, as the instructions
978 computing jump destination may be hoisted outside the basic block. */
979 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
982 /* Do not duplicate blocks containing insns that can't be copied. */
983 if (targetm
.cannot_copy_insn_p
)
985 rtx insn
= BB_HEAD (bb
);
988 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
990 if (insn
== BB_END (bb
))
992 insn
= NEXT_INSN (insn
);
1000 duplicate_insn_chain (rtx from
, rtx to
)
1004 /* Avoid updating of boundaries of previous basic block. The
1005 note will get removed from insn stream in fixup. */
1006 last
= emit_note (NOTE_INSN_DELETED
);
1008 /* Create copy at the end of INSN chain. The chain will
1009 be reordered later. */
1010 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
1012 switch (GET_CODE (insn
))
1017 /* Avoid copying of dispatch tables. We never duplicate
1018 tablejumps, so this can hit only in case the table got
1019 moved far from original jump. */
1020 if (GET_CODE (PATTERN (insn
)) == ADDR_VEC
1021 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
)
1023 emit_copy_of_insn_after (insn
, get_last_insn ());
1034 switch (NOTE_LINE_NUMBER (insn
))
1036 /* In case prologue is empty and function contain label
1037 in first BB, we may want to copy the block. */
1038 case NOTE_INSN_PROLOGUE_END
:
1040 case NOTE_INSN_DELETED
:
1041 case NOTE_INSN_DELETED_LABEL
:
1042 /* No problem to strip these. */
1043 case NOTE_INSN_EPILOGUE_BEG
:
1044 /* Debug code expect these notes to exist just once.
1045 Keep them in the master copy.
1046 ??? It probably makes more sense to duplicate them for each
1048 case NOTE_INSN_FUNCTION_BEG
:
1049 /* There is always just single entry to function. */
1050 case NOTE_INSN_BASIC_BLOCK
:
1053 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
1054 emit_note_copy (insn
);
1058 /* All other notes should have already been eliminated.
1060 gcc_assert (NOTE_LINE_NUMBER (insn
) >= 0);
1062 /* It is possible that no_line_number is set and the note
1063 won't be emitted. */
1064 emit_note_copy (insn
);
1071 insn
= NEXT_INSN (last
);
1075 /* Create a duplicate of the basic block BB. */
1077 /* We do not want to declare the function in a header file, since it should
1078 only be used through the cfghooks interface, and we do not want to move
1079 it to cfgrtl.c since it would require also moving quite a lot of related
1081 extern basic_block
cfg_layout_duplicate_bb (basic_block
);
1084 cfg_layout_duplicate_bb (basic_block bb
)
1089 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
1090 new_bb
= create_basic_block (insn
,
1091 insn
? get_last_insn () : NULL
,
1092 EXIT_BLOCK_PTR
->prev_bb
);
1094 BB_COPY_PARTITION (new_bb
, bb
);
1095 if (bb
->il
.rtl
->header
)
1097 insn
= bb
->il
.rtl
->header
;
1098 while (NEXT_INSN (insn
))
1099 insn
= NEXT_INSN (insn
);
1100 insn
= duplicate_insn_chain (bb
->il
.rtl
->header
, insn
);
1102 new_bb
->il
.rtl
->header
= unlink_insn_chain (insn
, get_last_insn ());
1105 if (bb
->il
.rtl
->footer
)
1107 insn
= bb
->il
.rtl
->footer
;
1108 while (NEXT_INSN (insn
))
1109 insn
= NEXT_INSN (insn
);
1110 insn
= duplicate_insn_chain (bb
->il
.rtl
->footer
, insn
);
1112 new_bb
->il
.rtl
->footer
= unlink_insn_chain (insn
, get_last_insn ());
1115 if (bb
->il
.rtl
->global_live_at_start
)
1117 new_bb
->il
.rtl
->global_live_at_start
= ALLOC_REG_SET (®_obstack
);
1118 new_bb
->il
.rtl
->global_live_at_end
= ALLOC_REG_SET (®_obstack
);
1119 COPY_REG_SET (new_bb
->il
.rtl
->global_live_at_start
,
1120 bb
->il
.rtl
->global_live_at_start
);
1121 COPY_REG_SET (new_bb
->il
.rtl
->global_live_at_end
,
1122 bb
->il
.rtl
->global_live_at_end
);
1128 /* Main entry point to this module - initialize the datastructures for
1129 CFG layout changes. It keeps LOOPS up-to-date if not null.
1131 FLAGS is a set of additional flags to pass to cleanup_cfg(). It should
1132 include CLEANUP_UPDATE_LIFE if liveness information must be kept up
1136 cfg_layout_initialize (unsigned int flags
)
1138 initialize_original_copy_tables ();
1140 cfg_layout_rtl_register_cfg_hooks ();
1142 record_effective_endpoints ();
1144 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
1147 /* Splits superblocks. */
1149 break_superblocks (void)
1151 sbitmap superblocks
;
1155 superblocks
= sbitmap_alloc (last_basic_block
);
1156 sbitmap_zero (superblocks
);
1159 if (bb
->flags
& BB_SUPERBLOCK
)
1161 bb
->flags
&= ~BB_SUPERBLOCK
;
1162 SET_BIT (superblocks
, bb
->index
);
1168 rebuild_jump_labels (get_insns ());
1169 find_many_sub_basic_blocks (superblocks
);
1175 /* Finalize the changes: reorder insn list according to the sequence specified
1176 by aux pointers, enter compensation code, rebuild scope forest. */
1179 cfg_layout_finalize (void)
1183 #ifdef ENABLE_CHECKING
1184 verify_flow_info ();
1186 rtl_register_cfg_hooks ();
1187 if (reload_completed
1188 #ifdef HAVE_epilogue
1192 fixup_fallthru_exit_predecessor ();
1193 fixup_reorder_chain ();
1195 rebuild_jump_labels (get_insns ());
1196 delete_dead_jumptables ();
1198 #ifdef ENABLE_CHECKING
1199 verify_insn_chain ();
1201 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1203 bb
->il
.rtl
->header
= bb
->il
.rtl
->footer
= NULL
;
1205 bb
->il
.rtl
->visited
= 0;
1208 #ifdef ENABLE_CHECKING
1209 verify_flow_info ();
1212 free_original_copy_tables ();
1215 /* Checks whether all N blocks in BBS array can be copied. */
1217 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1223 for (i
= 0; i
< n
; i
++)
1224 bbs
[i
]->flags
|= BB_DUPLICATED
;
1226 for (i
= 0; i
< n
; i
++)
1228 /* In case we should redirect abnormal edge during duplication, fail. */
1230 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1231 if ((e
->flags
& EDGE_ABNORMAL
)
1232 && (e
->dest
->flags
& BB_DUPLICATED
))
1238 if (!can_duplicate_block_p (bbs
[i
]))
1246 for (i
= 0; i
< n
; i
++)
1247 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1252 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1253 are placed into array NEW_BBS in the same order. Edges from basic blocks
1254 in BBS are also duplicated and copies of those of them
1255 that lead into BBS are redirected to appropriate newly created block. The
1256 function assigns bbs into loops (copy of basic block bb is assigned to
1257 bb->loop_father->copy loop, so this must be set up correctly in advance)
1258 and updates dominators locally (LOOPS structure that contains the information
1259 about dominators is passed to enable this).
1261 BASE is the superloop to that basic block belongs; if its header or latch
1262 is copied, we do not set the new blocks as header or latch.
1264 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1265 also in the same order.
1267 Newly created basic blocks are put after the basic block AFTER in the
1268 instruction stream, and the order of the blocks in BBS array is preserved. */
1271 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1272 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1273 struct loop
*base
, basic_block after
)
1276 basic_block bb
, new_bb
, dom_bb
;
1279 /* Duplicate bbs, update dominators, assign bbs to loops. */
1280 for (i
= 0; i
< n
; i
++)
1284 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
);
1286 bb
->flags
|= BB_DUPLICATED
;
1287 /* Possibly set loop header. */
1288 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1289 new_bb
->loop_father
->header
= new_bb
;
1291 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1292 new_bb
->loop_father
->latch
= new_bb
;
1295 /* Set dominators. */
1296 for (i
= 0; i
< n
; i
++)
1299 new_bb
= new_bbs
[i
];
1301 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1302 if (dom_bb
->flags
& BB_DUPLICATED
)
1304 dom_bb
= get_bb_copy (dom_bb
);
1305 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1309 /* Redirect edges. */
1310 for (j
= 0; j
< num_edges
; j
++)
1311 new_edges
[j
] = NULL
;
1312 for (i
= 0; i
< n
; i
++)
1315 new_bb
= new_bbs
[i
];
1318 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1320 for (j
= 0; j
< num_edges
; j
++)
1321 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1324 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1326 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1330 /* Clear information about duplicates. */
1331 for (i
= 0; i
< n
; i
++)
1332 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1335 #include "gt-cfglayout.h"