Daily bump.
[official-gcc.git] / gcc / sched-ebb.c
bloba0422f4b1baf03a168e9dfc2e97afcfd66f15a45
1 /* Instruction scheduling pass.
2 Copyright (C) 1992-2017 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
11 version.
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
16 for more details.
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/>. */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "backend.h"
26 #include "target.h"
27 #include "rtl.h"
28 #include "cfghooks.h"
29 #include "df.h"
30 #include "profile.h"
31 #include "insn-attr.h"
32 #include "params.h"
33 #include "cfgrtl.h"
34 #include "cfgbuild.h"
35 #include "sched-int.h"
38 #ifdef INSN_SCHEDULING
40 /* The number of insns to be scheduled in total. */
41 static int rgn_n_insns;
43 /* The number of insns scheduled so far. */
44 static int sched_rgn_n_insns;
46 /* Set of blocks, that already have their dependencies calculated. */
47 static bitmap_head dont_calc_deps;
49 /* Last basic block in current ebb. */
50 static basic_block last_bb;
52 /* Implementations of the sched_info functions for region scheduling. */
53 static void init_ready_list (void);
54 static void begin_schedule_ready (rtx_insn *);
55 static int schedule_more_p (void);
56 static const char *ebb_print_insn (const rtx_insn *, int);
57 static int rank (rtx_insn *, rtx_insn *);
58 static int ebb_contributes_to_priority (rtx_insn *, rtx_insn *);
59 static basic_block earliest_block_with_similiar_load (basic_block, rtx);
60 static void add_deps_for_risky_insns (rtx_insn *, rtx_insn *);
61 static void debug_ebb_dependencies (rtx_insn *, rtx_insn *);
63 static void ebb_add_remove_insn (rtx_insn *, int);
64 static void ebb_add_block (basic_block, basic_block);
65 static basic_block advance_target_bb (basic_block, rtx_insn *);
66 static void ebb_fix_recovery_cfg (int, int, int);
68 /* Allocate memory and store the state of the frontend. Return the allocated
69 memory. */
70 static void *
71 save_ebb_state (void)
73 int *p = XNEW (int);
74 *p = sched_rgn_n_insns;
75 return p;
78 /* Restore the state of the frontend from P_, then free it. */
79 static void
80 restore_ebb_state (void *p_)
82 int *p = (int *)p_;
83 sched_rgn_n_insns = *p;
84 free (p_);
87 /* Return nonzero if there are more insns that should be scheduled. */
89 static int
90 schedule_more_p (void)
92 return sched_rgn_n_insns < rgn_n_insns;
95 /* Print dependency information about ebb between HEAD and TAIL. */
96 static void
97 debug_ebb_dependencies (rtx_insn *head, rtx_insn *tail)
99 fprintf (sched_dump,
100 ";; --------------- forward dependences: ------------ \n");
102 fprintf (sched_dump, "\n;; --- EBB Dependences --- from bb%d to bb%d \n",
103 BLOCK_NUM (head), BLOCK_NUM (tail));
105 debug_dependencies (head, tail);
108 /* Add all insns that are initially ready to the ready list READY. Called
109 once before scheduling a set of insns. */
111 static void
112 init_ready_list (void)
114 int n = 0;
115 rtx_insn *prev_head = current_sched_info->prev_head;
116 rtx_insn *next_tail = current_sched_info->next_tail;
117 rtx_insn *insn;
119 sched_rgn_n_insns = 0;
121 /* Print debugging information. */
122 if (sched_verbose >= 5)
123 debug_ebb_dependencies (NEXT_INSN (prev_head), PREV_INSN (next_tail));
125 /* Initialize ready list with all 'ready' insns in target block.
126 Count number of insns in the target block being scheduled. */
127 for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn))
129 try_ready (insn);
130 n++;
133 gcc_assert (n == rgn_n_insns);
136 /* INSN is being scheduled after LAST. Update counters. */
137 static void
138 begin_schedule_ready (rtx_insn *insn ATTRIBUTE_UNUSED)
140 sched_rgn_n_insns++;
143 /* INSN is being moved to its place in the schedule, after LAST. */
144 static void
145 begin_move_insn (rtx_insn *insn, rtx_insn *last)
147 if (BLOCK_FOR_INSN (insn) == last_bb
148 /* INSN is a jump in the last block, ... */
149 && control_flow_insn_p (insn)
150 /* that is going to be moved over some instructions. */
151 && last != PREV_INSN (insn))
153 edge e;
154 basic_block bb;
156 /* An obscure special case, where we do have partially dead
157 instruction scheduled after last control flow instruction.
158 In this case we can create new basic block. It is
159 always exactly one basic block last in the sequence. */
161 e = find_fallthru_edge (last_bb->succs);
163 gcc_checking_assert (!e || !(e->flags & EDGE_COMPLEX));
165 gcc_checking_assert (BLOCK_FOR_INSN (insn) == last_bb
166 && !IS_SPECULATION_CHECK_P (insn)
167 && BB_HEAD (last_bb) != insn
168 && BB_END (last_bb) == insn);
171 rtx_insn *x = NEXT_INSN (insn);
172 if (e)
173 gcc_checking_assert (NOTE_P (x) || LABEL_P (x));
174 else
175 gcc_checking_assert (BARRIER_P (x));
178 if (e)
180 bb = split_edge (e);
181 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_END (bb)));
183 else
185 /* Create an empty unreachable block after the INSN. */
186 rtx_insn *next = NEXT_INSN (insn);
187 if (next && BARRIER_P (next))
188 next = NEXT_INSN (next);
189 bb = create_basic_block (next, NULL_RTX, last_bb);
192 /* split_edge () creates BB before E->DEST. Keep in mind, that
193 this operation extends scheduling region till the end of BB.
194 Hence, we need to shift NEXT_TAIL, so haifa-sched.c won't go out
195 of the scheduling region. */
196 current_sched_info->next_tail = NEXT_INSN (BB_END (bb));
197 gcc_assert (current_sched_info->next_tail);
199 /* Append new basic block to the end of the ebb. */
200 sched_init_only_bb (bb, last_bb);
201 gcc_assert (last_bb == bb);
205 /* Return a string that contains the insn uid and optionally anything else
206 necessary to identify this insn in an output. It's valid to use a
207 static buffer for this. The ALIGNED parameter should cause the string
208 to be formatted so that multiple output lines will line up nicely. */
210 static const char *
211 ebb_print_insn (const rtx_insn *insn, int aligned ATTRIBUTE_UNUSED)
213 static char tmp[80];
215 /* '+' before insn means it is a new cycle start. */
216 if (GET_MODE (insn) == TImode)
217 sprintf (tmp, "+ %4d", INSN_UID (insn));
218 else
219 sprintf (tmp, " %4d", INSN_UID (insn));
221 return tmp;
224 /* Compare priority of two insns. Return a positive number if the second
225 insn is to be preferred for scheduling, and a negative one if the first
226 is to be preferred. Zero if they are equally good. */
228 static int
229 rank (rtx_insn *insn1, rtx_insn *insn2)
231 basic_block bb1 = BLOCK_FOR_INSN (insn1);
232 basic_block bb2 = BLOCK_FOR_INSN (insn2);
234 if (bb1->count > bb2->count
235 || bb1->frequency > bb2->frequency)
236 return -1;
237 if (bb1->count < bb2->count
238 || bb1->frequency < bb2->frequency)
239 return 1;
240 return 0;
243 /* NEXT is an instruction that depends on INSN (a backward dependence);
244 return nonzero if we should include this dependence in priority
245 calculations. */
247 static int
248 ebb_contributes_to_priority (rtx_insn *next ATTRIBUTE_UNUSED,
249 rtx_insn *insn ATTRIBUTE_UNUSED)
251 return 1;
254 /* INSN is a JUMP_INSN. Store the set of registers that
255 must be considered as used by this jump in USED. */
257 void
258 ebb_compute_jump_reg_dependencies (rtx insn, regset used)
260 basic_block b = BLOCK_FOR_INSN (insn);
261 edge e;
262 edge_iterator ei;
264 FOR_EACH_EDGE (e, ei, b->succs)
265 if ((e->flags & EDGE_FALLTHRU) == 0)
266 bitmap_ior_into (used, df_get_live_in (e->dest));
269 /* Used in schedule_insns to initialize current_sched_info for scheduling
270 regions (or single basic blocks). */
272 static struct common_sched_info_def ebb_common_sched_info;
274 static struct sched_deps_info_def ebb_sched_deps_info =
276 ebb_compute_jump_reg_dependencies,
277 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
278 NULL,
279 1, 0, 0
282 static struct haifa_sched_info ebb_sched_info =
284 init_ready_list,
285 NULL,
286 schedule_more_p,
287 NULL,
288 rank,
289 ebb_print_insn,
290 ebb_contributes_to_priority,
291 NULL, /* insn_finishes_block_p */
293 NULL, NULL,
294 NULL, NULL,
295 1, 0,
297 ebb_add_remove_insn,
298 begin_schedule_ready,
299 begin_move_insn,
300 advance_target_bb,
302 save_ebb_state,
303 restore_ebb_state,
305 SCHED_EBB
306 /* We can create new blocks in begin_schedule_ready (). */
307 | NEW_BBS
310 /* Returns the earliest block in EBB currently being processed where a
311 "similar load" 'insn2' is found, and hence LOAD_INSN can move
312 speculatively into the found block. All the following must hold:
314 (1) both loads have 1 base register (PFREE_CANDIDATEs).
315 (2) load_insn and load2 have a def-use dependence upon
316 the same insn 'insn1'.
318 From all these we can conclude that the two loads access memory
319 addresses that differ at most by a constant, and hence if moving
320 load_insn would cause an exception, it would have been caused by
321 load2 anyhow.
323 The function uses list (given by LAST_BLOCK) of already processed
324 blocks in EBB. The list is formed in `add_deps_for_risky_insns'. */
326 static basic_block
327 earliest_block_with_similiar_load (basic_block last_block, rtx load_insn)
329 sd_iterator_def back_sd_it;
330 dep_t back_dep;
331 basic_block bb, earliest_block = NULL;
333 FOR_EACH_DEP (load_insn, SD_LIST_BACK, back_sd_it, back_dep)
335 rtx_insn *insn1 = DEP_PRO (back_dep);
337 if (DEP_TYPE (back_dep) == REG_DEP_TRUE)
338 /* Found a DEF-USE dependence (insn1, load_insn). */
340 sd_iterator_def fore_sd_it;
341 dep_t fore_dep;
343 FOR_EACH_DEP (insn1, SD_LIST_FORW, fore_sd_it, fore_dep)
345 rtx_insn *insn2 = DEP_CON (fore_dep);
346 basic_block insn2_block = BLOCK_FOR_INSN (insn2);
348 if (DEP_TYPE (fore_dep) == REG_DEP_TRUE)
350 if (earliest_block != NULL
351 && earliest_block->index < insn2_block->index)
352 continue;
354 /* Found a DEF-USE dependence (insn1, insn2). */
355 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
356 /* insn2 not guaranteed to be a 1 base reg load. */
357 continue;
359 for (bb = last_block; bb; bb = (basic_block) bb->aux)
360 if (insn2_block == bb)
361 break;
363 if (!bb)
364 /* insn2 is the similar load. */
365 earliest_block = insn2_block;
371 return earliest_block;
374 /* The following function adds dependencies between jumps and risky
375 insns in given ebb. */
377 static void
378 add_deps_for_risky_insns (rtx_insn *head, rtx_insn *tail)
380 rtx_insn *insn, *prev;
381 int classification;
382 rtx_insn *last_jump = NULL;
383 rtx_insn *next_tail = NEXT_INSN (tail);
384 basic_block last_block = NULL, bb;
386 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
388 add_delay_dependencies (insn);
389 if (control_flow_insn_p (insn))
391 bb = BLOCK_FOR_INSN (insn);
392 bb->aux = last_block;
393 last_block = bb;
394 /* Ensure blocks stay in the same order. */
395 if (last_jump)
396 add_dependence (insn, last_jump, REG_DEP_ANTI);
397 last_jump = insn;
399 else if (INSN_P (insn) && last_jump != NULL_RTX)
401 classification = haifa_classify_insn (insn);
402 prev = last_jump;
404 switch (classification)
406 case PFREE_CANDIDATE:
407 if (flag_schedule_speculative_load)
409 bb = earliest_block_with_similiar_load (last_block, insn);
410 if (bb)
412 bb = (basic_block) bb->aux;
413 if (!bb)
414 break;
415 prev = BB_END (bb);
418 /* Fall through. */
419 case TRAP_RISKY:
420 case IRISKY:
421 case PRISKY_CANDIDATE:
422 /* ??? We could implement better checking PRISKY_CANDIDATEs
423 analogous to sched-rgn.c. */
424 /* We can not change the mode of the backward
425 dependency because REG_DEP_ANTI has the lowest
426 rank. */
427 if (! sched_insns_conditions_mutex_p (insn, prev))
429 if ((current_sched_info->flags & DO_SPECULATION)
430 && (spec_info->mask & BEGIN_CONTROL))
432 dep_def _dep, *dep = &_dep;
434 init_dep (dep, prev, insn, REG_DEP_ANTI);
436 if (current_sched_info->flags & USE_DEPS_LIST)
438 DEP_STATUS (dep) = set_dep_weak (DEP_ANTI, BEGIN_CONTROL,
439 MAX_DEP_WEAK);
442 sd_add_or_update_dep (dep, false);
444 else
445 add_dependence (insn, prev, REG_DEP_CONTROL);
448 break;
450 default:
451 break;
455 /* Maintain the invariant that bb->aux is clear after use. */
456 while (last_block)
458 bb = (basic_block) last_block->aux;
459 last_block->aux = NULL;
460 last_block = bb;
464 /* Schedule a single extended basic block, defined by the boundaries
465 HEAD and TAIL.
467 We change our expectations about scheduler behavior depending on
468 whether MODULO_SCHEDULING is true. If it is, we expect that the
469 caller has already called set_modulo_params and created delay pairs
470 as appropriate. If the modulo schedule failed, we return
471 NULL_RTX. */
473 basic_block
474 schedule_ebb (rtx_insn *head, rtx_insn *tail, bool modulo_scheduling)
476 basic_block first_bb, target_bb;
477 struct deps_desc tmp_deps;
478 bool success;
480 /* Blah. We should fix the rest of the code not to get confused by
481 a note or two. */
482 while (head != tail)
484 if (NOTE_P (head) || DEBUG_INSN_P (head))
485 head = NEXT_INSN (head);
486 else if (NOTE_P (tail) || DEBUG_INSN_P (tail))
487 tail = PREV_INSN (tail);
488 else if (LABEL_P (head))
489 head = NEXT_INSN (head);
490 else
491 break;
494 first_bb = BLOCK_FOR_INSN (head);
495 last_bb = BLOCK_FOR_INSN (tail);
497 if (no_real_insns_p (head, tail))
498 return BLOCK_FOR_INSN (tail);
500 gcc_assert (INSN_P (head) && INSN_P (tail));
502 if (!bitmap_bit_p (&dont_calc_deps, first_bb->index))
504 init_deps_global ();
506 /* Compute dependencies. */
507 init_deps (&tmp_deps, false);
508 sched_analyze (&tmp_deps, head, tail);
509 free_deps (&tmp_deps);
511 add_deps_for_risky_insns (head, tail);
513 if (targetm.sched.dependencies_evaluation_hook)
514 targetm.sched.dependencies_evaluation_hook (head, tail);
516 finish_deps_global ();
518 else
519 /* Only recovery blocks can have their dependencies already calculated,
520 and they always are single block ebbs. */
521 gcc_assert (first_bb == last_bb);
523 /* Set priorities. */
524 current_sched_info->sched_max_insns_priority = 0;
525 rgn_n_insns = set_priorities (head, tail);
526 current_sched_info->sched_max_insns_priority++;
528 current_sched_info->prev_head = PREV_INSN (head);
529 current_sched_info->next_tail = NEXT_INSN (tail);
531 remove_notes (head, tail);
533 unlink_bb_notes (first_bb, last_bb);
535 target_bb = first_bb;
537 /* Make ready list big enough to hold all the instructions from the ebb. */
538 sched_extend_ready_list (rgn_n_insns);
539 success = schedule_block (&target_bb, NULL);
540 gcc_assert (success || modulo_scheduling);
542 /* Free ready list. */
543 sched_finish_ready_list ();
545 /* We might pack all instructions into fewer blocks,
546 so we may made some of them empty. Can't assert (b == last_bb). */
548 /* Sanity check: verify that all region insns were scheduled. */
549 gcc_assert (modulo_scheduling || sched_rgn_n_insns == rgn_n_insns);
551 /* Free dependencies. */
552 sched_free_deps (current_sched_info->head, current_sched_info->tail, true);
554 gcc_assert (haifa_recovery_bb_ever_added_p
555 || deps_pools_are_empty_p ());
557 if (EDGE_COUNT (last_bb->preds) == 0)
558 /* LAST_BB is unreachable. */
560 gcc_assert (first_bb != last_bb
561 && EDGE_COUNT (last_bb->succs) == 0);
562 last_bb = last_bb->prev_bb;
563 delete_basic_block (last_bb->next_bb);
566 return success ? last_bb : NULL;
569 /* Perform initializations before running schedule_ebbs or a single
570 schedule_ebb. */
571 void
572 schedule_ebbs_init (void)
574 /* Setup infos. */
576 memcpy (&ebb_common_sched_info, &haifa_common_sched_info,
577 sizeof (ebb_common_sched_info));
579 ebb_common_sched_info.fix_recovery_cfg = ebb_fix_recovery_cfg;
580 ebb_common_sched_info.add_block = ebb_add_block;
581 ebb_common_sched_info.sched_pass_id = SCHED_EBB_PASS;
583 common_sched_info = &ebb_common_sched_info;
584 sched_deps_info = &ebb_sched_deps_info;
585 current_sched_info = &ebb_sched_info;
588 haifa_sched_init ();
590 compute_bb_for_insn ();
592 /* Initialize DONT_CALC_DEPS and ebb-{start, end} markers. */
593 bitmap_initialize (&dont_calc_deps, 0);
594 bitmap_clear (&dont_calc_deps);
597 /* Perform cleanups after scheduling using schedules_ebbs or schedule_ebb. */
598 void
599 schedule_ebbs_finish (void)
601 bitmap_clear (&dont_calc_deps);
603 /* Reposition the prologue and epilogue notes in case we moved the
604 prologue/epilogue insns. */
605 if (reload_completed)
606 reposition_prologue_and_epilogue_notes ();
608 haifa_sched_finish ();
611 /* The main entry point in this file. */
613 void
614 schedule_ebbs (void)
616 basic_block bb;
617 int probability_cutoff;
618 rtx_insn *tail;
620 /* Taking care of this degenerate case makes the rest of
621 this code simpler. */
622 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
623 return;
625 if (profile_info && profile_status_for_fn (cfun) == PROFILE_READ)
626 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
627 else
628 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
629 probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
631 schedule_ebbs_init ();
633 /* Schedule every region in the subroutine. */
634 FOR_EACH_BB_FN (bb, cfun)
636 rtx_insn *head = BB_HEAD (bb);
638 if (bb->flags & BB_DISABLE_SCHEDULE)
639 continue;
641 for (;;)
643 edge e;
644 tail = BB_END (bb);
645 if (bb->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
646 || LABEL_P (BB_HEAD (bb->next_bb)))
647 break;
648 e = find_fallthru_edge (bb->succs);
649 if (! e)
650 break;
651 if (e->probability.initialized_p ()
652 && e->probability.to_reg_br_prob_base () <= probability_cutoff)
653 break;
654 if (e->dest->flags & BB_DISABLE_SCHEDULE)
655 break;
656 bb = bb->next_bb;
659 bb = schedule_ebb (head, tail, false);
661 schedule_ebbs_finish ();
664 /* INSN has been added to/removed from current ebb. */
665 static void
666 ebb_add_remove_insn (rtx_insn *insn ATTRIBUTE_UNUSED, int remove_p)
668 if (!remove_p)
669 rgn_n_insns++;
670 else
671 rgn_n_insns--;
674 /* BB was added to ebb after AFTER. */
675 static void
676 ebb_add_block (basic_block bb, basic_block after)
678 /* Recovery blocks are always bounded by BARRIERS,
679 therefore, they always form single block EBB,
680 therefore, we can use rec->index to identify such EBBs. */
681 if (after == EXIT_BLOCK_PTR_FOR_FN (cfun))
682 bitmap_set_bit (&dont_calc_deps, bb->index);
683 else if (after == last_bb)
684 last_bb = bb;
687 /* Return next block in ebb chain. For parameter meaning please refer to
688 sched-int.h: struct sched_info: advance_target_bb. */
689 static basic_block
690 advance_target_bb (basic_block bb, rtx_insn *insn)
692 if (insn)
694 if (BLOCK_FOR_INSN (insn) != bb
695 && control_flow_insn_p (insn)
696 /* We handle interblock movement of the speculation check
697 or over a speculation check in
698 haifa-sched.c: move_block_after_check (). */
699 && !IS_SPECULATION_BRANCHY_CHECK_P (insn)
700 && !IS_SPECULATION_BRANCHY_CHECK_P (BB_END (bb)))
702 /* Assert that we don't move jumps across blocks. */
703 gcc_assert (!control_flow_insn_p (BB_END (bb))
704 && NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (bb->next_bb)));
705 return bb;
707 else
708 return 0;
710 else
711 /* Return next non empty block. */
715 gcc_assert (bb != last_bb);
717 bb = bb->next_bb;
719 while (bb_note (bb) == BB_END (bb));
721 return bb;
725 /* Fix internal data after interblock movement of jump instruction.
726 For parameter meaning please refer to
727 sched-int.h: struct sched_info: fix_recovery_cfg. */
728 static void
729 ebb_fix_recovery_cfg (int bbi ATTRIBUTE_UNUSED, int jump_bbi,
730 int jump_bb_nexti)
732 gcc_assert (last_bb->index != bbi);
734 if (jump_bb_nexti == last_bb->index)
735 last_bb = BASIC_BLOCK_FOR_FN (cfun, jump_bbi);
738 #endif /* INSN_SCHEDULING */