2006-08-06 Paolo Carlini <pcarlini@suse.de>
[official-gcc.git] / gcc / sched-ebb.c
blobd7a3db9b61d459defb7091aa4250b50a4d1c2d13
1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
4 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
5 and currently maintained by, Jim Wilson (wilson@cygnus.com)
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 2, or (at your option) any later
12 version.
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 for more details.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING. If not, write to the Free
21 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 02110-1301, USA. */
24 #include "config.h"
25 #include "system.h"
26 #include "coretypes.h"
27 #include "tm.h"
28 #include "toplev.h"
29 #include "rtl.h"
30 #include "tm_p.h"
31 #include "hard-reg-set.h"
32 #include "regs.h"
33 #include "function.h"
34 #include "flags.h"
35 #include "insn-config.h"
36 #include "insn-attr.h"
37 #include "except.h"
38 #include "toplev.h"
39 #include "recog.h"
40 #include "cfglayout.h"
41 #include "params.h"
42 #include "sched-int.h"
43 #include "target.h"
44 #include "output.h"
46 /* The number of insns scheduled so far. */
47 static int sched_n_insns;
49 /* The number of insns to be scheduled in total. */
50 static int n_insns;
52 /* Set of blocks, that already have their dependencies calculated. */
53 static bitmap_head dont_calc_deps;
54 /* Set of basic blocks, that are ebb heads of tails respectively. */
55 static bitmap_head ebb_head, ebb_tail;
57 /* Last basic block in current ebb. */
58 static basic_block last_bb;
60 /* Implementations of the sched_info functions for region scheduling. */
61 static void init_ready_list (void);
62 static void begin_schedule_ready (rtx, rtx);
63 static int schedule_more_p (void);
64 static const char *ebb_print_insn (rtx, int);
65 static int rank (rtx, rtx);
66 static int contributes_to_priority (rtx, rtx);
67 static void compute_jump_reg_dependencies (rtx, regset, regset, regset);
68 static basic_block earliest_block_with_similiar_load (basic_block, rtx);
69 static void add_deps_for_risky_insns (rtx, rtx);
70 static basic_block schedule_ebb (rtx, rtx);
72 static void add_remove_insn (rtx, int);
73 static void add_block1 (basic_block, basic_block);
74 static basic_block advance_target_bb (basic_block, rtx);
75 static void fix_recovery_cfg (int, int, int);
77 #ifdef ENABLE_CHECKING
78 static int ebb_head_or_leaf_p (basic_block, int);
79 #endif
81 /* Return nonzero if there are more insns that should be scheduled. */
83 static int
84 schedule_more_p (void)
86 return sched_n_insns < n_insns;
89 /* Add all insns that are initially ready to the ready list READY. Called
90 once before scheduling a set of insns. */
92 static void
93 init_ready_list (void)
95 int n = 0;
96 rtx prev_head = current_sched_info->prev_head;
97 rtx next_tail = current_sched_info->next_tail;
98 rtx insn;
100 sched_n_insns = 0;
102 #if 0
103 /* Print debugging information. */
104 if (sched_verbose >= 5)
105 debug_dependencies ();
106 #endif
108 /* Initialize ready list with all 'ready' insns in target block.
109 Count number of insns in the target block being scheduled. */
110 for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
112 try_ready (insn);
113 n++;
116 gcc_assert (n == n_insns);
119 /* INSN is being scheduled after LAST. Update counters. */
120 static void
121 begin_schedule_ready (rtx insn, rtx last)
123 sched_n_insns++;
125 if (BLOCK_FOR_INSN (insn) == last_bb
126 /* INSN is a jump in the last block, ... */
127 && control_flow_insn_p (insn)
128 /* that is going to be moved over some instructions. */
129 && last != PREV_INSN (insn))
131 edge e;
132 edge_iterator ei;
133 basic_block bb;
135 /* An obscure special case, where we do have partially dead
136 instruction scheduled after last control flow instruction.
137 In this case we can create new basic block. It is
138 always exactly one basic block last in the sequence. */
140 FOR_EACH_EDGE (e, ei, last_bb->succs)
141 if (e->flags & EDGE_FALLTHRU)
142 break;
144 #ifdef ENABLE_CHECKING
145 gcc_assert (!e || !(e->flags & EDGE_COMPLEX));
147 gcc_assert (BLOCK_FOR_INSN (insn) == last_bb
148 && !RECOVERY_BLOCK (insn)
149 && BB_HEAD (last_bb) != insn
150 && BB_END (last_bb) == insn);
153 rtx x;
155 x = NEXT_INSN (insn);
156 if (e)
157 gcc_assert (NOTE_P (x) || LABEL_P (x));
158 else
159 gcc_assert (BARRIER_P (x));
161 #endif
163 if (e)
165 bb = split_edge (e);
166 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_END (bb)));
168 else
169 bb = create_basic_block (insn, 0, last_bb);
171 /* split_edge () creates BB before E->DEST. Keep in mind, that
172 this operation extends scheduling region till the end of BB.
173 Hence, we need to shift NEXT_TAIL, so haifa-sched.c won't go out
174 of the scheduling region. */
175 current_sched_info->next_tail = NEXT_INSN (BB_END (bb));
176 gcc_assert (current_sched_info->next_tail);
178 add_block (bb, last_bb);
179 gcc_assert (last_bb == bb);
183 /* Return a string that contains the insn uid and optionally anything else
184 necessary to identify this insn in an output. It's valid to use a
185 static buffer for this. The ALIGNED parameter should cause the string
186 to be formatted so that multiple output lines will line up nicely. */
188 static const char *
189 ebb_print_insn (rtx insn, int aligned ATTRIBUTE_UNUSED)
191 static char tmp[80];
193 sprintf (tmp, "%4d", INSN_UID (insn));
194 return tmp;
197 /* Compare priority of two insns. Return a positive number if the second
198 insn is to be preferred for scheduling, and a negative one if the first
199 is to be preferred. Zero if they are equally good. */
201 static int
202 rank (rtx insn1, rtx insn2)
204 basic_block bb1 = BLOCK_FOR_INSN (insn1);
205 basic_block bb2 = BLOCK_FOR_INSN (insn2);
207 if (bb1->count > bb2->count
208 || bb1->frequency > bb2->frequency)
209 return -1;
210 if (bb1->count < bb2->count
211 || bb1->frequency < bb2->frequency)
212 return 1;
213 return 0;
216 /* NEXT is an instruction that depends on INSN (a backward dependence);
217 return nonzero if we should include this dependence in priority
218 calculations. */
220 static int
221 contributes_to_priority (rtx next ATTRIBUTE_UNUSED,
222 rtx insn ATTRIBUTE_UNUSED)
224 return 1;
227 /* INSN is a JUMP_INSN, COND_SET is the set of registers that are
228 conditionally set before INSN. Store the set of registers that
229 must be considered as used by this jump in USED and that of
230 registers that must be considered as set in SET. */
232 static void
233 compute_jump_reg_dependencies (rtx insn, regset cond_set, regset used,
234 regset set)
236 basic_block b = BLOCK_FOR_INSN (insn);
237 edge e;
238 edge_iterator ei;
240 FOR_EACH_EDGE (e, ei, b->succs)
241 if (e->flags & EDGE_FALLTHRU)
242 /* The jump may be a by-product of a branch that has been merged
243 in the main codepath after being conditionalized. Therefore
244 it may guard the fallthrough block from using a value that has
245 conditionally overwritten that of the main codepath. So we
246 consider that it restores the value of the main codepath. */
247 bitmap_and (set, glat_start [e->dest->index], cond_set);
248 else
249 bitmap_ior_into (used, glat_start [e->dest->index]);
252 /* Used in schedule_insns to initialize current_sched_info for scheduling
253 regions (or single basic blocks). */
255 static struct sched_info ebb_sched_info =
257 init_ready_list,
258 NULL,
259 schedule_more_p,
260 NULL,
261 rank,
262 ebb_print_insn,
263 contributes_to_priority,
264 compute_jump_reg_dependencies,
266 NULL, NULL,
267 NULL, NULL,
268 0, 1, 0,
270 add_remove_insn,
271 begin_schedule_ready,
272 add_block1,
273 advance_target_bb,
274 fix_recovery_cfg,
275 #ifdef ENABLE_CHECKING
276 ebb_head_or_leaf_p,
277 #endif
278 /* We need to DETACH_LIVE_INFO to be able to create new basic blocks.
279 See begin_schedule_ready (). */
280 SCHED_EBB | USE_GLAT | DETACH_LIFE_INFO
283 /* Returns the earliest block in EBB currently being processed where a
284 "similar load" 'insn2' is found, and hence LOAD_INSN can move
285 speculatively into the found block. All the following must hold:
287 (1) both loads have 1 base register (PFREE_CANDIDATEs).
288 (2) load_insn and load2 have a def-use dependence upon
289 the same insn 'insn1'.
291 From all these we can conclude that the two loads access memory
292 addresses that differ at most by a constant, and hence if moving
293 load_insn would cause an exception, it would have been caused by
294 load2 anyhow.
296 The function uses list (given by LAST_BLOCK) of already processed
297 blocks in EBB. The list is formed in `add_deps_for_risky_insns'. */
299 static basic_block
300 earliest_block_with_similiar_load (basic_block last_block, rtx load_insn)
302 rtx back_link;
303 basic_block bb, earliest_block = NULL;
305 for (back_link = LOG_LINKS (load_insn);
306 back_link;
307 back_link = XEXP (back_link, 1))
309 rtx insn1 = XEXP (back_link, 0);
311 if (GET_MODE (back_link) == VOIDmode)
313 /* Found a DEF-USE dependence (insn1, load_insn). */
314 rtx fore_link;
316 for (fore_link = INSN_DEPEND (insn1);
317 fore_link;
318 fore_link = XEXP (fore_link, 1))
320 rtx insn2 = XEXP (fore_link, 0);
321 basic_block insn2_block = BLOCK_FOR_INSN (insn2);
323 if (GET_MODE (fore_link) == VOIDmode)
325 if (earliest_block != NULL
326 && earliest_block->index < insn2_block->index)
327 continue;
329 /* Found a DEF-USE dependence (insn1, insn2). */
330 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
331 /* insn2 not guaranteed to be a 1 base reg load. */
332 continue;
334 for (bb = last_block; bb; bb = bb->aux)
335 if (insn2_block == bb)
336 break;
338 if (!bb)
339 /* insn2 is the similar load. */
340 earliest_block = insn2_block;
346 return earliest_block;
349 /* The following function adds dependencies between jumps and risky
350 insns in given ebb. */
352 static void
353 add_deps_for_risky_insns (rtx head, rtx tail)
355 rtx insn, prev;
356 int class;
357 rtx last_jump = NULL_RTX;
358 rtx next_tail = NEXT_INSN (tail);
359 basic_block last_block = NULL, bb;
361 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
362 if (control_flow_insn_p (insn))
364 bb = BLOCK_FOR_INSN (insn);
365 bb->aux = last_block;
366 last_block = bb;
367 last_jump = insn;
369 else if (INSN_P (insn) && last_jump != NULL_RTX)
371 class = haifa_classify_insn (insn);
372 prev = last_jump;
373 switch (class)
375 case PFREE_CANDIDATE:
376 if (flag_schedule_speculative_load)
378 bb = earliest_block_with_similiar_load (last_block, insn);
379 if (bb)
381 bb = bb->aux;
382 if (!bb)
383 break;
384 prev = BB_END (bb);
387 /* Fall through. */
388 case TRAP_RISKY:
389 case IRISKY:
390 case PRISKY_CANDIDATE:
391 /* ??? We could implement better checking PRISKY_CANDIDATEs
392 analogous to sched-rgn.c. */
393 /* We can not change the mode of the backward
394 dependency because REG_DEP_ANTI has the lowest
395 rank. */
396 if (! sched_insns_conditions_mutex_p (insn, prev))
398 if (!(current_sched_info->flags & DO_SPECULATION))
400 enum DEPS_ADJUST_RESULT res;
402 res = add_or_update_back_dep (insn, prev,
403 REG_DEP_ANTI, DEP_ANTI);
405 if (res == DEP_CREATED)
406 add_forw_dep (insn, LOG_LINKS (insn));
407 else
408 gcc_assert (res != DEP_CHANGED);
410 else
411 add_or_update_back_forw_dep (insn, prev, REG_DEP_ANTI,
412 set_dep_weak (DEP_ANTI,
413 BEGIN_CONTROL,
414 MAX_DEP_WEAK));
417 break;
419 default:
420 break;
423 /* Maintain the invariant that bb->aux is clear after use. */
424 while (last_block)
426 bb = last_block->aux;
427 last_block->aux = NULL;
428 last_block = bb;
432 /* Schedule a single extended basic block, defined by the boundaries HEAD
433 and TAIL. */
435 static basic_block
436 schedule_ebb (rtx head, rtx tail)
438 basic_block first_bb, target_bb;
439 struct deps tmp_deps;
441 first_bb = BLOCK_FOR_INSN (head);
442 last_bb = BLOCK_FOR_INSN (tail);
444 if (no_real_insns_p (head, tail))
445 return BLOCK_FOR_INSN (tail);
447 gcc_assert (INSN_P (head) && INSN_P (tail));
449 if (!bitmap_bit_p (&dont_calc_deps, first_bb->index))
451 init_deps_global ();
453 /* Compute LOG_LINKS. */
454 init_deps (&tmp_deps);
455 sched_analyze (&tmp_deps, head, tail);
456 free_deps (&tmp_deps);
458 /* Compute INSN_DEPEND. */
459 compute_forward_dependences (head, tail);
461 add_deps_for_risky_insns (head, tail);
463 if (targetm.sched.dependencies_evaluation_hook)
464 targetm.sched.dependencies_evaluation_hook (head, tail);
466 finish_deps_global ();
468 else
469 /* Only recovery blocks can have their dependencies already calculated,
470 and they always are single block ebbs. */
471 gcc_assert (first_bb == last_bb);
473 /* Set priorities. */
474 current_sched_info->sched_max_insns_priority = 0;
475 n_insns = set_priorities (head, tail);
476 current_sched_info->sched_max_insns_priority++;
478 current_sched_info->prev_head = PREV_INSN (head);
479 current_sched_info->next_tail = NEXT_INSN (tail);
481 if (write_symbols != NO_DEBUG)
483 save_line_notes (first_bb->index, head, tail);
484 rm_line_notes (head, tail);
487 /* rm_other_notes only removes notes which are _inside_ the
488 block---that is, it won't remove notes before the first real insn
489 or after the last real insn of the block. So if the first insn
490 has a REG_SAVE_NOTE which would otherwise be emitted before the
491 insn, it is redundant with the note before the start of the
492 block, and so we have to take it out. */
493 if (INSN_P (head))
495 rtx note;
497 for (note = REG_NOTES (head); note; note = XEXP (note, 1))
498 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
499 remove_note (head, note);
502 /* Remove remaining note insns from the block, save them in
503 note_list. These notes are restored at the end of
504 schedule_block (). */
505 rm_other_notes (head, tail);
507 unlink_bb_notes (first_bb, last_bb);
509 current_sched_info->queue_must_finish_empty = 1;
511 target_bb = first_bb;
512 schedule_block (&target_bb, n_insns);
514 /* We might pack all instructions into fewer blocks,
515 so we may made some of them empty. Can't assert (b == last_bb). */
517 /* Sanity check: verify that all region insns were scheduled. */
518 gcc_assert (sched_n_insns == n_insns);
519 head = current_sched_info->head;
520 tail = current_sched_info->tail;
522 if (write_symbols != NO_DEBUG)
523 restore_line_notes (head, tail);
525 if (EDGE_COUNT (last_bb->preds) == 0)
526 /* LAST_BB is unreachable. */
528 gcc_assert (first_bb != last_bb
529 && EDGE_COUNT (last_bb->succs) == 0);
530 last_bb = last_bb->prev_bb;
531 delete_basic_block (last_bb->next_bb);
534 return last_bb;
537 /* The one entry point in this file. */
539 void
540 schedule_ebbs (void)
542 basic_block bb;
543 int probability_cutoff;
544 rtx tail;
545 sbitmap large_region_blocks, blocks;
546 int any_large_regions;
548 if (profile_info && flag_branch_probabilities)
549 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
550 else
551 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
552 probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
554 /* Taking care of this degenerate case makes the rest of
555 this code simpler. */
556 if (n_basic_blocks == NUM_FIXED_BLOCKS)
557 return;
559 /* We need current_sched_info in init_dependency_caches, which is
560 invoked via sched_init. */
561 current_sched_info = &ebb_sched_info;
563 sched_init ();
565 compute_bb_for_insn ();
567 /* Initialize DONT_CALC_DEPS and ebb-{start, end} markers. */
568 bitmap_initialize (&dont_calc_deps, 0);
569 bitmap_clear (&dont_calc_deps);
570 bitmap_initialize (&ebb_head, 0);
571 bitmap_clear (&ebb_head);
572 bitmap_initialize (&ebb_tail, 0);
573 bitmap_clear (&ebb_tail);
575 /* Schedule every region in the subroutine. */
576 FOR_EACH_BB (bb)
578 rtx head = BB_HEAD (bb);
580 for (;;)
582 edge e;
583 edge_iterator ei;
584 tail = BB_END (bb);
585 if (bb->next_bb == EXIT_BLOCK_PTR
586 || LABEL_P (BB_HEAD (bb->next_bb)))
587 break;
588 FOR_EACH_EDGE (e, ei, bb->succs)
589 if ((e->flags & EDGE_FALLTHRU) != 0)
590 break;
591 if (! e)
592 break;
593 if (e->probability <= probability_cutoff)
594 break;
595 bb = bb->next_bb;
598 /* Blah. We should fix the rest of the code not to get confused by
599 a note or two. */
600 while (head != tail)
602 if (NOTE_P (head))
603 head = NEXT_INSN (head);
604 else if (NOTE_P (tail))
605 tail = PREV_INSN (tail);
606 else if (LABEL_P (head))
607 head = NEXT_INSN (head);
608 else
609 break;
612 bitmap_set_bit (&ebb_head, BLOCK_NUM (head));
613 bb = schedule_ebb (head, tail);
614 bitmap_set_bit (&ebb_tail, bb->index);
616 bitmap_clear (&dont_calc_deps);
618 gcc_assert (current_sched_info->flags & DETACH_LIFE_INFO);
619 /* We can create new basic blocks during scheduling, and
620 attach_life_info () will create regsets for them
621 (along with attaching existing info back). */
622 attach_life_info ();
624 /* Updating register live information. */
625 allocate_reg_life_data ();
627 any_large_regions = 0;
628 large_region_blocks = sbitmap_alloc (last_basic_block);
629 sbitmap_zero (large_region_blocks);
630 FOR_EACH_BB (bb)
631 SET_BIT (large_region_blocks, bb->index);
633 blocks = sbitmap_alloc (last_basic_block);
634 sbitmap_zero (blocks);
636 /* Update life information. For regions consisting of multiple blocks
637 we've possibly done interblock scheduling that affects global liveness.
638 For regions consisting of single blocks we need to do only local
639 liveness. */
640 FOR_EACH_BB (bb)
642 int bbi;
644 bbi = bb->index;
646 if (!bitmap_bit_p (&ebb_head, bbi)
647 || !bitmap_bit_p (&ebb_tail, bbi)
648 /* New blocks (e.g. recovery blocks) should be processed
649 as parts of large regions. */
650 || !glat_start[bbi])
651 any_large_regions = 1;
652 else
654 SET_BIT (blocks, bbi);
655 RESET_BIT (large_region_blocks, bbi);
659 update_life_info (blocks, UPDATE_LIFE_LOCAL, 0);
660 sbitmap_free (blocks);
662 if (any_large_regions)
664 update_life_info (large_region_blocks, UPDATE_LIFE_GLOBAL, 0);
666 #ifdef ENABLE_CHECKING
667 /* !!! We can't check reg_live_info here because of the fact,
668 that destination registers of COND_EXEC's may be dead
669 before scheduling (while they should be alive). Don't know why. */
670 /*check_reg_live (true);*/
671 #endif
673 sbitmap_free (large_region_blocks);
675 bitmap_clear (&ebb_head);
676 bitmap_clear (&ebb_tail);
678 /* Reposition the prologue and epilogue notes in case we moved the
679 prologue/epilogue insns. */
680 if (reload_completed)
681 reposition_prologue_and_epilogue_notes (get_insns ());
683 if (write_symbols != NO_DEBUG)
684 rm_redundant_line_notes ();
686 sched_finish ();
689 /* INSN has been added to/removed from current ebb. */
690 static void
691 add_remove_insn (rtx insn ATTRIBUTE_UNUSED, int remove_p)
693 if (!remove_p)
694 n_insns++;
695 else
696 n_insns--;
699 /* BB was added to ebb after AFTER. */
700 static void
701 add_block1 (basic_block bb, basic_block after)
703 /* Recovery blocks are always bounded by BARRIERS,
704 therefore, they always form single block EBB,
705 therefore, we can use rec->index to identify such EBBs. */
706 if (after == EXIT_BLOCK_PTR)
707 bitmap_set_bit (&dont_calc_deps, bb->index);
708 else if (after == last_bb)
709 last_bb = bb;
712 /* Return next block in ebb chain. For parameter meaning please refer to
713 sched-int.h: struct sched_info: advance_target_bb. */
714 static basic_block
715 advance_target_bb (basic_block bb, rtx insn)
717 if (insn)
719 if (BLOCK_FOR_INSN (insn) != bb
720 && control_flow_insn_p (insn)
721 && !RECOVERY_BLOCK (insn)
722 && !RECOVERY_BLOCK (BB_END (bb)))
724 gcc_assert (!control_flow_insn_p (BB_END (bb))
725 && NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (bb->next_bb)));
726 return bb;
728 else
729 return 0;
731 else if (bb != last_bb)
732 return bb->next_bb;
733 else
734 gcc_unreachable ();
737 /* Fix internal data after interblock movement of jump instruction.
738 For parameter meaning please refer to
739 sched-int.h: struct sched_info: fix_recovery_cfg. */
740 static void
741 fix_recovery_cfg (int bbi ATTRIBUTE_UNUSED, int jump_bbi, int jump_bb_nexti)
743 gcc_assert (last_bb->index != bbi);
745 if (jump_bb_nexti == last_bb->index)
746 last_bb = BASIC_BLOCK (jump_bbi);
749 #ifdef ENABLE_CHECKING
750 /* Return non zero, if BB is first or last (depending of LEAF_P) block in
751 current ebb. For more information please refer to
752 sched-int.h: struct sched_info: region_head_or_leaf_p. */
753 static int
754 ebb_head_or_leaf_p (basic_block bb, int leaf_p)
756 if (!leaf_p)
757 return bitmap_bit_p (&ebb_head, bb->index);
758 else
759 return bitmap_bit_p (&ebb_tail, bb->index);
761 #endif /* ENABLE_CHECKING */