* gcc_update: libjava/configure.in -> configure.ac.
[official-gcc.git] / gcc / cfglayout.c
bloba81ce4c7f8cafc8029b85906015b1bee4867cfda
1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2003, 2004 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
9 version.
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
14 for more details.
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, 59 Temple Place - Suite 330, Boston, MA
19 02111-1307, USA. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "rtl.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
29 #include "insn-config.h"
30 #include "output.h"
31 #include "function.h"
32 #include "obstack.h"
33 #include "cfglayout.h"
34 #include "cfgloop.h"
35 #include "target.h"
36 #include "ggc.h"
37 #include "alloc-pool.h"
38 #include "flags.h"
40 /* The contents of the current function definition are allocated
41 in this obstack, and all are freed at the end of the function. */
42 extern struct obstack flow_obstack;
44 /* Holds the interesting trailing notes for the function. */
45 rtx cfg_layout_function_footer, cfg_layout_function_header;
47 static rtx skip_insns_after_block (basic_block);
48 static void record_effective_endpoints (void);
49 static rtx label_for_bb (basic_block);
50 static void fixup_reorder_chain (void);
52 static void set_block_levels (tree, int);
53 static void change_scope (rtx, tree, tree);
55 void verify_insn_chain (void);
56 static void fixup_fallthru_exit_predecessor (void);
57 static tree insn_scope (rtx);
58 static void update_unlikely_executed_notes (basic_block);
60 rtx
61 unlink_insn_chain (rtx first, rtx last)
63 rtx prevfirst = PREV_INSN (first);
64 rtx nextlast = NEXT_INSN (last);
66 PREV_INSN (first) = NULL;
67 NEXT_INSN (last) = NULL;
68 if (prevfirst)
69 NEXT_INSN (prevfirst) = nextlast;
70 if (nextlast)
71 PREV_INSN (nextlast) = prevfirst;
72 else
73 set_last_insn (prevfirst);
74 if (!prevfirst)
75 set_first_insn (nextlast);
76 return first;
79 /* Skip over inter-block insns occurring after BB which are typically
80 associated with BB (e.g., barriers). If there are any such insns,
81 we return the last one. Otherwise, we return the end of BB. */
83 static rtx
84 skip_insns_after_block (basic_block bb)
86 rtx insn, last_insn, next_head, prev;
88 next_head = NULL_RTX;
89 if (bb->next_bb != EXIT_BLOCK_PTR)
90 next_head = BB_HEAD (bb->next_bb);
92 for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )
94 if (insn == next_head)
95 break;
97 switch (GET_CODE (insn))
99 case BARRIER:
100 last_insn = insn;
101 continue;
103 case NOTE:
104 switch (NOTE_LINE_NUMBER (insn))
106 case NOTE_INSN_LOOP_END:
107 case NOTE_INSN_BLOCK_END:
108 last_insn = insn;
109 continue;
110 case NOTE_INSN_DELETED:
111 case NOTE_INSN_DELETED_LABEL:
112 continue;
114 default:
115 continue;
116 break;
118 break;
120 case CODE_LABEL:
121 if (NEXT_INSN (insn)
122 && JUMP_P (NEXT_INSN (insn))
123 && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
124 || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
126 insn = NEXT_INSN (insn);
127 last_insn = insn;
128 continue;
130 break;
132 default:
133 break;
136 break;
139 /* It is possible to hit contradictory sequence. For instance:
141 jump_insn
142 NOTE_INSN_LOOP_BEG
143 barrier
145 Where barrier belongs to jump_insn, but the note does not. This can be
146 created by removing the basic block originally following
147 NOTE_INSN_LOOP_BEG. In such case reorder the notes. */
149 for (insn = last_insn; insn != BB_END (bb); insn = prev)
151 prev = PREV_INSN (insn);
152 if (NOTE_P (insn))
153 switch (NOTE_LINE_NUMBER (insn))
155 case NOTE_INSN_LOOP_END:
156 case NOTE_INSN_BLOCK_END:
157 case NOTE_INSN_DELETED:
158 case NOTE_INSN_DELETED_LABEL:
159 continue;
160 default:
161 reorder_insns (insn, insn, last_insn);
165 return last_insn;
168 /* Locate or create a label for a given basic block. */
170 static rtx
171 label_for_bb (basic_block bb)
173 rtx label = BB_HEAD (bb);
175 if (!LABEL_P (label))
177 if (dump_file)
178 fprintf (dump_file, "Emitting label for block %d\n", bb->index);
180 label = block_label (bb);
183 return label;
186 /* Locate the effective beginning and end of the insn chain for each
187 block, as defined by skip_insns_after_block above. */
189 static void
190 record_effective_endpoints (void)
192 rtx next_insn;
193 basic_block bb;
194 rtx insn;
196 for (insn = get_insns ();
197 insn
198 && NOTE_P (insn)
199 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK;
200 insn = NEXT_INSN (insn))
201 continue;
202 if (!insn)
203 abort (); /* No basic blocks at all? */
204 if (PREV_INSN (insn))
205 cfg_layout_function_header =
206 unlink_insn_chain (get_insns (), PREV_INSN (insn));
207 else
208 cfg_layout_function_header = NULL_RTX;
210 next_insn = get_insns ();
211 FOR_EACH_BB (bb)
213 rtx end;
215 if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
216 bb->rbi->header = unlink_insn_chain (next_insn,
217 PREV_INSN (BB_HEAD (bb)));
218 end = skip_insns_after_block (bb);
219 if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
220 bb->rbi->footer = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
221 next_insn = NEXT_INSN (BB_END (bb));
224 cfg_layout_function_footer = next_insn;
225 if (cfg_layout_function_footer)
226 cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
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 GTY(()) varray_type block_locators_locs;
237 static GTY(()) varray_type block_locators_blocks;
238 static GTY(()) varray_type line_locators_locs;
239 static GTY(()) varray_type line_locators_lines;
240 static GTY(()) varray_type 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
247 INSN_LOCATORs. */
249 void
250 insn_locators_initialize (void)
252 tree block = NULL;
253 tree last_block = NULL;
254 rtx insn, next;
255 int loc = 0;
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 VARRAY_INT_INIT (block_locators_locs, 32, "block_locators_locs");
262 VARRAY_TREE_INIT (block_locators_blocks, 32, "block_locators_blocks");
263 VARRAY_INT_INIT (line_locators_locs, 32, "line_locators_locs");
264 VARRAY_INT_INIT (line_locators_lines, 32, "line_locators_lines");
265 VARRAY_INT_INIT (file_locators_locs, 32, "file_locators_locs");
266 VARRAY_CHAR_PTR_INIT (file_locators_files, 32, "file_locators_files");
268 for (insn = get_insns (); insn; insn = next)
270 next = NEXT_INSN (insn);
272 if ((active_insn_p (insn)
273 && GET_CODE (PATTERN (insn)) != ADDR_VEC
274 && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC)
275 || !NEXT_INSN (insn)
276 || (!prologue_locator && file_name))
278 if (last_block != block)
280 loc++;
281 VARRAY_PUSH_INT (block_locators_locs, loc);
282 VARRAY_PUSH_TREE (block_locators_blocks, block);
283 last_block = block;
285 if (last_line_number != line_number)
287 loc++;
288 VARRAY_PUSH_INT (line_locators_locs, loc);
289 VARRAY_PUSH_INT (line_locators_lines, line_number);
290 last_line_number = line_number;
292 if (last_file_name != file_name)
294 loc++;
295 VARRAY_PUSH_INT (file_locators_locs, loc);
296 VARRAY_PUSH_CHAR_PTR (file_locators_files, (char *) file_name);
297 last_file_name = file_name;
300 if (!prologue_locator && file_name)
301 prologue_locator = loc;
302 if (!NEXT_INSN (insn))
303 epilogue_locator = loc;
304 if (active_insn_p (insn))
305 INSN_LOCATOR (insn) = loc;
306 else if (NOTE_P (insn))
308 switch (NOTE_LINE_NUMBER (insn))
310 case NOTE_INSN_BLOCK_BEG:
311 case NOTE_INSN_BLOCK_END:
312 abort ();
314 default:
315 if (NOTE_LINE_NUMBER (insn) > 0)
317 expanded_location xloc;
318 NOTE_EXPANDED_LOCATION (xloc, insn);
319 line_number = xloc.line;
320 file_name = xloc.file;
322 break;
326 check_block_change (insn, &block);
329 /* Tag the blocks with a depth number so that change_scope can find
330 the common parent easily. */
331 set_block_levels (DECL_INITIAL (cfun->decl), 0);
333 free_block_changes ();
336 /* For each lexical block, set BLOCK_NUMBER to the depth at which it is
337 found in the block tree. */
339 static void
340 set_block_levels (tree block, int level)
342 while (block)
344 BLOCK_NUMBER (block) = level;
345 set_block_levels (BLOCK_SUBBLOCKS (block), level + 1);
346 block = BLOCK_CHAIN (block);
350 /* Return sope resulting from combination of S1 and S2. */
351 tree
352 choose_inner_scope (tree s1, tree s2)
354 if (!s1)
355 return s2;
356 if (!s2)
357 return s1;
358 if (BLOCK_NUMBER (s1) > BLOCK_NUMBER (s2))
359 return s1;
360 return s2;
363 /* Emit lexical block notes needed to change scope from S1 to S2. */
365 static void
366 change_scope (rtx orig_insn, tree s1, tree s2)
368 rtx insn = orig_insn;
369 tree com = NULL_TREE;
370 tree ts1 = s1, ts2 = s2;
371 tree s;
373 while (ts1 != ts2)
375 if (ts1 == NULL || ts2 == NULL)
376 abort ();
377 if (BLOCK_NUMBER (ts1) > BLOCK_NUMBER (ts2))
378 ts1 = BLOCK_SUPERCONTEXT (ts1);
379 else if (BLOCK_NUMBER (ts1) < BLOCK_NUMBER (ts2))
380 ts2 = BLOCK_SUPERCONTEXT (ts2);
381 else
383 ts1 = BLOCK_SUPERCONTEXT (ts1);
384 ts2 = BLOCK_SUPERCONTEXT (ts2);
387 com = ts1;
389 /* Close scopes. */
390 s = s1;
391 while (s != com)
393 rtx note = emit_note_before (NOTE_INSN_BLOCK_END, insn);
394 NOTE_BLOCK (note) = s;
395 s = BLOCK_SUPERCONTEXT (s);
398 /* Open scopes. */
399 s = s2;
400 while (s != com)
402 insn = emit_note_before (NOTE_INSN_BLOCK_BEG, insn);
403 NOTE_BLOCK (insn) = s;
404 s = BLOCK_SUPERCONTEXT (s);
408 /* Return lexical scope block insn belong to. */
409 static tree
410 insn_scope (rtx insn)
412 int max = VARRAY_ACTIVE_SIZE (block_locators_locs);
413 int min = 0;
414 int loc = INSN_LOCATOR (insn);
416 /* When block_locators_locs was initialized, the pro- and epilogue
417 insns didn't exist yet and can therefore not be found this way.
418 But we know that they belong to the outer most block of the
419 current function.
420 Without this test, the prologue would be put inside the block of
421 the first valid instruction in the function and when that first
422 insn is part of an inlined function then the low_pc of that
423 inlined function is messed up. Likewise for the epilogue and
424 the last valid instruction. */
425 if (loc == prologue_locator || loc == epilogue_locator)
426 return DECL_INITIAL (cfun->decl);
428 if (!max || !loc)
429 return NULL;
430 while (1)
432 int pos = (min + max) / 2;
433 int tmp = VARRAY_INT (block_locators_locs, pos);
435 if (tmp <= loc && min != pos)
436 min = pos;
437 else if (tmp > loc && max != pos)
438 max = pos;
439 else
441 min = pos;
442 break;
445 return VARRAY_TREE (block_locators_blocks, min);
448 /* Return line number of the statement specified by the locator. */
450 locator_line (int loc)
452 int max = VARRAY_ACTIVE_SIZE (line_locators_locs);
453 int min = 0;
455 if (!max || !loc)
456 return 0;
457 while (1)
459 int pos = (min + max) / 2;
460 int tmp = VARRAY_INT (line_locators_locs, pos);
462 if (tmp <= loc && min != pos)
463 min = pos;
464 else if (tmp > loc && max != pos)
465 max = pos;
466 else
468 min = pos;
469 break;
472 return VARRAY_INT (line_locators_lines, min);
475 /* Return line number of the statement that produced this insn. */
477 insn_line (rtx insn)
479 return locator_line (INSN_LOCATOR (insn));
482 /* Return source file of the statement specified by LOC. */
483 const char *
484 locator_file (int loc)
486 int max = VARRAY_ACTIVE_SIZE (file_locators_locs);
487 int min = 0;
489 if (!max || !loc)
490 return NULL;
491 while (1)
493 int pos = (min + max) / 2;
494 int tmp = VARRAY_INT (file_locators_locs, pos);
496 if (tmp <= loc && min != pos)
497 min = pos;
498 else if (tmp > loc && max != pos)
499 max = pos;
500 else
502 min = pos;
503 break;
506 return VARRAY_CHAR_PTR (file_locators_files, min);
509 /* Return source file of the statement that produced this insn. */
510 const char *
511 insn_file (rtx insn)
513 return locator_file (INSN_LOCATOR (insn));
516 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
517 on the scope tree and the newly reordered instructions. */
519 void
520 reemit_insn_block_notes (void)
522 tree cur_block = DECL_INITIAL (cfun->decl);
523 rtx insn, note;
525 insn = get_insns ();
526 if (!active_insn_p (insn))
527 insn = next_active_insn (insn);
528 for (; insn; insn = next_active_insn (insn))
530 tree this_block;
532 this_block = insn_scope (insn);
533 /* For sequences compute scope resulting from merging all scopes
534 of instructions nested inside. */
535 if (GET_CODE (PATTERN (insn)) == SEQUENCE)
537 int i;
538 rtx body = PATTERN (insn);
540 this_block = NULL;
541 for (i = 0; i < XVECLEN (body, 0); i++)
542 this_block = choose_inner_scope (this_block,
543 insn_scope (XVECEXP (body, 0, i)));
545 if (! this_block)
546 continue;
548 if (this_block != cur_block)
550 change_scope (insn, cur_block, this_block);
551 cur_block = this_block;
555 /* change_scope emits before the insn, not after. */
556 note = emit_note (NOTE_INSN_DELETED);
557 change_scope (note, cur_block, DECL_INITIAL (cfun->decl));
558 delete_insn (note);
560 reorder_blocks ();
563 /* Given a reorder chain, rearrange the code to match. */
565 static void
566 fixup_reorder_chain (void)
568 basic_block bb, prev_bb;
569 int index;
570 rtx insn = NULL;
572 if (cfg_layout_function_header)
574 set_first_insn (cfg_layout_function_header);
575 insn = cfg_layout_function_header;
576 while (NEXT_INSN (insn))
577 insn = NEXT_INSN (insn);
580 /* First do the bulk reordering -- rechain the blocks without regard to
581 the needed changes to jumps and labels. */
583 for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
584 bb != 0;
585 bb = bb->rbi->next, index++)
587 if (bb->rbi->header)
589 if (insn)
590 NEXT_INSN (insn) = bb->rbi->header;
591 else
592 set_first_insn (bb->rbi->header);
593 PREV_INSN (bb->rbi->header) = insn;
594 insn = bb->rbi->header;
595 while (NEXT_INSN (insn))
596 insn = NEXT_INSN (insn);
598 if (insn)
599 NEXT_INSN (insn) = BB_HEAD (bb);
600 else
601 set_first_insn (BB_HEAD (bb));
602 PREV_INSN (BB_HEAD (bb)) = insn;
603 insn = BB_END (bb);
604 if (bb->rbi->footer)
606 NEXT_INSN (insn) = bb->rbi->footer;
607 PREV_INSN (bb->rbi->footer) = insn;
608 while (NEXT_INSN (insn))
609 insn = NEXT_INSN (insn);
613 if (index != n_basic_blocks)
614 abort ();
616 NEXT_INSN (insn) = cfg_layout_function_footer;
617 if (cfg_layout_function_footer)
618 PREV_INSN (cfg_layout_function_footer) = insn;
620 while (NEXT_INSN (insn))
621 insn = NEXT_INSN (insn);
623 set_last_insn (insn);
624 #ifdef ENABLE_CHECKING
625 verify_insn_chain ();
626 #endif
627 delete_dead_jumptables ();
629 /* Now add jumps and labels as needed to match the blocks new
630 outgoing edges. */
632 for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = bb->rbi->next)
634 edge e_fall, e_taken, e;
635 rtx bb_end_insn;
636 basic_block nb;
637 basic_block old_bb;
639 if (bb->succ == NULL)
640 continue;
642 /* Find the old fallthru edge, and another non-EH edge for
643 a taken jump. */
644 e_taken = e_fall = NULL;
645 for (e = bb->succ; e ; e = e->succ_next)
646 if (e->flags & EDGE_FALLTHRU)
647 e_fall = e;
648 else if (! (e->flags & EDGE_EH))
649 e_taken = e;
651 bb_end_insn = BB_END (bb);
652 if (JUMP_P (bb_end_insn))
654 if (any_condjump_p (bb_end_insn))
656 /* If the old fallthru is still next, nothing to do. */
657 if (bb->rbi->next == e_fall->dest
658 || e_fall->dest == EXIT_BLOCK_PTR)
659 continue;
661 /* The degenerated case of conditional jump jumping to the next
662 instruction can happen on target having jumps with side
663 effects.
665 Create temporarily the duplicated edge representing branch.
666 It will get unidentified by force_nonfallthru_and_redirect
667 that would otherwise get confused by fallthru edge not pointing
668 to the next basic block. */
669 if (!e_taken)
671 rtx note;
672 edge e_fake;
674 e_fake = unchecked_make_edge (bb, e_fall->dest, 0);
676 if (!redirect_jump (BB_END (bb), block_label (bb), 0))
677 abort ();
678 note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
679 if (note)
681 int prob = INTVAL (XEXP (note, 0));
683 e_fake->probability = prob;
684 e_fake->count = e_fall->count * prob / REG_BR_PROB_BASE;
685 e_fall->probability -= e_fall->probability;
686 e_fall->count -= e_fake->count;
687 if (e_fall->probability < 0)
688 e_fall->probability = 0;
689 if (e_fall->count < 0)
690 e_fall->count = 0;
693 /* There is one special case: if *neither* block is next,
694 such as happens at the very end of a function, then we'll
695 need to add a new unconditional jump. Choose the taken
696 edge based on known or assumed probability. */
697 else if (bb->rbi->next != e_taken->dest)
699 rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
701 if (note
702 && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
703 && invert_jump (bb_end_insn,
704 (e_fall->dest == EXIT_BLOCK_PTR
705 ? NULL_RTX
706 : label_for_bb (e_fall->dest)), 0))
708 e_fall->flags &= ~EDGE_FALLTHRU;
709 #ifdef ENABLE_CHECKING
710 if (!could_fall_through (e_taken->src, e_taken->dest))
711 abort ();
712 #endif
713 e_taken->flags |= EDGE_FALLTHRU;
714 update_br_prob_note (bb);
715 e = e_fall, e_fall = e_taken, e_taken = e;
719 /* If the "jumping" edge is a crossing edge, and the fall
720 through edge is non-crossing, leave things as they are. */
721 else if (e_taken->crossing_edge && !e_fall->crossing_edge)
722 continue;
724 /* Otherwise we can try to invert the jump. This will
725 basically never fail, however, keep up the pretense. */
726 else if (invert_jump (bb_end_insn,
727 (e_fall->dest == EXIT_BLOCK_PTR
728 ? NULL_RTX
729 : label_for_bb (e_fall->dest)), 0))
731 e_fall->flags &= ~EDGE_FALLTHRU;
732 #ifdef ENABLE_CHECKING
733 if (!could_fall_through (e_taken->src, e_taken->dest))
734 abort ();
735 #endif
736 e_taken->flags |= EDGE_FALLTHRU;
737 update_br_prob_note (bb);
738 continue;
741 else if (returnjump_p (bb_end_insn))
742 continue;
743 else
745 /* Otherwise we have some switch or computed jump. In the
746 99% case, there should not have been a fallthru edge. */
747 if (! e_fall)
748 continue;
750 #ifdef CASE_DROPS_THROUGH
751 /* Except for VAX. Since we didn't have predication for the
752 tablejump, the fallthru block should not have moved. */
753 if (bb->rbi->next == e_fall->dest)
754 continue;
755 bb_end_insn = skip_insns_after_block (bb);
756 #else
757 abort ();
758 #endif
761 else
763 /* No fallthru implies a noreturn function with EH edges, or
764 something similarly bizarre. In any case, we don't need to
765 do anything. */
766 if (! e_fall)
767 continue;
769 /* If the fallthru block is still next, nothing to do. */
770 if (bb->rbi->next == e_fall->dest)
771 continue;
773 /* A fallthru to exit block. */
774 if (e_fall->dest == EXIT_BLOCK_PTR)
775 continue;
778 /* We got here if we need to add a new jump insn. */
779 nb = force_nonfallthru (e_fall);
780 if (nb)
782 initialize_bb_rbi (nb);
783 nb->rbi->visited = 1;
784 nb->rbi->next = bb->rbi->next;
785 bb->rbi->next = nb;
786 /* Don't process this new block. */
787 old_bb = bb;
788 bb = nb;
790 /* Make sure new bb is tagged for correct section (same as
791 fall-thru source). */
792 e_fall->src->partition = bb->pred->src->partition;
793 if (flag_reorder_blocks_and_partition)
795 if (bb->pred->src->partition == COLD_PARTITION)
797 rtx new_note;
798 rtx note = BB_HEAD (e_fall->src);
800 while (!INSN_P (note)
801 && note != BB_END (e_fall->src))
802 note = NEXT_INSN (note);
804 new_note = emit_note_before
805 (NOTE_INSN_UNLIKELY_EXECUTED_CODE,
806 note);
807 NOTE_BASIC_BLOCK (new_note) = bb;
809 if (JUMP_P (BB_END (bb))
810 && !any_condjump_p (BB_END (bb))
811 && bb->succ->crossing_edge )
812 REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST
813 (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb)));
818 /* Put basic_block_info in the new order. */
820 if (dump_file)
822 fprintf (dump_file, "Reordered sequence:\n");
823 for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
825 bb = bb->rbi->next, index++)
827 fprintf (dump_file, " %i ", index);
828 if (bb->rbi->original)
829 fprintf (dump_file, "duplicate of %i ",
830 bb->rbi->original->index);
831 else if (forwarder_block_p (bb)
832 && !LABEL_P (BB_HEAD (bb)))
833 fprintf (dump_file, "compensation ");
834 else
835 fprintf (dump_file, "bb %i ", bb->index);
836 fprintf (dump_file, " [%i]\n", bb->frequency);
840 prev_bb = ENTRY_BLOCK_PTR;
841 bb = ENTRY_BLOCK_PTR->next_bb;
842 index = 0;
844 for (; bb; prev_bb = bb, bb = bb->rbi->next, index ++)
846 bb->index = index;
847 BASIC_BLOCK (index) = bb;
849 update_unlikely_executed_notes (bb);
851 bb->prev_bb = prev_bb;
852 prev_bb->next_bb = bb;
854 prev_bb->next_bb = EXIT_BLOCK_PTR;
855 EXIT_BLOCK_PTR->prev_bb = prev_bb;
857 /* Annoying special case - jump around dead jumptables left in the code. */
858 FOR_EACH_BB (bb)
860 edge e;
861 for (e = bb->succ; e && !(e->flags & EDGE_FALLTHRU); e = e->succ_next)
862 continue;
863 if (e && !can_fallthru (e->src, e->dest))
864 force_nonfallthru (e);
868 /* Update the basic block number information in any
869 NOTE_INSN_UNLIKELY_EXECUTED_CODE notes within the basic block. */
871 static void
872 update_unlikely_executed_notes (basic_block bb)
874 rtx cur_insn;
876 for (cur_insn = BB_HEAD (bb); cur_insn != BB_END (bb);
877 cur_insn = NEXT_INSN (cur_insn))
878 if (NOTE_P (cur_insn)
879 && NOTE_LINE_NUMBER (cur_insn) == NOTE_INSN_UNLIKELY_EXECUTED_CODE)
880 NOTE_BASIC_BLOCK (cur_insn) = bb;
883 /* Perform sanity checks on the insn chain.
884 1. Check that next/prev pointers are consistent in both the forward and
885 reverse direction.
886 2. Count insns in chain, going both directions, and check if equal.
887 3. Check that get_last_insn () returns the actual end of chain. */
889 void
890 verify_insn_chain (void)
892 rtx x, prevx, nextx;
893 int insn_cnt1, insn_cnt2;
895 for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
896 x != 0;
897 prevx = x, insn_cnt1++, x = NEXT_INSN (x))
898 if (PREV_INSN (x) != prevx)
899 abort ();
901 if (prevx != get_last_insn ())
902 abort ();
904 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
905 x != 0;
906 nextx = x, insn_cnt2++, x = PREV_INSN (x))
907 if (NEXT_INSN (x) != nextx)
908 abort ();
910 if (insn_cnt1 != insn_cnt2)
911 abort ();
914 /* If we have assembler epilogues, the block falling through to exit must
915 be the last one in the reordered chain when we reach final. Ensure
916 that this condition is met. */
917 static void
918 fixup_fallthru_exit_predecessor (void)
920 edge e;
921 basic_block bb = NULL;
923 /* This transformation is not valid before reload, because we might separate
924 a call from the instruction that copies the return value. */
925 if (! reload_completed)
926 abort ();
928 for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
929 if (e->flags & EDGE_FALLTHRU)
930 bb = e->src;
932 if (bb && bb->rbi->next)
934 basic_block c = ENTRY_BLOCK_PTR->next_bb;
936 /* If the very first block is the one with the fall-through exit
937 edge, we have to split that block. */
938 if (c == bb)
940 bb = split_block (bb, NULL)->dest;
941 initialize_bb_rbi (bb);
942 bb->rbi->next = c->rbi->next;
943 c->rbi->next = bb;
944 bb->rbi->footer = c->rbi->footer;
945 c->rbi->footer = NULL;
948 while (c->rbi->next != bb)
949 c = c->rbi->next;
951 c->rbi->next = bb->rbi->next;
952 while (c->rbi->next)
953 c = c->rbi->next;
955 c->rbi->next = bb;
956 bb->rbi->next = NULL;
960 /* Return true in case it is possible to duplicate the basic block BB. */
962 /* We do not want to declare the function in a header file, since it should
963 only be used through the cfghooks interface, and we do not want to move
964 it to cfgrtl.c since it would require also moving quite a lot of related
965 code. */
966 extern bool cfg_layout_can_duplicate_bb_p (basic_block);
968 bool
969 cfg_layout_can_duplicate_bb_p (basic_block bb)
971 /* Do not attempt to duplicate tablejumps, as we need to unshare
972 the dispatch table. This is difficult to do, as the instructions
973 computing jump destination may be hoisted outside the basic block. */
974 if (tablejump_p (BB_END (bb), NULL, NULL))
975 return false;
977 /* Do not duplicate blocks containing insns that can't be copied. */
978 if (targetm.cannot_copy_insn_p)
980 rtx insn = BB_HEAD (bb);
981 while (1)
983 if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
984 return false;
985 if (insn == BB_END (bb))
986 break;
987 insn = NEXT_INSN (insn);
991 return true;
995 duplicate_insn_chain (rtx from, rtx to)
997 rtx insn, last;
999 /* Avoid updating of boundaries of previous basic block. The
1000 note will get removed from insn stream in fixup. */
1001 last = emit_note (NOTE_INSN_DELETED);
1003 /* Create copy at the end of INSN chain. The chain will
1004 be reordered later. */
1005 for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
1007 switch (GET_CODE (insn))
1009 case INSN:
1010 case CALL_INSN:
1011 case JUMP_INSN:
1012 /* Avoid copying of dispatch tables. We never duplicate
1013 tablejumps, so this can hit only in case the table got
1014 moved far from original jump. */
1015 if (GET_CODE (PATTERN (insn)) == ADDR_VEC
1016 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
1017 break;
1018 emit_copy_of_insn_after (insn, get_last_insn ());
1019 break;
1021 case CODE_LABEL:
1022 break;
1024 case BARRIER:
1025 emit_barrier ();
1026 break;
1028 case NOTE:
1029 switch (NOTE_LINE_NUMBER (insn))
1031 /* In case prologue is empty and function contain label
1032 in first BB, we may want to copy the block. */
1033 case NOTE_INSN_PROLOGUE_END:
1035 case NOTE_INSN_LOOP_VTOP:
1036 case NOTE_INSN_LOOP_CONT:
1037 case NOTE_INSN_LOOP_BEG:
1038 case NOTE_INSN_LOOP_END:
1039 /* Strip down the loop notes - we don't really want to keep
1040 them consistent in loop copies. */
1041 case NOTE_INSN_DELETED:
1042 case NOTE_INSN_DELETED_LABEL:
1043 /* No problem to strip these. */
1044 case NOTE_INSN_EPILOGUE_BEG:
1045 case NOTE_INSN_FUNCTION_END:
1046 /* Debug code expect these notes to exist just once.
1047 Keep them in the master copy.
1048 ??? It probably makes more sense to duplicate them for each
1049 epilogue copy. */
1050 case NOTE_INSN_FUNCTION_BEG:
1051 /* There is always just single entry to function. */
1052 case NOTE_INSN_BASIC_BLOCK:
1053 break;
1055 /* There is no purpose to duplicate prologue. */
1056 case NOTE_INSN_BLOCK_BEG:
1057 case NOTE_INSN_BLOCK_END:
1058 /* The BLOCK_BEG/BLOCK_END notes should be eliminated when BB
1059 reordering is in the progress. */
1060 case NOTE_INSN_EH_REGION_BEG:
1061 case NOTE_INSN_EH_REGION_END:
1062 /* Should never exist at BB duplication time. */
1063 abort ();
1064 break;
1065 case NOTE_INSN_REPEATED_LINE_NUMBER:
1066 case NOTE_INSN_UNLIKELY_EXECUTED_CODE:
1067 emit_note_copy (insn);
1068 break;
1070 default:
1071 if (NOTE_LINE_NUMBER (insn) < 0)
1072 abort ();
1073 /* It is possible that no_line_number is set and the note
1074 won't be emitted. */
1075 emit_note_copy (insn);
1077 break;
1078 default:
1079 abort ();
1082 insn = NEXT_INSN (last);
1083 delete_insn (last);
1084 return insn;
1086 /* Create a duplicate of the basic block BB. */
1088 /* We do not want to declare the function in a header file, since it should
1089 only be used through the cfghooks interface, and we do not want to move
1090 it to cfgrtl.c since it would require also moving quite a lot of related
1091 code. */
1092 extern basic_block cfg_layout_duplicate_bb (basic_block);
1094 basic_block
1095 cfg_layout_duplicate_bb (basic_block bb)
1097 rtx insn;
1098 basic_block new_bb;
1100 insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
1101 new_bb = create_basic_block (insn,
1102 insn ? get_last_insn () : NULL,
1103 EXIT_BLOCK_PTR->prev_bb);
1105 if (bb->rbi->header)
1107 insn = bb->rbi->header;
1108 while (NEXT_INSN (insn))
1109 insn = NEXT_INSN (insn);
1110 insn = duplicate_insn_chain (bb->rbi->header, insn);
1111 if (insn)
1112 new_bb->rbi->header = unlink_insn_chain (insn, get_last_insn ());
1115 if (bb->rbi->footer)
1117 insn = bb->rbi->footer;
1118 while (NEXT_INSN (insn))
1119 insn = NEXT_INSN (insn);
1120 insn = duplicate_insn_chain (bb->rbi->footer, insn);
1121 if (insn)
1122 new_bb->rbi->footer = unlink_insn_chain (insn, get_last_insn ());
1125 if (bb->global_live_at_start)
1127 new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1128 new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1129 COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_start);
1130 COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
1133 return new_bb;
1136 /* Main entry point to this module - initialize the datastructures for
1137 CFG layout changes. It keeps LOOPS up-to-date if not null.
1139 FLAGS is a set of additional flags to pass to cleanup_cfg(). It should
1140 include CLEANUP_UPDATE_LIFE if liveness information must be kept up
1141 to date. */
1143 void
1144 cfg_layout_initialize (unsigned int flags)
1146 basic_block bb;
1148 /* Our algorithm depends on fact that there are no dead jumptables
1149 around the code. */
1150 alloc_rbi_pool ();
1152 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1153 initialize_bb_rbi (bb);
1155 cfg_layout_rtl_register_cfg_hooks ();
1157 record_effective_endpoints ();
1159 cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
1162 /* Splits superblocks. */
1163 void
1164 break_superblocks (void)
1166 sbitmap superblocks;
1167 bool need = false;
1168 basic_block bb;
1170 superblocks = sbitmap_alloc (last_basic_block);
1171 sbitmap_zero (superblocks);
1173 FOR_EACH_BB (bb)
1174 if (bb->flags & BB_SUPERBLOCK)
1176 bb->flags &= ~BB_SUPERBLOCK;
1177 SET_BIT (superblocks, bb->index);
1178 need = true;
1181 if (need)
1183 rebuild_jump_labels (get_insns ());
1184 find_many_sub_basic_blocks (superblocks);
1187 free (superblocks);
1190 /* Finalize the changes: reorder insn list according to the sequence, enter
1191 compensation code, rebuild scope forest. */
1193 void
1194 cfg_layout_finalize (void)
1196 basic_block bb;
1198 #ifdef ENABLE_CHECKING
1199 verify_flow_info ();
1200 #endif
1201 rtl_register_cfg_hooks ();
1202 if (reload_completed
1203 #ifdef HAVE_epilogue
1204 && !HAVE_epilogue
1205 #endif
1207 fixup_fallthru_exit_predecessor ();
1208 fixup_reorder_chain ();
1210 #ifdef ENABLE_CHECKING
1211 verify_insn_chain ();
1212 #endif
1214 free_rbi_pool ();
1215 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1216 bb->rbi = NULL;
1218 break_superblocks ();
1220 #ifdef ENABLE_CHECKING
1221 verify_flow_info ();
1222 #endif
1225 /* Checks whether all N blocks in BBS array can be copied. */
1226 bool
1227 can_copy_bbs_p (basic_block *bbs, unsigned n)
1229 unsigned i;
1230 edge e;
1231 int ret = true;
1233 for (i = 0; i < n; i++)
1234 bbs[i]->rbi->duplicated = 1;
1236 for (i = 0; i < n; i++)
1238 /* In case we should redirect abnormal edge during duplication, fail. */
1239 for (e = bbs[i]->succ; e; e = e->succ_next)
1240 if ((e->flags & EDGE_ABNORMAL)
1241 && e->dest->rbi->duplicated)
1243 ret = false;
1244 goto end;
1247 if (!can_duplicate_block_p (bbs[i]))
1249 ret = false;
1250 break;
1254 end:
1255 for (i = 0; i < n; i++)
1256 bbs[i]->rbi->duplicated = 0;
1258 return ret;
1261 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1262 are placed into array NEW_BBS in the same order. Edges from basic blocks
1263 in BBS are also duplicated and copies of those of them
1264 that lead into BBS are redirected to appropriate newly created block. The
1265 function assigns bbs into loops (copy of basic block bb is assigned to
1266 bb->loop_father->copy loop, so this must be set up correctly in advance)
1267 and updates dominators locally (LOOPS structure that contains the information
1268 about dominators is passed to enable this).
1270 BASE is the superloop to that basic block belongs; if its header or latch
1271 is copied, we do not set the new blocks as header or latch.
1273 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1274 also in the same order. */
1276 void
1277 copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
1278 edge *edges, unsigned n_edges, edge *new_edges,
1279 struct loop *base)
1281 unsigned i, j;
1282 basic_block bb, new_bb, dom_bb;
1283 edge e;
1285 /* Duplicate bbs, update dominators, assign bbs to loops. */
1286 for (i = 0; i < n; i++)
1288 /* Duplicate. */
1289 bb = bbs[i];
1290 new_bb = new_bbs[i] = duplicate_block (bb, NULL);
1291 bb->rbi->duplicated = 1;
1292 /* Add to loop. */
1293 add_bb_to_loop (new_bb, bb->loop_father->copy);
1294 /* Possibly set header. */
1295 if (bb->loop_father->header == bb && bb->loop_father != base)
1296 new_bb->loop_father->header = new_bb;
1297 /* Or latch. */
1298 if (bb->loop_father->latch == bb && bb->loop_father != base)
1299 new_bb->loop_father->latch = new_bb;
1302 /* Set dominators. */
1303 for (i = 0; i < n; i++)
1305 bb = bbs[i];
1306 new_bb = new_bbs[i];
1308 dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1309 if (dom_bb->rbi->duplicated)
1311 dom_bb = dom_bb->rbi->copy;
1312 set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
1316 /* Redirect edges. */
1317 for (j = 0; j < n_edges; j++)
1318 new_edges[j] = NULL;
1319 for (i = 0; i < n; i++)
1321 new_bb = new_bbs[i];
1322 bb = bbs[i];
1324 for (e = new_bb->succ; e; e = e->succ_next)
1326 for (j = 0; j < n_edges; j++)
1327 if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest)
1328 new_edges[j] = e;
1330 if (!e->dest->rbi->duplicated)
1331 continue;
1332 redirect_edge_and_branch_force (e, e->dest->rbi->copy);
1336 /* Clear information about duplicates. */
1337 for (i = 0; i < n; i++)
1338 bbs[i]->rbi->duplicated = 0;
1341 #include "gt-cfglayout.h"