bb-reorder.c (REORDER_MOVED_BLOCK_END): Removed.
[gcc.git] / gcc / bb-reorder.c
1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000 Free Software Foundation, Inc.
3
4 This file is part of GNU CC.
5
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
9 any later version.
10
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
20
21 /* References:
22
23 "Profile Guided Code Positioning"
24 Pettis and Hanson; PLDI '90.
25 */
26
27 #include "config.h"
28 #include "system.h"
29 #include "tree.h"
30 #include "rtl.h"
31 #include "tm_p.h"
32 #include "basic-block.h"
33 #include "insn-config.h"
34 #include "regs.h"
35 #include "hard-reg-set.h"
36 #include "flags.h"
37 #include "output.h"
38 #include "function.h"
39 #include "except.h"
40 #include "toplev.h"
41 #include "recog.h"
42 #include "insn-flags.h"
43 #include "expr.h"
44 #include "obstack.h"
45
46
47 /* The contents of the current function definition are allocated
48 in this obstack, and all are freed at the end of the function.
49 For top-level functions, this is temporary_obstack.
50 Separate obstacks are made for nested functions. */
51
52 extern struct obstack *function_obstack;
53
54
55 typedef struct reorder_block_def {
56 int flags;
57 int index;
58 basic_block add_jump;
59 edge succ;
60 rtx end;
61 int block_begin;
62 int block_end;
63 rtx eff_head;
64 rtx eff_end;
65 } *reorder_block_def;
66
67 static struct reorder_block_def rbd_init
68 = {
69 0, /* flags */
70 0, /* index */
71 NULL, /* add_jump */
72 NULL, /* succ */
73 NULL_RTX, /* end */
74 0, /* block_begin */
75 0, /* block_end */
76 NULL_RTX, /* eff_head */
77 NULL_RTX /* eff_end */
78 };
79
80
81 #define REORDER_BLOCK_HEAD 0x1
82 #define REORDER_BLOCK_VISITED 0x2
83
84 #define REORDER_BLOCK_FLAGS(bb) \
85 ((reorder_block_def) (bb)->aux)->flags
86
87 #define REORDER_BLOCK_INDEX(bb) \
88 ((reorder_block_def) (bb)->aux)->index
89
90 #define REORDER_BLOCK_ADD_JUMP(bb) \
91 ((reorder_block_def) (bb)->aux)->add_jump
92
93 #define REORDER_BLOCK_SUCC(bb) \
94 ((reorder_block_def) (bb)->aux)->succ
95
96 #define REORDER_BLOCK_OLD_END(bb) \
97 ((reorder_block_def) (bb)->aux)->end
98
99 #define REORDER_BLOCK_BEGIN(bb) \
100 ((reorder_block_def) (bb)->aux)->block_begin
101
102 #define REORDER_BLOCK_END(bb) \
103 ((reorder_block_def) (bb)->aux)->block_end
104
105 #define REORDER_BLOCK_EFF_HEAD(bb) \
106 ((reorder_block_def) (bb)->aux)->eff_head
107
108 #define REORDER_BLOCK_EFF_END(bb) \
109 ((reorder_block_def) (bb)->aux)->eff_end
110
111
112 static int reorder_index;
113 static basic_block reorder_last_visited;
114
115 enum reorder_skip_type {REORDER_SKIP_BEFORE, REORDER_SKIP_AFTER,
116 REORDER_SKIP_BLOCK_END};
117
118
119 /* Local function prototypes. */
120 static rtx skip_insns_between_block PARAMS ((basic_block,
121 enum reorder_skip_type));
122 static basic_block get_common_dest PARAMS ((basic_block, basic_block));
123 static basic_block chain_reorder_blocks PARAMS ((edge, basic_block));
124 static void make_reorder_chain PARAMS ((basic_block));
125 static void fixup_reorder_chain PARAMS ((void));
126 static void verify_insn_chain PARAMS ((void));
127
128
129 /* Skip over insns BEFORE or AFTER BB which are typically associated with
130 basic block BB. */
131
132 static rtx
133 skip_insns_between_block (bb, skip_type)
134 basic_block bb;
135 enum reorder_skip_type skip_type;
136 {
137 rtx insn, last_insn;
138
139 if (skip_type == REORDER_SKIP_BEFORE)
140 {
141 if (bb == ENTRY_BLOCK_PTR)
142 return 0;
143
144 last_insn = bb->head;
145 for (insn = PREV_INSN (bb->head);
146 insn && insn != BASIC_BLOCK (bb->index - 1)->end;
147 last_insn = insn, insn = PREV_INSN (insn))
148 {
149 if (NEXT_INSN (insn) != last_insn)
150 break;
151
152 if (GET_CODE (insn) == NOTE
153 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
154 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK
155 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BLOCK_END)
156 continue;
157
158 break;
159 }
160 }
161 else
162 {
163 last_insn = bb->end;
164
165 if (bb == EXIT_BLOCK_PTR)
166 return 0;
167
168 for (insn = NEXT_INSN (bb->end);
169 insn;
170 last_insn = insn, insn = NEXT_INSN (insn))
171 {
172 if (bb->index + 1 != n_basic_blocks
173 && insn == BASIC_BLOCK (bb->index + 1)->head)
174 break;
175
176 if (GET_CODE (insn) == BARRIER
177 || GET_CODE (insn) == JUMP_INSN
178 || (GET_CODE (insn) == NOTE
179 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
180 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END)))
181 continue;
182
183 if (GET_CODE (insn) == CODE_LABEL
184 && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
185 && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
186 || GET_CODE (PATTERN
187 (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
188 {
189 insn = NEXT_INSN (insn);
190 continue;
191 }
192
193 /* Skip to next non-deleted insn. */
194 if (GET_CODE (insn) == NOTE
195 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED
196 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED_LABEL))
197 continue;
198
199 break;
200 }
201
202 if (skip_type == REORDER_SKIP_BLOCK_END)
203 {
204 int found_block_end = 0;
205
206 for (; insn; last_insn = insn, insn = NEXT_INSN (insn))
207 {
208 if (bb->index + 1 != n_basic_blocks
209 && insn == BASIC_BLOCK (bb->index + 1)->head)
210 break;
211
212 if (GET_CODE (insn) == NOTE
213 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END)
214 {
215 found_block_end = 1;
216 continue;
217 }
218
219 if (GET_CODE (insn) == NOTE
220 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
221 continue;
222
223 if (GET_CODE (insn) == NOTE
224 && NOTE_LINE_NUMBER (insn) >= 0
225 && NEXT_INSN (insn)
226 && GET_CODE (NEXT_INSN (insn)) == NOTE
227 && (NOTE_LINE_NUMBER (NEXT_INSN (insn))
228 == NOTE_INSN_BLOCK_END))
229 continue;
230 break;
231 }
232
233 if (! found_block_end)
234 last_insn = 0;
235 }
236 }
237
238 return last_insn;
239 }
240
241
242 /* Return common destination for blocks BB0 and BB1. */
243
244 static basic_block
245 get_common_dest (bb0, bb1)
246 basic_block bb0, bb1;
247 {
248 edge e0, e1;
249
250 for (e0 = bb0->succ; e0; e0 = e0->succ_next)
251 {
252 for (e1 = bb1->succ; e1; e1 = e1->succ_next)
253 {
254 if (e0->dest == e1->dest)
255 {
256 return e0->dest;
257 }
258 }
259 }
260 return 0;
261 }
262
263
264 /* Move the destination block for edge E after chain end block CEB
265 Adding jumps and labels is deferred until fixup_reorder_chain. */
266
267 static basic_block
268 chain_reorder_blocks (e, ceb)
269 edge e;
270 basic_block ceb;
271 {
272 basic_block sb = e->src;
273 basic_block db = e->dest;
274 rtx cebe_insn, cebbe_insn, dbh_insn, dbe_insn;
275 edge ee, last_edge;
276
277 enum cond_types {NO_COND, PREDICT_THEN_WITH_ELSE, PREDICT_ELSE,
278 PREDICT_THEN_NO_ELSE, PREDICT_NOT_THEN_NO_ELSE};
279 enum cond_types cond_type;
280 enum cond_block_types {NO_COND_BLOCK, THEN_BLOCK, ELSE_BLOCK,
281 NO_ELSE_BLOCK};
282 enum cond_block_types cond_block_type;
283
284 if (rtl_dump_file)
285 fprintf (rtl_dump_file,
286 "Edge from basic block %d to basic block %d last visited %d\n",
287 sb->index, db->index, ceb->index);
288
289 dbh_insn = REORDER_BLOCK_EFF_HEAD (db);
290 cebe_insn = REORDER_BLOCK_EFF_END (ceb);
291 cebbe_insn = skip_insns_between_block (ceb, REORDER_SKIP_BLOCK_END);
292
293 {
294 int block_begins = 0;
295 rtx insn;
296
297 for (insn = dbh_insn; insn && insn != db->end; insn = NEXT_INSN (insn))
298 {
299 if (GET_CODE (insn) == NOTE
300 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG)
301 {
302 block_begins += 1;
303 break;
304 }
305 }
306 REORDER_BLOCK_BEGIN (sb) = block_begins;
307 }
308
309 if (cebbe_insn)
310 {
311 int block_ends = 0;
312 rtx insn;
313
314 for (insn = cebe_insn; insn; insn = NEXT_INSN (insn))
315 {
316 if (PREV_INSN (insn) == cebbe_insn)
317 break;
318 if (GET_CODE (insn) == NOTE
319 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END)
320 {
321 block_ends += 1;
322 continue;
323 }
324 }
325 REORDER_BLOCK_END (ceb) = block_ends;
326 }
327
328 /* Blocks are in original order. */
329 if (sb->index == ceb->index
330 && ceb->index + 1 == db->index && NEXT_INSN (cebe_insn))
331 return db;
332
333 /* Get the type of block and type of condition. */
334 cond_type = NO_COND;
335 cond_block_type = NO_COND_BLOCK;
336 if (GET_CODE (sb->end) == JUMP_INSN && ! simplejump_p (sb->end)
337 && condjump_p (sb->end))
338 {
339 if (e->flags & EDGE_FALLTHRU)
340 cond_block_type = THEN_BLOCK;
341 else if (get_common_dest (sb->succ->dest, sb))
342 cond_block_type = NO_ELSE_BLOCK;
343 else
344 cond_block_type = ELSE_BLOCK;
345
346 if (sb->succ->succ_next
347 && get_common_dest (sb->succ->dest, sb))
348 {
349 if (cond_block_type == THEN_BLOCK)
350 {
351 if (! (REORDER_BLOCK_FLAGS (sb->succ->succ_next->dest)
352 & REORDER_BLOCK_VISITED))
353 cond_type = PREDICT_THEN_NO_ELSE;
354 else
355 cond_type = PREDICT_NOT_THEN_NO_ELSE;
356 }
357 else if (cond_block_type == NO_ELSE_BLOCK)
358 {
359 if (! (REORDER_BLOCK_FLAGS (sb->succ->dest)
360 & REORDER_BLOCK_VISITED))
361 cond_type = PREDICT_NOT_THEN_NO_ELSE;
362 else
363 cond_type = PREDICT_THEN_NO_ELSE;
364 }
365 }
366 else
367 {
368 if (cond_block_type == THEN_BLOCK)
369 {
370 if (! (REORDER_BLOCK_FLAGS (sb->succ->succ_next->dest)
371 & REORDER_BLOCK_VISITED))
372 cond_type = PREDICT_THEN_WITH_ELSE;
373 else
374 cond_type = PREDICT_ELSE;
375 }
376 else if (cond_block_type == ELSE_BLOCK
377 && sb->succ->dest != EXIT_BLOCK_PTR)
378 {
379 if (! (REORDER_BLOCK_FLAGS (sb->succ->dest)
380 & REORDER_BLOCK_VISITED))
381 cond_type = PREDICT_ELSE;
382 else
383 cond_type = PREDICT_THEN_WITH_ELSE;
384 }
385 }
386 }
387
388 if (rtl_dump_file)
389 {
390 static const char * cond_type_str [] = {"not cond jump", "predict then",
391 "predict else",
392 "predict then w/o else",
393 "predict not then w/o else"};
394 static const char * cond_block_type_str [] = {"not then or else block",
395 "then block",
396 "else block",
397 "then w/o else block"};
398
399 fprintf (rtl_dump_file, " %s (looking at %s)\n",
400 cond_type_str[(int)cond_type],
401 cond_block_type_str[(int)cond_block_type]);
402 }
403
404 /* Reflect that then block will move and we'll jump to it. */
405 if (cond_block_type != THEN_BLOCK
406 && (cond_type == PREDICT_ELSE
407 || cond_type == PREDICT_NOT_THEN_NO_ELSE))
408 {
409 if (rtl_dump_file)
410 fprintf (rtl_dump_file,
411 " then jump from block %d to block %d\n",
412 sb->index, sb->succ->dest->index);
413
414 /* Jump to reordered then block. */
415 REORDER_BLOCK_ADD_JUMP (sb) = sb->succ->dest;
416 }
417
418 /* Reflect that then block will jump back when we have no else. */
419 if (cond_block_type != THEN_BLOCK
420 && cond_type == PREDICT_NOT_THEN_NO_ELSE)
421 {
422 for (ee = sb->succ->dest->succ;
423 ee && ! (ee->flags & EDGE_FALLTHRU);
424 ee = ee->succ_next)
425 continue;
426
427 if (ee && ! (GET_CODE (sb->succ->dest->end) == JUMP_INSN
428 && ! simplejump_p (sb->succ->dest->end)))
429 {
430 REORDER_BLOCK_ADD_JUMP (sb->succ->dest) = ee->dest;
431 }
432 }
433
434 /* Reflect that else block will jump back. */
435 if (cond_block_type == ELSE_BLOCK
436 && (cond_type == PREDICT_THEN_WITH_ELSE || cond_type == PREDICT_ELSE))
437 {
438 last_edge=db->succ;
439
440 if (last_edge
441 && last_edge->dest != EXIT_BLOCK_PTR
442 && GET_CODE (last_edge->dest->head) == CODE_LABEL
443 && ! (GET_CODE (db->end) == JUMP_INSN))
444 {
445 if (rtl_dump_file)
446 fprintf (rtl_dump_file,
447 " else jump from block %d to block %d\n",
448 db->index, last_edge->dest->index);
449
450 REORDER_BLOCK_ADD_JUMP (db) = last_edge->dest;
451 }
452 }
453
454 /* This block's successor has already been reordered. This can happen
455 when we reorder a chain starting at a then or else. */
456 for (last_edge = db->succ;
457 last_edge && ! (last_edge->flags & EDGE_FALLTHRU);
458 last_edge = last_edge->succ_next)
459 continue;
460
461 if (last_edge
462 && last_edge->dest != EXIT_BLOCK_PTR
463 && (REORDER_BLOCK_FLAGS (last_edge->dest)
464 & REORDER_BLOCK_VISITED))
465 {
466 if (rtl_dump_file)
467 fprintf (rtl_dump_file,
468 " end of chain jump from block %d to block %d\n",
469 db->index, last_edge->dest->index);
470
471 REORDER_BLOCK_ADD_JUMP (db) = last_edge->dest;
472 }
473
474 dbh_insn = REORDER_BLOCK_EFF_HEAD (db);
475 cebe_insn = REORDER_BLOCK_EFF_END (ceb);
476 dbe_insn = REORDER_BLOCK_EFF_END (db);
477
478 /* Leave behind any lexical block markers. */
479 if (debug_info_level > DINFO_LEVEL_TERSE
480 && ceb->index + 1 < db->index)
481 {
482 rtx insn, last_insn = get_last_insn ();
483 insn = NEXT_INSN (ceb->end);
484 if (! insn)
485 insn = REORDER_BLOCK_OLD_END (ceb);
486
487 if (NEXT_INSN (cebe_insn) == 0)
488 set_last_insn (cebe_insn);
489 for (; insn && insn != db->head/*dbh_insn*/;
490 insn = NEXT_INSN (insn))
491 {
492 if (GET_CODE (insn) == NOTE
493 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG))
494 {
495 cebe_insn = emit_note_after (NOTE_INSN_BLOCK_BEG, cebe_insn);
496 delete_insn (insn);
497 }
498 if (GET_CODE (insn) == NOTE
499 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END))
500 {
501 cebe_insn = emit_note_after (NOTE_INSN_BLOCK_END, cebe_insn);
502 delete_insn (insn);
503 }
504 }
505 set_last_insn (last_insn);
506 }
507
508 /* Rechain predicted block. */
509 NEXT_INSN (cebe_insn) = dbh_insn;
510 PREV_INSN (dbh_insn) = cebe_insn;
511
512 REORDER_BLOCK_OLD_END (db) = NEXT_INSN (dbe_insn);
513 if (db->index != n_basic_blocks - 1)
514 NEXT_INSN (dbe_insn) = 0;
515
516 return db;
517 }
518
519
520 /* Reorder blocks starting at block BB. */
521
522 static void
523 make_reorder_chain (bb)
524 basic_block bb;
525 {
526 edge e;
527 basic_block visited_edge = NULL;
528 rtx block_end;
529 int probability;
530
531 if (bb == EXIT_BLOCK_PTR)
532 return;
533
534 /* Find the most probable block. */
535 e = bb->succ;
536 block_end = bb->end;
537 if (GET_CODE (block_end) == JUMP_INSN && condjump_p (block_end))
538 {
539 rtx note = find_reg_note (block_end, REG_BR_PROB, 0);
540
541 if (note)
542 probability = INTVAL (XEXP (note, 0));
543 else
544 probability = 0;
545
546 if (probability >= REG_BR_PROB_BASE / 2)
547 e = bb->succ->succ_next;
548 }
549
550 /* Add chosen successor to chain and recurse on it. */
551 if (e && e->dest != EXIT_BLOCK_PTR
552 && e->dest != e->src
553 && (! (REORDER_BLOCK_FLAGS (e->dest) & REORDER_BLOCK_VISITED)
554 || (REORDER_BLOCK_FLAGS (e->dest) == REORDER_BLOCK_HEAD)))
555 {
556 if (! (REORDER_BLOCK_FLAGS (bb) & REORDER_BLOCK_VISITED))
557 {
558 REORDER_BLOCK_FLAGS (bb) |= REORDER_BLOCK_HEAD;
559 REORDER_BLOCK_INDEX (bb) = reorder_index++;
560 REORDER_BLOCK_FLAGS (bb) |= REORDER_BLOCK_VISITED;
561 }
562
563 if (REORDER_BLOCK_FLAGS (e->dest) & REORDER_BLOCK_VISITED)
564 REORDER_BLOCK_FLAGS (e->dest) &= ~REORDER_BLOCK_HEAD;
565
566 REORDER_BLOCK_SUCC (bb) = e;
567
568 visited_edge = e->dest;
569
570 reorder_last_visited = chain_reorder_blocks (e, bb);
571
572 if (e->dest
573 && ! (REORDER_BLOCK_FLAGS (e->dest)
574 & REORDER_BLOCK_VISITED))
575 make_reorder_chain (e->dest);
576 }
577 else
578 {
579 if (! (REORDER_BLOCK_FLAGS (bb) & REORDER_BLOCK_VISITED))
580 {
581 REORDER_BLOCK_INDEX (bb) = reorder_index++;
582 REORDER_BLOCK_FLAGS (bb) |= REORDER_BLOCK_VISITED;
583 }
584 }
585
586 /* Recurse on the successors. */
587 for (e = bb->succ; e; e = e->succ_next)
588 {
589 if (e->dest && e->dest == EXIT_BLOCK_PTR)
590 continue;
591
592 if (e->dest
593 && e->dest != e->src
594 && e->dest != visited_edge
595 && ! (REORDER_BLOCK_FLAGS (e->dest)
596 & REORDER_BLOCK_VISITED))
597 {
598 reorder_last_visited
599 = chain_reorder_blocks (e, reorder_last_visited);
600 make_reorder_chain (e->dest);
601 }
602 }
603 }
604
605
606 /* Fixup jumps and labels after reordering basic blocks. */
607
608 static void
609 fixup_reorder_chain ()
610 {
611 int i, j;
612 rtx insn;
613 int orig_num_blocks = n_basic_blocks;
614
615 /* Set the new last insn. */
616 {
617 int max_val = 0;
618 int max_index = 0;
619 for (j = 0; j < n_basic_blocks; j++)
620 {
621 int val = REORDER_BLOCK_INDEX (BASIC_BLOCK (j));
622 if (val > max_val)
623 {
624 max_val = val;
625 max_index = j;
626 }
627 }
628 insn = REORDER_BLOCK_EFF_END (BASIC_BLOCK (max_index));
629 NEXT_INSN (insn) = NULL_RTX;
630 set_last_insn (insn);
631 }
632
633 /* Add jumps and labels to fixup blocks. */
634 for (i = 0; i < orig_num_blocks; i++)
635 {
636 int need_block = 0;
637 basic_block bbi = BASIC_BLOCK (i);
638 if (REORDER_BLOCK_ADD_JUMP (bbi))
639 {
640 rtx label_insn, jump_insn, barrier_insn;
641
642 if (GET_CODE (REORDER_BLOCK_ADD_JUMP (bbi)->head) == CODE_LABEL)
643 label_insn = REORDER_BLOCK_ADD_JUMP (bbi)->head;
644 else
645 {
646 rtx new_label = gen_label_rtx ();
647 label_insn = emit_label_before (new_label,
648 REORDER_BLOCK_ADD_JUMP (bbi)->head);
649 REORDER_BLOCK_ADD_JUMP (bbi)->head = label_insn;
650 }
651
652 if (GET_CODE (bbi->end) != JUMP_INSN)
653 {
654 jump_insn = emit_jump_insn_after (gen_jump (label_insn),
655 bbi->end);
656 bbi->end = jump_insn;
657 need_block = 0;
658 }
659 else
660 {
661 jump_insn = emit_jump_insn_after (gen_jump (label_insn),
662 REORDER_BLOCK_EFF_END (bbi));
663 need_block = 1;
664 }
665
666 JUMP_LABEL (jump_insn) = label_insn;
667 ++LABEL_NUSES (label_insn);
668 barrier_insn = emit_barrier_after (jump_insn);
669
670 /* Add block for jump. Typically this is when a then is not
671 predicted and we are jumping to the moved then block. */
672 if (need_block)
673 {
674 basic_block nb;
675
676 VARRAY_GROW (basic_block_info, ++n_basic_blocks);
677 create_basic_block (n_basic_blocks - 1, jump_insn,
678 jump_insn, NULL);
679 nb = BASIC_BLOCK (n_basic_blocks - 1);
680 nb->global_live_at_start
681 = OBSTACK_ALLOC_REG_SET (function_obstack);
682 nb->global_live_at_end
683 = OBSTACK_ALLOC_REG_SET (function_obstack);
684
685 COPY_REG_SET (nb->global_live_at_start,
686 bbi->global_live_at_start);
687 COPY_REG_SET (nb->global_live_at_end,
688 bbi->global_live_at_start);
689 BASIC_BLOCK (nb->index)->local_set = 0;
690
691 nb->aux = xcalloc (1, sizeof (struct reorder_block_def));
692 REORDER_BLOCK_INDEX (BASIC_BLOCK (n_basic_blocks - 1))
693 = REORDER_BLOCK_INDEX (bbi) + 1;
694 /* Relink to new block. */
695 nb->succ = bbi->succ;
696 nb->succ->src = nb;
697
698 make_edge (NULL, bbi, nb, 0);
699 bbi->succ->succ_next
700 = bbi->succ->succ_next->succ_next;
701 nb->succ->succ_next = 0;
702 /* Fix reorder block index to reflect new block. */
703 for (j = 0; j < n_basic_blocks - 1; j++)
704 {
705 basic_block bbj = BASIC_BLOCK (j);
706 if (REORDER_BLOCK_INDEX (bbj)
707 >= REORDER_BLOCK_INDEX (bbi) + 1)
708 REORDER_BLOCK_INDEX (bbj)++;
709 }
710 }
711 }
712 }
713 }
714
715
716 /* Perform sanity checks on the insn chain.
717 1. Check that next/prev pointers are consistent in both the forward and
718 reverse direction.
719 2. Count insns in chain, going both directions, and check if equal.
720 3. Check that get_last_insn () returns the actual end of chain. */
721
722 static void
723 verify_insn_chain ()
724 {
725 rtx x,
726 prevx,
727 nextx;
728 int insn_cnt1,
729 insn_cnt2;
730
731 prevx = NULL;
732 insn_cnt1 = 1;
733 for (x = get_insns (); x; x = NEXT_INSN (x))
734 {
735 if (PREV_INSN (x) != prevx)
736 {
737 fprintf (stderr, "Forward traversal: insn chain corrupt.\n");
738 fprintf (stderr, "previous insn:\n");
739 debug_rtx (prevx);
740 fprintf (stderr, "current insn:\n");
741 debug_rtx (x);
742 abort ();
743 }
744 ++insn_cnt1;
745 prevx = x;
746 }
747
748 if (prevx != get_last_insn ())
749 {
750 fprintf (stderr, "last_insn corrupt.\n");
751 abort ();
752 }
753
754 nextx = NULL;
755 insn_cnt2 = 1;
756 for (x = get_last_insn (); x; x = PREV_INSN (x))
757 {
758 if (NEXT_INSN (x) != nextx)
759 {
760 fprintf (stderr, "Reverse traversal: insn chain corrupt.\n");
761 fprintf (stderr, "current insn:\n");
762 debug_rtx (x);
763 fprintf (stderr, "next insn:\n");
764 debug_rtx (nextx);
765 abort ();
766 }
767 ++insn_cnt2;
768 nextx = x;
769 }
770
771 if (insn_cnt1 != insn_cnt2)
772 {
773 fprintf (stderr, "insn_cnt1 (%d) not equal to insn_cnt2 (%d).\n",
774 insn_cnt1, insn_cnt2);
775 abort ();
776 }
777 }
778
779
780 /* Reorder basic blocks. */
781
782 void
783 reorder_basic_blocks ()
784 {
785 int i, j;
786 struct loops loops_info;
787 int num_loops;
788
789 if (profile_arc_flag)
790 return;
791
792 if (n_basic_blocks <= 1)
793 return;
794
795 /* Exception edges are not currently handled. */
796 for (i = 0; i < n_basic_blocks; i++)
797 {
798 edge e;
799
800 for (e = BASIC_BLOCK (i)->succ; e && ! (e->flags & EDGE_EH);
801 e = e->succ_next)
802 continue;
803
804 if (e && (e->flags & EDGE_EH))
805 return;
806 }
807
808 reorder_index = 0;
809
810 /* Find natural loops using the CFG. */
811 num_loops = flow_loops_find (&loops_info);
812
813 /* Dump loop information. */
814 flow_loops_dump (&loops_info, rtl_dump_file, 0);
815
816 /* Estimate using heuristics if no profiling info is available. */
817 if (! flag_branch_probabilities)
818 estimate_probability (&loops_info);
819
820 reorder_last_visited = BASIC_BLOCK (0);
821
822 for (i = 0; i < n_basic_blocks; i++)
823 {
824 basic_block bbi = BASIC_BLOCK (i);
825 bbi->aux = xcalloc (1, sizeof (struct reorder_block_def));
826 *((struct reorder_block_def *)bbi->aux) = rbd_init;
827 REORDER_BLOCK_EFF_END (bbi)
828 = skip_insns_between_block (bbi, REORDER_SKIP_AFTER);
829 if (i == 0)
830 REORDER_BLOCK_EFF_HEAD (bbi) = get_insns ();
831 else
832 {
833 rtx prev_eff_end = REORDER_BLOCK_EFF_END (BASIC_BLOCK (i - 1));
834 REORDER_BLOCK_EFF_HEAD (bbi) = NEXT_INSN (prev_eff_end);
835 }
836 }
837
838 make_reorder_chain (BASIC_BLOCK (0));
839
840 fixup_reorder_chain ();
841
842 #ifdef ENABLE_CHECKING
843 verify_insn_chain ();
844 #endif
845
846 /* Put basic_block_info in new order. */
847 for (i = 0; i < n_basic_blocks - 1; i++)
848 {
849 for (j = i; i != REORDER_BLOCK_INDEX (BASIC_BLOCK (j)); j++)
850 continue;
851
852 if (REORDER_BLOCK_INDEX (BASIC_BLOCK (j)) == i
853 && i != j)
854 {
855 basic_block tempbb;
856 int temprbi;
857 int rbi = REORDER_BLOCK_INDEX (BASIC_BLOCK (j));
858
859 temprbi = BASIC_BLOCK (rbi)->index;
860 BASIC_BLOCK (rbi)->index = BASIC_BLOCK (j)->index;
861 BASIC_BLOCK (j)->index = temprbi;
862 tempbb = BASIC_BLOCK (rbi);
863 BASIC_BLOCK (rbi) = BASIC_BLOCK (j);
864 BASIC_BLOCK (j) = tempbb;
865 }
866 }
867
868 #ifdef ENABLE_CHECKING
869 verify_flow_info ();
870 #endif
871
872 for (i = 0; i < n_basic_blocks; i++)
873 free (BASIC_BLOCK (i)->aux);
874
875 /* Free loop information. */
876 flow_loops_free (&loops_info);
877
878 }
879