1 /* Instruction scheduling pass.
2 Copyright (C) 1992-2014 Free Software Foundation, Inc.
3 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
4 and currently maintained by, Jim Wilson (wilson@cygnus.com)
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
26 #include "diagnostic-core.h"
29 #include "hard-reg-set.h"
39 #include "insn-config.h"
40 #include "insn-attr.h"
44 #include "dominance.h"
49 #include "basic-block.h"
50 #include "sched-int.h"
54 #ifdef INSN_SCHEDULING
56 /* The number of insns to be scheduled in total. */
57 static int rgn_n_insns
;
59 /* The number of insns scheduled so far. */
60 static int sched_rgn_n_insns
;
62 /* Set of blocks, that already have their dependencies calculated. */
63 static bitmap_head dont_calc_deps
;
65 /* Last basic block in current ebb. */
66 static basic_block last_bb
;
68 /* Implementations of the sched_info functions for region scheduling. */
69 static void init_ready_list (void);
70 static void begin_schedule_ready (rtx_insn
*);
71 static int schedule_more_p (void);
72 static const char *ebb_print_insn (const rtx_insn
*, int);
73 static int rank (rtx_insn
*, rtx_insn
*);
74 static int ebb_contributes_to_priority (rtx_insn
*, rtx_insn
*);
75 static basic_block
earliest_block_with_similiar_load (basic_block
, rtx
);
76 static void add_deps_for_risky_insns (rtx_insn
*, rtx_insn
*);
77 static void debug_ebb_dependencies (rtx_insn
*, rtx_insn
*);
79 static void ebb_add_remove_insn (rtx_insn
*, int);
80 static void ebb_add_block (basic_block
, basic_block
);
81 static basic_block
advance_target_bb (basic_block
, rtx_insn
*);
82 static void ebb_fix_recovery_cfg (int, int, int);
84 /* Allocate memory and store the state of the frontend. Return the allocated
90 *p
= sched_rgn_n_insns
;
94 /* Restore the state of the frontend from P_, then free it. */
96 restore_ebb_state (void *p_
)
99 sched_rgn_n_insns
= *p
;
103 /* Return nonzero if there are more insns that should be scheduled. */
106 schedule_more_p (void)
108 return sched_rgn_n_insns
< rgn_n_insns
;
111 /* Print dependency information about ebb between HEAD and TAIL. */
113 debug_ebb_dependencies (rtx_insn
*head
, rtx_insn
*tail
)
116 ";; --------------- forward dependences: ------------ \n");
118 fprintf (sched_dump
, "\n;; --- EBB Dependences --- from bb%d to bb%d \n",
119 BLOCK_NUM (head
), BLOCK_NUM (tail
));
121 debug_dependencies (head
, tail
);
124 /* Add all insns that are initially ready to the ready list READY. Called
125 once before scheduling a set of insns. */
128 init_ready_list (void)
131 rtx_insn
*prev_head
= current_sched_info
->prev_head
;
132 rtx_insn
*next_tail
= current_sched_info
->next_tail
;
135 sched_rgn_n_insns
= 0;
137 /* Print debugging information. */
138 if (sched_verbose
>= 5)
139 debug_ebb_dependencies (NEXT_INSN (prev_head
), PREV_INSN (next_tail
));
141 /* Initialize ready list with all 'ready' insns in target block.
142 Count number of insns in the target block being scheduled. */
143 for (insn
= NEXT_INSN (prev_head
); insn
!= next_tail
; insn
= NEXT_INSN (insn
))
149 gcc_assert (n
== rgn_n_insns
);
152 /* INSN is being scheduled after LAST. Update counters. */
154 begin_schedule_ready (rtx_insn
*insn ATTRIBUTE_UNUSED
)
159 /* INSN is being moved to its place in the schedule, after LAST. */
161 begin_move_insn (rtx_insn
*insn
, rtx_insn
*last
)
163 if (BLOCK_FOR_INSN (insn
) == last_bb
164 /* INSN is a jump in the last block, ... */
165 && control_flow_insn_p (insn
)
166 /* that is going to be moved over some instructions. */
167 && last
!= PREV_INSN (insn
))
172 /* An obscure special case, where we do have partially dead
173 instruction scheduled after last control flow instruction.
174 In this case we can create new basic block. It is
175 always exactly one basic block last in the sequence. */
177 e
= find_fallthru_edge (last_bb
->succs
);
179 gcc_checking_assert (!e
|| !(e
->flags
& EDGE_COMPLEX
));
181 gcc_checking_assert (BLOCK_FOR_INSN (insn
) == last_bb
182 && !IS_SPECULATION_CHECK_P (insn
)
183 && BB_HEAD (last_bb
) != insn
184 && BB_END (last_bb
) == insn
);
189 x
= NEXT_INSN (insn
);
191 gcc_checking_assert (NOTE_P (x
) || LABEL_P (x
));
193 gcc_checking_assert (BARRIER_P (x
));
199 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_END (bb
)));
203 /* Create an empty unreachable block after the INSN. */
204 rtx_insn
*next
= NEXT_INSN (insn
);
205 if (next
&& BARRIER_P (next
))
206 next
= NEXT_INSN (next
);
207 bb
= create_basic_block (next
, NULL_RTX
, last_bb
);
210 /* split_edge () creates BB before E->DEST. Keep in mind, that
211 this operation extends scheduling region till the end of BB.
212 Hence, we need to shift NEXT_TAIL, so haifa-sched.c won't go out
213 of the scheduling region. */
214 current_sched_info
->next_tail
= NEXT_INSN (BB_END (bb
));
215 gcc_assert (current_sched_info
->next_tail
);
217 /* Append new basic block to the end of the ebb. */
218 sched_init_only_bb (bb
, last_bb
);
219 gcc_assert (last_bb
== bb
);
223 /* Return a string that contains the insn uid and optionally anything else
224 necessary to identify this insn in an output. It's valid to use a
225 static buffer for this. The ALIGNED parameter should cause the string
226 to be formatted so that multiple output lines will line up nicely. */
229 ebb_print_insn (const rtx_insn
*insn
, int aligned ATTRIBUTE_UNUSED
)
233 /* '+' before insn means it is a new cycle start. */
234 if (GET_MODE (insn
) == TImode
)
235 sprintf (tmp
, "+ %4d", INSN_UID (insn
));
237 sprintf (tmp
, " %4d", INSN_UID (insn
));
242 /* Compare priority of two insns. Return a positive number if the second
243 insn is to be preferred for scheduling, and a negative one if the first
244 is to be preferred. Zero if they are equally good. */
247 rank (rtx_insn
*insn1
, rtx_insn
*insn2
)
249 basic_block bb1
= BLOCK_FOR_INSN (insn1
);
250 basic_block bb2
= BLOCK_FOR_INSN (insn2
);
252 if (bb1
->count
> bb2
->count
253 || bb1
->frequency
> bb2
->frequency
)
255 if (bb1
->count
< bb2
->count
256 || bb1
->frequency
< bb2
->frequency
)
261 /* NEXT is an instruction that depends on INSN (a backward dependence);
262 return nonzero if we should include this dependence in priority
266 ebb_contributes_to_priority (rtx_insn
*next ATTRIBUTE_UNUSED
,
267 rtx_insn
*insn ATTRIBUTE_UNUSED
)
272 /* INSN is a JUMP_INSN. Store the set of registers that
273 must be considered as used by this jump in USED. */
276 ebb_compute_jump_reg_dependencies (rtx insn
, regset used
)
278 basic_block b
= BLOCK_FOR_INSN (insn
);
282 FOR_EACH_EDGE (e
, ei
, b
->succs
)
283 if ((e
->flags
& EDGE_FALLTHRU
) == 0)
284 bitmap_ior_into (used
, df_get_live_in (e
->dest
));
287 /* Used in schedule_insns to initialize current_sched_info for scheduling
288 regions (or single basic blocks). */
290 static struct common_sched_info_def ebb_common_sched_info
;
292 static struct sched_deps_info_def ebb_sched_deps_info
=
294 ebb_compute_jump_reg_dependencies
,
295 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
,
300 static struct haifa_sched_info ebb_sched_info
=
308 ebb_contributes_to_priority
,
309 NULL
, /* insn_finishes_block_p */
316 begin_schedule_ready
,
324 /* We can create new blocks in begin_schedule_ready (). */
328 /* Returns the earliest block in EBB currently being processed where a
329 "similar load" 'insn2' is found, and hence LOAD_INSN can move
330 speculatively into the found block. All the following must hold:
332 (1) both loads have 1 base register (PFREE_CANDIDATEs).
333 (2) load_insn and load2 have a def-use dependence upon
334 the same insn 'insn1'.
336 From all these we can conclude that the two loads access memory
337 addresses that differ at most by a constant, and hence if moving
338 load_insn would cause an exception, it would have been caused by
341 The function uses list (given by LAST_BLOCK) of already processed
342 blocks in EBB. The list is formed in `add_deps_for_risky_insns'. */
345 earliest_block_with_similiar_load (basic_block last_block
, rtx load_insn
)
347 sd_iterator_def back_sd_it
;
349 basic_block bb
, earliest_block
= NULL
;
351 FOR_EACH_DEP (load_insn
, SD_LIST_BACK
, back_sd_it
, back_dep
)
353 rtx_insn
*insn1
= DEP_PRO (back_dep
);
355 if (DEP_TYPE (back_dep
) == REG_DEP_TRUE
)
356 /* Found a DEF-USE dependence (insn1, load_insn). */
358 sd_iterator_def fore_sd_it
;
361 FOR_EACH_DEP (insn1
, SD_LIST_FORW
, fore_sd_it
, fore_dep
)
363 rtx_insn
*insn2
= DEP_CON (fore_dep
);
364 basic_block insn2_block
= BLOCK_FOR_INSN (insn2
);
366 if (DEP_TYPE (fore_dep
) == REG_DEP_TRUE
)
368 if (earliest_block
!= NULL
369 && earliest_block
->index
< insn2_block
->index
)
372 /* Found a DEF-USE dependence (insn1, insn2). */
373 if (haifa_classify_insn (insn2
) != PFREE_CANDIDATE
)
374 /* insn2 not guaranteed to be a 1 base reg load. */
377 for (bb
= last_block
; bb
; bb
= (basic_block
) bb
->aux
)
378 if (insn2_block
== bb
)
382 /* insn2 is the similar load. */
383 earliest_block
= insn2_block
;
389 return earliest_block
;
392 /* The following function adds dependencies between jumps and risky
393 insns in given ebb. */
396 add_deps_for_risky_insns (rtx_insn
*head
, rtx_insn
*tail
)
398 rtx_insn
*insn
, *prev
;
400 rtx_insn
*last_jump
= NULL
;
401 rtx_insn
*next_tail
= NEXT_INSN (tail
);
402 basic_block last_block
= NULL
, bb
;
404 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
406 add_delay_dependencies (insn
);
407 if (control_flow_insn_p (insn
))
409 bb
= BLOCK_FOR_INSN (insn
);
410 bb
->aux
= last_block
;
412 /* Ensure blocks stay in the same order. */
414 add_dependence (insn
, last_jump
, REG_DEP_ANTI
);
417 else if (INSN_P (insn
) && last_jump
!= NULL_RTX
)
419 classification
= haifa_classify_insn (insn
);
422 switch (classification
)
424 case PFREE_CANDIDATE
:
425 if (flag_schedule_speculative_load
)
427 bb
= earliest_block_with_similiar_load (last_block
, insn
);
430 bb
= (basic_block
) bb
->aux
;
439 case PRISKY_CANDIDATE
:
440 /* ??? We could implement better checking PRISKY_CANDIDATEs
441 analogous to sched-rgn.c. */
442 /* We can not change the mode of the backward
443 dependency because REG_DEP_ANTI has the lowest
445 if (! sched_insns_conditions_mutex_p (insn
, prev
))
447 if ((current_sched_info
->flags
& DO_SPECULATION
)
448 && (spec_info
->mask
& BEGIN_CONTROL
))
450 dep_def _dep
, *dep
= &_dep
;
452 init_dep (dep
, prev
, insn
, REG_DEP_ANTI
);
454 if (current_sched_info
->flags
& USE_DEPS_LIST
)
456 DEP_STATUS (dep
) = set_dep_weak (DEP_ANTI
, BEGIN_CONTROL
,
460 sd_add_or_update_dep (dep
, false);
463 add_dependence (insn
, prev
, REG_DEP_CONTROL
);
473 /* Maintain the invariant that bb->aux is clear after use. */
476 bb
= (basic_block
) last_block
->aux
;
477 last_block
->aux
= NULL
;
482 /* Schedule a single extended basic block, defined by the boundaries
485 We change our expectations about scheduler behaviour depending on
486 whether MODULO_SCHEDULING is true. If it is, we expect that the
487 caller has already called set_modulo_params and created delay pairs
488 as appropriate. If the modulo schedule failed, we return
492 schedule_ebb (rtx_insn
*head
, rtx_insn
*tail
, bool modulo_scheduling
)
494 basic_block first_bb
, target_bb
;
495 struct deps_desc tmp_deps
;
498 /* Blah. We should fix the rest of the code not to get confused by
502 if (NOTE_P (head
) || DEBUG_INSN_P (head
))
503 head
= NEXT_INSN (head
);
504 else if (NOTE_P (tail
) || DEBUG_INSN_P (tail
))
505 tail
= PREV_INSN (tail
);
506 else if (LABEL_P (head
))
507 head
= NEXT_INSN (head
);
512 first_bb
= BLOCK_FOR_INSN (head
);
513 last_bb
= BLOCK_FOR_INSN (tail
);
515 if (no_real_insns_p (head
, tail
))
516 return BLOCK_FOR_INSN (tail
);
518 gcc_assert (INSN_P (head
) && INSN_P (tail
));
520 if (!bitmap_bit_p (&dont_calc_deps
, first_bb
->index
))
524 /* Compute dependencies. */
525 init_deps (&tmp_deps
, false);
526 sched_analyze (&tmp_deps
, head
, tail
);
527 free_deps (&tmp_deps
);
529 add_deps_for_risky_insns (head
, tail
);
531 if (targetm
.sched
.dependencies_evaluation_hook
)
532 targetm
.sched
.dependencies_evaluation_hook (head
, tail
);
534 finish_deps_global ();
537 /* Only recovery blocks can have their dependencies already calculated,
538 and they always are single block ebbs. */
539 gcc_assert (first_bb
== last_bb
);
541 /* Set priorities. */
542 current_sched_info
->sched_max_insns_priority
= 0;
543 rgn_n_insns
= set_priorities (head
, tail
);
544 current_sched_info
->sched_max_insns_priority
++;
546 current_sched_info
->prev_head
= PREV_INSN (head
);
547 current_sched_info
->next_tail
= NEXT_INSN (tail
);
549 remove_notes (head
, tail
);
551 unlink_bb_notes (first_bb
, last_bb
);
553 target_bb
= first_bb
;
555 /* Make ready list big enough to hold all the instructions from the ebb. */
556 sched_extend_ready_list (rgn_n_insns
);
557 success
= schedule_block (&target_bb
, NULL
);
558 gcc_assert (success
|| modulo_scheduling
);
560 /* Free ready list. */
561 sched_finish_ready_list ();
563 /* We might pack all instructions into fewer blocks,
564 so we may made some of them empty. Can't assert (b == last_bb). */
566 /* Sanity check: verify that all region insns were scheduled. */
567 gcc_assert (modulo_scheduling
|| sched_rgn_n_insns
== rgn_n_insns
);
569 /* Free dependencies. */
570 sched_free_deps (current_sched_info
->head
, current_sched_info
->tail
, true);
572 gcc_assert (haifa_recovery_bb_ever_added_p
573 || deps_pools_are_empty_p ());
575 if (EDGE_COUNT (last_bb
->preds
) == 0)
576 /* LAST_BB is unreachable. */
578 gcc_assert (first_bb
!= last_bb
579 && EDGE_COUNT (last_bb
->succs
) == 0);
580 last_bb
= last_bb
->prev_bb
;
581 delete_basic_block (last_bb
->next_bb
);
584 return success
? last_bb
: NULL
;
587 /* Perform initializations before running schedule_ebbs or a single
590 schedule_ebbs_init (void)
594 memcpy (&ebb_common_sched_info
, &haifa_common_sched_info
,
595 sizeof (ebb_common_sched_info
));
597 ebb_common_sched_info
.fix_recovery_cfg
= ebb_fix_recovery_cfg
;
598 ebb_common_sched_info
.add_block
= ebb_add_block
;
599 ebb_common_sched_info
.sched_pass_id
= SCHED_EBB_PASS
;
601 common_sched_info
= &ebb_common_sched_info
;
602 sched_deps_info
= &ebb_sched_deps_info
;
603 current_sched_info
= &ebb_sched_info
;
608 compute_bb_for_insn ();
610 /* Initialize DONT_CALC_DEPS and ebb-{start, end} markers. */
611 bitmap_initialize (&dont_calc_deps
, 0);
612 bitmap_clear (&dont_calc_deps
);
615 /* Perform cleanups after scheduling using schedules_ebbs or schedule_ebb. */
617 schedule_ebbs_finish (void)
619 bitmap_clear (&dont_calc_deps
);
621 /* Reposition the prologue and epilogue notes in case we moved the
622 prologue/epilogue insns. */
623 if (reload_completed
)
624 reposition_prologue_and_epilogue_notes ();
626 haifa_sched_finish ();
629 /* The main entry point in this file. */
635 int probability_cutoff
;
638 /* Taking care of this degenerate case makes the rest of
639 this code simpler. */
640 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
643 if (profile_info
&& flag_branch_probabilities
)
644 probability_cutoff
= PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK
);
646 probability_cutoff
= PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY
);
647 probability_cutoff
= REG_BR_PROB_BASE
/ 100 * probability_cutoff
;
649 schedule_ebbs_init ();
651 /* Schedule every region in the subroutine. */
652 FOR_EACH_BB_FN (bb
, cfun
)
654 rtx_insn
*head
= BB_HEAD (bb
);
656 if (bb
->flags
& BB_DISABLE_SCHEDULE
)
663 if (bb
->next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
664 || LABEL_P (BB_HEAD (bb
->next_bb
)))
666 e
= find_fallthru_edge (bb
->succs
);
669 if (e
->probability
<= probability_cutoff
)
671 if (e
->dest
->flags
& BB_DISABLE_SCHEDULE
)
676 bb
= schedule_ebb (head
, tail
, false);
678 schedule_ebbs_finish ();
681 /* INSN has been added to/removed from current ebb. */
683 ebb_add_remove_insn (rtx_insn
*insn ATTRIBUTE_UNUSED
, int remove_p
)
691 /* BB was added to ebb after AFTER. */
693 ebb_add_block (basic_block bb
, basic_block after
)
695 /* Recovery blocks are always bounded by BARRIERS,
696 therefore, they always form single block EBB,
697 therefore, we can use rec->index to identify such EBBs. */
698 if (after
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
699 bitmap_set_bit (&dont_calc_deps
, bb
->index
);
700 else if (after
== last_bb
)
704 /* Return next block in ebb chain. For parameter meaning please refer to
705 sched-int.h: struct sched_info: advance_target_bb. */
707 advance_target_bb (basic_block bb
, rtx_insn
*insn
)
711 if (BLOCK_FOR_INSN (insn
) != bb
712 && control_flow_insn_p (insn
)
713 /* We handle interblock movement of the speculation check
714 or over a speculation check in
715 haifa-sched.c: move_block_after_check (). */
716 && !IS_SPECULATION_BRANCHY_CHECK_P (insn
)
717 && !IS_SPECULATION_BRANCHY_CHECK_P (BB_END (bb
)))
719 /* Assert that we don't move jumps across blocks. */
720 gcc_assert (!control_flow_insn_p (BB_END (bb
))
721 && NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (bb
->next_bb
)));
728 /* Return next non empty block. */
732 gcc_assert (bb
!= last_bb
);
736 while (bb_note (bb
) == BB_END (bb
));
742 /* Fix internal data after interblock movement of jump instruction.
743 For parameter meaning please refer to
744 sched-int.h: struct sched_info: fix_recovery_cfg. */
746 ebb_fix_recovery_cfg (int bbi ATTRIBUTE_UNUSED
, int jump_bbi
,
749 gcc_assert (last_bb
->index
!= bbi
);
751 if (jump_bb_nexti
== last_bb
->index
)
752 last_bb
= BASIC_BLOCK_FOR_FN (cfun
, jump_bbi
);
755 #endif /* INSN_SCHEDULING */