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
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
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
26 #include "coretypes.h"
31 #include "hard-reg-set.h"
35 #include "insn-config.h"
36 #include "insn-attr.h"
40 #include "cfglayout.h"
42 #include "sched-int.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. */
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);
81 /* Return nonzero if there are more insns that should be scheduled. */
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. */
93 init_ready_list (void)
96 rtx prev_head = current_sched_info->prev_head;
97 rtx next_tail = current_sched_info->next_tail;
103 /* Print debugging information. */
104 if (sched_verbose >= 5)
105 debug_dependencies ();
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))
116 gcc_assert (n == n_insns);
119 /* INSN is being scheduled after LAST. Update counters. */
121 begin_schedule_ready (rtx insn, rtx last)
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))
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)
144 #ifdef ENABLE_CHECKING
145 gcc_assert (!e || !(e->flags & EDGE_COMPLEX));
147 gcc_assert (BLOCK_FOR_INSN (insn) == last_bb
148 && !IS_SPECULATION_CHECK_P (insn)
149 && BB_HEAD (last_bb) != insn
150 && BB_END (last_bb) == insn);
155 x = NEXT_INSN (insn);
157 gcc_assert (NOTE_P (x) || LABEL_P (x));
159 gcc_assert (BARRIER_P (x));
166 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_END (bb)));
169 /* Create an empty unreachable block after the INSN. */
170 bb = create_basic_block (NEXT_INSN (insn), NULL_RTX, last_bb);
172 /* split_edge () creates BB before E->DEST. Keep in mind, that
173 this operation extends scheduling region till the end of BB.
174 Hence, we need to shift NEXT_TAIL, so haifa-sched.c won't go out
175 of the scheduling region. */
176 current_sched_info->next_tail = NEXT_INSN (BB_END (bb));
177 gcc_assert (current_sched_info->next_tail);
179 add_block (bb, last_bb);
180 gcc_assert (last_bb == bb);
184 /* Return a string that contains the insn uid and optionally anything else
185 necessary to identify this insn in an output. It's valid to use a
186 static buffer for this. The ALIGNED parameter should cause the string
187 to be formatted so that multiple output lines will line up nicely. */
190 ebb_print_insn (rtx insn, int aligned ATTRIBUTE_UNUSED)
194 sprintf (tmp, "%4d", INSN_UID (insn));
198 /* Compare priority of two insns. Return a positive number if the second
199 insn is to be preferred for scheduling, and a negative one if the first
200 is to be preferred. Zero if they are equally good. */
203 rank (rtx insn1, rtx insn2)
205 basic_block bb1 = BLOCK_FOR_INSN (insn1);
206 basic_block bb2 = BLOCK_FOR_INSN (insn2);
208 if (bb1->count > bb2->count
209 || bb1->frequency > bb2->frequency)
211 if (bb1->count < bb2->count
212 || bb1->frequency < bb2->frequency)
217 /* NEXT is an instruction that depends on INSN (a backward dependence);
218 return nonzero if we should include this dependence in priority
222 contributes_to_priority (rtx next ATTRIBUTE_UNUSED,
223 rtx insn ATTRIBUTE_UNUSED)
228 /* INSN is a JUMP_INSN, COND_SET is the set of registers that are
229 conditionally set before INSN. Store the set of registers that
230 must be considered as used by this jump in USED and that of
231 registers that must be considered as set in SET. */
234 compute_jump_reg_dependencies (rtx insn, regset cond_set, regset used,
237 basic_block b = BLOCK_FOR_INSN (insn);
241 FOR_EACH_EDGE (e, ei, b->succs)
242 if (e->flags & EDGE_FALLTHRU)
243 /* The jump may be a by-product of a branch that has been merged
244 in the main codepath after being conditionalized. Therefore
245 it may guard the fallthrough block from using a value that has
246 conditionally overwritten that of the main codepath. So we
247 consider that it restores the value of the main codepath. */
248 bitmap_and (set, glat_start [e->dest->index], cond_set);
250 bitmap_ior_into (used, glat_start [e->dest->index]);
253 /* Used in schedule_insns to initialize current_sched_info for scheduling
254 regions (or single basic blocks). */
256 static struct sched_info ebb_sched_info =
264 contributes_to_priority,
265 compute_jump_reg_dependencies,
272 begin_schedule_ready,
276 #ifdef ENABLE_CHECKING
279 /* We need to DETACH_LIVE_INFO to be able to create new basic blocks.
280 See begin_schedule_ready (). */
281 SCHED_EBB | USE_GLAT | DETACH_LIFE_INFO
284 /* Returns the earliest block in EBB currently being processed where a
285 "similar load" 'insn2' is found, and hence LOAD_INSN can move
286 speculatively into the found block. All the following must hold:
288 (1) both loads have 1 base register (PFREE_CANDIDATEs).
289 (2) load_insn and load2 have a def-use dependence upon
290 the same insn 'insn1'.
292 From all these we can conclude that the two loads access memory
293 addresses that differ at most by a constant, and hence if moving
294 load_insn would cause an exception, it would have been caused by
297 The function uses list (given by LAST_BLOCK) of already processed
298 blocks in EBB. The list is formed in `add_deps_for_risky_insns'. */
301 earliest_block_with_similiar_load (basic_block last_block, rtx load_insn)
304 basic_block bb, earliest_block = NULL;
306 for (back_link = LOG_LINKS (load_insn);
308 back_link = XEXP (back_link, 1))
310 rtx insn1 = XEXP (back_link, 0);
312 if (GET_MODE (back_link) == VOIDmode)
314 /* Found a DEF-USE dependence (insn1, load_insn). */
317 for (fore_link = INSN_DEPEND (insn1);
319 fore_link = XEXP (fore_link, 1))
321 rtx insn2 = XEXP (fore_link, 0);
322 basic_block insn2_block = BLOCK_FOR_INSN (insn2);
324 if (GET_MODE (fore_link) == VOIDmode)
326 if (earliest_block != NULL
327 && earliest_block->index < insn2_block->index)
330 /* Found a DEF-USE dependence (insn1, insn2). */
331 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
332 /* insn2 not guaranteed to be a 1 base reg load. */
335 for (bb = last_block; bb; bb = bb->aux)
336 if (insn2_block == bb)
340 /* insn2 is the similar load. */
341 earliest_block = insn2_block;
347 return earliest_block;
350 /* The following function adds dependencies between jumps and risky
351 insns in given ebb. */
354 add_deps_for_risky_insns (rtx head, rtx tail)
358 rtx last_jump = NULL_RTX;
359 rtx next_tail = NEXT_INSN (tail);
360 basic_block last_block = NULL, bb;
362 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
363 if (control_flow_insn_p (insn))
365 bb = BLOCK_FOR_INSN (insn);
366 bb->aux = last_block;
370 else if (INSN_P (insn) && last_jump != NULL_RTX)
372 class = haifa_classify_insn (insn);
376 case PFREE_CANDIDATE:
377 if (flag_schedule_speculative_load)
379 bb = earliest_block_with_similiar_load (last_block, insn);
391 case PRISKY_CANDIDATE:
392 /* ??? We could implement better checking PRISKY_CANDIDATEs
393 analogous to sched-rgn.c. */
394 /* We can not change the mode of the backward
395 dependency because REG_DEP_ANTI has the lowest
397 if (! sched_insns_conditions_mutex_p (insn, prev))
399 if (!(current_sched_info->flags & DO_SPECULATION))
401 enum DEPS_ADJUST_RESULT res;
403 res = add_or_update_back_dep (insn, prev,
404 REG_DEP_ANTI, DEP_ANTI);
406 if (res == DEP_CREATED)
407 add_forw_dep (insn, LOG_LINKS (insn));
409 gcc_assert (res != DEP_CHANGED);
412 add_or_update_back_forw_dep (insn, prev, REG_DEP_ANTI,
413 set_dep_weak (DEP_ANTI,
424 /* Maintain the invariant that bb->aux is clear after use. */
427 bb = last_block->aux;
428 last_block->aux = NULL;
433 /* Schedule a single extended basic block, defined by the boundaries HEAD
437 schedule_ebb (rtx head, rtx tail)
439 basic_block first_bb, target_bb;
440 struct deps tmp_deps;
442 first_bb = BLOCK_FOR_INSN (head);
443 last_bb = BLOCK_FOR_INSN (tail);
445 if (no_real_insns_p (head, tail))
446 return BLOCK_FOR_INSN (tail);
448 gcc_assert (INSN_P (head) && INSN_P (tail));
450 if (!bitmap_bit_p (&dont_calc_deps, first_bb->index))
454 /* Compute LOG_LINKS. */
455 init_deps (&tmp_deps);
456 sched_analyze (&tmp_deps, head, tail);
457 free_deps (&tmp_deps);
459 /* Compute INSN_DEPEND. */
460 compute_forward_dependences (head, tail);
462 add_deps_for_risky_insns (head, tail);
464 if (targetm.sched.dependencies_evaluation_hook)
465 targetm.sched.dependencies_evaluation_hook (head, tail);
467 finish_deps_global ();
470 /* Only recovery blocks can have their dependencies already calculated,
471 and they always are single block ebbs. */
472 gcc_assert (first_bb == last_bb);
474 /* Set priorities. */
475 current_sched_info->sched_max_insns_priority = 0;
476 n_insns = set_priorities (head, tail);
477 current_sched_info->sched_max_insns_priority++;
479 current_sched_info->prev_head = PREV_INSN (head);
480 current_sched_info->next_tail = NEXT_INSN (tail);
482 if (write_symbols != NO_DEBUG)
484 save_line_notes (first_bb->index, 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. */
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);
537 /* The one entry point in this file. */
543 int probability_cutoff;
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);
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)
559 /* We need current_sched_info in init_dependency_caches, which is
560 invoked via sched_init. */
561 current_sched_info = &ebb_sched_info;
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. */
578 rtx head = BB_HEAD (bb);
585 if (bb->next_bb == EXIT_BLOCK_PTR
586 || LABEL_P (BB_HEAD (bb->next_bb)))
588 FOR_EACH_EDGE (e, ei, bb->succs)
589 if ((e->flags & EDGE_FALLTHRU) != 0)
593 if (e->probability <= probability_cutoff)
598 /* Blah. We should fix the rest of the code not to get confused by
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);
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). */
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);
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
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. */
651 any_large_regions = 1;
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);*/
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 ());
686 /* INSN has been added to/removed from current ebb. */
688 add_remove_insn (rtx insn ATTRIBUTE_UNUSED, int remove_p)
696 /* BB was added to ebb after AFTER. */
698 add_block1 (basic_block bb, basic_block after)
700 /* Recovery blocks are always bounded by BARRIERS,
701 therefore, they always form single block EBB,
702 therefore, we can use rec->index to identify such EBBs. */
703 if (after == EXIT_BLOCK_PTR)
704 bitmap_set_bit (&dont_calc_deps, bb->index);
705 else if (after == last_bb)
709 /* Return next block in ebb chain. For parameter meaning please refer to
710 sched-int.h: struct sched_info: advance_target_bb. */
712 advance_target_bb (basic_block bb, rtx insn)
716 if (BLOCK_FOR_INSN (insn) != bb
717 && control_flow_insn_p (insn)
718 /* We handle interblock movement of the speculation check
719 or over a speculation check in
720 haifa-sched.c: move_block_after_check (). */
721 && !IS_SPECULATION_BRANCHY_CHECK_P (insn)
722 && !IS_SPECULATION_BRANCHY_CHECK_P (BB_END (bb)))
724 /* Assert that we don't move jumps across blocks. */
725 gcc_assert (!control_flow_insn_p (BB_END (bb))
726 && NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (bb->next_bb)));
733 /* Return next non empty block. */
737 gcc_assert (bb != last_bb);
741 while (bb_note (bb) == BB_END (bb));
747 /* Fix internal data after interblock movement of jump instruction.
748 For parameter meaning please refer to
749 sched-int.h: struct sched_info: fix_recovery_cfg. */
751 fix_recovery_cfg (int bbi ATTRIBUTE_UNUSED, int jump_bbi, int jump_bb_nexti)
753 gcc_assert (last_bb->index != bbi);
755 if (jump_bb_nexti == last_bb->index)
756 last_bb = BASIC_BLOCK (jump_bbi);
759 #ifdef ENABLE_CHECKING
760 /* Return non zero, if BB is first or last (depending of LEAF_P) block in
761 current ebb. For more information please refer to
762 sched-int.h: struct sched_info: region_head_or_leaf_p. */
764 ebb_head_or_leaf_p (basic_block bb, int leaf_p)
767 return bitmap_bit_p (&ebb_head, bb->index);
769 return bitmap_bit_p (&ebb_tail, bb->index);
771 #endif /* ENABLE_CHECKING */