1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2003, 2004, 2005, 2007 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 3, 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 COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
26 #include "hard-reg-set.h"
28 #include "basic-block.h"
29 #include "insn-config.h"
32 #include "cfglayout.h"
36 #include "alloc-pool.h"
38 #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_BLOCK_END
:
105 case NOTE_INSN_DELETED
:
106 case NOTE_INSN_DELETED_LABEL
:
117 && JUMP_P (NEXT_INSN (insn
))
118 && (GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_VEC
119 || GET_CODE (PATTERN (NEXT_INSN (insn
))) == ADDR_DIFF_VEC
))
121 insn
= NEXT_INSN (insn
);
134 /* It is possible to hit contradictory sequence. For instance:
140 Where barrier belongs to jump_insn, but the note does not. This can be
141 created by removing the basic block originally following
142 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
144 for (insn
= last_insn
; insn
!= BB_END (bb
); insn
= prev
)
146 prev
= PREV_INSN (insn
);
148 switch (NOTE_LINE_NUMBER (insn
))
150 case NOTE_INSN_BLOCK_END
:
151 case NOTE_INSN_DELETED
:
152 case NOTE_INSN_DELETED_LABEL
:
155 reorder_insns (insn
, insn
, last_insn
);
162 /* Locate or create a label for a given basic block. */
165 label_for_bb (basic_block bb
)
167 rtx label
= BB_HEAD (bb
);
169 if (!LABEL_P (label
))
172 fprintf (dump_file
, "Emitting label for block %d\n", bb
->index
);
174 label
= block_label (bb
);
180 /* Locate the effective beginning and end of the insn chain for each
181 block, as defined by skip_insns_after_block above. */
184 record_effective_endpoints (void)
190 for (insn
= get_insns ();
193 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BASIC_BLOCK
;
194 insn
= NEXT_INSN (insn
))
196 /* No basic blocks at all? */
199 if (PREV_INSN (insn
))
200 cfg_layout_function_header
=
201 unlink_insn_chain (get_insns (), PREV_INSN (insn
));
203 cfg_layout_function_header
= NULL_RTX
;
205 next_insn
= get_insns ();
210 if (PREV_INSN (BB_HEAD (bb
)) && next_insn
!= BB_HEAD (bb
))
211 bb
->il
.rtl
->header
= unlink_insn_chain (next_insn
,
212 PREV_INSN (BB_HEAD (bb
)));
213 end
= skip_insns_after_block (bb
);
214 if (NEXT_INSN (BB_END (bb
)) && BB_END (bb
) != end
)
215 bb
->il
.rtl
->footer
= unlink_insn_chain (NEXT_INSN (BB_END (bb
)), end
);
216 next_insn
= NEXT_INSN (BB_END (bb
));
219 cfg_layout_function_footer
= next_insn
;
220 if (cfg_layout_function_footer
)
221 cfg_layout_function_footer
= unlink_insn_chain (cfg_layout_function_footer
, get_last_insn ());
224 /* Data structures representing mapping of INSN_LOCATOR into scope blocks, line
225 numbers and files. In order to be GGC friendly we need to use separate
226 varrays. This also slightly improve the memory locality in binary search.
227 The _locs array contains locators where the given property change. The
228 block_locators_blocks contains the scope block that is used for all insn
229 locator greater than corresponding block_locators_locs value and smaller
230 than the following one. Similarly for the other properties. */
231 static VEC(int,heap
) *block_locators_locs
;
232 static GTY(()) VEC(tree
,gc
) *block_locators_blocks
;
233 static VEC(int,heap
) *line_locators_locs
;
234 static VEC(int,heap
) *line_locators_lines
;
235 static VEC(int,heap
) *file_locators_locs
;
236 static GTY(()) varray_type file_locators_files
;
237 int prologue_locator
;
238 int epilogue_locator
;
240 /* During the RTL expansion the lexical blocks and line numbers are
241 represented via INSN_NOTEs. Replace them by representation using
245 insn_locators_initialize (void)
248 tree last_block
= NULL
;
251 int line_number
= 0, last_line_number
= 0;
252 const char *file_name
= NULL
, *last_file_name
= NULL
;
254 prologue_locator
= epilogue_locator
= 0;
256 block_locators_locs
= VEC_alloc (int, heap
, 32);
257 block_locators_blocks
= VEC_alloc (tree
, gc
, 32);
258 line_locators_locs
= VEC_alloc (int, heap
, 32);
259 line_locators_lines
= VEC_alloc (int, heap
, 32);
260 file_locators_locs
= VEC_alloc (int, heap
, 32);
261 VARRAY_CHAR_PTR_INIT (file_locators_files
, 32, "file_locators_files");
263 for (insn
= get_insns (); insn
; insn
= next
)
267 next
= NEXT_INSN (insn
);
271 gcc_assert (NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BLOCK_BEG
272 && NOTE_LINE_NUMBER (insn
) != NOTE_INSN_BLOCK_END
);
273 if (NOTE_LINE_NUMBER (insn
) > 0)
275 expanded_location xloc
;
276 NOTE_EXPANDED_LOCATION (xloc
, insn
);
277 line_number
= xloc
.line
;
278 file_name
= xloc
.file
;
282 active
= (active_insn_p (insn
)
283 && GET_CODE (PATTERN (insn
)) != ADDR_VEC
284 && GET_CODE (PATTERN (insn
)) != ADDR_DIFF_VEC
);
286 check_block_change (insn
, &block
);
290 || (!prologue_locator
&& file_name
))
292 if (last_block
!= block
)
295 VEC_safe_push (int, heap
, block_locators_locs
, loc
);
296 VEC_safe_push (tree
, gc
, block_locators_blocks
, block
);
299 if (last_line_number
!= line_number
)
302 VEC_safe_push (int, heap
, line_locators_locs
, loc
);
303 VEC_safe_push (int, heap
, line_locators_lines
, line_number
);
304 last_line_number
= line_number
;
306 if (last_file_name
!= file_name
)
309 VEC_safe_push (int, heap
, file_locators_locs
, loc
);
310 VARRAY_PUSH_CHAR_PTR (file_locators_files
, (char *) file_name
);
311 last_file_name
= file_name
;
313 if (!prologue_locator
&& file_name
)
314 prologue_locator
= loc
;
316 epilogue_locator
= loc
;
318 INSN_LOCATOR (insn
) = loc
;
322 /* Tag the blocks with a depth number so that change_scope can find
323 the common parent easily. */
324 set_block_levels (DECL_INITIAL (cfun
->decl
), 0);
326 free_block_changes ();
330 struct tree_opt_pass pass_insn_locators_initialize
=
332 "locators", /* name */
334 insn_locators_initialize
, /* execute */
337 0, /* static_pass_number */
339 0, /* properties_required */
340 0, /* properties_provided */
341 0, /* properties_destroyed */
342 0, /* todo_flags_start */
343 TODO_dump_func
, /* todo_flags_finish */
348 /* For each lexical block, set BLOCK_NUMBER to the depth at which it is
349 found in the block tree. */
352 set_block_levels (tree block
, int level
)
356 BLOCK_NUMBER (block
) = level
;
357 set_block_levels (BLOCK_SUBBLOCKS (block
), level
+ 1);
358 block
= BLOCK_CHAIN (block
);
362 /* Return sope resulting from combination of S1 and S2. */
364 choose_inner_scope (tree s1
, tree s2
)
370 if (BLOCK_NUMBER (s1
) > BLOCK_NUMBER (s2
))
375 /* Emit lexical block notes needed to change scope from S1 to S2. */
378 change_scope (rtx orig_insn
, tree s1
, tree s2
)
380 rtx insn
= orig_insn
;
381 tree com
= NULL_TREE
;
382 tree ts1
= s1
, ts2
= s2
;
387 gcc_assert (ts1
&& ts2
);
388 if (BLOCK_NUMBER (ts1
) > BLOCK_NUMBER (ts2
))
389 ts1
= BLOCK_SUPERCONTEXT (ts1
);
390 else if (BLOCK_NUMBER (ts1
) < BLOCK_NUMBER (ts2
))
391 ts2
= BLOCK_SUPERCONTEXT (ts2
);
394 ts1
= BLOCK_SUPERCONTEXT (ts1
);
395 ts2
= BLOCK_SUPERCONTEXT (ts2
);
404 rtx note
= emit_note_before (NOTE_INSN_BLOCK_END
, insn
);
405 NOTE_BLOCK (note
) = s
;
406 s
= BLOCK_SUPERCONTEXT (s
);
413 insn
= emit_note_before (NOTE_INSN_BLOCK_BEG
, insn
);
414 NOTE_BLOCK (insn
) = s
;
415 s
= BLOCK_SUPERCONTEXT (s
);
419 /* Return lexical scope block insn belong to. */
421 insn_scope (rtx insn
)
423 int max
= VEC_length (int, block_locators_locs
);
425 int loc
= INSN_LOCATOR (insn
);
427 /* When block_locators_locs was initialized, the pro- and epilogue
428 insns didn't exist yet and can therefore not be found this way.
429 But we know that they belong to the outer most block of the
431 Without this test, the prologue would be put inside the block of
432 the first valid instruction in the function and when that first
433 insn is part of an inlined function then the low_pc of that
434 inlined function is messed up. Likewise for the epilogue and
435 the last valid instruction. */
436 if (loc
== prologue_locator
|| loc
== epilogue_locator
)
437 return DECL_INITIAL (cfun
->decl
);
443 int pos
= (min
+ max
) / 2;
444 int tmp
= VEC_index (int, block_locators_locs
, pos
);
446 if (tmp
<= loc
&& min
!= pos
)
448 else if (tmp
> loc
&& max
!= pos
)
456 return VEC_index (tree
, block_locators_blocks
, min
);
459 /* Return line number of the statement specified by the locator. */
461 locator_line (int loc
)
463 int max
= VEC_length (int, line_locators_locs
);
470 int pos
= (min
+ max
) / 2;
471 int tmp
= VEC_index (int, line_locators_locs
, pos
);
473 if (tmp
<= loc
&& min
!= pos
)
475 else if (tmp
> loc
&& max
!= pos
)
483 return VEC_index (int, line_locators_lines
, min
);
486 /* Return line number of the statement that produced this insn. */
490 return locator_line (INSN_LOCATOR (insn
));
493 /* Return source file of the statement specified by LOC. */
495 locator_file (int loc
)
497 int max
= VEC_length (int, file_locators_locs
);
504 int pos
= (min
+ max
) / 2;
505 int tmp
= VEC_index (int, file_locators_locs
, pos
);
507 if (tmp
<= loc
&& min
!= pos
)
509 else if (tmp
> loc
&& max
!= pos
)
517 return VARRAY_CHAR_PTR (file_locators_files
, min
);
520 /* Return source file of the statement that produced this insn. */
524 return locator_file (INSN_LOCATOR (insn
));
527 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
528 on the scope tree and the newly reordered instructions. */
531 reemit_insn_block_notes (void)
533 tree cur_block
= DECL_INITIAL (cfun
->decl
);
537 if (!active_insn_p (insn
))
538 insn
= next_active_insn (insn
);
539 for (; insn
; insn
= next_active_insn (insn
))
543 /* Avoid putting scope notes between jump table and its label. */
545 && (GET_CODE (PATTERN (insn
)) == ADDR_VEC
546 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
))
549 this_block
= insn_scope (insn
);
550 /* For sequences compute scope resulting from merging all scopes
551 of instructions nested inside. */
552 if (GET_CODE (PATTERN (insn
)) == SEQUENCE
)
555 rtx body
= PATTERN (insn
);
558 for (i
= 0; i
< XVECLEN (body
, 0); i
++)
559 this_block
= choose_inner_scope (this_block
,
560 insn_scope (XVECEXP (body
, 0, i
)));
565 if (this_block
!= cur_block
)
567 change_scope (insn
, cur_block
, this_block
);
568 cur_block
= this_block
;
572 /* change_scope emits before the insn, not after. */
573 note
= emit_note (NOTE_INSN_DELETED
);
574 change_scope (note
, cur_block
, DECL_INITIAL (cfun
->decl
));
580 /* Given a reorder chain, rearrange the code to match. */
583 fixup_reorder_chain (void)
585 basic_block bb
, prev_bb
;
589 if (cfg_layout_function_header
)
591 set_first_insn (cfg_layout_function_header
);
592 insn
= cfg_layout_function_header
;
593 while (NEXT_INSN (insn
))
594 insn
= NEXT_INSN (insn
);
597 /* First do the bulk reordering -- rechain the blocks without regard to
598 the needed changes to jumps and labels. */
600 for (bb
= ENTRY_BLOCK_PTR
->next_bb
, index
= NUM_FIXED_BLOCKS
;
602 bb
= bb
->aux
, index
++)
604 if (bb
->il
.rtl
->header
)
607 NEXT_INSN (insn
) = bb
->il
.rtl
->header
;
609 set_first_insn (bb
->il
.rtl
->header
);
610 PREV_INSN (bb
->il
.rtl
->header
) = insn
;
611 insn
= bb
->il
.rtl
->header
;
612 while (NEXT_INSN (insn
))
613 insn
= NEXT_INSN (insn
);
616 NEXT_INSN (insn
) = BB_HEAD (bb
);
618 set_first_insn (BB_HEAD (bb
));
619 PREV_INSN (BB_HEAD (bb
)) = insn
;
621 if (bb
->il
.rtl
->footer
)
623 NEXT_INSN (insn
) = bb
->il
.rtl
->footer
;
624 PREV_INSN (bb
->il
.rtl
->footer
) = insn
;
625 while (NEXT_INSN (insn
))
626 insn
= NEXT_INSN (insn
);
630 gcc_assert (index
== n_basic_blocks
);
632 NEXT_INSN (insn
) = cfg_layout_function_footer
;
633 if (cfg_layout_function_footer
)
634 PREV_INSN (cfg_layout_function_footer
) = insn
;
636 while (NEXT_INSN (insn
))
637 insn
= NEXT_INSN (insn
);
639 set_last_insn (insn
);
640 #ifdef ENABLE_CHECKING
641 verify_insn_chain ();
643 delete_dead_jumptables ();
645 /* Now add jumps and labels as needed to match the blocks new
648 for (bb
= ENTRY_BLOCK_PTR
->next_bb
; bb
; bb
= bb
->aux
)
650 edge e_fall
, e_taken
, e
;
655 if (EDGE_COUNT (bb
->succs
) == 0)
658 /* Find the old fallthru edge, and another non-EH edge for
660 e_taken
= e_fall
= NULL
;
662 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
663 if (e
->flags
& EDGE_FALLTHRU
)
665 else if (! (e
->flags
& EDGE_EH
))
668 bb_end_insn
= BB_END (bb
);
669 if (JUMP_P (bb_end_insn
))
671 if (any_condjump_p (bb_end_insn
))
673 /* If the old fallthru is still next, nothing to do. */
674 if (bb
->aux
== e_fall
->dest
675 || e_fall
->dest
== EXIT_BLOCK_PTR
)
678 /* The degenerated case of conditional jump jumping to the next
679 instruction can happen for jumps with side effects. We need
680 to construct a forwarder block and this will be done just
681 fine by force_nonfallthru below. */
685 /* There is another special case: if *neither* block is next,
686 such as happens at the very end of a function, then we'll
687 need to add a new unconditional jump. Choose the taken
688 edge based on known or assumed probability. */
689 else if (bb
->aux
!= e_taken
->dest
)
691 rtx note
= find_reg_note (bb_end_insn
, REG_BR_PROB
, 0);
694 && INTVAL (XEXP (note
, 0)) < REG_BR_PROB_BASE
/ 2
695 && invert_jump (bb_end_insn
,
696 (e_fall
->dest
== EXIT_BLOCK_PTR
698 : label_for_bb (e_fall
->dest
)), 0))
700 e_fall
->flags
&= ~EDGE_FALLTHRU
;
701 #ifdef ENABLE_CHECKING
702 gcc_assert (could_fall_through
703 (e_taken
->src
, e_taken
->dest
));
705 e_taken
->flags
|= EDGE_FALLTHRU
;
706 update_br_prob_note (bb
);
707 e
= e_fall
, e_fall
= e_taken
, e_taken
= e
;
711 /* If the "jumping" edge is a crossing edge, and the fall
712 through edge is non-crossing, leave things as they are. */
713 else if ((e_taken
->flags
& EDGE_CROSSING
)
714 && !(e_fall
->flags
& EDGE_CROSSING
))
717 /* Otherwise we can try to invert the jump. This will
718 basically never fail, however, keep up the pretense. */
719 else if (invert_jump (bb_end_insn
,
720 (e_fall
->dest
== EXIT_BLOCK_PTR
722 : label_for_bb (e_fall
->dest
)), 0))
724 e_fall
->flags
&= ~EDGE_FALLTHRU
;
725 #ifdef ENABLE_CHECKING
726 gcc_assert (could_fall_through
727 (e_taken
->src
, e_taken
->dest
));
729 e_taken
->flags
|= EDGE_FALLTHRU
;
730 update_br_prob_note (bb
);
736 /* Otherwise we have some return, switch or computed
737 jump. In the 99% case, there should not have been a
739 gcc_assert (returnjump_p (bb_end_insn
) || !e_fall
);
745 /* No fallthru implies a noreturn function with EH edges, or
746 something similarly bizarre. In any case, we don't need to
751 /* If the fallthru block is still next, nothing to do. */
752 if (bb
->aux
== e_fall
->dest
)
755 /* A fallthru to exit block. */
756 if (e_fall
->dest
== EXIT_BLOCK_PTR
)
760 /* We got here if we need to add a new jump insn. */
761 nb
= force_nonfallthru (e_fall
);
764 nb
->il
.rtl
->visited
= 1;
767 /* Don't process this new block. */
770 /* Make sure new bb is tagged for correct section (same as
771 fall-thru source, since you cannot fall-throu across
772 section boundaries). */
773 BB_COPY_PARTITION (e_fall
->src
, single_pred (bb
));
774 if (flag_reorder_blocks_and_partition
775 && targetm
.have_named_sections
776 && JUMP_P (BB_END (bb
))
777 && !any_condjump_p (BB_END (bb
))
778 && (EDGE_SUCC (bb
, 0)->flags
& EDGE_CROSSING
))
779 REG_NOTES (BB_END (bb
)) = gen_rtx_EXPR_LIST
780 (REG_CROSSING_JUMP
, NULL_RTX
, REG_NOTES (BB_END (bb
)));
784 /* Put basic_block_info in the new order. */
788 fprintf (dump_file
, "Reordered sequence:\n");
789 for (bb
= ENTRY_BLOCK_PTR
->next_bb
, index
= NUM_FIXED_BLOCKS
;
791 bb
= bb
->aux
, index
++)
793 fprintf (dump_file
, " %i ", index
);
794 if (get_bb_original (bb
))
795 fprintf (dump_file
, "duplicate of %i ",
796 get_bb_original (bb
)->index
);
797 else if (forwarder_block_p (bb
)
798 && !LABEL_P (BB_HEAD (bb
)))
799 fprintf (dump_file
, "compensation ");
801 fprintf (dump_file
, "bb %i ", bb
->index
);
802 fprintf (dump_file
, " [%i]\n", bb
->frequency
);
806 prev_bb
= ENTRY_BLOCK_PTR
;
807 bb
= ENTRY_BLOCK_PTR
->next_bb
;
808 index
= NUM_FIXED_BLOCKS
;
810 for (; bb
; prev_bb
= bb
, bb
= bb
->aux
, index
++)
813 SET_BASIC_BLOCK (index
, bb
);
815 bb
->prev_bb
= prev_bb
;
816 prev_bb
->next_bb
= bb
;
818 prev_bb
->next_bb
= EXIT_BLOCK_PTR
;
819 EXIT_BLOCK_PTR
->prev_bb
= prev_bb
;
821 /* Annoying special case - jump around dead jumptables left in the code. */
827 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
828 if (e
->flags
& EDGE_FALLTHRU
)
831 if (e
&& !can_fallthru (e
->src
, e
->dest
))
832 force_nonfallthru (e
);
836 /* Perform sanity checks on the insn chain.
837 1. Check that next/prev pointers are consistent in both the forward and
839 2. Count insns in chain, going both directions, and check if equal.
840 3. Check that get_last_insn () returns the actual end of chain. */
843 verify_insn_chain (void)
846 int insn_cnt1
, insn_cnt2
;
848 for (prevx
= NULL
, insn_cnt1
= 1, x
= get_insns ();
850 prevx
= x
, insn_cnt1
++, x
= NEXT_INSN (x
))
851 gcc_assert (PREV_INSN (x
) == prevx
);
853 gcc_assert (prevx
== get_last_insn ());
855 for (nextx
= NULL
, insn_cnt2
= 1, x
= get_last_insn ();
857 nextx
= x
, insn_cnt2
++, x
= PREV_INSN (x
))
858 gcc_assert (NEXT_INSN (x
) == nextx
);
860 gcc_assert (insn_cnt1
== insn_cnt2
);
863 /* If we have assembler epilogues, the block falling through to exit must
864 be the last one in the reordered chain when we reach final. Ensure
865 that this condition is met. */
867 fixup_fallthru_exit_predecessor (void)
871 basic_block bb
= NULL
;
873 /* This transformation is not valid before reload, because we might
874 separate a call from the instruction that copies the return
876 gcc_assert (reload_completed
);
878 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
879 if (e
->flags
& EDGE_FALLTHRU
)
884 basic_block c
= ENTRY_BLOCK_PTR
->next_bb
;
886 /* If the very first block is the one with the fall-through exit
887 edge, we have to split that block. */
890 bb
= split_block (bb
, NULL
)->dest
;
893 bb
->il
.rtl
->footer
= c
->il
.rtl
->footer
;
894 c
->il
.rtl
->footer
= NULL
;
909 /* Return true in case it is possible to duplicate the basic block BB. */
911 /* We do not want to declare the function in a header file, since it should
912 only be used through the cfghooks interface, and we do not want to move
913 it to cfgrtl.c since it would require also moving quite a lot of related
915 extern bool cfg_layout_can_duplicate_bb_p (basic_block
);
918 cfg_layout_can_duplicate_bb_p (basic_block bb
)
920 /* Do not attempt to duplicate tablejumps, as we need to unshare
921 the dispatch table. This is difficult to do, as the instructions
922 computing jump destination may be hoisted outside the basic block. */
923 if (tablejump_p (BB_END (bb
), NULL
, NULL
))
926 /* Do not duplicate blocks containing insns that can't be copied. */
927 if (targetm
.cannot_copy_insn_p
)
929 rtx insn
= BB_HEAD (bb
);
932 if (INSN_P (insn
) && targetm
.cannot_copy_insn_p (insn
))
934 if (insn
== BB_END (bb
))
936 insn
= NEXT_INSN (insn
);
944 duplicate_insn_chain (rtx from
, rtx to
)
948 /* Avoid updating of boundaries of previous basic block. The
949 note will get removed from insn stream in fixup. */
950 last
= emit_note (NOTE_INSN_DELETED
);
952 /* Create copy at the end of INSN chain. The chain will
953 be reordered later. */
954 for (insn
= from
; insn
!= NEXT_INSN (to
); insn
= NEXT_INSN (insn
))
956 switch (GET_CODE (insn
))
961 /* Avoid copying of dispatch tables. We never duplicate
962 tablejumps, so this can hit only in case the table got
963 moved far from original jump. */
964 if (GET_CODE (PATTERN (insn
)) == ADDR_VEC
965 || GET_CODE (PATTERN (insn
)) == ADDR_DIFF_VEC
)
967 emit_copy_of_insn_after (insn
, get_last_insn ());
978 switch (NOTE_LINE_NUMBER (insn
))
980 /* In case prologue is empty and function contain label
981 in first BB, we may want to copy the block. */
982 case NOTE_INSN_PROLOGUE_END
:
984 case NOTE_INSN_DELETED
:
985 case NOTE_INSN_DELETED_LABEL
:
986 /* No problem to strip these. */
987 case NOTE_INSN_EPILOGUE_BEG
:
988 case NOTE_INSN_FUNCTION_END
:
989 /* Debug code expect these notes to exist just once.
990 Keep them in the master copy.
991 ??? It probably makes more sense to duplicate them for each
993 case NOTE_INSN_FUNCTION_BEG
:
994 /* There is always just single entry to function. */
995 case NOTE_INSN_BASIC_BLOCK
:
998 case NOTE_INSN_REPEATED_LINE_NUMBER
:
999 case NOTE_INSN_SWITCH_TEXT_SECTIONS
:
1000 emit_note_copy (insn
);
1004 /* All other notes should have already been eliminated.
1006 gcc_assert (NOTE_LINE_NUMBER (insn
) >= 0);
1008 /* It is possible that no_line_number is set and the note
1009 won't be emitted. */
1010 emit_note_copy (insn
);
1017 insn
= NEXT_INSN (last
);
1021 /* Create a duplicate of the basic block BB. */
1023 /* We do not want to declare the function in a header file, since it should
1024 only be used through the cfghooks interface, and we do not want to move
1025 it to cfgrtl.c since it would require also moving quite a lot of related
1027 extern basic_block
cfg_layout_duplicate_bb (basic_block
);
1030 cfg_layout_duplicate_bb (basic_block bb
)
1035 insn
= duplicate_insn_chain (BB_HEAD (bb
), BB_END (bb
));
1036 new_bb
= create_basic_block (insn
,
1037 insn
? get_last_insn () : NULL
,
1038 EXIT_BLOCK_PTR
->prev_bb
);
1040 BB_COPY_PARTITION (new_bb
, bb
);
1041 if (bb
->il
.rtl
->header
)
1043 insn
= bb
->il
.rtl
->header
;
1044 while (NEXT_INSN (insn
))
1045 insn
= NEXT_INSN (insn
);
1046 insn
= duplicate_insn_chain (bb
->il
.rtl
->header
, insn
);
1048 new_bb
->il
.rtl
->header
= unlink_insn_chain (insn
, get_last_insn ());
1051 if (bb
->il
.rtl
->footer
)
1053 insn
= bb
->il
.rtl
->footer
;
1054 while (NEXT_INSN (insn
))
1055 insn
= NEXT_INSN (insn
);
1056 insn
= duplicate_insn_chain (bb
->il
.rtl
->footer
, insn
);
1058 new_bb
->il
.rtl
->footer
= unlink_insn_chain (insn
, get_last_insn ());
1061 if (bb
->il
.rtl
->global_live_at_start
)
1063 new_bb
->il
.rtl
->global_live_at_start
= ALLOC_REG_SET (®_obstack
);
1064 new_bb
->il
.rtl
->global_live_at_end
= ALLOC_REG_SET (®_obstack
);
1065 COPY_REG_SET (new_bb
->il
.rtl
->global_live_at_start
,
1066 bb
->il
.rtl
->global_live_at_start
);
1067 COPY_REG_SET (new_bb
->il
.rtl
->global_live_at_end
,
1068 bb
->il
.rtl
->global_live_at_end
);
1074 /* Main entry point to this module - initialize the datastructures for
1075 CFG layout changes. It keeps LOOPS up-to-date if not null.
1077 FLAGS is a set of additional flags to pass to cleanup_cfg(). It should
1078 include CLEANUP_UPDATE_LIFE if liveness information must be kept up
1082 cfg_layout_initialize (unsigned int flags
)
1084 initialize_original_copy_tables ();
1086 cfg_layout_rtl_register_cfg_hooks ();
1088 record_effective_endpoints ();
1090 cleanup_cfg (CLEANUP_CFGLAYOUT
| flags
);
1093 /* Splits superblocks. */
1095 break_superblocks (void)
1097 sbitmap superblocks
;
1101 superblocks
= sbitmap_alloc (last_basic_block
);
1102 sbitmap_zero (superblocks
);
1105 if (bb
->flags
& BB_SUPERBLOCK
)
1107 bb
->flags
&= ~BB_SUPERBLOCK
;
1108 SET_BIT (superblocks
, bb
->index
);
1114 rebuild_jump_labels (get_insns ());
1115 find_many_sub_basic_blocks (superblocks
);
1121 /* Finalize the changes: reorder insn list according to the sequence specified
1122 by aux pointers, enter compensation code, rebuild scope forest. */
1125 cfg_layout_finalize (void)
1129 #ifdef ENABLE_CHECKING
1130 verify_flow_info ();
1132 rtl_register_cfg_hooks ();
1133 if (reload_completed
1134 #ifdef HAVE_epilogue
1138 fixup_fallthru_exit_predecessor ();
1139 fixup_reorder_chain ();
1141 #ifdef ENABLE_CHECKING
1142 verify_insn_chain ();
1144 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
1146 bb
->il
.rtl
->header
= bb
->il
.rtl
->footer
= NULL
;
1148 bb
->il
.rtl
->visited
= 0;
1151 break_superblocks ();
1153 #ifdef ENABLE_CHECKING
1154 verify_flow_info ();
1157 free_original_copy_tables ();
1160 /* Checks whether all N blocks in BBS array can be copied. */
1162 can_copy_bbs_p (basic_block
*bbs
, unsigned n
)
1168 for (i
= 0; i
< n
; i
++)
1169 bbs
[i
]->flags
|= BB_DUPLICATED
;
1171 for (i
= 0; i
< n
; i
++)
1173 /* In case we should redirect abnormal edge during duplication, fail. */
1175 FOR_EACH_EDGE (e
, ei
, bbs
[i
]->succs
)
1176 if ((e
->flags
& EDGE_ABNORMAL
)
1177 && (e
->dest
->flags
& BB_DUPLICATED
))
1183 if (!can_duplicate_block_p (bbs
[i
]))
1191 for (i
= 0; i
< n
; i
++)
1192 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1197 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1198 are placed into array NEW_BBS in the same order. Edges from basic blocks
1199 in BBS are also duplicated and copies of those of them
1200 that lead into BBS are redirected to appropriate newly created block. The
1201 function assigns bbs into loops (copy of basic block bb is assigned to
1202 bb->loop_father->copy loop, so this must be set up correctly in advance)
1203 and updates dominators locally (LOOPS structure that contains the information
1204 about dominators is passed to enable this).
1206 BASE is the superloop to that basic block belongs; if its header or latch
1207 is copied, we do not set the new blocks as header or latch.
1209 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1210 also in the same order.
1212 Newly created basic blocks are put after the basic block AFTER in the
1213 instruction stream, and the order of the blocks in BBS array is preserved. */
1216 copy_bbs (basic_block
*bbs
, unsigned n
, basic_block
*new_bbs
,
1217 edge
*edges
, unsigned num_edges
, edge
*new_edges
,
1218 struct loop
*base
, basic_block after
)
1221 basic_block bb
, new_bb
, dom_bb
;
1224 /* Duplicate bbs, update dominators, assign bbs to loops. */
1225 for (i
= 0; i
< n
; i
++)
1229 new_bb
= new_bbs
[i
] = duplicate_block (bb
, NULL
, after
);
1231 bb
->flags
|= BB_DUPLICATED
;
1233 add_bb_to_loop (new_bb
, bb
->loop_father
->copy
);
1234 /* Possibly set header. */
1235 if (bb
->loop_father
->header
== bb
&& bb
->loop_father
!= base
)
1236 new_bb
->loop_father
->header
= new_bb
;
1238 if (bb
->loop_father
->latch
== bb
&& bb
->loop_father
!= base
)
1239 new_bb
->loop_father
->latch
= new_bb
;
1242 /* Set dominators. */
1243 for (i
= 0; i
< n
; i
++)
1246 new_bb
= new_bbs
[i
];
1248 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1249 if (dom_bb
->flags
& BB_DUPLICATED
)
1251 dom_bb
= get_bb_copy (dom_bb
);
1252 set_immediate_dominator (CDI_DOMINATORS
, new_bb
, dom_bb
);
1256 /* Redirect edges. */
1257 for (j
= 0; j
< num_edges
; j
++)
1258 new_edges
[j
] = NULL
;
1259 for (i
= 0; i
< n
; i
++)
1262 new_bb
= new_bbs
[i
];
1265 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
1267 for (j
= 0; j
< num_edges
; j
++)
1268 if (edges
[j
] && edges
[j
]->src
== bb
&& edges
[j
]->dest
== e
->dest
)
1271 if (!(e
->dest
->flags
& BB_DUPLICATED
))
1273 redirect_edge_and_branch_force (e
, get_bb_copy (e
->dest
));
1277 /* Clear information about duplicates. */
1278 for (i
= 0; i
< n
; i
++)
1279 bbs
[i
]->flags
&= ~BB_DUPLICATED
;
1282 #include "gt-cfglayout.h"