1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
3 2001, 2002, 2003, 2004, 2005, 2006, 2007 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 3, 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 COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* Instruction scheduling pass. This file, along with sched-deps.c,
24 contains the generic parts. The actual entry point is found for
25 the normal instruction scheduling pass is found in sched-rgn.c.
27 We compute insn priorities based on data dependencies. Flow
28 analysis only creates a fraction of the data-dependencies we must
29 observe: namely, only those dependencies which the combiner can be
30 expected to use. For this pass, we must therefore create the
31 remaining dependencies we need to observe: register dependencies,
32 memory dependencies, dependencies to keep function calls in order,
33 and the dependence between a conditional branch and the setting of
34 condition codes are all dealt with here.
36 The scheduler first traverses the data flow graph, starting with
37 the last instruction, and proceeding to the first, assigning values
38 to insn_priority as it goes. This sorts the instructions
39 topologically by data dependence.
41 Once priorities have been established, we order the insns using
42 list scheduling. This works as follows: starting with a list of
43 all the ready insns, and sorted according to priority number, we
44 schedule the insn from the end of the list by placing its
45 predecessors in the list according to their priority order. We
46 consider this insn scheduled by setting the pointer to the "end" of
47 the list to point to the previous insn. When an insn has no
48 predecessors, we either queue it until sufficient time has elapsed
49 or add it to the ready list. As the instructions are scheduled or
50 when stalls are introduced, the queue advances and dumps insns into
51 the ready list. When all insns down to the lowest priority have
52 been scheduled, the critical path of the basic block has been made
53 as short as possible. The remaining insns are then scheduled in
56 The following list shows the order in which we want to break ties
57 among insns in the ready list:
59 1. choose insn with the longest path to end of bb, ties
61 2. choose insn with least contribution to register pressure,
63 3. prefer in-block upon interblock motion, ties broken by
64 4. prefer useful upon speculative motion, ties broken by
65 5. choose insn with largest control flow probability, ties
67 6. choose insn with the least dependences upon the previously
68 scheduled insn, or finally
69 7 choose the insn which has the most insns dependent on it.
70 8. choose insn with lowest UID.
72 Memory references complicate matters. Only if we can be certain
73 that memory references are not part of the data dependency graph
74 (via true, anti, or output dependence), can we move operations past
75 memory references. To first approximation, reads can be done
76 independently, while writes introduce dependencies. Better
77 approximations will yield fewer dependencies.
79 Before reload, an extended analysis of interblock data dependences
80 is required for interblock scheduling. This is performed in
81 compute_block_backward_dependences ().
83 Dependencies set up by memory references are treated in exactly the
84 same way as other dependencies, by using insn backward dependences
85 INSN_BACK_DEPS. INSN_BACK_DEPS are translated into forward dependences
86 INSN_FORW_DEPS the purpose of forward list scheduling.
88 Having optimized the critical path, we may have also unduly
89 extended the lifetimes of some registers. If an operation requires
90 that constants be loaded into registers, it is certainly desirable
91 to load those constants as early as necessary, but no earlier.
92 I.e., it will not do to load up a bunch of registers at the
93 beginning of a basic block only to use them at the end, if they
94 could be loaded later, since this may result in excessive register
97 Note that since branches are never in basic blocks, but only end
98 basic blocks, this pass will not move branches. But that is ok,
99 since we can use GNU's delayed branch scheduling pass to take care
102 Also note that no further optimizations based on algebraic
103 identities are performed, so this pass would be a good one to
104 perform instruction splitting, such as breaking up a multiply
105 instruction into shifts and adds where that is profitable.
107 Given the memory aliasing analysis that this pass should perform,
108 it should be possible to remove redundant stores to memory, and to
109 load values from registers instead of hitting memory.
111 Before reload, speculative insns are moved only if a 'proof' exists
112 that no exception will be caused by this, and if no live registers
113 exist that inhibit the motion (live registers constraints are not
114 represented by data dependence edges).
116 This pass must update information that subsequent passes expect to
117 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
118 reg_n_calls_crossed, and reg_live_length. Also, BB_HEAD, BB_END.
120 The information in the line number notes is carefully retained by
121 this pass. Notes that refer to the starting and ending of
122 exception regions are also carefully retained by this pass. All
123 other NOTE insns are grouped in their same relative order at the
124 beginning of basic blocks and regions that have been scheduled. */
128 #include "coretypes.h"
133 #include "hard-reg-set.h"
135 #include "function.h"
137 #include "insn-config.h"
138 #include "insn-attr.h"
142 #include "sched-int.h"
148 #ifdef INSN_SCHEDULING
150 /* issue_rate is the number of insns that can be scheduled in the same
151 machine cycle. It can be defined in the config/mach/mach.h file,
152 otherwise we set it to 1. */
154 static int issue_rate;
156 /* sched-verbose controls the amount of debugging output the
157 scheduler prints. It is controlled by -fsched-verbose=N:
158 N>0 and no -DSR : the output is directed to stderr.
159 N>=10 will direct the printouts to stderr (regardless of -dSR).
161 N=2: bb's probabilities, detailed ready list info, unit/insn info.
162 N=3: rtl at abort point, control-flow, regions info.
163 N=5: dependences info. */
165 static int sched_verbose_param = 0;
166 int sched_verbose = 0;
168 /* Debugging file. All printouts are sent to dump, which is always set,
169 either to stderr, or to the dump listing file (-dRS). */
170 FILE *sched_dump = 0;
172 /* Highest uid before scheduling. */
173 static int old_max_uid;
175 /* fix_sched_param() is called from toplev.c upon detection
176 of the -fsched-verbose=N option. */
179 fix_sched_param (const char *param, const char *val)
181 if (!strcmp (param, "verbose"))
182 sched_verbose_param = atoi (val);
184 warning (0, "fix_sched_param: unknown param: %s", param);
187 struct haifa_insn_data *h_i_d;
189 #define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick)
190 #define INTER_TICK(INSN) (h_i_d[INSN_UID (INSN)].inter_tick)
192 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
193 then it should be recalculated from scratch. */
194 #define INVALID_TICK (-(max_insn_queue_index + 1))
195 /* The minimal value of the INSN_TICK of an instruction. */
196 #define MIN_TICK (-max_insn_queue_index)
198 /* Issue points are used to distinguish between instructions in max_issue ().
199 For now, all instructions are equally good. */
200 #define ISSUE_POINTS(INSN) 1
202 /* List of important notes we must keep around. This is a pointer to the
203 last element in the list. */
204 static rtx note_list;
206 static struct spec_info_def spec_info_var;
207 /* Description of the speculative part of the scheduling.
208 If NULL - no speculation. */
209 spec_info_t spec_info;
211 /* True, if recovery block was added during scheduling of current block.
212 Used to determine, if we need to fix INSN_TICKs. */
213 static bool haifa_recovery_bb_recently_added_p;
215 /* True, if recovery block was added during this scheduling pass.
216 Used to determine if we should have empty memory pools of dependencies
217 after finishing current region. */
218 bool haifa_recovery_bb_ever_added_p;
220 /* Counters of different types of speculative instructions. */
221 static int nr_begin_data, nr_be_in_data, nr_begin_control, nr_be_in_control;
223 /* Array used in {unlink, restore}_bb_notes. */
224 static rtx *bb_header = 0;
226 /* Number of basic_blocks. */
227 static int old_last_basic_block;
229 /* Basic block after which recovery blocks will be created. */
230 static basic_block before_recovery;
234 /* An instruction is ready to be scheduled when all insns preceding it
235 have already been scheduled. It is important to ensure that all
236 insns which use its result will not be executed until its result
237 has been computed. An insn is maintained in one of four structures:
239 (P) the "Pending" set of insns which cannot be scheduled until
240 their dependencies have been satisfied.
241 (Q) the "Queued" set of insns that can be scheduled when sufficient
243 (R) the "Ready" list of unscheduled, uncommitted insns.
244 (S) the "Scheduled" list of insns.
246 Initially, all insns are either "Pending" or "Ready" depending on
247 whether their dependencies are satisfied.
249 Insns move from the "Ready" list to the "Scheduled" list as they
250 are committed to the schedule. As this occurs, the insns in the
251 "Pending" list have their dependencies satisfied and move to either
252 the "Ready" list or the "Queued" set depending on whether
253 sufficient time has passed to make them ready. As time passes,
254 insns move from the "Queued" set to the "Ready" list.
256 The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
257 unscheduled insns, i.e., those that are ready, queued, and pending.
258 The "Queued" set (Q) is implemented by the variable `insn_queue'.
259 The "Ready" list (R) is implemented by the variables `ready' and
261 The "Scheduled" list (S) is the new insn chain built by this pass.
263 The transition (R->S) is implemented in the scheduling loop in
264 `schedule_block' when the best insn to schedule is chosen.
265 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
266 insns move from the ready list to the scheduled list.
267 The transition (Q->R) is implemented in 'queue_to_insn' as time
268 passes or stalls are introduced. */
270 /* Implement a circular buffer to delay instructions until sufficient
271 time has passed. For the new pipeline description interface,
272 MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
273 than maximal time of instruction execution computed by genattr.c on
274 the base maximal time of functional unit reservations and getting a
275 result. This is the longest time an insn may be queued. */
277 static rtx *insn_queue;
278 static int q_ptr = 0;
279 static int q_size = 0;
280 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
281 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
283 #define QUEUE_SCHEDULED (-3)
284 #define QUEUE_NOWHERE (-2)
285 #define QUEUE_READY (-1)
286 /* QUEUE_SCHEDULED - INSN is scheduled.
287 QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
289 QUEUE_READY - INSN is in ready list.
290 N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
292 #define QUEUE_INDEX(INSN) (h_i_d[INSN_UID (INSN)].queue_index)
294 /* The following variable value refers for all current and future
295 reservations of the processor units. */
298 /* The following variable value is size of memory representing all
299 current and future reservations of the processor units. */
300 static size_t dfa_state_size;
302 /* The following array is used to find the best insn from ready when
303 the automaton pipeline interface is used. */
304 static char *ready_try;
306 /* Describe the ready list of the scheduler.
307 VEC holds space enough for all insns in the current region. VECLEN
308 says how many exactly.
309 FIRST is the index of the element with the highest priority; i.e. the
310 last one in the ready list, since elements are ordered by ascending
312 N_READY determines how many insns are on the ready list. */
322 /* The pointer to the ready list. */
323 static struct ready_list *readyp;
325 /* Scheduling clock. */
326 static int clock_var;
328 /* Number of instructions in current scheduling region. */
329 static int rgn_n_insns;
331 static int may_trap_exp (const_rtx, int);
333 /* Nonzero iff the address is comprised from at most 1 register. */
334 #define CONST_BASED_ADDRESS_P(x) \
336 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
337 || (GET_CODE (x) == LO_SUM)) \
338 && (CONSTANT_P (XEXP (x, 0)) \
339 || CONSTANT_P (XEXP (x, 1)))))
341 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
342 as found by analyzing insn's expression. */
345 may_trap_exp (const_rtx x, int is_store)
354 if (code == MEM && may_trap_p (x))
361 /* The insn uses memory: a volatile load. */
362 if (MEM_VOLATILE_P (x))
364 /* An exception-free load. */
367 /* A load with 1 base register, to be further checked. */
368 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
369 return PFREE_CANDIDATE;
370 /* No info on the load, to be further checked. */
371 return PRISKY_CANDIDATE;
376 int i, insn_class = TRAP_FREE;
378 /* Neither store nor load, check if it may cause a trap. */
381 /* Recursive step: walk the insn... */
382 fmt = GET_RTX_FORMAT (code);
383 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
387 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
388 insn_class = WORST_CLASS (insn_class, tmp_class);
390 else if (fmt[i] == 'E')
393 for (j = 0; j < XVECLEN (x, i); j++)
395 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
396 insn_class = WORST_CLASS (insn_class, tmp_class);
397 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
401 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
408 /* Classifies insn for the purpose of verifying that it can be
409 moved speculatively, by examining it's patterns, returning:
410 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
411 TRAP_FREE: non-load insn.
412 IFREE: load from a globally safe location.
413 IRISKY: volatile load.
414 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
415 being either PFREE or PRISKY. */
418 haifa_classify_insn (const_rtx insn)
420 rtx pat = PATTERN (insn);
421 int tmp_class = TRAP_FREE;
422 int insn_class = TRAP_FREE;
425 if (GET_CODE (pat) == PARALLEL)
427 int i, len = XVECLEN (pat, 0);
429 for (i = len - 1; i >= 0; i--)
431 code = GET_CODE (XVECEXP (pat, 0, i));
435 /* Test if it is a 'store'. */
436 tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
439 /* Test if it is a store. */
440 tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
441 if (tmp_class == TRAP_RISKY)
443 /* Test if it is a load. */
445 = WORST_CLASS (tmp_class,
446 may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)),
451 tmp_class = TRAP_RISKY;
456 insn_class = WORST_CLASS (insn_class, tmp_class);
457 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
463 code = GET_CODE (pat);
467 /* Test if it is a 'store'. */
468 tmp_class = may_trap_exp (XEXP (pat, 0), 1);
471 /* Test if it is a store. */
472 tmp_class = may_trap_exp (SET_DEST (pat), 1);
473 if (tmp_class == TRAP_RISKY)
475 /* Test if it is a load. */
477 WORST_CLASS (tmp_class,
478 may_trap_exp (SET_SRC (pat), 0));
482 tmp_class = TRAP_RISKY;
486 insn_class = tmp_class;
492 /* A typedef for rtx vector. */
493 typedef VEC(rtx, heap) *rtx_vec_t;
495 /* Forward declarations. */
497 static int priority (rtx);
498 static int rank_for_schedule (const void *, const void *);
499 static void swap_sort (rtx *, int);
500 static void queue_insn (rtx, int);
501 static int schedule_insn (rtx);
502 static int find_set_reg_weight (const_rtx);
503 static void find_insn_reg_weight (basic_block);
504 static void find_insn_reg_weight1 (rtx);
505 static void adjust_priority (rtx);
506 static void advance_one_cycle (void);
508 /* Notes handling mechanism:
509 =========================
510 Generally, NOTES are saved before scheduling and restored after scheduling.
511 The scheduler distinguishes between two types of notes:
513 (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
514 Before scheduling a region, a pointer to the note is added to the insn
515 that follows or precedes it. (This happens as part of the data dependence
516 computation). After scheduling an insn, the pointer contained in it is
517 used for regenerating the corresponding note (in reemit_notes).
519 (2) All other notes (e.g. INSN_DELETED): Before scheduling a block,
520 these notes are put in a list (in rm_other_notes() and
521 unlink_other_notes ()). After scheduling the block, these notes are
522 inserted at the beginning of the block (in schedule_block()). */
524 static rtx unlink_other_notes (rtx, rtx);
525 static void reemit_notes (rtx);
527 static rtx *ready_lastpos (struct ready_list *);
528 static void ready_add (struct ready_list *, rtx, bool);
529 static void ready_sort (struct ready_list *);
530 static rtx ready_remove_first (struct ready_list *);
532 static void queue_to_ready (struct ready_list *);
533 static int early_queue_to_ready (state_t, struct ready_list *);
535 static void debug_ready_list (struct ready_list *);
537 static void move_insn (rtx);
539 /* The following functions are used to implement multi-pass scheduling
540 on the first cycle. */
541 static rtx ready_element (struct ready_list *, int);
542 static rtx ready_remove (struct ready_list *, int);
543 static void ready_remove_insn (rtx);
544 static int max_issue (struct ready_list *, int *, int);
546 static int choose_ready (struct ready_list *, rtx *);
548 static void fix_inter_tick (rtx, rtx);
549 static int fix_tick_ready (rtx);
550 static void change_queue_index (rtx, int);
552 /* The following functions are used to implement scheduling of data/control
553 speculative instructions. */
555 static void extend_h_i_d (void);
556 static void extend_ready (int);
557 static void extend_global (rtx);
558 static void extend_all (rtx);
559 static void init_h_i_d (rtx);
560 static void generate_recovery_code (rtx);
561 static void process_insn_forw_deps_be_in_spec (rtx, rtx, ds_t);
562 static void begin_speculative_block (rtx);
563 static void add_to_speculative_block (rtx);
564 static dw_t dep_weak (ds_t);
565 static edge find_fallthru_edge (basic_block);
566 static void init_before_recovery (void);
567 static basic_block create_recovery_block (void);
568 static void create_check_block_twin (rtx, bool);
569 static void fix_recovery_deps (basic_block);
570 static void change_pattern (rtx, rtx);
571 static int speculate_insn (rtx, ds_t, rtx *);
572 static void dump_new_block_header (int, basic_block, rtx, rtx);
573 static void restore_bb_notes (basic_block);
574 static void extend_bb (void);
575 static void fix_jump_move (rtx);
576 static void move_block_after_check (rtx);
577 static void move_succs (VEC(edge,gc) **, basic_block);
578 static void sched_remove_insn (rtx);
579 static void clear_priorities (rtx, rtx_vec_t *);
580 static void calc_priorities (rtx_vec_t);
581 static void add_jump_dependencies (rtx, rtx);
582 #ifdef ENABLE_CHECKING
583 static int has_edge_p (VEC(edge,gc) *, int);
584 static void check_cfg (rtx, rtx);
585 static void check_sched_flags (void);
588 #endif /* INSN_SCHEDULING */
590 /* Point to state used for the current scheduling pass. */
591 struct sched_info *current_sched_info;
593 #ifndef INSN_SCHEDULING
595 schedule_insns (void)
600 /* Working copy of frontend's sched_info variable. */
601 static struct sched_info current_sched_info_var;
603 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
604 so that insns independent of the last scheduled insn will be preferred
605 over dependent instructions. */
607 static rtx last_scheduled_insn;
609 /* Cached cost of the instruction. Use below function to get cost of the
610 insn. -1 here means that the field is not initialized. */
611 #define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost)
613 /* Compute cost of executing INSN.
614 This is the number of cycles between instruction issue and
615 instruction results. */
619 int cost = INSN_COST (insn);
623 /* A USE insn, or something else we don't need to
624 understand. We can't pass these directly to
625 result_ready_cost or insn_default_latency because it will
626 trigger a fatal error for unrecognizable insns. */
627 if (recog_memoized (insn) < 0)
629 INSN_COST (insn) = 0;
634 cost = insn_default_latency (insn);
638 INSN_COST (insn) = cost;
645 /* Compute cost of dependence LINK.
646 This is the number of cycles between instruction issue and
647 instruction results. */
649 dep_cost (dep_t link)
651 rtx used = DEP_CON (link);
654 /* A USE insn should never require the value used to be computed.
655 This allows the computation of a function's result and parameter
656 values to overlap the return and call. */
657 if (recog_memoized (used) < 0)
661 rtx insn = DEP_PRO (link);
662 enum reg_note dep_type = DEP_TYPE (link);
664 cost = insn_cost (insn);
666 if (INSN_CODE (insn) >= 0)
668 if (dep_type == REG_DEP_ANTI)
670 else if (dep_type == REG_DEP_OUTPUT)
672 cost = (insn_default_latency (insn)
673 - insn_default_latency (used));
677 else if (bypass_p (insn))
678 cost = insn_latency (insn, used);
681 if (targetm.sched.adjust_cost != NULL)
683 /* This variable is used for backward compatibility with the
685 rtx dep_cost_rtx_link = alloc_INSN_LIST (NULL_RTX, NULL_RTX);
687 /* Make it self-cycled, so that if some tries to walk over this
688 incomplete list he/she will be caught in an endless loop. */
689 XEXP (dep_cost_rtx_link, 1) = dep_cost_rtx_link;
691 /* Targets use only REG_NOTE_KIND of the link. */
692 PUT_REG_NOTE_KIND (dep_cost_rtx_link, DEP_TYPE (link));
694 cost = targetm.sched.adjust_cost (used, dep_cost_rtx_link,
697 free_INSN_LIST_node (dep_cost_rtx_link);
707 /* Return 'true' if DEP should be included in priority calculations. */
709 contributes_to_priority_p (dep_t dep)
711 /* Critical path is meaningful in block boundaries only. */
712 if (!current_sched_info->contributes_to_priority (DEP_CON (dep),
716 /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
717 then speculative instructions will less likely be
718 scheduled. That is because the priority of
719 their producers will increase, and, thus, the
720 producers will more likely be scheduled, thus,
721 resolving the dependence. */
722 if ((current_sched_info->flags & DO_SPECULATION)
723 && !(spec_info->flags & COUNT_SPEC_IN_CRITICAL_PATH)
724 && (DEP_STATUS (dep) & SPECULATIVE))
730 /* Compute the priority number for INSN. */
737 /* We should not be interested in priority of an already scheduled insn. */
738 gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
740 if (!INSN_PRIORITY_KNOWN (insn))
742 int this_priority = 0;
744 if (sd_lists_empty_p (insn, SD_LIST_FORW))
745 /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
746 some forward deps but all of them are ignored by
747 contributes_to_priority hook. At the moment we set priority of
749 this_priority = insn_cost (insn);
752 rtx prev_first, twin;
755 /* For recovery check instructions we calculate priority slightly
756 different than that of normal instructions. Instead of walking
757 through INSN_FORW_DEPS (check) list, we walk through
758 INSN_FORW_DEPS list of each instruction in the corresponding
761 rec = RECOVERY_BLOCK (insn);
762 if (!rec || rec == EXIT_BLOCK_PTR)
764 prev_first = PREV_INSN (insn);
769 prev_first = NEXT_INSN (BB_HEAD (rec));
770 twin = PREV_INSN (BB_END (rec));
775 sd_iterator_def sd_it;
778 FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep)
783 next = DEP_CON (dep);
785 if (BLOCK_FOR_INSN (next) != rec)
789 if (!contributes_to_priority_p (dep))
793 cost = dep_cost (dep);
796 struct _dep _dep1, *dep1 = &_dep1;
798 init_dep (dep1, insn, next, REG_DEP_ANTI);
800 cost = dep_cost (dep1);
803 next_priority = cost + priority (next);
805 if (next_priority > this_priority)
806 this_priority = next_priority;
810 twin = PREV_INSN (twin);
812 while (twin != prev_first);
814 INSN_PRIORITY (insn) = this_priority;
815 INSN_PRIORITY_STATUS (insn) = 1;
818 return INSN_PRIORITY (insn);
821 /* Macros and functions for keeping the priority queue sorted, and
822 dealing with queuing and dequeuing of instructions. */
824 #define SCHED_SORT(READY, N_READY) \
825 do { if ((N_READY) == 2) \
826 swap_sort (READY, N_READY); \
827 else if ((N_READY) > 2) \
828 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
831 /* Returns a positive value if x is preferred; returns a negative value if
832 y is preferred. Should never return 0, since that will make the sort
836 rank_for_schedule (const void *x, const void *y)
838 rtx tmp = *(const rtx *) y;
839 rtx tmp2 = *(const rtx *) x;
840 int tmp_class, tmp2_class;
841 int val, priority_val, weight_val, info_val;
843 /* The insn in a schedule group should be issued the first. */
844 if (SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
845 return SCHED_GROUP_P (tmp2) ? 1 : -1;
847 /* Make sure that priority of TMP and TMP2 are initialized. */
848 gcc_assert (INSN_PRIORITY_KNOWN (tmp) && INSN_PRIORITY_KNOWN (tmp2));
850 /* Prefer insn with higher priority. */
851 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
856 /* Prefer speculative insn with greater dependencies weakness. */
863 ds1 = TODO_SPEC (tmp) & SPECULATIVE;
865 dw1 = dep_weak (ds1);
869 ds2 = TODO_SPEC (tmp2) & SPECULATIVE;
871 dw2 = dep_weak (ds2);
876 if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8))
880 /* Prefer an insn with smaller contribution to registers-pressure. */
881 if (!reload_completed &&
882 (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
885 info_val = (*current_sched_info->rank) (tmp, tmp2);
889 /* Compare insns based on their relation to the last-scheduled-insn. */
890 if (INSN_P (last_scheduled_insn))
895 /* Classify the instructions into three classes:
896 1) Data dependent on last schedule insn.
897 2) Anti/Output dependent on last scheduled insn.
898 3) Independent of last scheduled insn, or has latency of one.
899 Choose the insn from the highest numbered class if different. */
900 dep1 = sd_find_dep_between (last_scheduled_insn, tmp, true);
902 if (dep1 == NULL || dep_cost (dep1) == 1)
904 else if (/* Data dependence. */
905 DEP_TYPE (dep1) == REG_DEP_TRUE)
910 dep2 = sd_find_dep_between (last_scheduled_insn, tmp2, true);
912 if (dep2 == NULL || dep_cost (dep2) == 1)
914 else if (/* Data dependence. */
915 DEP_TYPE (dep2) == REG_DEP_TRUE)
920 if ((val = tmp2_class - tmp_class))
924 /* Prefer the insn which has more later insns that depend on it.
925 This gives the scheduler more freedom when scheduling later
926 instructions at the expense of added register pressure. */
928 val = (sd_lists_size (tmp2, SD_LIST_FORW)
929 - sd_lists_size (tmp, SD_LIST_FORW));
934 /* If insns are equally good, sort by INSN_LUID (original insn order),
935 so that we make the sort stable. This minimizes instruction movement,
936 thus minimizing sched's effect on debugging and cross-jumping. */
937 return INSN_LUID (tmp) - INSN_LUID (tmp2);
940 /* Resort the array A in which only element at index N may be out of order. */
942 HAIFA_INLINE static void
943 swap_sort (rtx *a, int n)
948 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
956 /* Add INSN to the insn queue so that it can be executed at least
957 N_CYCLES after the currently executing insn. Preserve insns
958 chain for debugging purposes. */
960 HAIFA_INLINE static void
961 queue_insn (rtx insn, int n_cycles)
963 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
964 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
966 gcc_assert (n_cycles <= max_insn_queue_index);
968 insn_queue[next_q] = link;
971 if (sched_verbose >= 2)
973 fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
974 (*current_sched_info->print_insn) (insn, 0));
976 fprintf (sched_dump, "queued for %d cycles.\n", n_cycles);
979 QUEUE_INDEX (insn) = next_q;
982 /* Remove INSN from queue. */
984 queue_remove (rtx insn)
986 gcc_assert (QUEUE_INDEX (insn) >= 0);
987 remove_free_INSN_LIST_elem (insn, &insn_queue[QUEUE_INDEX (insn)]);
989 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
992 /* Return a pointer to the bottom of the ready list, i.e. the insn
993 with the lowest priority. */
995 HAIFA_INLINE static rtx *
996 ready_lastpos (struct ready_list *ready)
998 gcc_assert (ready->n_ready >= 1);
999 return ready->vec + ready->first - ready->n_ready + 1;
1002 /* Add an element INSN to the ready list so that it ends up with the
1003 lowest/highest priority depending on FIRST_P. */
1005 HAIFA_INLINE static void
1006 ready_add (struct ready_list *ready, rtx insn, bool first_p)
1010 if (ready->first == ready->n_ready)
1012 memmove (ready->vec + ready->veclen - ready->n_ready,
1013 ready_lastpos (ready),
1014 ready->n_ready * sizeof (rtx));
1015 ready->first = ready->veclen - 1;
1017 ready->vec[ready->first - ready->n_ready] = insn;
1021 if (ready->first == ready->veclen - 1)
1024 /* ready_lastpos() fails when called with (ready->n_ready == 0). */
1025 memmove (ready->vec + ready->veclen - ready->n_ready - 1,
1026 ready_lastpos (ready),
1027 ready->n_ready * sizeof (rtx));
1028 ready->first = ready->veclen - 2;
1030 ready->vec[++(ready->first)] = insn;
1035 gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY);
1036 QUEUE_INDEX (insn) = QUEUE_READY;
1039 /* Remove the element with the highest priority from the ready list and
1042 HAIFA_INLINE static rtx
1043 ready_remove_first (struct ready_list *ready)
1047 gcc_assert (ready->n_ready);
1048 t = ready->vec[ready->first--];
1050 /* If the queue becomes empty, reset it. */
1051 if (ready->n_ready == 0)
1052 ready->first = ready->veclen - 1;
1054 gcc_assert (QUEUE_INDEX (t) == QUEUE_READY);
1055 QUEUE_INDEX (t) = QUEUE_NOWHERE;
1060 /* The following code implements multi-pass scheduling for the first
1061 cycle. In other words, we will try to choose ready insn which
1062 permits to start maximum number of insns on the same cycle. */
1064 /* Return a pointer to the element INDEX from the ready. INDEX for
1065 insn with the highest priority is 0, and the lowest priority has
1068 HAIFA_INLINE static rtx
1069 ready_element (struct ready_list *ready, int index)
1071 gcc_assert (ready->n_ready && index < ready->n_ready);
1073 return ready->vec[ready->first - index];
1076 /* Remove the element INDEX from the ready list and return it. INDEX
1077 for insn with the highest priority is 0, and the lowest priority
1080 HAIFA_INLINE static rtx
1081 ready_remove (struct ready_list *ready, int index)
1087 return ready_remove_first (ready);
1088 gcc_assert (ready->n_ready && index < ready->n_ready);
1089 t = ready->vec[ready->first - index];
1091 for (i = index; i < ready->n_ready; i++)
1092 ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
1093 QUEUE_INDEX (t) = QUEUE_NOWHERE;
1097 /* Remove INSN from the ready list. */
1099 ready_remove_insn (rtx insn)
1103 for (i = 0; i < readyp->n_ready; i++)
1104 if (ready_element (readyp, i) == insn)
1106 ready_remove (readyp, i);
1112 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
1115 HAIFA_INLINE static void
1116 ready_sort (struct ready_list *ready)
1118 rtx *first = ready_lastpos (ready);
1119 SCHED_SORT (first, ready->n_ready);
1122 /* PREV is an insn that is ready to execute. Adjust its priority if that
1123 will help shorten or lengthen register lifetimes as appropriate. Also
1124 provide a hook for the target to tweek itself. */
1126 HAIFA_INLINE static void
1127 adjust_priority (rtx prev)
1129 /* ??? There used to be code here to try and estimate how an insn
1130 affected register lifetimes, but it did it by looking at REG_DEAD
1131 notes, which we removed in schedule_region. Nor did it try to
1132 take into account register pressure or anything useful like that.
1134 Revisit when we have a machine model to work with and not before. */
1136 if (targetm.sched.adjust_priority)
1137 INSN_PRIORITY (prev) =
1138 targetm.sched.adjust_priority (prev, INSN_PRIORITY (prev));
1141 /* Advance time on one cycle. */
1142 HAIFA_INLINE static void
1143 advance_one_cycle (void)
1145 if (targetm.sched.dfa_pre_advance_cycle)
1146 targetm.sched.dfa_pre_advance_cycle ();
1148 if (targetm.sched.dfa_pre_cycle_insn)
1149 state_transition (curr_state,
1150 targetm.sched.dfa_pre_cycle_insn ());
1152 state_transition (curr_state, NULL);
1154 if (targetm.sched.dfa_post_cycle_insn)
1155 state_transition (curr_state,
1156 targetm.sched.dfa_post_cycle_insn ());
1158 if (targetm.sched.dfa_post_advance_cycle)
1159 targetm.sched.dfa_post_advance_cycle ();
1162 /* Clock at which the previous instruction was issued. */
1163 static int last_clock_var;
1165 /* INSN is the "currently executing insn". Launch each insn which was
1166 waiting on INSN. READY is the ready list which contains the insns
1167 that are ready to fire. CLOCK is the current cycle. The function
1168 returns necessary cycle advance after issuing the insn (it is not
1169 zero for insns in a schedule group). */
1172 schedule_insn (rtx insn)
1174 sd_iterator_def sd_it;
1178 if (sched_verbose >= 1)
1182 print_insn (buf, insn, 0);
1184 fprintf (sched_dump, ";;\t%3i--> %-40s:", clock_var, buf);
1186 if (recog_memoized (insn) < 0)
1187 fprintf (sched_dump, "nothing");
1189 print_reservation (sched_dump, insn);
1190 fputc ('\n', sched_dump);
1193 /* Scheduling instruction should have all its dependencies resolved and
1194 should have been removed from the ready list. */
1195 gcc_assert (sd_lists_empty_p (insn, SD_LIST_BACK));
1197 gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
1198 QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
1200 gcc_assert (INSN_TICK (insn) >= MIN_TICK);
1201 if (INSN_TICK (insn) > clock_var)
1202 /* INSN has been prematurely moved from the queue to the ready list.
1203 This is possible only if following flag is set. */
1204 gcc_assert (flag_sched_stalled_insns);
1206 /* ??? Probably, if INSN is scheduled prematurely, we should leave
1207 INSN_TICK untouched. This is a machine-dependent issue, actually. */
1208 INSN_TICK (insn) = clock_var;
1210 /* Update dependent instructions. */
1211 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
1212 sd_iterator_cond (&sd_it, &dep);)
1214 rtx next = DEP_CON (dep);
1216 /* Resolve the dependence between INSN and NEXT.
1217 sd_resolve_dep () moves current dep to another list thus
1218 advancing the iterator. */
1219 sd_resolve_dep (sd_it);
1221 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn))
1225 effective_cost = try_ready (next);
1227 if (effective_cost >= 0
1228 && SCHED_GROUP_P (next)
1229 && advance < effective_cost)
1230 advance = effective_cost;
1233 /* Check always has only one forward dependence (to the first insn in
1234 the recovery block), therefore, this will be executed only once. */
1236 gcc_assert (sd_lists_empty_p (insn, SD_LIST_FORW));
1237 fix_recovery_deps (RECOVERY_BLOCK (insn));
1241 /* This is the place where scheduler doesn't *basically* need backward and
1242 forward dependencies for INSN anymore. Nevertheless they are used in
1243 heuristics in rank_for_schedule (), early_queue_to_ready () and in
1244 some targets (e.g. rs6000). Thus the earliest place where we *can*
1245 remove dependencies is after targetm.sched.md_finish () call in
1246 schedule_block (). But, on the other side, the safest place to remove
1247 dependencies is when we are finishing scheduling entire region. As we
1248 don't generate [many] dependencies during scheduling itself, we won't
1249 need memory until beginning of next region.
1250 Bottom line: Dependencies are removed for all insns in the end of
1251 scheduling the region. */
1253 /* Annotate the instruction with issue information -- TImode
1254 indicates that the instruction is expected not to be able
1255 to issue on the same cycle as the previous insn. A machine
1256 may use this information to decide how the instruction should
1259 && GET_CODE (PATTERN (insn)) != USE
1260 && GET_CODE (PATTERN (insn)) != CLOBBER)
1262 if (reload_completed)
1263 PUT_MODE (insn, clock_var > last_clock_var ? TImode : VOIDmode);
1264 last_clock_var = clock_var;
1270 /* Functions for handling of notes. */
1272 /* Delete notes beginning with INSN and put them in the chain
1273 of notes ended by NOTE_LIST.
1274 Returns the insn following the notes. */
1277 unlink_other_notes (rtx insn, rtx tail)
1279 rtx prev = PREV_INSN (insn);
1281 while (insn != tail && NOTE_NOT_BB_P (insn))
1283 rtx next = NEXT_INSN (insn);
1284 basic_block bb = BLOCK_FOR_INSN (insn);
1286 /* Delete the note from its current position. */
1288 NEXT_INSN (prev) = next;
1290 PREV_INSN (next) = prev;
1294 /* Basic block can begin with either LABEL or
1295 NOTE_INSN_BASIC_BLOCK. */
1296 gcc_assert (BB_HEAD (bb) != insn);
1298 /* Check if we are removing last insn in the BB. */
1299 if (BB_END (bb) == insn)
1303 /* See sched_analyze to see how these are handled. */
1304 if (NOTE_KIND (insn) != NOTE_INSN_EH_REGION_BEG
1305 && NOTE_KIND (insn) != NOTE_INSN_EH_REGION_END)
1307 /* Insert the note at the end of the notes list. */
1308 PREV_INSN (insn) = note_list;
1310 NEXT_INSN (note_list) = insn;
1319 /* Return the head and tail pointers of ebb starting at BEG and ending
1323 get_ebb_head_tail (basic_block beg, basic_block end, rtx *headp, rtx *tailp)
1325 rtx beg_head = BB_HEAD (beg);
1326 rtx beg_tail = BB_END (beg);
1327 rtx end_head = BB_HEAD (end);
1328 rtx end_tail = BB_END (end);
1330 /* Don't include any notes or labels at the beginning of the BEG
1331 basic block, or notes at the end of the END basic blocks. */
1333 if (LABEL_P (beg_head))
1334 beg_head = NEXT_INSN (beg_head);
1336 while (beg_head != beg_tail)
1337 if (NOTE_P (beg_head))
1338 beg_head = NEXT_INSN (beg_head);
1345 end_head = beg_head;
1346 else if (LABEL_P (end_head))
1347 end_head = NEXT_INSN (end_head);
1349 while (end_head != end_tail)
1350 if (NOTE_P (end_tail))
1351 end_tail = PREV_INSN (end_tail);
1358 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
1361 no_real_insns_p (const_rtx head, const_rtx tail)
1363 while (head != NEXT_INSN (tail))
1365 if (!NOTE_P (head) && !LABEL_P (head))
1367 head = NEXT_INSN (head);
1372 /* Delete notes between HEAD and TAIL and put them in the chain
1373 of notes ended by NOTE_LIST. */
1376 rm_other_notes (rtx head, rtx tail)
1382 if (head == tail && (! INSN_P (head)))
1385 next_tail = NEXT_INSN (tail);
1386 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1390 /* Farm out notes, and maybe save them in NOTE_LIST.
1391 This is needed to keep the debugger from
1392 getting completely deranged. */
1393 if (NOTE_NOT_BB_P (insn))
1397 insn = unlink_other_notes (insn, next_tail);
1399 gcc_assert (prev != tail && prev != head && insn != next_tail);
1404 /* Functions for computation of registers live/usage info. */
1406 /* This function looks for a new register being defined.
1407 If the destination register is already used by the source,
1408 a new register is not needed. */
1411 find_set_reg_weight (const_rtx x)
1413 if (GET_CODE (x) == CLOBBER
1414 && register_operand (SET_DEST (x), VOIDmode))
1416 if (GET_CODE (x) == SET
1417 && register_operand (SET_DEST (x), VOIDmode))
1419 if (REG_P (SET_DEST (x)))
1421 if (!reg_mentioned_p (SET_DEST (x), SET_SRC (x)))
1431 /* Calculate INSN_REG_WEIGHT for all insns of a block. */
1434 find_insn_reg_weight (basic_block bb)
1436 rtx insn, next_tail, head, tail;
1438 get_ebb_head_tail (bb, bb, &head, &tail);
1439 next_tail = NEXT_INSN (tail);
1441 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
1442 find_insn_reg_weight1 (insn);
1445 /* Calculate INSN_REG_WEIGHT for single instruction.
1446 Separated from find_insn_reg_weight because of need
1447 to initialize new instruction in generate_recovery_code. */
1449 find_insn_reg_weight1 (rtx insn)
1454 /* Handle register life information. */
1455 if (! INSN_P (insn))
1458 /* Increment weight for each register born here. */
1460 reg_weight += find_set_reg_weight (x);
1461 if (GET_CODE (x) == PARALLEL)
1464 for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
1466 x = XVECEXP (PATTERN (insn), 0, j);
1467 reg_weight += find_set_reg_weight (x);
1470 /* Decrement weight for each register that dies here. */
1471 for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
1473 if (REG_NOTE_KIND (x) == REG_DEAD
1474 || REG_NOTE_KIND (x) == REG_UNUSED)
1478 INSN_REG_WEIGHT (insn) = reg_weight;
1481 /* Move insns that became ready to fire from queue to ready list. */
1484 queue_to_ready (struct ready_list *ready)
1490 q_ptr = NEXT_Q (q_ptr);
1492 if (dbg_cnt (sched_insn) == false)
1493 /* If debug counter is activated do not requeue insn next after
1494 last_scheduled_insn. */
1495 skip_insn = next_nonnote_insn (last_scheduled_insn);
1497 skip_insn = NULL_RTX;
1499 /* Add all pending insns that can be scheduled without stalls to the
1501 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
1503 insn = XEXP (link, 0);
1506 if (sched_verbose >= 2)
1507 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
1508 (*current_sched_info->print_insn) (insn, 0));
1510 /* If the ready list is full, delay the insn for 1 cycle.
1511 See the comment in schedule_block for the rationale. */
1512 if (!reload_completed
1513 && ready->n_ready > MAX_SCHED_READY_INSNS
1514 && !SCHED_GROUP_P (insn)
1515 && insn != skip_insn)
1517 if (sched_verbose >= 2)
1518 fprintf (sched_dump, "requeued because ready full\n");
1519 queue_insn (insn, 1);
1523 ready_add (ready, insn, false);
1524 if (sched_verbose >= 2)
1525 fprintf (sched_dump, "moving to ready without stalls\n");
1528 free_INSN_LIST_list (&insn_queue[q_ptr]);
1530 /* If there are no ready insns, stall until one is ready and add all
1531 of the pending insns at that point to the ready list. */
1532 if (ready->n_ready == 0)
1536 for (stalls = 1; stalls <= max_insn_queue_index; stalls++)
1538 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
1540 for (; link; link = XEXP (link, 1))
1542 insn = XEXP (link, 0);
1545 if (sched_verbose >= 2)
1546 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
1547 (*current_sched_info->print_insn) (insn, 0));
1549 ready_add (ready, insn, false);
1550 if (sched_verbose >= 2)
1551 fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
1553 free_INSN_LIST_list (&insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]);
1555 advance_one_cycle ();
1560 advance_one_cycle ();
1563 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
1564 clock_var += stalls;
1568 /* Used by early_queue_to_ready. Determines whether it is "ok" to
1569 prematurely move INSN from the queue to the ready list. Currently,
1570 if a target defines the hook 'is_costly_dependence', this function
1571 uses the hook to check whether there exist any dependences which are
1572 considered costly by the target, between INSN and other insns that
1573 have already been scheduled. Dependences are checked up to Y cycles
1574 back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
1575 controlling this value.
1576 (Other considerations could be taken into account instead (or in
1577 addition) depending on user flags and target hooks. */
1580 ok_for_early_queue_removal (rtx insn)
1583 rtx prev_insn = last_scheduled_insn;
1585 if (targetm.sched.is_costly_dependence)
1587 for (n_cycles = flag_sched_stalled_insns_dep; n_cycles; n_cycles--)
1589 for ( ; prev_insn; prev_insn = PREV_INSN (prev_insn))
1593 if (prev_insn == current_sched_info->prev_head)
1599 if (!NOTE_P (prev_insn))
1603 dep = sd_find_dep_between (prev_insn, insn, true);
1607 cost = dep_cost (dep);
1609 if (targetm.sched.is_costly_dependence (dep, cost,
1610 flag_sched_stalled_insns_dep - n_cycles))
1615 if (GET_MODE (prev_insn) == TImode) /* end of dispatch group */
1621 prev_insn = PREV_INSN (prev_insn);
1629 /* Remove insns from the queue, before they become "ready" with respect
1630 to FU latency considerations. */
1633 early_queue_to_ready (state_t state, struct ready_list *ready)
1641 state_t temp_state = alloca (dfa_state_size);
1643 int insns_removed = 0;
1646 Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
1649 X == 0: There is no limit on how many queued insns can be removed
1650 prematurely. (flag_sched_stalled_insns = -1).
1652 X >= 1: Only X queued insns can be removed prematurely in each
1653 invocation. (flag_sched_stalled_insns = X).
1655 Otherwise: Early queue removal is disabled.
1656 (flag_sched_stalled_insns = 0)
1659 if (! flag_sched_stalled_insns)
1662 for (stalls = 0; stalls <= max_insn_queue_index; stalls++)
1664 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
1666 if (sched_verbose > 6)
1667 fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls);
1672 next_link = XEXP (link, 1);
1673 insn = XEXP (link, 0);
1674 if (insn && sched_verbose > 6)
1675 print_rtl_single (sched_dump, insn);
1677 memcpy (temp_state, state, dfa_state_size);
1678 if (recog_memoized (insn) < 0)
1679 /* non-negative to indicate that it's not ready
1680 to avoid infinite Q->R->Q->R... */
1683 cost = state_transition (temp_state, insn);
1685 if (sched_verbose >= 6)
1686 fprintf (sched_dump, "transition cost = %d\n", cost);
1688 move_to_ready = false;
1691 move_to_ready = ok_for_early_queue_removal (insn);
1692 if (move_to_ready == true)
1694 /* move from Q to R */
1696 ready_add (ready, insn, false);
1699 XEXP (prev_link, 1) = next_link;
1701 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link;
1703 free_INSN_LIST_node (link);
1705 if (sched_verbose >= 2)
1706 fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n",
1707 (*current_sched_info->print_insn) (insn, 0));
1710 if (insns_removed == flag_sched_stalled_insns)
1711 /* Remove no more than flag_sched_stalled_insns insns
1712 from Q at a time. */
1713 return insns_removed;
1717 if (move_to_ready == false)
1724 } /* for stalls.. */
1726 return insns_removed;
1730 /* Print the ready list for debugging purposes. Callable from debugger. */
1733 debug_ready_list (struct ready_list *ready)
1738 if (ready->n_ready == 0)
1740 fprintf (sched_dump, "\n");
1744 p = ready_lastpos (ready);
1745 for (i = 0; i < ready->n_ready; i++)
1746 fprintf (sched_dump, " %s", (*current_sched_info->print_insn) (p[i], 0));
1747 fprintf (sched_dump, "\n");
1750 /* Search INSN for REG_SAVE_NOTE note pairs for
1751 NOTE_INSN_EHREGION_{BEG,END}; and convert them back into
1752 NOTEs. The REG_SAVE_NOTE note following first one is contains the
1753 saved value for NOTE_BLOCK_NUMBER which is useful for
1754 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. */
1757 reemit_notes (rtx insn)
1759 rtx note, last = insn;
1761 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1763 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
1765 enum insn_note note_type = INTVAL (XEXP (note, 0));
1767 last = emit_note_before (note_type, last);
1768 remove_note (insn, note);
1773 /* Move INSN. Reemit notes if needed. Update CFG, if needed. */
1775 move_insn (rtx insn)
1777 rtx last = last_scheduled_insn;
1779 if (PREV_INSN (insn) != last)
1785 bb = BLOCK_FOR_INSN (insn);
1787 /* BB_HEAD is either LABEL or NOTE. */
1788 gcc_assert (BB_HEAD (bb) != insn);
1790 if (BB_END (bb) == insn)
1791 /* If this is last instruction in BB, move end marker one
1794 /* Jumps are always placed at the end of basic block. */
1795 jump_p = control_flow_insn_p (insn);
1798 || ((current_sched_info->flags & SCHED_RGN)
1799 && IS_SPECULATION_BRANCHY_CHECK_P (insn))
1800 || (current_sched_info->flags & SCHED_EBB));
1802 gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn)) == bb);
1804 BB_END (bb) = PREV_INSN (insn);
1807 gcc_assert (BB_END (bb) != last);
1810 /* We move the block note along with jump. */
1812 /* NT is needed for assertion below. */
1813 rtx nt = current_sched_info->next_tail;
1815 note = NEXT_INSN (insn);
1816 while (NOTE_NOT_BB_P (note) && note != nt)
1817 note = NEXT_INSN (note);
1821 || BARRIER_P (note)))
1822 note = NEXT_INSN (note);
1824 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
1829 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (note);
1830 PREV_INSN (NEXT_INSN (note)) = PREV_INSN (insn);
1832 NEXT_INSN (note) = NEXT_INSN (last);
1833 PREV_INSN (NEXT_INSN (last)) = note;
1835 NEXT_INSN (last) = insn;
1836 PREV_INSN (insn) = last;
1838 bb = BLOCK_FOR_INSN (last);
1842 fix_jump_move (insn);
1844 if (BLOCK_FOR_INSN (insn) != bb)
1845 move_block_after_check (insn);
1847 gcc_assert (BB_END (bb) == last);
1850 set_block_for_insn (insn, bb);
1851 df_insn_change_bb (insn);
1853 /* Update BB_END, if needed. */
1854 if (BB_END (bb) == last)
1858 reemit_notes (insn);
1860 SCHED_GROUP_P (insn) = 0;
1863 /* The following structure describe an entry of the stack of choices. */
1866 /* Ordinal number of the issued insn in the ready queue. */
1868 /* The number of the rest insns whose issues we should try. */
1870 /* The number of issued essential insns. */
1872 /* State after issuing the insn. */
1876 /* The following array is used to implement a stack of choices used in
1877 function max_issue. */
1878 static struct choice_entry *choice_stack;
1880 /* The following variable value is number of essential insns issued on
1881 the current cycle. An insn is essential one if it changes the
1882 processors state. */
1883 static int cycle_issued_insns;
1885 /* The following variable value is maximal number of tries of issuing
1886 insns for the first cycle multipass insn scheduling. We define
1887 this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
1888 need this constraint if all real insns (with non-negative codes)
1889 had reservations because in this case the algorithm complexity is
1890 O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
1891 might be incomplete and such insn might occur. For such
1892 descriptions, the complexity of algorithm (without the constraint)
1893 could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
1894 static int max_lookahead_tries;
1896 /* The following value is value of hook
1897 `first_cycle_multipass_dfa_lookahead' at the last call of
1899 static int cached_first_cycle_multipass_dfa_lookahead = 0;
1901 /* The following value is value of `issue_rate' at the last call of
1903 static int cached_issue_rate = 0;
1905 /* The following function returns maximal (or close to maximal) number
1906 of insns which can be issued on the same cycle and one of which
1907 insns is insns with the best rank (the first insn in READY). To
1908 make this function tries different samples of ready insns. READY
1909 is current queue `ready'. Global array READY_TRY reflects what
1910 insns are already issued in this try. MAX_POINTS is the sum of points
1911 of all instructions in READY. The function stops immediately,
1912 if it reached the such a solution, that all instruction can be issued.
1913 INDEX will contain index of the best insn in READY. The following
1914 function is used only for first cycle multipass scheduling. */
1916 max_issue (struct ready_list *ready, int *index, int max_points)
1918 int n, i, all, n_ready, best, delay, tries_num, points = -1;
1919 struct choice_entry *top;
1923 memcpy (choice_stack->state, curr_state, dfa_state_size);
1925 top->rest = cached_first_cycle_multipass_dfa_lookahead;
1927 n_ready = ready->n_ready;
1928 for (all = i = 0; i < n_ready; i++)
1935 if (top->rest == 0 || i >= n_ready)
1937 if (top == choice_stack)
1939 if (best < top - choice_stack && ready_try [0])
1941 best = top - choice_stack;
1942 *index = choice_stack [1].index;
1944 if (top->n == max_points || best == all)
1950 memcpy (curr_state, top->state, dfa_state_size);
1952 else if (!ready_try [i])
1955 if (tries_num > max_lookahead_tries)
1957 insn = ready_element (ready, i);
1958 delay = state_transition (curr_state, insn);
1961 if (state_dead_lock_p (curr_state))
1966 if (memcmp (top->state, curr_state, dfa_state_size) != 0)
1967 n += ISSUE_POINTS (insn);
1969 top->rest = cached_first_cycle_multipass_dfa_lookahead;
1972 memcpy (top->state, curr_state, dfa_state_size);
1979 while (top != choice_stack)
1981 ready_try [top->index] = 0;
1984 memcpy (curr_state, choice_stack->state, dfa_state_size);
1986 if (sched_verbose >= 4)
1987 fprintf (sched_dump, ";;\t\tChoosed insn : %s; points: %d/%d\n",
1988 (*current_sched_info->print_insn) (ready_element (ready, *index),
1990 points, max_points);
1995 /* The following function chooses insn from READY and modifies
1996 *N_READY and READY. The following function is used only for first
1997 cycle multipass scheduling.
1999 -1 if cycle should be advanced,
2000 0 if INSN_PTR is set to point to the desirable insn,
2001 1 if choose_ready () should be restarted without advancing the cycle. */
2003 choose_ready (struct ready_list *ready, rtx *insn_ptr)
2007 if (dbg_cnt (sched_insn) == false)
2011 insn = next_nonnote_insn (last_scheduled_insn);
2013 if (QUEUE_INDEX (insn) == QUEUE_READY)
2014 /* INSN is in the ready_list. */
2016 ready_remove_insn (insn);
2021 /* INSN is in the queue. Advance cycle to move it to the ready list. */
2027 if (targetm.sched.first_cycle_multipass_dfa_lookahead)
2028 lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead ();
2029 if (lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0)))
2031 *insn_ptr = ready_remove_first (ready);
2036 /* Try to choose the better insn. */
2037 int index = 0, i, n;
2039 int more_issue, max_points, try_data = 1, try_control = 1;
2041 if (cached_first_cycle_multipass_dfa_lookahead != lookahead)
2043 cached_first_cycle_multipass_dfa_lookahead = lookahead;
2044 max_lookahead_tries = 100;
2045 for (i = 0; i < issue_rate; i++)
2046 max_lookahead_tries *= lookahead;
2048 insn = ready_element (ready, 0);
2049 if (INSN_CODE (insn) < 0)
2051 *insn_ptr = ready_remove_first (ready);
2056 && spec_info->flags & (PREFER_NON_DATA_SPEC
2057 | PREFER_NON_CONTROL_SPEC))
2059 for (i = 0, n = ready->n_ready; i < n; i++)
2064 x = ready_element (ready, i);
2067 if (spec_info->flags & PREFER_NON_DATA_SPEC
2068 && !(s & DATA_SPEC))
2071 if (!(spec_info->flags & PREFER_NON_CONTROL_SPEC)
2076 if (spec_info->flags & PREFER_NON_CONTROL_SPEC
2077 && !(s & CONTROL_SPEC))
2080 if (!(spec_info->flags & PREFER_NON_DATA_SPEC) || !try_data)
2086 if ((!try_data && (TODO_SPEC (insn) & DATA_SPEC))
2087 || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC))
2088 || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec
2089 && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec
2091 /* Discard speculative instruction that stands first in the ready
2094 change_queue_index (insn, 1);
2098 max_points = ISSUE_POINTS (insn);
2099 more_issue = issue_rate - cycle_issued_insns - 1;
2101 for (i = 1; i < ready->n_ready; i++)
2103 insn = ready_element (ready, i);
2105 = (INSN_CODE (insn) < 0
2106 || (!try_data && (TODO_SPEC (insn) & DATA_SPEC))
2107 || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC))
2108 || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard
2109 && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard
2112 if (!ready_try [i] && more_issue-- > 0)
2113 max_points += ISSUE_POINTS (insn);
2116 if (max_issue (ready, &index, max_points) == 0)
2118 *insn_ptr = ready_remove_first (ready);
2123 *insn_ptr = ready_remove (ready, index);
2129 /* Use forward list scheduling to rearrange insns of block pointed to by
2130 TARGET_BB, possibly bringing insns from subsequent blocks in the same
2134 schedule_block (basic_block *target_bb, int rgn_n_insns1)
2136 struct ready_list ready;
2137 int i, first_cycle_insn_p;
2139 state_t temp_state = NULL; /* It is used for multipass scheduling. */
2140 int sort_p, advance, start_clock_var;
2142 /* Head/tail info for this block. */
2143 rtx prev_head = current_sched_info->prev_head;
2144 rtx next_tail = current_sched_info->next_tail;
2145 rtx head = NEXT_INSN (prev_head);
2146 rtx tail = PREV_INSN (next_tail);
2148 /* We used to have code to avoid getting parameters moved from hard
2149 argument registers into pseudos.
2151 However, it was removed when it proved to be of marginal benefit
2152 and caused problems because schedule_block and compute_forward_dependences
2153 had different notions of what the "head" insn was. */
2155 gcc_assert (head != tail || INSN_P (head));
2157 haifa_recovery_bb_recently_added_p = false;
2161 dump_new_block_header (0, *target_bb, head, tail);
2163 state_reset (curr_state);
2165 /* Allocate the ready list. */
2169 choice_stack = NULL;
2172 extend_ready (rgn_n_insns1 + 1);
2174 ready.first = ready.veclen - 1;
2177 /* It is used for first cycle multipass scheduling. */
2178 temp_state = alloca (dfa_state_size);
2180 if (targetm.sched.md_init)
2181 targetm.sched.md_init (sched_dump, sched_verbose, ready.veclen);
2183 /* We start inserting insns after PREV_HEAD. */
2184 last_scheduled_insn = prev_head;
2186 gcc_assert (NOTE_P (last_scheduled_insn)
2187 && BLOCK_FOR_INSN (last_scheduled_insn) == *target_bb);
2189 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
2194 insn_queue = alloca ((max_insn_queue_index + 1) * sizeof (rtx));
2195 memset (insn_queue, 0, (max_insn_queue_index + 1) * sizeof (rtx));
2197 /* Start just before the beginning of time. */
2200 /* We need queue and ready lists and clock_var be initialized
2201 in try_ready () (which is called through init_ready_list ()). */
2202 (*current_sched_info->init_ready_list) ();
2204 /* The algorithm is O(n^2) in the number of ready insns at any given
2205 time in the worst case. Before reload we are more likely to have
2206 big lists so truncate them to a reasonable size. */
2207 if (!reload_completed && ready.n_ready > MAX_SCHED_READY_INSNS)
2209 ready_sort (&ready);
2211 /* Find first free-standing insn past MAX_SCHED_READY_INSNS. */
2212 for (i = MAX_SCHED_READY_INSNS; i < ready.n_ready; i++)
2213 if (!SCHED_GROUP_P (ready_element (&ready, i)))
2216 if (sched_verbose >= 2)
2218 fprintf (sched_dump,
2219 ";;\t\tReady list on entry: %d insns\n", ready.n_ready);
2220 fprintf (sched_dump,
2221 ";;\t\t before reload => truncated to %d insns\n", i);
2224 /* Delay all insns past it for 1 cycle. If debug counter is
2225 activated make an exception for the insn right after
2226 last_scheduled_insn. */
2230 if (dbg_cnt (sched_insn) == false)
2231 skip_insn = next_nonnote_insn (last_scheduled_insn);
2233 skip_insn = NULL_RTX;
2235 while (i < ready.n_ready)
2239 insn = ready_remove (&ready, i);
2241 if (insn != skip_insn)
2242 queue_insn (insn, 1);
2247 /* Now we can restore basic block notes and maintain precise cfg. */
2248 restore_bb_notes (*target_bb);
2250 last_clock_var = -1;
2255 /* Loop until all the insns in BB are scheduled. */
2256 while ((*current_sched_info->schedule_more_p) ())
2260 start_clock_var = clock_var;
2264 advance_one_cycle ();
2266 /* Add to the ready list all pending insns that can be issued now.
2267 If there are no ready insns, increment clock until one
2268 is ready and add all pending insns at that point to the ready
2270 queue_to_ready (&ready);
2272 gcc_assert (ready.n_ready);
2274 if (sched_verbose >= 2)
2276 fprintf (sched_dump, ";;\t\tReady list after queue_to_ready: ");
2277 debug_ready_list (&ready);
2279 advance -= clock_var - start_clock_var;
2281 while (advance > 0);
2285 /* Sort the ready list based on priority. */
2286 ready_sort (&ready);
2288 if (sched_verbose >= 2)
2290 fprintf (sched_dump, ";;\t\tReady list after ready_sort: ");
2291 debug_ready_list (&ready);
2295 /* Allow the target to reorder the list, typically for
2296 better instruction bundling. */
2297 if (sort_p && targetm.sched.reorder
2298 && (ready.n_ready == 0
2299 || !SCHED_GROUP_P (ready_element (&ready, 0))))
2301 targetm.sched.reorder (sched_dump, sched_verbose,
2302 ready_lastpos (&ready),
2303 &ready.n_ready, clock_var);
2305 can_issue_more = issue_rate;
2307 first_cycle_insn_p = 1;
2308 cycle_issued_insns = 0;
2315 if (sched_verbose >= 2)
2317 fprintf (sched_dump, ";;\tReady list (t = %3d): ",
2319 debug_ready_list (&ready);
2322 if (ready.n_ready == 0
2324 && reload_completed)
2326 /* Allow scheduling insns directly from the queue in case
2327 there's nothing better to do (ready list is empty) but
2328 there are still vacant dispatch slots in the current cycle. */
2329 if (sched_verbose >= 6)
2330 fprintf (sched_dump,";;\t\tSecond chance\n");
2331 memcpy (temp_state, curr_state, dfa_state_size);
2332 if (early_queue_to_ready (temp_state, &ready))
2333 ready_sort (&ready);
2336 if (ready.n_ready == 0 || !can_issue_more
2337 || state_dead_lock_p (curr_state)
2338 || !(*current_sched_info->schedule_more_p) ())
2341 /* Select and remove the insn from the ready list. */
2347 res = choose_ready (&ready, &insn);
2353 /* Restart choose_ready (). */
2356 gcc_assert (insn != NULL_RTX);
2359 insn = ready_remove_first (&ready);
2361 if (targetm.sched.dfa_new_cycle
2362 && targetm.sched.dfa_new_cycle (sched_dump, sched_verbose,
2363 insn, last_clock_var,
2364 clock_var, &sort_p))
2365 /* SORT_P is used by the target to override sorting
2366 of the ready list. This is needed when the target
2367 has modified its internal structures expecting that
2368 the insn will be issued next. As we need the insn
2369 to have the highest priority (so it will be returned by
2370 the ready_remove_first call above), we invoke
2371 ready_add (&ready, insn, true).
2372 But, still, there is one issue: INSN can be later
2373 discarded by scheduler's front end through
2374 current_sched_info->can_schedule_ready_p, hence, won't
2377 ready_add (&ready, insn, true);
2382 memcpy (temp_state, curr_state, dfa_state_size);
2383 if (recog_memoized (insn) < 0)
2385 asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT
2386 || asm_noperands (PATTERN (insn)) >= 0);
2387 if (!first_cycle_insn_p && asm_p)
2388 /* This is asm insn which is tryed to be issued on the
2389 cycle not first. Issue it on the next cycle. */
2392 /* A USE insn, or something else we don't need to
2393 understand. We can't pass these directly to
2394 state_transition because it will trigger a
2395 fatal error for unrecognizable insns. */
2400 cost = state_transition (temp_state, insn);
2409 queue_insn (insn, cost);
2410 if (SCHED_GROUP_P (insn))
2419 if (current_sched_info->can_schedule_ready_p
2420 && ! (*current_sched_info->can_schedule_ready_p) (insn))
2421 /* We normally get here only if we don't want to move
2422 insn from the split block. */
2424 TODO_SPEC (insn) = (TODO_SPEC (insn) & ~SPECULATIVE) | HARD_DEP;
2428 /* DECISION is made. */
2430 if (TODO_SPEC (insn) & SPECULATIVE)
2431 generate_recovery_code (insn);
2433 if (control_flow_insn_p (last_scheduled_insn)
2434 /* This is used to switch basic blocks by request
2435 from scheduler front-end (actually, sched-ebb.c only).
2436 This is used to process blocks with single fallthru
2437 edge. If succeeding block has jump, it [jump] will try
2438 move at the end of current bb, thus corrupting CFG. */
2439 || current_sched_info->advance_target_bb (*target_bb, insn))
2441 *target_bb = current_sched_info->advance_target_bb
2448 x = next_real_insn (last_scheduled_insn);
2450 dump_new_block_header (1, *target_bb, x, tail);
2453 last_scheduled_insn = bb_note (*target_bb);
2456 /* Update counters, etc in the scheduler's front end. */
2457 (*current_sched_info->begin_schedule_ready) (insn,
2458 last_scheduled_insn);
2461 last_scheduled_insn = insn;
2463 if (memcmp (curr_state, temp_state, dfa_state_size) != 0)
2465 cycle_issued_insns++;
2466 memcpy (curr_state, temp_state, dfa_state_size);
2469 if (targetm.sched.variable_issue)
2471 targetm.sched.variable_issue (sched_dump, sched_verbose,
2472 insn, can_issue_more);
2473 /* A naked CLOBBER or USE generates no instruction, so do
2474 not count them against the issue rate. */
2475 else if (GET_CODE (PATTERN (insn)) != USE
2476 && GET_CODE (PATTERN (insn)) != CLOBBER)
2479 advance = schedule_insn (insn);
2481 /* After issuing an asm insn we should start a new cycle. */
2482 if (advance == 0 && asm_p)
2487 first_cycle_insn_p = 0;
2489 /* Sort the ready list based on priority. This must be
2490 redone here, as schedule_insn may have readied additional
2491 insns that will not be sorted correctly. */
2492 if (ready.n_ready > 0)
2493 ready_sort (&ready);
2495 if (targetm.sched.reorder2
2496 && (ready.n_ready == 0
2497 || !SCHED_GROUP_P (ready_element (&ready, 0))))
2500 targetm.sched.reorder2 (sched_dump, sched_verbose,
2502 ? ready_lastpos (&ready) : NULL,
2503 &ready.n_ready, clock_var);
2511 fprintf (sched_dump, ";;\tReady list (final): ");
2512 debug_ready_list (&ready);
2515 if (current_sched_info->queue_must_finish_empty)
2516 /* Sanity check -- queue must be empty now. Meaningless if region has
2518 gcc_assert (!q_size && !ready.n_ready);
2521 /* We must maintain QUEUE_INDEX between blocks in region. */
2522 for (i = ready.n_ready - 1; i >= 0; i--)
2526 x = ready_element (&ready, i);
2527 QUEUE_INDEX (x) = QUEUE_NOWHERE;
2528 TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
2532 for (i = 0; i <= max_insn_queue_index; i++)
2535 for (link = insn_queue[i]; link; link = XEXP (link, 1))
2540 QUEUE_INDEX (x) = QUEUE_NOWHERE;
2541 TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
2543 free_INSN_LIST_list (&insn_queue[i]);
2547 if (!current_sched_info->queue_must_finish_empty
2548 || haifa_recovery_bb_recently_added_p)
2550 /* INSN_TICK (minimum clock tick at which the insn becomes
2551 ready) may be not correct for the insn in the subsequent
2552 blocks of the region. We should use a correct value of
2553 `clock_var' or modify INSN_TICK. It is better to keep
2554 clock_var value equal to 0 at the start of a basic block.
2555 Therefore we modify INSN_TICK here. */
2556 fix_inter_tick (NEXT_INSN (prev_head), last_scheduled_insn);
2559 if (targetm.sched.md_finish)
2561 targetm.sched.md_finish (sched_dump, sched_verbose);
2563 /* Target might have added some instructions to the scheduled block.
2564 in its md_finish () hook. These new insns don't have any data
2565 initialized and to identify them we extend h_i_d so that they'll
2570 /* Update head/tail boundaries. */
2571 head = NEXT_INSN (prev_head);
2572 tail = last_scheduled_insn;
2574 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
2575 previously found among the insns. Insert them at the beginning
2579 basic_block head_bb = BLOCK_FOR_INSN (head);
2580 rtx note_head = note_list;
2582 while (PREV_INSN (note_head))
2584 set_block_for_insn (note_head, head_bb);
2585 note_head = PREV_INSN (note_head);
2587 /* In the above cycle we've missed this note: */
2588 set_block_for_insn (note_head, head_bb);
2590 PREV_INSN (note_head) = PREV_INSN (head);
2591 NEXT_INSN (PREV_INSN (head)) = note_head;
2592 PREV_INSN (head) = note_list;
2593 NEXT_INSN (note_list) = head;
2600 fprintf (sched_dump, ";; total time = %d\n;; new head = %d\n",
2601 clock_var, INSN_UID (head));
2602 fprintf (sched_dump, ";; new tail = %d\n\n",
2606 current_sched_info->head = head;
2607 current_sched_info->tail = tail;
2612 for (i = 0; i <= rgn_n_insns; i++)
2613 free (choice_stack [i].state);
2614 free (choice_stack);
2617 /* Set_priorities: compute priority of each insn in the block. */
2620 set_priorities (rtx head, rtx tail)
2624 int sched_max_insns_priority =
2625 current_sched_info->sched_max_insns_priority;
2628 if (head == tail && (! INSN_P (head)))
2633 prev_head = PREV_INSN (head);
2634 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
2640 (void) priority (insn);
2642 gcc_assert (INSN_PRIORITY_KNOWN (insn));
2644 sched_max_insns_priority = MAX (sched_max_insns_priority,
2645 INSN_PRIORITY (insn));
2648 current_sched_info->sched_max_insns_priority = sched_max_insns_priority;
2653 /* Next LUID to assign to an instruction. */
2656 /* Initialize some global state for the scheduler. */
2665 /* Switch to working copy of sched_info. */
2666 memcpy (¤t_sched_info_var, current_sched_info,
2667 sizeof (current_sched_info_var));
2668 current_sched_info = ¤t_sched_info_var;
2670 /* Disable speculative loads in their presence if cc0 defined. */
2672 flag_schedule_speculative_load = 0;
2675 /* Set dump and sched_verbose for the desired debugging output. If no
2676 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
2677 For -fsched-verbose=N, N>=10, print everything to stderr. */
2678 sched_verbose = sched_verbose_param;
2679 if (sched_verbose_param == 0 && dump_file)
2681 sched_dump = ((sched_verbose_param >= 10 || !dump_file)
2682 ? stderr : dump_file);
2684 /* Initialize SPEC_INFO. */
2685 if (targetm.sched.set_sched_flags)
2687 spec_info = &spec_info_var;
2688 targetm.sched.set_sched_flags (spec_info);
2689 if (current_sched_info->flags & DO_SPECULATION)
2690 spec_info->weakness_cutoff =
2691 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF) * MAX_DEP_WEAK) / 100;
2693 /* So we won't read anything accidentally. */
2695 #ifdef ENABLE_CHECKING
2696 check_sched_flags ();
2700 /* So we won't read anything accidentally. */
2703 /* Initialize issue_rate. */
2704 if (targetm.sched.issue_rate)
2705 issue_rate = targetm.sched.issue_rate ();
2709 if (cached_issue_rate != issue_rate)
2711 cached_issue_rate = issue_rate;
2712 /* To invalidate max_lookahead_tries: */
2713 cached_first_cycle_multipass_dfa_lookahead = 0;
2720 for (i = 0; i < old_max_uid; i++)
2723 h_i_d[i].todo_spec = HARD_DEP;
2724 h_i_d[i].queue_index = QUEUE_NOWHERE;
2725 h_i_d[i].tick = INVALID_TICK;
2726 h_i_d[i].inter_tick = INVALID_TICK;
2729 if (targetm.sched.init_dfa_pre_cycle_insn)
2730 targetm.sched.init_dfa_pre_cycle_insn ();
2732 if (targetm.sched.init_dfa_post_cycle_insn)
2733 targetm.sched.init_dfa_post_cycle_insn ();
2736 dfa_state_size = state_size ();
2737 curr_state = xmalloc (dfa_state_size);
2742 for (insn = BB_HEAD (b); ; insn = NEXT_INSN (insn))
2744 INSN_LUID (insn) = luid;
2746 /* Increment the next luid, unless this is a note. We don't
2747 really need separate IDs for notes and we don't want to
2748 schedule differently depending on whether or not there are
2749 line-number notes, i.e., depending on whether or not we're
2750 generating debugging information. */
2754 if (insn == BB_END (b))
2758 init_dependency_caches (luid);
2760 init_alias_analysis ();
2762 old_last_basic_block = 0;
2765 /* Compute INSN_REG_WEIGHT for all blocks. We must do this before
2766 removing death notes. */
2767 FOR_EACH_BB_REVERSE (b)
2768 find_insn_reg_weight (b);
2770 if (targetm.sched.md_init_global)
2771 targetm.sched.md_init_global (sched_dump, sched_verbose, old_max_uid);
2773 nr_begin_data = nr_begin_control = nr_be_in_data = nr_be_in_control = 0;
2774 before_recovery = 0;
2776 haifa_recovery_bb_ever_added_p = false;
2778 #ifdef ENABLE_CHECKING
2779 /* This is used preferably for finding bugs in check_cfg () itself. */
2784 /* Free global data used during insn scheduling. */
2792 free_dependency_caches ();
2793 end_alias_analysis ();
2795 if (targetm.sched.md_finish_global)
2796 targetm.sched.md_finish_global (sched_dump, sched_verbose);
2798 if (spec_info && spec_info->dump)
2800 char c = reload_completed ? 'a' : 'b';
2802 fprintf (spec_info->dump,
2803 ";; %s:\n", current_function_name ());
2805 fprintf (spec_info->dump,
2806 ";; Procedure %cr-begin-data-spec motions == %d\n",
2808 fprintf (spec_info->dump,
2809 ";; Procedure %cr-be-in-data-spec motions == %d\n",
2811 fprintf (spec_info->dump,
2812 ";; Procedure %cr-begin-control-spec motions == %d\n",
2813 c, nr_begin_control);
2814 fprintf (spec_info->dump,
2815 ";; Procedure %cr-be-in-control-spec motions == %d\n",
2816 c, nr_be_in_control);
2819 #ifdef ENABLE_CHECKING
2820 /* After reload ia64 backend clobbers CFG, so can't check anything. */
2821 if (!reload_completed)
2825 current_sched_info = NULL;
2828 /* Fix INSN_TICKs of the instructions in the current block as well as
2829 INSN_TICKs of their dependents.
2830 HEAD and TAIL are the begin and the end of the current scheduled block. */
2832 fix_inter_tick (rtx head, rtx tail)
2834 /* Set of instructions with corrected INSN_TICK. */
2835 bitmap_head processed;
2836 /* ??? It is doubtful if we should assume that cycle advance happens on
2837 basic block boundaries. Basically insns that are unconditionally ready
2838 on the start of the block are more preferable then those which have
2839 a one cycle dependency over insn from the previous block. */
2840 int next_clock = clock_var + 1;
2842 bitmap_initialize (&processed, 0);
2844 /* Iterates over scheduled instructions and fix their INSN_TICKs and
2845 INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
2846 across different blocks. */
2847 for (tail = NEXT_INSN (tail); head != tail; head = NEXT_INSN (head))
2852 sd_iterator_def sd_it;
2855 tick = INSN_TICK (head);
2856 gcc_assert (tick >= MIN_TICK);
2858 /* Fix INSN_TICK of instruction from just scheduled block. */
2859 if (!bitmap_bit_p (&processed, INSN_LUID (head)))
2861 bitmap_set_bit (&processed, INSN_LUID (head));
2864 if (tick < MIN_TICK)
2867 INSN_TICK (head) = tick;
2870 FOR_EACH_DEP (head, SD_LIST_RES_FORW, sd_it, dep)
2874 next = DEP_CON (dep);
2875 tick = INSN_TICK (next);
2877 if (tick != INVALID_TICK
2878 /* If NEXT has its INSN_TICK calculated, fix it.
2879 If not - it will be properly calculated from
2880 scratch later in fix_tick_ready. */
2881 && !bitmap_bit_p (&processed, INSN_LUID (next)))
2883 bitmap_set_bit (&processed, INSN_LUID (next));
2886 if (tick < MIN_TICK)
2889 if (tick > INTER_TICK (next))
2890 INTER_TICK (next) = tick;
2892 tick = INTER_TICK (next);
2894 INSN_TICK (next) = tick;
2899 bitmap_clear (&processed);
2902 /* Check if NEXT is ready to be added to the ready or queue list.
2903 If "yes", add it to the proper list.
2905 -1 - is not ready yet,
2906 0 - added to the ready list,
2907 0 < N - queued for N cycles. */
2909 try_ready (rtx next)
2913 ts = &TODO_SPEC (next);
2916 gcc_assert (!(old_ts & ~(SPECULATIVE | HARD_DEP))
2917 && ((old_ts & HARD_DEP)
2918 || (old_ts & SPECULATIVE)));
2920 if (sd_lists_empty_p (next, SD_LIST_BACK))
2921 /* NEXT has all its dependencies resolved. */
2923 /* Remove HARD_DEP bit from NEXT's status. */
2926 if (current_sched_info->flags & DO_SPECULATION)
2927 /* Remove all speculative bits from NEXT's status. */
2928 *ts &= ~SPECULATIVE;
2932 /* One of the NEXT's dependencies has been resolved.
2933 Recalculate NEXT's status. */
2935 *ts &= ~SPECULATIVE & ~HARD_DEP;
2937 if (sd_lists_empty_p (next, SD_LIST_HARD_BACK))
2938 /* Now we've got NEXT with speculative deps only.
2939 1. Look at the deps to see what we have to do.
2940 2. Check if we can do 'todo'. */
2942 sd_iterator_def sd_it;
2944 bool first_p = true;
2946 FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
2948 ds_t ds = DEP_STATUS (dep) & SPECULATIVE;
2957 *ts = ds_merge (*ts, ds);
2960 if (dep_weak (*ts) < spec_info->weakness_cutoff)
2961 /* Too few points. */
2962 *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
2969 gcc_assert (*ts == old_ts
2970 && QUEUE_INDEX (next) == QUEUE_NOWHERE);
2971 else if (current_sched_info->new_ready)
2972 *ts = current_sched_info->new_ready (next, *ts);
2974 /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
2975 have its original pattern or changed (speculative) one. This is due
2976 to changing ebb in region scheduling.
2977 * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
2978 has speculative pattern.
2980 We can't assert (!(*ts & HARD_DEP) || *ts == old_ts) here because
2981 control-speculative NEXT could have been discarded by sched-rgn.c
2982 (the same case as when discarded by can_schedule_ready_p ()). */
2984 if ((*ts & SPECULATIVE)
2985 /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't
2986 need to change anything. */
2992 gcc_assert ((*ts & SPECULATIVE) && !(*ts & ~SPECULATIVE));
2994 res = speculate_insn (next, *ts, &new_pat);
2999 /* It would be nice to change DEP_STATUS of all dependences,
3000 which have ((DEP_STATUS & SPECULATIVE) == *ts) to HARD_DEP,
3001 so we won't reanalyze anything. */
3002 *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
3006 /* We follow the rule, that every speculative insn
3007 has non-null ORIG_PAT. */
3008 if (!ORIG_PAT (next))
3009 ORIG_PAT (next) = PATTERN (next);
3013 if (!ORIG_PAT (next))
3014 /* If we gonna to overwrite the original pattern of insn,
3016 ORIG_PAT (next) = PATTERN (next);
3018 change_pattern (next, new_pat);
3026 /* We need to restore pattern only if (*ts == 0), because otherwise it is
3027 either correct (*ts & SPECULATIVE),
3028 or we simply don't care (*ts & HARD_DEP). */
3030 gcc_assert (!ORIG_PAT (next)
3031 || !IS_SPECULATION_BRANCHY_CHECK_P (next));
3035 /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
3036 control-speculative NEXT could have been discarded by sched-rgn.c
3037 (the same case as when discarded by can_schedule_ready_p ()). */
3038 /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
3040 change_queue_index (next, QUEUE_NOWHERE);
3043 else if (!(*ts & BEGIN_SPEC) && ORIG_PAT (next) && !IS_SPECULATION_CHECK_P (next))
3044 /* We should change pattern of every previously speculative
3045 instruction - and we determine if NEXT was speculative by using
3046 ORIG_PAT field. Except one case - speculation checks have ORIG_PAT
3047 pat too, so skip them. */
3049 change_pattern (next, ORIG_PAT (next));
3050 ORIG_PAT (next) = 0;
3053 if (sched_verbose >= 2)
3055 int s = TODO_SPEC (next);
3057 fprintf (sched_dump, ";;\t\tdependencies resolved: insn %s",
3058 (*current_sched_info->print_insn) (next, 0));
3060 if (spec_info && spec_info->dump)
3063 fprintf (spec_info->dump, "; data-spec;");
3064 if (s & BEGIN_CONTROL)
3065 fprintf (spec_info->dump, "; control-spec;");
3066 if (s & BE_IN_CONTROL)
3067 fprintf (spec_info->dump, "; in-control-spec;");
3070 fprintf (sched_dump, "\n");
3073 adjust_priority (next);
3075 return fix_tick_ready (next);
3078 /* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */
3080 fix_tick_ready (rtx next)
3084 if (!sd_lists_empty_p (next, SD_LIST_RES_BACK))
3087 sd_iterator_def sd_it;
3090 tick = INSN_TICK (next);
3091 /* if tick is not equal to INVALID_TICK, then update
3092 INSN_TICK of NEXT with the most recent resolved dependence
3093 cost. Otherwise, recalculate from scratch. */
3094 full_p = (tick == INVALID_TICK);
3096 FOR_EACH_DEP (next, SD_LIST_RES_BACK, sd_it, dep)
3098 rtx pro = DEP_PRO (dep);
3101 gcc_assert (INSN_TICK (pro) >= MIN_TICK);
3103 tick1 = INSN_TICK (pro) + dep_cost (dep);
3114 INSN_TICK (next) = tick;
3116 delay = tick - clock_var;
3118 delay = QUEUE_READY;
3120 change_queue_index (next, delay);
3125 /* Move NEXT to the proper queue list with (DELAY >= 1),
3126 or add it to the ready list (DELAY == QUEUE_READY),
3127 or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */
3129 change_queue_index (rtx next, int delay)
3131 int i = QUEUE_INDEX (next);
3133 gcc_assert (QUEUE_NOWHERE <= delay && delay <= max_insn_queue_index
3135 gcc_assert (i != QUEUE_SCHEDULED);
3137 if ((delay > 0 && NEXT_Q_AFTER (q_ptr, delay) == i)
3138 || (delay < 0 && delay == i))
3139 /* We have nothing to do. */
3142 /* Remove NEXT from wherever it is now. */
3143 if (i == QUEUE_READY)
3144 ready_remove_insn (next);
3146 queue_remove (next);
3148 /* Add it to the proper place. */
3149 if (delay == QUEUE_READY)
3150 ready_add (readyp, next, false);
3151 else if (delay >= 1)
3152 queue_insn (next, delay);
3154 if (sched_verbose >= 2)
3156 fprintf (sched_dump, ";;\t\ttick updated: insn %s",
3157 (*current_sched_info->print_insn) (next, 0));
3159 if (delay == QUEUE_READY)
3160 fprintf (sched_dump, " into ready\n");
3161 else if (delay >= 1)
3162 fprintf (sched_dump, " into queue with cost=%d\n", delay);
3164 fprintf (sched_dump, " removed from ready or queue lists\n");
3168 /* Extend H_I_D data. */
3172 /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
3173 pseudos which do not cross calls. */
3174 int new_max_uid = get_max_uid () + 1;
3176 h_i_d = xrecalloc (h_i_d, new_max_uid, old_max_uid, sizeof (*h_i_d));
3177 old_max_uid = new_max_uid;
3179 if (targetm.sched.h_i_d_extended)
3180 targetm.sched.h_i_d_extended ();
3183 /* Extend READY, READY_TRY and CHOICE_STACK arrays.
3184 N_NEW_INSNS is the number of additional elements to allocate. */
3186 extend_ready (int n_new_insns)
3190 readyp->veclen = rgn_n_insns + n_new_insns + 1 + issue_rate;
3191 readyp->vec = XRESIZEVEC (rtx, readyp->vec, readyp->veclen);
3193 ready_try = xrecalloc (ready_try, rgn_n_insns + n_new_insns + 1,
3194 rgn_n_insns + 1, sizeof (char));
3196 rgn_n_insns += n_new_insns;
3198 choice_stack = XRESIZEVEC (struct choice_entry, choice_stack,
3201 for (i = rgn_n_insns; n_new_insns--; i--)
3202 choice_stack[i].state = xmalloc (dfa_state_size);
3205 /* Extend global scheduler structures (those, that live across calls to
3206 schedule_block) to include information about just emitted INSN. */
3208 extend_global (rtx insn)
3210 gcc_assert (INSN_P (insn));
3212 /* These structures have scheduler scope. */
3218 /* Init data handled in sched-deps.c. */
3219 sd_init_insn (insn);
3221 /* Extend dependency caches by one element. */
3222 extend_dependency_caches (1, false);
3225 /* Extends global and local scheduler structures to include information
3226 about just emitted INSN. */
3228 extend_all (rtx insn)
3230 extend_global (insn);
3232 /* These structures have block scope. */
3235 (*current_sched_info->add_remove_insn) (insn, 0);
3238 /* Initialize h_i_d entry of the new INSN with default values.
3239 Values, that are not explicitly initialized here, hold zero. */
3241 init_h_i_d (rtx insn)
3243 INSN_LUID (insn) = luid++;
3244 INSN_COST (insn) = -1;
3245 TODO_SPEC (insn) = HARD_DEP;
3246 QUEUE_INDEX (insn) = QUEUE_NOWHERE;
3247 INSN_TICK (insn) = INVALID_TICK;
3248 INTER_TICK (insn) = INVALID_TICK;
3249 find_insn_reg_weight1 (insn);
3252 /* Generates recovery code for INSN. */
3254 generate_recovery_code (rtx insn)
3256 if (TODO_SPEC (insn) & BEGIN_SPEC)
3257 begin_speculative_block (insn);
3259 /* Here we have insn with no dependencies to
3260 instructions other then CHECK_SPEC ones. */
3262 if (TODO_SPEC (insn) & BE_IN_SPEC)
3263 add_to_speculative_block (insn);
3267 Tries to add speculative dependencies of type FS between instructions
3268 in deps_list L and TWIN. */
3270 process_insn_forw_deps_be_in_spec (rtx insn, rtx twin, ds_t fs)
3272 sd_iterator_def sd_it;
3275 FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
3280 consumer = DEP_CON (dep);
3282 ds = DEP_STATUS (dep);
3284 if (/* If we want to create speculative dep. */
3286 /* And we can do that because this is a true dep. */
3287 && (ds & DEP_TYPES) == DEP_TRUE)
3289 gcc_assert (!(ds & BE_IN_SPEC));
3291 if (/* If this dep can be overcome with 'begin speculation'. */
3293 /* Then we have a choice: keep the dep 'begin speculative'
3294 or transform it into 'be in speculative'. */
3296 if (/* In try_ready we assert that if insn once became ready
3297 it can be removed from the ready (or queue) list only
3298 due to backend decision. Hence we can't let the
3299 probability of the speculative dep to decrease. */
3300 dep_weak (ds) <= dep_weak (fs))
3304 new_ds = (ds & ~BEGIN_SPEC) | fs;
3306 if (/* consumer can 'be in speculative'. */
3307 sched_insn_is_legitimate_for_speculation_p (consumer,
3309 /* Transform it to be in speculative. */
3314 /* Mark the dep as 'be in speculative'. */
3319 dep_def _new_dep, *new_dep = &_new_dep;
3321 init_dep_1 (new_dep, twin, consumer, DEP_TYPE (dep), ds);
3322 sd_add_dep (new_dep, false);
3327 /* Generates recovery code for BEGIN speculative INSN. */
3329 begin_speculative_block (rtx insn)
3331 if (TODO_SPEC (insn) & BEGIN_DATA)
3333 if (TODO_SPEC (insn) & BEGIN_CONTROL)
3336 create_check_block_twin (insn, false);
3338 TODO_SPEC (insn) &= ~BEGIN_SPEC;
3341 /* Generates recovery code for BE_IN speculative INSN. */
3343 add_to_speculative_block (rtx insn)
3346 sd_iterator_def sd_it;
3349 rtx_vec_t priorities_roots;
3351 ts = TODO_SPEC (insn);
3352 gcc_assert (!(ts & ~BE_IN_SPEC));
3354 if (ts & BE_IN_DATA)
3356 if (ts & BE_IN_CONTROL)
3359 TODO_SPEC (insn) &= ~BE_IN_SPEC;
3360 gcc_assert (!TODO_SPEC (insn));
3362 DONE_SPEC (insn) |= ts;
3364 /* First we convert all simple checks to branchy. */
3365 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3366 sd_iterator_cond (&sd_it, &dep);)
3368 rtx check = DEP_PRO (dep);
3370 if (IS_SPECULATION_SIMPLE_CHECK_P (check))
3372 create_check_block_twin (check, true);
3374 /* Restart search. */
3375 sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3378 /* Continue search. */
3379 sd_iterator_next (&sd_it);
3382 priorities_roots = NULL;
3383 clear_priorities (insn, &priorities_roots);
3390 /* Get the first backward dependency of INSN. */
3391 sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3392 if (!sd_iterator_cond (&sd_it, &dep))
3393 /* INSN has no backward dependencies left. */
3396 gcc_assert ((DEP_STATUS (dep) & BEGIN_SPEC) == 0
3397 && (DEP_STATUS (dep) & BE_IN_SPEC) != 0
3398 && (DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
3400 check = DEP_PRO (dep);
3402 gcc_assert (!IS_SPECULATION_CHECK_P (check) && !ORIG_PAT (check)
3403 && QUEUE_INDEX (check) == QUEUE_NOWHERE);
3405 rec = BLOCK_FOR_INSN (check);
3407 twin = emit_insn_before (copy_insn (PATTERN (insn)), BB_END (rec));
3408 extend_global (twin);
3410 sd_copy_back_deps (twin, insn, true);
3412 if (sched_verbose && spec_info->dump)
3413 /* INSN_BB (insn) isn't determined for twin insns yet.
3414 So we can't use current_sched_info->print_insn. */
3415 fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
3416 INSN_UID (twin), rec->index);
3418 twins = alloc_INSN_LIST (twin, twins);
3420 /* Add dependences between TWIN and all appropriate
3421 instructions from REC. */
3422 FOR_EACH_DEP (insn, SD_LIST_SPEC_BACK, sd_it, dep)
3424 rtx pro = DEP_PRO (dep);
3426 gcc_assert (DEP_TYPE (dep) == REG_DEP_TRUE);
3428 /* INSN might have dependencies from the instructions from
3429 several recovery blocks. At this iteration we process those
3430 producers that reside in REC. */
3431 if (BLOCK_FOR_INSN (pro) == rec)
3433 dep_def _new_dep, *new_dep = &_new_dep;
3435 init_dep (new_dep, pro, twin, REG_DEP_TRUE);
3436 sd_add_dep (new_dep, false);
3440 process_insn_forw_deps_be_in_spec (insn, twin, ts);
3442 /* Remove all dependencies between INSN and insns in REC. */
3443 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3444 sd_iterator_cond (&sd_it, &dep);)
3446 rtx pro = DEP_PRO (dep);
3448 if (BLOCK_FOR_INSN (pro) == rec)
3449 sd_delete_dep (sd_it);
3451 sd_iterator_next (&sd_it);
3455 /* We couldn't have added the dependencies between INSN and TWINS earlier
3456 because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
3461 twin = XEXP (twins, 0);
3464 dep_def _new_dep, *new_dep = &_new_dep;
3466 init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
3467 sd_add_dep (new_dep, false);
3470 twin = XEXP (twins, 1);
3471 free_INSN_LIST_node (twins);
3475 calc_priorities (priorities_roots);
3476 VEC_free (rtx, heap, priorities_roots);
3479 /* Extends and fills with zeros (only the new part) array pointed to by P. */
3481 xrecalloc (void *p, size_t new_nmemb, size_t old_nmemb, size_t size)
3483 gcc_assert (new_nmemb >= old_nmemb);
3484 p = XRESIZEVAR (void, p, new_nmemb * size);
3485 memset (((char *) p) + old_nmemb * size, 0, (new_nmemb - old_nmemb) * size);
3489 /* Return the probability of speculation success for the speculation
3497 dt = FIRST_SPEC_TYPE;
3502 res *= (ds_t) get_dep_weak (ds, dt);
3506 if (dt == LAST_SPEC_TYPE)
3508 dt <<= SPEC_TYPE_SHIFT;
3514 res /= MAX_DEP_WEAK;
3516 if (res < MIN_DEP_WEAK)
3519 gcc_assert (res <= MAX_DEP_WEAK);
3525 Find fallthru edge from PRED. */
3527 find_fallthru_edge (basic_block pred)
3533 succ = pred->next_bb;
3534 gcc_assert (succ->prev_bb == pred);
3536 if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
3538 FOR_EACH_EDGE (e, ei, pred->succs)
3539 if (e->flags & EDGE_FALLTHRU)
3541 gcc_assert (e->dest == succ);
3547 FOR_EACH_EDGE (e, ei, succ->preds)
3548 if (e->flags & EDGE_FALLTHRU)
3550 gcc_assert (e->src == pred);
3558 /* Initialize BEFORE_RECOVERY variable. */
3560 init_before_recovery (void)
3565 last = EXIT_BLOCK_PTR->prev_bb;
3566 e = find_fallthru_edge (last);
3570 /* We create two basic blocks:
3571 1. Single instruction block is inserted right after E->SRC
3573 2. Empty block right before EXIT_BLOCK.
3574 Between these two blocks recovery blocks will be emitted. */
3576 basic_block single, empty;
3579 single = create_empty_bb (last);
3580 empty = create_empty_bb (single);
3582 single->count = last->count;
3583 empty->count = last->count;
3584 single->frequency = last->frequency;
3585 empty->frequency = last->frequency;
3586 BB_COPY_PARTITION (single, last);
3587 BB_COPY_PARTITION (empty, last);
3589 redirect_edge_succ (e, single);
3590 make_single_succ_edge (single, empty, 0);
3591 make_single_succ_edge (empty, EXIT_BLOCK_PTR,
3592 EDGE_FALLTHRU | EDGE_CAN_FALLTHRU);
3594 label = block_label (empty);
3595 x = emit_jump_insn_after (gen_jump (label), BB_END (single));
3596 JUMP_LABEL (x) = label;
3597 LABEL_NUSES (label)++;
3600 emit_barrier_after (x);
3602 add_block (empty, 0);
3603 add_block (single, 0);
3605 before_recovery = single;
3607 if (sched_verbose >= 2 && spec_info->dump)
3608 fprintf (spec_info->dump,
3609 ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n",
3610 last->index, single->index, empty->index);
3613 before_recovery = last;
3616 /* Returns new recovery block. */
3618 create_recovery_block (void)
3624 haifa_recovery_bb_recently_added_p = true;
3625 haifa_recovery_bb_ever_added_p = true;
3627 if (!before_recovery)
3628 init_before_recovery ();
3630 barrier = get_last_bb_insn (before_recovery);
3631 gcc_assert (BARRIER_P (barrier));
3633 label = emit_label_after (gen_label_rtx (), barrier);
3635 rec = create_basic_block (label, label, before_recovery);
3637 /* Recovery block always end with an unconditional jump. */
3638 emit_barrier_after (BB_END (rec));
3640 if (BB_PARTITION (before_recovery) != BB_UNPARTITIONED)
3641 BB_SET_PARTITION (rec, BB_COLD_PARTITION);
3643 if (sched_verbose && spec_info->dump)
3644 fprintf (spec_info->dump, ";;\t\tGenerated recovery block rec%d\n",
3647 before_recovery = rec;
3652 /* This function creates recovery code for INSN. If MUTATE_P is nonzero,
3653 INSN is a simple check, that should be converted to branchy one. */
3655 create_check_block_twin (rtx insn, bool mutate_p)
3658 rtx label, check, twin;
3660 sd_iterator_def sd_it;
3662 dep_def _new_dep, *new_dep = &_new_dep;
3664 gcc_assert (ORIG_PAT (insn)
3666 || (IS_SPECULATION_SIMPLE_CHECK_P (insn)
3667 && !(TODO_SPEC (insn) & SPECULATIVE))));
3669 /* Create recovery block. */
3670 if (mutate_p || targetm.sched.needs_block_p (insn))
3672 rec = create_recovery_block ();
3673 label = BB_HEAD (rec);
3677 rec = EXIT_BLOCK_PTR;
3682 check = targetm.sched.gen_check (insn, label, mutate_p);
3684 if (rec != EXIT_BLOCK_PTR)
3686 /* To have mem_reg alive at the beginning of second_bb,
3687 we emit check BEFORE insn, so insn after splitting
3688 insn will be at the beginning of second_bb, which will
3689 provide us with the correct life information. */
3690 check = emit_jump_insn_before (check, insn);
3691 JUMP_LABEL (check) = label;
3692 LABEL_NUSES (label)++;
3695 check = emit_insn_before (check, insn);
3697 /* Extend data structures. */
3699 RECOVERY_BLOCK (check) = rec;
3701 if (sched_verbose && spec_info->dump)
3702 fprintf (spec_info->dump, ";;\t\tGenerated check insn : %s\n",
3703 (*current_sched_info->print_insn) (check, 0));
3705 gcc_assert (ORIG_PAT (insn));
3707 /* Initialize TWIN (twin is a duplicate of original instruction
3708 in the recovery block). */
3709 if (rec != EXIT_BLOCK_PTR)
3711 sd_iterator_def sd_it;
3714 FOR_EACH_DEP (insn, SD_LIST_RES_BACK, sd_it, dep)
3715 if ((DEP_STATUS (dep) & DEP_OUTPUT) != 0)
3717 struct _dep _dep2, *dep2 = &_dep2;
3719 init_dep (dep2, DEP_PRO (dep), check, REG_DEP_TRUE);
3721 sd_add_dep (dep2, true);
3724 twin = emit_insn_after (ORIG_PAT (insn), BB_END (rec));
3725 extend_global (twin);
3727 if (sched_verbose && spec_info->dump)
3728 /* INSN_BB (insn) isn't determined for twin insns yet.
3729 So we can't use current_sched_info->print_insn. */
3730 fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
3731 INSN_UID (twin), rec->index);
3735 ORIG_PAT (check) = ORIG_PAT (insn);
3736 HAS_INTERNAL_DEP (check) = 1;
3738 /* ??? We probably should change all OUTPUT dependencies to
3742 /* Copy all resolved back dependencies of INSN to TWIN. This will
3743 provide correct value for INSN_TICK (TWIN). */
3744 sd_copy_back_deps (twin, insn, true);
3746 if (rec != EXIT_BLOCK_PTR)
3747 /* In case of branchy check, fix CFG. */
3749 basic_block first_bb, second_bb;
3754 first_bb = BLOCK_FOR_INSN (check);
3755 e = split_block (first_bb, check);
3756 /* split_block emits note if *check == BB_END. Probably it
3757 is better to rip that note off. */
3758 gcc_assert (e->src == first_bb);
3759 second_bb = e->dest;
3761 /* This is fixing of incoming edge. */
3762 /* ??? Which other flags should be specified? */
3763 if (BB_PARTITION (first_bb) != BB_PARTITION (rec))
3764 /* Partition type is the same, if it is "unpartitioned". */
3765 edge_flags = EDGE_CROSSING;
3769 e = make_edge (first_bb, rec, edge_flags);
3771 add_block (second_bb, first_bb);
3773 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (second_bb)));
3774 label = block_label (second_bb);
3775 jump = emit_jump_insn_after (gen_jump (label), BB_END (rec));
3776 JUMP_LABEL (jump) = label;
3777 LABEL_NUSES (label)++;
3778 extend_global (jump);
3780 if (BB_PARTITION (second_bb) != BB_PARTITION (rec))
3781 /* Partition type is the same, if it is "unpartitioned". */
3783 /* Rewritten from cfgrtl.c. */
3784 if (flag_reorder_blocks_and_partition
3785 && targetm.have_named_sections
3786 /*&& !any_condjump_p (jump)*/)
3787 /* any_condjump_p (jump) == false.
3788 We don't need the same note for the check because
3789 any_condjump_p (check) == true. */
3791 REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP,
3795 edge_flags = EDGE_CROSSING;
3800 make_single_succ_edge (rec, second_bb, edge_flags);
3802 add_block (rec, EXIT_BLOCK_PTR);
3805 /* Move backward dependences from INSN to CHECK and
3806 move forward dependences from INSN to TWIN. */
3808 /* First, create dependencies between INSN's producers and CHECK & TWIN. */
3809 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
3811 rtx pro = DEP_PRO (dep);
3814 /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
3815 check --TRUE--> producer ??? or ANTI ???
3816 twin --TRUE--> producer
3817 twin --ANTI--> check
3819 If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
3820 check --ANTI--> producer
3821 twin --ANTI--> producer
3822 twin --ANTI--> check
3824 If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
3825 check ~~TRUE~~> producer
3826 twin ~~TRUE~~> producer
3827 twin --ANTI--> check */
3829 ds = DEP_STATUS (dep);
3831 if (ds & BEGIN_SPEC)
3833 gcc_assert (!mutate_p);
3837 init_dep_1 (new_dep, pro, check, DEP_TYPE (dep), ds);
3838 sd_add_dep (new_dep, false);
3840 if (rec != EXIT_BLOCK_PTR)
3842 DEP_CON (new_dep) = twin;
3843 sd_add_dep (new_dep, false);
3847 /* Second, remove backward dependencies of INSN. */
3848 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
3849 sd_iterator_cond (&sd_it, &dep);)
3851 if ((DEP_STATUS (dep) & BEGIN_SPEC)
3853 /* We can delete this dep because we overcome it with
3854 BEGIN_SPECULATION. */
3855 sd_delete_dep (sd_it);
3857 sd_iterator_next (&sd_it);
3860 /* Future Speculations. Determine what BE_IN speculations will be like. */
3863 /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
3866 gcc_assert (!DONE_SPEC (insn));
3870 ds_t ts = TODO_SPEC (insn);
3872 DONE_SPEC (insn) = ts & BEGIN_SPEC;
3873 CHECK_SPEC (check) = ts & BEGIN_SPEC;
3875 /* Luckiness of future speculations solely depends upon initial
3876 BEGIN speculation. */
3877 if (ts & BEGIN_DATA)
3878 fs = set_dep_weak (fs, BE_IN_DATA, get_dep_weak (ts, BEGIN_DATA));
3879 if (ts & BEGIN_CONTROL)
3880 fs = set_dep_weak (fs, BE_IN_CONTROL,
3881 get_dep_weak (ts, BEGIN_CONTROL));
3884 CHECK_SPEC (check) = CHECK_SPEC (insn);
3886 /* Future speculations: call the helper. */
3887 process_insn_forw_deps_be_in_spec (insn, twin, fs);
3889 if (rec != EXIT_BLOCK_PTR)
3891 /* Which types of dependencies should we use here is,
3892 generally, machine-dependent question... But, for now,
3897 init_dep (new_dep, insn, check, REG_DEP_TRUE);
3898 sd_add_dep (new_dep, false);
3900 init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
3901 sd_add_dep (new_dep, false);
3905 if (spec_info->dump)
3906 fprintf (spec_info->dump, ";;\t\tRemoved simple check : %s\n",
3907 (*current_sched_info->print_insn) (insn, 0));
3909 /* Remove all dependencies of the INSN. */
3911 sd_it = sd_iterator_start (insn, (SD_LIST_FORW
3913 | SD_LIST_RES_BACK));
3914 while (sd_iterator_cond (&sd_it, &dep))
3915 sd_delete_dep (sd_it);
3918 /* If former check (INSN) already was moved to the ready (or queue)
3919 list, add new check (CHECK) there too. */
3920 if (QUEUE_INDEX (insn) != QUEUE_NOWHERE)
3923 /* Remove old check from instruction stream and free its
3925 sched_remove_insn (insn);
3928 init_dep (new_dep, check, twin, REG_DEP_ANTI);
3929 sd_add_dep (new_dep, false);
3933 init_dep_1 (new_dep, insn, check, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT);
3934 sd_add_dep (new_dep, false);
3938 /* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
3939 because it'll be done later in add_to_speculative_block. */
3941 rtx_vec_t priorities_roots = NULL;
3943 clear_priorities (twin, &priorities_roots);
3944 calc_priorities (priorities_roots);
3945 VEC_free (rtx, heap, priorities_roots);
3949 /* Removes dependency between instructions in the recovery block REC
3950 and usual region instructions. It keeps inner dependences so it
3951 won't be necessary to recompute them. */
3953 fix_recovery_deps (basic_block rec)
3955 rtx note, insn, jump, ready_list = 0;
3956 bitmap_head in_ready;
3959 bitmap_initialize (&in_ready, 0);
3961 /* NOTE - a basic block note. */
3962 note = NEXT_INSN (BB_HEAD (rec));
3963 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
3964 insn = BB_END (rec);
3965 gcc_assert (JUMP_P (insn));
3966 insn = PREV_INSN (insn);
3970 sd_iterator_def sd_it;
3973 for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
3974 sd_iterator_cond (&sd_it, &dep);)
3976 rtx consumer = DEP_CON (dep);
3978 if (BLOCK_FOR_INSN (consumer) != rec)
3980 sd_delete_dep (sd_it);
3982 if (!bitmap_bit_p (&in_ready, INSN_LUID (consumer)))
3984 ready_list = alloc_INSN_LIST (consumer, ready_list);
3985 bitmap_set_bit (&in_ready, INSN_LUID (consumer));
3990 gcc_assert ((DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
3992 sd_iterator_next (&sd_it);
3996 insn = PREV_INSN (insn);
3998 while (insn != note);
4000 bitmap_clear (&in_ready);
4002 /* Try to add instructions to the ready or queue list. */
4003 for (link = ready_list; link; link = XEXP (link, 1))
4004 try_ready (XEXP (link, 0));
4005 free_INSN_LIST_list (&ready_list);
4007 /* Fixing jump's dependences. */
4008 insn = BB_HEAD (rec);
4009 jump = BB_END (rec);
4011 gcc_assert (LABEL_P (insn));
4012 insn = NEXT_INSN (insn);
4014 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
4015 add_jump_dependencies (insn, jump);
4018 /* Changes pattern of the INSN to NEW_PAT. */
4020 change_pattern (rtx insn, rtx new_pat)
4024 t = validate_change (insn, &PATTERN (insn), new_pat, 0);
4026 /* Invalidate INSN_COST, so it'll be recalculated. */
4027 INSN_COST (insn) = -1;
4028 /* Invalidate INSN_TICK, so it'll be recalculated. */
4029 INSN_TICK (insn) = INVALID_TICK;
4030 dfa_clear_single_insn_cache (insn);
4033 /* Return true if INSN can potentially be speculated with type DS. */
4035 sched_insn_is_legitimate_for_speculation_p (const_rtx insn, ds_t ds)
4037 if (HAS_INTERNAL_DEP (insn))
4040 if (!NONJUMP_INSN_P (insn))
4043 if (SCHED_GROUP_P (insn))
4046 if (IS_SPECULATION_CHECK_P (insn))
4049 if (side_effects_p (PATTERN (insn)))
4052 if ((ds & BE_IN_SPEC)
4053 && may_trap_p (PATTERN (insn)))
4059 /* -1 - can't speculate,
4060 0 - for speculation with REQUEST mode it is OK to use
4061 current instruction pattern,
4062 1 - need to change pattern for *NEW_PAT to be speculative. */
4064 speculate_insn (rtx insn, ds_t request, rtx *new_pat)
4066 gcc_assert (current_sched_info->flags & DO_SPECULATION
4067 && (request & SPECULATIVE)
4068 && sched_insn_is_legitimate_for_speculation_p (insn, request));
4070 if ((request & spec_info->mask) != request)
4073 if (request & BE_IN_SPEC
4074 && !(request & BEGIN_SPEC))
4077 return targetm.sched.speculate_insn (insn, request & BEGIN_SPEC, new_pat);
4080 /* Print some information about block BB, which starts with HEAD and
4081 ends with TAIL, before scheduling it.
4082 I is zero, if scheduler is about to start with the fresh ebb. */
4084 dump_new_block_header (int i, basic_block bb, rtx head, rtx tail)
4087 fprintf (sched_dump,
4088 ";; ======================================================\n");
4090 fprintf (sched_dump,
4091 ";; =====================ADVANCING TO=====================\n");
4092 fprintf (sched_dump,
4093 ";; -- basic block %d from %d to %d -- %s reload\n",
4094 bb->index, INSN_UID (head), INSN_UID (tail),
4095 (reload_completed ? "after" : "before"));
4096 fprintf (sched_dump,
4097 ";; ======================================================\n");
4098 fprintf (sched_dump, "\n");
4101 /* Unlink basic block notes and labels and saves them, so they
4102 can be easily restored. We unlink basic block notes in EBB to
4103 provide back-compatibility with the previous code, as target backends
4104 assume, that there'll be only instructions between
4105 current_sched_info->{head and tail}. We restore these notes as soon
4107 FIRST (LAST) is the first (last) basic block in the ebb.
4108 NB: In usual case (FIRST == LAST) nothing is really done. */
4110 unlink_bb_notes (basic_block first, basic_block last)
4112 /* We DON'T unlink basic block notes of the first block in the ebb. */
4116 bb_header = xmalloc (last_basic_block * sizeof (*bb_header));
4118 /* Make a sentinel. */
4119 if (last->next_bb != EXIT_BLOCK_PTR)
4120 bb_header[last->next_bb->index] = 0;
4122 first = first->next_bb;
4125 rtx prev, label, note, next;
4127 label = BB_HEAD (last);
4128 if (LABEL_P (label))
4129 note = NEXT_INSN (label);
4132 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
4134 prev = PREV_INSN (label);
4135 next = NEXT_INSN (note);
4136 gcc_assert (prev && next);
4138 NEXT_INSN (prev) = next;
4139 PREV_INSN (next) = prev;
4141 bb_header[last->index] = label;
4146 last = last->prev_bb;
4151 /* Restore basic block notes.
4152 FIRST is the first basic block in the ebb. */
4154 restore_bb_notes (basic_block first)
4159 /* We DON'T unlink basic block notes of the first block in the ebb. */
4160 first = first->next_bb;
4161 /* Remember: FIRST is actually a second basic block in the ebb. */
4163 while (first != EXIT_BLOCK_PTR
4164 && bb_header[first->index])
4166 rtx prev, label, note, next;
4168 label = bb_header[first->index];
4169 prev = PREV_INSN (label);
4170 next = NEXT_INSN (prev);
4172 if (LABEL_P (label))
4173 note = NEXT_INSN (label);
4176 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
4178 bb_header[first->index] = 0;
4180 NEXT_INSN (prev) = label;
4181 NEXT_INSN (note) = next;
4182 PREV_INSN (next) = note;
4184 first = first->next_bb;
4191 /* Extend per basic block data structures of the scheduler.
4192 If BB is NULL, initialize structures for the whole CFG.
4193 Otherwise, initialize them for the just created BB. */
4199 old_last_basic_block = last_basic_block;
4201 /* The following is done to keep current_sched_info->next_tail non null. */
4203 insn = BB_END (EXIT_BLOCK_PTR->prev_bb);
4204 if (NEXT_INSN (insn) == 0
4207 /* Don't emit a NOTE if it would end up before a BARRIER. */
4208 && !BARRIER_P (NEXT_INSN (insn))))
4210 rtx note = emit_note_after (NOTE_INSN_DELETED, insn);
4211 /* Make insn appear outside BB. */
4212 set_block_for_insn (note, NULL);
4213 BB_END (EXIT_BLOCK_PTR->prev_bb) = insn;
4217 /* Add a basic block BB to extended basic block EBB.
4218 If EBB is EXIT_BLOCK_PTR, then BB is recovery block.
4219 If EBB is NULL, then BB should be a new region. */
4221 add_block (basic_block bb, basic_block ebb)
4223 gcc_assert (current_sched_info->flags & NEW_BBS);
4227 if (current_sched_info->add_block)
4228 /* This changes only data structures of the front-end. */
4229 current_sched_info->add_block (bb, ebb);
4233 Fix CFG after both in- and inter-block movement of
4234 control_flow_insn_p JUMP. */
4236 fix_jump_move (rtx jump)
4238 basic_block bb, jump_bb, jump_bb_next;
4240 bb = BLOCK_FOR_INSN (PREV_INSN (jump));
4241 jump_bb = BLOCK_FOR_INSN (jump);
4242 jump_bb_next = jump_bb->next_bb;
4244 gcc_assert (current_sched_info->flags & SCHED_EBB
4245 || IS_SPECULATION_BRANCHY_CHECK_P (jump));
4247 if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next)))
4248 /* if jump_bb_next is not empty. */
4249 BB_END (jump_bb) = BB_END (jump_bb_next);
4251 if (BB_END (bb) != PREV_INSN (jump))
4252 /* Then there are instruction after jump that should be placed
4254 BB_END (jump_bb_next) = BB_END (bb);
4256 /* Otherwise jump_bb_next is empty. */
4257 BB_END (jump_bb_next) = NEXT_INSN (BB_HEAD (jump_bb_next));
4259 /* To make assertion in move_insn happy. */
4260 BB_END (bb) = PREV_INSN (jump);
4262 update_bb_for_insn (jump_bb_next);
4265 /* Fix CFG after interblock movement of control_flow_insn_p JUMP. */
4267 move_block_after_check (rtx jump)
4269 basic_block bb, jump_bb, jump_bb_next;
4272 bb = BLOCK_FOR_INSN (PREV_INSN (jump));
4273 jump_bb = BLOCK_FOR_INSN (jump);
4274 jump_bb_next = jump_bb->next_bb;
4276 update_bb_for_insn (jump_bb);
4278 gcc_assert (IS_SPECULATION_CHECK_P (jump)
4279 || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next)));
4281 unlink_block (jump_bb_next);
4282 link_block (jump_bb_next, bb);
4286 move_succs (&(jump_bb->succs), bb);
4287 move_succs (&(jump_bb_next->succs), jump_bb);
4288 move_succs (&t, jump_bb_next);
4290 df_mark_solutions_dirty ();
4292 if (current_sched_info->fix_recovery_cfg)
4293 current_sched_info->fix_recovery_cfg
4294 (bb->index, jump_bb->index, jump_bb_next->index);
4297 /* Helper function for move_block_after_check.
4298 This functions attaches edge vector pointed to by SUCCSP to
4301 move_succs (VEC(edge,gc) **succsp, basic_block to)
4306 gcc_assert (to->succs == 0);
4308 to->succs = *succsp;
4310 FOR_EACH_EDGE (e, ei, to->succs)
4316 /* Remove INSN from the instruction stream.
4317 INSN should have any dependencies. */
4319 sched_remove_insn (rtx insn)
4321 sd_finish_insn (insn);
4323 change_queue_index (insn, QUEUE_NOWHERE);
4324 current_sched_info->add_remove_insn (insn, 1);
4328 /* Clear priorities of all instructions, that are forward dependent on INSN.
4329 Store in vector pointed to by ROOTS_PTR insns on which priority () should
4330 be invoked to initialize all cleared priorities. */
4332 clear_priorities (rtx insn, rtx_vec_t *roots_ptr)
4334 sd_iterator_def sd_it;
4336 bool insn_is_root_p = true;
4338 gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
4340 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
4342 rtx pro = DEP_PRO (dep);
4344 if (INSN_PRIORITY_STATUS (pro) >= 0
4345 && QUEUE_INDEX (insn) != QUEUE_SCHEDULED)
4347 /* If DEP doesn't contribute to priority then INSN itself should
4348 be added to priority roots. */
4349 if (contributes_to_priority_p (dep))
4350 insn_is_root_p = false;
4352 INSN_PRIORITY_STATUS (pro) = -1;
4353 clear_priorities (pro, roots_ptr);
4358 VEC_safe_push (rtx, heap, *roots_ptr, insn);
4361 /* Recompute priorities of instructions, whose priorities might have been
4362 changed. ROOTS is a vector of instructions whose priority computation will
4363 trigger initialization of all cleared priorities. */
4365 calc_priorities (rtx_vec_t roots)
4370 for (i = 0; VEC_iterate (rtx, roots, i, insn); i++)
4375 /* Add dependences between JUMP and other instructions in the recovery
4376 block. INSN is the first insn the recovery block. */
4378 add_jump_dependencies (rtx insn, rtx jump)
4382 insn = NEXT_INSN (insn);
4386 if (sd_lists_empty_p (insn, SD_LIST_FORW))
4388 dep_def _new_dep, *new_dep = &_new_dep;
4390 init_dep (new_dep, insn, jump, REG_DEP_ANTI);
4391 sd_add_dep (new_dep, false);
4396 gcc_assert (!sd_lists_empty_p (jump, SD_LIST_BACK));
4399 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
4401 bb_note (basic_block bb)
4405 note = BB_HEAD (bb);
4407 note = NEXT_INSN (note);
4409 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
4413 #ifdef ENABLE_CHECKING
4414 /* Helper function for check_cfg.
4415 Return nonzero, if edge vector pointed to by EL has edge with TYPE in
4418 has_edge_p (VEC(edge,gc) *el, int type)
4423 FOR_EACH_EDGE (e, ei, el)
4424 if (e->flags & type)
4429 /* Check few properties of CFG between HEAD and TAIL.
4430 If HEAD (TAIL) is NULL check from the beginning (till the end) of the
4431 instruction stream. */
4433 check_cfg (rtx head, rtx tail)
4437 int not_first = 0, not_last;
4440 head = get_insns ();
4442 tail = get_last_insn ();
4443 next_tail = NEXT_INSN (tail);
4447 not_last = head != tail;
4450 gcc_assert (NEXT_INSN (PREV_INSN (head)) == head);
4452 gcc_assert (PREV_INSN (NEXT_INSN (head)) == head);
4455 || (NOTE_INSN_BASIC_BLOCK_P (head)
4457 || (not_first && !LABEL_P (PREV_INSN (head))))))
4459 gcc_assert (bb == 0);
4460 bb = BLOCK_FOR_INSN (head);
4462 gcc_assert (BB_HEAD (bb) == head);
4464 /* This is the case of jump table. See inside_basic_block_p (). */
4465 gcc_assert (LABEL_P (head) && !inside_basic_block_p (head));
4470 gcc_assert (!inside_basic_block_p (head));
4471 head = NEXT_INSN (head);
4475 gcc_assert (inside_basic_block_p (head)
4477 gcc_assert (BLOCK_FOR_INSN (head) == bb);
4481 head = NEXT_INSN (head);
4482 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (head));
4486 if (control_flow_insn_p (head))
4488 gcc_assert (BB_END (bb) == head);
4490 if (any_uncondjump_p (head))
4491 gcc_assert (EDGE_COUNT (bb->succs) == 1
4492 && BARRIER_P (NEXT_INSN (head)));
4493 else if (any_condjump_p (head))
4494 gcc_assert (/* Usual case. */
4495 (EDGE_COUNT (bb->succs) > 1
4496 && !BARRIER_P (NEXT_INSN (head)))
4497 /* Or jump to the next instruction. */
4498 || (EDGE_COUNT (bb->succs) == 1
4499 && (BB_HEAD (EDGE_I (bb->succs, 0)->dest)
4500 == JUMP_LABEL (head))));
4502 if (BB_END (bb) == head)
4504 if (EDGE_COUNT (bb->succs) > 1)
4505 gcc_assert (control_flow_insn_p (head)
4506 || has_edge_p (bb->succs, EDGE_COMPLEX));
4510 head = NEXT_INSN (head);
4516 while (head != next_tail);
4518 gcc_assert (bb == 0);
4521 /* Perform a few consistency checks of flags in different data structures. */
4523 check_sched_flags (void)
4525 unsigned int f = current_sched_info->flags;
4527 if (flag_sched_stalled_insns)
4528 gcc_assert (!(f & DO_SPECULATION));
4529 if (f & DO_SPECULATION)
4530 gcc_assert (!flag_sched_stalled_insns
4532 && spec_info->mask);
4534 #endif /* ENABLE_CHECKING */
4536 #endif /* INSN_SCHEDULING */