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 2, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING. If not, write to the Free
21 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 /* Instruction scheduling pass. This file, along with sched-deps.c,
25 contains the generic parts. The actual entry point is found for
26 the normal instruction scheduling pass is found in sched-rgn.c.
28 We compute insn priorities based on data dependencies. Flow
29 analysis only creates a fraction of the data-dependencies we must
30 observe: namely, only those dependencies which the combiner can be
31 expected to use. For this pass, we must therefore create the
32 remaining dependencies we need to observe: register dependencies,
33 memory dependencies, dependencies to keep function calls in order,
34 and the dependence between a conditional branch and the setting of
35 condition codes are all dealt with here.
37 The scheduler first traverses the data flow graph, starting with
38 the last instruction, and proceeding to the first, assigning values
39 to insn_priority as it goes. This sorts the instructions
40 topologically by data dependence.
42 Once priorities have been established, we order the insns using
43 list scheduling. This works as follows: starting with a list of
44 all the ready insns, and sorted according to priority number, we
45 schedule the insn from the end of the list by placing its
46 predecessors in the list according to their priority order. We
47 consider this insn scheduled by setting the pointer to the "end" of
48 the list to point to the previous insn. When an insn has no
49 predecessors, we either queue it until sufficient time has elapsed
50 or add it to the ready list. As the instructions are scheduled or
51 when stalls are introduced, the queue advances and dumps insns into
52 the ready list. When all insns down to the lowest priority have
53 been scheduled, the critical path of the basic block has been made
54 as short as possible. The remaining insns are then scheduled in
57 The following list shows the order in which we want to break ties
58 among insns in the ready list:
60 1. choose insn with the longest path to end of bb, ties
62 2. choose insn with least contribution to register pressure,
64 3. prefer in-block upon interblock motion, ties broken by
65 4. prefer useful upon speculative motion, ties broken by
66 5. choose insn with largest control flow probability, ties
68 6. choose insn with the least dependences upon the previously
69 scheduled insn, or finally
70 7 choose the insn which has the most insns dependent on it.
71 8. choose insn with lowest UID.
73 Memory references complicate matters. Only if we can be certain
74 that memory references are not part of the data dependency graph
75 (via true, anti, or output dependence), can we move operations past
76 memory references. To first approximation, reads can be done
77 independently, while writes introduce dependencies. Better
78 approximations will yield fewer dependencies.
80 Before reload, an extended analysis of interblock data dependences
81 is required for interblock scheduling. This is performed in
82 compute_block_backward_dependences ().
84 Dependencies set up by memory references are treated in exactly the
85 same way as other dependencies, by using insn backward dependences
86 INSN_BACK_DEPS. INSN_BACK_DEPS are translated into forward dependences
87 INSN_FORW_DEPS the purpose of forward list scheduling.
89 Having optimized the critical path, we may have also unduly
90 extended the lifetimes of some registers. If an operation requires
91 that constants be loaded into registers, it is certainly desirable
92 to load those constants as early as necessary, but no earlier.
93 I.e., it will not do to load up a bunch of registers at the
94 beginning of a basic block only to use them at the end, if they
95 could be loaded later, since this may result in excessive register
98 Note that since branches are never in basic blocks, but only end
99 basic blocks, this pass will not move branches. But that is ok,
100 since we can use GNU's delayed branch scheduling pass to take care
103 Also note that no further optimizations based on algebraic
104 identities are performed, so this pass would be a good one to
105 perform instruction splitting, such as breaking up a multiply
106 instruction into shifts and adds where that is profitable.
108 Given the memory aliasing analysis that this pass should perform,
109 it should be possible to remove redundant stores to memory, and to
110 load values from registers instead of hitting memory.
112 Before reload, speculative insns are moved only if a 'proof' exists
113 that no exception will be caused by this, and if no live registers
114 exist that inhibit the motion (live registers constraints are not
115 represented by data dependence edges).
117 This pass must update information that subsequent passes expect to
118 be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
119 reg_n_calls_crossed, and reg_live_length. Also, BB_HEAD, BB_END.
121 The information in the line number notes is carefully retained by
122 this pass. Notes that refer to the starting and ending of
123 exception regions are also carefully retained by this pass. All
124 other NOTE insns are grouped in their same relative order at the
125 beginning of basic blocks and regions that have been scheduled. */
129 #include "coretypes.h"
134 #include "hard-reg-set.h"
136 #include "function.h"
138 #include "insn-config.h"
139 #include "insn-attr.h"
143 #include "sched-int.h"
149 #ifdef INSN_SCHEDULING
151 /* issue_rate is the number of insns that can be scheduled in the same
152 machine cycle. It can be defined in the config/mach/mach.h file,
153 otherwise we set it to 1. */
155 static int issue_rate
;
157 /* sched-verbose controls the amount of debugging output the
158 scheduler prints. It is controlled by -fsched-verbose=N:
159 N>0 and no -DSR : the output is directed to stderr.
160 N>=10 will direct the printouts to stderr (regardless of -dSR).
162 N=2: bb's probabilities, detailed ready list info, unit/insn info.
163 N=3: rtl at abort point, control-flow, regions info.
164 N=5: dependences info. */
166 static int sched_verbose_param
= 0;
167 int sched_verbose
= 0;
169 /* Debugging file. All printouts are sent to dump, which is always set,
170 either to stderr, or to the dump listing file (-dRS). */
171 FILE *sched_dump
= 0;
173 /* Highest uid before scheduling. */
174 static int old_max_uid
;
176 /* fix_sched_param() is called from toplev.c upon detection
177 of the -fsched-verbose=N option. */
180 fix_sched_param (const char *param
, const char *val
)
182 if (!strcmp (param
, "verbose"))
183 sched_verbose_param
= atoi (val
);
185 warning (0, "fix_sched_param: unknown param: %s", param
);
188 struct haifa_insn_data
*h_i_d
;
190 #define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick)
191 #define INTER_TICK(INSN) (h_i_d[INSN_UID (INSN)].inter_tick)
193 /* If INSN_TICK of an instruction is equal to INVALID_TICK,
194 then it should be recalculated from scratch. */
195 #define INVALID_TICK (-(max_insn_queue_index + 1))
196 /* The minimal value of the INSN_TICK of an instruction. */
197 #define MIN_TICK (-max_insn_queue_index)
199 /* Issue points are used to distinguish between instructions in max_issue ().
200 For now, all instructions are equally good. */
201 #define ISSUE_POINTS(INSN) 1
203 /* List of important notes we must keep around. This is a pointer to the
204 last element in the list. */
205 static rtx note_list
;
207 static struct spec_info_def spec_info_var
;
208 /* Description of the speculative part of the scheduling.
209 If NULL - no speculation. */
210 static spec_info_t spec_info
;
212 /* True, if recovery block was added during scheduling of current block.
213 Used to determine, if we need to fix INSN_TICKs. */
214 static bool added_recovery_block_p
;
216 /* Counters of different types of speculative instructions. */
217 static int nr_begin_data
, nr_be_in_data
, nr_begin_control
, nr_be_in_control
;
219 /* Array used in {unlink, restore}_bb_notes. */
220 static rtx
*bb_header
= 0;
222 /* Number of basic_blocks. */
223 static int old_last_basic_block
;
225 /* Basic block after which recovery blocks will be created. */
226 static basic_block before_recovery
;
230 /* An instruction is ready to be scheduled when all insns preceding it
231 have already been scheduled. It is important to ensure that all
232 insns which use its result will not be executed until its result
233 has been computed. An insn is maintained in one of four structures:
235 (P) the "Pending" set of insns which cannot be scheduled until
236 their dependencies have been satisfied.
237 (Q) the "Queued" set of insns that can be scheduled when sufficient
239 (R) the "Ready" list of unscheduled, uncommitted insns.
240 (S) the "Scheduled" list of insns.
242 Initially, all insns are either "Pending" or "Ready" depending on
243 whether their dependencies are satisfied.
245 Insns move from the "Ready" list to the "Scheduled" list as they
246 are committed to the schedule. As this occurs, the insns in the
247 "Pending" list have their dependencies satisfied and move to either
248 the "Ready" list or the "Queued" set depending on whether
249 sufficient time has passed to make them ready. As time passes,
250 insns move from the "Queued" set to the "Ready" list.
252 The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
253 unscheduled insns, i.e., those that are ready, queued, and pending.
254 The "Queued" set (Q) is implemented by the variable `insn_queue'.
255 The "Ready" list (R) is implemented by the variables `ready' and
257 The "Scheduled" list (S) is the new insn chain built by this pass.
259 The transition (R->S) is implemented in the scheduling loop in
260 `schedule_block' when the best insn to schedule is chosen.
261 The transitions (P->R and P->Q) are implemented in `schedule_insn' as
262 insns move from the ready list to the scheduled list.
263 The transition (Q->R) is implemented in 'queue_to_insn' as time
264 passes or stalls are introduced. */
266 /* Implement a circular buffer to delay instructions until sufficient
267 time has passed. For the new pipeline description interface,
268 MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
269 than maximal time of instruction execution computed by genattr.c on
270 the base maximal time of functional unit reservations and getting a
271 result. This is the longest time an insn may be queued. */
273 static rtx
*insn_queue
;
274 static int q_ptr
= 0;
275 static int q_size
= 0;
276 #define NEXT_Q(X) (((X)+1) & max_insn_queue_index)
277 #define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index)
279 #define QUEUE_SCHEDULED (-3)
280 #define QUEUE_NOWHERE (-2)
281 #define QUEUE_READY (-1)
282 /* QUEUE_SCHEDULED - INSN is scheduled.
283 QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in
285 QUEUE_READY - INSN is in ready list.
286 N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */
288 #define QUEUE_INDEX(INSN) (h_i_d[INSN_UID (INSN)].queue_index)
290 /* The following variable value refers for all current and future
291 reservations of the processor units. */
294 /* The following variable value is size of memory representing all
295 current and future reservations of the processor units. */
296 static size_t dfa_state_size
;
298 /* The following array is used to find the best insn from ready when
299 the automaton pipeline interface is used. */
300 static char *ready_try
;
302 /* Describe the ready list of the scheduler.
303 VEC holds space enough for all insns in the current region. VECLEN
304 says how many exactly.
305 FIRST is the index of the element with the highest priority; i.e. the
306 last one in the ready list, since elements are ordered by ascending
308 N_READY determines how many insns are on the ready list. */
318 /* The pointer to the ready list. */
319 static struct ready_list
*readyp
;
321 /* Scheduling clock. */
322 static int clock_var
;
324 /* Number of instructions in current scheduling region. */
325 static int rgn_n_insns
;
327 static int may_trap_exp (rtx
, int);
329 /* Nonzero iff the address is comprised from at most 1 register. */
330 #define CONST_BASED_ADDRESS_P(x) \
332 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
333 || (GET_CODE (x) == LO_SUM)) \
334 && (CONSTANT_P (XEXP (x, 0)) \
335 || CONSTANT_P (XEXP (x, 1)))))
337 /* Returns a class that insn with GET_DEST(insn)=x may belong to,
338 as found by analyzing insn's expression. */
341 may_trap_exp (rtx x
, int is_store
)
350 if (code
== MEM
&& may_trap_p (x
))
357 /* The insn uses memory: a volatile load. */
358 if (MEM_VOLATILE_P (x
))
360 /* An exception-free load. */
363 /* A load with 1 base register, to be further checked. */
364 if (CONST_BASED_ADDRESS_P (XEXP (x
, 0)))
365 return PFREE_CANDIDATE
;
366 /* No info on the load, to be further checked. */
367 return PRISKY_CANDIDATE
;
372 int i
, insn_class
= TRAP_FREE
;
374 /* Neither store nor load, check if it may cause a trap. */
377 /* Recursive step: walk the insn... */
378 fmt
= GET_RTX_FORMAT (code
);
379 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
383 int tmp_class
= may_trap_exp (XEXP (x
, i
), is_store
);
384 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
386 else if (fmt
[i
] == 'E')
389 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
391 int tmp_class
= may_trap_exp (XVECEXP (x
, i
, j
), is_store
);
392 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
393 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
397 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
404 /* Classifies insn for the purpose of verifying that it can be
405 moved speculatively, by examining it's patterns, returning:
406 TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
407 TRAP_FREE: non-load insn.
408 IFREE: load from a globally safe location.
409 IRISKY: volatile load.
410 PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
411 being either PFREE or PRISKY. */
414 haifa_classify_insn (rtx insn
)
416 rtx pat
= PATTERN (insn
);
417 int tmp_class
= TRAP_FREE
;
418 int insn_class
= TRAP_FREE
;
421 if (GET_CODE (pat
) == PARALLEL
)
423 int i
, len
= XVECLEN (pat
, 0);
425 for (i
= len
- 1; i
>= 0; i
--)
427 code
= GET_CODE (XVECEXP (pat
, 0, i
));
431 /* Test if it is a 'store'. */
432 tmp_class
= may_trap_exp (XEXP (XVECEXP (pat
, 0, i
), 0), 1);
435 /* Test if it is a store. */
436 tmp_class
= may_trap_exp (SET_DEST (XVECEXP (pat
, 0, i
)), 1);
437 if (tmp_class
== TRAP_RISKY
)
439 /* Test if it is a load. */
441 = WORST_CLASS (tmp_class
,
442 may_trap_exp (SET_SRC (XVECEXP (pat
, 0, i
)),
447 tmp_class
= TRAP_RISKY
;
452 insn_class
= WORST_CLASS (insn_class
, tmp_class
);
453 if (insn_class
== TRAP_RISKY
|| insn_class
== IRISKY
)
459 code
= GET_CODE (pat
);
463 /* Test if it is a 'store'. */
464 tmp_class
= may_trap_exp (XEXP (pat
, 0), 1);
467 /* Test if it is a store. */
468 tmp_class
= may_trap_exp (SET_DEST (pat
), 1);
469 if (tmp_class
== TRAP_RISKY
)
471 /* Test if it is a load. */
473 WORST_CLASS (tmp_class
,
474 may_trap_exp (SET_SRC (pat
), 0));
478 tmp_class
= TRAP_RISKY
;
482 insn_class
= tmp_class
;
488 /* A typedef for rtx vector. */
489 typedef VEC(rtx
, heap
) *rtx_vec_t
;
491 /* Forward declarations. */
493 static int priority (rtx
);
494 static int rank_for_schedule (const void *, const void *);
495 static void swap_sort (rtx
*, int);
496 static void queue_insn (rtx
, int);
497 static int schedule_insn (rtx
);
498 static int find_set_reg_weight (rtx
);
499 static void find_insn_reg_weight (basic_block
);
500 static void find_insn_reg_weight1 (rtx
);
501 static void adjust_priority (rtx
);
502 static void advance_one_cycle (void);
504 /* Notes handling mechanism:
505 =========================
506 Generally, NOTES are saved before scheduling and restored after scheduling.
507 The scheduler distinguishes between two types of notes:
509 (1) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes:
510 Before scheduling a region, a pointer to the note is added to the insn
511 that follows or precedes it. (This happens as part of the data dependence
512 computation). After scheduling an insn, the pointer contained in it is
513 used for regenerating the corresponding note (in reemit_notes).
515 (2) All other notes (e.g. INSN_DELETED): Before scheduling a block,
516 these notes are put in a list (in rm_other_notes() and
517 unlink_other_notes ()). After scheduling the block, these notes are
518 inserted at the beginning of the block (in schedule_block()). */
520 static rtx
unlink_other_notes (rtx
, rtx
);
521 static void reemit_notes (rtx
);
523 static rtx
*ready_lastpos (struct ready_list
*);
524 static void ready_add (struct ready_list
*, rtx
, bool);
525 static void ready_sort (struct ready_list
*);
526 static rtx
ready_remove_first (struct ready_list
*);
528 static void queue_to_ready (struct ready_list
*);
529 static int early_queue_to_ready (state_t
, struct ready_list
*);
531 static void debug_ready_list (struct ready_list
*);
533 static void move_insn (rtx
);
535 /* The following functions are used to implement multi-pass scheduling
536 on the first cycle. */
537 static rtx
ready_element (struct ready_list
*, int);
538 static rtx
ready_remove (struct ready_list
*, int);
539 static void ready_remove_insn (rtx
);
540 static int max_issue (struct ready_list
*, int *, int);
542 static int choose_ready (struct ready_list
*, rtx
*);
544 static void fix_inter_tick (rtx
, rtx
);
545 static int fix_tick_ready (rtx
);
546 static void change_queue_index (rtx
, int);
548 /* The following functions are used to implement scheduling of data/control
549 speculative instructions. */
551 static void extend_h_i_d (void);
552 static void extend_ready (int);
553 static void extend_global (rtx
);
554 static void extend_all (rtx
);
555 static void init_h_i_d (rtx
);
556 static void generate_recovery_code (rtx
);
557 static void process_insn_forw_deps_be_in_spec (deps_list_t
, rtx
, ds_t
);
558 static void begin_speculative_block (rtx
);
559 static void add_to_speculative_block (rtx
);
560 static dw_t
dep_weak (ds_t
);
561 static edge
find_fallthru_edge (basic_block
);
562 static void init_before_recovery (void);
563 static basic_block
create_recovery_block (void);
564 static void create_check_block_twin (rtx
, bool);
565 static void fix_recovery_deps (basic_block
);
566 static void change_pattern (rtx
, rtx
);
567 static int speculate_insn (rtx
, ds_t
, rtx
*);
568 static void dump_new_block_header (int, basic_block
, rtx
, rtx
);
569 static void restore_bb_notes (basic_block
);
570 static void extend_bb (void);
571 static void fix_jump_move (rtx
);
572 static void move_block_after_check (rtx
);
573 static void move_succs (VEC(edge
,gc
) **, basic_block
);
574 static void sched_remove_insn (rtx
);
575 static void clear_priorities (rtx
, rtx_vec_t
*);
576 static void calc_priorities (rtx_vec_t
);
577 static void add_jump_dependencies (rtx
, rtx
);
578 #ifdef ENABLE_CHECKING
579 static int has_edge_p (VEC(edge
,gc
) *, int);
580 static void check_cfg (rtx
, rtx
);
581 static void check_sched_flags (void);
584 #endif /* INSN_SCHEDULING */
586 /* Point to state used for the current scheduling pass. */
587 struct sched_info
*current_sched_info
;
589 #ifndef INSN_SCHEDULING
591 schedule_insns (void)
596 /* Working copy of frontend's sched_info variable. */
597 static struct sched_info current_sched_info_var
;
599 /* Pointer to the last instruction scheduled. Used by rank_for_schedule,
600 so that insns independent of the last scheduled insn will be preferred
601 over dependent instructions. */
603 static rtx last_scheduled_insn
;
605 /* Cached cost of the instruction. Use below function to get cost of the
606 insn. -1 here means that the field is not initialized. */
607 #define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost)
609 /* Compute cost of executing INSN.
610 This is the number of cycles between instruction issue and
611 instruction results. */
615 int cost
= INSN_COST (insn
);
619 /* A USE insn, or something else we don't need to
620 understand. We can't pass these directly to
621 result_ready_cost or insn_default_latency because it will
622 trigger a fatal error for unrecognizable insns. */
623 if (recog_memoized (insn
) < 0)
625 INSN_COST (insn
) = 0;
630 cost
= insn_default_latency (insn
);
634 INSN_COST (insn
) = cost
;
641 /* Compute cost of dependence LINK.
642 This is the number of cycles between instruction issue and
643 instruction results. */
645 dep_cost (dep_t link
)
647 rtx used
= DEP_CON (link
);
650 /* A USE insn should never require the value used to be computed.
651 This allows the computation of a function's result and parameter
652 values to overlap the return and call. */
653 if (recog_memoized (used
) < 0)
657 rtx insn
= DEP_PRO (link
);
658 enum reg_note dep_type
= DEP_KIND (link
);
660 cost
= insn_cost (insn
);
662 if (INSN_CODE (insn
) >= 0)
664 if (dep_type
== REG_DEP_ANTI
)
666 else if (dep_type
== REG_DEP_OUTPUT
)
668 cost
= (insn_default_latency (insn
)
669 - insn_default_latency (used
));
673 else if (bypass_p (insn
))
674 cost
= insn_latency (insn
, used
);
677 if (targetm
.sched
.adjust_cost
!= NULL
)
679 /* This variable is used for backward compatibility with the
681 rtx dep_cost_rtx_link
= alloc_INSN_LIST (NULL_RTX
, NULL_RTX
);
683 /* Make it self-cycled, so that if some tries to walk over this
684 incomplete list he/she will be caught in an endless loop. */
685 XEXP (dep_cost_rtx_link
, 1) = dep_cost_rtx_link
;
687 /* Targets use only REG_NOTE_KIND of the link. */
688 PUT_REG_NOTE_KIND (dep_cost_rtx_link
, DEP_KIND (link
));
690 cost
= targetm
.sched
.adjust_cost (used
, dep_cost_rtx_link
,
693 free_INSN_LIST_node (dep_cost_rtx_link
);
703 /* Return 'true' if DEP should be included in priority calculations. */
705 contributes_to_priority_p (dep_t dep
)
707 /* Critical path is meaningful in block boundaries only. */
708 if (!current_sched_info
->contributes_to_priority (DEP_CON (dep
),
712 /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
713 then speculative instructions will less likely be
714 scheduled. That is because the priority of
715 their producers will increase, and, thus, the
716 producers will more likely be scheduled, thus,
717 resolving the dependence. */
718 if ((current_sched_info
->flags
& DO_SPECULATION
)
719 && !(spec_info
->flags
& COUNT_SPEC_IN_CRITICAL_PATH
)
720 && (DEP_STATUS (dep
) & SPECULATIVE
))
726 /* Compute the priority number for INSN. */
735 /* We should not be interested in priority of an already scheduled insn. */
736 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
);
738 if (!INSN_PRIORITY_KNOWN (insn
))
740 int this_priority
= 0;
742 if (deps_list_empty_p (INSN_FORW_DEPS (insn
)))
743 /* ??? We should set INSN_PRIORITY to insn_cost when and insn has
744 some forward deps but all of them are ignored by
745 contributes_to_priority hook. At the moment we set priority of
747 this_priority
= insn_cost (insn
);
750 rtx prev_first
, twin
;
753 /* For recovery check instructions we calculate priority slightly
754 different than that of normal instructions. Instead of walking
755 through INSN_FORW_DEPS (check) list, we walk through
756 INSN_FORW_DEPS list of each instruction in the corresponding
759 rec
= RECOVERY_BLOCK (insn
);
760 if (!rec
|| rec
== EXIT_BLOCK_PTR
)
762 prev_first
= PREV_INSN (insn
);
767 prev_first
= NEXT_INSN (BB_HEAD (rec
));
768 twin
= PREV_INSN (BB_END (rec
));
773 FOR_EACH_DEP_LINK (link
, INSN_FORW_DEPS (twin
))
777 dep_t dep
= DEP_LINK_DEP (link
);
779 next
= DEP_CON (dep
);
781 if (BLOCK_FOR_INSN (next
) != rec
)
785 if (!contributes_to_priority_p (dep
))
789 cost
= dep_cost (dep
);
792 struct _dep _dep1
, *dep1
= &_dep1
;
794 init_dep (dep1
, insn
, next
, REG_DEP_ANTI
);
796 cost
= dep_cost (dep1
);
799 next_priority
= cost
+ priority (next
);
801 if (next_priority
> this_priority
)
802 this_priority
= next_priority
;
806 twin
= PREV_INSN (twin
);
808 while (twin
!= prev_first
);
810 INSN_PRIORITY (insn
) = this_priority
;
811 INSN_PRIORITY_STATUS (insn
) = 1;
814 return INSN_PRIORITY (insn
);
817 /* Macros and functions for keeping the priority queue sorted, and
818 dealing with queuing and dequeuing of instructions. */
820 #define SCHED_SORT(READY, N_READY) \
821 do { if ((N_READY) == 2) \
822 swap_sort (READY, N_READY); \
823 else if ((N_READY) > 2) \
824 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
827 /* Returns a positive value if x is preferred; returns a negative value if
828 y is preferred. Should never return 0, since that will make the sort
832 rank_for_schedule (const void *x
, const void *y
)
834 rtx tmp
= *(const rtx
*) y
;
835 rtx tmp2
= *(const rtx
*) x
;
836 dep_link_t link1
, link2
;
837 int tmp_class
, tmp2_class
;
838 int val
, priority_val
, weight_val
, info_val
;
840 /* The insn in a schedule group should be issued the first. */
841 if (SCHED_GROUP_P (tmp
) != SCHED_GROUP_P (tmp2
))
842 return SCHED_GROUP_P (tmp2
) ? 1 : -1;
844 /* Make sure that priority of TMP and TMP2 are initialized. */
845 gcc_assert (INSN_PRIORITY_KNOWN (tmp
) && INSN_PRIORITY_KNOWN (tmp2
));
847 /* Prefer insn with higher priority. */
848 priority_val
= INSN_PRIORITY (tmp2
) - INSN_PRIORITY (tmp
);
853 /* Prefer speculative insn with greater dependencies weakness. */
860 ds1
= TODO_SPEC (tmp
) & SPECULATIVE
;
862 dw1
= dep_weak (ds1
);
866 ds2
= TODO_SPEC (tmp2
) & SPECULATIVE
;
868 dw2
= dep_weak (ds2
);
873 if (dw
> (NO_DEP_WEAK
/ 8) || dw
< -(NO_DEP_WEAK
/ 8))
877 /* Prefer an insn with smaller contribution to registers-pressure. */
878 if (!reload_completed
&&
879 (weight_val
= INSN_REG_WEIGHT (tmp
) - INSN_REG_WEIGHT (tmp2
)))
882 info_val
= (*current_sched_info
->rank
) (tmp
, tmp2
);
886 /* Compare insns based on their relation to the last-scheduled-insn. */
887 if (INSN_P (last_scheduled_insn
))
889 /* Classify the instructions into three classes:
890 1) Data dependent on last schedule insn.
891 2) Anti/Output dependent on last scheduled insn.
892 3) Independent of last scheduled insn, or has latency of one.
893 Choose the insn from the highest numbered class if different. */
895 = find_link_by_con_in_deps_list (INSN_FORW_DEPS (last_scheduled_insn
),
898 if (link1
== NULL
|| dep_cost (DEP_LINK_DEP (link1
)) == 1)
900 else if (/* Data dependence. */
901 DEP_LINK_KIND (link1
) == REG_DEP_TRUE
)
907 = find_link_by_con_in_deps_list (INSN_FORW_DEPS (last_scheduled_insn
),
910 if (link2
== NULL
|| dep_cost (DEP_LINK_DEP (link2
)) == 1)
912 else if (/* Data dependence. */
913 DEP_LINK_KIND (link2
) == REG_DEP_TRUE
)
918 if ((val
= tmp2_class
- tmp_class
))
922 /* Prefer the insn which has more later insns that depend on it.
923 This gives the scheduler more freedom when scheduling later
924 instructions at the expense of added register pressure. */
926 link1
= DEPS_LIST_FIRST (INSN_FORW_DEPS (tmp
));
927 link2
= DEPS_LIST_FIRST (INSN_FORW_DEPS (tmp2
));
929 while (link1
!= NULL
&& link2
!= NULL
)
931 link1
= DEP_LINK_NEXT (link1
);
932 link2
= DEP_LINK_NEXT (link2
);
935 if (link1
!= NULL
&& link2
== NULL
)
936 /* TMP (Y) has more insns that depend on it. */
938 if (link1
== NULL
&& link2
!= NULL
)
939 /* TMP2 (X) has more insns that depend on it. */
942 /* If insns are equally good, sort by INSN_LUID (original insn order),
943 so that we make the sort stable. This minimizes instruction movement,
944 thus minimizing sched's effect on debugging and cross-jumping. */
945 return INSN_LUID (tmp
) - INSN_LUID (tmp2
);
948 /* Resort the array A in which only element at index N may be out of order. */
950 HAIFA_INLINE
static void
951 swap_sort (rtx
*a
, int n
)
956 while (i
>= 0 && rank_for_schedule (a
+ i
, &insn
) >= 0)
964 /* Add INSN to the insn queue so that it can be executed at least
965 N_CYCLES after the currently executing insn. Preserve insns
966 chain for debugging purposes. */
968 HAIFA_INLINE
static void
969 queue_insn (rtx insn
, int n_cycles
)
971 int next_q
= NEXT_Q_AFTER (q_ptr
, n_cycles
);
972 rtx link
= alloc_INSN_LIST (insn
, insn_queue
[next_q
]);
974 gcc_assert (n_cycles
<= max_insn_queue_index
);
976 insn_queue
[next_q
] = link
;
979 if (sched_verbose
>= 2)
981 fprintf (sched_dump
, ";;\t\tReady-->Q: insn %s: ",
982 (*current_sched_info
->print_insn
) (insn
, 0));
984 fprintf (sched_dump
, "queued for %d cycles.\n", n_cycles
);
987 QUEUE_INDEX (insn
) = next_q
;
990 /* Remove INSN from queue. */
992 queue_remove (rtx insn
)
994 gcc_assert (QUEUE_INDEX (insn
) >= 0);
995 remove_free_INSN_LIST_elem (insn
, &insn_queue
[QUEUE_INDEX (insn
)]);
997 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
1000 /* Return a pointer to the bottom of the ready list, i.e. the insn
1001 with the lowest priority. */
1003 HAIFA_INLINE
static rtx
*
1004 ready_lastpos (struct ready_list
*ready
)
1006 gcc_assert (ready
->n_ready
>= 1);
1007 return ready
->vec
+ ready
->first
- ready
->n_ready
+ 1;
1010 /* Add an element INSN to the ready list so that it ends up with the
1011 lowest/highest priority depending on FIRST_P. */
1013 HAIFA_INLINE
static void
1014 ready_add (struct ready_list
*ready
, rtx insn
, bool first_p
)
1018 if (ready
->first
== ready
->n_ready
)
1020 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
,
1021 ready_lastpos (ready
),
1022 ready
->n_ready
* sizeof (rtx
));
1023 ready
->first
= ready
->veclen
- 1;
1025 ready
->vec
[ready
->first
- ready
->n_ready
] = insn
;
1029 if (ready
->first
== ready
->veclen
- 1)
1032 /* ready_lastpos() fails when called with (ready->n_ready == 0). */
1033 memmove (ready
->vec
+ ready
->veclen
- ready
->n_ready
- 1,
1034 ready_lastpos (ready
),
1035 ready
->n_ready
* sizeof (rtx
));
1036 ready
->first
= ready
->veclen
- 2;
1038 ready
->vec
[++(ready
->first
)] = insn
;
1043 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_READY
);
1044 QUEUE_INDEX (insn
) = QUEUE_READY
;
1047 /* Remove the element with the highest priority from the ready list and
1050 HAIFA_INLINE
static rtx
1051 ready_remove_first (struct ready_list
*ready
)
1055 gcc_assert (ready
->n_ready
);
1056 t
= ready
->vec
[ready
->first
--];
1058 /* If the queue becomes empty, reset it. */
1059 if (ready
->n_ready
== 0)
1060 ready
->first
= ready
->veclen
- 1;
1062 gcc_assert (QUEUE_INDEX (t
) == QUEUE_READY
);
1063 QUEUE_INDEX (t
) = QUEUE_NOWHERE
;
1068 /* The following code implements multi-pass scheduling for the first
1069 cycle. In other words, we will try to choose ready insn which
1070 permits to start maximum number of insns on the same cycle. */
1072 /* Return a pointer to the element INDEX from the ready. INDEX for
1073 insn with the highest priority is 0, and the lowest priority has
1076 HAIFA_INLINE
static rtx
1077 ready_element (struct ready_list
*ready
, int index
)
1079 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
1081 return ready
->vec
[ready
->first
- index
];
1084 /* Remove the element INDEX from the ready list and return it. INDEX
1085 for insn with the highest priority is 0, and the lowest priority
1088 HAIFA_INLINE
static rtx
1089 ready_remove (struct ready_list
*ready
, int index
)
1095 return ready_remove_first (ready
);
1096 gcc_assert (ready
->n_ready
&& index
< ready
->n_ready
);
1097 t
= ready
->vec
[ready
->first
- index
];
1099 for (i
= index
; i
< ready
->n_ready
; i
++)
1100 ready
->vec
[ready
->first
- i
] = ready
->vec
[ready
->first
- i
- 1];
1101 QUEUE_INDEX (t
) = QUEUE_NOWHERE
;
1105 /* Remove INSN from the ready list. */
1107 ready_remove_insn (rtx insn
)
1111 for (i
= 0; i
< readyp
->n_ready
; i
++)
1112 if (ready_element (readyp
, i
) == insn
)
1114 ready_remove (readyp
, i
);
1120 /* Sort the ready list READY by ascending priority, using the SCHED_SORT
1123 HAIFA_INLINE
static void
1124 ready_sort (struct ready_list
*ready
)
1126 rtx
*first
= ready_lastpos (ready
);
1127 SCHED_SORT (first
, ready
->n_ready
);
1130 /* PREV is an insn that is ready to execute. Adjust its priority if that
1131 will help shorten or lengthen register lifetimes as appropriate. Also
1132 provide a hook for the target to tweek itself. */
1134 HAIFA_INLINE
static void
1135 adjust_priority (rtx prev
)
1137 /* ??? There used to be code here to try and estimate how an insn
1138 affected register lifetimes, but it did it by looking at REG_DEAD
1139 notes, which we removed in schedule_region. Nor did it try to
1140 take into account register pressure or anything useful like that.
1142 Revisit when we have a machine model to work with and not before. */
1144 if (targetm
.sched
.adjust_priority
)
1145 INSN_PRIORITY (prev
) =
1146 targetm
.sched
.adjust_priority (prev
, INSN_PRIORITY (prev
));
1149 /* Advance time on one cycle. */
1150 HAIFA_INLINE
static void
1151 advance_one_cycle (void)
1153 if (targetm
.sched
.dfa_pre_cycle_insn
)
1154 state_transition (curr_state
,
1155 targetm
.sched
.dfa_pre_cycle_insn ());
1157 state_transition (curr_state
, NULL
);
1159 if (targetm
.sched
.dfa_post_cycle_insn
)
1160 state_transition (curr_state
,
1161 targetm
.sched
.dfa_post_cycle_insn ());
1164 /* Clock at which the previous instruction was issued. */
1165 static int last_clock_var
;
1167 /* INSN is the "currently executing insn". Launch each insn which was
1168 waiting on INSN. READY is the ready list which contains the insns
1169 that are ready to fire. CLOCK is the current cycle. The function
1170 returns necessary cycle advance after issuing the insn (it is not
1171 zero for insns in a schedule group). */
1174 schedule_insn (rtx insn
)
1179 if (sched_verbose
>= 1)
1183 print_insn (buf
, insn
, 0);
1185 fprintf (sched_dump
, ";;\t%3i--> %-40s:", clock_var
, buf
);
1187 if (recog_memoized (insn
) < 0)
1188 fprintf (sched_dump
, "nothing");
1190 print_reservation (sched_dump
, insn
);
1191 fputc ('\n', sched_dump
);
1194 /* Scheduling instruction should have all its dependencies resolved and
1195 should have been removed from the ready list. */
1196 gcc_assert (INSN_DEP_COUNT (insn
) == 0
1197 && deps_list_empty_p (INSN_BACK_DEPS (insn
)));
1198 free_deps_list (INSN_BACK_DEPS (insn
));
1200 /* Now we can free INSN_RESOLVED_BACK_DEPS list. */
1201 delete_deps_list (INSN_RESOLVED_BACK_DEPS (insn
));
1203 gcc_assert (QUEUE_INDEX (insn
) == QUEUE_NOWHERE
);
1204 QUEUE_INDEX (insn
) = QUEUE_SCHEDULED
;
1206 gcc_assert (INSN_TICK (insn
) >= MIN_TICK
);
1207 if (INSN_TICK (insn
) > clock_var
)
1208 /* INSN has been prematurely moved from the queue to the ready list.
1209 This is possible only if following flag is set. */
1210 gcc_assert (flag_sched_stalled_insns
);
1212 /* ??? Probably, if INSN is scheduled prematurely, we should leave
1213 INSN_TICK untouched. This is a machine-dependent issue, actually. */
1214 INSN_TICK (insn
) = clock_var
;
1216 /* Update dependent instructions. */
1217 FOR_EACH_DEP_LINK (link
, INSN_FORW_DEPS (insn
))
1219 rtx next
= DEP_LINK_CON (link
);
1221 /* Resolve the dependence between INSN and NEXT. */
1223 INSN_DEP_COUNT (next
)--;
1225 move_dep_link (DEP_NODE_BACK (DEP_LINK_NODE (link
)),
1226 INSN_RESOLVED_BACK_DEPS (next
));
1228 gcc_assert ((INSN_DEP_COUNT (next
) == 0)
1229 == deps_list_empty_p (INSN_BACK_DEPS (next
)));
1231 if (!IS_SPECULATION_BRANCHY_CHECK_P (insn
))
1235 effective_cost
= try_ready (next
);
1237 if (effective_cost
>= 0
1238 && SCHED_GROUP_P (next
)
1239 && advance
< effective_cost
)
1240 advance
= effective_cost
;
1243 /* Check always has only one forward dependence (to the first insn in
1244 the recovery block), therefore, this will be executed only once. */
1246 gcc_assert (DEP_LINK_NEXT (link
) == NULL
);
1247 fix_recovery_deps (RECOVERY_BLOCK (insn
));
1251 /* Annotate the instruction with issue information -- TImode
1252 indicates that the instruction is expected not to be able
1253 to issue on the same cycle as the previous insn. A machine
1254 may use this information to decide how the instruction should
1257 && GET_CODE (PATTERN (insn
)) != USE
1258 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
1260 if (reload_completed
)
1261 PUT_MODE (insn
, clock_var
> last_clock_var
? TImode
: VOIDmode
);
1262 last_clock_var
= clock_var
;
1268 /* Functions for handling of notes. */
1270 /* Delete notes beginning with INSN and put them in the chain
1271 of notes ended by NOTE_LIST.
1272 Returns the insn following the notes. */
1275 unlink_other_notes (rtx insn
, rtx tail
)
1277 rtx prev
= PREV_INSN (insn
);
1279 while (insn
!= tail
&& NOTE_NOT_BB_P (insn
))
1281 rtx next
= NEXT_INSN (insn
);
1282 basic_block bb
= BLOCK_FOR_INSN (insn
);
1284 /* Delete the note from its current position. */
1286 NEXT_INSN (prev
) = next
;
1288 PREV_INSN (next
) = prev
;
1292 /* Basic block can begin with either LABEL or
1293 NOTE_INSN_BASIC_BLOCK. */
1294 gcc_assert (BB_HEAD (bb
) != insn
);
1296 /* Check if we are removing last insn in the BB. */
1297 if (BB_END (bb
) == insn
)
1301 /* See sched_analyze to see how these are handled. */
1302 if (NOTE_KIND (insn
) != NOTE_INSN_EH_REGION_BEG
1303 && NOTE_KIND (insn
) != NOTE_INSN_EH_REGION_END
)
1305 /* Insert the note at the end of the notes list. */
1306 PREV_INSN (insn
) = note_list
;
1308 NEXT_INSN (note_list
) = insn
;
1317 /* Return the head and tail pointers of ebb starting at BEG and ending
1321 get_ebb_head_tail (basic_block beg
, basic_block end
, rtx
*headp
, rtx
*tailp
)
1323 rtx beg_head
= BB_HEAD (beg
);
1324 rtx beg_tail
= BB_END (beg
);
1325 rtx end_head
= BB_HEAD (end
);
1326 rtx end_tail
= BB_END (end
);
1328 /* Don't include any notes or labels at the beginning of the BEG
1329 basic block, or notes at the end of the END basic blocks. */
1331 if (LABEL_P (beg_head
))
1332 beg_head
= NEXT_INSN (beg_head
);
1334 while (beg_head
!= beg_tail
)
1335 if (NOTE_P (beg_head
))
1336 beg_head
= NEXT_INSN (beg_head
);
1343 end_head
= beg_head
;
1344 else if (LABEL_P (end_head
))
1345 end_head
= NEXT_INSN (end_head
);
1347 while (end_head
!= end_tail
)
1348 if (NOTE_P (end_tail
))
1349 end_tail
= PREV_INSN (end_tail
);
1356 /* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
1359 no_real_insns_p (rtx head
, rtx tail
)
1361 while (head
!= NEXT_INSN (tail
))
1363 if (!NOTE_P (head
) && !LABEL_P (head
))
1365 head
= NEXT_INSN (head
);
1370 /* Delete notes between HEAD and TAIL and put them in the chain
1371 of notes ended by NOTE_LIST. */
1374 rm_other_notes (rtx head
, rtx tail
)
1380 if (head
== tail
&& (! INSN_P (head
)))
1383 next_tail
= NEXT_INSN (tail
);
1384 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1388 /* Farm out notes, and maybe save them in NOTE_LIST.
1389 This is needed to keep the debugger from
1390 getting completely deranged. */
1391 if (NOTE_NOT_BB_P (insn
))
1395 insn
= unlink_other_notes (insn
, next_tail
);
1397 gcc_assert (prev
!= tail
&& prev
!= head
&& insn
!= next_tail
);
1402 /* Functions for computation of registers live/usage info. */
1404 /* This function looks for a new register being defined.
1405 If the destination register is already used by the source,
1406 a new register is not needed. */
1409 find_set_reg_weight (rtx x
)
1411 if (GET_CODE (x
) == CLOBBER
1412 && register_operand (SET_DEST (x
), VOIDmode
))
1414 if (GET_CODE (x
) == SET
1415 && register_operand (SET_DEST (x
), VOIDmode
))
1417 if (REG_P (SET_DEST (x
)))
1419 if (!reg_mentioned_p (SET_DEST (x
), SET_SRC (x
)))
1429 /* Calculate INSN_REG_WEIGHT for all insns of a block. */
1432 find_insn_reg_weight (basic_block bb
)
1434 rtx insn
, next_tail
, head
, tail
;
1436 get_ebb_head_tail (bb
, bb
, &head
, &tail
);
1437 next_tail
= NEXT_INSN (tail
);
1439 for (insn
= head
; insn
!= next_tail
; insn
= NEXT_INSN (insn
))
1440 find_insn_reg_weight1 (insn
);
1443 /* Calculate INSN_REG_WEIGHT for single instruction.
1444 Separated from find_insn_reg_weight because of need
1445 to initialize new instruction in generate_recovery_code. */
1447 find_insn_reg_weight1 (rtx insn
)
1452 /* Handle register life information. */
1453 if (! INSN_P (insn
))
1456 /* Increment weight for each register born here. */
1458 reg_weight
+= find_set_reg_weight (x
);
1459 if (GET_CODE (x
) == PARALLEL
)
1462 for (j
= XVECLEN (x
, 0) - 1; j
>= 0; j
--)
1464 x
= XVECEXP (PATTERN (insn
), 0, j
);
1465 reg_weight
+= find_set_reg_weight (x
);
1468 /* Decrement weight for each register that dies here. */
1469 for (x
= REG_NOTES (insn
); x
; x
= XEXP (x
, 1))
1471 if (REG_NOTE_KIND (x
) == REG_DEAD
1472 || REG_NOTE_KIND (x
) == REG_UNUSED
)
1476 INSN_REG_WEIGHT (insn
) = reg_weight
;
1479 /* Move insns that became ready to fire from queue to ready list. */
1482 queue_to_ready (struct ready_list
*ready
)
1488 q_ptr
= NEXT_Q (q_ptr
);
1490 if (dbg_cnt (sched_insn
) == false)
1491 /* If debug counter is activated do not requeue insn next after
1492 last_scheduled_insn. */
1493 skip_insn
= next_nonnote_insn (last_scheduled_insn
);
1495 skip_insn
= NULL_RTX
;
1497 /* Add all pending insns that can be scheduled without stalls to the
1499 for (link
= insn_queue
[q_ptr
]; link
; link
= XEXP (link
, 1))
1501 insn
= XEXP (link
, 0);
1504 if (sched_verbose
>= 2)
1505 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
1506 (*current_sched_info
->print_insn
) (insn
, 0));
1508 /* If the ready list is full, delay the insn for 1 cycle.
1509 See the comment in schedule_block for the rationale. */
1510 if (!reload_completed
1511 && ready
->n_ready
> MAX_SCHED_READY_INSNS
1512 && !SCHED_GROUP_P (insn
)
1513 && insn
!= skip_insn
)
1515 if (sched_verbose
>= 2)
1516 fprintf (sched_dump
, "requeued because ready full\n");
1517 queue_insn (insn
, 1);
1521 ready_add (ready
, insn
, false);
1522 if (sched_verbose
>= 2)
1523 fprintf (sched_dump
, "moving to ready without stalls\n");
1526 free_INSN_LIST_list (&insn_queue
[q_ptr
]);
1528 /* If there are no ready insns, stall until one is ready and add all
1529 of the pending insns at that point to the ready list. */
1530 if (ready
->n_ready
== 0)
1534 for (stalls
= 1; stalls
<= max_insn_queue_index
; stalls
++)
1536 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
1538 for (; link
; link
= XEXP (link
, 1))
1540 insn
= XEXP (link
, 0);
1543 if (sched_verbose
>= 2)
1544 fprintf (sched_dump
, ";;\t\tQ-->Ready: insn %s: ",
1545 (*current_sched_info
->print_insn
) (insn
, 0));
1547 ready_add (ready
, insn
, false);
1548 if (sched_verbose
>= 2)
1549 fprintf (sched_dump
, "moving to ready with %d stalls\n", stalls
);
1551 free_INSN_LIST_list (&insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]);
1553 advance_one_cycle ();
1558 advance_one_cycle ();
1561 q_ptr
= NEXT_Q_AFTER (q_ptr
, stalls
);
1562 clock_var
+= stalls
;
1566 /* Used by early_queue_to_ready. Determines whether it is "ok" to
1567 prematurely move INSN from the queue to the ready list. Currently,
1568 if a target defines the hook 'is_costly_dependence', this function
1569 uses the hook to check whether there exist any dependences which are
1570 considered costly by the target, between INSN and other insns that
1571 have already been scheduled. Dependences are checked up to Y cycles
1572 back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
1573 controlling this value.
1574 (Other considerations could be taken into account instead (or in
1575 addition) depending on user flags and target hooks. */
1578 ok_for_early_queue_removal (rtx insn
)
1581 rtx prev_insn
= last_scheduled_insn
;
1583 if (targetm
.sched
.is_costly_dependence
)
1585 for (n_cycles
= flag_sched_stalled_insns_dep
; n_cycles
; n_cycles
--)
1587 for ( ; prev_insn
; prev_insn
= PREV_INSN (prev_insn
))
1591 if (!NOTE_P (prev_insn
))
1593 dep_link_t dep_link
;
1595 dep_link
= (find_link_by_con_in_deps_list
1596 (INSN_FORW_DEPS (prev_insn
), insn
));
1600 dep_t dep
= DEP_LINK_DEP (dep_link
);
1602 cost
= dep_cost (dep
);
1604 if (targetm
.sched
.is_costly_dependence (dep
, cost
,
1605 flag_sched_stalled_insns_dep
- n_cycles
))
1610 if (GET_MODE (prev_insn
) == TImode
) /* end of dispatch group */
1616 prev_insn
= PREV_INSN (prev_insn
);
1624 /* Remove insns from the queue, before they become "ready" with respect
1625 to FU latency considerations. */
1628 early_queue_to_ready (state_t state
, struct ready_list
*ready
)
1636 state_t temp_state
= alloca (dfa_state_size
);
1638 int insns_removed
= 0;
1641 Flag '-fsched-stalled-insns=X' determines the aggressiveness of this
1644 X == 0: There is no limit on how many queued insns can be removed
1645 prematurely. (flag_sched_stalled_insns = -1).
1647 X >= 1: Only X queued insns can be removed prematurely in each
1648 invocation. (flag_sched_stalled_insns = X).
1650 Otherwise: Early queue removal is disabled.
1651 (flag_sched_stalled_insns = 0)
1654 if (! flag_sched_stalled_insns
)
1657 for (stalls
= 0; stalls
<= max_insn_queue_index
; stalls
++)
1659 if ((link
= insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)]))
1661 if (sched_verbose
> 6)
1662 fprintf (sched_dump
, ";; look at index %d + %d\n", q_ptr
, stalls
);
1667 next_link
= XEXP (link
, 1);
1668 insn
= XEXP (link
, 0);
1669 if (insn
&& sched_verbose
> 6)
1670 print_rtl_single (sched_dump
, insn
);
1672 memcpy (temp_state
, state
, dfa_state_size
);
1673 if (recog_memoized (insn
) < 0)
1674 /* non-negative to indicate that it's not ready
1675 to avoid infinite Q->R->Q->R... */
1678 cost
= state_transition (temp_state
, insn
);
1680 if (sched_verbose
>= 6)
1681 fprintf (sched_dump
, "transition cost = %d\n", cost
);
1683 move_to_ready
= false;
1686 move_to_ready
= ok_for_early_queue_removal (insn
);
1687 if (move_to_ready
== true)
1689 /* move from Q to R */
1691 ready_add (ready
, insn
, false);
1694 XEXP (prev_link
, 1) = next_link
;
1696 insn_queue
[NEXT_Q_AFTER (q_ptr
, stalls
)] = next_link
;
1698 free_INSN_LIST_node (link
);
1700 if (sched_verbose
>= 2)
1701 fprintf (sched_dump
, ";;\t\tEarly Q-->Ready: insn %s\n",
1702 (*current_sched_info
->print_insn
) (insn
, 0));
1705 if (insns_removed
== flag_sched_stalled_insns
)
1706 /* Remove no more than flag_sched_stalled_insns insns
1707 from Q at a time. */
1708 return insns_removed
;
1712 if (move_to_ready
== false)
1719 } /* for stalls.. */
1721 return insns_removed
;
1725 /* Print the ready list for debugging purposes. Callable from debugger. */
1728 debug_ready_list (struct ready_list
*ready
)
1733 if (ready
->n_ready
== 0)
1735 fprintf (sched_dump
, "\n");
1739 p
= ready_lastpos (ready
);
1740 for (i
= 0; i
< ready
->n_ready
; i
++)
1741 fprintf (sched_dump
, " %s", (*current_sched_info
->print_insn
) (p
[i
], 0));
1742 fprintf (sched_dump
, "\n");
1745 /* Search INSN for REG_SAVE_NOTE note pairs for
1746 NOTE_INSN_EHREGION_{BEG,END}; and convert them back into
1747 NOTEs. The REG_SAVE_NOTE note following first one is contains the
1748 saved value for NOTE_BLOCK_NUMBER which is useful for
1749 NOTE_INSN_EH_REGION_{BEG,END} NOTEs. */
1752 reemit_notes (rtx insn
)
1754 rtx note
, last
= insn
;
1756 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1758 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
1760 enum insn_note note_type
= INTVAL (XEXP (note
, 0));
1762 last
= emit_note_before (note_type
, last
);
1763 remove_note (insn
, note
);
1768 /* Move INSN. Reemit notes if needed. Update CFG, if needed. */
1770 move_insn (rtx insn
)
1772 rtx last
= last_scheduled_insn
;
1774 if (PREV_INSN (insn
) != last
)
1780 bb
= BLOCK_FOR_INSN (insn
);
1782 /* BB_HEAD is either LABEL or NOTE. */
1783 gcc_assert (BB_HEAD (bb
) != insn
);
1785 if (BB_END (bb
) == insn
)
1786 /* If this is last instruction in BB, move end marker one
1789 /* Jumps are always placed at the end of basic block. */
1790 jump_p
= control_flow_insn_p (insn
);
1793 || ((current_sched_info
->flags
& SCHED_RGN
)
1794 && IS_SPECULATION_BRANCHY_CHECK_P (insn
))
1795 || (current_sched_info
->flags
& SCHED_EBB
));
1797 gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn
)) == bb
);
1799 BB_END (bb
) = PREV_INSN (insn
);
1802 gcc_assert (BB_END (bb
) != last
);
1805 /* We move the block note along with jump. */
1807 /* NT is needed for assertion below. */
1808 rtx nt
= current_sched_info
->next_tail
;
1810 note
= NEXT_INSN (insn
);
1811 while (NOTE_NOT_BB_P (note
) && note
!= nt
)
1812 note
= NEXT_INSN (note
);
1816 || BARRIER_P (note
)))
1817 note
= NEXT_INSN (note
);
1819 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
1824 NEXT_INSN (PREV_INSN (insn
)) = NEXT_INSN (note
);
1825 PREV_INSN (NEXT_INSN (note
)) = PREV_INSN (insn
);
1827 NEXT_INSN (note
) = NEXT_INSN (last
);
1828 PREV_INSN (NEXT_INSN (last
)) = note
;
1830 NEXT_INSN (last
) = insn
;
1831 PREV_INSN (insn
) = last
;
1833 bb
= BLOCK_FOR_INSN (last
);
1837 fix_jump_move (insn
);
1839 if (BLOCK_FOR_INSN (insn
) != bb
)
1840 move_block_after_check (insn
);
1842 gcc_assert (BB_END (bb
) == last
);
1845 set_block_for_insn (insn
, bb
);
1846 df_insn_change_bb (insn
);
1848 /* Update BB_END, if needed. */
1849 if (BB_END (bb
) == last
)
1853 reemit_notes (insn
);
1855 SCHED_GROUP_P (insn
) = 0;
1858 /* The following structure describe an entry of the stack of choices. */
1861 /* Ordinal number of the issued insn in the ready queue. */
1863 /* The number of the rest insns whose issues we should try. */
1865 /* The number of issued essential insns. */
1867 /* State after issuing the insn. */
1871 /* The following array is used to implement a stack of choices used in
1872 function max_issue. */
1873 static struct choice_entry
*choice_stack
;
1875 /* The following variable value is number of essential insns issued on
1876 the current cycle. An insn is essential one if it changes the
1877 processors state. */
1878 static int cycle_issued_insns
;
1880 /* The following variable value is maximal number of tries of issuing
1881 insns for the first cycle multipass insn scheduling. We define
1882 this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not
1883 need this constraint if all real insns (with non-negative codes)
1884 had reservations because in this case the algorithm complexity is
1885 O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions
1886 might be incomplete and such insn might occur. For such
1887 descriptions, the complexity of algorithm (without the constraint)
1888 could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */
1889 static int max_lookahead_tries
;
1891 /* The following value is value of hook
1892 `first_cycle_multipass_dfa_lookahead' at the last call of
1894 static int cached_first_cycle_multipass_dfa_lookahead
= 0;
1896 /* The following value is value of `issue_rate' at the last call of
1898 static int cached_issue_rate
= 0;
1900 /* The following function returns maximal (or close to maximal) number
1901 of insns which can be issued on the same cycle and one of which
1902 insns is insns with the best rank (the first insn in READY). To
1903 make this function tries different samples of ready insns. READY
1904 is current queue `ready'. Global array READY_TRY reflects what
1905 insns are already issued in this try. MAX_POINTS is the sum of points
1906 of all instructions in READY. The function stops immediately,
1907 if it reached the such a solution, that all instruction can be issued.
1908 INDEX will contain index of the best insn in READY. The following
1909 function is used only for first cycle multipass scheduling. */
1911 max_issue (struct ready_list
*ready
, int *index
, int max_points
)
1913 int n
, i
, all
, n_ready
, best
, delay
, tries_num
, points
= -1;
1914 struct choice_entry
*top
;
1918 memcpy (choice_stack
->state
, curr_state
, dfa_state_size
);
1920 top
->rest
= cached_first_cycle_multipass_dfa_lookahead
;
1922 n_ready
= ready
->n_ready
;
1923 for (all
= i
= 0; i
< n_ready
; i
++)
1930 if (top
->rest
== 0 || i
>= n_ready
)
1932 if (top
== choice_stack
)
1934 if (best
< top
- choice_stack
&& ready_try
[0])
1936 best
= top
- choice_stack
;
1937 *index
= choice_stack
[1].index
;
1939 if (top
->n
== max_points
|| best
== all
)
1945 memcpy (curr_state
, top
->state
, dfa_state_size
);
1947 else if (!ready_try
[i
])
1950 if (tries_num
> max_lookahead_tries
)
1952 insn
= ready_element (ready
, i
);
1953 delay
= state_transition (curr_state
, insn
);
1956 if (state_dead_lock_p (curr_state
))
1961 if (memcmp (top
->state
, curr_state
, dfa_state_size
) != 0)
1962 n
+= ISSUE_POINTS (insn
);
1964 top
->rest
= cached_first_cycle_multipass_dfa_lookahead
;
1967 memcpy (top
->state
, curr_state
, dfa_state_size
);
1974 while (top
!= choice_stack
)
1976 ready_try
[top
->index
] = 0;
1979 memcpy (curr_state
, choice_stack
->state
, dfa_state_size
);
1981 if (sched_verbose
>= 4)
1982 fprintf (sched_dump
, ";;\t\tChoosed insn : %s; points: %d/%d\n",
1983 (*current_sched_info
->print_insn
) (ready_element (ready
, *index
),
1985 points
, max_points
);
1990 /* The following function chooses insn from READY and modifies
1991 *N_READY and READY. The following function is used only for first
1992 cycle multipass scheduling.
1994 -1 if cycle should be advanced,
1995 0 if INSN_PTR is set to point to the desirable insn,
1996 1 if choose_ready () should be restarted without advancing the cycle. */
1998 choose_ready (struct ready_list
*ready
, rtx
*insn_ptr
)
2002 if (dbg_cnt (sched_insn
) == false)
2006 insn
= next_nonnote_insn (last_scheduled_insn
);
2008 if (QUEUE_INDEX (insn
) == QUEUE_READY
)
2009 /* INSN is in the ready_list. */
2011 ready_remove_insn (insn
);
2016 /* INSN is in the queue. Advance cycle to move it to the ready list. */
2022 if (targetm
.sched
.first_cycle_multipass_dfa_lookahead
)
2023 lookahead
= targetm
.sched
.first_cycle_multipass_dfa_lookahead ();
2024 if (lookahead
<= 0 || SCHED_GROUP_P (ready_element (ready
, 0)))
2026 *insn_ptr
= ready_remove_first (ready
);
2031 /* Try to choose the better insn. */
2032 int index
= 0, i
, n
;
2034 int more_issue
, max_points
, try_data
= 1, try_control
= 1;
2036 if (cached_first_cycle_multipass_dfa_lookahead
!= lookahead
)
2038 cached_first_cycle_multipass_dfa_lookahead
= lookahead
;
2039 max_lookahead_tries
= 100;
2040 for (i
= 0; i
< issue_rate
; i
++)
2041 max_lookahead_tries
*= lookahead
;
2043 insn
= ready_element (ready
, 0);
2044 if (INSN_CODE (insn
) < 0)
2046 *insn_ptr
= ready_remove_first (ready
);
2051 && spec_info
->flags
& (PREFER_NON_DATA_SPEC
2052 | PREFER_NON_CONTROL_SPEC
))
2054 for (i
= 0, n
= ready
->n_ready
; i
< n
; i
++)
2059 x
= ready_element (ready
, i
);
2062 if (spec_info
->flags
& PREFER_NON_DATA_SPEC
2063 && !(s
& DATA_SPEC
))
2066 if (!(spec_info
->flags
& PREFER_NON_CONTROL_SPEC
)
2071 if (spec_info
->flags
& PREFER_NON_CONTROL_SPEC
2072 && !(s
& CONTROL_SPEC
))
2075 if (!(spec_info
->flags
& PREFER_NON_DATA_SPEC
) || !try_data
)
2081 if ((!try_data
&& (TODO_SPEC (insn
) & DATA_SPEC
))
2082 || (!try_control
&& (TODO_SPEC (insn
) & CONTROL_SPEC
))
2083 || (targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard_spec
2084 && !targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard_spec
2086 /* Discard speculative instruction that stands first in the ready
2089 change_queue_index (insn
, 1);
2093 max_points
= ISSUE_POINTS (insn
);
2094 more_issue
= issue_rate
- cycle_issued_insns
- 1;
2096 for (i
= 1; i
< ready
->n_ready
; i
++)
2098 insn
= ready_element (ready
, i
);
2100 = (INSN_CODE (insn
) < 0
2101 || (!try_data
&& (TODO_SPEC (insn
) & DATA_SPEC
))
2102 || (!try_control
&& (TODO_SPEC (insn
) & CONTROL_SPEC
))
2103 || (targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard
2104 && !targetm
.sched
.first_cycle_multipass_dfa_lookahead_guard
2107 if (!ready_try
[i
] && more_issue
-- > 0)
2108 max_points
+= ISSUE_POINTS (insn
);
2111 if (max_issue (ready
, &index
, max_points
) == 0)
2113 *insn_ptr
= ready_remove_first (ready
);
2118 *insn_ptr
= ready_remove (ready
, index
);
2124 /* Use forward list scheduling to rearrange insns of block pointed to by
2125 TARGET_BB, possibly bringing insns from subsequent blocks in the same
2129 schedule_block (basic_block
*target_bb
, int rgn_n_insns1
)
2131 struct ready_list ready
;
2132 int i
, first_cycle_insn_p
;
2134 state_t temp_state
= NULL
; /* It is used for multipass scheduling. */
2135 int sort_p
, advance
, start_clock_var
;
2137 /* Head/tail info for this block. */
2138 rtx prev_head
= current_sched_info
->prev_head
;
2139 rtx next_tail
= current_sched_info
->next_tail
;
2140 rtx head
= NEXT_INSN (prev_head
);
2141 rtx tail
= PREV_INSN (next_tail
);
2143 /* We used to have code to avoid getting parameters moved from hard
2144 argument registers into pseudos.
2146 However, it was removed when it proved to be of marginal benefit
2147 and caused problems because schedule_block and compute_forward_dependences
2148 had different notions of what the "head" insn was. */
2150 gcc_assert (head
!= tail
|| INSN_P (head
));
2152 added_recovery_block_p
= false;
2156 dump_new_block_header (0, *target_bb
, head
, tail
);
2158 state_reset (curr_state
);
2160 /* Allocate the ready list. */
2164 choice_stack
= NULL
;
2167 extend_ready (rgn_n_insns1
+ 1);
2169 ready
.first
= ready
.veclen
- 1;
2172 /* It is used for first cycle multipass scheduling. */
2173 temp_state
= alloca (dfa_state_size
);
2175 if (targetm
.sched
.md_init
)
2176 targetm
.sched
.md_init (sched_dump
, sched_verbose
, ready
.veclen
);
2178 /* We start inserting insns after PREV_HEAD. */
2179 last_scheduled_insn
= prev_head
;
2181 gcc_assert (NOTE_P (last_scheduled_insn
)
2182 && BLOCK_FOR_INSN (last_scheduled_insn
) == *target_bb
);
2184 /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
2189 insn_queue
= alloca ((max_insn_queue_index
+ 1) * sizeof (rtx
));
2190 memset (insn_queue
, 0, (max_insn_queue_index
+ 1) * sizeof (rtx
));
2192 /* Start just before the beginning of time. */
2195 /* We need queue and ready lists and clock_var be initialized
2196 in try_ready () (which is called through init_ready_list ()). */
2197 (*current_sched_info
->init_ready_list
) ();
2199 /* The algorithm is O(n^2) in the number of ready insns at any given
2200 time in the worst case. Before reload we are more likely to have
2201 big lists so truncate them to a reasonable size. */
2202 if (!reload_completed
&& ready
.n_ready
> MAX_SCHED_READY_INSNS
)
2204 ready_sort (&ready
);
2206 /* Find first free-standing insn past MAX_SCHED_READY_INSNS. */
2207 for (i
= MAX_SCHED_READY_INSNS
; i
< ready
.n_ready
; i
++)
2208 if (!SCHED_GROUP_P (ready_element (&ready
, i
)))
2211 if (sched_verbose
>= 2)
2213 fprintf (sched_dump
,
2214 ";;\t\tReady list on entry: %d insns\n", ready
.n_ready
);
2215 fprintf (sched_dump
,
2216 ";;\t\t before reload => truncated to %d insns\n", i
);
2219 /* Delay all insns past it for 1 cycle. If debug counter is
2220 activated make an exception for the insn right after
2221 last_scheduled_insn. */
2225 if (dbg_cnt (sched_insn
) == false)
2226 skip_insn
= next_nonnote_insn (last_scheduled_insn
);
2228 skip_insn
= NULL_RTX
;
2230 while (i
< ready
.n_ready
)
2234 insn
= ready_remove (&ready
, i
);
2236 if (insn
!= skip_insn
)
2237 queue_insn (insn
, 1);
2242 /* Now we can restore basic block notes and maintain precise cfg. */
2243 restore_bb_notes (*target_bb
);
2245 last_clock_var
= -1;
2250 /* Loop until all the insns in BB are scheduled. */
2251 while ((*current_sched_info
->schedule_more_p
) ())
2255 start_clock_var
= clock_var
;
2259 advance_one_cycle ();
2261 /* Add to the ready list all pending insns that can be issued now.
2262 If there are no ready insns, increment clock until one
2263 is ready and add all pending insns at that point to the ready
2265 queue_to_ready (&ready
);
2267 gcc_assert (ready
.n_ready
);
2269 if (sched_verbose
>= 2)
2271 fprintf (sched_dump
, ";;\t\tReady list after queue_to_ready: ");
2272 debug_ready_list (&ready
);
2274 advance
-= clock_var
- start_clock_var
;
2276 while (advance
> 0);
2280 /* Sort the ready list based on priority. */
2281 ready_sort (&ready
);
2283 if (sched_verbose
>= 2)
2285 fprintf (sched_dump
, ";;\t\tReady list after ready_sort: ");
2286 debug_ready_list (&ready
);
2290 /* Allow the target to reorder the list, typically for
2291 better instruction bundling. */
2292 if (sort_p
&& targetm
.sched
.reorder
2293 && (ready
.n_ready
== 0
2294 || !SCHED_GROUP_P (ready_element (&ready
, 0))))
2296 targetm
.sched
.reorder (sched_dump
, sched_verbose
,
2297 ready_lastpos (&ready
),
2298 &ready
.n_ready
, clock_var
);
2300 can_issue_more
= issue_rate
;
2302 first_cycle_insn_p
= 1;
2303 cycle_issued_insns
= 0;
2310 if (sched_verbose
>= 2)
2312 fprintf (sched_dump
, ";;\tReady list (t = %3d): ",
2314 debug_ready_list (&ready
);
2317 if (ready
.n_ready
== 0
2319 && reload_completed
)
2321 /* Allow scheduling insns directly from the queue in case
2322 there's nothing better to do (ready list is empty) but
2323 there are still vacant dispatch slots in the current cycle. */
2324 if (sched_verbose
>= 6)
2325 fprintf (sched_dump
,";;\t\tSecond chance\n");
2326 memcpy (temp_state
, curr_state
, dfa_state_size
);
2327 if (early_queue_to_ready (temp_state
, &ready
))
2328 ready_sort (&ready
);
2331 if (ready
.n_ready
== 0 || !can_issue_more
2332 || state_dead_lock_p (curr_state
)
2333 || !(*current_sched_info
->schedule_more_p
) ())
2336 /* Select and remove the insn from the ready list. */
2342 res
= choose_ready (&ready
, &insn
);
2348 /* Restart choose_ready (). */
2351 gcc_assert (insn
!= NULL_RTX
);
2354 insn
= ready_remove_first (&ready
);
2356 if (targetm
.sched
.dfa_new_cycle
2357 && targetm
.sched
.dfa_new_cycle (sched_dump
, sched_verbose
,
2358 insn
, last_clock_var
,
2359 clock_var
, &sort_p
))
2360 /* SORT_P is used by the target to override sorting
2361 of the ready list. This is needed when the target
2362 has modified its internal structures expecting that
2363 the insn will be issued next. As we need the insn
2364 to have the highest priority (so it will be returned by
2365 the ready_remove_first call above), we invoke
2366 ready_add (&ready, insn, true).
2367 But, still, there is one issue: INSN can be later
2368 discarded by scheduler's front end through
2369 current_sched_info->can_schedule_ready_p, hence, won't
2372 ready_add (&ready
, insn
, true);
2377 memcpy (temp_state
, curr_state
, dfa_state_size
);
2378 if (recog_memoized (insn
) < 0)
2380 asm_p
= (GET_CODE (PATTERN (insn
)) == ASM_INPUT
2381 || asm_noperands (PATTERN (insn
)) >= 0);
2382 if (!first_cycle_insn_p
&& asm_p
)
2383 /* This is asm insn which is tryed to be issued on the
2384 cycle not first. Issue it on the next cycle. */
2387 /* A USE insn, or something else we don't need to
2388 understand. We can't pass these directly to
2389 state_transition because it will trigger a
2390 fatal error for unrecognizable insns. */
2395 cost
= state_transition (temp_state
, insn
);
2404 queue_insn (insn
, cost
);
2405 if (SCHED_GROUP_P (insn
))
2414 if (current_sched_info
->can_schedule_ready_p
2415 && ! (*current_sched_info
->can_schedule_ready_p
) (insn
))
2416 /* We normally get here only if we don't want to move
2417 insn from the split block. */
2419 TODO_SPEC (insn
) = (TODO_SPEC (insn
) & ~SPECULATIVE
) | HARD_DEP
;
2423 /* DECISION is made. */
2425 if (TODO_SPEC (insn
) & SPECULATIVE
)
2426 generate_recovery_code (insn
);
2428 if (control_flow_insn_p (last_scheduled_insn
)
2429 /* This is used to switch basic blocks by request
2430 from scheduler front-end (actually, sched-ebb.c only).
2431 This is used to process blocks with single fallthru
2432 edge. If succeeding block has jump, it [jump] will try
2433 move at the end of current bb, thus corrupting CFG. */
2434 || current_sched_info
->advance_target_bb (*target_bb
, insn
))
2436 *target_bb
= current_sched_info
->advance_target_bb
2443 x
= next_real_insn (last_scheduled_insn
);
2445 dump_new_block_header (1, *target_bb
, x
, tail
);
2448 last_scheduled_insn
= bb_note (*target_bb
);
2451 /* Update counters, etc in the scheduler's front end. */
2452 (*current_sched_info
->begin_schedule_ready
) (insn
,
2453 last_scheduled_insn
);
2456 last_scheduled_insn
= insn
;
2458 if (memcmp (curr_state
, temp_state
, dfa_state_size
) != 0)
2460 cycle_issued_insns
++;
2461 memcpy (curr_state
, temp_state
, dfa_state_size
);
2464 if (targetm
.sched
.variable_issue
)
2466 targetm
.sched
.variable_issue (sched_dump
, sched_verbose
,
2467 insn
, can_issue_more
);
2468 /* A naked CLOBBER or USE generates no instruction, so do
2469 not count them against the issue rate. */
2470 else if (GET_CODE (PATTERN (insn
)) != USE
2471 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
2474 advance
= schedule_insn (insn
);
2476 /* After issuing an asm insn we should start a new cycle. */
2477 if (advance
== 0 && asm_p
)
2482 first_cycle_insn_p
= 0;
2484 /* Sort the ready list based on priority. This must be
2485 redone here, as schedule_insn may have readied additional
2486 insns that will not be sorted correctly. */
2487 if (ready
.n_ready
> 0)
2488 ready_sort (&ready
);
2490 if (targetm
.sched
.reorder2
2491 && (ready
.n_ready
== 0
2492 || !SCHED_GROUP_P (ready_element (&ready
, 0))))
2495 targetm
.sched
.reorder2 (sched_dump
, sched_verbose
,
2497 ? ready_lastpos (&ready
) : NULL
,
2498 &ready
.n_ready
, clock_var
);
2506 fprintf (sched_dump
, ";;\tReady list (final): ");
2507 debug_ready_list (&ready
);
2510 if (current_sched_info
->queue_must_finish_empty
)
2511 /* Sanity check -- queue must be empty now. Meaningless if region has
2513 gcc_assert (!q_size
&& !ready
.n_ready
);
2516 /* We must maintain QUEUE_INDEX between blocks in region. */
2517 for (i
= ready
.n_ready
- 1; i
>= 0; i
--)
2521 x
= ready_element (&ready
, i
);
2522 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
2523 TODO_SPEC (x
) = (TODO_SPEC (x
) & ~SPECULATIVE
) | HARD_DEP
;
2527 for (i
= 0; i
<= max_insn_queue_index
; i
++)
2530 for (link
= insn_queue
[i
]; link
; link
= XEXP (link
, 1))
2535 QUEUE_INDEX (x
) = QUEUE_NOWHERE
;
2536 TODO_SPEC (x
) = (TODO_SPEC (x
) & ~SPECULATIVE
) | HARD_DEP
;
2538 free_INSN_LIST_list (&insn_queue
[i
]);
2542 if (!current_sched_info
->queue_must_finish_empty
2543 || added_recovery_block_p
)
2545 /* INSN_TICK (minimum clock tick at which the insn becomes
2546 ready) may be not correct for the insn in the subsequent
2547 blocks of the region. We should use a correct value of
2548 `clock_var' or modify INSN_TICK. It is better to keep
2549 clock_var value equal to 0 at the start of a basic block.
2550 Therefore we modify INSN_TICK here. */
2551 fix_inter_tick (NEXT_INSN (prev_head
), last_scheduled_insn
);
2554 if (targetm
.sched
.md_finish
)
2555 targetm
.sched
.md_finish (sched_dump
, sched_verbose
);
2557 /* Update head/tail boundaries. */
2558 head
= NEXT_INSN (prev_head
);
2559 tail
= last_scheduled_insn
;
2561 /* Restore-other-notes: NOTE_LIST is the end of a chain of notes
2562 previously found among the insns. Insert them at the beginning
2566 basic_block head_bb
= BLOCK_FOR_INSN (head
);
2567 rtx note_head
= note_list
;
2569 while (PREV_INSN (note_head
))
2571 set_block_for_insn (note_head
, head_bb
);
2572 note_head
= PREV_INSN (note_head
);
2574 /* In the above cycle we've missed this note: */
2575 set_block_for_insn (note_head
, head_bb
);
2577 PREV_INSN (note_head
) = PREV_INSN (head
);
2578 NEXT_INSN (PREV_INSN (head
)) = note_head
;
2579 PREV_INSN (head
) = note_list
;
2580 NEXT_INSN (note_list
) = head
;
2587 fprintf (sched_dump
, ";; total time = %d\n;; new head = %d\n",
2588 clock_var
, INSN_UID (head
));
2589 fprintf (sched_dump
, ";; new tail = %d\n\n",
2593 current_sched_info
->head
= head
;
2594 current_sched_info
->tail
= tail
;
2599 for (i
= 0; i
<= rgn_n_insns
; i
++)
2600 free (choice_stack
[i
].state
);
2601 free (choice_stack
);
2604 /* Set_priorities: compute priority of each insn in the block. */
2607 set_priorities (rtx head
, rtx tail
)
2611 int sched_max_insns_priority
=
2612 current_sched_info
->sched_max_insns_priority
;
2615 if (head
== tail
&& (! INSN_P (head
)))
2620 prev_head
= PREV_INSN (head
);
2621 for (insn
= tail
; insn
!= prev_head
; insn
= PREV_INSN (insn
))
2627 (void) priority (insn
);
2629 gcc_assert (INSN_PRIORITY_KNOWN (insn
));
2631 sched_max_insns_priority
= MAX (sched_max_insns_priority
,
2632 INSN_PRIORITY (insn
));
2635 current_sched_info
->sched_max_insns_priority
= sched_max_insns_priority
;
2640 /* Next LUID to assign to an instruction. */
2643 /* Initialize some global state for the scheduler. */
2652 /* Switch to working copy of sched_info. */
2653 memcpy (¤t_sched_info_var
, current_sched_info
,
2654 sizeof (current_sched_info_var
));
2655 current_sched_info
= ¤t_sched_info_var
;
2657 /* Disable speculative loads in their presence if cc0 defined. */
2659 flag_schedule_speculative_load
= 0;
2662 /* Set dump and sched_verbose for the desired debugging output. If no
2663 dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
2664 For -fsched-verbose=N, N>=10, print everything to stderr. */
2665 sched_verbose
= sched_verbose_param
;
2666 if (sched_verbose_param
== 0 && dump_file
)
2668 sched_dump
= ((sched_verbose_param
>= 10 || !dump_file
)
2669 ? stderr
: dump_file
);
2671 /* Initialize SPEC_INFO. */
2672 if (targetm
.sched
.set_sched_flags
)
2674 spec_info
= &spec_info_var
;
2675 targetm
.sched
.set_sched_flags (spec_info
);
2676 if (current_sched_info
->flags
& DO_SPECULATION
)
2677 spec_info
->weakness_cutoff
=
2678 (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF
) * MAX_DEP_WEAK
) / 100;
2680 /* So we won't read anything accidentally. */
2682 #ifdef ENABLE_CHECKING
2683 check_sched_flags ();
2687 /* So we won't read anything accidentally. */
2690 /* Initialize issue_rate. */
2691 if (targetm
.sched
.issue_rate
)
2692 issue_rate
= targetm
.sched
.issue_rate ();
2696 if (cached_issue_rate
!= issue_rate
)
2698 cached_issue_rate
= issue_rate
;
2699 /* To invalidate max_lookahead_tries: */
2700 cached_first_cycle_multipass_dfa_lookahead
= 0;
2707 for (i
= 0; i
< old_max_uid
; i
++)
2710 h_i_d
[i
].todo_spec
= HARD_DEP
;
2711 h_i_d
[i
].queue_index
= QUEUE_NOWHERE
;
2712 h_i_d
[i
].tick
= INVALID_TICK
;
2713 h_i_d
[i
].inter_tick
= INVALID_TICK
;
2716 if (targetm
.sched
.init_dfa_pre_cycle_insn
)
2717 targetm
.sched
.init_dfa_pre_cycle_insn ();
2719 if (targetm
.sched
.init_dfa_post_cycle_insn
)
2720 targetm
.sched
.init_dfa_post_cycle_insn ();
2723 dfa_state_size
= state_size ();
2724 curr_state
= xmalloc (dfa_state_size
);
2729 for (insn
= BB_HEAD (b
); ; insn
= NEXT_INSN (insn
))
2731 INSN_LUID (insn
) = luid
;
2733 /* Increment the next luid, unless this is a note. We don't
2734 really need separate IDs for notes and we don't want to
2735 schedule differently depending on whether or not there are
2736 line-number notes, i.e., depending on whether or not we're
2737 generating debugging information. */
2741 if (insn
== BB_END (b
))
2745 init_dependency_caches (luid
);
2747 init_alias_analysis ();
2749 old_last_basic_block
= 0;
2752 /* Compute INSN_REG_WEIGHT for all blocks. We must do this before
2753 removing death notes. */
2754 FOR_EACH_BB_REVERSE (b
)
2755 find_insn_reg_weight (b
);
2757 if (targetm
.sched
.md_init_global
)
2758 targetm
.sched
.md_init_global (sched_dump
, sched_verbose
, old_max_uid
);
2760 nr_begin_data
= nr_begin_control
= nr_be_in_data
= nr_be_in_control
= 0;
2761 before_recovery
= 0;
2763 #ifdef ENABLE_CHECKING
2764 /* This is used preferably for finding bugs in check_cfg () itself. */
2769 /* Free global data used during insn scheduling. */
2777 free_dependency_caches ();
2778 end_alias_analysis ();
2780 if (targetm
.sched
.md_finish_global
)
2781 targetm
.sched
.md_finish_global (sched_dump
, sched_verbose
);
2783 if (spec_info
&& spec_info
->dump
)
2785 char c
= reload_completed
? 'a' : 'b';
2787 fprintf (spec_info
->dump
,
2788 ";; %s:\n", current_function_name ());
2790 fprintf (spec_info
->dump
,
2791 ";; Procedure %cr-begin-data-spec motions == %d\n",
2793 fprintf (spec_info
->dump
,
2794 ";; Procedure %cr-be-in-data-spec motions == %d\n",
2796 fprintf (spec_info
->dump
,
2797 ";; Procedure %cr-begin-control-spec motions == %d\n",
2798 c
, nr_begin_control
);
2799 fprintf (spec_info
->dump
,
2800 ";; Procedure %cr-be-in-control-spec motions == %d\n",
2801 c
, nr_be_in_control
);
2804 #ifdef ENABLE_CHECKING
2805 /* After reload ia64 backend clobbers CFG, so can't check anything. */
2806 if (!reload_completed
)
2810 current_sched_info
= NULL
;
2813 /* Fix INSN_TICKs of the instructions in the current block as well as
2814 INSN_TICKs of their dependents.
2815 HEAD and TAIL are the begin and the end of the current scheduled block. */
2817 fix_inter_tick (rtx head
, rtx tail
)
2819 /* Set of instructions with corrected INSN_TICK. */
2820 bitmap_head processed
;
2821 int next_clock
= clock_var
+ 1;
2823 bitmap_initialize (&processed
, 0);
2825 /* Iterates over scheduled instructions and fix their INSN_TICKs and
2826 INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
2827 across different blocks. */
2828 for (tail
= NEXT_INSN (tail
); head
!= tail
; head
= NEXT_INSN (head
))
2835 tick
= INSN_TICK (head
);
2836 gcc_assert (tick
>= MIN_TICK
);
2838 /* Fix INSN_TICK of instruction from just scheduled block. */
2839 if (!bitmap_bit_p (&processed
, INSN_LUID (head
)))
2841 bitmap_set_bit (&processed
, INSN_LUID (head
));
2844 if (tick
< MIN_TICK
)
2847 INSN_TICK (head
) = tick
;
2850 FOR_EACH_DEP_LINK (link
, INSN_FORW_DEPS (head
))
2854 next
= DEP_LINK_CON (link
);
2855 tick
= INSN_TICK (next
);
2857 if (tick
!= INVALID_TICK
2858 /* If NEXT has its INSN_TICK calculated, fix it.
2859 If not - it will be properly calculated from
2860 scratch later in fix_tick_ready. */
2861 && !bitmap_bit_p (&processed
, INSN_LUID (next
)))
2863 bitmap_set_bit (&processed
, INSN_LUID (next
));
2866 if (tick
< MIN_TICK
)
2869 if (tick
> INTER_TICK (next
))
2870 INTER_TICK (next
) = tick
;
2872 tick
= INTER_TICK (next
);
2874 INSN_TICK (next
) = tick
;
2879 bitmap_clear (&processed
);
2882 /* Check if NEXT is ready to be added to the ready or queue list.
2883 If "yes", add it to the proper list.
2885 -1 - is not ready yet,
2886 0 - added to the ready list,
2887 0 < N - queued for N cycles. */
2889 try_ready (rtx next
)
2894 ts
= &TODO_SPEC (next
);
2897 gcc_assert (!(old_ts
& ~(SPECULATIVE
| HARD_DEP
))
2898 && ((old_ts
& HARD_DEP
)
2899 || (old_ts
& SPECULATIVE
)));
2901 if (!(current_sched_info
->flags
& DO_SPECULATION
))
2903 if (deps_list_empty_p (INSN_BACK_DEPS (next
)))
2908 *ts
&= ~SPECULATIVE
& ~HARD_DEP
;
2910 link
= DEPS_LIST_FIRST (INSN_BACK_DEPS (next
));
2914 ds_t ds
= DEP_LINK_STATUS (link
) & SPECULATIVE
;
2916 /* Backward dependencies of the insn are maintained sorted.
2917 So if DEP_STATUS of the first dep is SPECULATIVE,
2918 than all other deps are speculative too. */
2921 /* Now we've got NEXT with speculative deps only.
2922 1. Look at the deps to see what we have to do.
2923 2. Check if we can do 'todo'. */
2926 while ((link
= DEP_LINK_NEXT (link
)) != NULL
)
2928 ds
= DEP_LINK_STATUS (link
) & SPECULATIVE
;
2929 *ts
= ds_merge (*ts
, ds
);
2932 if (dep_weak (*ts
) < spec_info
->weakness_cutoff
)
2933 /* Too few points. */
2934 *ts
= (*ts
& ~SPECULATIVE
) | HARD_DEP
;
2942 gcc_assert (*ts
== old_ts
2943 && QUEUE_INDEX (next
) == QUEUE_NOWHERE
);
2944 else if (current_sched_info
->new_ready
)
2945 *ts
= current_sched_info
->new_ready (next
, *ts
);
2947 /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
2948 have its original pattern or changed (speculative) one. This is due
2949 to changing ebb in region scheduling.
2950 * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
2951 has speculative pattern.
2953 We can't assert (!(*ts & HARD_DEP) || *ts == old_ts) here because
2954 control-speculative NEXT could have been discarded by sched-rgn.c
2955 (the same case as when discarded by can_schedule_ready_p ()). */
2957 if ((*ts
& SPECULATIVE
)
2958 /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't
2959 need to change anything. */
2965 gcc_assert ((*ts
& SPECULATIVE
) && !(*ts
& ~SPECULATIVE
));
2967 res
= speculate_insn (next
, *ts
, &new_pat
);
2972 /* It would be nice to change DEP_STATUS of all dependences,
2973 which have ((DEP_STATUS & SPECULATIVE) == *ts) to HARD_DEP,
2974 so we won't reanalyze anything. */
2975 *ts
= (*ts
& ~SPECULATIVE
) | HARD_DEP
;
2979 /* We follow the rule, that every speculative insn
2980 has non-null ORIG_PAT. */
2981 if (!ORIG_PAT (next
))
2982 ORIG_PAT (next
) = PATTERN (next
);
2986 if (!ORIG_PAT (next
))
2987 /* If we gonna to overwrite the original pattern of insn,
2989 ORIG_PAT (next
) = PATTERN (next
);
2991 change_pattern (next
, new_pat
);
2999 /* We need to restore pattern only if (*ts == 0), because otherwise it is
3000 either correct (*ts & SPECULATIVE),
3001 or we simply don't care (*ts & HARD_DEP). */
3003 gcc_assert (!ORIG_PAT (next
)
3004 || !IS_SPECULATION_BRANCHY_CHECK_P (next
));
3008 /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
3009 control-speculative NEXT could have been discarded by sched-rgn.c
3010 (the same case as when discarded by can_schedule_ready_p ()). */
3011 /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
3013 change_queue_index (next
, QUEUE_NOWHERE
);
3016 else if (!(*ts
& BEGIN_SPEC
) && ORIG_PAT (next
) && !IS_SPECULATION_CHECK_P (next
))
3017 /* We should change pattern of every previously speculative
3018 instruction - and we determine if NEXT was speculative by using
3019 ORIG_PAT field. Except one case - speculation checks have ORIG_PAT
3020 pat too, so skip them. */
3022 change_pattern (next
, ORIG_PAT (next
));
3023 ORIG_PAT (next
) = 0;
3026 if (sched_verbose
>= 2)
3028 int s
= TODO_SPEC (next
);
3030 fprintf (sched_dump
, ";;\t\tdependencies resolved: insn %s",
3031 (*current_sched_info
->print_insn
) (next
, 0));
3033 if (spec_info
&& spec_info
->dump
)
3036 fprintf (spec_info
->dump
, "; data-spec;");
3037 if (s
& BEGIN_CONTROL
)
3038 fprintf (spec_info
->dump
, "; control-spec;");
3039 if (s
& BE_IN_CONTROL
)
3040 fprintf (spec_info
->dump
, "; in-control-spec;");
3043 fprintf (sched_dump
, "\n");
3046 adjust_priority (next
);
3048 return fix_tick_ready (next
);
3051 /* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */
3053 fix_tick_ready (rtx next
)
3057 if (!deps_list_empty_p (INSN_RESOLVED_BACK_DEPS (next
)))
3062 tick
= INSN_TICK (next
);
3063 /* if tick is not equal to INVALID_TICK, then update
3064 INSN_TICK of NEXT with the most recent resolved dependence
3065 cost. Otherwise, recalculate from scratch. */
3066 full_p
= (tick
== INVALID_TICK
);
3068 FOR_EACH_DEP_LINK (link
, INSN_RESOLVED_BACK_DEPS (next
))
3070 dep_t dep
= DEP_LINK_DEP (link
);
3071 rtx pro
= DEP_PRO (dep
);
3074 gcc_assert (INSN_TICK (pro
) >= MIN_TICK
);
3076 tick1
= INSN_TICK (pro
) + dep_cost (dep
);
3087 INSN_TICK (next
) = tick
;
3089 delay
= tick
- clock_var
;
3091 delay
= QUEUE_READY
;
3093 change_queue_index (next
, delay
);
3098 /* Move NEXT to the proper queue list with (DELAY >= 1),
3099 or add it to the ready list (DELAY == QUEUE_READY),
3100 or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */
3102 change_queue_index (rtx next
, int delay
)
3104 int i
= QUEUE_INDEX (next
);
3106 gcc_assert (QUEUE_NOWHERE
<= delay
&& delay
<= max_insn_queue_index
3108 gcc_assert (i
!= QUEUE_SCHEDULED
);
3110 if ((delay
> 0 && NEXT_Q_AFTER (q_ptr
, delay
) == i
)
3111 || (delay
< 0 && delay
== i
))
3112 /* We have nothing to do. */
3115 /* Remove NEXT from wherever it is now. */
3116 if (i
== QUEUE_READY
)
3117 ready_remove_insn (next
);
3119 queue_remove (next
);
3121 /* Add it to the proper place. */
3122 if (delay
== QUEUE_READY
)
3123 ready_add (readyp
, next
, false);
3124 else if (delay
>= 1)
3125 queue_insn (next
, delay
);
3127 if (sched_verbose
>= 2)
3129 fprintf (sched_dump
, ";;\t\ttick updated: insn %s",
3130 (*current_sched_info
->print_insn
) (next
, 0));
3132 if (delay
== QUEUE_READY
)
3133 fprintf (sched_dump
, " into ready\n");
3134 else if (delay
>= 1)
3135 fprintf (sched_dump
, " into queue with cost=%d\n", delay
);
3137 fprintf (sched_dump
, " removed from ready or queue lists\n");
3141 /* Extend H_I_D data. */
3145 /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
3146 pseudos which do not cross calls. */
3147 int new_max_uid
= get_max_uid () + 1;
3149 h_i_d
= xrecalloc (h_i_d
, new_max_uid
, old_max_uid
, sizeof (*h_i_d
));
3150 old_max_uid
= new_max_uid
;
3152 if (targetm
.sched
.h_i_d_extended
)
3153 targetm
.sched
.h_i_d_extended ();
3156 /* Extend READY, READY_TRY and CHOICE_STACK arrays.
3157 N_NEW_INSNS is the number of additional elements to allocate. */
3159 extend_ready (int n_new_insns
)
3163 readyp
->veclen
= rgn_n_insns
+ n_new_insns
+ 1 + issue_rate
;
3164 readyp
->vec
= XRESIZEVEC (rtx
, readyp
->vec
, readyp
->veclen
);
3166 ready_try
= xrecalloc (ready_try
, rgn_n_insns
+ n_new_insns
+ 1,
3167 rgn_n_insns
+ 1, sizeof (char));
3169 rgn_n_insns
+= n_new_insns
;
3171 choice_stack
= XRESIZEVEC (struct choice_entry
, choice_stack
,
3174 for (i
= rgn_n_insns
; n_new_insns
--; i
--)
3175 choice_stack
[i
].state
= xmalloc (dfa_state_size
);
3178 /* Extend global scheduler structures (those, that live across calls to
3179 schedule_block) to include information about just emitted INSN. */
3181 extend_global (rtx insn
)
3183 gcc_assert (INSN_P (insn
));
3184 /* These structures have scheduler scope. */
3188 extend_dependency_caches (1, 0);
3191 /* Extends global and local scheduler structures to include information
3192 about just emitted INSN. */
3194 extend_all (rtx insn
)
3196 extend_global (insn
);
3198 /* These structures have block scope. */
3201 (*current_sched_info
->add_remove_insn
) (insn
, 0);
3204 /* Initialize h_i_d entry of the new INSN with default values.
3205 Values, that are not explicitly initialized here, hold zero. */
3207 init_h_i_d (rtx insn
)
3209 INSN_LUID (insn
) = luid
++;
3210 INSN_COST (insn
) = -1;
3211 TODO_SPEC (insn
) = HARD_DEP
;
3212 QUEUE_INDEX (insn
) = QUEUE_NOWHERE
;
3213 INSN_TICK (insn
) = INVALID_TICK
;
3214 INTER_TICK (insn
) = INVALID_TICK
;
3215 find_insn_reg_weight1 (insn
);
3217 /* These two lists will be freed in schedule_insn (). */
3218 INSN_BACK_DEPS (insn
) = create_deps_list (false);
3219 INSN_RESOLVED_BACK_DEPS (insn
) = create_deps_list (false);
3221 /* This one should be allocated on the obstack because it should live till
3222 the scheduling ends. */
3223 INSN_FORW_DEPS (insn
) = create_deps_list (true);
3226 /* Generates recovery code for INSN. */
3228 generate_recovery_code (rtx insn
)
3230 if (TODO_SPEC (insn
) & BEGIN_SPEC
)
3231 begin_speculative_block (insn
);
3233 /* Here we have insn with no dependencies to
3234 instructions other then CHECK_SPEC ones. */
3236 if (TODO_SPEC (insn
) & BE_IN_SPEC
)
3237 add_to_speculative_block (insn
);
3241 Tries to add speculative dependencies of type FS between instructions
3242 in deps_list L and TWIN. */
3244 process_insn_forw_deps_be_in_spec (deps_list_t l
, rtx twin
, ds_t fs
)
3248 FOR_EACH_DEP_LINK (link
, l
)
3253 consumer
= DEP_LINK_CON (link
);
3255 ds
= DEP_LINK_STATUS (link
);
3257 if (/* If we want to create speculative dep. */
3259 /* And we can do that because this is a true dep. */
3260 && (ds
& DEP_TYPES
) == DEP_TRUE
)
3262 gcc_assert (!(ds
& BE_IN_SPEC
));
3264 if (/* If this dep can be overcome with 'begin speculation'. */
3266 /* Then we have a choice: keep the dep 'begin speculative'
3267 or transform it into 'be in speculative'. */
3269 if (/* In try_ready we assert that if insn once became ready
3270 it can be removed from the ready (or queue) list only
3271 due to backend decision. Hence we can't let the
3272 probability of the speculative dep to decrease. */
3273 dep_weak (ds
) <= dep_weak (fs
))
3274 /* Transform it to be in speculative. */
3275 ds
= (ds
& ~BEGIN_SPEC
) | fs
;
3278 /* Mark the dep as 'be in speculative'. */
3282 add_back_forw_dep (consumer
, twin
, DEP_LINK_KIND (link
), ds
);
3286 /* Generates recovery code for BEGIN speculative INSN. */
3288 begin_speculative_block (rtx insn
)
3290 if (TODO_SPEC (insn
) & BEGIN_DATA
)
3292 if (TODO_SPEC (insn
) & BEGIN_CONTROL
)
3295 create_check_block_twin (insn
, false);
3297 TODO_SPEC (insn
) &= ~BEGIN_SPEC
;
3300 /* Generates recovery code for BE_IN speculative INSN. */
3302 add_to_speculative_block (rtx insn
)
3307 rtx_vec_t priorities_roots
;
3309 ts
= TODO_SPEC (insn
);
3310 gcc_assert (!(ts
& ~BE_IN_SPEC
));
3312 if (ts
& BE_IN_DATA
)
3314 if (ts
& BE_IN_CONTROL
)
3317 TODO_SPEC (insn
) &= ~BE_IN_SPEC
;
3318 gcc_assert (!TODO_SPEC (insn
));
3320 DONE_SPEC (insn
) |= ts
;
3322 /* First we convert all simple checks to branchy. */
3323 for (link
= DEPS_LIST_FIRST (INSN_BACK_DEPS (insn
)); link
!= NULL
;)
3325 rtx check
= DEP_LINK_PRO (link
);
3327 if (IS_SPECULATION_SIMPLE_CHECK_P (check
))
3329 create_check_block_twin (check
, true);
3331 /* Restart search. */
3332 link
= DEPS_LIST_FIRST (INSN_BACK_DEPS (insn
));
3335 /* Continue search. */
3336 link
= DEP_LINK_NEXT (link
);
3339 priorities_roots
= NULL
;
3340 clear_priorities (insn
, &priorities_roots
);
3348 link
= DEPS_LIST_FIRST (INSN_BACK_DEPS (insn
));
3350 gcc_assert ((DEP_LINK_STATUS (link
) & BEGIN_SPEC
) == 0
3351 && (DEP_LINK_STATUS (link
) & BE_IN_SPEC
) != 0
3352 && (DEP_LINK_STATUS (link
) & DEP_TYPES
) == DEP_TRUE
);
3354 check
= DEP_LINK_PRO (link
);
3356 gcc_assert (!IS_SPECULATION_CHECK_P (check
) && !ORIG_PAT (check
)
3357 && QUEUE_INDEX (check
) == QUEUE_NOWHERE
);
3359 rec
= BLOCK_FOR_INSN (check
);
3361 twin
= emit_insn_before (copy_insn (PATTERN (insn
)), BB_END (rec
));
3362 extend_global (twin
);
3364 copy_deps_list_change_con (INSN_RESOLVED_BACK_DEPS (twin
),
3365 INSN_RESOLVED_BACK_DEPS (insn
),
3368 if (sched_verbose
&& spec_info
->dump
)
3369 /* INSN_BB (insn) isn't determined for twin insns yet.
3370 So we can't use current_sched_info->print_insn. */
3371 fprintf (spec_info
->dump
, ";;\t\tGenerated twin insn : %d/rec%d\n",
3372 INSN_UID (twin
), rec
->index
);
3374 twins
= alloc_INSN_LIST (twin
, twins
);
3376 /* Add dependences between TWIN and all appropriate
3377 instructions from REC. */
3380 add_back_forw_dep (twin
, check
, REG_DEP_TRUE
, DEP_TRUE
);
3384 link
= DEP_LINK_NEXT (link
);
3388 check
= DEP_LINK_PRO (link
);
3389 if (BLOCK_FOR_INSN (check
) == rec
)
3397 while (link
!= NULL
);
3399 process_insn_forw_deps_be_in_spec (INSN_FORW_DEPS (insn
), twin
, ts
);
3401 /* Remove all dependencies between INSN and insns in REC. */
3402 for (link
= DEPS_LIST_FIRST (INSN_BACK_DEPS (insn
)); link
!= NULL
;)
3404 check
= DEP_LINK_PRO (link
);
3406 if (BLOCK_FOR_INSN (check
) == rec
)
3408 delete_back_forw_dep (link
);
3410 /* Restart search. */
3411 link
= DEPS_LIST_FIRST (INSN_BACK_DEPS (insn
));
3414 /* Continue search. */
3415 link
= DEP_LINK_NEXT (link
);
3418 while (!deps_list_empty_p (INSN_BACK_DEPS (insn
)));
3420 /* We couldn't have added the dependencies between INSN and TWINS earlier
3421 because that would make TWINS appear in the INSN_BACK_DEPS (INSN). */
3426 twin
= XEXP (twins
, 0);
3427 add_back_forw_dep (twin
, insn
, REG_DEP_OUTPUT
, DEP_OUTPUT
);
3429 twin
= XEXP (twins
, 1);
3430 free_INSN_LIST_node (twins
);
3434 calc_priorities (priorities_roots
);
3435 VEC_free (rtx
, heap
, priorities_roots
);
3438 /* Extends and fills with zeros (only the new part) array pointed to by P. */
3440 xrecalloc (void *p
, size_t new_nmemb
, size_t old_nmemb
, size_t size
)
3442 gcc_assert (new_nmemb
>= old_nmemb
);
3443 p
= XRESIZEVAR (void, p
, new_nmemb
* size
);
3444 memset (((char *) p
) + old_nmemb
* size
, 0, (new_nmemb
- old_nmemb
) * size
);
3448 /* Return the probability of speculation success for the speculation
3456 dt
= FIRST_SPEC_TYPE
;
3461 res
*= (ds_t
) get_dep_weak (ds
, dt
);
3465 if (dt
== LAST_SPEC_TYPE
)
3467 dt
<<= SPEC_TYPE_SHIFT
;
3473 res
/= MAX_DEP_WEAK
;
3475 if (res
< MIN_DEP_WEAK
)
3478 gcc_assert (res
<= MAX_DEP_WEAK
);
3484 Find fallthru edge from PRED. */
3486 find_fallthru_edge (basic_block pred
)
3492 succ
= pred
->next_bb
;
3493 gcc_assert (succ
->prev_bb
== pred
);
3495 if (EDGE_COUNT (pred
->succs
) <= EDGE_COUNT (succ
->preds
))
3497 FOR_EACH_EDGE (e
, ei
, pred
->succs
)
3498 if (e
->flags
& EDGE_FALLTHRU
)
3500 gcc_assert (e
->dest
== succ
);
3506 FOR_EACH_EDGE (e
, ei
, succ
->preds
)
3507 if (e
->flags
& EDGE_FALLTHRU
)
3509 gcc_assert (e
->src
== pred
);
3517 /* Initialize BEFORE_RECOVERY variable. */
3519 init_before_recovery (void)
3524 last
= EXIT_BLOCK_PTR
->prev_bb
;
3525 e
= find_fallthru_edge (last
);
3529 /* We create two basic blocks:
3530 1. Single instruction block is inserted right after E->SRC
3532 2. Empty block right before EXIT_BLOCK.
3533 Between these two blocks recovery blocks will be emitted. */
3535 basic_block single
, empty
;
3538 single
= create_empty_bb (last
);
3539 empty
= create_empty_bb (single
);
3541 single
->count
= last
->count
;
3542 empty
->count
= last
->count
;
3543 single
->frequency
= last
->frequency
;
3544 empty
->frequency
= last
->frequency
;
3545 BB_COPY_PARTITION (single
, last
);
3546 BB_COPY_PARTITION (empty
, last
);
3548 redirect_edge_succ (e
, single
);
3549 make_single_succ_edge (single
, empty
, 0);
3550 make_single_succ_edge (empty
, EXIT_BLOCK_PTR
,
3551 EDGE_FALLTHRU
| EDGE_CAN_FALLTHRU
);
3553 label
= block_label (empty
);
3554 x
= emit_jump_insn_after (gen_jump (label
), BB_END (single
));
3555 JUMP_LABEL (x
) = label
;
3556 LABEL_NUSES (label
)++;
3559 emit_barrier_after (x
);
3561 add_block (empty
, 0);
3562 add_block (single
, 0);
3564 before_recovery
= single
;
3566 if (sched_verbose
>= 2 && spec_info
->dump
)
3567 fprintf (spec_info
->dump
,
3568 ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n",
3569 last
->index
, single
->index
, empty
->index
);
3572 before_recovery
= last
;
3575 /* Returns new recovery block. */
3577 create_recovery_block (void)
3583 added_recovery_block_p
= true;
3585 if (!before_recovery
)
3586 init_before_recovery ();
3588 barrier
= get_last_bb_insn (before_recovery
);
3589 gcc_assert (BARRIER_P (barrier
));
3591 label
= emit_label_after (gen_label_rtx (), barrier
);
3593 rec
= create_basic_block (label
, label
, before_recovery
);
3595 /* Recovery block always end with an unconditional jump. */
3596 emit_barrier_after (BB_END (rec
));
3598 if (BB_PARTITION (before_recovery
) != BB_UNPARTITIONED
)
3599 BB_SET_PARTITION (rec
, BB_COLD_PARTITION
);
3601 if (sched_verbose
&& spec_info
->dump
)
3602 fprintf (spec_info
->dump
, ";;\t\tGenerated recovery block rec%d\n",
3605 before_recovery
= rec
;
3610 /* This function creates recovery code for INSN. If MUTATE_P is nonzero,
3611 INSN is a simple check, that should be converted to branchy one. */
3613 create_check_block_twin (rtx insn
, bool mutate_p
)
3616 rtx label
, check
, twin
;
3620 gcc_assert (ORIG_PAT (insn
)
3622 || (IS_SPECULATION_SIMPLE_CHECK_P (insn
)
3623 && !(TODO_SPEC (insn
) & SPECULATIVE
))));
3625 /* Create recovery block. */
3626 if (mutate_p
|| targetm
.sched
.needs_block_p (insn
))
3628 rec
= create_recovery_block ();
3629 label
= BB_HEAD (rec
);
3633 rec
= EXIT_BLOCK_PTR
;
3638 check
= targetm
.sched
.gen_check (insn
, label
, mutate_p
);
3640 if (rec
!= EXIT_BLOCK_PTR
)
3642 /* To have mem_reg alive at the beginning of second_bb,
3643 we emit check BEFORE insn, so insn after splitting
3644 insn will be at the beginning of second_bb, which will
3645 provide us with the correct life information. */
3646 check
= emit_jump_insn_before (check
, insn
);
3647 JUMP_LABEL (check
) = label
;
3648 LABEL_NUSES (label
)++;
3651 check
= emit_insn_before (check
, insn
);
3653 /* Extend data structures. */
3655 RECOVERY_BLOCK (check
) = rec
;
3657 if (sched_verbose
&& spec_info
->dump
)
3658 fprintf (spec_info
->dump
, ";;\t\tGenerated check insn : %s\n",
3659 (*current_sched_info
->print_insn
) (check
, 0));
3661 gcc_assert (ORIG_PAT (insn
));
3663 /* Initialize TWIN (twin is a duplicate of original instruction
3664 in the recovery block). */
3665 if (rec
!= EXIT_BLOCK_PTR
)
3667 FOR_EACH_DEP_LINK (link
, INSN_RESOLVED_BACK_DEPS (insn
))
3668 if ((DEP_LINK_STATUS (link
) & DEP_OUTPUT
) != 0)
3670 struct _dep _dep
, *dep
= &_dep
;
3672 init_dep (dep
, DEP_LINK_PRO (link
), check
, REG_DEP_TRUE
);
3674 add_back_dep_to_deps_list (INSN_RESOLVED_BACK_DEPS (check
), dep
);
3677 twin
= emit_insn_after (ORIG_PAT (insn
), BB_END (rec
));
3678 extend_global (twin
);
3680 if (sched_verbose
&& spec_info
->dump
)
3681 /* INSN_BB (insn) isn't determined for twin insns yet.
3682 So we can't use current_sched_info->print_insn. */
3683 fprintf (spec_info
->dump
, ";;\t\tGenerated twin insn : %d/rec%d\n",
3684 INSN_UID (twin
), rec
->index
);
3688 ORIG_PAT (check
) = ORIG_PAT (insn
);
3689 HAS_INTERNAL_DEP (check
) = 1;
3691 /* ??? We probably should change all OUTPUT dependencies to
3695 copy_deps_list_change_con (INSN_RESOLVED_BACK_DEPS (twin
),
3696 INSN_RESOLVED_BACK_DEPS (insn
),
3699 if (rec
!= EXIT_BLOCK_PTR
)
3700 /* In case of branchy check, fix CFG. */
3702 basic_block first_bb
, second_bb
;
3707 first_bb
= BLOCK_FOR_INSN (check
);
3708 e
= split_block (first_bb
, check
);
3709 /* split_block emits note if *check == BB_END. Probably it
3710 is better to rip that note off. */
3711 gcc_assert (e
->src
== first_bb
);
3712 second_bb
= e
->dest
;
3714 /* This is fixing of incoming edge. */
3715 /* ??? Which other flags should be specified? */
3716 if (BB_PARTITION (first_bb
) != BB_PARTITION (rec
))
3717 /* Partition type is the same, if it is "unpartitioned". */
3718 edge_flags
= EDGE_CROSSING
;
3722 e
= make_edge (first_bb
, rec
, edge_flags
);
3724 add_block (second_bb
, first_bb
);
3726 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (second_bb
)));
3727 label
= block_label (second_bb
);
3728 jump
= emit_jump_insn_after (gen_jump (label
), BB_END (rec
));
3729 JUMP_LABEL (jump
) = label
;
3730 LABEL_NUSES (label
)++;
3731 extend_global (jump
);
3733 if (BB_PARTITION (second_bb
) != BB_PARTITION (rec
))
3734 /* Partition type is the same, if it is "unpartitioned". */
3736 /* Rewritten from cfgrtl.c. */
3737 if (flag_reorder_blocks_and_partition
3738 && targetm
.have_named_sections
3739 /*&& !any_condjump_p (jump)*/)
3740 /* any_condjump_p (jump) == false.
3741 We don't need the same note for the check because
3742 any_condjump_p (check) == true. */
3744 REG_NOTES (jump
) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP
,
3748 edge_flags
= EDGE_CROSSING
;
3753 make_single_succ_edge (rec
, second_bb
, edge_flags
);
3755 add_block (rec
, EXIT_BLOCK_PTR
);
3758 /* Move backward dependences from INSN to CHECK and
3759 move forward dependences from INSN to TWIN. */
3760 FOR_EACH_DEP_LINK (link
, INSN_BACK_DEPS (insn
))
3762 rtx pro
= DEP_LINK_PRO (link
);
3763 enum reg_note dk
= DEP_LINK_KIND (link
);
3766 /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
3767 check --TRUE--> producer ??? or ANTI ???
3768 twin --TRUE--> producer
3769 twin --ANTI--> check
3771 If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
3772 check --ANTI--> producer
3773 twin --ANTI--> producer
3774 twin --ANTI--> check
3776 If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
3777 check ~~TRUE~~> producer
3778 twin ~~TRUE~~> producer
3779 twin --ANTI--> check */
3781 ds
= DEP_LINK_STATUS (link
);
3783 if (ds
& BEGIN_SPEC
)
3785 gcc_assert (!mutate_p
);
3789 if (rec
!= EXIT_BLOCK_PTR
)
3791 add_back_forw_dep (check
, pro
, dk
, ds
);
3792 add_back_forw_dep (twin
, pro
, dk
, ds
);
3795 add_back_forw_dep (check
, pro
, dk
, ds
);
3798 for (link
= DEPS_LIST_FIRST (INSN_BACK_DEPS (insn
)); link
!= NULL
;)
3799 if ((DEP_LINK_STATUS (link
) & BEGIN_SPEC
)
3801 /* We can delete this dep only if we totally overcome it with
3802 BEGIN_SPECULATION. */
3804 delete_back_forw_dep (link
);
3806 /* Restart search. */
3807 link
= DEPS_LIST_FIRST (INSN_BACK_DEPS (insn
));
3810 /* Continue search. */
3811 link
= DEP_LINK_NEXT (link
);
3815 /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
3818 gcc_assert (!DONE_SPEC (insn
));
3822 ds_t ts
= TODO_SPEC (insn
);
3824 DONE_SPEC (insn
) = ts
& BEGIN_SPEC
;
3825 CHECK_SPEC (check
) = ts
& BEGIN_SPEC
;
3827 if (ts
& BEGIN_DATA
)
3828 fs
= set_dep_weak (fs
, BE_IN_DATA
, get_dep_weak (ts
, BEGIN_DATA
));
3829 if (ts
& BEGIN_CONTROL
)
3830 fs
= set_dep_weak (fs
, BE_IN_CONTROL
, get_dep_weak (ts
, BEGIN_CONTROL
));
3833 CHECK_SPEC (check
) = CHECK_SPEC (insn
);
3835 /* Future speculations: call the helper. */
3836 process_insn_forw_deps_be_in_spec (INSN_FORW_DEPS (insn
), twin
, fs
);
3838 if (rec
!= EXIT_BLOCK_PTR
)
3840 /* Which types of dependencies should we use here is,
3841 generally, machine-dependent question... But, for now,
3846 add_back_forw_dep (check
, insn
, REG_DEP_TRUE
, DEP_TRUE
);
3847 add_back_forw_dep (twin
, insn
, REG_DEP_OUTPUT
, DEP_OUTPUT
);
3853 if (spec_info
->dump
)
3854 fprintf (spec_info
->dump
, ";;\t\tRemoved simple check : %s\n",
3855 (*current_sched_info
->print_insn
) (insn
, 0));
3857 /* Remove all forward dependencies of the INSN. */
3858 link
= DEPS_LIST_FIRST (INSN_FORW_DEPS (insn
));
3859 while (link
!= NULL
)
3861 delete_back_forw_dep (link
);
3862 link
= DEPS_LIST_FIRST (INSN_FORW_DEPS (insn
));
3865 if (QUEUE_INDEX (insn
) != QUEUE_NOWHERE
)
3868 sched_remove_insn (insn
);
3871 add_back_forw_dep (twin
, check
, REG_DEP_ANTI
, DEP_ANTI
);
3874 add_back_forw_dep (check
, insn
, REG_DEP_TRUE
, DEP_TRUE
| DEP_OUTPUT
);
3877 /* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
3878 because it'll be done later in add_to_speculative_block. */
3880 rtx_vec_t priorities_roots
= NULL
;
3882 clear_priorities (twin
, &priorities_roots
);
3883 calc_priorities (priorities_roots
);
3884 VEC_free (rtx
, heap
, priorities_roots
);
3888 /* Removes dependency between instructions in the recovery block REC
3889 and usual region instructions. It keeps inner dependences so it
3890 won't be necessary to recompute them. */
3892 fix_recovery_deps (basic_block rec
)
3895 rtx note
, insn
, jump
, ready_list
= 0;
3896 bitmap_head in_ready
;
3899 bitmap_initialize (&in_ready
, 0);
3901 /* NOTE - a basic block note. */
3902 note
= NEXT_INSN (BB_HEAD (rec
));
3903 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
3904 insn
= BB_END (rec
);
3905 gcc_assert (JUMP_P (insn
));
3906 insn
= PREV_INSN (insn
);
3910 for (link
= DEPS_LIST_FIRST (INSN_FORW_DEPS (insn
)); link
!= NULL
;)
3914 consumer
= DEP_LINK_CON (link
);
3916 if (BLOCK_FOR_INSN (consumer
) != rec
)
3918 delete_back_forw_dep (link
);
3920 if (!bitmap_bit_p (&in_ready
, INSN_LUID (consumer
)))
3922 ready_list
= alloc_INSN_LIST (consumer
, ready_list
);
3923 bitmap_set_bit (&in_ready
, INSN_LUID (consumer
));
3926 /* Restart search. */
3927 link
= DEPS_LIST_FIRST (INSN_FORW_DEPS (insn
));
3931 gcc_assert ((DEP_LINK_STATUS (link
) & DEP_TYPES
) == DEP_TRUE
);
3933 /* Continue search. */
3934 link
= DEP_LINK_NEXT (link
);
3938 insn
= PREV_INSN (insn
);
3940 while (insn
!= note
);
3942 bitmap_clear (&in_ready
);
3944 /* Try to add instructions to the ready or queue list. */
3945 for (link1
= ready_list
; link1
; link1
= XEXP (link1
, 1))
3946 try_ready (XEXP (link1
, 0));
3947 free_INSN_LIST_list (&ready_list
);
3949 /* Fixing jump's dependences. */
3950 insn
= BB_HEAD (rec
);
3951 jump
= BB_END (rec
);
3953 gcc_assert (LABEL_P (insn
));
3954 insn
= NEXT_INSN (insn
);
3956 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn
));
3957 add_jump_dependencies (insn
, jump
);
3960 /* Changes pattern of the INSN to NEW_PAT. */
3962 change_pattern (rtx insn
, rtx new_pat
)
3966 t
= validate_change (insn
, &PATTERN (insn
), new_pat
, 0);
3968 /* Invalidate INSN_COST, so it'll be recalculated. */
3969 INSN_COST (insn
) = -1;
3970 /* Invalidate INSN_TICK, so it'll be recalculated. */
3971 INSN_TICK (insn
) = INVALID_TICK
;
3972 dfa_clear_single_insn_cache (insn
);
3976 /* -1 - can't speculate,
3977 0 - for speculation with REQUEST mode it is OK to use
3978 current instruction pattern,
3979 1 - need to change pattern for *NEW_PAT to be speculative. */
3981 speculate_insn (rtx insn
, ds_t request
, rtx
*new_pat
)
3983 gcc_assert (current_sched_info
->flags
& DO_SPECULATION
3984 && (request
& SPECULATIVE
));
3986 if (!NONJUMP_INSN_P (insn
)
3987 || HAS_INTERNAL_DEP (insn
)
3988 || SCHED_GROUP_P (insn
)
3989 || side_effects_p (PATTERN (insn
))
3990 || (request
& spec_info
->mask
) != request
)
3993 gcc_assert (!IS_SPECULATION_CHECK_P (insn
));
3995 if (request
& BE_IN_SPEC
)
3997 if (may_trap_p (PATTERN (insn
)))
4000 if (!(request
& BEGIN_SPEC
))
4004 return targetm
.sched
.speculate_insn (insn
, request
& BEGIN_SPEC
, new_pat
);
4007 /* Print some information about block BB, which starts with HEAD and
4008 ends with TAIL, before scheduling it.
4009 I is zero, if scheduler is about to start with the fresh ebb. */
4011 dump_new_block_header (int i
, basic_block bb
, rtx head
, rtx tail
)
4014 fprintf (sched_dump
,
4015 ";; ======================================================\n");
4017 fprintf (sched_dump
,
4018 ";; =====================ADVANCING TO=====================\n");
4019 fprintf (sched_dump
,
4020 ";; -- basic block %d from %d to %d -- %s reload\n",
4021 bb
->index
, INSN_UID (head
), INSN_UID (tail
),
4022 (reload_completed
? "after" : "before"));
4023 fprintf (sched_dump
,
4024 ";; ======================================================\n");
4025 fprintf (sched_dump
, "\n");
4028 /* Unlink basic block notes and labels and saves them, so they
4029 can be easily restored. We unlink basic block notes in EBB to
4030 provide back-compatibility with the previous code, as target backends
4031 assume, that there'll be only instructions between
4032 current_sched_info->{head and tail}. We restore these notes as soon
4034 FIRST (LAST) is the first (last) basic block in the ebb.
4035 NB: In usual case (FIRST == LAST) nothing is really done. */
4037 unlink_bb_notes (basic_block first
, basic_block last
)
4039 /* We DON'T unlink basic block notes of the first block in the ebb. */
4043 bb_header
= xmalloc (last_basic_block
* sizeof (*bb_header
));
4045 /* Make a sentinel. */
4046 if (last
->next_bb
!= EXIT_BLOCK_PTR
)
4047 bb_header
[last
->next_bb
->index
] = 0;
4049 first
= first
->next_bb
;
4052 rtx prev
, label
, note
, next
;
4054 label
= BB_HEAD (last
);
4055 if (LABEL_P (label
))
4056 note
= NEXT_INSN (label
);
4059 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
4061 prev
= PREV_INSN (label
);
4062 next
= NEXT_INSN (note
);
4063 gcc_assert (prev
&& next
);
4065 NEXT_INSN (prev
) = next
;
4066 PREV_INSN (next
) = prev
;
4068 bb_header
[last
->index
] = label
;
4073 last
= last
->prev_bb
;
4078 /* Restore basic block notes.
4079 FIRST is the first basic block in the ebb. */
4081 restore_bb_notes (basic_block first
)
4086 /* We DON'T unlink basic block notes of the first block in the ebb. */
4087 first
= first
->next_bb
;
4088 /* Remember: FIRST is actually a second basic block in the ebb. */
4090 while (first
!= EXIT_BLOCK_PTR
4091 && bb_header
[first
->index
])
4093 rtx prev
, label
, note
, next
;
4095 label
= bb_header
[first
->index
];
4096 prev
= PREV_INSN (label
);
4097 next
= NEXT_INSN (prev
);
4099 if (LABEL_P (label
))
4100 note
= NEXT_INSN (label
);
4103 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
4105 bb_header
[first
->index
] = 0;
4107 NEXT_INSN (prev
) = label
;
4108 NEXT_INSN (note
) = next
;
4109 PREV_INSN (next
) = note
;
4111 first
= first
->next_bb
;
4118 /* Extend per basic block data structures of the scheduler.
4119 If BB is NULL, initialize structures for the whole CFG.
4120 Otherwise, initialize them for the just created BB. */
4126 old_last_basic_block
= last_basic_block
;
4128 /* The following is done to keep current_sched_info->next_tail non null. */
4130 insn
= BB_END (EXIT_BLOCK_PTR
->prev_bb
);
4131 if (NEXT_INSN (insn
) == 0
4134 /* Don't emit a NOTE if it would end up before a BARRIER. */
4135 && !BARRIER_P (NEXT_INSN (insn
))))
4137 rtx note
= emit_note_after (NOTE_INSN_DELETED
, insn
);
4138 /* Make insn appear outside BB. */
4139 set_block_for_insn (note
, NULL
);
4140 BB_END (EXIT_BLOCK_PTR
->prev_bb
) = insn
;
4144 /* Add a basic block BB to extended basic block EBB.
4145 If EBB is EXIT_BLOCK_PTR, then BB is recovery block.
4146 If EBB is NULL, then BB should be a new region. */
4148 add_block (basic_block bb
, basic_block ebb
)
4150 gcc_assert (current_sched_info
->flags
& NEW_BBS
);
4154 if (current_sched_info
->add_block
)
4155 /* This changes only data structures of the front-end. */
4156 current_sched_info
->add_block (bb
, ebb
);
4160 Fix CFG after both in- and inter-block movement of
4161 control_flow_insn_p JUMP. */
4163 fix_jump_move (rtx jump
)
4165 basic_block bb
, jump_bb
, jump_bb_next
;
4167 bb
= BLOCK_FOR_INSN (PREV_INSN (jump
));
4168 jump_bb
= BLOCK_FOR_INSN (jump
);
4169 jump_bb_next
= jump_bb
->next_bb
;
4171 gcc_assert (current_sched_info
->flags
& SCHED_EBB
4172 || IS_SPECULATION_BRANCHY_CHECK_P (jump
));
4174 if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next
)))
4175 /* if jump_bb_next is not empty. */
4176 BB_END (jump_bb
) = BB_END (jump_bb_next
);
4178 if (BB_END (bb
) != PREV_INSN (jump
))
4179 /* Then there are instruction after jump that should be placed
4181 BB_END (jump_bb_next
) = BB_END (bb
);
4183 /* Otherwise jump_bb_next is empty. */
4184 BB_END (jump_bb_next
) = NEXT_INSN (BB_HEAD (jump_bb_next
));
4186 /* To make assertion in move_insn happy. */
4187 BB_END (bb
) = PREV_INSN (jump
);
4189 update_bb_for_insn (jump_bb_next
);
4192 /* Fix CFG after interblock movement of control_flow_insn_p JUMP. */
4194 move_block_after_check (rtx jump
)
4196 basic_block bb
, jump_bb
, jump_bb_next
;
4199 bb
= BLOCK_FOR_INSN (PREV_INSN (jump
));
4200 jump_bb
= BLOCK_FOR_INSN (jump
);
4201 jump_bb_next
= jump_bb
->next_bb
;
4203 update_bb_for_insn (jump_bb
);
4205 gcc_assert (IS_SPECULATION_CHECK_P (jump
)
4206 || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next
)));
4208 unlink_block (jump_bb_next
);
4209 link_block (jump_bb_next
, bb
);
4213 move_succs (&(jump_bb
->succs
), bb
);
4214 move_succs (&(jump_bb_next
->succs
), jump_bb
);
4215 move_succs (&t
, jump_bb_next
);
4217 df_mark_solutions_dirty ();
4219 if (current_sched_info
->fix_recovery_cfg
)
4220 current_sched_info
->fix_recovery_cfg
4221 (bb
->index
, jump_bb
->index
, jump_bb_next
->index
);
4224 /* Helper function for move_block_after_check.
4225 This functions attaches edge vector pointed to by SUCCSP to
4228 move_succs (VEC(edge
,gc
) **succsp
, basic_block to
)
4233 gcc_assert (to
->succs
== 0);
4235 to
->succs
= *succsp
;
4237 FOR_EACH_EDGE (e
, ei
, to
->succs
)
4243 /* Remove INSN from the instruction stream.
4244 INSN should have any dependencies. */
4246 sched_remove_insn (rtx insn
)
4248 change_queue_index (insn
, QUEUE_NOWHERE
);
4249 current_sched_info
->add_remove_insn (insn
, 1);
4253 /* Clear priorities of all instructions, that are forward dependent on INSN.
4254 Store in vector pointed to by ROOTS_PTR insns on which priority () should
4255 be invoked to initialize all cleared priorities. */
4257 clear_priorities (rtx insn
, rtx_vec_t
*roots_ptr
)
4260 bool insn_is_root_p
= true;
4262 gcc_assert (QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
);
4264 FOR_EACH_DEP_LINK (link
, INSN_BACK_DEPS (insn
))
4266 dep_t dep
= DEP_LINK_DEP (link
);
4267 rtx pro
= DEP_PRO (dep
);
4269 if (INSN_PRIORITY_STATUS (pro
) >= 0
4270 && QUEUE_INDEX (insn
) != QUEUE_SCHEDULED
)
4272 /* If DEP doesn't contribute to priority then INSN itself should
4273 be added to priority roots. */
4274 if (contributes_to_priority_p (dep
))
4275 insn_is_root_p
= false;
4277 INSN_PRIORITY_STATUS (pro
) = -1;
4278 clear_priorities (pro
, roots_ptr
);
4283 VEC_safe_push (rtx
, heap
, *roots_ptr
, insn
);
4286 /* Recompute priorities of instructions, whose priorities might have been
4287 changed. ROOTS is a vector of instructions whose priority computation will
4288 trigger initialization of all cleared priorities. */
4290 calc_priorities (rtx_vec_t roots
)
4295 for (i
= 0; VEC_iterate (rtx
, roots
, i
, insn
); i
++)
4300 /* Add dependences between JUMP and other instructions in the recovery
4301 block. INSN is the first insn the recovery block. */
4303 add_jump_dependencies (rtx insn
, rtx jump
)
4307 insn
= NEXT_INSN (insn
);
4311 if (deps_list_empty_p (INSN_FORW_DEPS (insn
)))
4312 add_back_forw_dep (jump
, insn
, REG_DEP_ANTI
, DEP_ANTI
);
4316 gcc_assert (!deps_list_empty_p (INSN_BACK_DEPS (jump
)));
4319 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
4321 bb_note (basic_block bb
)
4325 note
= BB_HEAD (bb
);
4327 note
= NEXT_INSN (note
);
4329 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note
));
4333 #ifdef ENABLE_CHECKING
4334 extern void debug_spec_status (ds_t
);
4336 /* Dump information about the dependence status S. */
4338 debug_spec_status (ds_t s
)
4343 fprintf (f
, "BEGIN_DATA: %d; ", get_dep_weak (s
, BEGIN_DATA
));
4345 fprintf (f
, "BE_IN_DATA: %d; ", get_dep_weak (s
, BE_IN_DATA
));
4346 if (s
& BEGIN_CONTROL
)
4347 fprintf (f
, "BEGIN_CONTROL: %d; ", get_dep_weak (s
, BEGIN_CONTROL
));
4348 if (s
& BE_IN_CONTROL
)
4349 fprintf (f
, "BE_IN_CONTROL: %d; ", get_dep_weak (s
, BE_IN_CONTROL
));
4352 fprintf (f
, "HARD_DEP; ");
4355 fprintf (f
, "DEP_TRUE; ");
4357 fprintf (f
, "DEP_ANTI; ");
4359 fprintf (f
, "DEP_OUTPUT; ");
4364 /* Helper function for check_cfg.
4365 Return nonzero, if edge vector pointed to by EL has edge with TYPE in
4368 has_edge_p (VEC(edge
,gc
) *el
, int type
)
4373 FOR_EACH_EDGE (e
, ei
, el
)
4374 if (e
->flags
& type
)
4379 /* Check few properties of CFG between HEAD and TAIL.
4380 If HEAD (TAIL) is NULL check from the beginning (till the end) of the
4381 instruction stream. */
4383 check_cfg (rtx head
, rtx tail
)
4387 int not_first
= 0, not_last
;
4390 head
= get_insns ();
4392 tail
= get_last_insn ();
4393 next_tail
= NEXT_INSN (tail
);
4397 not_last
= head
!= tail
;
4400 gcc_assert (NEXT_INSN (PREV_INSN (head
)) == head
);
4402 gcc_assert (PREV_INSN (NEXT_INSN (head
)) == head
);
4405 || (NOTE_INSN_BASIC_BLOCK_P (head
)
4407 || (not_first
&& !LABEL_P (PREV_INSN (head
))))))
4409 gcc_assert (bb
== 0);
4410 bb
= BLOCK_FOR_INSN (head
);
4412 gcc_assert (BB_HEAD (bb
) == head
);
4414 /* This is the case of jump table. See inside_basic_block_p (). */
4415 gcc_assert (LABEL_P (head
) && !inside_basic_block_p (head
));
4420 gcc_assert (!inside_basic_block_p (head
));
4421 head
= NEXT_INSN (head
);
4425 gcc_assert (inside_basic_block_p (head
)
4427 gcc_assert (BLOCK_FOR_INSN (head
) == bb
);
4431 head
= NEXT_INSN (head
);
4432 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (head
));
4436 if (control_flow_insn_p (head
))
4438 gcc_assert (BB_END (bb
) == head
);
4440 if (any_uncondjump_p (head
))
4441 gcc_assert (EDGE_COUNT (bb
->succs
) == 1
4442 && BARRIER_P (NEXT_INSN (head
)));
4443 else if (any_condjump_p (head
))
4444 gcc_assert (/* Usual case. */
4445 (EDGE_COUNT (bb
->succs
) > 1
4446 && !BARRIER_P (NEXT_INSN (head
)))
4447 /* Or jump to the next instruction. */
4448 || (EDGE_COUNT (bb
->succs
) == 1
4449 && (BB_HEAD (EDGE_I (bb
->succs
, 0)->dest
)
4450 == JUMP_LABEL (head
))));
4452 if (BB_END (bb
) == head
)
4454 if (EDGE_COUNT (bb
->succs
) > 1)
4455 gcc_assert (control_flow_insn_p (head
)
4456 || has_edge_p (bb
->succs
, EDGE_COMPLEX
));
4460 head
= NEXT_INSN (head
);
4466 while (head
!= next_tail
);
4468 gcc_assert (bb
== 0);
4471 /* Perform a few consistency checks of flags in different data structures. */
4473 check_sched_flags (void)
4475 unsigned int f
= current_sched_info
->flags
;
4477 if (flag_sched_stalled_insns
)
4478 gcc_assert (!(f
& DO_SPECULATION
));
4479 if (f
& DO_SPECULATION
)
4480 gcc_assert (!flag_sched_stalled_insns
4482 && spec_info
->mask
);
4484 #endif /* ENABLE_CHECKING */
4486 #endif /* INSN_SCHEDULING */