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"
41 /* Holds the interesting trailing notes for the function. */
42 rtx cfg_layout_function_footer
, cfg_layout_function_header
;
44 static rtx
skip_insns_after_block (basic_block
);
45 static void record_effective_endpoints (void);
46 static rtx
label_for_bb (basic_block
);
47 static void fixup_reorder_chain (void);
49 static void set_block_levels (tree
, int);
50 static void change_scope (rtx
, tree
, tree
);
52 void verify_insn_chain (void);
53 static void fixup_fallthru_exit_predecessor (void);
54 static tree
insn_scope (rtx
);
57 unlink_insn_chain (rtx first
, rtx last
)
59 rtx prevfirst
= PREV_INSN (first
);
60 rtx nextlast
= NEXT_INSN (last
);
62 PREV_INSN (first
) = NULL
;
63 NEXT_INSN (last
) = NULL
;
65 NEXT_INSN (prevfirst
) = nextlast
;
67 PREV_INSN (nextlast
) = prevfirst
;
69 set_last_insn (prevfirst
);
71 set_first_insn (nextlast
);
75 /* Skip over inter-block insns occurring after BB which are typically
76 associated with BB (e.g., barriers). If there are any such insns,
77 we return the last one. Otherwise, we return the end of BB. */
80 skip_insns_after_block (basic_block bb
)
82 rtx insn
, last_insn
, next_head
, prev
;
85 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
86 next_head
= BB_HEAD (bb
->next_bb
);
88 for (last_insn
= insn
= BB_END (bb
); (insn
= NEXT_INSN (insn
)) != 0; )
90 if (insn
== next_head
)
93 switch (GET_CODE (insn
))
100 switch (NOTE_LINE_NUMBER (insn
))
102 case NOTE_INSN_LOOP_END
:
103 case NOTE_INSN_BLOCK_END
:
106 case NOTE_INSN_DELETED
:
107 case NOTE_INSN_DELETED_LABEL
:
118 && JUMP_P (NEXT_INSN (insn
))
119 && (GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_VEC
120 || GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_DIFF_VEC
))
122 insn
= NEXT_INSN (insn
);
135 /* It is possible to hit contradictory sequence. For instance:
141 Where barrier belongs to jump_insn, but the note does not. This can be
142 created by removing the basic block originally following
143 NOTE_INSN_LOOP_BEG. In such case reorder the notes. */
145 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
147 prev
= PREV_INSN (insn
);
149 switch (NOTE_LINE_NUMBER (insn
))
151 case NOTE_INSN_LOOP_END
:
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 ());
227 DEF_VEC_ALLOC_I(int,heap
);
229 /* Data structures representing mapping of INSN_LOCATOR into scope blocks, line
230 numbers and files. In order to be GGC friendly we need to use separate
231 varrays. This also slightly improve the memory locality in binary search.
232 The _locs array contains locators where the given property change. The
233 block_locators_blocks contains the scope block that is used for all insn
234 locator greater than corresponding block_locators_locs value and smaller
235 than the following one. Similarly for the other properties. */
236 static VEC(int,heap
) *block_locators_locs
;
237 static GTY(()) VEC(tree
,gc
) *block_locators_blocks
;
238 static VEC(int,heap
) *line_locators_locs
;
239 static VEC(int,heap
) *line_locators_lines
;
240 static VEC(int,heap
) *file_locators_locs
;
241 static GTY(()) varray_type file_locators_files
;
242 int prologue_locator
;
243 int epilogue_locator
;
245 /* During the RTL expansion the lexical blocks and line numbers are
246 represented via INSN_NOTEs. Replace them by representation using
250 insn_locators_initialize (void)
253 tree last_block
= NULL
;
256 int line_number
= 0, last_line_number
= 0;
257 const char *file_name
= NULL
, *last_file_name
= NULL
;
259 prologue_locator
= epilogue_locator
= 0;
261 block_locators_locs
= VEC_alloc (int, heap
, 32);
262 block_locators_blocks
= VEC_alloc (tree
, gc
, 32);
263 line_locators_locs
= VEC_alloc (int, heap
, 32);
264 line_locators_lines
= VEC_alloc (int, heap
, 32);
265 file_locators_locs
= VEC_alloc (int, heap
, 32);
266 VARRAY_CHAR_PTR_INIT (file_locators_files
, 32, "file_locators_files");
268 for (insn
= get_insns (); insn
; insn
= next
)
272 next
= NEXT_INSN (insn
);
276 gcc_assert (NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BLOCK_BEG
277 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BLOCK_END
);
278 if (NOTE_LINE_NUMBER (insn
) > 0)
280 expanded_location xloc
;
281 NOTE_EXPANDED_LOCATION (xloc
, insn
);
282 line_number
= xloc
.line
;
283 file_name
= xloc
.file
;
287 active
= (active_insn_p (insn
)
288 && GET_CODE (PATTERN (insn
)) != ADDR_VEC
289 && GET_CODE (PATTERN (insn
)) != ADDR_DIFF_VEC
);
291 check_block_change (insn
, &block
);
295 || (!prologue_locator
&& file_name
))
297 if (last_block
!= block
)
300 VEC_safe_push (int, heap
, block_locators_locs
, loc
);
301 VEC_safe_push (tree
, gc
, block_locators_blocks
, block
);
304 if (last_line_number
!= line_number
)
307 VEC_safe_push (int, heap
, line_locators_locs
, loc
);
308 VEC_safe_push (int, heap
, line_locators_lines
, line_number
);
309 last_line_number
= line_number
;
311 if (last_file_name
!= file_name
)
314 VEC_safe_push (int, heap
, file_locators_locs
, loc
);
315 VARRAY_PUSH_CHAR_PTR (file_locators_files
, (char *) file_name
);
316 last_file_name
= file_name
;
318 if (!prologue_locator
&& file_name
)
319 prologue_locator
= loc
;
321 epilogue_locator
= loc
;
323 INSN_LOCATOR (insn
) = loc
;
327 /* Tag the blocks with a depth number so that change_scope can find
328 the common parent easily. */
329 set_block_levels (DECL_INITIAL (cfun
->decl
), 0);
331 free_block_changes ();
335 struct tree_opt_pass pass_insn_locators_initialize
=
337 "locators", /* name */
339 insn_locators_initialize
, /* execute */
342 0, /* static_pass_number */
344 0, /* properties_required */
345 0, /* properties_provided */
346 0, /* properties_destroyed */
347 0, /* todo_flags_start */
348 TODO_dump_func
, /* todo_flags_finish */
353 /* For each lexical block, set BLOCK_NUMBER to the depth at which it is
354 found in the block tree. */
357 set_block_levels (tree block
, int level
)
361 BLOCK_NUMBER (block
) = level
;
362 set_block_levels (BLOCK_SUBBLOCKS (block
), level
+ 1);
363 block
= BLOCK_CHAIN (block
);
367 /* Return sope resulting from combination of S1 and S2. */
369 choose_inner_scope (tree s1
, tree s2
)
375 if (BLOCK_NUMBER (s1
) > BLOCK_NUMBER (s2
))
380 /* Emit lexical block notes needed to change scope from S1 to S2. */
383 change_scope (rtx orig_insn
, tree s1
, tree s2
)
385 rtx insn
= orig_insn
;
386 tree com
= NULL_TREE
;
387 tree ts1
= s1
, ts2
= s2
;
392 gcc_assert (ts1
&& ts2
);
393 if (BLOCK_NUMBER (ts1
) > BLOCK_NUMBER (ts2
))
394 ts1
= BLOCK_SUPERCONTEXT (ts1
);
395 else if (BLOCK_NUMBER (ts1
) < BLOCK_NUMBER (ts2
))
396 ts2
= BLOCK_SUPERCONTEXT (ts2
);
399 ts1
= BLOCK_SUPERCONTEXT (ts1
);
400 ts2
= BLOCK_SUPERCONTEXT (ts2
);
409 rtx note
= emit_note_before (NOTE_INSN_BLOCK_END
, insn
);
410 NOTE_BLOCK (note
) = s
;
411 s
= BLOCK_SUPERCONTEXT (s
);
418 insn
= emit_note_before (NOTE_INSN_BLOCK_BEG
, insn
);
419 NOTE_BLOCK (insn
) = s
;
420 s
= BLOCK_SUPERCONTEXT (s
);
424 /* Return lexical scope block insn belong to. */
426 insn_scope (rtx insn
)
428 int max
= VEC_length (int, block_locators_locs
);
430 int loc
= INSN_LOCATOR (insn
);
432 /* When block_locators_locs was initialized, the pro- and epilogue
433 insns didn't exist yet and can therefore not be found this way.
434 But we know that they belong to the outer most block of the
436 Without this test, the prologue would be put inside the block of
437 the first valid instruction in the function and when that first
438 insn is part of an inlined function then the low_pc of that
439 inlined function is messed up. Likewise for the epilogue and
440 the last valid instruction. */
441 if (loc
== prologue_locator
|| loc
== epilogue_locator
)
442 return DECL_INITIAL (cfun
->decl
);
448 int pos
= (min
+ max
) / 2;
449 int tmp
= VEC_index (int, block_locators_locs
, pos
);
451 if (tmp
<= loc
&& min
!= pos
)
453 else if (tmp
> loc
&& max
!= pos
)
461 return VEC_index (tree
, block_locators_blocks
, min
);
464 /* Return line number of the statement specified by the locator. */
466 locator_line (int loc
)
468 int max
= VEC_length (int, line_locators_locs
);
475 int pos
= (min
+ max
) / 2;
476 int tmp
= VEC_index (int, line_locators_locs
, pos
);
478 if (tmp
<= loc
&& min
!= pos
)
480 else if (tmp
> loc
&& max
!= pos
)
488 return VEC_index (int, line_locators_lines
, min
);
491 /* Return line number of the statement that produced this insn. */
495 return locator_line (INSN_LOCATOR (insn
));
498 /* Return source file of the statement specified by LOC. */
500 locator_file (int loc
)
502 int max
= VEC_length (int, file_locators_locs
);
509 int pos
= (min
+ max
) / 2;
510 int tmp
= VEC_index (int, file_locators_locs
, pos
);
512 if (tmp
<= loc
&& min
!= pos
)
514 else if (tmp
> loc
&& max
!= pos
)
522 return VARRAY_CHAR_PTR (file_locators_files
, min
);
525 /* Return source file of the statement that produced this insn. */
529 return locator_file (INSN_LOCATOR (insn
));
532 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
533 on the scope tree and the newly reordered instructions. */
536 reemit_insn_block_notes (void)
538 tree cur_block
= DECL_INITIAL (cfun
->decl
);
542 if (!active_insn_p (insn
))
543 insn
= next_active_insn (insn
);
544 for (; insn
; insn
= next_active_insn (insn
))
548 /* Avoid putting scope notes between jump table and its label. */
550 && (GET_CODE (PATTERN (insn
)) == ADDR_VEC
551 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
))
554 this_block
= insn_scope (insn
);
555 /* For sequences compute scope resulting from merging all scopes
556 of instructions nested inside. */
557 if (GET_CODE (PATTERN (insn
)) == SEQUENCE
)
560 rtx body
= PATTERN (insn
);
563 for (i
= 0; i
< XVECLEN (body
, 0); i
++)
564 this_block
= choose_inner_scope (this_block
,
565 insn_scope (XVECEXP (body
, 0, i
)));
570 if (this_block
!= cur_block
)
572 change_scope (insn
, cur_block
, this_block
);
573 cur_block
= this_block
;
577 /* change_scope emits before the insn, not after. */
578 note
= emit_note (NOTE_INSN_DELETED
);
579 change_scope (note
, cur_block
, DECL_INITIAL (cfun
->decl
));
585 /* Given a reorder chain, rearrange the code to match. */
588 fixup_reorder_chain (void)
590 basic_block bb
, prev_bb
;
594 if (cfg_layout_function_header
)
596 set_first_insn (cfg_layout_function_header
);
597 insn
= cfg_layout_function_header
;
598 while (NEXT_INSN (insn
))
599 insn
= NEXT_INSN (insn
);
602 /* First do the bulk reordering -- rechain the blocks without regard to
603 the needed changes to jumps and labels. */
605 for (bb
= ENTRY_BLOCK_PTR
->next_bb
, index
= NUM_FIXED_BLOCKS
;
607 bb
= bb
->aux
, index
++)
609 if (bb
->il
.rtl
->header
)
612 NEXT_INSN (insn
) = bb
->il
.rtl
->header
;
614 set_first_insn (bb
->il
.rtl
->header
);
615 PREV_INSN (bb
->il
.rtl
->header
) = insn
;
616 insn
= bb
->il
.rtl
->header
;
617 while (NEXT_INSN (insn
))
618 insn
= NEXT_INSN (insn
);
621 NEXT_INSN (insn
) = BB_HEAD (bb
);
623 set_first_insn (BB_HEAD (bb
));
624 PREV_INSN (BB_HEAD (bb
)) = insn
;
626 if (bb
->il
.rtl
->footer
)
628 NEXT_INSN (insn
) = bb
->il
.rtl
->footer
;
629 PREV_INSN (bb
->il
.rtl
->footer
) = insn
;
630 while (NEXT_INSN (insn
))
631 insn
= NEXT_INSN (insn
);
635 gcc_assert (index
== n_basic_blocks
);
637 NEXT_INSN (insn
) = cfg_layout_function_footer
;
638 if (cfg_layout_function_footer
)
639 PREV_INSN (cfg_layout_function_footer
) = insn
;
641 while (NEXT_INSN (insn
))
642 insn
= NEXT_INSN (insn
);
644 set_last_insn (insn
);
645 #ifdef ENABLE_CHECKING
646 verify_insn_chain ();
648 delete_dead_jumptables ();
650 /* Now add jumps and labels as needed to match the blocks new
653 for (bb
= ENTRY_BLOCK_PTR
->next_bb
; bb
; bb
= bb
->aux
)
655 edge e_fall
, e_taken
, e
;
660 if (EDGE_COUNT (bb
->succs
) == 0)
663 /* Find the old fallthru edge, and another non-EH edge for
665 e_taken
= e_fall
= NULL
;
667 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
668 if (e
->flags
& EDGE_FALLTHRU
)
670 else if (! (e
->flags
& EDGE_EH
))
673 bb_end_insn
= BB_END (bb
);
674 if (JUMP_P (bb_end_insn
))
676 if (any_condjump_p (bb_end_insn
))
678 /* If the old fallthru is still next, nothing to do. */
679 if (bb
->aux
== e_fall
->dest
680 || e_fall
->dest
== EXIT_BLOCK_PTR
)
683 /* The degenerated case of conditional jump jumping to the next
684 instruction can happen for jumps with side effects. We need
685 to construct a forwarder block and this will be done just
686 fine by force_nonfallthru below. */
690 /* There is another special case: if *neither* block is next,
691 such as happens at the very end of a function, then we'll
692 need to add a new unconditional jump. Choose the taken
693 edge based on known or assumed probability. */
694 else if (bb
->aux
!= e_taken
->dest
)
696 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
699 && INTVAL (XEXP (note
, 0)) < REG_BR_PROB_BASE
/ 2
700 && invert_jump (bb_end_insn
,
701 (e_fall
->dest
== EXIT_BLOCK_PTR
703 : label_for_bb (e_fall
->dest
)), 0))
705 e_fall
->flags
&= ~EDGE_FALLTHRU
;
706 #ifdef ENABLE_CHECKING
707 gcc_assert (could_fall_through
708 (e_taken
->src
, e_taken
->dest
));
710 e_taken
->flags
|= EDGE_FALLTHRU
;
711 update_br_prob_note (bb
);
712 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
716 /* If the "jumping" edge is a crossing edge, and the fall
717 through edge is non-crossing, leave things as they are. */
718 else if ((e_taken
->flags
& EDGE_CROSSING
)
719 && !(e_fall
->flags
& EDGE_CROSSING
))
722 /* Otherwise we can try to invert the jump. This will
723 basically never fail, however, keep up the pretense. */
724 else if (invert_jump (bb_end_insn
,
725 (e_fall
->dest
== EXIT_BLOCK_PTR
727 : label_for_bb (e_fall
->dest
)), 0))
729 e_fall
->flags
&= ~EDGE_FALLTHRU
;
730 #ifdef ENABLE_CHECKING
731 gcc_assert (could_fall_through
732 (e_taken
->src
, e_taken
->dest
));
734 e_taken
->flags
|= EDGE_FALLTHRU
;
735 update_br_prob_note (bb
);
741 /* Otherwise we have some return, switch or computed
742 jump. In the 99% case, there should not have been a
744 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
750 /* No fallthru implies a noreturn function with EH edges, or
751 something similarly bizarre. In any case, we don't need to
756 /* If the fallthru block is still next, nothing to do. */
757 if (bb
->aux
== e_fall
->dest
)
760 /* A fallthru to exit block. */
761 if (e_fall
->dest
== EXIT_BLOCK_PTR
)
765 /* We got here if we need to add a new jump insn. */
766 nb
= force_nonfallthru (e_fall
);
769 nb
->il
.rtl
->visited
= 1;
772 /* Don't process this new block. */
775 /* Make sure new bb is tagged for correct section (same as
776 fall-thru source, since you cannot fall-throu across
777 section boundaries). */
778 BB_COPY_PARTITION (e_fall
->src
, single_pred (bb
));
779 if (flag_reorder_blocks_and_partition
780 && targetm
.have_named_sections
781 && JUMP_P (BB_END (bb
))
782 && !any_condjump_p (BB_END (bb
))
783 && (EDGE_SUCC (bb
, 0)->flags
& EDGE_CROSSING
))
784 REG_NOTES (BB_END (bb
)) = gen_rtx_EXPR_LIST
785 (REG_CROSSING_JUMP
, NULL_RTX
, REG_NOTES (BB_END (bb
)));
789 /* Put basic_block_info in the new order. */
793 fprintf (dump_file
, "Reordered sequence:\n");
794 for (bb
= ENTRY_BLOCK_PTR
->next_bb
, index
= NUM_FIXED_BLOCKS
;
796 bb
= bb
->aux
, index
++)
798 fprintf (dump_file
, " %i ", index
);
799 if (get_bb_original (bb
))
800 fprintf (dump_file
, "duplicate of %i ",
801 get_bb_original (bb
)->index
);
802 else if (forwarder_block_p (bb
)
803 && !LABEL_P (BB_HEAD (bb
)))
804 fprintf (dump_file
, "compensation ");
806 fprintf (dump_file
, "bb %i ", bb
->index
);
807 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
811 prev_bb
= ENTRY_BLOCK_PTR
;
812 bb
= ENTRY_BLOCK_PTR
->next_bb
;
813 index
= NUM_FIXED_BLOCKS
;
815 for (; bb
; prev_bb
= bb
, bb
= bb
->aux
, index
++)
818 SET_BASIC_BLOCK (index
, bb
);
820 bb
->prev_bb
= prev_bb
;
821 prev_bb
->next_bb
= bb
;
823 prev_bb
->next_bb
= EXIT_BLOCK_PTR
;
824 EXIT_BLOCK_PTR
->prev_bb
= prev_bb
;
826 /* Annoying special case - jump around dead jumptables left in the code. */
832 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
833 if (e
->flags
& EDGE_FALLTHRU
)
836 if (e
&& !can_fallthru (e
->src
, e
->dest
))
837 force_nonfallthru (e
);
841 /* Perform sanity checks on the insn chain.
842 1. Check that next/prev pointers are consistent in both the forward and
844 2. Count insns in chain, going both directions, and check if equal.
845 3. Check that get_last_insn () returns the actual end of chain. */
848 verify_insn_chain (void)
851 int insn_cnt1
, insn_cnt2
;
853 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
855 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
856 gcc_assert (PREV_INSN (x
) == prevx
);
858 gcc_assert (prevx
== get_last_insn ());
860 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
862 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
863 gcc_assert (NEXT_INSN (x
) == nextx
);
865 gcc_assert (insn_cnt1
== insn_cnt2
);
868 /* If we have assembler epilogues, the block falling through to exit must
869 be the last one in the reordered chain when we reach final. Ensure
870 that this condition is met. */
872 fixup_fallthru_exit_predecessor (void)
876 basic_block bb
= NULL
;
878 /* This transformation is not valid before reload, because we might
879 separate a call from the instruction that copies the return
881 gcc_assert (reload_completed
);
883 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
884 if (e
->flags
& EDGE_FALLTHRU
)
889 basic_block c
= ENTRY_BLOCK_PTR
->next_bb
;
891 /* If the very first block is the one with the fall-through exit
892 edge, we have to split that block. */
895 bb
= split_block (bb
, NULL
)->dest
;
898 bb
->il
.rtl
->footer
= c
->il
.rtl
->footer
;
899 c
->il
.rtl
->footer
= NULL
;
914 /* Return true in case it is possible to duplicate the basic block BB. */
916 /* We do not want to declare the function in a header file, since it should
917 only be used through the cfghooks interface, and we do not want to move
918 it to cfgrtl.c since it would require also moving quite a lot of related
920 extern bool cfg_layout_can_duplicate_bb_p (basic_block
);
923 cfg_layout_can_duplicate_bb_p (basic_block bb
)
925 /* Do not attempt to duplicate tablejumps, as we need to unshare
926 the dispatch table. This is difficult to do, as the instructions
927 computing jump destination may be hoisted outside the basic block. */
928 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
931 /* Do not duplicate blocks containing insns that can't be copied. */
932 if (targetm
.cannot_copy_insn_p
)
934 rtx insn
= BB_HEAD (bb
);
937 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
939 if (insn
== BB_END (bb
))
941 insn
= NEXT_INSN (insn
);
949 duplicate_insn_chain (rtx from
, rtx to
)
953 /* Avoid updating of boundaries of previous basic block. The
954 note will get removed from insn stream in fixup. */
955 last
= emit_note (NOTE_INSN_DELETED
);
957 /* Create copy at the end of INSN chain. The chain will
958 be reordered later. */
959 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
961 switch (GET_CODE (insn
))
966 /* Avoid copying of dispatch tables. We never duplicate
967 tablejumps, so this can hit only in case the table got
968 moved far from original jump. */
969 if (GET_CODE (PATTERN (insn
)) == ADDR_VEC
970 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
)
972 emit_copy_of_insn_after (insn
, get_last_insn ());
983 switch (NOTE_LINE_NUMBER (insn
))
985 /* In case prologue is empty and function contain label
986 in first BB, we may want to copy the block. */
987 case NOTE_INSN_PROLOGUE_END
:
989 case NOTE_INSN_LOOP_BEG
:
990 case NOTE_INSN_LOOP_END
:
991 /* Strip down the loop notes - we don't really want to keep
992 them consistent in loop copies. */
993 case NOTE_INSN_DELETED
:
994 case NOTE_INSN_DELETED_LABEL
:
995 /* No problem to strip these. */
996 case NOTE_INSN_EPILOGUE_BEG
:
997 case NOTE_INSN_FUNCTION_END
:
998 /* Debug code expect these notes to exist just once.
999 Keep them in the master copy.
1000 ??? It probably makes more sense to duplicate them for each
1002 case NOTE_INSN_FUNCTION_BEG
:
1003 /* There is always just single entry to function. */
1004 case NOTE_INSN_BASIC_BLOCK
:
1007 case NOTE_INSN_REPEATED_LINE_NUMBER
:
1008 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
1009 emit_note_copy (insn
);
1013 /* All other notes should have already been eliminated.
1015 gcc_assert (NOTE_LINE_NUMBER (insn
) >= 0);
1017 /* It is possible that no_line_number is set and the note
1018 won't be emitted. */
1019 emit_note_copy (insn
);
1026 insn
= NEXT_INSN (last
);
1030 /* Create a duplicate of the basic block BB. */
1032 /* We do not want to declare the function in a header file, since it should
1033 only be used through the cfghooks interface, and we do not want to move
1034 it to cfgrtl.c since it would require also moving quite a lot of related
1036 extern basic_block
cfg_layout_duplicate_bb (basic_block
);
1039 cfg_layout_duplicate_bb (basic_block bb
)
1044 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
1045 new_bb
= create_basic_block (insn
,
1046 insn
? get_last_insn () : NULL
,
1047 EXIT_BLOCK_PTR
->prev_bb
);
1049 BB_COPY_PARTITION (new_bb
, bb
);
1050 if (bb
->il
.rtl
->header
)
1052 insn
= bb
->il
.rtl
->header
;
1053 while (NEXT_INSN (insn
))
1054 insn
= NEXT_INSN (insn
);
1055 insn
= duplicate_insn_chain (bb
->il
.rtl
->header
, insn
);
1057 new_bb
->il
.rtl
->header
= unlink_insn_chain (insn
, get_last_insn ());
1060 if (bb
->il
.rtl
->footer
)
1062 insn
= bb
->il
.rtl
->footer
;
1063 while (NEXT_INSN (insn
))
1064 insn
= NEXT_INSN (insn
);
1065 insn
= duplicate_insn_chain (bb
->il
.rtl
->footer
, insn
);
1067 new_bb
->il
.rtl
->footer
= unlink_insn_chain (insn
, get_last_insn ());
1070 if (bb
->il
.rtl
->global_live_at_start
)
1072 new_bb
->il
.rtl
->global_live_at_start
= ALLOC_REG_SET (®_obstack
);
1073 new_bb
->il
.rtl
->global_live_at_end
= ALLOC_REG_SET (®_obstack
);
1074 COPY_REG_SET (new_bb
->il
.rtl
->global_live_at_start
,
1075 bb
->il
.rtl
->global_live_at_start
);
1076 COPY_REG_SET (new_bb
->il
.rtl
->global_live_at_end
,
1077 bb
->il
.rtl
->global_live_at_end
);
1083 /* Main entry point to this module - initialize the datastructures for
1084 CFG layout changes. It keeps LOOPS up-to-date if not null.
1086 FLAGS is a set of additional flags to pass to cleanup_cfg(). It should
1087 include CLEANUP_UPDATE_LIFE if liveness information must be kept up
1091 cfg_layout_initialize (unsigned int flags
)
1093 initialize_original_copy_tables ();
1095 cfg_layout_rtl_register_cfg_hooks ();
1097 record_effective_endpoints ();
1099 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
1102 /* Splits superblocks. */
1104 break_superblocks (void)
1106 sbitmap superblocks
;
1110 superblocks
= sbitmap_alloc (last_basic_block
);
1111 sbitmap_zero (superblocks
);
1114 if (bb
->flags
& BB_SUPERBLOCK
)
1116 bb
->flags
&= ~BB_SUPERBLOCK
;
1117 SET_BIT (superblocks
, bb
->index
);
1123 rebuild_jump_labels (get_insns ());
1124 find_many_sub_basic_blocks (superblocks
);
1130 /* Finalize the changes: reorder insn list according to the sequence specified
1131 by aux pointers, enter compensation code, rebuild scope forest. */
1134 cfg_layout_finalize (void)
1138 #ifdef ENABLE_CHECKING
1139 verify_flow_info ();
1141 rtl_register_cfg_hooks ();
1142 if (reload_completed
1143 #ifdef HAVE_epilogue
1147 fixup_fallthru_exit_predecessor ();
1148 fixup_reorder_chain ();
1150 #ifdef ENABLE_CHECKING
1151 verify_insn_chain ();
1153 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1155 bb
->il
.rtl
->header
= bb
->il
.rtl
->footer
= NULL
;
1157 bb
->il
.rtl
->visited
= 0;
1160 break_superblocks ();
1162 #ifdef ENABLE_CHECKING
1163 verify_flow_info ();
1166 free_original_copy_tables ();
1169 /* Checks whether all N blocks in BBS array can be copied. */
1171 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1177 for (i
= 0; i
< n
; i
++)
1178 bbs
[i
]->flags
|= BB_DUPLICATED
;
1180 for (i
= 0; i
< n
; i
++)
1182 /* In case we should redirect abnormal edge during duplication, fail. */
1184 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1185 if ((e
->flags
& EDGE_ABNORMAL
)
1186 && (e
->dest
->flags
& BB_DUPLICATED
))
1192 if (!can_duplicate_block_p (bbs
[i
]))
1200 for (i
= 0; i
< n
; i
++)
1201 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1206 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1207 are placed into array NEW_BBS in the same order. Edges from basic blocks
1208 in BBS are also duplicated and copies of those of them
1209 that lead into BBS are redirected to appropriate newly created block. The
1210 function assigns bbs into loops (copy of basic block bb is assigned to
1211 bb->loop_father->copy loop, so this must be set up correctly in advance)
1212 and updates dominators locally (LOOPS structure that contains the information
1213 about dominators is passed to enable this).
1215 BASE is the superloop to that basic block belongs; if its header or latch
1216 is copied, we do not set the new blocks as header or latch.
1218 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1219 also in the same order.
1221 Newly created basic blocks are put after the basic block AFTER in the
1222 instruction stream, and the order of the blocks in BBS array is preserved. */
1225 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1226 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1227 struct loop
*base
, basic_block after
)
1230 basic_block bb
, new_bb
, dom_bb
;
1233 /* Duplicate bbs, update dominators, assign bbs to loops. */
1234 for (i
= 0; i
< n
; i
++)
1238 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
);
1240 bb
->flags
|= BB_DUPLICATED
;
1242 add_bb_to_loop (new_bb
, bb
->loop_father
->copy
);
1243 /* Possibly set header. */
1244 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1245 new_bb
->loop_father
->header
= new_bb
;
1247 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1248 new_bb
->loop_father
->latch
= new_bb
;
1251 /* Set dominators. */
1252 for (i
= 0; i
< n
; i
++)
1255 new_bb
= new_bbs
[i
];
1257 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1258 if (dom_bb
->flags
& BB_DUPLICATED
)
1260 dom_bb
= get_bb_copy (dom_bb
);
1261 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1265 /* Redirect edges. */
1266 for (j
= 0; j
< num_edges
; j
++)
1267 new_edges
[j
] = NULL
;
1268 for (i
= 0; i
< n
; i
++)
1271 new_bb
= new_bbs
[i
];
1274 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1276 for (j
= 0; j
< num_edges
; j
++)
1277 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1280 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1282 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1286 /* Clear information about duplicates. */
1287 for (i
= 0; i
< n
; i
++)
1288 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1291 #include "gt-cfglayout.h"