1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2003, 2004, 2005 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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.
10
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.
15
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
19 02110-1301, USA. */
20
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 "obstack.h"
29 #include "basic-block.h"
30 #include "insn-config.h"
31 #include "output.h"
32 #include "function.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"
39 #include "tree-pass.h"
40 #include "vecprim.h"
41
42 /* Holds the interesting trailing notes for the function. */
43 rtx cfg_layout_function_footer, cfg_layout_function_header;
44
45 static rtx skip_insns_after_block (basic_block);
46 static void record_effective_endpoints (void);
47 static rtx label_for_bb (basic_block);
48 static void fixup_reorder_chain (void);
49
50 static void set_block_levels (tree, int);
51 static void change_scope (rtx, tree, tree);
52
53 void verify_insn_chain (void);
54 static void fixup_fallthru_exit_predecessor (void);
55 static tree insn_scope (rtx);
56
57 rtx
unlink_insn_chain(rtx first,rtx last)58 unlink_insn_chain (rtx first, rtx last)
59 {
60 rtx prevfirst = PREV_INSN (first);
61 rtx nextlast = NEXT_INSN (last);
62
63 PREV_INSN (first) = NULL;
64 NEXT_INSN (last) = NULL;
65 if (prevfirst)
66 NEXT_INSN (prevfirst) = nextlast;
67 if (nextlast)
68 PREV_INSN (nextlast) = prevfirst;
69 else
70 set_last_insn (prevfirst);
71 if (!prevfirst)
72 set_first_insn (nextlast);
73 return first;
74 }
75
76 /* Skip over inter-block insns occurring after BB which are typically
77 associated with BB (e.g., barriers). If there are any such insns,
78 we return the last one. Otherwise, we return the end of BB. */
79
80 static rtx
skip_insns_after_block(basic_block bb)81 skip_insns_after_block (basic_block bb)
82 {
83 rtx insn, last_insn, next_head, prev;
84
85 next_head = NULL_RTX;
86 if (bb->next_bb != EXIT_BLOCK_PTR)
87 next_head = BB_HEAD (bb->next_bb);
88
89 for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )
90 {
91 if (insn == next_head)
92 break;
93
94 switch (GET_CODE (insn))
95 {
96 case BARRIER:
97 last_insn = insn;
98 continue;
99
100 case NOTE:
101 switch (NOTE_LINE_NUMBER (insn))
102 {
103 case NOTE_INSN_BLOCK_END:
104 last_insn = insn;
105 continue;
106 case NOTE_INSN_DELETED:
107 case NOTE_INSN_DELETED_LABEL:
108 continue;
109
110 default:
111 continue;
112 break;
113 }
114 break;
115
116 case CODE_LABEL:
117 if (NEXT_INSN (insn)
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))
121 {
122 insn = NEXT_INSN (insn);
123 last_insn = insn;
124 continue;
125 }
126 break;
127
128 default:
129 break;
130 }
131
132 break;
133 }
134
135 /* It is possible to hit contradictory sequence. For instance:
136
137 jump_insn
138 NOTE_INSN_BLOCK_BEG
139 barrier
140
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_BLOCK_BEG. In such case reorder the notes. */
144
145 for (insn = last_insn; insn != BB_END (bb); insn = prev)
146 {
147 prev = PREV_INSN (insn);
148 if (NOTE_P (insn))
149 switch (NOTE_LINE_NUMBER (insn))
150 {
151 case NOTE_INSN_BLOCK_END:
152 case NOTE_INSN_DELETED:
153 case NOTE_INSN_DELETED_LABEL:
154 continue;
155 default:
156 reorder_insns (insn, insn, last_insn);
157 }
158 }
159
160 return last_insn;
161 }
162
163 /* Locate or create a label for a given basic block. */
164
165 static rtx
label_for_bb(basic_block bb)166 label_for_bb (basic_block bb)
167 {
168 rtx label = BB_HEAD (bb);
169
170 if (!LABEL_P (label))
171 {
172 if (dump_file)
173 fprintf (dump_file, "Emitting label for block %d\n", bb->index);
174
175 label = block_label (bb);
176 }
177
178 return label;
179 }
180
181 /* Locate the effective beginning and end of the insn chain for each
182 block, as defined by skip_insns_after_block above. */
183
184 static void
record_effective_endpoints(void)185 record_effective_endpoints (void)
186 {
187 rtx next_insn;
188 basic_block bb;
189 rtx insn;
190
191 for (insn = get_insns ();
192 insn
193 && NOTE_P (insn)
194 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK;
195 insn = NEXT_INSN (insn))
196 continue;
197 /* No basic blocks at all? */
198 gcc_assert (insn);
199
200 if (PREV_INSN (insn))
201 cfg_layout_function_header =
202 unlink_insn_chain (get_insns (), PREV_INSN (insn));
203 else
204 cfg_layout_function_header = NULL_RTX;
205
206 next_insn = get_insns ();
207 FOR_EACH_BB (bb)
208 {
209 rtx end;
210
211 if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
212 bb->il.rtl->header = unlink_insn_chain (next_insn,
213 PREV_INSN (BB_HEAD (bb)));
214 end = skip_insns_after_block (bb);
215 if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
216 bb->il.rtl->footer = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
217 next_insn = NEXT_INSN (BB_END (bb));
218 }
219
220 cfg_layout_function_footer = next_insn;
221 if (cfg_layout_function_footer)
222 cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
223 }
224
225 /* Data structures representing mapping of INSN_LOCATOR into scope blocks, line
226 numbers and files. In order to be GGC friendly we need to use separate
227 varrays. This also slightly improve the memory locality in binary search.
228 The _locs array contains locators where the given property change. The
229 block_locators_blocks contains the scope block that is used for all insn
230 locator greater than corresponding block_locators_locs value and smaller
231 than the following one. Similarly for the other properties. */
232 static VEC(int,heap) *block_locators_locs;
233 static GTY(()) VEC(tree,gc) *block_locators_blocks;
234 static VEC(int,heap) *line_locators_locs;
235 static VEC(int,heap) *line_locators_lines;
236 static VEC(int,heap) *file_locators_locs;
237 static GTY(()) varray_type file_locators_files;
238 int prologue_locator;
239 int epilogue_locator;
240
241 /* During the RTL expansion the lexical blocks and line numbers are
242 represented via INSN_NOTEs. Replace them by representation using
243 INSN_LOCATORs. */
244
245 unsigned int
insn_locators_initialize(void)246 insn_locators_initialize (void)
247 {
248 tree block = NULL;
249 tree last_block = NULL;
250 rtx insn, next;
251 int loc = 0;
252 int line_number = 0, last_line_number = 0;
253 const char *file_name = NULL, *last_file_name = NULL;
254
255 prologue_locator = epilogue_locator = 0;
256
257 block_locators_locs = VEC_alloc (int, heap, 32);
258 block_locators_blocks = VEC_alloc (tree, gc, 32);
259 line_locators_locs = VEC_alloc (int, heap, 32);
260 line_locators_lines = VEC_alloc (int, heap, 32);
261 file_locators_locs = VEC_alloc (int, heap, 32);
262 VARRAY_CHAR_PTR_INIT (file_locators_files, 32, "file_locators_files");
263
264 for (insn = get_insns (); insn; insn = next)
265 {
266 int active = 0;
267
268 next = NEXT_INSN (insn);
269
270 if (NOTE_P (insn))
271 {
272 gcc_assert (NOTE_LINE_NUMBER (insn) != NOTE_INSN_BLOCK_BEG
273 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BLOCK_END);
274 if (NOTE_LINE_NUMBER (insn) > 0)
275 {
276 expanded_location xloc;
277 NOTE_EXPANDED_LOCATION (xloc, insn);
278 line_number = xloc.line;
279 file_name = xloc.file;
280 }
281 }
282 else
283 active = (active_insn_p (insn)
284 && GET_CODE (PATTERN (insn)) != ADDR_VEC
285 && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC);
286
287 check_block_change (insn, &block);
288
289 if (active
290 || !next
291 || (!prologue_locator && file_name))
292 {
293 if (last_block != block)
294 {
295 loc++;
296 VEC_safe_push (int, heap, block_locators_locs, loc);
297 VEC_safe_push (tree, gc, block_locators_blocks, block);
298 last_block = block;
299 }
300 if (last_line_number != line_number)
301 {
302 loc++;
303 VEC_safe_push (int, heap, line_locators_locs, loc);
304 VEC_safe_push (int, heap, line_locators_lines, line_number);
305 last_line_number = line_number;
306 }
307 if (last_file_name != file_name)
308 {
309 loc++;
310 VEC_safe_push (int, heap, file_locators_locs, loc);
311 VARRAY_PUSH_CHAR_PTR (file_locators_files, (char *) file_name);
312 last_file_name = file_name;
313 }
314 if (!prologue_locator && file_name)
315 prologue_locator = loc;
316 if (!next)
317 epilogue_locator = loc;
318 if (active)
319 INSN_LOCATOR (insn) = loc;
320 }
321 }
322
323 /* Tag the blocks with a depth number so that change_scope can find
324 the common parent easily. */
325 set_block_levels (DECL_INITIAL (cfun->decl), 0);
326
327 free_block_changes ();
328 return 0;
329 }
330
331 struct tree_opt_pass pass_insn_locators_initialize =
332 {
333 "locators", /* name */
334 NULL, /* gate */
335 insn_locators_initialize, /* execute */
336 NULL, /* sub */
337 NULL, /* next */
338 0, /* static_pass_number */
339 0, /* tv_id */
340 0, /* properties_required */
341 0, /* properties_provided */
342 0, /* properties_destroyed */
343 0, /* todo_flags_start */
344 TODO_dump_func, /* todo_flags_finish */
345 0 /* letter */
346 };
347
348
349 /* For each lexical block, set BLOCK_NUMBER to the depth at which it is
350 found in the block tree. */
351
352 static void
set_block_levels(tree block,int level)353 set_block_levels (tree block, int level)
354 {
355 while (block)
356 {
357 BLOCK_NUMBER (block) = level;
358 set_block_levels (BLOCK_SUBBLOCKS (block), level + 1);
359 block = BLOCK_CHAIN (block);
360 }
361 }
362
363 /* Return sope resulting from combination of S1 and S2. */
364 static tree
choose_inner_scope(tree s1,tree s2)365 choose_inner_scope (tree s1, tree s2)
366 {
367 if (!s1)
368 return s2;
369 if (!s2)
370 return s1;
371 if (BLOCK_NUMBER (s1) > BLOCK_NUMBER (s2))
372 return s1;
373 return s2;
374 }
375
376 /* Emit lexical block notes needed to change scope from S1 to S2. */
377
378 static void
change_scope(rtx orig_insn,tree s1,tree s2)379 change_scope (rtx orig_insn, tree s1, tree s2)
380 {
381 rtx insn = orig_insn;
382 tree com = NULL_TREE;
383 tree ts1 = s1, ts2 = s2;
384 tree s;
385
386 while (ts1 != ts2)
387 {
388 gcc_assert (ts1 && ts2);
389 if (BLOCK_NUMBER (ts1) > BLOCK_NUMBER (ts2))
390 ts1 = BLOCK_SUPERCONTEXT (ts1);
391 else if (BLOCK_NUMBER (ts1) < BLOCK_NUMBER (ts2))
392 ts2 = BLOCK_SUPERCONTEXT (ts2);
393 else
394 {
395 ts1 = BLOCK_SUPERCONTEXT (ts1);
396 ts2 = BLOCK_SUPERCONTEXT (ts2);
397 }
398 }
399 com = ts1;
400
401 /* Close scopes. */
402 s = s1;
403 while (s != com)
404 {
405 rtx note = emit_note_before (NOTE_INSN_BLOCK_END, insn);
406 NOTE_BLOCK (note) = s;
407 s = BLOCK_SUPERCONTEXT (s);
408 }
409
410 /* Open scopes. */
411 s = s2;
412 while (s != com)
413 {
414 insn = emit_note_before (NOTE_INSN_BLOCK_BEG, insn);
415 NOTE_BLOCK (insn) = s;
416 s = BLOCK_SUPERCONTEXT (s);
417 }
418 }
419
420 /* Return lexical scope block insn belong to. */
421 static tree
insn_scope(rtx insn)422 insn_scope (rtx insn)
423 {
424 int max = VEC_length (int, block_locators_locs);
425 int min = 0;
426 int loc = INSN_LOCATOR (insn);
427
428 /* When block_locators_locs was initialized, the pro- and epilogue
429 insns didn't exist yet and can therefore not be found this way.
430 But we know that they belong to the outer most block of the
431 current function.
432 Without this test, the prologue would be put inside the block of
433 the first valid instruction in the function and when that first
434 insn is part of an inlined function then the low_pc of that
435 inlined function is messed up. Likewise for the epilogue and
436 the last valid instruction. */
437 if (loc == prologue_locator || loc == epilogue_locator)
438 return DECL_INITIAL (cfun->decl);
439
440 if (!max || !loc)
441 return NULL;
442 while (1)
443 {
444 int pos = (min + max) / 2;
445 int tmp = VEC_index (int, block_locators_locs, pos);
446
447 if (tmp <= loc && min != pos)
448 min = pos;
449 else if (tmp > loc && max != pos)
450 max = pos;
451 else
452 {
453 min = pos;
454 break;
455 }
456 }
457 return VEC_index (tree, block_locators_blocks, min);
458 }
459
460 /* Return line number of the statement specified by the locator. */
461 int
locator_line(int loc)462 locator_line (int loc)
463 {
464 int max = VEC_length (int, line_locators_locs);
465 int min = 0;
466
467 if (!max || !loc)
468 return 0;
469 while (1)
470 {
471 int pos = (min + max) / 2;
472 int tmp = VEC_index (int, line_locators_locs, pos);
473
474 if (tmp <= loc && min != pos)
475 min = pos;
476 else if (tmp > loc && max != pos)
477 max = pos;
478 else
479 {
480 min = pos;
481 break;
482 }
483 }
484 return VEC_index (int, line_locators_lines, min);
485 }
486
487 /* Return line number of the statement that produced this insn. */
488 int
insn_line(rtx insn)489 insn_line (rtx insn)
490 {
491 return locator_line (INSN_LOCATOR (insn));
492 }
493
494 /* Return source file of the statement specified by LOC. */
495 const char *
locator_file(int loc)496 locator_file (int loc)
497 {
498 int max = VEC_length (int, file_locators_locs);
499 int min = 0;
500
501 if (!max || !loc)
502 return NULL;
503 while (1)
504 {
505 int pos = (min + max) / 2;
506 int tmp = VEC_index (int, file_locators_locs, pos);
507
508 if (tmp <= loc && min != pos)
509 min = pos;
510 else if (tmp > loc && max != pos)
511 max = pos;
512 else
513 {
514 min = pos;
515 break;
516 }
517 }
518 return VARRAY_CHAR_PTR (file_locators_files, min);
519 }
520
521 /* Return source file of the statement that produced this insn. */
522 const char *
insn_file(rtx insn)523 insn_file (rtx insn)
524 {
525 return locator_file (INSN_LOCATOR (insn));
526 }
527
528 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
529 on the scope tree and the newly reordered instructions. */
530
531 void
reemit_insn_block_notes(void)532 reemit_insn_block_notes (void)
533 {
534 tree cur_block = DECL_INITIAL (cfun->decl);
535 rtx insn, note;
536
537 insn = get_insns ();
538 if (!active_insn_p (insn))
539 insn = next_active_insn (insn);
540 for (; insn; insn = next_active_insn (insn))
541 {
542 tree this_block;
543
544 /* Avoid putting scope notes between jump table and its label. */
545 if (JUMP_P (insn)
546 && (GET_CODE (PATTERN (insn)) == ADDR_VEC
547 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
548 continue;
549
550 this_block = insn_scope (insn);
551 /* For sequences compute scope resulting from merging all scopes
552 of instructions nested inside. */
553 if (GET_CODE (PATTERN (insn)) == SEQUENCE)
554 {
555 int i;
556 rtx body = PATTERN (insn);
557
558 this_block = NULL;
559 for (i = 0; i < XVECLEN (body, 0); i++)
560 this_block = choose_inner_scope (this_block,
561 insn_scope (XVECEXP (body, 0, i)));
562 }
563 if (! this_block)
564 continue;
565
566 if (this_block != cur_block)
567 {
568 change_scope (insn, cur_block, this_block);
569 cur_block = this_block;
570 }
571 }
572
573 /* change_scope emits before the insn, not after. */
574 note = emit_note (NOTE_INSN_DELETED);
575 change_scope (note, cur_block, DECL_INITIAL (cfun->decl));
576 delete_insn (note);
577
578 reorder_blocks ();
579 }
580
581 /* Given a reorder chain, rearrange the code to match. */
582
583 static void
fixup_reorder_chain(void)584 fixup_reorder_chain (void)
585 {
586 basic_block bb, prev_bb;
587 int index;
588 rtx insn = NULL;
589
590 if (cfg_layout_function_header)
591 {
592 set_first_insn (cfg_layout_function_header);
593 insn = cfg_layout_function_header;
594 while (NEXT_INSN (insn))
595 insn = NEXT_INSN (insn);
596 }
597
598 /* First do the bulk reordering -- rechain the blocks without regard to
599 the needed changes to jumps and labels. */
600
601 for (bb = ENTRY_BLOCK_PTR->next_bb, index = NUM_FIXED_BLOCKS;
602 bb != 0;
603 bb = bb->aux, index++)
604 {
605 if (bb->il.rtl->header)
606 {
607 if (insn)
608 NEXT_INSN (insn) = bb->il.rtl->header;
609 else
610 set_first_insn (bb->il.rtl->header);
611 PREV_INSN (bb->il.rtl->header) = insn;
612 insn = bb->il.rtl->header;
613 while (NEXT_INSN (insn))
614 insn = NEXT_INSN (insn);
615 }
616 if (insn)
617 NEXT_INSN (insn) = BB_HEAD (bb);
618 else
619 set_first_insn (BB_HEAD (bb));
620 PREV_INSN (BB_HEAD (bb)) = insn;
621 insn = BB_END (bb);
622 if (bb->il.rtl->footer)
623 {
624 NEXT_INSN (insn) = bb->il.rtl->footer;
625 PREV_INSN (bb->il.rtl->footer) = insn;
626 while (NEXT_INSN (insn))
627 insn = NEXT_INSN (insn);
628 }
629 }
630
631 gcc_assert (index == n_basic_blocks);
632
633 NEXT_INSN (insn) = cfg_layout_function_footer;
634 if (cfg_layout_function_footer)
635 PREV_INSN (cfg_layout_function_footer) = insn;
636
637 while (NEXT_INSN (insn))
638 insn = NEXT_INSN (insn);
639
640 set_last_insn (insn);
641 #ifdef ENABLE_CHECKING
642 verify_insn_chain ();
643 #endif
644 delete_dead_jumptables ();
645
646 /* Now add jumps and labels as needed to match the blocks new
647 outgoing edges. */
648
649 for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = bb->aux)
650 {
651 edge e_fall, e_taken, e;
652 rtx bb_end_insn;
653 basic_block nb;
654 edge_iterator ei;
655
656 if (EDGE_COUNT (bb->succs) == 0)
657 continue;
658
659 /* Find the old fallthru edge, and another non-EH edge for
660 a taken jump. */
661 e_taken = e_fall = NULL;
662
663 FOR_EACH_EDGE (e, ei, bb->succs)
664 if (e->flags & EDGE_FALLTHRU)
665 e_fall = e;
666 else if (! (e->flags & EDGE_EH))
667 e_taken = e;
668
669 bb_end_insn = BB_END (bb);
670 if (JUMP_P (bb_end_insn))
671 {
672 if (any_condjump_p (bb_end_insn))
673 {
674 /* If the old fallthru is still next, nothing to do. */
675 if (bb->aux == e_fall->dest
676 || e_fall->dest == EXIT_BLOCK_PTR)
677 continue;
678
679 /* The degenerated case of conditional jump jumping to the next
680 instruction can happen for jumps with side effects. We need
681 to construct a forwarder block and this will be done just
682 fine by force_nonfallthru below. */
683 if (!e_taken)
684 ;
685
686 /* There is another special case: if *neither* block is next,
687 such as happens at the very end of a function, then we'll
688 need to add a new unconditional jump. Choose the taken
689 edge based on known or assumed probability. */
690 else if (bb->aux != e_taken->dest)
691 {
692 rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
693
694 if (note
695 && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
696 && invert_jump (bb_end_insn,
697 (e_fall->dest == EXIT_BLOCK_PTR
698 ? NULL_RTX
699 : label_for_bb (e_fall->dest)), 0))
700 {
701 e_fall->flags &= ~EDGE_FALLTHRU;
702 #ifdef ENABLE_CHECKING
703 gcc_assert (could_fall_through
704 (e_taken->src, e_taken->dest));
705 #endif
706 e_taken->flags |= EDGE_FALLTHRU;
707 update_br_prob_note (bb);
708 e = e_fall, e_fall = e_taken, e_taken = e;
709 }
710 }
711
712 /* If the "jumping" edge is a crossing edge, and the fall
713 through edge is non-crossing, leave things as they are. */
714 else if ((e_taken->flags & EDGE_CROSSING)
715 && !(e_fall->flags & EDGE_CROSSING))
716 continue;
717
718 /* Otherwise we can try to invert the jump. This will
719 basically never fail, however, keep up the pretense. */
720 else if (invert_jump (bb_end_insn,
721 (e_fall->dest == EXIT_BLOCK_PTR
722 ? NULL_RTX
723 : label_for_bb (e_fall->dest)), 0))
724 {
725 e_fall->flags &= ~EDGE_FALLTHRU;
726 #ifdef ENABLE_CHECKING
727 gcc_assert (could_fall_through
728 (e_taken->src, e_taken->dest));
729 #endif
730 e_taken->flags |= EDGE_FALLTHRU;
731 update_br_prob_note (bb);
732 continue;
733 }
734 }
735 else
736 {
737 /* Otherwise we have some return, switch or computed
738 jump. In the 99% case, there should not have been a
739 fallthru edge. */
740 gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
741 continue;
742 }
743 }
744 else
745 {
746 /* No fallthru implies a noreturn function with EH edges, or
747 something similarly bizarre. In any case, we don't need to
748 do anything. */
749 if (! e_fall)
750 continue;
751
752 /* If the fallthru block is still next, nothing to do. */
753 if (bb->aux == e_fall->dest)
754 continue;
755
756 /* A fallthru to exit block. */
757 if (e_fall->dest == EXIT_BLOCK_PTR)
758 continue;
759 }
760
761 /* We got here if we need to add a new jump insn. */
762 nb = force_nonfallthru (e_fall);
763 if (nb)
764 {
765 nb->il.rtl->visited = 1;
766 nb->aux = bb->aux;
767 bb->aux = nb;
768 /* Don't process this new block. */
769 bb = nb;
770
771 /* Make sure new bb is tagged for correct section (same as
772 fall-thru source, since you cannot fall-throu across
773 section boundaries). */
774 BB_COPY_PARTITION (e_fall->src, single_pred (bb));
775 if (flag_reorder_blocks_and_partition
776 && targetm.have_named_sections
777 && JUMP_P (BB_END (bb))
778 && !any_condjump_p (BB_END (bb))
779 && (EDGE_SUCC (bb, 0)->flags & EDGE_CROSSING))
780 REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST
781 (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb)));
782 }
783 }
784
785 /* Put basic_block_info in the new order. */
786
787 if (dump_file)
788 {
789 fprintf (dump_file, "Reordered sequence:\n");
790 for (bb = ENTRY_BLOCK_PTR->next_bb, index = NUM_FIXED_BLOCKS;
791 bb;
792 bb = bb->aux, index++)
793 {
794 fprintf (dump_file, " %i ", index);
795 if (get_bb_original (bb))
796 fprintf (dump_file, "duplicate of %i ",
797 get_bb_original (bb)->index);
798 else if (forwarder_block_p (bb)
799 && !LABEL_P (BB_HEAD (bb)))
800 fprintf (dump_file, "compensation ");
801 else
802 fprintf (dump_file, "bb %i ", bb->index);
803 fprintf (dump_file, " [%i]\n", bb->frequency);
804 }
805 }
806
807 prev_bb = ENTRY_BLOCK_PTR;
808 bb = ENTRY_BLOCK_PTR->next_bb;
809 index = NUM_FIXED_BLOCKS;
810
811 for (; bb; prev_bb = bb, bb = bb->aux, index ++)
812 {
813 bb->index = index;
814 SET_BASIC_BLOCK (index, bb);
815
816 bb->prev_bb = prev_bb;
817 prev_bb->next_bb = bb;
818 }
819 prev_bb->next_bb = EXIT_BLOCK_PTR;
820 EXIT_BLOCK_PTR->prev_bb = prev_bb;
821
822 /* Annoying special case - jump around dead jumptables left in the code. */
823 FOR_EACH_BB (bb)
824 {
825 edge e;
826 edge_iterator ei;
827
828 FOR_EACH_EDGE (e, ei, bb->succs)
829 if (e->flags & EDGE_FALLTHRU)
830 break;
831
832 if (e && !can_fallthru (e->src, e->dest))
833 force_nonfallthru (e);
834 }
835 }
836
837 /* Perform sanity checks on the insn chain.
838 1. Check that next/prev pointers are consistent in both the forward and
839 reverse direction.
840 2. Count insns in chain, going both directions, and check if equal.
841 3. Check that get_last_insn () returns the actual end of chain. */
842
843 void
verify_insn_chain(void)844 verify_insn_chain (void)
845 {
846 rtx x, prevx, nextx;
847 int insn_cnt1, insn_cnt2;
848
849 for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
850 x != 0;
851 prevx = x, insn_cnt1++, x = NEXT_INSN (x))
852 gcc_assert (PREV_INSN (x) == prevx);
853
854 gcc_assert (prevx == get_last_insn ());
855
856 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
857 x != 0;
858 nextx = x, insn_cnt2++, x = PREV_INSN (x))
859 gcc_assert (NEXT_INSN (x) == nextx);
860
861 gcc_assert (insn_cnt1 == insn_cnt2);
862 }
863
864 /* If we have assembler epilogues, the block falling through to exit must
865 be the last one in the reordered chain when we reach final. Ensure
866 that this condition is met. */
867 static void
fixup_fallthru_exit_predecessor(void)868 fixup_fallthru_exit_predecessor (void)
869 {
870 edge e;
871 edge_iterator ei;
872 basic_block bb = NULL;
873
874 /* This transformation is not valid before reload, because we might
875 separate a call from the instruction that copies the return
876 value. */
877 gcc_assert (reload_completed);
878
879 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
880 if (e->flags & EDGE_FALLTHRU)
881 bb = e->src;
882
883 if (bb && bb->aux)
884 {
885 basic_block c = ENTRY_BLOCK_PTR->next_bb;
886
887 /* If the very first block is the one with the fall-through exit
888 edge, we have to split that block. */
889 if (c == bb)
890 {
891 bb = split_block (bb, NULL)->dest;
892 bb->aux = c->aux;
893 c->aux = bb;
894 bb->il.rtl->footer = c->il.rtl->footer;
895 c->il.rtl->footer = NULL;
896 }
897
898 while (c->aux != bb)
899 c = c->aux;
900
901 c->aux = bb->aux;
902 while (c->aux)
903 c = c->aux;
904
905 c->aux = bb;
906 bb->aux = NULL;
907 }
908 }
909
910 /* Return true in case it is possible to duplicate the basic block BB. */
911
912 /* We do not want to declare the function in a header file, since it should
913 only be used through the cfghooks interface, and we do not want to move
914 it to cfgrtl.c since it would require also moving quite a lot of related
915 code. */
916 extern bool cfg_layout_can_duplicate_bb_p (basic_block);
917
918 bool
cfg_layout_can_duplicate_bb_p(basic_block bb)919 cfg_layout_can_duplicate_bb_p (basic_block bb)
920 {
921 /* Do not attempt to duplicate tablejumps, as we need to unshare
922 the dispatch table. This is difficult to do, as the instructions
923 computing jump destination may be hoisted outside the basic block. */
924 if (tablejump_p (BB_END (bb), NULL, NULL))
925 return false;
926
927 /* Do not duplicate blocks containing insns that can't be copied. */
928 if (targetm.cannot_copy_insn_p)
929 {
930 rtx insn = BB_HEAD (bb);
931 while (1)
932 {
933 if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
934 return false;
935 if (insn == BB_END (bb))
936 break;
937 insn = NEXT_INSN (insn);
938 }
939 }
940
941 return true;
942 }
943
944 rtx
duplicate_insn_chain(rtx from,rtx to)945 duplicate_insn_chain (rtx from, rtx to)
946 {
947 rtx insn, last;
948
949 /* Avoid updating of boundaries of previous basic block. The
950 note will get removed from insn stream in fixup. */
951 last = emit_note (NOTE_INSN_DELETED);
952
953 /* Create copy at the end of INSN chain. The chain will
954 be reordered later. */
955 for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
956 {
957 switch (GET_CODE (insn))
958 {
959 case INSN:
960 case CALL_INSN:
961 case JUMP_INSN:
962 /* Avoid copying of dispatch tables. We never duplicate
963 tablejumps, so this can hit only in case the table got
964 moved far from original jump. */
965 if (GET_CODE (PATTERN (insn)) == ADDR_VEC
966 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
967 break;
968 emit_copy_of_insn_after (insn, get_last_insn ());
969 break;
970
971 case CODE_LABEL:
972 break;
973
974 case BARRIER:
975 emit_barrier ();
976 break;
977
978 case NOTE:
979 switch (NOTE_LINE_NUMBER (insn))
980 {
981 /* In case prologue is empty and function contain label
982 in first BB, we may want to copy the block. */
983 case NOTE_INSN_PROLOGUE_END:
984
985 case NOTE_INSN_DELETED:
986 case NOTE_INSN_DELETED_LABEL:
987 /* No problem to strip these. */
988 case NOTE_INSN_EPILOGUE_BEG:
989 case NOTE_INSN_FUNCTION_END:
990 /* Debug code expect these notes to exist just once.
991 Keep them in the master copy.
992 ??? It probably makes more sense to duplicate them for each
993 epilogue copy. */
994 case NOTE_INSN_FUNCTION_BEG:
995 /* There is always just single entry to function. */
996 case NOTE_INSN_BASIC_BLOCK:
997 break;
998
999 case NOTE_INSN_REPEATED_LINE_NUMBER:
1000 case NOTE_INSN_SWITCH_TEXT_SECTIONS:
1001 emit_note_copy (insn);
1002 break;
1003
1004 default:
1005 /* All other notes should have already been eliminated.
1006 */
1007 gcc_assert (NOTE_LINE_NUMBER (insn) >= 0);
1008
1009 /* It is possible that no_line_number is set and the note
1010 won't be emitted. */
1011 emit_note_copy (insn);
1012 }
1013 break;
1014 default:
1015 gcc_unreachable ();
1016 }
1017 }
1018 insn = NEXT_INSN (last);
1019 delete_insn (last);
1020 return insn;
1021 }
1022 /* Create a duplicate of the basic block BB. */
1023
1024 /* We do not want to declare the function in a header file, since it should
1025 only be used through the cfghooks interface, and we do not want to move
1026 it to cfgrtl.c since it would require also moving quite a lot of related
1027 code. */
1028 extern basic_block cfg_layout_duplicate_bb (basic_block);
1029
1030 basic_block
cfg_layout_duplicate_bb(basic_block bb)1031 cfg_layout_duplicate_bb (basic_block bb)
1032 {
1033 rtx insn;
1034 basic_block new_bb;
1035
1036 insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
1037 new_bb = create_basic_block (insn,
1038 insn ? get_last_insn () : NULL,
1039 EXIT_BLOCK_PTR->prev_bb);
1040
1041 BB_COPY_PARTITION (new_bb, bb);
1042 if (bb->il.rtl->header)
1043 {
1044 insn = bb->il.rtl->header;
1045 while (NEXT_INSN (insn))
1046 insn = NEXT_INSN (insn);
1047 insn = duplicate_insn_chain (bb->il.rtl->header, insn);
1048 if (insn)
1049 new_bb->il.rtl->header = unlink_insn_chain (insn, get_last_insn ());
1050 }
1051
1052 if (bb->il.rtl->footer)
1053 {
1054 insn = bb->il.rtl->footer;
1055 while (NEXT_INSN (insn))
1056 insn = NEXT_INSN (insn);
1057 insn = duplicate_insn_chain (bb->il.rtl->footer, insn);
1058 if (insn)
1059 new_bb->il.rtl->footer = unlink_insn_chain (insn, get_last_insn ());
1060 }
1061
1062 if (bb->il.rtl->global_live_at_start)
1063 {
1064 new_bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack);
1065 new_bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack);
1066 COPY_REG_SET (new_bb->il.rtl->global_live_at_start,
1067 bb->il.rtl->global_live_at_start);
1068 COPY_REG_SET (new_bb->il.rtl->global_live_at_end,
1069 bb->il.rtl->global_live_at_end);
1070 }
1071
1072 return new_bb;
1073 }
1074
1075 /* Main entry point to this module - initialize the datastructures for
1076 CFG layout changes. It keeps LOOPS up-to-date if not null.
1077
1078 FLAGS is a set of additional flags to pass to cleanup_cfg(). It should
1079 include CLEANUP_UPDATE_LIFE if liveness information must be kept up
1080 to date. */
1081
1082 void
cfg_layout_initialize(unsigned int flags)1083 cfg_layout_initialize (unsigned int flags)
1084 {
1085 initialize_original_copy_tables ();
1086
1087 cfg_layout_rtl_register_cfg_hooks ();
1088
1089 record_effective_endpoints ();
1090
1091 cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
1092 }
1093
1094 /* Splits superblocks. */
1095 void
break_superblocks(void)1096 break_superblocks (void)
1097 {
1098 sbitmap superblocks;
1099 bool need = false;
1100 basic_block bb;
1101
1102 superblocks = sbitmap_alloc (last_basic_block);
1103 sbitmap_zero (superblocks);
1104
1105 FOR_EACH_BB (bb)
1106 if (bb->flags & BB_SUPERBLOCK)
1107 {
1108 bb->flags &= ~BB_SUPERBLOCK;
1109 SET_BIT (superblocks, bb->index);
1110 need = true;
1111 }
1112
1113 if (need)
1114 {
1115 rebuild_jump_labels (get_insns ());
1116 find_many_sub_basic_blocks (superblocks);
1117 }
1118
1119 free (superblocks);
1120 }
1121
1122 /* Finalize the changes: reorder insn list according to the sequence specified
1123 by aux pointers, enter compensation code, rebuild scope forest. */
1124
1125 void
cfg_layout_finalize(void)1126 cfg_layout_finalize (void)
1127 {
1128 basic_block bb;
1129
1130 #ifdef ENABLE_CHECKING
1131 verify_flow_info ();
1132 #endif
1133 rtl_register_cfg_hooks ();
1134 if (reload_completed
1135 #ifdef HAVE_epilogue
1136 && !HAVE_epilogue
1137 #endif
1138 )
1139 fixup_fallthru_exit_predecessor ();
1140 fixup_reorder_chain ();
1141
1142 #ifdef ENABLE_CHECKING
1143 verify_insn_chain ();
1144 #endif
1145 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1146 {
1147 bb->il.rtl->header = bb->il.rtl->footer = NULL;
1148 bb->aux = NULL;
1149 bb->il.rtl->visited = 0;
1150 }
1151
1152 break_superblocks ();
1153
1154 #ifdef ENABLE_CHECKING
1155 verify_flow_info ();
1156 #endif
1157
1158 free_original_copy_tables ();
1159 }
1160
1161 /* Checks whether all N blocks in BBS array can be copied. */
1162 bool
can_copy_bbs_p(basic_block * bbs,unsigned n)1163 can_copy_bbs_p (basic_block *bbs, unsigned n)
1164 {
1165 unsigned i;
1166 edge e;
1167 int ret = true;
1168
1169 for (i = 0; i < n; i++)
1170 bbs[i]->flags |= BB_DUPLICATED;
1171
1172 for (i = 0; i < n; i++)
1173 {
1174 /* In case we should redirect abnormal edge during duplication, fail. */
1175 edge_iterator ei;
1176 FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1177 if ((e->flags & EDGE_ABNORMAL)
1178 && (e->dest->flags & BB_DUPLICATED))
1179 {
1180 ret = false;
1181 goto end;
1182 }
1183
1184 if (!can_duplicate_block_p (bbs[i]))
1185 {
1186 ret = false;
1187 break;
1188 }
1189 }
1190
1191 end:
1192 for (i = 0; i < n; i++)
1193 bbs[i]->flags &= ~BB_DUPLICATED;
1194
1195 return ret;
1196 }
1197
1198 /* Duplicates N basic blocks stored in array BBS. Newly created basic blocks
1199 are placed into array NEW_BBS in the same order. Edges from basic blocks
1200 in BBS are also duplicated and copies of those of them
1201 that lead into BBS are redirected to appropriate newly created block. The
1202 function assigns bbs into loops (copy of basic block bb is assigned to
1203 bb->loop_father->copy loop, so this must be set up correctly in advance)
1204 and updates dominators locally (LOOPS structure that contains the information
1205 about dominators is passed to enable this).
1206
1207 BASE is the superloop to that basic block belongs; if its header or latch
1208 is copied, we do not set the new blocks as header or latch.
1209
1210 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1211 also in the same order.
1212
1213 Newly created basic blocks are put after the basic block AFTER in the
1214 instruction stream, and the order of the blocks in BBS array is preserved. */
1215
1216 void
copy_bbs(basic_block * bbs,unsigned n,basic_block * new_bbs,edge * edges,unsigned num_edges,edge * new_edges,struct loop * base,basic_block after)1217 copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
1218 edge *edges, unsigned num_edges, edge *new_edges,
1219 struct loop *base, basic_block after)
1220 {
1221 unsigned i, j;
1222 basic_block bb, new_bb, dom_bb;
1223 edge e;
1224
1225 /* Duplicate bbs, update dominators, assign bbs to loops. */
1226 for (i = 0; i < n; i++)
1227 {
1228 /* Duplicate. */
1229 bb = bbs[i];
1230 new_bb = new_bbs[i] = duplicate_block (bb, NULL, after);
1231 after = new_bb;
1232 bb->flags |= BB_DUPLICATED;
1233 /* Add to loop. */
1234 add_bb_to_loop (new_bb, bb->loop_father->copy);
1235 /* Possibly set header. */
1236 if (bb->loop_father->header == bb && bb->loop_father != base)
1237 new_bb->loop_father->header = new_bb;
1238 /* Or latch. */
1239 if (bb->loop_father->latch == bb && bb->loop_father != base)
1240 new_bb->loop_father->latch = new_bb;
1241 }
1242
1243 /* Set dominators. */
1244 for (i = 0; i < n; i++)
1245 {
1246 bb = bbs[i];
1247 new_bb = new_bbs[i];
1248
1249 dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1250 if (dom_bb->flags & BB_DUPLICATED)
1251 {
1252 dom_bb = get_bb_copy (dom_bb);
1253 set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
1254 }
1255 }
1256
1257 /* Redirect edges. */
1258 for (j = 0; j < num_edges; j++)
1259 new_edges[j] = NULL;
1260 for (i = 0; i < n; i++)
1261 {
1262 edge_iterator ei;
1263 new_bb = new_bbs[i];
1264 bb = bbs[i];
1265
1266 FOR_EACH_EDGE (e, ei, new_bb->succs)
1267 {
1268 for (j = 0; j < num_edges; j++)
1269 if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest)
1270 new_edges[j] = e;
1271
1272 if (!(e->dest->flags & BB_DUPLICATED))
1273 continue;
1274 redirect_edge_and_branch_force (e, get_bb_copy (e->dest));
1275 }
1276 }
1277
1278 /* Clear information about duplicates. */
1279 for (i = 0; i < n; i++)
1280 bbs[i]->flags &= ~BB_DUPLICATED;
1281 }
1282
1283 #include "gt-cfglayout.h"
1284