1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
4 Free Software Foundation, Inc.
5 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
6 and currently maintained by, Jim Wilson (wilson@cygnus.com)
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 2, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING. If not, write to the Free
22 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
27 #include "coretypes.h"
32 #include "hard-reg-set.h"
36 #include "insn-config.h"
37 #include "insn-attr.h"
41 #include "cfglayout.h"
43 #include "sched-int.h"
48 /* The number of insns scheduled so far. */
49 static int sched_n_insns
;
51 /* The number of insns to be scheduled in total. */
54 /* Set of blocks, that already have their dependencies calculated. */
55 static bitmap_head dont_calc_deps
;
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 /* Return nonzero if there are more insns that should be scheduled. */
80 schedule_more_p (void)
82 return sched_n_insns
< n_insns
;
85 /* Print dependency information about ebb between HEAD and TAIL. */
87 debug_ebb_dependencies (rtx head
, rtx tail
)
90 ";; --------------- forward dependences: ------------ \n");
92 fprintf (sched_dump
, "\n;; --- EBB Dependences --- from bb%d to bb%d \n",
93 BLOCK_NUM (head
), BLOCK_NUM (tail
));
95 debug_dependencies (head
, tail
);
98 /* Add all insns that are initially ready to the ready list READY. Called
99 once before scheduling a set of insns. */
102 init_ready_list (void)
105 rtx prev_head
= current_sched_info
->prev_head
;
106 rtx next_tail
= current_sched_info
->next_tail
;
111 /* Print debugging information. */
112 if (sched_verbose
>= 5)
113 debug_ebb_dependencies (NEXT_INSN (prev_head
), PREV_INSN (next_tail
));
115 /* Initialize ready list with all 'ready' insns in target block.
116 Count number of insns in the target block being scheduled. */
117 for (insn
= NEXT_INSN (prev_head
); insn
!= next_tail
; insn
= NEXT_INSN (insn
))
123 gcc_assert (n
== n_insns
);
126 /* INSN is being scheduled after LAST. Update counters. */
128 begin_schedule_ready (rtx insn
, rtx last
)
132 if (BLOCK_FOR_INSN (insn
) == last_bb
133 /* INSN is a jump in the last block, ... */
134 && control_flow_insn_p (insn
)
135 /* that is going to be moved over some instructions. */
136 && last
!= PREV_INSN (insn
))
142 /* An obscure special case, where we do have partially dead
143 instruction scheduled after last control flow instruction.
144 In this case we can create new basic block. It is
145 always exactly one basic block last in the sequence. */
147 FOR_EACH_EDGE (e
, ei
, last_bb
->succs
)
148 if (e
->flags
& EDGE_FALLTHRU
)
151 #ifdef ENABLE_CHECKING
152 gcc_assert (!e
|| !(e
->flags
& EDGE_COMPLEX
));
154 gcc_assert (BLOCK_FOR_INSN (insn
) == last_bb
155 && !IS_SPECULATION_CHECK_P (insn
)
156 && BB_HEAD (last_bb
) != insn
157 && BB_END (last_bb
) == insn
);
162 x
= NEXT_INSN (insn
);
164 gcc_assert (NOTE_P (x
) || LABEL_P (x
));
166 gcc_assert (BARRIER_P (x
));
173 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_END (bb
)));
176 /* Create an empty unreachable block after the INSN. */
177 bb
= create_basic_block (NEXT_INSN (insn
), NULL_RTX
, last_bb
);
179 /* split_edge () creates BB before E->DEST. Keep in mind, that
180 this operation extends scheduling region till the end of BB.
181 Hence, we need to shift NEXT_TAIL, so haifa-sched.c won't go out
182 of the scheduling region. */
183 current_sched_info
->next_tail
= NEXT_INSN (BB_END (bb
));
184 gcc_assert (current_sched_info
->next_tail
);
186 add_block (bb
, last_bb
);
187 gcc_assert (last_bb
== bb
);
191 /* Return a string that contains the insn uid and optionally anything else
192 necessary to identify this insn in an output. It's valid to use a
193 static buffer for this. The ALIGNED parameter should cause the string
194 to be formatted so that multiple output lines will line up nicely. */
197 ebb_print_insn (rtx insn
, int aligned ATTRIBUTE_UNUSED
)
201 sprintf (tmp
, "%4d", INSN_UID (insn
));
205 /* Compare priority of two insns. Return a positive number if the second
206 insn is to be preferred for scheduling, and a negative one if the first
207 is to be preferred. Zero if they are equally good. */
210 rank (rtx insn1
, rtx insn2
)
212 basic_block bb1
= BLOCK_FOR_INSN (insn1
);
213 basic_block bb2
= BLOCK_FOR_INSN (insn2
);
215 if (bb1
->count
> bb2
->count
216 || bb1
->frequency
> bb2
->frequency
)
218 if (bb1
->count
< bb2
->count
219 || bb1
->frequency
< bb2
->frequency
)
224 /* NEXT is an instruction that depends on INSN (a backward dependence);
225 return nonzero if we should include this dependence in priority
229 contributes_to_priority (rtx next ATTRIBUTE_UNUSED
,
230 rtx insn ATTRIBUTE_UNUSED
)
235 /* INSN is a JUMP_INSN, COND_SET is the set of registers that are
236 conditionally set before INSN. Store the set of registers that
237 must be considered as used by this jump in USED and that of
238 registers that must be considered as set in SET. */
241 compute_jump_reg_dependencies (rtx insn
, regset cond_set
, regset used
,
244 basic_block b
= BLOCK_FOR_INSN (insn
);
248 FOR_EACH_EDGE (e
, ei
, b
->succs
)
249 if (e
->flags
& EDGE_FALLTHRU
)
250 /* The jump may be a by-product of a branch that has been merged
251 in the main codepath after being conditionalized. Therefore
252 it may guard the fallthrough block from using a value that has
253 conditionally overwritten that of the main codepath. So we
254 consider that it restores the value of the main codepath. */
255 bitmap_and (set
, DF_LIVE_IN (e
->dest
), cond_set
);
257 bitmap_ior_into (used
, DF_LIVE_IN (e
->dest
));
260 /* Used in schedule_insns to initialize current_sched_info for scheduling
261 regions (or single basic blocks). */
263 static struct sched_info ebb_sched_info
=
271 contributes_to_priority
,
272 compute_jump_reg_dependencies
,
279 begin_schedule_ready
,
284 /* We can create new blocks in begin_schedule_ready (). */
288 /* Returns the earliest block in EBB currently being processed where a
289 "similar load" 'insn2' is found, and hence LOAD_INSN can move
290 speculatively into the found block. All the following must hold:
292 (1) both loads have 1 base register (PFREE_CANDIDATEs).
293 (2) load_insn and load2 have a def-use dependence upon
294 the same insn 'insn1'.
296 From all these we can conclude that the two loads access memory
297 addresses that differ at most by a constant, and hence if moving
298 load_insn would cause an exception, it would have been caused by
301 The function uses list (given by LAST_BLOCK) of already processed
302 blocks in EBB. The list is formed in `add_deps_for_risky_insns'. */
305 earliest_block_with_similiar_load (basic_block last_block
, rtx load_insn
)
307 dep_link_t back_link
;
308 basic_block bb
, earliest_block
= NULL
;
310 FOR_EACH_DEP_LINK (back_link
, INSN_BACK_DEPS (load_insn
))
312 rtx insn1
= DEP_LINK_PRO (back_link
);
314 if (DEP_LINK_KIND (back_link
) == REG_DEP_TRUE
)
316 /* Found a DEF-USE dependence (insn1, load_insn). */
317 dep_link_t fore_link
;
319 FOR_EACH_DEP_LINK (fore_link
, INSN_FORW_DEPS (insn1
))
321 rtx insn2
= DEP_LINK_CON (fore_link
);
322 basic_block insn2_block
= BLOCK_FOR_INSN (insn2
);
324 if (DEP_LINK_KIND (fore_link
) == REG_DEP_TRUE
)
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 (DEPS_LIST_FIRST (INSN_BACK_DEPS (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 backward dependencies. */
455 init_deps (&tmp_deps
);
456 sched_analyze (&tmp_deps
, head
, tail
);
457 free_deps (&tmp_deps
);
459 /* Compute forward dependencies. */
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 /* rm_other_notes only removes notes which are _inside_ the
483 block---that is, it won't remove notes before the first real insn
484 or after the last real insn of the block. So if the first insn
485 has a REG_SAVE_NOTE which would otherwise be emitted before the
486 insn, it is redundant with the note before the start of the
487 block, and so we have to take it out. */
492 for (note
= REG_NOTES (head
); note
; note
= XEXP (note
, 1))
493 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
494 remove_note (head
, note
);
497 /* Remove remaining note insns from the block, save them in
498 note_list. These notes are restored at the end of
499 schedule_block (). */
500 rm_other_notes (head
, tail
);
502 unlink_bb_notes (first_bb
, last_bb
);
504 current_sched_info
->queue_must_finish_empty
= 1;
506 target_bb
= first_bb
;
507 schedule_block (&target_bb
, n_insns
);
509 /* We might pack all instructions into fewer blocks,
510 so we may made some of them empty. Can't assert (b == last_bb). */
512 /* Sanity check: verify that all region insns were scheduled. */
513 gcc_assert (sched_n_insns
== n_insns
);
514 head
= current_sched_info
->head
;
515 tail
= current_sched_info
->tail
;
517 if (EDGE_COUNT (last_bb
->preds
) == 0)
518 /* LAST_BB is unreachable. */
520 gcc_assert (first_bb
!= last_bb
521 && EDGE_COUNT (last_bb
->succs
) == 0);
522 last_bb
= last_bb
->prev_bb
;
523 delete_basic_block (last_bb
->next_bb
);
529 /* The one entry point in this file. */
535 int probability_cutoff
;
538 if (profile_info
&& flag_branch_probabilities
)
539 probability_cutoff
= PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK
);
541 probability_cutoff
= PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY
);
542 probability_cutoff
= REG_BR_PROB_BASE
/ 100 * probability_cutoff
;
544 /* Taking care of this degenerate case makes the rest of
545 this code simpler. */
546 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
549 /* We need current_sched_info in init_dependency_caches, which is
550 invoked via sched_init. */
551 current_sched_info
= &ebb_sched_info
;
553 df_set_flags (DF_LR_RUN_DCE
);
554 df_note_add_problem ();
556 df_clear_flags (DF_LR_RUN_DCE
);
557 regstat_compute_calls_crossed ();
560 compute_bb_for_insn ();
562 /* Initialize DONT_CALC_DEPS and ebb-{start, end} markers. */
563 bitmap_initialize (&dont_calc_deps
, 0);
564 bitmap_clear (&dont_calc_deps
);
566 /* Schedule every region in the subroutine. */
569 rtx head
= BB_HEAD (bb
);
576 if (bb
->next_bb
== EXIT_BLOCK_PTR
577 || LABEL_P (BB_HEAD (bb
->next_bb
)))
579 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
580 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
584 if (e
->probability
<= probability_cutoff
)
589 /* Blah. We should fix the rest of the code not to get confused by
594 head
= NEXT_INSN (head
);
595 else if (NOTE_P (tail
))
596 tail
= PREV_INSN (tail
);
597 else if (LABEL_P (head
))
598 head
= NEXT_INSN (head
);
603 bb
= schedule_ebb (head
, tail
);
605 bitmap_clear (&dont_calc_deps
);
607 /* Reposition the prologue and epilogue notes in case we moved the
608 prologue/epilogue insns. */
609 if (reload_completed
)
610 reposition_prologue_and_epilogue_notes ();
613 regstat_free_calls_crossed ();
616 /* INSN has been added to/removed from current ebb. */
618 add_remove_insn (rtx insn ATTRIBUTE_UNUSED
, int remove_p
)
626 /* BB was added to ebb after AFTER. */
628 add_block1 (basic_block bb
, basic_block after
)
630 /* Recovery blocks are always bounded by BARRIERS,
631 therefore, they always form single block EBB,
632 therefore, we can use rec->index to identify such EBBs. */
633 if (after
== EXIT_BLOCK_PTR
)
634 bitmap_set_bit (&dont_calc_deps
, bb
->index
);
635 else if (after
== last_bb
)
639 /* Return next block in ebb chain. For parameter meaning please refer to
640 sched-int.h: struct sched_info: advance_target_bb. */
642 advance_target_bb (basic_block bb
, rtx insn
)
646 if (BLOCK_FOR_INSN (insn
) != bb
647 && control_flow_insn_p (insn
)
648 /* We handle interblock movement of the speculation check
649 or over a speculation check in
650 haifa-sched.c: move_block_after_check (). */
651 && !IS_SPECULATION_BRANCHY_CHECK_P (insn
)
652 && !IS_SPECULATION_BRANCHY_CHECK_P (BB_END (bb
)))
654 /* Assert that we don't move jumps across blocks. */
655 gcc_assert (!control_flow_insn_p (BB_END (bb
))
656 && NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (bb
->next_bb
)));
663 /* Return next non empty block. */
667 gcc_assert (bb
!= last_bb
);
671 while (bb_note (bb
) == BB_END (bb
));
677 /* Fix internal data after interblock movement of jump instruction.
678 For parameter meaning please refer to
679 sched-int.h: struct sched_info: fix_recovery_cfg. */
681 fix_recovery_cfg (int bbi ATTRIBUTE_UNUSED
, int jump_bbi
, int jump_bb_nexti
)
683 gcc_assert (last_bb
->index
!= bbi
);
685 if (jump_bb_nexti
== last_bb
->index
)
686 last_bb
= BASIC_BLOCK (jump_bbi
);